Scala Tutorials Part #22 - Substitution model of evaluation

Substitution model of evaluation

This is part 22 of the Scala tutorial series. Check here for the full series.

In part 19 we saw how lambda calculus was the motivation behind functional programming and many concepts were adapted from it. In this part we are going to see what strategy Scala uses to evaluate expressions and functions which also came
from lambda calculus.

Index

• Introduction
• Expression evaluation
• Function evaluation
• Conclusion

Introduction

Program expressions are evaluated in the same way we would evaluate a mathematical expression. It goes roughly like below,

• Consider operator precedence
• Evaluation starts from left to right.
• Apply the operators to the operands based on precedence.

This is slightly different from regular languages such as Java where only a general language rule is applied and it is not a functional language.

Expression evaluation

Let’s take a very simple expression.

` (210)+(94) `

If you trace the execution flow, it will probably be something like below.

-> 20+(9*4)

-> 20+36

-> 56

The () braces come first, and hence the + is not calculated till 9*4 is evaluated and then finally add up with 20 and the result is 56. Let’s do one more which is slightly complicated with variables.

val x = 20

val y = 30

(10*8) / x+y

-> 80/x+y

-> 80/20+y

-> 4+y

-> 4+30

-> 34

Function evaluation

In part 3, we saw how function evaluation takes place, so I will not be going over it again. But there is one quirky detail that I will be explaining below. (Example adapted from Functional Programming Principles in Scala — Coursera)

Let’s consider a method that calls itself recursively.

 def loop:Int = loop 

Another method which just returns one of the arguments passed in.

def test(x: Int, y: Int) = x

Under normal evaluation calling the loop method will lead to infinite loop. But what will happen if we call the test method?

Since Scala uses call-by-value as default, it would lead to infinite loop even though the second argument does not play any role in it. test(1,loop) will keep on running. We can fix this by making the test method’s second parameter as call by name.

def test(x: Int, y : => Int) = x

We already saw how functions can be passed in as parameters. This is nothing but a function which expects another function i.e y as a parameter. These are called Higher Order Functions which we will see later.

Now when we call test(1,loop), it evaluates to 1 since it resorts to lazy evaluation behind the scenes and does not evaluate the loop function.

Conclusion

This evaluation strategy is buried deep under the depths of the Scala compiler. There is a lot more to it than what is mentioned in this article. But let’s summarize.

• Scala’s evaluation strategy is modeled from lambda calculus
• Expressions are evaluated from left to right and follow operator precedence
• Functions are evaluated using Call by Value, but can also be changed to use Call by Name depending on where it is necessary

This knowledge is immensely useful if you are designing libraries in Scala. In a general day to day programming, it is good to know but not really necessary to worry about it too much.