Scala 2

Tail Recursion

Evaluating a Function Application

One simple rule: One evaluates a function application f(e1,e2,...,en)

1. 对e1...en进行求值，得到v1...vn
2. 把等号右边的函数体展开
3. 用v1,...,vn替换函数内的参数e1,...,en

Application Rewriting Rule

This can be formalized as rewriting of the program itself

//定义一个函数f
def f(x1,...,xn) = B; ...f(v1...vn)

//调用了这个函数
f(v1,...,vn)

//将f展开
[v1/x1,...,vn/xn]B

• Here, [v1/x1,...,vn/xn] 意味着:
  • The expression B in which all occurrences of xi have been replaced by vi
  • [v1/x1,...,vn/xn] is called a substitution

Example #1

def gcd(a:Int, b:Int) : Int = 
	if (b == 0) a else gcd(b,a%b)

gcd(14,21) is evaluated as follows:

-> `if(21 == 0) 14 else gcd (21,14%21) `
-> `if(false) 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`

Example #2

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

factorial(4) is evaluated as follows:

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

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

意思是如果一个函数，在最后递归调用自己，则它的stack可以被复用。它的性能变成和使用for循环相同。

例1中，最后一个else会递归，由于它后面没有其它指令了，因此他是Tail Recursive的，例2中，else执行递归后还有一条指令是和x相乘，因此它不满足Tail Recursive

In general, if the last action of a function consists of calling a function（maybe the same, maybe some other functions）, one stack frame would be sufficient for both functions. Such calls are called tail-calls

如果一个函数的最后一条指令是调用另一个函数，那么这种调用叫tail-calls，这种情况下一个stack frame可以满足两个函数公用。

但是并不是所有的函数都需要使用尾部递归，JVM允许的递归深度为几百，如果超过这个层次就会stack overflow，因此对于递归层次很深的函数，要使用这种技巧。

针对例2，来实现一种满足Tail Recursive的方法。

object exercise {  
	def factorial(x:Int):Int = 
	{
		def loop(acc:Int, x:Int):Int = 
				
		if ( x== 0 ) acc
		else
			loop(acc*x,x-1)
			
		loop(1,x) 
	}
	factorial(4) 
}

Higher Order Function

• first-class values
• like any other value, a function can be passed as a parameter and returned as a result
• This provides a flexible way to compose programs
• Function takes other functions as parameters or that return functions as results are called HOF

def sum(f: Int=>Int, a:Int, b:Int):Int = 
	if (a>b) 0
	else f(a) + sum(f,a+1,b)

We can then write:

def sumInts(a:Int, b:Int) 		= sum(id,a,b)
def sumCubes(a:Int, b:Int) 		= sum(cube,a,b)
def sumFactorials(a:Int,b:Int) = sum(fact,a,b)

where:

def id(x:Int):Int = x
def cube(x:Int):Int = x * x * x
def fact(x:Int):Int = if(x==0) 1 else fact(x-1)

Function Types

The type A => B is the type of a function that takes an argument of type A and returns a result of type B

Anonymous Functions

上面的例子中，将函数最为参数的一个副作用是要创建许多子函数。有些时候定义这些子函数有些冗余，这时候可以使用匿名函数

(x:Int) => x * x * x

Here,(x:Int) => x * x * x是匿名函数

• 参数的类型可以省略，他可以被编译器推断

(x:Int, y:Int) => x+y

所有的匿名函数都可以用def表示:

(x1:T1,...,xn:Tn) => E
//等价于
{
	def f(x1:T1,...,xn:Tn) = E;
	f
}

因此匿名函数实际上函数的语法糖 = {} + def f

 //return a function using block
 def sum(f: Int => Int) : (Int,Int)=>Int = 
  {
		def sumF(a:Int, b:Int):Int =
		
			if(a>b) 0
			else f(a) + sumF(a+1,b)
		sumF
	
  } 

使用匿名函数

def sumInt(a:Int, b:Int) = sum(x => x, a, b)
def sumCubes(a:Int,b:Int) = sum(x=>x*x*x,a,b)

Currying

Motivation

Look again at the summation functions:

def sumInts(a:Int, b:Int) = sum(x=>x ,a,b)

• Question

Note that a and b get passed unchanged from sumInts and sumCubes into sum. Can we be even shorter by getting rid of these parameters?

Functions Returning Functions

Let’s rewrite sum as follows:

def sum(f: Int => Int) : (Int,Int)=>Int = 
{
	def sumF(a:Int, b:Int):Int = 
		
		if(a>b) 0
		else f(a) + sumF(a+1,b)
	sumF
	
}

sum is now a function that returns another function. The returned function sumF applies the given function parameter f and sums the result

def sumIncrease = sum( x=>x+1 )
val result = sumIncrease(2,4)

//也可以直接计算:
val result = sum (x => x+1 )(2,4)

Generally,function application associates to the left. 代码中，函数的运算是左结合：

sum(x=>x+1)(1,10) = (sum(x=>x+1))(1,10)

对于一个返回函数的函数来说，scala提供了一种syntax, 以上面的sum函数为例:

def sum(f:Int=>Int)(a:Int,b:Int) : Int = 
	if(a>b) 0 else f(a) + sum(f)(a+1,b)

相当于将参数直接代入进来，使sum (x => x+1 )(2,4)这种写法更直观

