CODEWITHSUNDEEP
haskelllambda-calculuscallbynamecall-by-value
Cirdec
Cirdec

Reputation: 24166

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

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.

Upvotes: 4

Views: 2150

Answers (2)

András Kovács
András Kovács

Reputation: 30103

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.

Upvotes: 5

chi
chi

Reputation: 116174

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.

Upvotes: 3

Related Questions