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

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

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.

(2*10)+(9*4)

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.

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.


Tagged Under


Scala


Search this website...




Keeping up with blogs...

I blog occasionally and mostly write about Software engineering and the likes. If you are interested in keeping up with new blog posts, you should follow me on twitter where I usually tweet when I publish them. You can also use the RSS feed , or even subscribe via email below.

Feedio Subscribe


Share & Like

If you like this post, then you can either share/discuss/vote up on the below sites.



Thoughts ...

Please feel free to share your comments below for discussion

Blog comments powered by Disqus