# Learning Note for Functional Programming

Coursera Note

Sentence in red is my own perspective, inspired by the instructor.

#### Imperative Programs and Computers

There is strong correspondence between

Mutable variables ~ Memory cells

Variable assignments ~ store instructions

Control structures ~ jumps

Problem: how can we avoid conceptualizing programs word by word.

Reference: john Backus, Can Programming Be Liberated from the von. Neumann Style?, Turing Award Lecture 1978.

The new thing he proposed is functional programming.

#### Scaling Up

In the end, pure imperative programming is limited by the “Von Neumann” bottleneck:

One tends to conceptualize data structures word-by-word

We need other techniques for defining high-level abstractions such as collections, polynomials, geometric shapes, strings, documents.

Ideally: Develop theories of collections, shapes, strings…

• Decoupling between CPU instructions and programming language.

Consequences for programming

If we want to implement high-level concepts following their mathematical theories, there’s no place for mutation.

• The theories do not admit it
• Mutation can destroy useful laws in the theories

Therefore, let’s

• concentrate on defining theories for operators expressed as functions,
• avoid mutations,
• have powerful ways to abstract and compose functions.
• So in software analysis class, Ruzica always said that for assignment sentences, say x := x + 11,we must {assume tmp = x; havoc x; x = tmp + 1} because variables are immutable. We must alloc a new variable to simulate assignment function.

Functional Programming

• In a restricted sense a functional programming language is one which does not have mutable variables, assignments, or imperative control structures.
• In a wider sense, a functional programming language enables the construction of elegant programs that focus on functions
• In particular, functions in a FP language are first-class citizens. This means
• they can be defined anywhere, including inside other functions
• like any other value, they can be passed as parameters to functions and returned as results
• as for other values, there exists a set of operators to compose functions (How?)

Some Functional Programming Languages

In restrict sense,

• Pure Lisp,XSLT, XPath, XQuery, FP

In wider sense

• Lisp, Scheme, Racket, Clojure
• SML, Ocaml, F#
• Scala
• Smalltalk, Ruby(!)

Why Functional Programming?

• Simpler reasoning principles
• better modularity
• Good for exploiting parallelism for multicore and cloud computing.

### 1.2 Elements of Programming

Elements of Programming

Every non-trivial programming language provides:

• primitive expressions representing the simplest elements, Var(n)
• ways to combine expressions,  Sum(expression, expression)
• ways to abstract expressions, which introduce a name for an expression by which it can then be referred to, type Env = String => Int

Something like:

```expression:
expression + expression |
expression - expression |
expression * expression |
expression / expression |
var |
const |
(expression)```

Scala Example

`def sumOfSquares(a: Double, b: Double): Double = a * a + b * b`

expression evaluation is called the substitution model.

The idea underlying this model is that all evaluation does is reduce an expression to a value.

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

Termination

So here comes a question,

Does every expression reduce to a value?

No, here is an example,

`def loop: Int = loop`

Call by name and Call by value

```def test(x: Int, y: Int): Int = x * x

test(2,3) => 2 * 2 => 4

// Call by value, reduce the parameter to value, then call the function.
test(3+4, 8) => test(7,8) => 7 * 7 => 49
// Call by name, call the function immediately before evaluating the expression to value
test(3+4, 8) => (3+4) * (3+4) => 7 * (3+4) => 7 * 7 => 49```

1.3 Evaluation Strategies and Termination

Call by value(CBV) terminates => Call by name(CBN) terminates

But not vise versa.

example, CBV not terminates, but CBN terminates

```def first(x: Int, y: Int) = x
def loop: Int = loop

first(1, loop)```

Scala use call by value, since it’s more efficient. But if the type of a function parameter starts with => it uses call-by-name

```def constone(x: Int, y: => Int) = 1

constOne(1+2, loop) // terminates
constOne(loop, 1) // not terminate```
```// it is important in implementing some fundamental functions
def constone(x: Boolean, y: => Boolean) = 1

constOne(1+2, loop) // terminates
constOne(loop, 1) // not terminate```

This site uses Akismet to reduce spam. Learn how your comment data is processed.