ADVENT #4 — aperture card

In our last installment, I looked at the simple tape for ((lambda (v) (add v 22)) 12) and found that it took a lot of motion to add two numbers together. Some other quick things fell out from that. One was that ((lambda (v) (add v 22)) 12) was exactly equivalent to (add 12 22). That is, of course, because they are exactly equivalent. The reason that the program didn‘t constant fold down to 34 directly is that the compiler has no idea what the semantics of ‘add’ are. It’s a foreign function that may as well ask a passerby to add the arguments together.

A problem with that simple example is that it didn’t actually show off all five key Alice instructions. Here‘s a slightly more complicated program offered with more targeted commentary.

((lambda (incr) (incr 2)) (lambda (v) (add v 1)))

Initial registers: pc=20, fp=28, others zero

Boilerplate tape cells. alice takes position zero. Note that the ‘next’ field of the deferred entry points to 40. That’s where the next deferred tape on the cell is.

pos 0: alice(undefined[undefined], undefined[undefined])
pos 1: deferred "pc":1,"fp":1,"r":0,"r2":0,"blocked":1,"completed":1,"next":40

This frame is the data section

2: frame(0)-------------
3: lit:1
4: sz:3

This is a lone addr cell. The compiler emits an address for every frame. Without an address cell, the frame cannot be referenced. This frame was produced by the compiler, which just emitted the address into the tape before the frame.
5: addr:6

This frame is text. It feeds a frame and passes its own fp[1] into the r[1] for the new frame and adds an absolute addressed cell ‘abs[3]’ as the second argument, then calls add. This is a function that adds one to an argument.

6: frame(7)-------------
7: feed(fp[4], abs[4])
8: reg[r1] = fp[4]
9: r1[1] = fp[1]
10: r1[2] = abs[3]
11: call(add, fp[4])
12: fp[0] = r1[0]
13: alice()

The address so that we can reference the following frame.
14: addr:15

A data frame. We can see where it gets used by looking to see who references abs[14].

15: frame(3)-------------
16: addr:6
17: sz:5
18: addr:2
19: lit:2

This is the text frame where execution begins. Ah! It references the data frame above. It feeds a frame based on a size it reads from the above frame and then uses that as an argument for fork(). When functions are packaged by the compiler, they turn into a text frame and a companion data frame that contains information the caller needs — like how much frame to feed for arguments plus local storage for the callee. ’call’, in the text frame above and in our earlier example, doesn’t require this. For call, the caller allocates space for the arguments and the result. Foreign call targets are expected to manage their own storage requirements just as they manage their side effects. Alice guarantees that a particular execution can be replayed, not that the program will execute the same way twice — speaking of which… ‘fork‘ is what Alice has for branch. It starts a new thread given a new pc and fp. Execution will then continue in both. A given implementation will have a finite number of available thread units, so a typically arises. This version of Alice is maximally unperformant and has a single thread. The runtime will pick a thread to continue and defer the other by writing a deferred entry to the tape. We can see which happened by looking at entries in the tape but we know that the fork parent would block on instruction 26 when it attempts to copy the result out of the child’s frame.

20: frame(7)-------------
21: reg[r1] = abs[14]
22: feed(fp[4], r1[1])
23: reg[r2] = fp[4]
24: r2[1] = abs[19]
25: fork(fp[4], r1[0])
26: fp[0] = r2[0]
27: alice()

This is the initial fp frame

28: frame(5)-------------
29: lit:3
30: blank
31: addr:2
32: addr:28
33: addr:34

This is the frame generated by instruction 22 (and is written into the fp[4] of that instruction, address 33 above. The return address of a feed is always written to the tape somewhere before the fed frame. This frame is used as the fp frame for the fork call at instruction 25. The target of the fork call was r1[0], the frame at addr:6 — the increment function. It sure looks like it accepted 2 and returned 1. I honestly don’t remember why the blank cells are there. An artifact of an ABI that I never finished? I don’t remember

34: frame(5)-------------
35: lit:3
36: lit:2
37: blank
38: blank

I don’t really have anything to say about this last cell in the above frame but I’m fighting with ghost and I can’t re-join cell 39 with the cell 38 without a weird paragraph break. Since we’re here, though, this value addr:32 is the result of the feed at instruction 11.

39: addr:42

This is a deferred entry that names the call to increment and says it was blocked on cell 6. Cell six was populated at the time the call ran (something I don’t wish to be bothered to prove at the moment), so this is the runtime scheduler‘s way of saying that it is parking a perfectly runnable thread because there were more runnable threads than thread units. By the way, this tells us that the scheduler decided to continue with the fork parent rather than the fork child.

40: deferred: "pc":6,"fp":34,"r1":0,"r2":0,"blocked":6,"completed":1,"next":41}

Here’s another deferred entry. This one is for the thread parent. It blocked exactly where we thought it might — in copying the return value of increvent into the cell that satisfies the execution.

41: deferred: "pc":26,"fp":28,"r1":15,"r2":34,"blocked":35,"completed":1,"next":0}

After that deferral, the only runnable thread was pc:6, fp:34 and that’s where execution resumes. This frame was created by the feed at instruction 7 and the result was written to fp[4], which was (34+1)+4. Pleasantly, cell 39 is addr:42. The execution of that thread will have continued until the end of the frame or an Alice. The above deferred entry shows that there is no ‘next’ deferred entry on the tape so we know it finished to completion and unblocked tape location 35 in the process. That made the thread pc:26, fp:28 runnable. It ran and wrote lit:3 to location 29.

At the end of that thread, the tape location 35 will be written and the above deferred thread is now runnable. The thread pc:6, fp:34 wrote lit:3 to its fp[0], tape location 29. That location satisfies the execution and execution stops.

42: frame(3)-------------
43: lit:3
44: lit:2
45: lit:1

The removable media for this installment is the ‘aperture card’, a type of paper punched card that contains a microfilm slide. These cards have been in use for around 75 years. For most of that time, they associated high-resolution mechanical drawings spanning many sheets with machine-readable metadata. A standard punched card might hold 80 bytes but the film chip on an aperture card may hold up to tens of megabytes worth of information in the analog domain. While the whole card may not be computer-readable by the machines of the 1950s, it was a very dense computer-indexable media.

The aperture card was not the only removable-mixed-media storage technology. We’ll talk about the hybrid disk packs of the CMX-600 in a future installment.