Our Goals

The system we develop should have all of the following characteristics.

• It should be intuitive to program for. The procedure bodies should be easily readable and writable by humans, even in assembler form.

• It should be efficient. Variable accesses are very common, so procedures shouldn't cost much to run.

• It should allow multiple arity in both arguments and return values. We won't require that an unlimited amount of information be passable, but it should allow more than the three bytes the registers give us.

• It should permit tail call elimination, an optimization that will allow certain forms of recursion to actually not grow the stack.

Here is a system that meets all these properties.

• Reserve two bytes of the zero page for a stack pointer. At the beginning of the program, set it to the top of memory.

• Divide the remainder of Zero Page into two parts:

  • The scratch space, which is where arguments and return values go, and which may be scrambled by any function call, and

  • The local area, which all functions must restore to their initial state once finished.

• Assign to each procedure a frame size S, which is a maximum size on the amount of the local area the procedure can use. The procedure's variables will sit in the first S bytes of the local area.

• Upon entering the procedure, push the first S bytes of the local area onto the stack; upon exit, pop hose S bytes back on top of the local area.

• While the procedure is running, only touch the local area and the scratch space.

This meets our design criteria neatly:

• It's as intuitive as such a system will get. You have to call init'stack at the beginning, and you need to ensure that save'stack and restore'stack are called right. The procedure's program text can pretend that it's just referring to its own variables, just like with the old style. If a procedure doesn't call anyone, then it can just do all its work in the scratch space.

• It's efficient; the inside of the procedure is likely to be faster and smaller than its FORTRAN-style counterpart, because all variable references are on the Zero Page.

• Both arguments and return values can be as large as the scratch space. It's not infinite, but it's probably good enough.

• Tail call elimination is possible; just restore the stack before making the JMP to the tail call target.

The necessary support code is pretty straightforward. The stack modification routines take the size of the frame in the accumulator, and while saving the local area, it copies over the corresponding values from the scratch space. (This is because most functions will be wanting to keep their arguments around across calls.)

.scope
; Stack routines
.data zp
.space _sp      $02
.space _counter $01
.space fun'args $10
.space fun'vars $40

.text
init'stack:
        lda     #$00
        sta     _sp
        lda     #$A0
        sta     _sp+1
        rts

save'stack:
        sta     _counter
        sec
        lda     _sp
        sbc     _counter
        sta     _sp
        lda     _sp+1
        sbc     #$00
        sta     _sp+1
        ldy     #$00
*       lda     fun'vars, y
        sta     (_sp), y
        lda     fun'args, y
        sta     fun'vars, y
        iny
        dec     _counter
        bne -
        rts

restore'stack:
        pha
        sta     _counter
        ldy     #$00
*       lda     (_sp), y
        sta     fun'vars, y
        iny
        dec     _counter
        bne -
        pla
        clc
        adc     _sp
        sta     _sp
        lda     _sp+1
        adc     #$00
        sta     _sp+1
        rts
.scend