Notes of Scala course on Coursera -- Week 1

Here are my notes for the week 1’s lecture of Functional Programming Principles in Scala on Coursera.

Evaluation of Programming

Every non-trivial programming language provides:

  • primitive expressions representing the simplest elements
  • ways to combine expressions
  • ways to abstract expressions, which introduces a name for an expression by which it can be referred to

A non-primitive expression is evaluated as follows:

  1. Take the leftmost operator
  2. Evaluate its operands (left before right)
  3. Apply the operator to the operands

A name is evaluated by replacing it with the right hand side of its definition.

Example:

1
2
3
4
(2 * pi) * radius
(2 * 3.14159) * radius
6.28318 * radius
6.28318 * 10

Definition can have parameters:

1
def square(x: Double) = x * x

Parameter and Return Types:

1
def power(x: Double, y: Int): Double = ...

Evaluation of Function Applications

  1. Evaluate all function arguments, from left to right.
  2. Replace the function application by the function’s right-hand side, and, at the same time,
  3. Replace the formal parameters of the function by the actual arguments.

Example:

1
2
3
4
5
6
7
8
sumOfSquares(3, 2+2)
sumOfSquares(3, 4)
square(3) + square(4)
3 * 3 + square(4)
9 + square(4)
9 + 4 * 4
9 + 16
25

The substitution model

The scheme of expression evaluation is called the substitution model.

The idea is that all evaluation dose is reduce an expression to a value.

It can be applied to all expressions, as long as they have no side effects.

The substitution model is formalized in the λ-calculus, which gives a
foundation for functional programming.




Call By Value v.s. Call By Name

Both strategies reduce to the same final values as long as

  • the reduced expression consists of pure functions, and
  • both evaluations terminate.

Call-by-value has the advantage that it evaluates every function
argument only once
.

Call-by-name has the advantage that a function argument is not
evaluated if the corresponding parameter is unused in the evaluation
of the function body
.

An Example of CBV:

1
2
3
4
5
6
7
8
sumOfSquares(3, 2+2)
sumOfSquares(3, 4)
square(3) + square(4)
3 * 3 + square(4)
9 + square(4)
9 + 4 * 4
9 + 16
25

An Example of CBN:

1
2
3
4
5
6
7
8
sumOfSquares(3, 2+2)
square(3) + square(2+2)
3 * 3 + square(2+2)
9 + square(2+2)
9 + (2+2) * (2+2)
9 + 4 * (2+2)
9 + 4 * 4
25

CBV vs CBN:

Call By Value v.s. Call By Name

  • If CBV evaluation of an expression e terminates, then CBN evaluation of e terminates, too.
  • The other direction is not true.

Let’s define

1
2
def first(x: Int, y: Int) = x
def loop: Int = loop

and consider the expression first(1, loop).

Under CBN, it will terminate.

Under CBV, it won’t.

CBN v.s. CBV

Scala normally uses call-by-value.

  • Because it avoids this repeated recomputation of argument expressions that call by name entails
  • It plays much nicer with, imperative effects and side effects because you tend to know much better when expressions will be evaluated

But if the type of a function parameter starts with => it uses call-by-name.

Example:

1
def constOne(x: Int, y: => Int) = 1

Let’s trace the evaluations of

1
2
constOne(1+2, loop)
constOne(loop, 1+2)

CBN

CBV





Conditional Expressions

It looks like a if-else in Java, but is used for expressions, not statements.

Example:

1
def abs(x: Int) = if (x >= 0) x else -x





Value Definitions

def: “by-name”, its right hand side is evaluated on each
use.

var: “by-value”, Example:

1
2
val x = 2
val y = square(x) // y refers to 4 , not square(2)

Value Definitions and Termination

A definition

1
def x = loop

is OK, but a definition

1
val x = loop

will lead to an infinite loop.



Exercise

Write functions and and or such that for all argument expressions x
and y :

1
2
and(x, y) == x && y
or(x, y) == x || y

(do not use || and && in your implementation)

1
2
3
4
5
def and(x: Boolean, y: Boolean) =
if (x) y else false
def or(x: Boolean, y: Boolean) =
if (x) true else y

It seems OK, but what if

1
and(false loop)

OOPS! What’ wrong? y: Boolean is a call-by-value form, let’s change it to call-by-name form:

1
def and(x: Boolean, y: => Boolean)

Try and(false loop) again, it’s OK!





Example – square roots with Newton’s method

1
2
/** Calculates the square root of parameter x */
def sqrt(x: Double): Double = ...

Square roots with Newton’s method

Implementation in Scala

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def sqrt(x: Double): Double = {
def sqrtIter(guess: Double, x: Double): Double =
if (isGoodEnough(guess, x)) guess
else sqrtIter(improve(guess, x), x)
def improve(guess: Double, x: Double) =
(guess + x / guess) / 2
def isGoodEnough(guess: Double, x: Double) =
abs(guess * guess - x) / x < 0.0001
def abs(x: Double) = if (x < 0) -x else x
sqrtIter(1)
}





Blocks and Lexical Scope

Nested functions

It’s good functional programming style to split up a task into many small functions.

But the names of functions like sqrtIter, improve, and isGoodEnough matter only for the implementation of sqrt , not for its usage.

Normally we would not like users to access these functions directly.

We can achieve this and at the same time avoid “name-space
pollution”
by putting the auxciliary functions inside sqrt.

Blocks in Scala

  • A block is delimited by braces { … }
  • It contains a sequence of definitions or expressions.
  • The last element of a block is an expression that defines its value.
  • This return expression can be preceded by auxiliary definitions.
  • Blocks are themselves expressions; a block may appear everywhere an expression can.

Blocks and Visibility

1
2
3
4
5
6
val x = 0
def f(y: Int) = y + 1
val result = {
val x = f(3)
x * x
}
  • The definitions inside a block are only visible from within the block.
  • The definitions inside a block shadow definitions of the same names outside the block.

Scope Rules

Lexical Scoping

Definitions of outer blocks are visible inside a block unless they are
shadowed.

Therefore, we can simplify sqrt by eliminating redundant
occurrences of the x parameter
, which means everywhere the same
thing:

1
2
3
4
5
6
7
8
9
10
def sqrt(x: Double) = {
def sqrtIter(guess: Double): Double =
if (isGoodEnough(guess)) guess
else sqrtIter(improve(guess))
def improve(guess: Double) =
(guess + x / guess) / 2
def isGoodEnough(guess: Double) =
abs(square(guess) - x) < 0.001
sqrtIter(1.0)
}

Semicolons

In Scala, semicolons at the end of lines are in most cases optional.
You could write

1
val x = 1;

but most people would omit the semicolon.
On the other hand, if there are more than one statements on a line,
they need to be separated by semicolons:

1
val y = x + 1; y * y

Semicolons and infix operators

One issue with Scala’s semicolon convention is how to write
expressions that span several lines. For instance

1
2
someLongExpression
+ someOtherExpression

would be interpreted as two expressions:

1
2
someLongExpression;
+ someOtherExpression

There are two ways to overcome this problem.
You could write the multi-line expression in parentheses, because
semicolons are never inserted inside (…) :

1
2
(someLongExpression
+ someOtherExpression)

Or you could write the operator on the first line, because this tells
the Scala compiler that the expression is not yet finished:

1
2
someLongExpression +
someOtherExpression