[Yhc] What constitutes an 'evaluated node'?

[Stefan O'Rear]

On Thu, Mar 01, 2007 at 10:49:14AM +0000, Tom Shackell wrote:
> Hi Stefan,
> 
> > Some of the bytecodes, eg INT_SWITCH, require the node they are
> > applied to, to be 'evaluated'.  EVAL takes a node and returns an
> > equivalent evaluated node.  However in the current implementation
> > (Yhi) EVAL has the side-effect of making any other reference to the
> > original node become evaluated.
> 
> This is a definite 'feature', in fact it's entirely integral to the 
> correct handling of lazy evaluation. Remember that in Haskell no 
> computation is actually performed unless it is needed in order to 
> produce an output. Thus for example
> 
>   const x y = y
> 
>   f = const (...really expensive...) 3
> 
> because const doesn't need the value of x in order to give a result the 
> 'really expensive' computation isn't needed and is thus never performed.
> 
> Similarly Haskell avoids doing the same computation twice
> 
>   f = g x x x x
>     where
>     x = ... some really expensive computation ...
> 
>   g a b c d = a + b + c + d
> 
> Here although x is passed to g 4 times (and g will only evaluate x when 
> it needs to), the really expensive computation will only be done once.

I'm sorry, I seem to have horribly mangled my question.  in the present
implementation:

ptr1 -----> Some Big
ptr2 -----> Full PAP

after EVAL: 
           /-----------\
ptr1 -----/ An Ind-     \--V 
ptr2 -----> irection ---> Value

after POP_1:
             An Ind-
ptr1 ----->  irection ---> Value

INT_SWITCH examines Value.

In the implementation I'm trying for, INT_SWITCH would examine the
indirection, BUT in my implentation EVAL *does* chase indirections,
so:

g(ptr1,ptr2) = ptr1 `seq` ptr2

ptr1 -----> Some Big
ptr2 -----> Full PAP

after EVAL: 
           /-----------\
ptr1 -----/ An Ind-     \--V 
ptr2 -----> irection ---> Value

after POP_1:
             An Ind-
ptr1 ----->  irection ---> Value

after EVAL: (chases the ind):
             An Ind-
ptr1 ---\    irection  /-> Value
         \------------/
which is returned.  (yes I know about RETURN_EVAL)

> Now if EVAL didn't update all the other references to '... some really 
> expensive computation ...' then g would end up doing the expensive 
> computation 4 times.

> However because when EVAL first evaluates the expensive computation it 
> replaces it with an indirection to it's result then it only does the 
> expensive computation once.
> 
> Doing something 4 times when you could do it once is bad enough. But 
> infact it can be a lot more than this, with certain examples not having 
> memorization can turn a linear algorithm into an exponential one!
Known, known, known.
> For a more thorough explanation of implementation lazy functional 
> programming languages I suggest reading 'Implementing Functional 
> Programming Languages: A tutorial' by Simon Peyton Jones and David 
> Lester, the full text is available online
> 
> http://research.microsoft.com/%7Esimonpj/Papers/pj%2Dlester%2Dbook/
> 
> There is also a more in-depth version available called 'The 
> implementation of functional programming languages', which is also 
> available online:
> 
> http://research.microsoft.com/~simonpj/Papers/slpj-book-1987/index.htm
Am doing so since about a week ago :)

Hope this time it makes more sense

Stefan