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:

- Take the leftmost operator
- Evaluate its operands (left before right)
- 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

- Evaluate all function arguments, from left to right.
- Replace the function application by the function’s right-hand side, and, at the same time,
- 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 functionargument only once**.

Call-by-name has the advantage that **a function argument is notevaluated if the corresponding parameter is unused in the evaluationof 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-spacepollution”** 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 redundantoccurrences 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
```