TITLE	"Fibonacci numbers"
;	-- optimized but still recursive

	USE	"hawk.h"
	USE	"monitor.h"
	INT	MAIN
	S	MAIN

	SUBTITLE"Recursive Fibonacci function"
; activation record format
RETAD	=	0
I	=	4
J	=	8
K	=	12
ARSIZE	=	16

;	expect R1 = return address
;	uses   R2 = stack pointer for activation records
;	expect R3 = i, the parameter
;	return R3 = fib(i)
;	use    R4-...

FIB:	STORES	R1,R2		; save return addr
				; for now, parameter i in R3
	CMPI	R3,1
	BLEU	ENDIF		; if (i > 1) {
				;   -- i is in R3
	STORE	R3,R2,I		;   -- save parameter i
	ADDSI	R3,-1		;   -- parameter: i-1
	ADDI	R2,R2,ARSIZE	;   -- push my AR
	JSR	R1,FIB
	ADDI	R2,R2,-ARSIZE	;   -- pop my AR
	STORE	R3,R2,J		;   j = fib( i - 1 )
	
	LOAD	R3,R2,I
	ADDSI	R3,-2		;   -- parameter: i-2
	ADDI	R2,R2,ARSIZE	;   -- push my AR
	JSR	R1,FIB
	ADDI	R2,R2,-ARSIZE	;   -- pop my AR
				;   k = fib( i - 1 ) (k is in R3 here)
	LOAD	R4,R2,J
	ADD	R3,R3,R4	;   i = j + k (i is now in r3 )

ENDIF:				; }
				; i is in R3 on all branches to here
	LOADS	R1,R2
	JUMPS	R1		; return i

	SUBTITLE"Main program"
; activation record format
RETAD	=	0
I	=	4
ARSIZE	=	8

;	expect R1 = return address
;	uses   R2 = stack pointer for activation records

MAIN:	; main program
	STORES	R1,R2		; save return address
	LIS	R3,0
	STORE	R3,R2,I		; i = 0;
LOOP:
	LOAD	R3,R2,I
	CMPI	R3,20
	BGE	DONE		; while (i < 20) {

	LOAD	R3,R2,I
	ADDI	R2,R2,ARSIZE	;   -- push my AR
	JSR	R1,FIB
	ADDI	R2,R2,-ARSIZE	;   -- pop my AR
				;   -- param: fib( i )
	LIS	R4,8		;   -- param: 8
	ADDI	R2,R2,ARSIZE	;   -- push my AR
	LIL	R1,PUTDEC
	JSRS	R1,R1
	ADDI	R2,R2,-ARSIZE	;   putdec( fib( i ), 8 )

	LOAD	R3,R2,I
	ADDSI	R3,1
	STORE	R3,R2,I		;   i = i + 1

	BR	LOOP		; }
DONE:
	LOADS	R1,R2
	JUMPS	R1		; return

	END