allocate-registers x, y, ackermann, zero, one, two, cont, sp, result, tmp

li zero, 0
li one, 1
li two, 2
li ackermann ackermann-label
read x
read y

li cont end-label
j ackermann
end-label:
write result
halt

;; Procedure to compute Ackermann's function which is defined recursively:
;; A(0,y) = 1                for y >= 0
;; A(1,0) = 2
;; A(x,0) = x+2              for x > 0
;; A(x,y) = A(A(x-1,y),y-1)  for x,y > 0
;; Return value placed in registure result

Ackermann-label:

;; BASE CASES FIRST
;; Loading result temporarily rather than jumping to base cases.

li result 1        ;; A(0, y) = 1
jeqz x cont

li result 2        ;; A(1, 0) = 2
add tmp x y
sub tmp tmp one
jeqz tmp cont

add result x two   ;; A(x, 0) = x+2
jeqz y cont

;; THE GENERAL CASE A(x,y) = A(A(x-1,y), y-1)

st y sp            ;; Save y and cont on stack
add sp one sp
st cont sp
add sp one sp

sub x x one        ;; Compute A(x-1, y)
li cont after-recursive
j ackermann  

after-recursive:
sub sp sp one      ;; Restore y and cont from stack
ld cont sp
sub sp sp one
ld y sp

;; Because the procedure is "tail recursive", all of the remaining
;; lines can be replaced with the single line "j ackermann"

st cont sp    ;; store cont on stack
add sp one sp

add x result zero
sub y y one
li cont after-second
j ackermann   ;; Compute A(result, y-1)
after-second:

sub sp sp one ;; restore cont from stack
ld cont sp

j cont