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

David Menendez dave at zednenem.com
Mon Oct 5 19:22:59 EDT 2009

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"?


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
    update m = m >>= \x -> writeSTRef r (Left x) >> return x

Dave Menendez <dave at zednenem.com>

More information about the Haskell-Cafe mailing list