About

I'm Nicholas FitzRoy-Dale, a software developer from London, UK. I'm interested in embedded systems and operating system research, code optimisation, 8-bit music, rock climbing, shiny things...

Personal blog

Contact

May 11
2014

Call-by-name semantics

I’ve been playing around with call-by-name semantics recently, and they’re kind of interesting. This post is about function calling behaviour, and I’m not an expert in the field, so I apologise in advance if I get some of this wrong. (Please point it out to me if I do.)

Most programming languages use call-by-value or call-by-reference semantics, or some combination. Under call-by-value semantics, when calling a function, each argument passed to the function is first evaluated. The values are then supplied to the function. So, for example, using a lisp-like language I’ve been playing with, here is a definition of a function called add1. It takes one argument, named lhs. When it’s called, it adds 1 to its parameter and returns the result.

(def add1 (lhs) (
(+ lhs 1)))

If you were to call it like this:

(add1 (* a 2))

… then, under call-by-value semantics, here’s what happens
  1. The expression (* a 2) is evaluated, yielding an integer (presumably).
  2. That integer is passed to “add1” and bound to “lhs”.
  3. add1 executes, adding the value of lhs, which is just an integer, to 1.
Call-by-name, however, behaves differently. Under call-by-name, function arguments are not evaluated immediately prior to the function call. Instead, the function can choose to evaluate them whenever it likes — it can also not evaluate them, or it can evaluate them more than once. Here is what happens during a call to to add1 if you rewrite it to use call-by-name semantics:
  1. The expression (* a 2) is compiled to a thunk, which is a parameterless closure — it’s a callable thing (i.e. it is code which produces a value), which retains the scope of wherever it was defined.
  2. A pointer to the closure is passed to add1.
  3. add1 evaluates “lhs”, which results in an integer.
  4. add1 adds the result of the evaluation to 1 and returns it.
On the face of it, this seems a lot more work for little gain. But thunks capture the scope of wherever they are defined, which means you can do very cool things. For example, you can implement iterators by having your expression return different things each time it’s evaluated. You can also implement control structures. For example, logical AND and OR are short-circuiting operators, which means they don’t evaluate their second parameter if they don’t need to. So you could implement them as taking their second parameter by-name. Here’s an example for “or”, where “>” is syntax for by-name calling, and “if” takes three arguments, being an expression, a list of expressions to evaluate in the true case, and a list of expressions to evaluate in the false case:

(def || (lhs >rhs) (
(if lhs (true) (if (rhs) true false))))

Note that rhs has parentheses around it to evaluate it, whereas lhs doesn’t.

Of course, what actually gives call-by-name its power is closures. But it’s quite interesting to see that call-by-name gives you quite a lot of the the same power without ever exposing closures to the programmer. By-name parameters let the function author choose whether arguments are evaluated eagerly or lazily.

There are two downsides to call-by-name.

Firstly, it’s quite a lot of overhead. Some of this can be ameliorated in the compiler, but I do recognise that “this isn’t a problem given a sufficiently powerful compiler” is a hymn which has been sung for a long time now.

Secondly, it’s potentially terribly confusing if you don’t realise what’s going on. For example, if you pass a side-effect-generating argument as a by-name parameter, then it will possibly be evaluated more or fewer times than you’d like. That seems fine for implementing simple, well-known things such as short-circuiting Boolean operators, and even for implementing complex, well-known control structures such as, for example, generators, but it’s probably not really a good idea for any other reason.

ALGOL was entirely call-by-name. Simula and Scala support it in roughly the above way (by annotating function arguments). Someone on the c2 wiki reckons that the C preprocessor is an extreme form of call-by-name. And of course you get some approximation of it in any language which lets you define closures.