# [Yhc] What constitutes an 'evaluated node'?

Stefan O'Rear stefanor at cox.net
Thu Mar 1 10:12:42 EST 2007

```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
```