Implementing call-by-value lambda-calculus in Haskell

Question

When implementing call-by-value lambda-calculus in Haskell, should I force the evaluation of the arguments to a function in the object language (i.e., the call-by-value lambda-calculus) to get around the call-by-need evaluation order of the meta-language (i.e., Haskell)?

Concretely, for the following implementation using higher-order abstract syntax:

data Exp
  = Abs (Exp -> Exp)
  | App Exp Exp

eval :: Exp -> Exp
eval exp = case exp of
  Abs _       -> exp
  App opr opd -> case eval opr of
    Abs fun -> eval (fun $ eval opd)  -- argument evaluation

on the line with comment, should I force the evaluation of eval opd by using fun $! eval opd instead?

I am aware that the evaluation order dependence between the object and meta- level can be avoid by CPS transformation. But I do not wanna bother it for the moment. I just wanna make sure that call-by-value is implemented faithfully in Haskell. I raised this question because many example implementations I have seen seem not to take this into account. I mean those implementations do not force eval opd. I wonder whether it is that they neglect it or that I consider too much. Thanks.

Answer 1

Using $! does work here, as long as evaluating eval e to weak head normal form in the meta-language corresponds to evaluating e to a value in the object language.

Let me demonstrate that by adding a new constructor to the Exp data type to represent a diverging computation, and a value that we can actually print:

data Exp
  = Abs (Exp -> Exp)
  | App Exp Exp
  | Bot
  | Value

printExp :: Exp -> String
printExp Bot = "bottom"
printExp Value = "base value"
printExp (Abs _) = "function"
printExp (App _ _) = "thunk"

For simplicity, let’s just transform it to a call to error in the evaluation function.

eval :: Exp -> Exp
eval exp = case exp of
  Bot         -> error "Evaluation would not terminate "
  Value       -> Value
  Abs _       -> exp
  App opr opd -> case eval opr of
    Abs fun -> eval (fun $ eval opd)

Now we can see if this is call-by-value. The following code should diverge, as we are passing bottom to a function. Alas, it does not:

*Main> let e = App (Abs (\_ -> Value)) Bot
*Main> printExp e
"thunk"
*Main> printExp (eval e)
"base value"

Does it help to change $ to $!? Yes, it does:

*Main> let e = App (Abs (const Value)) Bot
*Main> printExp (eval e)
"*** Exception: Evaluation would not terminate 

But how reliable is that? Any change to the Exp datatype has to be carefully checked to see if forcing the outermost constructor is what you want, e.g. introduction of pairs.

It might be a bit more reliable to use deepseq, i.e. $!!. But what I would really suggest is to add a isValue :: Exp -> Bool predicate that explicitly checks if the argument is a base value of your object language, and check isValue (eval opd) in eval before calling fun.