About call-by-value, call-by-name and thunking

This is something nice I learned during the winter school in Marseille, and used right after it on a program I was implementing in OCaml. This week I finally got the time to write it down nicely with an example that hopefully makes things easier to understand =)

So in programming we often use some functions, right? These functions have arguments (which can be themselves functions). Call-by-value and call-by-name are two different strategies to deal with these arguments (and please do not confuse this with passing parameters as values and as references… these are actually two ways of passing parameters in the call-by-value paradigm, if I understand correctly). Here’s a brief explanation of both:

Call-by-value
The arguments of a function are evaluated and then their results are passed to the function.

Call-by-name
The arguments of a function are substituted directly on the function’s body and evaluated only when necessary.

Take, for example, the following function:

let f x = x +x

and apply it to (print “hi!!”; 4).
If  f (print “hi!!”; 4) is evaluated using a call-by-value strategy, the argument will be evaluated once, hi!! will be printed and the return value will be 8.
If  f (print “hi!!”; 4) is evaluated using a call-by-name strategy, the argument will be copied to the body of the function, which will become: (print “hi!!”; 4) + (print “hi!!”; 4). Then, each part of the sum will be evaluated, hi!! will be printed twice and the return value will be 8.

Now, as far as I know, most of the languages use the call-by-value strategy. Maybe because of efficiency, since the repeated use of an argument would cause it to be evaluated several times in the call-by-name strategy. But sometimes it is the case that we actually want a call-by-name strategy to be used. This happened to me when I was implementing a continuation passing style. Basically my function had two arguments, which were functions themselves, called success and fail. Some computation was done and depending on the result the function would be continued by success or fail. Now, I did not want these functions to be executed right away, of course, but only when I had already computed something and decided which was the case. This was implemented in OCaml, which uses the call-by-value strategy. So, in order to simulate a call-by-name, I had to use something called thunking.

Thunk
Thunks are types such as ()-> A which are used to delay evaluation, i.e., if a parameter of a function is of thunk type, it is not evaluated until needed, in a call-by-name style. Thunks simulate CBN in a CBV language.

This is easier to see with an example:

(* Quick OCaml example of call-by-value, call-by-name and thunking *)


let arg () = 
  print_endline “Function evaluated.”
;;


let cbv f =
  print_endline “=> Not using the argument, evaluated anyway.”
;;


let cbn f = 
  print_endline “=> Not using the argument, not evaluated.”
;;


let _ = 
  print_endline “Call-by-value:”;
  cbv (arg ());
  print_endline “Call-by-name:”;
  cbn (fun () -> arg ())
;;

You can try this by saving a file and executing it with ocaml. Cool, isn’t it?