Difference between call-by-value and call-by-name interpreter for the lambda calculus

Question

In another question, Bob presented the following interpreter for the untyped lambda calculus.

data Expr = Var String | Lam String Expr | App Expr Expr

data Value a = V a | F (Value a -> Value a)

interpret :: [(String, Value a)] -> Expr -> Value a
interpret env (Var x) = case lookup x env of
  Nothing -> error "undefined variable"
  Just v -> v
interpret env (Lam x e) = F (\v -> interpret ((x, v):env) e)
interpret env (App e1 e2) = case interpret env e1 of
  V _ -> error "not a function"
  F f -> f (interpret env e2)

Ivan Zakharyaschev remarked that this interpreter is call-by-value due to F f -> f (interpret env e2). How would the implementation of a call-by-name interpreter be different from the one presented above?

Plotkin studied call-by-name and call-by-value strategies for evaluating the lambda calculus in the 1970s.

This looks like call by need to me, since Haskell is call by need (modulo pedantry) — luqui, Mar 01 '15 at 04:45
@loqui This is definitely not call-by-need or call-by-name. The normal call-by-name Y combinator causes an [infinite loop](http://stackoverflow.com/a/6715144/414413), suggesting that this is in fact call-by-value and requires a call-by-value [fixed-point combinator](http://en.wikipedia.org/wiki/Fixed-point_combinator). — Cirdec, Mar 11 '15 at 23:18

András Kovács · Accepted Answer · 2015-03-01T14:42:33.977

I don't think proper call-by-name is possible with the original data definition. F (Value a -> Value a) has Value a as argument, so we have no choice but to pass in some already interpreted value, and it'll be call-by-need under Haskell reduction behaviour.

We could modify the data definition:

data Value a = V a | F ((() -> Value a) -> Value a)

And also have the interpreter return explicit thunks:

interpret :: [(String, () -> Value a)] -> Expr -> () -> Value a
interpret env (Var x) = delay (case lookup x env of
  Nothing -> error "undefined variable"
  Just v -> force v)
interpret env (Lam x e) = delay (F (\v -> force (interpret ((x, v):env) e)))
interpret env (App e1 e2) = delay (case force (interpret env e1) of
  V _ -> error "not a function"
  F f -> f (interpret env e2))

force :: (() -> a) -> a
force f = f ()
{-# NOINLINE force #-}

delay :: a -> () -> a
delay a () = a
{-# NOINLINE delay #-}

Now, instead of storing a thunk in the environment, we store a partial application object, and then evaluate it separately at different call sites.

force and delay are required to prevent GHC from floating out function bodies, thereby recovering sharing. Alternatively, one could compile with {-# OPTIONS -fno-full-laziness #-} and use simple lambdas and applications instead instead of the above machinery.

Unfortunately, GHC relies on full laziness very heavily to support other transformations. Maybe someone will do something about that some day, but I'm not optimistic. — dfeuer, Mar 01 '15 at 13:47

score 3 · Answer 2 · answered Mar 01 '15 at 08:44

CBV/CBN are concepts related to the evaluation strategy of the lambda calculus, i.e. related to the choice of redex in lambda term reduction. In an operational-style interpreter which reduces terms representations, you can properly speak of CBV/CBN.

In a denotational-style interpreter like the posted one, I'd speak of eager vs lazy semantics, instead of CBV/CBN. Of course eager corresponds to CBV, and lazy to CBN.

Since Haskell is lazy, the code

interpret env (App e1 e2) = case interpret env e1 of
  V _ -> error "not a function"
  F f -> f (interpret env e2)

implements a lazy semantics (CBN). (As luqui states, operationally GHC would reduce this in a call-by-need fashion).

To get an eager (CBV) semantics, we can force the argument before the call:

interpret env (App e1 e2) = case interpret env e1 of
  V _ -> error "not a function"
  F f -> case interpret env e2 of
         V v -> f v
         F g -> f g

This ensures that no unevaluated thunks are fed to a function, unless they are already in the environment. The environment, however, is populated only when evaluating a lambda, which will insert the values v,g above in the environment. Hence, no thunks will be inserted there.

Difference between call-by-value and call-by-name interpreter for the lambda calculus

2 Answers2