> But normal order evaluation with memoization (what human computer would do - write result only once) uses graphs and graph rewriting.

...which are still most simply implemented with a stack.