2009/10/5 Robert Atkey <bob.atkey@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@zednenem.com> <http://www.eyrie.org/~zednenem/>