1
$\begingroup$

I've landed to SML pages, comparing call‑by‑name and call‑by‑value, asserting the former always succeed while the latter may fails. As this seems counter intuitive to me, I feel at least an example case would be useful.

Call-by-value, call-by-name and call-by-need

Theorem (Church Rosser 1)

For a purely functional language, if call-by-value evaluation and call-by-name evaluation both yield a well-defined result then they yield the same result.

Theorem (Church Rosser 2)

If a well-defined result exists for an expression then the call-by-name evaluation strategy will find it where, in some cases, call-by-value evaluation will not.

What make it counter‑intuitive to me, is that call‑by‑name may re‑evaluate expressions multiple times, which I don't understand how it can make it succeed when call‑by‑value and its one‑time evaluation, would fails. If, as the context is FP and its referential transparency, both expression are supposed to evaluated to the same, how evaluating multiple time may make something succeed or alternatively potentially fails if the same expression is evaluated only once? Unless there are side‑effect somewhere?… is this related to side effects and non‑pure FP?

As a reminder, here is what would look like call‑by‑value and call‑by‑name with SML (if there is an error here, feel free to tell), added call‑by‑need to help not confuse one with the others:

(* This, is supposed to sometime fails… *)

fun call_by_value a =
   a + a  (* `a` is evaluated only once *)

(* …when this is supposed to succeed *)

fun call_by_name a =
   a () + a ()  (* `a` is evaluated for each of its reference *)

(* None of the above should be confused with call‑by‑need: *)

fun call_by_need a =
   let val a' = a ()  (* memoization *)
   in fn () => a' + a'  (* to be evaluated when needed *)
   end

val _ = print (Int.toString (call_by_value 2) ^ "\n")
val _ = print (Int.toString (call_by_name (fn () => 2)) ^ "\n")
val r = call_by_need (fn () => 2) ()  (* memoization *)
val _ = print (Int.toString r ^ "\n")
$\endgroup$
2
  • 1
    $\begingroup$ Note: this has nothing to do with computability theory. $\endgroup$
    – Raphael
    Jul 22, 2014 at 14:15
  • $\begingroup$ @Raphael, thanks for the notice, I will care of it and will review the purpose of computability theories. $\endgroup$
    – Hibou57
    Jul 22, 2014 at 14:39

2 Answers 2

5
$\begingroup$

Call-by-value evaluates the arguments to a function exactly once. Call-by-name evaluates the arguments to a function, zero, once, or more times. Call-by-need evaluates the arguments to a function zero or once, but not more than once.

The trick you are looking for here is a case where call-by-value needs to evaluate an argument once while call-by-name does not need to evaluate its argument at all. The particular thing that Church and Rosser were worried about was that the argument might be an infinite loop.

So if I have the following

fun call_by_name (cond a b) =
  if cond
    a
  else
    b

and

fun loop_forever () =
   loop_forever()

Then

call_by_name(true, 1, loop_forever())

will return 1 while

call_by_value(true, 1, loop_forever())

will loop forever.

Actually, call-by-name is super cool because it allows you to implement control-flow constructs like if-then-else and while-do. Suppose, for example that your language doesn't have if-then-else built in. You can implement boolean values True and false and if-then-else in call-by-name as follows:

fun True  (t f) = t
fun False (t f) = f
fun if_else (cond t f) = cond(t f)

Now

if_else(True, 1, loop_forever())

returns 1 and

if_else(False, loop_forever(), 0)

returns 0.

$\endgroup$
2
  • $\begingroup$ “Actually, call-by-name is super cool because it allows you to implement control-flow constructs like if-then-else and while-do.”: which is also related to LISP's quoted expressions. $\endgroup$
    – Hibou57
    Jul 22, 2014 at 15:26
  • 1
    $\begingroup$ What's amazing is that I first read about call-by-name in a book about Algol (either 60 or 68, but I think Algol 60), and now it is available in Swift 3 under the name "auto closure". 55 years later. $\endgroup$
    – gnasher729
    Feb 23, 2017 at 22:17
3
$\begingroup$

This is a bit simpler (in OCaml notation):

(fun x => 42) (let rec f x = f x in f ())

It loops in call-by-value and returns 42 in call-by-name and call-by-need.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.