# Programming Language 课程笔记

Posted by Masutangu on March 2, 2018

## 一. 声明式编程和命令式编程

#### 声明式编程（Declarative Programming）

Building the structure and elements of computer programs, that expresses the logic of a computation without describing its control flow.

#### 命令式编程（Imperative Programming）

Describes computation in terms of statements that change a program state.

## 二. 函数式编程

• No Mutation
• First Class Function
• Tail Recursion Optimization

### 1. No Mutation

• No code can ever distinguish aliasing vs. identical copies
• No need to think about aliasing: focus on other things
• Can use aliasing, which saves space, without danger

### 2. How to build bigger types

3 most important type building-blocks in any language

• Each of: A t value contains values of each of t1 t2 … tn
• One of: A t value contains values of one of t1 t2 … tn
• Self reference: A t value can refer to other t values

### 3. Tail Recursion and Accumulators

ML recognizes these tail calls in the compiler and treats them differently: pop the caller before the call, allowing callee to reuse the same stack space

### 4. Higher Order Function

#### Map

1
2
3
4
fun map (f,xs) =
case xs of
[] => []
| x::xs’ => (f x)::(map(f,xs’))


#### Filter

1
2
3
4
5
6
fun filter (f,xs) =
case xs of
[] => []
| x::xs’ => if f x
then x::(filter(f,xs’))
else filter(f,xs’)


#### Fold

1
2
3
4
fun fold f acc xs =
case xs of
[] => acc
| x::xs’ => fold f (f(acc,x)) xs’


#### Higher Order Function vs For Loop

Fold is another very famous iterator over recursive structures. This pattern separates recursive traversal from data processing:

• Can reuse same traversal for different data processing
• Can reuse same data processing for different data structures
• In both cases, using common vocabulary concisely communicates intent

### 5. Function Closure

A function value has two parts:

• The code
• The environment that was current when the function was defined

This pair is called a function closure.

### 6. Abstract Data Types With Closure

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
datatype set = S of { insert : int -> set,
member : int -> bool,
size   : unit -> int }

val empty_set =
let
fun make_set xs = (* xs is a "private field" in result *)
let (* contains a "private method" in result *)
fun contains i = List.exists (fn j => i=j) xs
in
S { insert = fn i => if contains i
then make_set xs
else make_set (i::xs),
member = contains,
size   = fn () => length xs
}
end
in
make_set []
end

fun use_sets () =
let val S s1 = empty_set
val S s2 = (#insert s1) 34
val S s3 = (#insert s2) 34
val S s4 = #insert s3 19
in
if (#member s4) 42
then 99
else if (#member s4) 19
then 17 + (#size s3) ()
else 0
end


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
interface Func<B,A> {
B m(A x);
}
interface Pred<A> {
boolean m(A x);
}

class List<T> {
List<T> tail;
List(T x, List<T> xs) {
tail = xs;
}

// * the advantage of a static method is it allows xs to be null
//    -- a more OO way would be a subclass for empty lists
// * a more efficient way in Java would be a messy while loop
//   where you keep a pointer to the previous element and mutate it
//   -- (try it if you do not believe it is messy)
static <A,B> List<B> map(Func<B,A> f, List<A> xs) {
if(xs==null)
return null;
return new List<B>(f.m(xs.head), map(f,xs.tail));
}

static <A> List<A> filter(Pred<A> f, List<A> xs) {
if(xs==null)
return null;
return new List<A>(xs.head, filter(f,xs.tail));
return filter(f,xs.tail);
}

// * again recursion would be more elegant but less efficient
// * again an instance method would be more common, but then
//   all clients have to special-case null
static <A> int length(List<A> xs) {
int ans = 0;
while(xs != null) {
++ans;
xs = xs.tail;
}
return ans;
}
}

class ExampleClients {
static List<Integer> doubleAll(List<Integer> xs) {
return List.map((new Func<Integer,Integer>() {
public Integer m(Integer x) { return x * 2; }
}), xs);
}
static int countNs(List<Integer> xs, final int n) {
return List.length(List.filter(
(new Pred<Integer>() {
public boolean m(Integer x) { return x==n; }
}), xs));
}
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
typedef struct List list_t;
struct List {
list_t * tail;
};

list_t * makelist (void * x, list_t * xs) {
list_t * ans = (list_t *)malloc(sizeof(list_t));
ans->tail = xs;
return ans;
}

list_t * map(void* (*f)(void*,void*), void* env, list_t * xs) {
if(xs==NULL)
return NULL;
}

list_t * filter(bool (*f)(void*,void*), void* env, list_t * xs) {
if(xs==NULL)
return NULL;
return filter(f,env,xs->tail);
}

int length(list_t* xs) {
int ans = 0;
while(xs != NULL) {
++ans;
xs = xs->tail;
}
return ans;
}

// clients of our list implementation:
// [the clients that cast from void* to intptr_t are technically not legal C,
//  as explained in detail below if curious]

// awful type casts to match what map expects
void* doubleInt(void* ignore, void* i) {
return (void*)(((intptr_t)i)*2);
}

// assumes list holds intptr_t fields
list_t * doubleAll(list_t * xs) {
return map(doubleInt, NULL, xs);
}

// awful type casts to match what filter expects
bool isN(void* n, void* i) {
return ((intptr_t)n)==((intptr_t)i);
}

// assumes list hold intptr_t fields
int countNs(list_t * xs, intptr_t n) {
return length(filter(isN, (void*)n, xs));
} 