Tip:
Highlight text to annotate it
X
So in this week, we are going to do some Scala programming.
We're going to take the first steps into this new programming language and into
functional programming in general. A lot of the material in this session will
look very easy to you because it's familiar.
But there are also some things that are fundamental, in particular, the former
model of evaluation that we call the substitution model, which will be very
important for the sessions later on. So, it's good to pay a little attention.
Okay, let's get into it. Every non-trivial language provides
primitive expressions that represents the simplest elements of the language.
And then some ways to combine expressions and ways to abstract expressions.
Abstraction means that we introduce a name for an expression and then further on we
can reference the expression by its name. One way to approach functional programming
is to see it a little bit like a calculator.
In fact most functional languages have an interactive shell.
That's also sometimes called a REPL, which stands for read, eval, print, loop, and in
that shell you can type expressions, and it will respond with the results of
evaluating these expressions. In Scala you can start the REPL simply by
typing Scala. So if you write Scala here, Then you get
the ripple, that assumes that you have a standard Scalar distribution.
That's actually not a requirement for this course.
For the course, we ask you to install SVT, the Scala build tool instead.
From the SVT, you can also get the ripple simply by typing SVT consol.
It's the same REPL, so it doesn't matter whether you start that with Scala and SVT
consol. Once you're on the REPL, you can type an
expression like 42. You can also define values.
Such as radius = ten. Enter REPL, in each case, respond.
If you have an expression, with the expression's type, in this case that is
INT, and the expression's value. If you do have a definition like radius,
it would just give you the type of the definition.
You can also define floating point numbers.
And afterwards you can refer To what you have defined before.
Now, let's have a look at evaluation. You have seen how that these expressions
were evaluated. How exactly did that happen?
Well. The rules are well known from simple
algebra. To evaluate a non-primitive expression, we
typically take the left most operator, subject to the rules of precedence.
We evaluate the operands of that operator. Typically left before right.
And we apply the operator to the operands. What about evaluating a name?
Well, that's evaluated by replacing it with the right hand side of its
definition. We applied these steps one by one, until
finally, the evaluation process results in a value.
And for the moment the value is just a number, later on, we also consider other
kinds of values. So let's see an example, here's the
evaluation of the arithmetic expression, two times pi times radius.
What's happening there, first thing we do is we look up the name pi and we get its
definition, 3.14159. Then we perform the arithmetic operation
on the left. Then we look up the radius evaluate radius
yielding ten, and finally, we perform the final multiplication, yielding the result.
Definitions can also have parameters. For instance, we can define a square
function by writing def square. Then comes the parameter x of type double,
and then comes the right hand side, x times x.
The right hand side refers to the parameter x.
And the p evaluation then would yield the expected square of two, would give four, a
square of five times four would give 81, We can, of course, also have,
parameterized definitions that refer to parameterized functions as in the sum of
squares function here, that takes two parameters, x and y of type double, and it
computes the square x and square y and sums them.
We've seen in the last slide that function parameters come with a type, and this type
is given after the parameter name and a colon in Scala.
So you would write x colon double y colon int.
You can also give the return type of a function that follows after the parameter
list. The permative types are written as in
Java, but they are capitalized. So, int for example, is a 32-bit integer,
double is a 64-bit, 40-point number, and Boolean represents a Boolean type bit
value true and false. Now, how are function applications
evaluated? In fact, they are evaluated in a way that
is very similar to operators. We first evaluate all function arguments
going from left to right. We then replace the function application
by the function's right hand side, and at the same time, we replace the former
parameters of the function by the actual arguments.
Let's see how this works in an example. We start with sum of squares of three and
two + two. The two + two gets rewritten to a value,
four, and we and, we have sum of squares three, four.
Then we take the definition of sum of squares, that was square of x plus square
of y, and we replace the application by this right hand side, where at the same
time we replace the parameters x and y by the actual arguments three and four.
We then repeat the process with the square applications.
The square of three becomes three times three.
The right turn side of square where three replaces the promidence.
We get an arithmetic simplification, and we do the same thing for the right hand
operators yielding the final value 25. This scheme of expression evaluation is
called the substitution model. The idea underlying this model is that all
evaluation does is reduce an expression to a value.
And that reduction can be expressed by a sequence of simple rewriting steps that
rewrite the expression term itself until it is a value, very similar to what you
would do in algebraic simplification. Simple as it is, this model is very
powerful. In fact it has been shown that it can
express every algorithm, so it's equivalent to what you would call a Turing
machine. This has been shown a long time before
functional programming, in fact, a long time before computers by a logician called
Alonzo Church in the lambda calculus. He did that in the thirties of the last
century. You might have come across lambda calculus
in theoretical computer science, and if you did, then you know how to make the
connection to this model. If you didn't, don't worry.
We won't need the theory for following the course.
What's important though is to know that number calculus as a model, and the
substitution model, can be applied only to expressions that do not have a side
effect. Now, what is a side effect?
A typical side effect would be an expression called.
C++ where c is a variable. And evaluating this expression means that
you return the old value of c, and at the same time you increment the value.
So, at the next time you return the value, you would return the value one larger than
before. Turns out there's no good way to represent
this evaluation sequence by a simple rewriting of this term.
You need something else, like store, where the current value of the variable is kept.
In other words the expression C++ has a side effect on the current value of the
variable. And that side effect cannot be expressed
by the substitution model. So one of the motivations for ruling out
side effects in function programming is that we can keep to the simple model of
evaluation. Once we have the substitution model,
another question comes up. Does every expression reduce to a value in
a finite number of steps? In fact, the answer is no.
Here's a counter example. Let's write simple function def loop int
equals loop. And that's then called, referred to the
name loop. What would happen.
Well, according to our model we have to de evaluate that name which happens by
replacing the name by its right hand side. The right hand side is looped again.
So we have reduced the name to itself and this can go on ad infinitum.
Another way to visualize this reduction sequence is by starting with the loop and
then reducing to the same term again. We've seen that the Scala interpreter
reduces function arguments to values before rewriting the function application.
That's not the only possible reduction strategy.
Alternatively, one could apply the function to unreduced arguments.
For instance, we could start with some of squares three, two plus two, and then go
on as follows. We keep the right hand side.
We don't reduce it to four and we simply pass it as an expression to the square
function. We then simplify the right hand side as
before. And then do the same thing again, pass the
expression, two plus two to this occurrence of square, that gives two plus
two twice in the multiplication. We then simplify the two further steps to
arrive at the final result, 25. Now you've seen two ways to evaluate the
same expression. The first evaluation strategy is known by
core by value. The second is known as core by name.
An important theorem, in fact, of lambda calculus is that both strategies reduce to
the same final value as long as the reduced expression consists of pure
functions and both evaluations terminate. Call-by-value has the advantage that every
function argument is evaluated only once. Call-by-name has the advantage that a
function argument is not evaluated at all if the corresponding parameter is not used
in the evaluation of the function's body. Here's a question, say you're given the
following function definition: Def test of x and y equals x times x.
For each of the following function applications, indicate which evaluation
strategy is fastest, by which we mean, has the fewest reduction steps.
That's for test of two three then test of three plus four eight.
Test seven two times four, then finally, test three plus four, two times four.
Let's see how we would answer this question.
I have the test function here and I have the calls that I want to compare here.
Let's start with the first one, test two, three.
How would that evaluate? Well, test two three, we take the
definition of test, x times x. So, that would give two times two and that
would reduce to four. And in fact that would reduce to four on
their both evaluation strategies, both core by name and core by value because we
have started with already evaluated arguments so there's no choice in the
matter. So here the answer would be, they are,
they have the same complexity. Let's do the next one.
Test three plus four eight. And I call by value, we have to evaluate
the arguments. So we get test.
7,8. And that gives us seven times seven.
And the final result. Where it's under called by name we get
three plus four times three plus four. That reduces to seven times three plus
four. Seven times seven and 49.
In one step more than in the core by value version.
So core by value, has the advantage here. Let's look at the third example.
Test. Of seven and two times four.
Here with call by value, we would get test of seven and eight.
Finally, seven, seven. And the final, whereas with call by name,
we would get seven. Times 749.
So in this case, we have avoided the unnecessary computation for the second
argument and the call by name is faster. The fourth example, test three plus four
two, two times four combines the evaluation of the second and third
example. So it comes at no surprise that it's again
a draw, that core by value and core by name, reduces the same number of steps