Notes of Scala course on Coursera -- Week 2 (1)

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



1. Recursion and Tail Recursion

1.1 Examples of Recursion

/* Euclid's Algorithm */ 
def gcd(a: Int, b: Int): Int = 
  if (b == 0) a else gcd(b, a % b)

gcd(14, 21) is evaluated as follows:

gcd(14, 21)
--> if (21 == 0) 14 else gcd(21, 14 % 21)
--> if (false) 14 else gcd(21, 14 % 21)
--> gcd(21, 14 % 21)
--> gcd(21, 14)
--> if (14 == 0) 21 else gcd(14, 21 % 14)
-->> gcd(14, 7)
-->> gcd(7, 0)
--> if (0 == 0) 7 else gcd(0, 7 % 0)
--> 7

Another example:

def factorial(n: Int): Int = 
  if (n == 0) 1 else n * factorial(n - 1)

factorial(4) is evaluated as follows:

factorial(4)
--> if (4 == 0) 1 else 4 * factorial(4 - 1)
-->> 4 * factorial(3)
-->> 4 * (3 * factorial(2))
-->> 4 * (3 * (2 * factorial(1)))
-->> 4 * (3 * (2 * (1 * factorial(0)))) 
-->> 4 * (3 * (2 * (1 * 1)))


1.2 Tail Recursion

Implementation Consideration:

If a function calls itself as its last action, the function’s stack frame can be reused. This is called tail recursion.

Tail recursive functions are iterative processes.

In general, if the last action of a function consists of calling a function (which may be the same), one stack frame would be sufficient for both functions. Such calls are called tail-calls.

More

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:

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

More

Start Learning Scala

还记得大三时候室友打印了一本厚厚的SICP来读,当时我还不以为意。不过读了Paul Graham《黑客与画家》后我也想亲自尝试一下,领略下Functional Programming(函数式编程)的威力。

于是选了Coursera上的函数式编程课程Functional Programming Principles in Scala,老师是欧洲名校EPFL(洛桑联邦理工学院)的教授,Scala语言的发明人Martin Odersky。目前我刚刚完成前两周的课程,这里从第一周的第一个Lecture里摘选一点内容,简单介绍一下函数式编程。


---

在说“函数式”之前,先要知道它是一种编程范式(Programming paradigm)

Wikipedia上指出:

编程范式是一类典型的编程风格,是指从事软件工程的一类典型的风格(可以对照方法学)。
编程范式提供了(同时决定了)程序员对程序执行的看法。

常见的编程范式有:

  • imperative programming(命令式编程)
  • functional programming(函数式编程)
  • logic programming(逻辑式编程)
  • object-oriented programming(面向对象编程)

More