[Yhc] What constitutes an 'evaluated node'?

[Tom Shackell]

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.

Now the yhc byte-code for g would be something along the lines of

   g(a,b,c,d):
     PUSH_ARG d
     EVAL
     PUSH_ARG c
     EVAL
     ADDI
     PUSH_ARG b
     EVAL
     ADDI
     PUSH_ARG a
     EVAL
     ADDI
     RETURN

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!

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

Hope that helps


Tom