[Haskell-cafe] Finally tagless - stuck with implementation of "lam"

[David Menendez]

2009/10/5 Robert Atkey <bob.atkey at ed.ac.uk>:
> Hi Günther,
>
> The underlying problem with the implementation of 'lam' is that
> you have to pick an evaluation order for the side effects you want in
> the semantics of your embedded language. The two obvious options are
> call-by-name and call-by-value.

I wonder how easily one can provide both, like in Algol.


> The other obvious evaluation strategy is call-by-need, as used by
> Haskell itself, but I don't know if it is possible to implement this. I
> guess it may be possible using the ST monad as the mutable storage of
> thunks.

Perhaps something along the lines of "Purely Functional Lazy
Non-deterministic Programming"?

<http://okmij.org/ftp/Computation/monads.html#lazy-sharing-nondet>

Obviously, doing a deterministic version is simpler. You can probably
get away with representing values as simple self-evaluating thunks.

data Thunk s a = STRef s (Either a (ST s a))

evalThunk :: Thunk s a -> ST s a
evalThunk r = readSTRef r >>= either return update
    where
    update m = m >>= \x -> writeSTRef r (Left x) >> return x

-- 
Dave Menendez <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>