2009/10/5 Robert Atkey
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