Franklin's blog postshttps://franklin.dyer.meThe blog of Franklin Pezzuti Dyer.http://www.rssboard.org/rss-specificationpython-feedgenMon, 11 Nov 2024 22:41:13 +0000Lessons from implementing Sokoban for the Intel 8080https://franklin.dyer.me/post/231<html dir="ltr" lang="en">
<head>
<title>Franklin Pezzuti Dyer</title>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]},
processEscapes: true,
menuSettings: { inTabOrder: false },
"AssistiveMML": {
disabled: false,
styles: {
".MJX_Assistive_MathML": {
position:"absolute!important",
clip: (MathJax.Hub.Browser.isMSIE && (document.documentMode||0) < 8 ?
"rect(1px 1px 1px 1px)" : "rect(1px, 1px, 1px, 1px)"),
padding: "1px 0 0 0!important",
border: "0!important",
height: "1px!important",
width: "1px!important",
overflow: "hidden!important",
display:"block!important"
}
}
}
});
</script>
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no, type=text/html" charset="UTF-8">
<link rel="stylesheet" href="/css/style.css">
<link rel="stylesheet" href="/css/style-local-.css">
<script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML' async></script>
</head>
<body>
<h2>Franklin Pezzuti Dyer</h2>
<div>
<span class="hidden">
<a href="#begin-content">Skip to page content</a>
</span>
<a id="pagenav"></a>
<a href="/">Home</a>
<a href="/posts">Posts</a>
<a href="/post/1">CV</a>
<a href="/post/2">Contact</a>
<a href="/post/216">People</a>
<a href="/rss/en">RSS</a>
</div>
<hr>
<span class="hidden">
<a href="#pagenav">Skip to navigation</a>
</span>
<a id="begin-content"></a>
<div id="table-of-contents"></div>
<div id="post-body">
<h2>Lessons from implementing Sokoban for the Intel 8080</h2>
<p>For a while, I've had the urge to find a project that would give me an excuse to learn more about how computer architectures work at a low level. This is a topic I've been meaning to review since I took a very poorly-taught and unsatisfying <a href="https://catalog.unm.edu/catalogs/2021-2022/courses/CS/341L.html">computer architecture class</a> at UNM. I do <a href="https://franklin.dyer.me/post/209">enjoy programming in Brainfuck</a>, but it's classified as an esolang for a reason, and it's closer to the mathematical construct of a Turing Machine than a real-life CPU. Programming something in assembly has always been an option but I'd been at a loss for what to program.</p>
<p>Several weeks ago I stumbled across <a href="https://franklin.dyer.me/post/209">the Emulator 101</a> website and knew immediately that it was what I had been looking for. What better way to learn how a CPU works than to implement all of the operations explicitly in C? The website has an extremely helpful and detailed tutorial, and there's a very clear payoff: you can run the original Space Invaders binary on your computer! The Intel 8080 isn't the same as modern computer architectures, but at the very least it's something that people have used to write "real" programs.</p>
<p>After several weeks of painstaking debugging, I was able to run Space Invaders:</p>
<p><center><img alt="Fig 1" src="/img/2024-08-10-Fig1.png" /></center> </p>
<p>My 8080 emulator was probably one of the most difficult things I've ever had to debug, and using the Space Invaders binary as test code wouldn't have been feasible without <a href="http://computerarcheology.com/Arcade/SpaceInvaders/Code.html">these detailed annotations</a>. Getting the flags right was the trickiest part, particularly because they aren't documented very well for some of the instructions listed in the Intel 8080 programming manual. I also found the binary for another old Taito game called Lunar Rescue, which I was also able to run and play (but not before it exposed more bugs in my emulator):</p>
<p><center><img alt="Fig 2" src="/img/2024-08-10-Fig2.png" /></center> </p>
<p>I was also able to run an adorable predecessor of Space Invaders called Gunfight:</p>
<p><center><img alt="Fig 3" src="/img/2024-08-10-Fig3.png" /></center></p>
<p>I won't write any more about implementing the emulator other than just to say that the Emulator 101 is a fantastic guide and I highly recommend it. All the time I spent poring over the annotated source code of Space Invaders and trying to reverse-engineer bits and pieces of Lunar Rescue and Gunfight (mainly to figure out how the game controls and sound effects map to the bits of the <code>IN</code> and <code>OUT</code> ports) made me want to try writing something myself. I'm a huge fan of <a href="https://en.wikipedia.org/wiki/Sokoban">Sokoban</a> puzzles, so that's what I decided to tackle.</p>
<p>You can find my partial Intel 8080 emulator in <a href="https://en.wikipedia.org/wiki/Sokoban">this Github repo</a>, along with the binaries for Space Invaders, Lunar Rescue, Gunfight and my Sokoban game, and a <code>Makefile</code> that can be used to compile and run them through the emulator. Here's a screenshot of one of my favorite levels:</p>
<p><center><img alt="Fig 4" src="/img/2024-08-10-Fig4.png" /></center></p>
<p>Sokoban is a fairly simple grid-based game, so in the spirit of getting as much intuition about low-level programming as possible, I decided to take on the challenge of writing the game binary directly rather than using an assembler for the Intel 8080 architecture. (No, I promise I'm not a masochist.) I've been using a hex editor called <a href="https://github.com/HexFiend/HexFiend">Hex Fiend</a> to write the binary. This has been a really interesting exercise that has stretched my brain much differently than a high-level coding project.</p>
<p>I'm not going to get technical about the structure of my code. If you'd like a peek at the nuts and bolts, <a href="/file/sokoban-intel8080-code.txt">here's a link to my personal notes</a>. Below are just some lessons I'm taking away from my first Intel 8080 program.</p>
<hr>
<p><strong>Keeping notes is extremely important.</strong> In my opinion this is important in any kind of programming, and I take copious amounts of notes for most of my coding projects, but in a high level language you can often get away with coding for a long time before any kind of documentation is needed. You can even write self-documenting code. Not so when programming in assembly.</p>
<p>This is not just because higher-level languages offer more opportunities to give things meaningful names as a hint to yourself. In assembly programming you can kiss goodbye the referential transparency offerred by function calls in a high-level language. Sure, you can make <em>some</em> of your functions <em>mostly</em> referentially transparent by using <code>PUSH</code> and <code>POP</code> generously, but this is a lot of extra instructions and you will be tempted to cut corners (which is not necessarily a bad thing when you're using a hex editor to write your code one <a href="https://en.wikipedia.org/wiki/Nibble">nibble</a> at a time).</p>
<p>Different computer architectures have their own <a href="https://en.wikipedia.org/wiki/X86_calling_conventions">calling conventions</a> dictating, among other things, which registers must be preserved by function calls and which ones are allowed to be "volatile". This is essential for code interoperability. If you're just writing a self-contained game, you may not need your code to be interoperable with <em>anyone else's</em> code, but you do need to <em>remember</em> which registers each of your functions uses as arguments, which registers it leaves untouched (or pops back to their original state after using them), and which registers it uses to pass output back to the caller. Hence the importance of detailed notes.</p>
<p>Here's an example of "calling conventions" that I wrote for one of my helper functions:</p>
<div class="code"><pre><code>
ROUTINE DRAWTILERUN 0x0080
Calling convention for drawTileRun:
- HL must contain the address of the sprite ID sequence
- Format: 1b length of sequence, followed by L bytes
- (B,C) must be the coordinates on the 32x32 screen to start drawing
- After calling, HL points to the last element of the sequence
- After calling, (B,C) are the coords of the cell AFTER the last cell
- E is not affected
</code></pre></div>
<hr>
<p><strong>Leave lots of padding.</strong> If you're coding in assembly and have the ability to label lines of code and write jump instructions that jump to specific labels, then the assembler is taking care of this issue for you and you don't need to worry about it. As mentioned earlier, I opted to <a href="https://www.nytimes.com/2024/07/17/style/rawdog-flights-term.html">raw dog it</a>, which introduced an interesting complication. When you go back to make edits to your code by adding or deleting instructions, the memory locations of <em>all subsequent instructions</em> are changed. This means that any existing instructions from the <code>JMP</code> or <code>CALL</code> families that point to addresses in that region will probably break, pointing to a different instruction.</p>
<p>Obviously the solution is not to manually go through your code and update all of the <code>JMP</code> or <code>CALL</code> instructions every time you make an edit that causes an address shift. The solution is also not to pretend that you will be able to write all of your code correctly the first time and never make any edits.</p>
<p>Instead, you can leave a lot of "slack space" at the end of each of your functions in the form of a long sequence of <code>NOP</code>s. This way, when you need to edit a function by adding or subtracting a few bytes, you can use these <code>NOP</code> bytes as a buffer so that the subsequent functions can stay at the same address. You might choose to do this not only for the beginnings of functions, but also for specific steps within a function that will be the target of a <code>JMP</code> instruction elsewhere in the function, to further insure against address shifts within the function (especially if your function is very long). </p>
<p>But this does mean that you will have to take your best guess about <em>at most</em> how long each of your functions will end up being after the inevitable refactoring. Good luck. In a pinch, you can always jump to a code snippet stored elsewhere and then jump back.</p>
<hr>
<p><strong>You will need to sacrifice efficiency for convenience.</strong> By "efficiency", I am referring more to memory efficiency than speed. For a simple game like Space Invaders or my Sokoban game, the computations aren't very intensive, and emulation in C is fast. My game also isn't very large, but I do think it's a bit more bloated than the Space Invaders binary, mainly because redundant data can save you a lot of time if you let it.</p>
<p>Here's an example of a tradeoff that I faced while implementing Sokoban. In my implementation, the player and the crates are stored by their coordinates on the game board, whereas the "tiles" (walls, targets and empty spaces) are stored in what is essentially a 2D array. Since there are only 3 kinds of tiles, in principle, you only need 2 bits to specify the value of a single tile. This means that there is a perfectly natural way of storing the tile map for a Sokoban level with $N$ tiles using only about $N/4$ bytes.</p>
<p>But this is not what I did. Instead, I used one byte for each tile. All of the 8x8 game sprites are stored sequentially in a region of memory starting at <code>0x2000</code>, and for each byte of the tile map, I used the <em>index</em> of the corresponding sprite in this list of sprites. This is absurdly inefficient, since I only really use three different values for these bytes, namely <code>0x24</code> (wall), <code>0x2c</code> (empty space) and <code>0x27</code> (target). This choice still makes me cringe a little, but the truth is that I probably would have undergone several more hours of frustrated debugging if I had gone the route of combining four two-bit tile codes in each byte of the tile map, since accessing a random tile in the tile map by its index $n$ would require finding byte $n/4$ in the tile map and shifting it by $2\cdot (n\bmod 4)$ bits to extract the correct bit pair. Drawing said tile would then require translating the two-bit tile code into the correct sprite index, and <em>then</em> drawing the sprite at that index.</p>
<p>No thanks. In my current implementation, to draw the tile at a given index, I just have to navigate to the beginning of the tile map, add the tile index to <code>HL</code>, and then draw the tile whose index is stored there. In exchange for this convenience, my level data is more bloated than it could be.</p>
<p>If you're not convinced, and still think I should have gone with the two-bits-per-tile idea, here's my response: theoretically, it's also possible to devise a code that uses no more than $\approx \log_2(3)\cdot N/8$ or approximately $N/5$ bytes to store the values of $N$ tiles each of which can take on one of $3$ possible values. I think it's more clear that this level of compression would be excessive for a silly Sokoban game - it all depends on what balance you choose to strike.</p>
<hr>
<p><strong>When it comes to modularity, pick your battles carefully.</strong> If you decide to undertake this exercise with as few high-level crutches as I have, you will need to force your inner software developer to take a backseat while you program. You may even have to tie up, gag and blindfold your inner software developer in the backseat. Because if you insist on making your program modular, this will take a <em>looong</em> time.</p>
<p>I did not set out to make anything particularly modular or extensible. There are definitely places where I could have used another layer of indirection to make certain game mechanics easier to change, but chose not to (in part because I was just ready to be done with the damn thing).</p>
<p>However, there are certain places where extensibility is more valuable than others. I do not anticipate coming back to this code and making significant changes to the game mechanics. But I could definitely see myself coming back to add more Sokoban puzzles at some point, so I'm trying to make it easy to add new levels to the data section of memory with as few changes to the code section as possible.</p>
<hr>
<p><strong>Code is data.</strong> Some high-level languages highlight the fact that "code" and "data" are just two ways of looking at the same thing. (I'm thinking of Scheme.) But nothing rubs your nose in this fact like writing your executable code by hand in the same binary file as your strings, game sprites and video memory map. If you screw up and forget to <code>RET</code> at the end of a function, the program counter may run off and try to execute whatever happens to be stored in video memory or beyond.</p>
<p>Some of the funniest bugs have come from my PC ending up somewhere it wasn't supposed to be. Sometimes this simply crashes the game by trying to execute a nonexistent CPU instruction. But other times, it wreaks complete havoc on the game. I've seen this pixel salad many times, almost always because I somehow failed to keep my PC within the code section of my memory:</p>
<p><center><img alt="Fig 5" src="/img/2024-08-10-Fig5.png" /></center> </p>
<p>This one is very puzzling:</p>
<p><center><img alt="Fig 6" src="/img/2024-08-10-Fig6.png" /></center> </p>
<p>And this ominous slow-moving memory corruption was pretty funny to watch:</p>
<p><center><img alt="Fig 7" src="/img/2024-08-10-Fig7.png" /></center> </p>
</div>
<script src="/js/toc.js"></script>
<br>
<a href="/">back to home page</a>
<hr>
<div id="license-statement">The posts on this website are licensed under <a href="https://creativecommons.org/licenses/by-nc/4.0/">CC-by-NC 4.0</a>.</div>
<div id="notbyai"><a href="https://notbyai.fyi/"><img src="/img/written-by-human.png"/><img src="/img/illustrated-by-human.png"/></a></div>
<script src="/js/post_proc.js"></script>
</body>
</html>
Sat, 10 Aug 2024 00:00:00 +0000Monodromy in graphs and spaceshttps://franklin.dyer.me/post/232<html dir="ltr" lang="en">
<head>
<title>Franklin Pezzuti Dyer</title>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]},
processEscapes: true,
menuSettings: { inTabOrder: false },
"AssistiveMML": {
disabled: false,
styles: {
".MJX_Assistive_MathML": {
position:"absolute!important",
clip: (MathJax.Hub.Browser.isMSIE && (document.documentMode||0) < 8 ?
"rect(1px 1px 1px 1px)" : "rect(1px, 1px, 1px, 1px)"),
padding: "1px 0 0 0!important",
border: "0!important",
height: "1px!important",
width: "1px!important",
overflow: "hidden!important",
display:"block!important"
}
}
}
});
</script>
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no, type=text/html" charset="UTF-8">
<link rel="stylesheet" href="/css/style.css">
<link rel="stylesheet" href="/css/style-local-.css">
<script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML' async></script>
</head>
<body>
<h2>Franklin Pezzuti Dyer</h2>
<div>
<span class="hidden">
<a href="#begin-content">Skip to page content</a>
</span>
<a id="pagenav"></a>
<a href="/">Home</a>
<a href="/posts">Posts</a>
<a href="/post/1">CV</a>
<a href="/post/2">Contact</a>
<a href="/post/216">People</a>
<a href="/rss/en">RSS</a>
</div>
<hr>
<span class="hidden">
<a href="#pagenav">Skip to navigation</a>
</span>
<a id="begin-content"></a>
<div id="table-of-contents"></div>
<div id="post-body">
<script type="text/javascript" src="/js/jsxgraphcore.js"></script>
<p><link rel="stylesheet" href="/css/jsxgraph.css"></p>
<script type="text/javascript" src="/js/fraction.min.js"></script>
<script type="text/javascript" src="/js/complex.min.js"></script>
<script type="text/javascript" src="/js/quaternion.min.js"></script>
<script type="text/javascript" src="/js/polynomial.min.js"></script>
<script type="text/javascript" src="/js/poly-root-toy.js"></script>
<h2>Monodromy in graphs and spaces</h2>
<h3>Crate permutations in Sokoban <a id="toc-section-1" class="toc-section"></a></h3>
<p>My <a href="/post/231">most recent obsession project</a> has given me cause to think about Sokoban puzzles again, which are an old favorite of mine. I've also had <a href="/post/217">group theory</a> <a href="/post/229">on the mind</a> <a href="/post/230">recently</a>, and having both of these topics rattling around in my brain at once gave rise to another interesting (if incredibly esoteric) idea. What if we could define a group action corresponding to a Sokoban level that describes the ways in which the level's crates can be permuted?</p>
<p>Here's what I came up with. Consider a Sokoban level in which each of the $n$ crates is already on top of a target, and the player is in some specific position $(x,y)$ on the grid. Let the crates be labelled $1,2,\cdots,n$. We can say that a specific permutation $\sigma\in S_n$ is <em>realizable</em> in this Sokoban arrangement if there is a valid sequence of moves by the player that permutes the crates as described by $\sigma$ (so that they all end end up on targets again, but with different crates on different targets) and the player ends up back at $(x,y)$.</p>
<p>I claim that the collection of all realizable configurations for a given Sokoban arrangement forms a <em>group</em>, in particular a subgroup of $S_n$, which describes how the crates can be "shuffled". To prove this, we need to argue that (1) the composition of any two realizable permutations is also realizable, and (2) the inverse of any realizable permutation is realizable.</p>
<p>To see why (1) is true, suppose that $\sigma$ and $\tau$ are two realizable permutations such that are realized by the respective sequences of moves $\mu_1,\cdots,\mu_i$ and $\nu_1,\cdots,\nu_j$, where each $\mu$ and $\nu$ corresponds to one of the four possible player movements "up, down, left, right". Since the sequence $\mu_1,\cdots,\mu_i$ brings the player back to the position $(x,y)$ by definition, executing the sequence of moves $\mu_1,\cdots,\mu_i$ <em>followed by</em> the sequence of moves $\nu_1,\cdots,\nu_j$ will also bring the player back to the position $(x,y)$, and will have the effect of applying the permutation $\sigma$ <em>followed by</em> the permutation $\tau$ to the level's crates, effectively applying the permutation $\tau\sigma$. This means that $\tau\sigma$ is also realizable. (Note that the condition of the player returning to their starting position is essential for composability, because executing the same sequence of moves from a different starting position might have a different outcome.)</p>
<p>To see why (2) is true, suppose $\sigma$ is a realizable permutation. It belongs to $S_n$, where $n\in\mathbb N$ is the finite number of crates in the level. Because $S_n$ is finite, $\sigma$ must have finite order. If its order is $k\in\mathbb N$, so that $\sigma^k = e$, the identity permutation, then we have that $\sigma\cdot \sigma^{k-1} = \sigma^{k-1}\cdot \sigma = e$, meaning that $\sigma^{k-1}$ is the inverse of $\sigma$ (and is also realizable by (1)). That is, to invert a given permutation of the crates realized by a certain sequence of moves, you just have to repeat that same sequence of moves "enough times".</p>
<p>Let's look at a couple of examples. (I'm using the <a href="https://www.puzzlescript.net">Puzzlescript</a> replica of Sokoban to make these examples, as well as <a href="https://www.puzzlescript.net/Documentation/gifs.html">generate the GIFs</a>.) First, consider this arrangement involving $3$ crates:</p>
<p><center><img alt="Fig 1" src="/img/2024-08-30-Fig1.png" /></center></p>
<p>The following sequence of moves swaps the two crates on the left, so we can say that it corresponds to the permutation $\sigma = (12)$:</p>
<p><center><img alt="Fig 2" src="/img/2024-08-30-Fig2.gif" /></center></p>
<p>And this sequence of moves swaps the two crates on the right, so we can say that it corresponds to the permutation $\sigma = (23)$:</p>
<p><center><img alt="Fig 3" src="/img/2024-08-30-Fig3.gif" /></center></p>
<p>These two transpositions together generate the entire symmetric group $S_3$, that is, all possible permutations of three crates. Thus, we can say that the group of realizable permutations for this arrangement is $S_3$.</p>
<p>Here's another arrangement to consider:</p>
<p><center><img alt="Fig 4" src="/img/2024-08-30-Fig4.png" /></center></p>
<p>I designed this arrangement specifically to have the permutation group $C_3$, the group of cyclic permutations on $3$ elements. If you play around with this level, you should be able to convince yourself that the shape of the level allows you to cyclically permute the crates, like this:</p>
<p><center><img alt="Fig 5" src="/img/2024-08-30-Fig5.gif" /></center></p>
<p>but does not allow you to transpose any two crates without moving the third crate. I think this kind of level design can be generalized to manifest arbitrary cyclic groups $C_n$ as groups of realizable permutations of Sokoban arrangements. For instance, here's an arrangement for $C_4$:</p>
<p><center><img alt="Fig 6" src="/img/2024-08-30-Fig6.png" /></center></p>
<p>I'm also pretty sure - but not completely convinced - that the group action associated with the following arrangement is the transitive action of $A_4$ on the four crates:</p>
<p><center><img alt="Fig 7" src="/img/2024-08-30-Fig7.png" /></center></p>
<p>I'd like to see some other interesting transitive group actions realized as groups of permutations on Sokoban crates. I've been trying to come up with an arrangement whose associated group action is the transitive action of the Klein four-group $V$ on 4 elements, but no luck so far.</p>
<p>(Psst! If you manage to come up with any Sokoban arrangements with other interesting associated group actions, I'll gladly add them to this blog post, along with an attribution.)</p>
<h3>Monodromy with graphs as state-spaces <a id="toc-section-2" class="toc-section"></a></h3>
<p>A natural question at this point is whether this construction can be generalized from Sokoban to other puzzle games. One way of describing puzzle games like Sokoban that is pretty agnostic to the type of puzzle and easily generalizable is with a <em>state graph</em>. This is a directed graph $G$ in which each vertex represents a particular state of the game, and each directed edge represents a valid "move" from one state to the next. These state graphs can be enormous, but here's what just a little piece of the state graph of a Sokoban puzzle might look like:</p>
<p><center><img alt="Fig 8" src="/img/2024-08-30-Fig8.png" /></center></p>
<p>Any playable sequence of moves in the game will correspond to a <em>path</em> in the state graph of the game. If a sequence of moves brings the game back to the same state that it started in, it corresponds to a <em>loop</em> or a <em>cycle</em> in the graph. It turns out that the collection of loops in a graph that start and end at the same point can be endowed with a group structure that is directly analogous to the <a href="https://en.wikipedia.org/wiki/Fundamental_group#Graphs">fundamental group</a> from topology. Perhaps this is related to the group structure we discovered for Sokoban arrangements?</p>
<p>You might have noticed that there is some ambiguity in how we've described the "state graph" for a Sokoban puzzle. We have not specified whether the crates are "distinguishable" or "indistinguishable" in the state graph. If the player carries out a sequence of moves that swaps two of the boxes and then returns to the starting position, have they looped back to their starting node in the state graph, or have they travelled to a different node? For instance, is this sequence of moves a loop...</p>
<p><center><img alt="Fig 9" src="/img/2024-08-30-Fig9.png" /></center></p>
<p>...or is it a path that does not wrap around?</p>
<p><center><img alt="Fig 10" src="/img/2024-08-30-Fig10.png" /></center></p>
<p>Depending on whether or not we discriminate between the crates, our state graph can be one of two different graphs. The state graph $G$ that we get by treating the crates as indistinguishable (in which the above sequence of moves is a loop) has only one-sixth as many nodes as the state graph $H$ that we get by treating the crates as unique (in which the above sequence of moves is not a loop). As a matter of fact, we can define a surjective function between these graphs $f:H\to G$ that "forgets" the identities of each crate, so that each node of $G$ is the image of exactly $6$ different nodes of $H$, and these preimages are the $6$ different labellings of the $3$ crates. More generally, if $G$ is the state graph of a Sokoban puzzle with $n$ <em>unlabeled</em> crates and $H$ is the state graph of a Sokoban puzzle with $n$ <em>labeled</em> crates, then the "forgetful" mapping $f:H\to G$ covers each node of $G$ with $n!$ preimages.</p>
<p>This "label-forgetting" function $f$ has the handy property of being a <a href="https://en.wikipedia.org/wiki/Covering_graph">graph covering</a>. (You should click on that link, the Wikipedia page on covering graphs is fantastic.) Graph coverings have some very interesting properties. One interesting property is the <strong>path lifting property</strong>: for any path $p$ in $G = (V,E)$ starting at the node $v_0 = V$, and for any given preimage $\tilde{v_0}$ of $v$ under the covering $f$, there exists a unique preimage $\tilde{p}$ of the path $p$ which starts at the node $\tilde{v_0}$. In the context of state graphs of Sokoban puzzles, this roughly says that if we know the way that the crates are initially labelled, and we know the sequence of moves that is executed on the unlabelled crates, then we can also deduce the labelling of the crates after all of the moves are executed.</p>
<p>This has a very interesting implication: a graph covering $f:G\to H$ gives rise to a group homomorphism $\tilde{f}:\pi(H)\to\pi(G)$ between the fundamental groups of the two graphs. This works because each loop in $H$ is projected down onto a loop in $G$ by the covering $f$. However, not every loop in $G$ lifts to a loop in $H$, meaning that $\tilde{f}$ may not be (and often isn't) a surjection.</p>
<p>Here comes the punch line: the crate permutation group that we described earlier is precisely the quotient group $\pi(G)/\text{im}(\tilde{f})$. (Can you convince yourself that $\text{im}(\tilde{f})\trianglelefteq \pi(G)$?) Intuitively, a quotient group is a construction whereby we take an existing group and insist that a certain subgroup is actually trivial - so, by quotienting $\pi(G)$ by $\text{im}(\tilde{f})$, we are essentially taking the group of loops in the state graph of a Sokoban level (which is always a free group, hence infinite) and insisting that the paths that don't swap any of the crates are trivial. This causes the infinite fundamental group $\pi(G)$ to "collapse" into a group that only accounts for how the crates are be acted upon.</p>
<p>Given a graph covering $f:H\to G$, we will call the group produced by the above construction the <strong>monodromy group</strong> of that graph covering. To be honest, I don't have a source to cite for this definition, but it seems like a natural piece of terminology to use given the way that fundamental groups are defined for both topological spaces to graphs, and the way that the monodromy group is defined for topological spaces (a bit more on this in the next section).</p>
<p>The nice thing about this definition is that is generalizes the group construction from specifically Sokoban to many different puzzles. For example, it can be applied to the famous <a href="https://en.wikipedia.org/wiki/15_puzzle">15 puzzle</a>, where the graph $H$ consists of $16!$ vertices (in two connected components) and the graph $G$ is the space of states that the puzzles can occupy <em>ignoring</em> how the tiles are labelled:</p>
<p><center><img alt="Fig 11" src="/img/2024-08-30-Fig11.png" /></center></p>
<p>The graph $H$ that covers this is unimaginably huge. For the smaller $2\times 3$ variation of this puzzle, I can at least begin to draw a small piece of the covering graph (which has $2$ components and $720$ nodes in all):</p>
<p><center><img alt="Fig 12" src="/img/2024-08-30-Fig12.png" /></center></p>
<p>There's a lot more to say about covering graphs, but I'll leave it there for now, in favor of talking just a little about what monodromy means in topological spaces. Not that topological spaces give any particular insights into Sokoban - I just think the connection between the two is neat! If you want to think more about graph monodromy, I challenge you to try coming up with graph coverings that have specific prescribed monodromy groups, as we started doing with the Sokoban groups. (The problem is a lot easier for arbitrary graphs, and the notion of the <a href="https://en.wikipedia.org/wiki/Cayley_graph">Cayley Graph</a> of a group is very helpful.)</p>
<h3>Monodromy with complex covering spaces <a id="toc-section-3" class="toc-section"></a></h3>
<p>The "real" definition of a <strong>monodromy group</strong> comes from topology, and the study of <a href="https://en.wikipedia.org/wiki/Covering_space">covering spaces</a> of topological spaces. I won't get into the weeds with rigorous definitions and theorems, but intuitively speaking a covering of topological spaces is a way of "folding" a topological space upon itself continuously to "lay down flat" on top of another topological space. This could happen in a trivial way, like if several copies of a topological space $X$ were stacked on top of each other like pancakes. Here's an example where $X=\mathbb S^1$ is the circle:</p>
<p><center><img alt="Fig 13" src="/img/2024-08-30-Fig13.png" /></center></p>
<p>This is a "triple-covering" because exactly three points in the domain space map onto every single point in the codomain space. But here's a different triple covering of the circle:</p>
<p><center><img alt="Fig 14" src="/img/2024-08-30-Fig14.png" /></center></p>
<p>This is actually a covering of $\mathbb S^1$ by $\mathbb S^1$ <em>itself</em> - the circle can triple-cover itself. Pardon the bad drawing... if you prefer to think of this covering in symbolic terms, the covering map sends each point $(\cos\vartheta,\sin\vartheta)$ in the domain to the point $(\cos 3\vartheta, \sin 3\vartheta)$ in the codomain. My point is that the more interesting topological coverings are the ones that less like stacked pancakes and more like a single connected space that is "twisted" upon itself.</p>
<p>Topological coverings $f:Y\to X$ have a <strong>path lifting</strong> property just like the one that I mentioned earlier about graphs: given any path $\gamma$ in the codomain space $X$ starting at $x\in X$, and any base point $y\in Y$ in the domain space that is a preimage of $x$, there is a unique path $\tilde{\gamma}$ in $Y$ that starts at $y$ and maps down onto $\gamma$. Here's what this looks like for a particular base point and path in the trivial "pancake" triple-covering of the circle:</p>
<p><center><img alt="Fig 15" src="/img/2024-08-30-Fig15.png" /></center></p>
<p>and here's what it looks like in the "twisted" triple-covering of the circle:</p>
<p><center><img alt="Fig 16" src="/img/2024-08-30-Fig16.png" /></center></p>
<p>Something cool is <em>fundamentally different</em> about the twisted covering. In the pancake covering, if the path $\gamma$ in the codomain happens to be a loop, then it will always lift to a loop in the domain:</p>
<p><center><img alt="Fig 17" src="/img/2024-08-30-Fig17.png" /></center></p>
<p>But if $\gamma$ is a loop in the twisted covering, it <em>might not</em> lift to a loop. For instance, a single loop around the circle in the twisted covering lifts to a path that takes $y\in X$ to a <em>different</em> preimage $y'$ of $x$:</p>
<p><center><img alt="Fig 18" src="/img/2024-08-30-Fig18.png" /></center></p>
<p>And guess what? If we had used that preimage $y'$ as our basepoint, the corresponding lift of $\gamma$ would terminate at yet <em>another</em> preimage of $x$:</p>
<p><center><img alt="Fig 19" src="/img/2024-08-30-Fig19.png" /></center></p>
<p>The set of all preimages of $x$ under some covering is sometimes called the <strong>fiber</strong> of $x$. The general takeaway from this is as follows: <em>a loop in the codomain of a topological covering induces a permutation on the fiber of its basepoint</em>. In particular, if $f:Y\to X$ is the covering and $x\in X$ is some base point for a loop $\gamma$ in $X$, the permutation $\sigma:f^{-1}(x)\to f^{-1}(x)$ sends each point $y\in f^{-1}(x)$ to the <em>endpoint</em> of the unique lift $\tilde{\gamma}$ of $\gamma$ with $y$ as its <em>starting point</em>. These permutations together comprise a group action on the fiber $f^{-1}(x)$, which is how we define the <strong>monodromy group</strong> of a topological covering.</p>
<p><center><img alt="Fig 20" src="/img/2024-08-30-Fig20.png" /></center></p>
<p>Anyhow, I don't expect to do the idea justice with my pictures, and anything much more complicated than a twisted covering of $\mathbb S^1$ is pretty near impossible to draw. </p>
<p>So instead I've given several <em>explicit</em> examples of topological coverings below, along with some cute little graph widgets (Javascript code stolen from <a href="https://duetosymmetry.com/tool/polynomial-roots-toy/">this page</a>) allowing you to play with monodromy and see exactly how specific loops in the complex plane permute the preimages of a point under different rational function coverings $f(z)$. Rational functions on $\mathbb C$ (or rather, the <a href="https://en.wikipedia.org/wiki/Riemann_sphere">Riemann Sphere</a>) are fantastic ways of constructing interesting covering spaces, since the <a href="https://en.wikipedia.org/wiki/Fundamental_theorem_of_algebra">Fundamental Theorem of Algebra</a> gives nice guarantees about how big the fiber of each point under a rational function $f(z)$ will be, <em>except</em> at finitely many critical points (which can just be "cut out" of the domain and codomain spaces to obtain a perfect triple-, quadruple- or whatever-covering). Have fun!</p>
<p>For clarity, in each example below, there are two graphs. The graph on the left is the codomain space, and the point labelled $f(z)$ is draggable. The point labelled $c$ is also draggable, and if you click on it and hold down, $f(z)$ will follow a circular path around it - this is just for convenience, so that you don't have to drag $f(z)$ around a circular path or worry about moving it smoothly by hand if you want to see what happen when $f(z)$ makes a circular loop. The graph on the right shows <em>all (three or four) of the preimages</em> of the point $f(z)$ on the left.</p>
<hr>
<p>The polynomial <script type="math/tex; mode=display">f(z) = z^3</script> has monodromy group isomorphic to $C_3$, the cyclic group with three elements. It defines a triple covering <script type="math/tex; mode=display">\tilde{\mathbb C}\backslash \{0,\infty\}\to \tilde{\mathbb C}\backslash \{0,\infty\} </script> with a single small rotation around the origin corresponding to a cyclic permutation of the roots. We can deduce the monodromy group from the fact that the monodromy group must be generated by the permutation resulting from a loop about $w=0$, and the only transitive action on $3$ points with a single generator is the $C_3$ action. (The only groups with a single generator are the cyclic groups.)</p>
<p>Try dragging $f(z)$ in a small circle around the origin, and watch what happens to the preimages $z_0,z_1,z_2$. You should see that they are cyclically permuted!</p>
<p><center></p>
<div id="coeffbox1" class="jxgbox mybox graphbox" style="">
</div>
<div id="rootbox1" class="jxgbox mybox graphbox" style="">
</div>
<p></center></p>
<script type="text/javascript">
var controller = new PolyRootController(
"rootbox1",
"coeffbox1",
Polynomial({'3': Complex(1,0)}),
Polynomial({'0': Complex(1,0)}));
</script>
<hr>
<p>The polynomial <script type="math/tex; mode=display">f(z) = z^3 - 3z</script> has monodromy group isomorphic to $S_3$, the symmetric group with three elements. It defines a triple covering <script type="math/tex; mode=display">\tilde{\mathbb C}\backslash \{\pm 1,\pm 2,\infty\}\to \tilde{\mathbb C}\backslash \{\pm 2,\infty\} </script> Its monodromy group must be generated by two permutations, induced by letting $f(z)$ follow a small loop encircling the respective points $w=\pm 2$. Because $z^3-3z-2$ and $z^3-3z+2$ have roots of order two, we can deduce that each of these permutation is a simple transposition. This rules out the monodromy group $C_3$, which contains no simple transpositions, allowing us to deduce the correct monodromy group of $S_3$.</p>
<p>Try dragging $f(z)$ in a small circle centered around $w=+2$. Then try dragging it in a small circle centered around $w=-2$. What happens?</p>
<p><center></p>
<div id="coeffbox2" class="jxgbox mybox graphbox" style="">
</div>
<div id="rootbox2" class="jxgbox mybox graphbox" style="">
</div>
<p></center></p>
<script type="text/javascript">
var controller = new PolyRootController(
"rootbox2",
"coeffbox2",
Polynomial({'3': Complex(1,0), '1': Complex(-3,0)}),
Polynomial({'0': Complex(1,0)}));
</script>
<hr>
<p>The polynomial <script type="math/tex; mode=display">f(z) = z^4</script> has monodromy group isomorphic to $C_4$, the cyclic group with four elements. It defines a quadruple covering <script type="math/tex; mode=display">\tilde{\mathbb C}\backslash \{0,\infty\}\to \tilde{\mathbb C}\backslash \{0,\infty\} </script> and we can use the same reasoning as in the example $f(z)=z^3$ to deduce that its monodromy group is cyclic, as it must have a single generator (corresponding to $f(z)$ looping once about $w=0$).</p>
<p>Try dragging $f(z)$ in a circle around the origin for this example.</p>
<p><center></p>
<div id="coeffbox3" class="jxgbox mybox graphbox" style="">
</div>
<div id="rootbox3" class="jxgbox mybox graphbox" style="">
</div>
<p></center></p>
<script type="text/javascript">
var controller = new PolyRootController(
"rootbox3",
"coeffbox3",
Polynomial({'4': Complex(1,0)}),
Polynomial({'0': Complex(1,0)}));
</script>
<hr>
<p>The rational function <script type="math/tex; mode=display">f(z) = \frac{(z^2-1)^2}{z^2}</script> has monodromy group isomorphic to $V$, the Klein four-group. It defines a quadruple covering <script type="math/tex; mode=display">\tilde{\mathbb C}\backslash \{0,\infty,\pm 1, \pm i\}\to \tilde{\mathbb C}\backslash \{0,-4,\infty\}</script> We can deduce this monodromy group by considering the factorizations of $f(z)$ and $f(z)+4$. They tell us that when $f(z)\approx 0$, the preimage $z$ can be one of $4$ points, two of which are close to $+1$ and two of which are close to $-1$, meaning that letting $f(z)$ make a small loop around $w=0$ transposes each of these pairs of roots. Similarly, when $f(z)\approx -4$, the preimage $z$ can be one of $4$ points, two of which are close to $+i$ and two of which are close to $-i$. This means that the monodromy group of $f$ is generated by two permutations, each of which has the cycle type of $(12)(34)$ - and the only permutation group acting transitively on four elements with generators of this shape is $V$.</p>
<p>TLDR: try dragging $f(z)$ in a small circle about $w=0$, and then try dragging $f(z)$ in a small circle about $w=-4$. You should see that in the former case, two pairs of the preimages are swapped, and in the latter case, two <em>different</em> pairings of preimages are swapped.</p>
<p><center></p>
<div id="coeffbox4" class="jxgbox mybox graphbox" style="">
</div>
<div id="rootbox4" class="jxgbox mybox graphbox" style="">
</div>
<p></center></p>
<script type="text/javascript">
var controller = new PolyRootController(
"rootbox4",
"coeffbox4",
Polynomial({'4': Complex(1,0), '2': Complex(-2,0), '0': Complex(1,0)}),
Polynomial({'2': Complex(1,0)}));
</script>
<hr>
<p>The rational function <script type="math/tex; mode=display">f(z) = \frac{z^4}{2z^2 - 1}</script> has monodromy group isomorphic to $D_4$, the dihedral group with $8$ elements. It defines a quadruple covering <script type="math/tex; mode=display">\tilde{\mathbb C}\backslash \{0,\pm 1,\infty\}\to \tilde{\mathbb C}\backslash \{0,1,\infty\}</script> Since $f(z) = \mathcal O(z^4)$ for $z\approx 0$ we can say that letting $f(z)$ follow a small loop about $w=0$ induces a 4-cycle on the preimage points. And since $f(z) = 1 +\mathcal O((z-1)^2)$ for $z\approx 1$ and $f(z) = 1 + \mathcal O((z+1)^2)$ for $z\approx -1$, we have that letting $f(z)$ follow a small loop about $w=1$ induces a permutation on the preimages consisting of a pair of transpositions. The only transitive group action on 4 points with generators of these cycle types is $D_4$.</p>
<p>Try dragging $f(z)$ in a small circle about $w=0$, then try dragging it in a small circle about $w=1$. Finally, drag it in a <em>large</em> circle around the origin, so that the circle encompasses both $w=0$ and $w=1$. What kind of action do you notice on the roots?</p>
<p><center></p>
<div id="coeffbox5" class="jxgbox mybox graphbox" style="">
</div>
<div id="rootbox5" class="jxgbox mybox graphbox" style="">
</div>
<p></center></p>
<script type="text/javascript">
var controller = new PolyRootController(
"rootbox5",
"coeffbox5",
Polynomial({'4': Complex(1,0)}),
Polynomial({'0': Complex(-1,0), '2': Complex(2,0)}));
</script>
<hr>
<p>The rational function <script type="math/tex; mode=display">f(z) = \frac{z^3 (z+3)}{z^3+2z+1}</script> has monodromy group isomorphic to $A_4$, the alternating group of permutations on $4$ elements. It defines a quadruple covering <script type="math/tex; mode=display">\tilde{\mathbb C}\backslash \{0,\pm 1,-3,\infty\}\to \tilde{\mathbb C}\backslash \{0,1,\infty\}</script> Since $f(z)=\mathcal O(z^3)$ for $z\approx 0$, we can say that a small loop about the origin induces a 3-cycle on the preimage points. Similarly, since $f(z) = 1+\mathcal O((z+1)^3)$ for $z\approx -1$, we can also say that a small loop about $w=1$ induces a 3-cycle on the preimage points, meaning that the monodromy group action is generated by two 3-cycles, and is hence isomorphic to $A_4$.</p>
<p>Try dragging $f(z)$ in a small circle about $w=0$, then try dragging it in a small circle about $w=1$. What do you notice? Does this remind you at all of my Sokoban puzzle for $A_4$?</p>
<p><center></p>
<div id="coeffbox6" class="jxgbox mybox graphbox" style="">
</div>
<div id="rootbox6" class="jxgbox mybox graphbox" style="">
</div>
<p></center></p>
<script type="text/javascript">
var controller = new PolyRootController(
"rootbox6",
"coeffbox6",
Polynomial({'4': Complex(1,0), '3': Complex(3,0)}),
Polynomial({'0': Complex(1,0), '1': Complex(2,0), '3': Complex(1,0)}));
</script>
<hr>
</div>
<script src="/js/toc.js"></script>
<br>
<a href="/">back to home page</a>
<hr>
<div id="license-statement">The posts on this website are licensed under <a href="https://creativecommons.org/licenses/by-nc/4.0/">CC-by-NC 4.0</a>.</div>
<div id="notbyai"><a href="https://notbyai.fyi/"><img src="/img/written-by-human.png"/><img src="/img/illustrated-by-human.png"/></a></div>
<script src="/js/post_proc.js"></script>
</body>
</html>
Fri, 30 Aug 2024 00:00:00 +0000Garbage collection by reference counting in a simple Lisp-like languagehttps://franklin.dyer.me/post/233<html dir="ltr" lang="en">
<head>
<title>Franklin Pezzuti Dyer</title>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]},
processEscapes: true,
menuSettings: { inTabOrder: false },
"AssistiveMML": {
disabled: false,
styles: {
".MJX_Assistive_MathML": {
position:"absolute!important",
clip: (MathJax.Hub.Browser.isMSIE && (document.documentMode||0) < 8 ?
"rect(1px 1px 1px 1px)" : "rect(1px, 1px, 1px, 1px)"),
padding: "1px 0 0 0!important",
border: "0!important",
height: "1px!important",
width: "1px!important",
overflow: "hidden!important",
display:"block!important"
}
}
}
});
</script>
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no, type=text/html" charset="UTF-8">
<link rel="stylesheet" href="/css/style.css">
<link rel="stylesheet" href="/css/style-local-.css">
<script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML' async></script>
</head>
<body>
<h2>Franklin Pezzuti Dyer</h2>
<div>
<span class="hidden">
<a href="#begin-content">Skip to page content</a>
</span>
<a id="pagenav"></a>
<a href="/">Home</a>
<a href="/posts">Posts</a>
<a href="/post/1">CV</a>
<a href="/post/2">Contact</a>
<a href="/post/216">People</a>
<a href="/rss/en">RSS</a>
</div>
<hr>
<span class="hidden">
<a href="#pagenav">Skip to navigation</a>
</span>
<a id="begin-content"></a>
<div id="table-of-contents"></div>
<div id="post-body">
<h2>Garbage collection by reference counting in a simple Lisp-like language</h2>
<p>I first learned to program in Python and Java, and when I started programming in C for the first time and had to deal with manual memory management, it made me start to wonder about all of the bookkeeping that must have been happening behind the scenes in higher-level languages. Since then, I've been wanting to understand garbage collection on a deeper level. This is part of my long journey to deeply understand <a href="https://franklin.dyer.me/post/231">computer programming at a lower level</a>.</p>
<p>In this post, I'll describe a recent project of mine in which I wrote a very basic programming language that is similar to Lisp/Scheme and uses <strong>reference counting</strong> for garbage collection. Mind you, this is not the kind of garbage collection algorithm that Java uses. Apparently <a href="https://en.wikipedia.org/wiki/Reference_counting#Python">Python <em>does</em> use reference counting</a>, but it also needs to detect reference cycles, which is a complexity that we won't have to deal with in our language since it doesn't allow mutation. In any case, this project has been one step in the direction of understanding garbage collection more generally.</p>
<p>You can find my source code in <a href="https://github.com/franklindyer/pairadise">this GitHub repo</a>.</p>
<h3>The Pairadise language <a id="toc-section-1" class="toc-section"></a></h3>
<p>I was trying to think of a project that would give me some practical experience implementing reference counting, but I don't enjoy writing parsers. So I settled on a very simple Lisp-like language of my own invention whose only values are <code>NULL</code> and pairs of other values. The only built-ins for this language are:</p>
<ul>
<li><code>empty</code>, which evaluates to the null value.</li>
<li><code>pair(expr1,expr2)</code> which evaluates to a pair whose left and right elements are defined by <code>expr1</code> and <code>expr2</code>, respectively.</li>
<li><code>let(expr1, \x expr2[x])</code> which evaluates to the value obtained by substituting <code>expr1</code> for the free variable <code>x</code> in the expression <code>expr2[x]</code> with free variable <code>x</code>.</li>
<li><code>cond(expr1, expr2, \x,y expr3[x,y])</code> which is basically a case-split on whether <code>expr1</code> is null or a pair. If <code>expr1</code> evaluates to null, it returns the result of evaluating <code>expr2</code>, but if it evaluates to a pair, it returns the result of substituting the left-side for <code>x</code> and the right-side for <code>y</code> in <code>expr3[x,y]</code>.</li>
<li><code>fix(expr1, \x expr2[x])</code> implements fixed-point iteration, repeatedly substituting values for <code>x</code> in the expression <code>expr2[x]</code> with free variable <code>x</code> until arriving at a fixed point, starting with the initial value obtained by evaluating <code>expr1</code>.</li>
<li><code>in</code> evaluates to a pair value read from standard input, with <code>(_,_)</code> used to represent pairs and <code>*</code> used to represent the null value.</li>
</ul>
<p>If you're familiar with the formal syntax for describing the statics and dynamics of a programming language (as in Harper's <em>Practical Foundations for Programming Languages</em>), you might find it easier to read than my informal descriptions. If not, you can just skip past the gobbledygook below. I'm only just beginning to learn about this formalism myself, so I might have gotten them wrong... but here is how I would describe the statics of this language:</p>
<p>
<script type="math/tex; mode=display">\dfrac{}{\Gamma \vdash \texttt{empty} : \texttt{PAIR}}</script>
</p>
<p>
<script type="math/tex; mode=display">\dfrac{\Gamma\vdash e_1 : \texttt{PAIR} ~ ~ ~ \Gamma\vdash e_2:\texttt{PAIR}}{\Gamma \vdash \texttt{pair}(e_1,e_2) : \texttt{PAIR}}</script>
</p>
<p>
<script type="math/tex; mode=display">\dfrac{\Gamma\vdash e_1 : \texttt{PAIR} ~ ~ ~ \Gamma,x:\texttt{PAIR}\vdash e_2:\texttt{PAIR}}{\Gamma \vdash \texttt{let}(e_1,x.e_2) : \texttt{PAIR}}</script>
</p>
<p>
<script type="math/tex; mode=display">\dfrac{\Gamma\vdash e_1 : \texttt{PAIR} ~ ~ ~ \Gamma\vdash e_2 : \texttt{PAIR} ~ ~ ~ \Gamma,x:\texttt{PAIR},y:\texttt{PAIR}\vdash e_3:\texttt{PAIR}}{\Gamma \vdash \texttt{cond}(e_1,e_2,x.y.e_3) : \texttt{PAIR}}</script>
</p>
<p>
<script type="math/tex; mode=display">\dfrac{\Gamma\vdash e_1 : \texttt{PAIR} ~ ~ ~ \Gamma\vdash e_2:\texttt{PAIR}}{\Gamma \vdash \texttt{fix}(e_1,e_2) : \texttt{PAIR}}</script>
</p>
<p>
<script type="math/tex; mode=display">\dfrac{}{\Gamma \vdash \texttt{in} : \texttt{PAIR}}</script>
</p>
<p>And here is how I would describe the dynamics (except for the expression <code>in</code>, which I'm not sure how to describe since it is not referentially transparent, drawing its value from input):</p>
<p>
<script type="math/tex; mode=display">\dfrac{}{\texttt{PAIR}(\ast) ~ \text{val}}</script>
</p>
<p>
<script type="math/tex; mode=display">\dfrac{\texttt{PAIR}(p_1) ~ \text{val} ~ ~ ~ \texttt{PAIR}(p_2) ~ \text{val}}{\texttt{PAIR}((p_1,p_2)) ~ \text{val}}</script>
</p>
<p>
<script type="math/tex; mode=display">\dfrac{(p_1,p_2) = p ~ \text{pair}}{\texttt{pair}(\texttt{PAIR}(p_1), \texttt{PAIR}(p_2)) \mapsto \texttt{PAIR}(p)}</script>
</p>
<p>
<script type="math/tex; mode=display">\dfrac{e_1\mapsto e_1'}{\texttt{pair}(e_1,e_2)\mapsto \texttt{pair}(e_1',e_2)}</script>
</p>
<p>
<script type="math/tex; mode=display">\dfrac{e_1 ~ \text{val} ~ ~ ~ e_2\mapsto e_2'}{\texttt{pair}(e_1,e_2)\mapsto \texttt{pair}(e_1,e_2')}</script>
</p>
<p>
<script type="math/tex; mode=display">\dfrac{e_1\mapsto e_1'}{\texttt{let}(e_1,x.e_2)\mapsto \texttt{let}(e_1',x.e_2)}</script>
</p>
<p>
<script type="math/tex; mode=display">\dfrac{e_1 ~ \text{val}}{\texttt{let}(e_1,x.e_2)\mapsto [e_1/x]e_2}</script>
</p>
<p>
<script type="math/tex; mode=display">\dfrac{e_1 \mapsto \texttt{PAIR}(*)}{\texttt{cond}(e_1,e_2,x.y.e_3)\mapsto e_2}</script>
</p>
<p>
<script type="math/tex; mode=display">\dfrac{e_1 \mapsto \texttt{PAIR}(p) ~ ~ ~ (p_1,p_2) = p ~ \text{pair}}{\texttt{cond}(e_1,e_2,x.y.e_3)\mapsto [\texttt{PAIR}(p_1)/x][\texttt{PAIR}(p_2)/y]e_3}</script>
</p>
<p>
<script type="math/tex; mode=display">\dfrac{e_1 \mapsto e_1'}{\texttt{fix}(e_1,x.e_2)\mapsto \texttt{fix}(e_1',x.e_2)}</script>
</p>
<p>
<script type="math/tex; mode=display">\dfrac{e_1 ~ \text{val} ~ ~ ~ [e_1/x]e_2 \mapsto e_1}{\texttt{fix}(e_1,x.e_2)\mapsto e_1}</script>
</p>
<p>
<script type="math/tex; mode=display">\dfrac{e_1 ~ \text{val}}{\texttt{fix}(e_1,x.e_2)\mapsto \texttt{fix}([e_1/x]e_2,x.e_2)}</script>
</p>
<p>If anyone reading this knows type systems better than I do, please correct my attempt. :-)</p>
<p>Anyways. I don't like coming up with funny names for things, but I'm giving this language a name because it's too awkward to keep saying "my toy programming language". For the sake of this blog post I'm (sarcastically) dubbing the language <em>Pairadise</em> because all of its values are based on pairs, and programming in it absolutely <em>does not</em> make you feel like you are in paradise.</p>
<p>To give you an example of what a program looks like in Pairadise (ha), here's a program that takes a number as input and doubles it. In this language, I represent numbers as pair trees that are "heavy on the right", with zero being <code>*</code>, one being <code>(*,*)</code>, two being <code>(*,(*,*))</code>, three being <code>(*,(*,(*,*)))</code> and so on.</p>
<div class="code"><pre><code>
let(
in,
\x0 cond(
fix(
pair(x0,empty),
\x1 cond(
x1,
empty,
\x2,x3 cond(
x2,
pair(empty,x3),
\x4,x5 pair(x5,pair(empty,pair(empty,x3)))
)
)
),
empty,
\x1,x2 x2
)
)
</code></pre></div>
<p>Yeah, it's ugly, I know. But I like the challenge of constructing programs out of the simplest building blocks possible, which has the added benefit of requiring me to do the least amount of tedious parsing possible! Here's another program, which computes the triangular numbers $1+2+\cdots + n$:</p>
<div class="code"><pre><code>
let(
in,
\x0 cond(
fix(
pair(x0,empty),
\x1 cond(
x1,
empty,
\x2,x3 cond(
x2,
x1,
\x4,x5 pair(
x5,
cond(
fix(
pair(x2,x3),
\x6 cond(
x6,
empty,
\x7,x8 cond(
x7,
x6,
\x9,x10 pair(x10,pair(empty,x8))
)
)
),
empty,
\x6,x7 x7
)
)
)
)
),
empty,
\x1,x2 x2
)
)
</code></pre></div>
<p>Yowza! If you're looking for a challenge and are willing to indulge this bare-bones language, see if you can write a Pairadise program that takes an arbitrary value as input and <em>mirrors</em> it. For example, <code>(*,(*,*))</code> should become <code>((*,*),*)</code>, and <code>(*,((*,*),*))</code> should become <code>((*,(*,*)),*)</code>. (My solution has 405 characters excluding whitespace.)</p>
<h3>Algorithm for reference counting <a id="toc-section-2" class="toc-section"></a></h3>
<p>The basic idea behind reference counting is as follows: when a structure is allocated in memory, up until the time when it is freed, a running count is maintained of the number of pointers to it that exist at any given time. When it is created, its reference count equals 1. From that point onwards, no pointer to that structure may be copied without first incrementing its reference count, and no pointer to that structure may be erased without first decrementing its reference count. Once the reference count reaches zero, the structure is deallocated - and this can occur without risk of leaving behind a dangling pointer, because there should be no pointers left to dereference once the reference count becomes zero.</p>
<p>Of course, we cannot really free a piece of memory <em>after</em> the reference count becomes zero, because we need a pointer to a structure in order to dereference it. Instead, we free the memory in the moment when its last remaining pointer would be erased.</p>
<p>In Pairadise, the only values are pairs and the empty value. Each pair may contain pointers to up to two other pairs, meaning that when a pair is finally freed due to its reference count reaching zero, up to two more pointers will be erased. This could result in yet more pairs being freed, which could result in even more pointers being erased and more pairs being freed, and so on.</p>
<p>Here's an example. If we had a value corresponding to the nested pair expression <code>((*,*),((*,*),(*,*)))</code>, the memory allocated for it might look like this:</p>
<p><center>
<img alt="Fig 1" src="/img/2024-09-30-Fig1.png" />
</center></p>
<p>If the pointer to this value were suddenly deleted, this would trigger a recursive deletion of every structure in this tree. These pair structures would be freed in the following sequence:</p>
<p><center>
<img alt="Fig 2" src="/img/2024-09-30-Fig2.png" />
</center></p>
<p><center>
<img alt="Fig 3" src="/img/2024-09-30-Fig3.png" />
</center></p>
<p>In this example, the pairs involved in the structure and their respective pointers comprise a tree. However, I allow memory to be <em>shared</em> between values in my implementation, meaning that values might not always be trees - they could be arbitrary <a href="https://en.wikipedia.org/wiki/Directed_acyclic_graph">directed acyclic graphs</a>. For example, in the value <code>(((*,*),(*,*)),((*,*),(*,*)))</code>, all of the pairs could be stored disjointly in memory:</p>
<p><center>
<img alt="Fig 4" src="/img/2024-09-30-Fig4.png" />
</center></p>
<p>or the subvalues of shape <code>((*,*),(*,*))</code> could overlap in memory:</p>
<p><center>
<img alt="Fig 5" src="/img/2024-09-30-Fig5.png" />
</center></p>
<p>or all of the subvalues of shape <code>(*,*)</code> could overlap in memory instead:</p>
<p><center>
<img alt="Fig 6" src="/img/2024-09-30-Fig6.png" />
</center></p>
<p>And so on. </p>
<h3>Implementation of reference counting <a id="toc-section-3" class="toc-section"></a></h3>
<p>The reference counting algorithm is straightforward enough to describe, but while implementing it in C, it's easy to lose track of pointers. I had to debug several memory leaks and double-free bugs.</p>
<p>In the end, I found that the best way of keeping track was to write just a few helper functions that manipulate pair pointers while maintaining the correct reference counts, and then use them almost exclusively for handling pair pointers. I used the following three functions:</p>
<div class="code"><pre><code>
void delete_pair_pointer(pair_val** pointer);
void assign_pair_pointer(pair_val** pointer, pair_val* pointee)
pair_val* new_pair_val()
</code></pre></div>
<p>The <code>delete_pair_pointer</code> function is used to "delete" a pair pointer passed by reference by replacing its value with <code>NULL</code> and updating the refcount of the corresponding pair, freeing it and recursing when appropriate. The <code>assign_pair_pointer</code> is used to <em>copy</em> a pair pointer to another pair pointer, incrementing the refcount. Finally, <code>new_pair_val</code> is the only function that I allowed myself to use for creating brand new pair pointers, and is the only place where <code>malloc</code> is called to allocate pair values. It initializes the reference count the new pair value to 1, corresponding to the single pointer returned by <code>new_pair_val</code>.</p>
<p>To give you an example, under my self-imposed restriction to use these functions exclusively, the following code would <em>not be allowed</em>:</p>
<div class="code"><pre><code>
pair_val* pv1, pv2;
pv1 = new_pair_val();
pv2 = pv1;
</code></pre></div>
<p>because the assignment <code>pv2 = pv1</code> duplicates the pointer in <code>pv1</code> without updating the reference count accordingly. Instead, the following code should be used to accomplish the same result while maintaining the correct refcounts:</p>
<div class="code"><pre><code>
pair_val* pv1, pv2;
pv1 = new_pair_val();
assign_pair_pointer(&pv2, pv1)
</code></pre></div>
<p>There is a sneaky "gotcha" that makes it a little bit tricky to use these functions <em>exclusively</em> for creation and destruction of <code>pair_val</code> pointers: a <code>pair_val*</code> can be lost just by <em>going out of scope</em>. And if a non-null <code>pair_val*</code>goes out of scope, then it is lost without its refcount being decremented. For example, in this code:</p>
<div class="code"><pre><code>
if (condition) {
pair_val* pv = new_pair_val();
// Do some things with pv...
}
</code></pre></div>
<p>at the end of the <code>if</code> block, <code>pv</code> goes out of scope, destroying the pointer it holds. This could result in a <code>pair_val</code> residing in memory somewhere with a refcount of $1$ but no pointers pointing to it, causing a memory leak, since this <code>pair_val</code> could never be freed. Instead, non-null <code>pair_val*</code> variables must be <em>deleted</em> using <code>delete_pair_pointer</code> before they go out of scope.</p>
<div class="code"><pre><code>
if (condition) {
pair_val* pv = new_pair_val();
// Do some things with pv...
delete_pair_pointer(&pv);
// Now pv is NULL when it goes out of scope
}
</code></pre></div>
<p>The one exception is when a <code>pair_val*</code> variable goes out of scope in the body of a function <em>that returns its value</em>. The local variable holding the pointer goes out of scope when the function returns, but a <em>new</em> pointer is returned from the function, so when a <code>pair_val*</code> is returned from a function where it goes out of scope, there is a net zero gain/loss of pointers to its memory. For example, if we have a function that looks like this:</p>
<div class="code"><pre><code>
pair_val* f() {
pair_val* pv = new_pair_val();
// Do some stuff with pv...
return pv;
}
</code></pre></div>
<p>and when <code>f()</code> is called, a pointer is lost when <code>pv</code> goes out of scope, but one is also gained from <code>pv</code> being returned. Note that this means it is <em>illegal</em> to call <code>f()</code> alone without assigning its value to some variable, because this would result in the return value of <code>f</code> being lost, and hence an incorrect refcount. Instead, whenever <code>f</code> is called, it must appear on the right-hand side of an assignment <code>somevar = f()</code>.</p>
<p>I won't go through my code line-by-line, but you can see the most important bits of it <a href="https://github.com/franklindyer/pairadise/blob/main/refcount_eval.c">here</a>. While working on it, I couldn't help thinking of how nice it would be for all of these constraints to be enforced by the compiler, so that I wouldn't have to spend time debugging segfaults or memory leaks caused by careless violations of these rules. This makes me appreciate languages like Rust that use <a href="https://en.wikipedia.org/wiki/Substructural_type_system">linear type systems</a> to track ownership at compile-time.</p>
<h3>Some pretty graphs of pair value lifetimes <a id="toc-section-4" class="toc-section"></a></h3>
<p>Since every <code>malloc</code> of a <code>pair_val*</code> occurs in <code>new_pair_val</code>, and every <code>free</code> of a <code>pair_val*</code> occurs in <code>delete_pair_pointer</code>, it is very easy to have the interpreter log every allocation and deallocation. Just for shits and giggles, I've written a simple Python script to convert a log of these debug statements into a <a href="https://en.wikipedia.org/wiki/Gantt_chart">Gantt chart</a> that shows the lifetimes of each chunk of allocated memory, some of which are allocated and freed multiple times. For example, this is what the chart looks like when my natural-number doubling program is called on <code>(*,(*,(*,*)))</code>:</p>
<p><center>
<img alt="Fig 7" src="/img/2024-09-30-Fig7.png" />
</center></p>
<p>Here's what the malloc lifetimes look like when my triangular-number program is called on the input <code>(*,(*,(*,(*,*))))</code>:</p>
<p><center>
<img alt="Fig 8" src="/img/2024-09-30-Fig8.png" />
</center></p>
<p>And here's what the malloc lifetimes look like when my tree-reflecting program is called on the input <code>(*,(((*,*),(*,*)),*))</code>:</p>
<p><center>
<img alt="Fig 9" src="/img/2024-09-30-Fig9.png" />
</center></p>
</div>
<script src="/js/toc.js"></script>
<br>
<a href="/">back to home page</a>
<hr>
<div id="license-statement">The posts on this website are licensed under <a href="https://creativecommons.org/licenses/by-nc/4.0/">CC-by-NC 4.0</a>.</div>
<div id="notbyai"><a href="https://notbyai.fyi/"><img src="/img/written-by-human.png"/><img src="/img/illustrated-by-human.png"/></a></div>
<script src="/js/post_proc.js"></script>
</body>
</html>
Mon, 30 Sep 2024 00:00:00 +0000A cartoon primer on online advertisinghttps://franklin.dyer.me/post/234<html dir="ltr" lang="en">
<head>
<title>Franklin Pezzuti Dyer</title>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]},
processEscapes: true,
menuSettings: { inTabOrder: false },
"AssistiveMML": {
disabled: false,
styles: {
".MJX_Assistive_MathML": {
position:"absolute!important",
clip: (MathJax.Hub.Browser.isMSIE && (document.documentMode||0) < 8 ?
"rect(1px 1px 1px 1px)" : "rect(1px, 1px, 1px, 1px)"),
padding: "1px 0 0 0!important",
border: "0!important",
height: "1px!important",
width: "1px!important",
overflow: "hidden!important",
display:"block!important"
}
}
}
});
</script>
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no, type=text/html" charset="UTF-8">
<link rel="stylesheet" href="/css/style.css">
<link rel="stylesheet" href="/css/style-local-.css">
<script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML' async></script>
</head>
<body>
<h2>Franklin Pezzuti Dyer</h2>
<div>
<span class="hidden">
<a href="#begin-content">Skip to page content</a>
</span>
<a id="pagenav"></a>
<a href="/">Home</a>
<a href="/posts">Posts</a>
<a href="/post/1">CV</a>
<a href="/post/2">Contact</a>
<a href="/post/216">People</a>
<a href="/rss/en">RSS</a>
</div>
<hr>
<span class="hidden">
<a href="#pagenav">Skip to navigation</a>
</span>
<a id="begin-content"></a>
<div id="table-of-contents"></div>
<div id="post-body">
<h2>A cartoon primer on online advertising</h2>
<p><center>
<img alt="Fig1" src="/img/2024-10-15-Fig1.jpg" /> <br>
<img alt="Fig2" src="/img/2024-10-15-Fig2.jpg" /> <br>
<img alt="Fig3" src="/img/2024-10-15-Fig3.jpg" /> <br>
<img alt="Fig4" src="/img/2024-10-15-Fig4.jpg" /> <br>
<img alt="Fig5" src="/img/2024-10-15-Fig5.jpg" /> <br>
<img alt="Fig6" src="/img/2024-10-15-Fig6.jpg" /> <br>
<img alt="Fig7" src="/img/2024-10-15-Fig7.jpg" /> <br>
<img alt="Fig8" src="/img/2024-10-15-Fig8.jpg" /> <br>
<img alt="Fig9" src="/img/2024-10-15-Fig9.jpg" /> <br>
<img alt="Fig10" src="/img/2024-10-15-Fig10.jpg" /> <br>
<img alt="Fig11" src="/img/2024-10-15-Fig11.jpg" /> <br>
<img alt="Fig12" src="/img/2024-10-15-Fig12.jpg" /> <br>
<img alt="Fig13" src="/img/2024-10-15-Fig13.jpg" /> <br>
<img alt="Fig14" src="/img/2024-10-15-Fig14.jpg" /> <br>
<img alt="Fig15" src="/img/2024-10-15-Fig15.jpg" /> <br>
<img alt="Fig16" src="/img/2024-10-15-Fig16.jpg" /> <br>
<img alt="Fig17" src="/img/2024-10-15-Fig17.jpg" /> <br>
<img alt="Fig18" src="/img/2024-10-15-Fig18.jpg" /> <br>
<img alt="Fig19" src="/img/2024-10-15-Fig19.jpg" /> <br>
<img alt="Fig20" src="/img/2024-10-15-Fig20.jpg" /> <br>
<img alt="Fig21" src="/img/2024-10-15-Fig21.jpg" /> <br>
</center></p>
<p>If you want to learn more about online advertising, here are some sources:</p>
<ul>
<li><a href="https://www.ftc.gov/news-events/news/press-releases/2019/09/google-youtube-will-pay-record-170-million-alleged-violations-childrens-privacy-law">An article</a> about YouTube's violation of COPPA</li>
<li>The FTC's <a href="https://www.ftc.gov/business-guidance/resources/disclosures-101-social-media-influencers">guidelines</a> and <a href="https://www.ftc.gov/business-guidance/resources/ftcs-endorsement-guides-what-people-are-asking">FAQs</a> for influencer endorsements</li>
<li>The <a href="https://storage.courtlistener.com/recap/gov.uscourts.vaed.533508/gov.uscourts.vaed.533508.1.0_2.pdf">antitrust complaint</a> filed against Google's online ad empire</li>
<li>For detailed info about how ads work on YouTube and Google Ads:<ul>
<li>Docs on <a href="https://support.google.com/youtube/answer/12929256?hl=en&co=YOUTUBE._YTVideoType%3Dvideo">how ads work</a>, for content creators</li>
<li>Docs on <a href="https://support.google.com/youtube/answer/6162278">ad-friendly content</a>, for content creators</li>
<li>Docs on <a href="https://adsense.google.com/start/how-adsense-works/">how AdSense works</a>, for publishers</li>
<li>Docs on <a href="https://support.google.com/adsense/answer/9713?sjid=6946465016229447776-NA">ad targeting</a>, for publishers</li>
<li>An <a href="https://support.google.com/youtube/answer/188570">overview of YouTube's ad policy</a>, for advertisers</li>
<li>Docs on <a href="https://support.google.com/adspolicy/answer/6015406?hl=en">inappropriate content</a>, for advertisers</li>
<li>Docs on <a href="https://support.google.com/google-ads/answer/2375454">bidding and budgeting</a>, for advertisers</li>
<li>Definitions of <a href="https://support.google.com/google-ads/answer/6320?sjid=7297785039378825859-NC">impression</a>, <a href="https://support.google.com/google-ads/answer/31799">click</a> and <a href="https://support.google.com/google-ads/answer/6365?sjid=7297785039378825859-NC">conversion</a></li>
<li>Docs on <a href="https://support.google.com/google-ads/answer/6259715">attribution</a>, for advertisers</li>
</ul>
</li>
<li>The <a href="https://www.youtube.com/channel/UCsP7Bpw36J666Fct5M8u-ZA">YouTube channel of Ann Reardon</a>, a food scientist and YouTuber who creates a lot of "debunking" videos about viral cooking/baking content produced by content farms</li>
<li>A <a href="https://drive.google.com/file/d/1YaG9xpu-WQKBPUi8yQ4HaDYQLUSa7Y3J/view">leaked memo</a> from the YouTuber MrBeast's production company</li>
</ul>
</div>
<script src="/js/toc.js"></script>
<br>
<a href="/">back to home page</a>
<hr>
<div id="license-statement">The posts on this website are licensed under <a href="https://creativecommons.org/licenses/by-nc/4.0/">CC-by-NC 4.0</a>.</div>
<div id="notbyai"><a href="https://notbyai.fyi/"><img src="/img/written-by-human.png"/><img src="/img/illustrated-by-human.png"/></a></div>
<script src="/js/post_proc.js"></script>
</body>
</html>
Tue, 15 Oct 2024 00:00:00 +0000A shitpost about Unicode's superscript digitshttps://franklin.dyer.me/post/236<html dir="ltr" lang="en">
<head>
<title>Franklin Pezzuti Dyer</title>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]},
processEscapes: true,
menuSettings: { inTabOrder: false },
"AssistiveMML": {
disabled: false,
styles: {
".MJX_Assistive_MathML": {
position:"absolute!important",
clip: (MathJax.Hub.Browser.isMSIE && (document.documentMode||0) < 8 ?
"rect(1px 1px 1px 1px)" : "rect(1px, 1px, 1px, 1px)"),
padding: "1px 0 0 0!important",
border: "0!important",
height: "1px!important",
width: "1px!important",
overflow: "hidden!important",
display:"block!important"
}
}
}
});
</script>
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no, type=text/html" charset="UTF-8">
<link rel="stylesheet" href="/css/style.css">
<link rel="stylesheet" href="/css/style-local-.css">
<script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML' async></script>
</head>
<body>
<h2>Franklin Pezzuti Dyer</h2>
<div>
<span class="hidden">
<a href="#begin-content">Skip to page content</a>
</span>
<a id="pagenav"></a>
<a href="/">Home</a>
<a href="/posts">Posts</a>
<a href="/post/1">CV</a>
<a href="/post/2">Contact</a>
<a href="/post/216">People</a>
<a href="/rss/en">RSS</a>
</div>
<hr>
<span class="hidden">
<a href="#pagenav">Skip to navigation</a>
</span>
<a id="begin-content"></a>
<div id="table-of-contents"></div>
<div id="post-body">
<h2>A shitpost about Unicode's superscript digits</h2>
<p>I was writing some C++ code to do computations involving polynomials. For my own gratification, I wanted to write a function that would pretty-print polynomials to my terminal, given a vector of coefficients. Naturally, I thought I'd use the special Unicode characters <code>⁰¹²³⁴⁵⁶⁷⁸⁹</code> to make the exponents look good, because <code>x⁵</code> looks a lot nicer than <code>x^5</code>. I started by writing a function for translating a digit between 0 and 9 into its Unicode superscript counterpart.</p>
<div class="code"><code><pre>
char digit_superscript(int d) {
// some stuff here...
}
</pre></code></div>
<p>But no, that won't work. Unicode characters encoded using UTF8 can actually occupy up to four bytes. A <code>char</code> can only hold one byte, so I had to return a <code>string</code> instead.</p>
<div class="code"><code><pre>
string digit_superscript(int d) {
// some stuff here...
}
</pre></code></div>
<p>The easy (and probably performant) way of doing this would be to list out all ten cases and return the corresponding Unicode character. But that would be really ugly and repetitive code, and I don't care about how efficiently my polynomials are printed. I remembered an old trick that has served me well when working with ASCII: to get the nth letter of the alphabet, you can start with <code>'a'</code> and simply add $n$, because the letters <code>a..z</code> are consecutive. So perhaps I could get the superscript digit for $d$ by starting with the code point for <code>⁰</code> and adding $d$.</p>
<p>The character <code>⁰</code> is code point <code>U+2070</code>, which is encoded in UTF8 as the bytes <code>e2 81 b0</code>. So I gave this a try:</p>
<div class="code"><code><pre>
string digit_superscript(int d) {
string num = "\xe2\x81\xb0";
num.at(2) += d;
return num;
}
</pre></code></div>
<p>And I tested the function by trying to print out the digits from zero through nine:</p>
<div class="code"><code><pre>
int main() {
for (int i = 0; i < 10; i++)
cout << digit_superscript(i);
cout << "\n";
}
</pre></code></div>
<p>The output was <code>⁰ⁱ⁴⁵⁶⁷⁸⁹</code>. What the fuck?</p>
<p>That's right: the Unicode superscript digits are not consecutive. The superscript zero is <code>U+2070</code>, but <code>U+2071</code> is the superscript "i" character <code>ⁱ</code>. Even better, the code points <code>U+2072</code> and <code>U+2073</code> are not mapped to any character at all right now, just "reserved for future use". The superscript digits <code>⁴⁵⁶⁷⁸⁹</code>, however, are fortunate enough to occupy the consecutive code points from <code>U+2074</code> through <code>U+2079</code>.</p>
<p>So what's the deal with <code>¹²³</code>? <a href="https://en.wikipedia.org/wiki/Unicode_subscripts_and_superscripts#Superscripts_and_subscripts_block">According to Wikipedia</a> they are inherited from the encoding ISO-8859-1, which was a single-byte encoding extending ASCII that possessed these three superscript digits and <em>none of the other seven</em>. Unicode was considerate enough to allow the ISO-8859-1 characters to retain their code points in its Latin-1 block, with the unfortunate consequence that the superscript digits <code>¹²³</code> be separated from their bretheren by 8000 or so characters. But hey, at least <code>⁰</code> has <code>ⁱ</code> to keep it company. They're vaguely related, right? You know, because they're both superscripted... things?</p>
<p>Not only that, but <code>¹²³</code> were not even consecutive in ISO-8859-1. The characters <code>²³</code> are <code>U+00B2</code> and <code>U+00B3</code>, but <code>¹</code> is <code>U+00B9</code>. Lovely.</p>
<p><center><img alt="Fig1" src="/img/2024-11-10-Fig1.jpeg" /></center></p>
<p>Alright, back to coding. I was able to use the offset trick for the digits <code>⁰⁴⁵⁶⁷⁸⁹</code> but the digits <code>¹²³</code> have to be treated as their own special case.</p>
<div class="code"><code><pre>
string digit_superscript(int d) {
switch (d) {
case 1:
return "\u00b9";
case 2:
return "\u00b2";
case 3:
return "\u00b3";
default:
string num = "\xe2\x81\xb0";
num.at(2) += d;
return num;
}
}
</pre></code></div>
<p>How <em>disgusting</em>...</p>
</div>
<script src="/js/toc.js"></script>
<br>
<a href="/">back to home page</a>
<hr>
<div id="license-statement">The posts on this website are licensed under <a href="https://creativecommons.org/licenses/by-nc/4.0/">CC-by-NC 4.0</a>.</div>
<div id="notbyai"><a href="https://notbyai.fyi/"><img src="/img/written-by-human.png"/><img src="/img/illustrated-by-human.png"/></a></div>
<script src="/js/post_proc.js"></script>
</body>
</html>
Sun, 10 Nov 2024 00:00:00 +0000