Coursera Note

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

1.1 Programming Paradigms

Imperative Programs and Computers

There is strong correspondence between

Mutable variables ~ Memory cells

Variable dereference ~ load instructions

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
• Haskell (without I/O Monad or UnsafePerformIO)

In wider sense

• Lisp, Scheme, Racket, Clojure
• SML, Ocaml, F#
• Haskell (full language)
• 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