3
$\begingroup$

I am reading Software Engineering 1: Abstraction and Modelling by Dines Bjørner. One of the chapters talks a little bit about call-by-value vs call-by-name. In it, the author states that most programming languages use call-by-value, rather than call-by-name. But from what I have read in the chapter, it seems that call-by-name is a much safer method of calling functions.

For example, say we have a function like f(x, y) = y * 3, and we call it somewhere like f(infinteLoop(), 6), where infinteLoop() is some function which never terminates. If we use call-by-name, we never have to call infiniteLoop() because x is never used in the body of f. But if we use call-by-value, we need to evaluate infinteLoop(), even though it will never be used in the body of f. This will cause the program not to terminate, of course.

It seems to me that call-by-name is both safer and more efficient (since we do not need to evaluate unused expressions). So for what reason do most (or any for that matter) programming languages use call-by-value instead of call-by-name?

$\endgroup$
4
  • 1
    $\begingroup$ Try to use call-by-name to compute $f(1, 10)$ where $f(x, k) = \textbf{if } (k > 0) \textbf{ then } f(x + x, k -1) \textbf{ else } x$. If it's not convincing enough, try $f(1, 100)$. Citing the Wikipedia: "If an argument is not used in the function body, the argument is never evaluated; if it is used several times, it is re-evaluated each time it appears". The bold text is the problem. Call-by-need does have it uses (though it has some practical problems, e.g. risk of stack overflow). $\endgroup$ – Dmitry Mar 15 at 2:18
  • $\begingroup$ @Dmitry couldn't the compiler just make sure that this value is computed once and the result reused in the function? I suppose this maybe misses the point, but I think that this would be a reasonable way to overcome that issue. $\endgroup$ – Blake F. Mar 15 at 2:33
  • 1
    $\begingroup$ It can, and it's called call-by-need. $\endgroup$ – Dmitry Mar 15 at 2:34
  • 1
    $\begingroup$ About call-by-need (CbN): it's used in some languages (eg Haskell relies on it for infinite lists). It has some issues though. A natural CbN implementation is $f() = \text{if (value is not computed) then }value = compute();\ \ return\ value;$. There is an overhead and, since $compute()$ can be nested, there is a risk of stack overflow on tasks like "find the sum of the array". CbN is rarely needed: people usually pass only what they need. Cases, when CbN is needed, can be handled, see eg docs.oracle.com/javase/8/docs/api/java/util/… $\endgroup$ – Dmitry Mar 15 at 3:14
2
$\begingroup$

There's a couple of factors which come into place. There can be performance costs to call-by-name, as well as difficulty with understandability in the presence of effects.

First of all, call-by-name can use exponentially more time than call-by-value, since it may have to evaluate an expression multiple times. Imagine calling f(x) = x + x when x takes a while to compute. In true call-by-name, the entire expression for x needs to be evaluated twice inside the body of f.

So in practice, instead of call-by-name, we likely would prefer call-by-need. We can instead cache the result of evaluating x, so that we don't have to compute it multiple times. This is what the programming language Haskell does (preceded by Miranda, Lazy ML). This solves the time complexity problem (as you may have intuited above, the time complexity is no worse than call-by-value), but it can also use much more space. This is because it may need large closures in order to delay evaluation. A machine integer uses a finite amount of space, but a Haskell Int could use arbitrarily large amounts, by accumulating a closure of computation that needs to be run. In the Glasgow Haskell Compiler, the garbage collector has special rules to specifically find and eliminate certain kinds of "space leaks" where we use excessive space via closures.

Even putting the theoretical aside, there are practical difficulties for implementing a call-by-name or call-by-need language on a traditional machine. Many programmers are used to using side effects in their program, such as input and output, and having their expressions run sequentially. In a call-by-name programming language, this is no longer the case, effects could be latent anywhere within an unevaluated expression, and only take effect when that data is examined. It took many years for the discovery that mathematical monads could be used as a sequencing interface. Prior methods for controlling input/output were difficult to use.

Call-by-value languages tend to also be able to be performant much more easily than call-by-name/call-by-need. Haskell has taken extensive optimization effort to run quickly, largely by being able to carefully introduce strictness to eliminate overhead of laziness. With laziness, a value of any type could be a closure: a complex allocated object and a pointer to remote code to run. This can require more allocations and more indirection to manipulate than machine integers and simple objects.

So, while we can't answer definitively why such languages aren't more popular, we can see that there has been plenty of complexity and research necessary to tackle, and so languages which used call-by-value have long had a head start.

$\endgroup$
0
$\begingroup$

I'm reminded of that joke about playing all the right notes, but not necessarily in the right order.

Although there is often some room for rearrangement, the order in which operations appear in code, broadly correspond to the order in which they must be executed so as to produce a correct outcome.

Call-by-value is little more than a natural expression of this principle - the arguments of a call, which represent its inputs, are evaluated before the call itself.

It's difficult to grasp the basis on which any other system of evaluation is thought to be "more efficient" or "safer" by default.

Obviously it is possible to contrive situations in which it may seem to be more efficient if an argument were not immediately evaluated, but this often ignores the computational inefficiency of analysing the code and deciding whether such opportunities exist. In the example given, the two modes of evaluation actually don't produce equivalent outcomes - one locks up into an infinite loop unconditionally, the other only maybe so.

It also ignores the fact that we do not always need to simply tolerate inefficient orders of evaluation under the call-by-value regime - instead, the programmer can rework the code so that evaluation occurs explicitly in an efficient order. Any difficulties this entails, are likely to be less than the difficulty of working with a language where the order of evaluation is never consistent.

I also read Jason Carr's answer above with interest, and what it makes clear to me is that certain thinkers on the subject presuppose why programmers use 'calls', and presuppose that calls can or should be used only in the fashion of 'pure functions' which transform arguments into return values, with no 'side effects'.

Unfortunately, from the point of view of most programmers, the idea that manipulating global or shared state within a call is a "side effect", is as curious as the idea that drunkenness is a "side effect" of drinking beer. In fact, transformation of shared state is the primary purpose of most programs.

Calls are not only used for transforming arguments into return values, but also for orchestrating access to "shared state" that exists external to the current scope (and perhaps external to the current program or even machine).

Where shared state does exist, the programmer must be able to reason about when shared state is being read or rewritten, so as to coordinate that access correctly.

The full information about what shared state is involved, and terms on which such coordinated access to it is being done, is not normally available in the code itself, so the computer must simply do as the programmer says, in the order he says.

And that's why we come back around to call-by-value, because as I said above, it is simply a natural extension of the principle that the order of operations is important to the correctness of the program, and there appears to be no other sensible approach than to evaluate the arguments, before evaluating the calls which employ those arguments.

$\endgroup$
0
$\begingroup$

Call-by-name was used in Algol 60, and it was let’s say “interesting”. Nowadays in the Swift language you can have “autoclosure” parameters: instead of evaluating an expression and passing the result, the actual expression itself is passed. It is evaluated every time the function that is called accesses the parameter. This allows for example implementing the && and || operators as ordinary functions.

$\endgroup$
2
  • $\begingroup$ This just sounds like Apple inventing their own name for lazy evaluation... $\endgroup$ – jmite Apr 24 at 15:54
  • $\begingroup$ When you have closures as parameters, it would be utterly stupid to call a feature that turns an expression automatically into a closure “lazy evaluation” instead of “auto closure”. Plus it’s not lazy evaluation. Plus it’s not a new language feature, it’s a tiny bit of syntactic sugar. $\endgroup$ – gnasher729 Apr 25 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.