\ Ackermann function, illustrating use of "memoization".

\ Memoization is a technique whereby intermediate computed values are stored
\ away against later need.  It is particularly valuable when calculating those
\ values is time or resource intensive, as with the Ackermann function.

\ make the stack much bigger so this can complete!
100000 stack-size

\ This is where memoized values are stored:
{} var, dict

\ Simple accessor words
: dict! \ "key" val --
  dict @ -rot m:! drop ;

: dict@ \ "key" -- val
  dict @ swap m:@ nip ;

defer: ack1

\ We just jam the string representation of the two numbers together for a key:
: makeKey  \ m n -- m n key
	2dup >s swap >s s:+ ;

: ack2 \ m n -- A
	makeKey dup
	dict@ null?
	if \ can't find key in dict
		\ m n key null
		drop \ m n key
		-rot \ key m n
		ack1 \ key A
		tuck \ A key A
		dict! \ A
	else \ found value
		\ m n key value
		>r drop 2drop r>
	then ;

: ack \ m n -- A
	over not
	if
		nip n:1+
	else
		dup not
		if
			drop n:1- 1 ack2
		else
			over swap n:1- ack2
			swap n:1- swap ack2
		then
	then ;

' ack is ack1

: ackOf \ m n --
        2dup
        "Ack(" . swap . ", " . . ") = " . ack . cr ;


0 0 ackOf
0 4 ackOf
1 0 ackOf
1 1 ackOf
2 1 ackOf
2 2 ackOf
3 1 ackOf
3 3 ackOf
4 0 ackOf

\ this last requires a very large data stack.  So start 8th with a parameter '-k 100000'
4 1 ackOf

bye