Call‑by‑name will succeeds where call‑by‑value may fails: some example cases? 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 () =&gt; 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 () =&gt; 2)) ^ "\n")
val r = call_by_need (fn () =&gt; 2) ()  (* memoization *)
val _ = print (Int.toString r ^ "\n")
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.