Functions and Evaluation Strategies. JavaScript Examples.

Functions and evaluation Strategies

The fact that modern programming languages allow the combination of simple expressions into complex ones is taken for granted. Similarly, unless we're complete beginner programmers, the concept of a function declaration—a method of creating an abstraction where a complex operation gets a name and can be operated on—is something we intuitively understand.

But is the evaluation of functions really that trivial? Like most things in the theory of programming languages, we quickly discover it's not, once we delve into it.

Strict evaluation

Evaluation strategy is a set of rules defining when and in what order the values of expressions that are part of a larger whole (in this case, a function) should be computed.

Let's analyze the order of operations for the applicative order of computation. In this model, for a function call in the form of name(arguments), the first step is always to compute the values of the argument expressions and retrieve the function's value. Only then we do apply the function, substituting the parameters with the argument values.

Consider the following snippet in JavaScript (which, like most programming languages, uses applicative order):

function square(x) {
  return x * x;
}
function calculateDelta(b, a, c) {
  return square(b) - 4 * a * c;
}
function numberOfSolutions(delta) {
  return delta === 0 ? 1 : delta < 0 ? 0 : 2;
}
numberOfSolutions(calculateDelta(6, 1, 5));

To obtain the value of the expression numberOfSolutions(calculateDelta(6,1,5)); using the applicative method, we need to perform the following steps:

  1. Call numberOfSolutions(calculateDelta(6,1,5));.
  2. Evaluate calculateDelta(6,1,5);.
  3. Find the value returned by the expression square(6) - 4 * 1 * 5;.
  4. Evaluate square(6).
  5. Find the value returned by the expression 6 * 6; (36).
  6. Find the value returned by the expression 36 - 4 * 1 * 5. (16) This gives us the argument value for the call numberOfSolutions.
  7. Find the value returned by the expression 16 === 0 ? 1 : 16 < 0 ? 0 : 2;.
  8. The result is 2.

The call stack is used to evaluate functions in the applicative model. To visualize the order of function calls more easily, use the tool: JS Visualizer

In this case, the evaluation strategy is called strict because the value of the argument always has to be obtained before the function is executed. The applicative strategy refers to the evaluation order where argument values are found from left to right. The applicative strategy is strict, but not all strict strategies are applicative. We can also say that the above strategy is greedy because the function call is executed immediately upon encountering it in the expression.

Non-strict evaluation order

The above example is not the only way to execute these calculations. As an alternative, we can perform a series of expansions, substituting appropriate expressions for variables until we obtain an expression consisting solely of operators and primitive functions. This sequence of actions is called normal order evaluation. Let's examine it more closely.

How would we compute the value of our function call numberOfSolutions(calculateDelta(6, 1, 5)); this way?

  1. Call numberOfSolutions(calculateDelta(6, 1, 5));
  2. Substitute the parameter for numberOfSolutions: calculateDelta(6, 1, 5) === 0 ? 1 : calculateDelta(6, 1, 5) < 0 ? 0 : 2
  3. Substitute the argument in the body of calculateDelta: square(6) - 4 * 1 * 5; => square(6) - 4 * 1 * 5 === 0 ? 1 : square(6) - 4 * 1 * 5 < 0 ? 0 : 2
  4. Substitute square(6) with the function body: 6 * 6 => 6 * 6 - 4 * 1 * 5 === 0 ? 1 : 6 * 6 - 4 * 1 * 5 < 0 ? 0 : 2
  5. Finally, we can proceed with calculating the result according to the rules of order of operations: 16 === 0 ? 1 : 16 < 0 ? 0 : 2
  6. The result is 2

We receive the same answer, albeit achieved differently. If we could summarize this process in one sentence, it would be: Expand everything and compute. For the applicative order, the summary might be: Compute arguments and call the function.

Comparison of strict and non-strict evaluation

There are several significant differences resulting from the choice of evaluation order. Among others, there's performance differences between the two ways. In the applicative model, we first compute the argument value to substitute it for the parameter, while in the normal model, we substitute the parameter with the argument expression. If we use the argument more than once, it will lead to the situation where the normal order is less efficient due to duplicated computations. In our example, we can see this in the body of the function numberOfSolutions. While in the first variant we substitute the previously computed value 16 into the expression, in the second case, we compute it twice (6 * 6 - 4 * 1 * 5 === 0 ? 1 : 6 * 6 - 4 * 1 * 5 < 0 ? 0 : 2). In practice, with non-strict evaluation orders (that normal order is an example of), methods that eliminate this problem are used, such as lazy evaluation, where each expression is computed only when its value is needed, but no more than once.

