allocate-registers n, cont ; the argument, continuation,
allocate-registers val ; and result of factorial procedure
allocate-registers factorial, base-case ; these hold labels' values
allocate-registers sp ; this is the "stack pointer", it records how many
; memory locations are occupied by saved values
; (starting at location 0)
allocate-registers one ; this holds the constant 1, used in several places
;; set up the constants
li one, 1
li factorial, factorial-label
li base-case, base-case-label
;; initialize the stack pointer (nothing saved yet)
li sp, 0
;; set up for the top level call to factorial
read n ; the argument, n, is read in
li cont, after-top-level ; the continuation is set
;; and then we can fall right into the procedure
factorial-label:
;; computes the factorial of n into val and jumps to cont;
;; doesn't touch the first sp locations of memory and
;; restores sp back to its entry value when cont is jumped to;
;; assumes the factorial, base-case, and one registers hold the
;; constant values established at the beginning of the program
jeqz n, base-case
;; if n isn't zero, we save n and cont into memory for
;; safe keeping while computing (n-1)!; sp tells us where in
;; memory to save them (so as not to clobber other, previously
;; saved values), and we adjust sp to reflect the new saves
st n, sp
add sp, sp, one
st cont, sp
add sp, sp, one
;; now that we're done saving, we can set up for (n-1)!
sub n, n, one ; using n-1 as the new n argument
li cont, after-recursive-invocation ; the continuation
j factorial ; after this call
after-recursive-invocation: ; is down here
;; having made it through the recursive call, the saved
;; values of cont and n can be restored to their registers
;; from memory; note that they are "popped" from the stack
;; in the opposite order they were "pushed" onto the stack,
;; since the second one pushed wound up "on top" (i.e., later
;; in memory), so should be retrieved first
sub sp, sp, one
ld cont, sp
sub sp, sp, one
ld n, sp
;; having retrieved n and cont and set sp back to the way it
;; was on entry (since it went up by two and back down by two)
;; we are ready to compute n! as (n-1)! * n, i.e. val * n,
;; putting the result into val, and jump to the continuation
mul val, val, n
j cont
base-case-label:
;; this is the n = 0 case, which is trivial
li val, 1
j cont
after-top-level:
;; when the top level factorial has put n! in val, it jumps here
write val ; to display that result
halt