Expansion of Multiple Parameter Lists

In general, a definition of a function with multiple parameter lists

//带有参数列表的函数
def f(args1)...(argsn) = E

where n>1, 等价于

def f(args1)...(argsn-1) = {def g(argsn)=E; g}

理解:

• arg1,args2,…,argsn-1实际上都表示匿名函数:

  • def ((f(g)h)z) ... = {def g(x) = E; g}

  • 其中g(x)是所有这些匿名函数代入后的最终函数

whare g is a fresh identifier. Or for short:

def f(args1)...(argsn-1) = (argsn => E)

上面这个式子使用匿名函数表达：

等号左边是匿名函数的求解，等号右边是最终的函数：输入为argsn， 输出为E

也可定义为：

def f = (args1 => (args2 => ... (argsn => E)...))

这种将匿名函数的返回值作为下一个函数的输入，这种风格叫做currying，命名来自Haskell的创使人：Haskell Brooks Curry(1900-1982)

• 分析sum

def sum(f:Int=>Int)(a:Int,b:Int):Int = E

what is the type of sum?

(Int => Int) => (Int, Int) => Int

- 输入是(Int => Int) 

- 输出是(Int,Int)=>Int

- 因此，上面的式子等价于 `(Int => Int) => ((Int, Int) => Int)`

	- 但是函数是右结合的，因此左后的括号可以免掉


###Summation with Anonymous Functions

使用匿名函数，我们能简化`sum`函数

```scala

def sumInts(a:Int,b:Int) = sum(x=>x, a,b)
def sumCubes(a:Int,b:Int) = sum(x * x * x, a,b)

###MapReduce

• map,reduce这种函数的基础就是currying

def product(f:Int => Int)(a:Int, b:Int):Int =
  
  		if (a > b) 1
  		else f(a) * product(f)(a+1,b)     //> product: (f: Int => Int)(a: Int, b: Int)Int
  		
def fact(n:Int) = product(x => x)(1,n)          //> fact: (n: Int)Int
  
fact(3)                                         //> res1: Int = 6


def mapReduce(map:Int=>Int, combine:(Int,Int)=>Int,zero:Int)(a:Int, b:Int):Int =
	
		if (a>b) zero
		else combine(map(a), mapReduce(map,combine,zero)(a+1,b))
                                                  //> mapReduce: (map: Int => Int, combine: (Int, Int) => Int, zero: Int)(a: Int, 
                                                  //| b: Int)Int
		
	mapReduce(x=>x,(x,y)=>x*y,1)(2,4)         //> res2: Int = 24
	
	
	def new_product(f:Int=>Int)(a:Int,b:Int) = mapReduce(f,(x,y)=>x*y,1)(a,b)
                                                  //> new_product: (f: Int => Int)(a: Int, b: Int)Int
	def new_fact(n:Int) = new_product(x=>x)(1,n)
                                                  //> new_fact: (n: Int)Int
 	new_fact(4)                               //> res3: Int = 24
 	

##2-3: Finding a fixed point of a function

A number x is called a fixed point of a function f if

f(x) = x

For some functions f we can locate the fixed points by starting with an initial estimate and then by applying f in a repetitive way.

x, f(x), f(f(x)), f(f(f(x))),....

until the values does not vary anymore(or the change is sufficiently small).

This leads to the following function for finding a fixed point:

 	val tolerance = 0.0001                    //> tolerance  : Double = 1.0E-4
 
 	def isCloseEnough(x:Double,y:Double) = abs((x-y)/x)/x < tolerance
                                                  //> isCloseEnough: (x: Double, y: Double)Boolean
 
 	def fixedPoint(f:Double => Double)(firstGuess:Double):Double =
	{
			def iterate(guess:Double):Double = {
			
				val next = f(guess)
				
				if (isCloseEnough(guess,next)) next
				else
						iterate(next)
			}
			
		iterate(firstGuess)
	
	} 

###Summary

• 上周我们知道了Function是first-class的

• 这周我们知道HOF可以将function combine起来，可以做入参也可以做返回值

• As a programmer, one must look for opportunities to abstract and reuse.

• The highest level of abstraction is not always the best, but it is important to know the techniques, so as to use them properly.

##2-4:Scala syntax summary

We have seen language elements to express types, expressions and definations.

Below, we give their context-free syntax in Extended Backus-Naur form(EBNF), where:

• | denotes an alternative

• [...] an option(0 or 1)

• {...} a repetition (0 or more)

###Types

FunctionType = SimpleType => Type

		 | `( [Types] )` `=>` Type

SimpleType = Ident

Types = Type {‘,’ Type}

A type can be:

• A numeric type : Int, Double, Byte, Short, Char, Long, Float

• Boolean type : true,false

• String type

• function type, like Int => Int, (Int,Int) => Int

###Expressions

An expression can be:

• An identifier such as x, isGoodEnough

• An literal, like 0,1.0,"abc"

• An function application, like sqrt(x)

• An operator application, like -x,y+x

• An selection , like math.abs

• An conditional expression, like if(x<0) -x else x

• A block like {val x= math.abs(y) ; x+2}

• An anonymous function, like x => x+1

###Definiations:

Definition:

• A function definition like def sum(x:Int,y:Int) = x+y

• A value definitions like val y = square(2)

Parameter

• A call-by-value param, like(x:Int)

• A call-by-name para like (y: => Double)