The difference between a call by value and an interpreter by name for lambda calculus

Question

In another question, Bob introduced the following interpreter for 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 Zakharyashev noted that this interpreter is significant in value because of F f -> f (interpret env e2). How can the implementation of the interpreter by name differ from the above?

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

Answer 1

, . F (Value a -> Value a) Value a , , - , Haskell.

:

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

, 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 #-}

thunk , .

force delay GHC , . {-# OPTIONS -fno-full-laziness #-} .

Answer 2

CBV/CBN , -, redex -. , , CBV/CBN.

, , CBV/CBN. , CBV CBN.

Haskell ,

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

(CBN). ( luqui, GHC ).

(CBV), :

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

, thunks , . , v, g . , .