Register machine

A register machine can be thought of as a low-level computer that sequentially executes instructions to manipulate the contents of a fixed set of storage containers known as registers using simple data movement and primitive operations. A register machine consists of:

1. Data paths describing the registers, operations, how they are connected, and buttons controlling data flow, essentially a hardware layout of the computation.
2. Controller consisting of instructions on sequencing the operation of all the levers in the data paths. In order to properly carry out some computation, the buttons need to be pushed in the right order, and the controller describes this order.

The computation in a register machine can be summarized via a low-level programming language that looks like some generic assembly language (including labels for lines of code). Repeatedly used blocks of computation can be wrapped into subroutines that can be entered and exited. The exit location is guided with continue registers that store the label of the subroutine-caller.

Implementation

Stack for recursion

In order to implement recursion, we further need a stack to store and restore intermediate results/values and, importantly, labels for the continue register to direct the exits once a recursive call at a particular level is completed. A stack is ultimately a physically implemented memory structure and can, therefore, result in a stack overflow (I only just realized that this is where the website's name comes from).

Storage allocation and garbage collection

Memory needs to be managed as computation proceeds, handling explicit object creation as well as internal structures such as environments and argument lists. This is easy enough if memory were infinite but real finite memories require automatic storage allocation to support the illusion of an infinite memory. One popular storage allocation strategy is garbage collection (also used in Python).

Tail recursion, an important optimization

Tail recursion can be straightforwardly implemented in a register machine by ensuring a special treatment for the last expression in a sequence of expressions. For the last expression, the continue register is just set to the continuation specified by the original caller to the sequence. This precludes the need to save additional variables (continue, env, rest-exps, etc) on the stack that would simply be popped out later before returning for the final time.