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:

(2 * pi) * radius
(2 * 3.14159) * radius  
6.28318 * radius
6.28318 * 10

---

Definition can have parameters:

def square(x: Double) = x * x

---

Parameter and Return Types:

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:

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:

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:

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:

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

Let’s define

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.

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:

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

Let’s trace the evaluations of

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

---

Conditional Expressions

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

Example:

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:

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

Value Definitions and Termination

A definition

def x = loop

is OK, but a definition

val x = loop

will lead to an infinite loop.

---

Exercise

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

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

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

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

and(false loop)

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

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

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

---

Example – square roots with Newton’s method

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

Implementation in Scala

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

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.

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:

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

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:

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

someLongExpression
+ someOtherExpression

would be interpreted as two expressions:

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 (…) :

(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:

someLongExpression +
someOtherExpression

---