On the other hand, there are situations where computing the value of all the arguments will not be necessary. In such a scenario, strict strategies will lose in terms of performance. However, this has implications far beyond just performance! Consider the following function:

function test(condition, passMessage, failMessage) {
  return condition ? passMessage : failMessage;
}

Let's call it with the following arguments:

test(5 > 0, 'number is positive', undefined.failMessage);

JavaScript, using applicative order evaluation, will fail to execute the above call. We get the error Uncaught TypeError: Cannot read properties of undefined (reading 'failMessage'). This happens because we immediately evaluate the value of the expression undefined.failMessage, which is not valid in JavaScript. If we applied the normal order evaluation rules and instead of computing the argument value with an error, we substituted it for the parameter and computed the entire expression at the end, this function would execute correctly, because the conditional operator would never reach the point where the value of undefined.failMessage is needed.

In the example with test(5 > 0, 'number is positive', undefined.failMessage);, we saw how the test function could execute in normal order, even with an invalid third argument value. Just as we didn't trigger an error by attempting to evaluate a faulty expression, similarly, we wouldn't fall into an infinite loop trying to execute non-terminating code. This property of non-strict evaluation allows for defining certain algorithms in a much more natural way.

Consider the following code describing a function returning the factorial of a given number:

function unless(condition, usualValue, exceptionalValue) {
  return condition ? exceptionalValue : usualValue;
}
function factorial(n) {
  return unless(n === 1, n * factorial(n - 1), 1);
}
factorial(5);

Trying to execute the above code, we would fall into an infinite loop, or at least, when executing our code in a context like a browser, we would get an error: RangeError: Maximum call stack size exceeded. If we used normal order evaluation, there would be no problem. The arguments to the unless function would not be evaluated before calling it, and for the value n === 1, the second argument n * factorial(n - 1) would not be computed at all, and the function would return 1.

Unfortunately, JavaScript uses applicative order here, so let's modify our function to make it executable.

function factorial(n) {
  if (n == 1)
    return 1;
  else {
    return (n * factorial(n - 1));
  }
}
factorial(5);

Although the vast majority of languages use strict evaluation methods, there are a few interesting applications of non-strict evaluation methods. They allow us, among other things, to create infinite data structures. Interestingly, although we might associate such methods with functional programming languages like Haskell, JavaScript also gives us this possibility! Thanks to new functionalities in the ES6 standard, such as generators, we can also define infinite collections in JavaScript.

Below, we'll create an infinite collection using a generator:

var naturalNumbers = function* () {
  let i = 0;
  while (true) {
    yield i++;
  }
}

for (let i of naturalNumbers()) {
  if (i > 10) break;
  console.log(i);
}

Such a data structure can be very useful when we don't know in advance how many elements we will need. Imagine we want to find 100 prime numbers using a library similar to RxJs, without the ability to create an infinite collection:

const primeNumbers = naturalNumbers
.filter(isPrime)
.first(100)

Assuming that naturalNumbers stands for a sequence of consecutive natural numbers, 1, 2, 3, 4..., what should its length be? 10,000? It's certainly hard to judge at first glance. The ability to use a data structure like naturalNumbers generator gives us a tremendous advantage here. We can do this precisely because generators in JavaScript are based on lazy evaluation. Subsequent elements of naturalNumbers are generated on demand, according to the definition we provided to the generator.

Let's consider the classic example: the Fibonacci sequence.

Suppose we want to define a function that gives the n-th term of the sequence:

function fibonacci(n) {
  if (n <= 1) {
   return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2);
}

To print the first 10 terms of the sequence:

for (let i = 0; i < 10; i++) {
  console.log(fibonacci(i));
}

Instead of using the above function, we can define a generator describing the Fibonacci sequence:

function* fibonacci() {
  let [a, b] = [0, 1];
  while (true) {
    yield a;
    [a, b] = [b, a + b];
  }
}

We instantiate the Fibonacci generator as follows:

var fib = fibonacci();

Let's print the first 10 terms of the sequence:

for (let i = 0; i < 10; i++) {
  console.log(fib.next().value);
}

Sources

This article was based on Structure and Interpretation of Computer Programs. I hope it answers some of the questions I had after reading related chapters in the book. It also attempts to describe the problem using slightly simpler language with more examples to learn from. Thanks for reading it!