data stack as history

iepos@tunes.org — 2000-07-15 00:19:28

Hello folks ... well, I guess I should apologize for bringing up yet

another topic while Manfred is still trying to catch up :-)

I'll try to make this quick. Here is the little thought which I wanted

to share:



The data stack can be thought of as a complement to the instruction

queue. Whereas the instruction queue can be thought of as a plan for

the future, the data stack can be thought of as a history of the past

(not the entire past, of course; only the important things which must

be remembered).



Now, this leads me to discuss a bit about Lazy Evaluation. Whereas

usually the data stack only contains literals such as "2", "3",

or "[dup *]", it would be an interesting thing to implement

lazy evaluation by leaving Operators or other such things on

the history (the stack).



For example, suppose one did "2 3 +". Normally this would cause

"5" to be pushed onto the stack. But, a lazy system might simply

dump "2 3 +" onto the stack, as a history, pretending that "2 3 +"

had actually been executed. Of course, in this specific example,

this would be ridiculous, since "+" is such a trivial operator,

and space would be saved by going ahead and executing it.

However, there must be other examples, where the operator in question

is quite computationally expensive or where the solution requires

more storage than the problem; in those cases, lazy evaluation could

be useful.



Also, copy-by-reference could be viewed as a sort of lazy evaluation.

If one has a large structure on the stack and "dup" needs to be executed,

one could simply dump "dup" onto the history rather than physically

copying. This would be an odd technique; I'm not sure that it would

work well in practice.



The pitfall of lazy evaluation is when it comes time to execute an

side-effecting operator, such as ".", which requires physical evaluation

of the stack. It would then become necessary for the system to go

back and actually execute some of those operators that it just stashed

in the history.



Anyway, that's just a little food for thought.



- Brent Kerby