Evaluation Order

For an expression to yield its value, it must be evaluated. When we are first learning to program, this seems to happen magically. We run the code, and poof! there's our value. Code long enough, though, and we will start to encounter situations where we need to have a mental model of how and when evaluation occurs.

Order of Evaluation

Consider the expression a + b - c / d. What part of this expression will be evaluated first? The c / d, right? That's the operator that has the highest precedence, so that seems like a fair assumption. Before you put any money down, let's do an experiment. Examine this Ruby script, which monkey patches the operators +, -, and / so that they log their operation as they are evaluated, and predict the output before reading further:

class Integer
  def +(that)
    puts '+'
    self
  end

  def -(that)
    puts '-'
    self
  end

  def /(that)
    puts '/'
    self
  end
end

5 + 6 - 7 / 8

The output might surprise you:

+
/
-

The division operation is not evaluated first. It does happen before the subtraction at least. But this behavior is strange. Shouldn't division happen first? Isn't that what precedence means? No, actually. The precedence and associativity of the operators shape the parse tree as we expect:

But once the parse tree is formed, the precedence and associativity no longer matter. The interpreter or runtime may evaluate this tree in a couple of different ways: a + b may be evaluated first, or c / d. The exact order depends on the language. The C and C++ standards leave the evaluation order up to the compiler writer. Ruby, Python, and Java guarantee left-to-right evaluation order.

Function calls present a similar situation. The call f(a(), b(), c()) has three actual parameters to compute. C and C++ do not guarantee the order in which a, b, and c are called. Ruby, Python, and Java call them in left-to-right order.

The evaluation order doesn't always matter, as in the arithmetic expression above. But sometimes it does. Consider this Java statement that contains two assignments to i:

numbers[i++] = i++;

If a language doesn't pin down the order of evaluation, we may encounter two different results from a statement like this.

Avoiding Evaluation

Not only may the evaluation order be surprising, but some operators don't evaluate all of their operands. You have likely seen the short-circuiting behavior of the binary logical operators.

The conditional expression also must be careful not to evaluate all of its operands. After evaluating its condition, it must evaluate only one of its then and else expressions. This Ruby script illustrates its conservative behavior:

def get_then()
  print 'then'
end

def get_else()
  print 'else'
end

5 > 6 ? then_value : else_value          # prints "else"

Sometimes programmers may be tempted to write their own if function, like this one, which adds an element of chance to the condition being true:

def if_maybe(condition, then_expression, else_expression)
  if condition && rand > 0.5
    then_expression
  else
    else_expression
  end
end

if_maybe(5 > 6, get_then(), get_else())  # prints "thenelse"

However, unless the language has pass-by-name parameters, this code triggers both side-effects, which is likely not the programmer's intent. Many languages, including Ruby, evaluate actual parameters before the function is called. In this case, then_value and else_value are both called. This may not be safe since the condition for the then expression hasn't been met. This is also wasteful since only one of the two expressions will be referenced inside if_maybe.

Languages that evaluate their parameters eagerly, before the function takes over, are called strict languages. C, C++, Ruby, Python, and JavaScript are all strict languages. We cannot write our own if-like function in a strict language. Conditional and short-circuiting operators must be special forms recognized by the language as having non-eager evaluation. Haskell is non-strict. We could write an if function in Haskell.

Lazy Evaluation

Imagine you are in a band, and there's a songwriting contest that you'd like to enter. This contest could take a couple different forms. You could record the song ahead of time and submit it. On the day of the contest, the judges play your recording. Or the contest could be a Battle of the Bands event in which you perform your song live. Each form has its advantages. If you record the song, then you've done all the work up front, and the competition will flow smoothly from recording to recording. But suppose the event gets canceled the day before. You'll have spent a lot of time recording—only to have your song never played. On the other hand, if the live event gets canceled, you won't have lost any time getting that perfect recording.

Eager evaluation is like recording your song ahead of time. Evaluating operands and parameters before they are needed will make for quick access when they are referenced, but the work of evaluating them is wasted if their values aren't needed. Waiting to perform an evaluation until just when it's needed is lazy evaluation. Consider this Ruby class that uses lazy evaluation to delay reading in an image from disk until it's absolutely needed:

class LazyImage
  def initialize(path)
    @path = path
    @cache = nil
  end

  def pixels
    if @cache.nil?
      @cache = File.read(@path)
    end
    @cache
  end
end

image = LazyImage.new('map-2000000x1000000.png')
# images.pixels   <- only this is expensive

This code executes instantly despite the very large size of the image. That's because the image is never actually read. No one calls the pixels method. As soon as someone does, the image data is read and cached. Any subsequent calls to pixels will not read the file in again; the cached pixels will be returned immediately.

The lazy evaluation found in the LazyImage class is homemade. Ruby doesn't provide a mechanism creating a lazily evaluated expression. However, Haskell does. Most of its expressions aren't truly evaluated until their values are output to the user. You can't really tell this is the case because Haskell has hidden its laziness quite well. There's no special syntax to delay or force the evaluation. It is automatic.

There is one situation where the laziness is apparent: infinite lists. Consider this Haskell expression:

[1..]          -- yields the list 1, 2, 3, 4, 5, ...

This list has no end. If you enter it into ghci, it will go on for ever showing integer after integer. However, this expression, which operates on the same infinite list, executes and finishes just fine:

take 4 [1..]   -- yields the list [1, 2, 3, 4]

The infinite list is evaluated only as needed. The take function only needs the first four values, so there's no infinite loop like you'd see with eager evaluation of function parameters. Each node in the list holds its number and a function that produces the rest of the list on demand.

Summary

Functional languages exhibit two features not found in imperative languages: programs are made by calling functions that produce values rather than statements that produce side effects, and data is immutable. Values are produced by expressions, which may be literal data, variable references, calls to other functions, or operators combining subexpressions. Haskell is a prime example of a functional language, and it accordingly offers considerable power for composing expressions. New operators may be defined with arbitrary precedence and associativity. Functions may be treated as operators and operators may be treated as functions. When we must choose amongst values, we may employ an if expression, a case expression, or guards. The Haskell compiler ensures that operations and function calls are well-formed through a static type system. Static types often give programmers more upfront labor, but Haskell's type system offers some relief. Omitted types are inferred by the compiler, and functions with type wildcards in their signature serve many types. Typeclasses impose a set of operations on a group of types and allow polymorphic functions to serve a particular interface.