[Haskell-cafe] CBN, CBV, Lazy in the same final tagless framework

[oleg at okmij.org]

Actually it is possible to implement all three evaluation orders
within the same final tagless framework, using the same interpretation
of types and reusing most of the code save the semantics of lam. That
is where the three orders differ, by their own definition.

In call-by-name, we have
    lam f   = S . return $ (unS . f . S)

In call-by-value, we have
    lam f   = S . return $ (\x -> x >>= unS . f . S . return)

In call-by-need, we have
    lam f   = S . return $ (\x -> share x >>= unS . f . S)

In CBV, the function first evaluates its argument, whether the value
will be needed or not. In call-by-need, we arrange for the sharing of
the result should the computation be evaluated.

Here is an illustrative test

t2 :: HOAS exp => exp IntT
t2 = (lam $ \z -> lam $ \x -> let_ (x `add` x)
                      $ \y -> y `add` y) `app` (int 100 `sub` int 10)
                                         `app` (int 5 `add` int 5)

t2SN = runName t2 >>= print
{-
*CB> t2SN
Adding
Adding
Adding
Adding
Adding
Adding
Adding
40
-}
In CBN, the result of subtraction was not needed, and so it was not performed
OTH, (int 5 `add` int 5) was computed four times.


t2SV = runValue t2 >>= print
{-
*CB> t2SV
Subtracting
Adding
Adding
Adding
40
-}
In CBV, although the result of subtraction was not needed, it was
still performed. OTH, (int 5 `add` int 5) was computed only once.

t2SL = runLazy t2 >>= print
{-
*CB> t2SL
Adding
Adding
Adding
40
-}
Now, Lazy is better than both CBN and CBV: subtraction was not needed,
and it was not performed.  All other expressions were needed, and
evaluated once.

The complete code is at
	http://okmij.org/ftp/tagless-final/CB.hs