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

Robert Atkey bob.atkey at ed.ac.uk
Wed Oct 7 15:23:36 EDT 2009

On Mon, 2009-10-05 at 19:22 -0400, David Menendez wrote:
> > The two obvious options are
> > call-by-name and call-by-value.
> I wonder how easily one can provide both, like in Algol.

Fairly easy, you can either do a language that has an explicit monad (a
bit like Haskell with only the IO monad), or you can go the whole hog
and embed Paul Levy's Call-by-push-value. This requires a bit more
cleverness, and an explicit representation of the embedded types in
order to define the algebra maps on the computation types.

> 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

I had a go at this and it seems to work. Happily, it is a tiny tweak to
the CBV implementation I gave: you just replace "return" with your
"evalThunk" (or something like it) and wrap the argument in the 'app'
case with a function that creates a thunk.


The University of Edinburgh is a charitable body, registered in
Scotland, with registration number SC005336.

More information about the Haskell-Cafe mailing list