ADVENT #3 — magnetic strip

The last installment showed a trivial tape but offered little explanation. I’m back to … yeah, I sort of forgot how this works. I remember that I thought that would happen, and I built it so that someone would later be able to figure it out and that someone would maybe be me.

The compiler generates an initial tape and also generates initial register values. For this tape, the initial register values were pc=6, fp=14, and all other registers 0. The execution is satisfied when tape index 15 is written.

Here’s the tape, again, for the trivial program.

((lambda (v) (add v 22)) 12)

0: alice

‘alice’ is a halt instruction. This is a placeholder since 0 is a reserved tape location. This particular instruction could never be executed, since execution always begins at frame boundaries and this is a loose instruction on the tape not part of a frame.

1: deferred pc: 1 fp: 1 r1: 0 r2: 0 blocked: 1 completed: 1 next: 0

’deferred’ cells are generated by the runtime when a thread context needs to be paged out by the scheduler. This entry is generated by the compiler as part of a standard tape lead-in. Each deferred entry contains enough information to determine that the thread is restartable (this is usually a tape cell that was blank when the thread tried to read it) and enough information to restart the thread. Really, it contains enough information to restart the thread efficiently and that’s a tradeoff that I keep exploring. In general, a program counter and a frame pointer are enough, everything else is recoverable. This version of Alice keeps a list of these, so this cell exists to be the head of that list and would have its ‘next’ field populated when another entry was created later in the list. deferred entries are created on the tape in chronological order.

2: frame(0)

This is a (pointless) frame cell. frame cells are created either by the compiler when it generates an input tape or by the ’feed’ instruction. Frames have associated sizes. The base registers (here fp, r1, r2) can only be loaded with frame cells and reference the associated frames following. Dynamically created frames are recorded on the tape in chronological order. This frame cell exists as the start of what would be the ‘data’ section emitted by the compiler. The current implementation references this data with an absolute addressing scheme. This is likely to change.

3: lit:12

This is twelve, literally

4: lit:22

Twenty-two, literally

5: sz:3

This is a ‘size’ cell. The feed instruction takes ’size’-type cells. These values are created by the compiler for the input tape. They can be copied at runtime, but no new size cells can be created with values not present in the original tape.

6: frame(7)

A frame of size 7. frames are created in two ways. The compiler can generate them as part of an input tape or they can be created by a ’feed’ instruction. A feed instruction writes the result to a tape location that must already exist before the new tape is created. Since we have gotten this far into the tape without seeing an addr:6 stored somewhere to correspond to this frame, we know it was created by the compiler and not at runtime. This cell is also the initial program counter. Execution always starts at a frame boundary and continues, if it continues, until the end of the frame or an Alice instruction. Because there is no branch, the Alice instruction is usually unnecessary however it allows data and blank tape to follow text in a frame.

7: feed(fp[4], abs[5])

Here is one one of those feed instructions. This feeds abs[5]-many cells of tape, plus a new frame cell, and writes the address of the frame into the location fp[4]. ’fp’ is the frame base register, analogous to a stack pointer. The initial fp is 14, so fp[4] is tape cell 19. That holds addr:20. Because that tape cell is written, and because we can show that no prior instruction wrote that tape cell, we can show that the feed instruction was executed. All dynamically-generated frames must have their result stored to the tape, and at a point prior to the new cells. This is because feed cannot store its result to a register directly and it will not execute if the result cell does not exist or is already non-blank.

8: reg[r1] = fp[4]

The r1 base register is set to the frame generated by the preceding feed instruction. Because this was first bounced to the tape, we have additional execution ordering information. Because this doesn’t change the tape, we don’t know if this instruction executed until we see that a subsequent instruction executed.

9: r1[1] = abs[3]

Put the value lit:12 at the tape cell at (r1+1)+1. Because we know that the frame at cell 20 was dynamically created, that cell 22 is non-empty, and that no prior instruction wrote to that cell, we know that this instruction executed and also that the previous instruction executed.

10: r1[2] = abs[4]

Put the value lit:22 at the tape cell at (r1+1)+2. As above, we can see that this instruction executed because tape cell 23 is non-empty.

11: call(add, fp[4])

Recall r1 == fp[4]. This is a call instruction using the frame that we generated and just populated with the literal values 22 and 12. Alice has no idea what add is, it just names an external interface in this particular Alice. External call handlers may write only to their frames or tape locations which can be reached from those frames. The Alice ABI convention is that calls return values in index 0 of their frame, though Alice does not care. External call handlers can put most legal values in their frame, except for ‘size’ type cells and cell types internal to the machine, like deferred. They cannot put ‘frame’ cells in their own frame because frames cannot be nested and these would therefore not be legal.

12: fp[0] = r1[0]

Alice may not care that calls write a return value to index 0, but this instruction certainly cares. It blocks until the prior call writes a value to index 0. We can see that this happened because fp[0], tape index 15, is not blank and was not written previously. That cell holds lit:34, which is a sensible value for 22 + 12.

If we wished to replay this execution, it doesn’t really matter what add does and whether it always returns the same value. We know what it returned that time and we captured the value.

Because execution is satisfied when location 21 is non-blank, the machine can stop running here.

13: Alice

This is unnecessary, but courteous.

14: frame(5)

A frame like the text frame above. We know this was not dynamically generated because we do not see its address recorded at a prior tape location. This is the initial fp for execution.

15: lit:34

We saw this cell written at index 12. This satisfies execution.

16: blank

I don’t remember why the compiler put this blank cell here. Anyway, it wasn’t written! Any attempt to read it would block until it was.

17: addr:2

Likewise no idea why this was written. It points to an empty frame. Now that I think about it, this may be residue of the compiler’s treatment of the Scheme environment. It’s never referenced, so never mind.

18: addr:14

This is a reference back to this frame. I wish I remember why I put it here.

19: addr:20

We saw this written (as fp[4]) by feed.

20: frame(3)

This is the frame dynamically created in order to call add.

21: lit:34

This is the return value from add

22: lit:12

This is one of the operands to add

23: lit:22

This is the other operand to add. That’s the end of the tape!

Was this an inefficient way to add 12 and 22? Yes. Was it stunningly inefficient? Also yes. Do I care? Not especially.

Is it much less efficient than generating a trace of some other architecture running a similar program? Not obviously. That’s kind of the point. A trace-quality tape that I actually believe because it was produced as part of execution, not as a secondary artifact. Can I transform this tape back into the original input tape? Yes. Can I easily and soundly rewrite this into a more efficient tape? Yes.

Today’s removable media is the magnetic strip memory of the HP 65 calculator. I believe that the HP 65, introduced in 1974, was the first handheld calculator to use removable media for stored programs (or perhaps for any other purpose). According to Wikipedia, it was also the first electronic calculator in space on an Apollo mission where it was used for mission-specific programs. I wonder if this was the first removable media in space.

These cards were like a cross between slips of magnetic tape and the upper half of a credit card snapped in two. They were read by a motorized transport in the calculator that was a bit like a tape drive that dragged the card through the calculator. So these were not only removeable, they were physically ejected from the calculator as they were read or written.