201511 SICP系列 第2讲 高阶过程、复合数据和元语言抽象 学习笔记 - xiaoxianfaye/Learning GitHub Wiki
- 0 Overview
- 1 High-Order Procedures
- 2 Compound Data
- 3 Escher’s Square Limit
- 3.1 A General Thinking to Learn a New Language
- 3.2 Henderson’s Picture Language
- 3.3 Implementation (Rectangle)
- 3.4 Implementation (Frame)
- 3.5 Complement
- 4 Summary
0 Overview
Structure and Interpretation of Computer Programs Lecture 2 - High-Order Procedures, Compound Data and Picture Language
在上一讲中讲到了，控制软件系统复杂性的三大魔法：黑盒抽象、通用接口和元语言抽象。
Outline
- High-Order Procedures
- Compound Data
- Picture Language
这一讲的主要内容有：高阶过程，复合数据，Henderson Escher画家语言设计与实现。涉及到哪几类魔法呢？
- 高阶函数能够帮助我们抽取出计算模式中的那些公共模式。
- 复合数据在比语言能够给我们提供的基础数据更高的层次上去处理领域中比较复杂的数据的问题。
- Picture Language则涉及到了元语言抽象。
1 High-Order Procedures
1.1 You’re now Certified Programmers
Erlang是一个函数式语言，用一般的过程调用就能实现迭代。
1.1.1 sum int
递归写法
-module(sum).
-compile(export_all).
sum_int(A, B) when A > B -> 0;
sum_int(A, B) -> A + sum_int(A + 1, B).
迭代写法
sum_int_i(A, B) ->
sum_int_i(A, B, 0).
sum_int_i(A, B, Acc) when A > B ->
Acc;
sum_int_i(A, B, Acc) ->
sum_int_i(A + 1, B, Acc + A).
1.1.2 sum square
递归写法
sum_sq(A, B) when A > B -> 0;
sum_sq(A, B) -> A * A + sum_sq(A + 1, B).
迭代写法
sum_sq_i(A, B) ->
sum_sq_i(A, B, 0).
sum_sq_i(A, B, Acc) when A > B ->
Acc;
sum_sq_i(A, B, Acc) ->
sum_sq_i(A + 1, B, Acc + A * A).
1.1.3 Similarity and Difference
sum_int和sum_sq有哪些相同和不同呢？ 上图中左边是相同点，包括：相同的谓词判断(都是判断A是否大于B)；相同的Consequence(A大于B的时候都表示序列结束了，都会返回0)；如果A小于B，都是要把当前值加上后面序列产生的结果。上图中右边是不同点。
1.1.4 What is the Essence?
递归写法
pi_sum(A, B) when A > B -> 0;
pi_sum(A, B) -> 1 / (A * (A + 2)) + pi_sum(A + 4, B).
迭代写法
pi_sum_i(A, B) ->
pi_sum_i(A, B, 0).
pi_sum_i(A, B, Acc) when A > B ->
Acc;
pi_sum_i(A, B, Acc) ->
pi_sum_i(A + 4, B, Acc + 1 / (A * (A + 2))).
其实，就是下面这个序列之和：
这是一个极限过程。用极限过程的结果逐步逼近最终的结果。这个极限过程是另外一个极限过程的特例。
这也是一个极限过程——莱布尼斯级数。“四分之π”是半径为1/2的圆的面积。莱布尼斯级数的关键之处在于用一个非常简单的奇数的序列把π和圆的曲线的面积联系起来。这就是用极限过程去解决的一类问题，比如曲线的面积、找出一个东西的重心，这类问题就是我们平时说的“积分”。
可以看到，当B等于10000000时，计算结果的前8位小数已经和“八分之π”一样了。
1.2 Black-Box Abstraction: Capture Common Patterns
在我们刚才写的三个小程序中间，是否存在一些Common Patterns(公共模式)？或者说，我们写的三个小函数做的是一件什么样的事情？——序列求和。数学家们也很早就发现了，所以发明了“Σ”的记法。我们经常说我们一定要挖掘出我们在做的事情的本质是什么？这个本质挖掘出来以后，给它一个形式化，给它一个名字。数学家们早就给它了一个名字，我们看到的“Σ”符号就是对序列求和概念形式化的结果。“Σ”符号周围的一些记法是序列求和概念中的关键元要素。
这个关键的元要素是什么？现在概念已经有了，计算模式中的公共模式是什么？公共模式表达如下：
这是一个序列求和，指明序列开始的序号是什么，序列结束的序号是什么，怎么从当前序号能够到当前元素的一个映射，怎么从当前序号到下一个序号的映射。整个给一个名字，就是“Σ”(sum)。
怎样把这个公共模式用函数式的语言体现出来呢？关键概念是求和，关键语素是term、next、A和B。
形式化的过程就是为它选取一个恰当意义的名字来把它表示出来。
递归写法
sum(_Term, A, _Next, B) when A > B -> 0;
sum(Term, A, Next, B) ->
Term(A) + sum(Term, Next(A), Next, B).
用sum/4改造sum_int、sum_sq和pi_sum的实现：
sum_int_2(A, B) ->
sum(fun(X) -> X end, A, fun(X) -> X + 1 end, B).
sum_sq_2(A, B) ->
sum(fun(X) -> X * X end, A, fun(X) -> X + 1 end, B).
pi_sum_2(A, B) ->
sum(fun(X) -> 1 / (X * (X + 2)) end, A, fun(X) -> X + 4 end, B).
一个“How To”是另外一个“How To”的特例。sum是Σ求和，sum_int_2、sum_sq_2和pi_sum_2是sum的特例。
这个过程虽然非常小，但是可以体会一下，一开始是在函数式编程中间怎样完成迭代这样一件事情，在写了三个函数的过程中，怎样找出中间的Common Pattern：概念本身是什么、概念中的关键语素是什么、给这些语素赋予名字。虽然这个例子比较小，但想想如果不是这样一个语言，看上去我们是做了这样一个抽象，如果是在其他语言中，如何对看似简单的这个东西来做抽象呢？在其它语言中做这件事情还真的不是那么容易。在这个过程中，体会Procedure的魔力，拿这个Procedure在两个“How to”之间传递了一些东西。
现在写的sum是一个递归过程(Recursive Process)，把sum改成一个迭代过程(Iterative Process)。对于递归过程的求和来说，计算机帮我们保存了什么状态？——就是延迟求值的“和”。所以，写成迭代版本的话，把这个“和”显式地表达出来，初始值从0开始。
迭代写法
sum_i(Term, A, Next, B) ->
sum_i(Term, A, Next, B, 0).
sum_i(_Term, A, _Next, B, Acc) when A > B ->
Acc;
sum_i(Term, A, Next, B, Acc) ->
sum_i(Term, Next(A), Next, B, Acc + Term(A)).
用sum_i/4改造sum_int、sum_sq和pi_sum的实现：
sum_int_3(A, B) ->
sum_i(fun(X) -> X end, A, fun(X) -> X + 1 end, B).
sum_sq_3(A, B) ->
sum_i(fun(X) -> X * X end, A, fun(X) -> X + 1 end, B).
pi_sum_3(A, B) ->
sum_i(fun(X) -> 1 / (X * (X + 2)) end, A, fun(X) -> X + 4 end, B).
可以看到，用高阶函数抽取了计算上的公共模式以后，有了求和这个概念以后，就可以形式化很多其它的概念。这个很重要。有了这个以后，给定一个函数，求A到B之间的定积分就是用这样一个方式来做。积分符号 “∫”其实就是“Σ”的变形。
《SICP》 P39 定积分的例子，练习1.29中也有一个定积分的改进算法。
1.3 Method for Finding a Fixed Point of a Function F
黑盒抽象，求解平方根是求解不动点的特例。
不动点：有一类函数，它们有一个性质，给了它初始值，不断地用初始值去迭代调用这个函数，在返回和输入之间会趋于稳定，这个点就是函数的不动点。
1.3.1 fixed_points? That’s George’s Matter!
求解平方根是求解不动点的特例，函数就是求Y和X/Y的平均。假设已经有了不动点的盒子，现在写一个求解平方根的过程，如何表达出它是求解不动点的过程的特例呢？“It’s George’s matter.”——“Wishful Thinking”。Wishful Thinking是一种非常非常非常好的思维方式，它是你成为Master的必要条件。
sqrt(X) ->
fixed_points(fun(Y) -> average(Y, X / Y) end, 1).
1.3.2 Who is George?
-module(fixed_points).
-compile(export_all).
-define(TOLERANCE, 0.00001).
fixed_points(Fun, Guess) ->
fixed_points_iter(Fun, Guess, Fun(Guess)).
fixed_points_iter(Fun, Old, New) ->
case close_enough(Old, New) of
true ->
New;
false ->
fixed_points_iter(Fun, New, Fun(New))
end.
close_enough(Old, New) ->
abs(New - Old) < ?TOLERANCE.
average(X, Y) ->
(X + Y) / 2.
1.3.3 What Heron of Alexandria was up to?
既然是求解平方根，很容易想到的求解函数不动点的函数是f(Y) = X/Y，刚才用的函数是f(Y) = (Y + X/Y) / 2，为什么f(Y) = X/Y这个函数不行呢？
因为不收敛，是一个不断地在无阻尼振荡的过程。那怎么消除这个振荡呢？加一点阻尼(damp out oscillations)。一个加阻尼的最简单的策略就是：在最近的这两次值之间求平均值，把这个值作为猜测，不断地去逼近。
我们现在要做的事情是：给你一个函数，你传过来的可能是无阻尼振荡，通过刚才的策略，把你传过来的无阻尼振荡的函数变成阻尼振荡的函数。
average_damp(F) ->
fun(Y) ->
average(Y, F(Y))
end.
sqrt_2(X) ->
fixed_points(average_damp(fun(Y) -> X / Y end), 1).
average_damp()函数的输入参数F，觉得F不够好，希望average_damp()返回一个平均后的函数，所以average_damp()首先返回一个函数，其次这个函数的签名肯定要和F一样，如果不一样，average_damp就不能代入到不动点的盒子去求解平方根。在average_damp返回的函数中做的事情是：拿到一个值以后，这个值不够用，把这个值放到F里做一次变成一个新的猜测，把这两个猜测取一个平均，把平均值当做猜测返回去。
不管是求平方根，还是立方根等，很容易想到的一个不动点的函数是直接提一个Y过来就可以，但这样的函数很可能是无阻尼振荡的函数，不能作为不动点输入求解，因为它不具备不动点的特性。我们所要做的就是让它具备这个特性，给它加一点阻尼。
Alexandria发明了求解平方根的过程，他做的事情就是能够让求解的过程不断地去收敛，让它不断收敛采用的手段是加了一点阻尼。
1.3.4 Play with the square root thing even more
牛顿法是求解一个函数的零值点(zero point)。零值点的意思是：求解出这个函数的一个参数，把这个参数代入到这个函数中，函数返回0，那么y就是函数的零值点。
1.3.5 George? It’s Me!
求解平方根如果是牛顿法的特例的话，传给牛顿方法的函数是什么？平方根是函数的零值点，即$f(\sqrt{X}) = 0$。所以传给牛顿方法的函数是：$f(y) = x – y^2$。
上图中的牛顿方法过程就是求解不动点的特例。$y_{n+1}$是新的Guess、$y_n$是老的猜测，$y_{n+1}$和$y_n$足够接近就是$y_{n+1}$减去$y_n$足够接近0。所以传给求解不动点的函数就是图中的那个表达式。
求解平方根是牛顿法的特例，牛顿法又是求解函数不动点的特例。
-define(DELTA_X, 0.00001).
sqrt_3(X) ->
newton(fun(Y) -> X - square(Y) end, 1).
newton(F, Guess) ->
newton(F, deriv(F), Guess).
newton(F, Df, Guess) ->
fixed_points(fun(Y) -> Y - F(Y) / Df(Y) end, Guess).
deriv(F) ->
fun(X) ->
(F(X + ?DELTA_X) - F(X)) / ?DELTA_X
end.
square(X) ->
X * X.
1.3.6 Black-box Diagram
1是初始guess，求解$\sqrt{x}$，先构造一个牛顿方法求解零值点的函数，这个函数和它的导函数一起构造出求解不动点的函数，这个函数和guess一起求解出最终的结果。
什么是黑盒抽象？盒子套盒子，每一个知识是另一个知识的一个例子。计算机科学是在表示“How to”，但我们在极致意义的追求上，还是要用“到底是什么”来把“How to”给表示出来。
1.3.7 The rights and privileges of first-class citizens
从上堂课到现在，我们都在谈论的是Procedure。谈论了一些原生的、构建在语言中的加、减、乘、除等东西；谈论了一些组合的手段，能够把它们组合在一起，构建出更大的、更加能表现领域复杂性的东西；谈论了一些抽象的手段，给这些手段赋予一个有意义的名字，就能让这个名字像原生的对象那样，能够参与构建更复杂的东西。
就在刚才，又谈论了高阶函数，体会一下在函数式编程的语言中间，Common Pattern这种抽象方式跟大家在其它语言或其它思维方式的抽象上有何不同。
Christopher Strachey，英国的计算机科学家，1975年去世，指示型语义的发明者、创造者，更重要的是他在编程语言方面非常有研究，他极力倡导将Procedure提升为编程语言的一等公民。
作为编程语言的一等公民(first-class elements或first-class citizens)，它拥有哪些特权：
- 可以给它命名；
- 可以作为函数过程本身的参数；
- 可以作为函数过程的返回值；
- 可以被组合进更大的数据结构，能帮助我们构建更加适合问题领域、更复杂的对象。
在函数式编程语言中，函数本身就是这样一个一等公民，因此在函数式编程语言中做抽象的手段和方法跟其它语言是不同的。
1.3.8 Layered System
这是我们搭建的一个分层的系统，虽然比较小。分层系统的层与层之间都会有一个抽象的边界(Abstraction Boundary)。这个抽象的边界是什么？就是我们经常说的“这是George的事情”。比如，求解sqrt，把good_enough交给George，至于他下面求解square或abs的过程，是否去找另外一个Peter，是不关心的，我们关心的是Geroge给我们做了good_enough这样一件事情，我们就可以继续去构建上面的更复杂的一些应用。
抽象边界的最关键之处在于：把构建系统的事情跟如何构建系统每个部分的事情分离开，这非常重要。它能够帮助你在思考时隔离不同层次的关注点，让你能够聚焦于核心逻辑，帮助我们构建出分层的系统，系统中的每一层都有一个抽象边界，不用关心底下如何实现，使用和实现做一个分离。
2 Compound Data
刚才我们一直在谈论Procedure，同样的，对于数据来说也是一样的。在一个编程语言中，那些基础的数据其实是不足以让我们能够应对领域中所要构建的那些复杂对象。我们有哪些基于数据的组合手段，像粘合剂一样，把一些原生的数据、基础的类型组合到一起？在我们把基础数据组合到一起的时候，会有一些非常强有力的数据抽象手段来帮助我们控制复杂性。
2.1 Arithmetic on Rational Numbers
我们想要做一个关于有理数操作的系统，先只做“加”和“乘”。
2.1.1 A Rational Number is?
想做一个关于有理数操作的系统，那么有理数是什么？在系统中，怎么样才是一个有理数？
在计算有理数的加和乘的时候，需要知道有理数的分子和分母。给定两个整数，就能构建出一个东西(祥云)，这个东西具体是什么不知道。如果把这个东西作为一个参数，可以提取出分子或分母。
2.1.2 In Terms of Clouds, I can ...
'+rat'(X, Y) ->
make_rat(numer(X) * denom(Y) + denom(X) * numer(Y),
denom(X) * denom(Y)).
'*rat'(X, Y) ->
make_rat(numer(X) * numer(Y),
denom(X) * denom(Y)).
2.1.3 The Essence I Assumed For New Kind of Object by Wishful Thinking
为什么要先假想有这么个有理数存在呢？通过Wishful Thinking，当George带来这个祥云的时候，假设有这么一个新数据对象，这个新数据对象意味着什么？意味着首先我们得有一个手段，这个手段能够帮我们构建出新的数据对象，这个手段就叫做构造器。既然我们有了新数据对象在这里，我们希望能够把新数据对象的组成部分都获取出来，就会希望有一些选择器，这些选择器能够将新数据对象中的组成部分提取出来。所以，形式化地说，我们对这个数据来做Wishful Thinking、来做假想的时候，其实就是假想有能够构建出新数据对象的构造器和能够提取出新数据对象部分信息的选择器。假想有些过程作为新数据对象的构造器，有些过程作为新数据对象的选择器。
2.1.4 Why Doing This in the First Place?
有理数虽然不是两个整数，但它是用两个整数来表示的。为什么刚才在实现有理数相加的函数的时候要求传入两个有理数，其实可以把一个有理数表示为两个整数，为什么不这样做呢？ 就是因为想要表达如上图所示的领域中的这样一个概念时，如果有理数的加、乘操作都是基于有理数的话，写出来的代码和图中的领域概念是一一对应的。
using_rat() ->
'*rat'('+rat'(X, Y),
'+rat'(S, T)).
但如果要是不这样做，可能会写成下面这样：
using_number() ->
{Pn, Pd} = '+rat'(Xn, Xd, Yn, Yd),
{Qn, Qd} = '+rat'(Sn, Sd, Tn, Td),
'*rat'(Pn, Pd, Qn, Qd).
可以看到，会有很多临时的变量。这个版本写法最大的问题在于：特别像我们用汇编语言实现两个数的相加一样，不直观。这种版本的写法在我们的日常工作中屡见不鲜。
我们希望我们编写程序让计算机来工作，其实就是我们和计算机之间的一个游戏，应该是计算机让我们快乐，而不是我们让计算机快乐。在这个游戏中间，最大的宗旨是：尽量提升语义层次，能够把头脑中的概念直观地表达出来。
当我们在有理数的世界进行思考的时候，我们想表示的就是有四个有理数，两两相加以后再相乘。
2.1.5 Glue: List Structure
接下来考虑一下，George怎么来做这个事儿。
Erlang语言中有一个列表结构可以充当粘合剂。更精确地说，不应该叫列表结构，其实是提供了一个手段，这个手段能够帮助我们去构建一个序对Pair。
序对就是把两个东西合到一起。[X|Y]就是构造器，把两个东西合到一起。hd和tl是选择器，hd取出第一个，tl取出第二个。
一般用右边的符号来标识一个序对。整个是一个序对，2和3分别表示第一个和第二个。
在Erlang Shell上试了一下：
2.1.6 Fulfill George’s Contract
-module(rational_number_without_gcd).
-compile(export_all).
make_rat(N, D) -> [N|D].
numer(R) -> hd(R).
denom(R) -> tl(R).
'+rat'(X, Y) ->
make_rat(numer(X) * denom(Y) + denom(X) * numer(Y),
denom(X) * denom(Y)).
'*rat'(X, Y) ->
make_rat(numer(X) * numer(Y),
denom(X) * denom(Y)).
test() ->
S = '+rat'(make_rat(1, 2), make_rat(1, 4)),
6 = numer(S),
8 = denom(S),
M = '*rat'(make_rat(1, 2), make_rat(2, 3)),
2 = numer(M),
6 = denom(M),
test_ok.
make_rat是有理数的构造器，numer和denom是有理数的选择器。“[|]”是Pair的构造器，hd和tl是Pair的选择器。
这么计算出来的结果是6/8和2/6，不是期望的3/4和1/3，没有约分，没有化简到最简形式。该George来做这件事儿。
2.1.7 What’s Wrong?
化简需要先求分子、分母的最大公约数GCD。
求最大公约数最简单的方法：将分子、分母因子分解，找到两者的公因子。 例如：42/30 42 = 2 × 3 × 7 30 = 2 × 3 × 5 所以，6是42和30的最大公约数，剩下7和5。
还有一个最高效的方法：欧几里得原本中的欧几里得算法。这个算法基于一个观察：如果要求解两个数X和Y的最大公约数，如果X模上Y、余数是R的话，那么GCD(X, Y) = GCD(Y, R)。
下面来非严格地写一下，现在是要求解GCD(X, Y)：
无论X大于Y，还是Y大于X，GCD(X, Y) = GCD(Y, X) 肯定成立。
所以，只考虑X大于等于Y的情况，如果X和Y的最大公约数是G，那么： X = G × Xo Y = G × Yo
刚才提过，X除以Y、余数是R，那么：X = N × Y + R 因为X大于等于Y，所以N一定是大于等于1的。
刚才提过，X = G × Xo Y = G × Yo， 可以看到，N × Y含有一个G因子，而X也含有一个G因子，所以余数R本身也肯定含有一个G因子。
所以，GCD(X, Y) = GCD(Y, R)。
根据这个算法，很容易写出如下求最大公约数的代码，在make_rat()中调用：
-module(rational_number_with_gcd).
-compile(export_all).
make_rat(N, D) ->
Gcd = gcd(N, D),
[N div Gcd | D div Gcd].
numer(R) -> hd(R).
denom(R) -> tl(R).
'+rat'(X, Y) ->
make_rat(numer(X) * denom(Y) + denom(X) * numer(Y),
denom(X) * denom(Y)).
'*rat'(X, Y) ->
make_rat(numer(X) * numer(Y),
denom(X) * denom(Y)).
% Euclid's algorithm for greatest common divisor
gcd(X, 0) -> X;
gcd(X, Y) ->
gcd(Y, X rem Y).
test() ->
S = '+rat'(make_rat(1, 2), make_rat(1, 4)),
3 = numer(S),
4 = denom(S),
M = '*rat'(make_rat(1, 2), make_rat(2, 3)),
1 = numer(M),
3 = denom(M),
test_ok.
这个GCD算法是个迭代过程，空间复杂度是1。
来看一下时间复杂度。比如，要计算42和30的GCD，根据欧几里得算法，会产生一个序列(前一个数模上后一个数)：42、30、12、6、0，通过比较这个序列和Fibonacci序列之间的关系，得到这个算法的时间复杂度。如果欧几里得算法需要K步骤来算出两个整数的GCD的话，X和Y这一对整数中间最小的数一定会大于等于第K个Fibonacci的数。Fibonacci的数是一个指数级的，那么序列本身是对数级的。所以这个GCD算法的时间复杂度是对数级的，可以参考《SICP》 P32。
2.1.8 Data Abstraction
虽然很小，但也是一个分层的系统。
make_rat、numer、denom这三个procedure构成的抽象层代表了有理数这样一个存在，这就是数据抽象方法。
数据抽象方法的关键在于：我们能够用一组构造器和选择器让数据对象的表示和上层的使用进行隔离——这是很重要的一个编程方法。
在右边的程序中，虽然有了组合手段，能够构建有理数，但看不到有理数存在，也看不到分子、分母。
虽然有了组合手段，但数据抽象的关键在于要给它一个名字，有了这个名字以后就能使用它。
2.1.9 The Advantage
数据抽象最直白的一个好处就是分离数据本身的表示和上面的使用，这样可以随意更换底下的表示而不影响上面的使用。
刚才的写法如下：
make_rat(N, D) ->
Gcd = gcd(N, D),
[N div Gcd | D div Gcd].
numer(R) -> hd(R).
denom(R) -> tl(R).
在make_rat中对有理数进行约分。
但还有一种写法：
make_rat(N, D) -> [N|D].
numer([N|D]) ->
Gcd = gcd(N, D),
N div Gcd.
denom([N|D]) ->
Gcd = gcd(N, D),
D div Gcd.
在构造的时候没有约简，而是在获取分子、分母的时候进行约简。
这两种写法的优劣要考虑到应用场景。如果在应用场景中总是不断地构建、而很少取出来的话，第二种写法是最合适的。如果是不断地获取分子、分母，然后要对它们进行操作做运算的话，第一种写法比较合适。
正是因为有了数据抽象，底下怎么实现都没有关系。
以上是数据抽象的一个好处，另外一个好处是：
The data abstraction gives you the power that
you can pretend that you have made the decision
and then later on figure out which one is right.
And when you can do that,
you have the best of both worlds.
在构建有理数的操作系统的时候，根本不用去关心怎么样表示出一个有理数。
对于一个系统架构师来说，日常最首要的工作是什么？ 不是“要做决策”，而是“要不要做决策”。一个系统架构师时时刻刻要考虑：是不是立即要为将要做的事情做出决策。
保持系统灵活性的方法就是尽量不要做出决策、直到不得不做出决策。因为一旦做出了决策，剩下来的事情很可能会受到这个决策带来的制约。希望事情向前发展，又不受已经做出的决策的制约。那怎么做事情呢？——数据抽象。
考虑“要不要做决策”的难点在于很难分清楚什么叫推迟做决策和拖延着、压根儿不做决策。
数据抽象是一个非常强有力的手段，你可以假装你已经对这个事情做出了决策，并且用Wishful Thinking给了它一个名字，然后就可以在整个系统中去使用它了，直到对系统的了解越来越深入、对它的细节各方面知识越来越清楚的时候，这时再对它该如何去做做出决策。这样就能获得双赢，既保存了系统构建时的灵活性，又能不受限于你做出的决策对后面可能产生的制约。
2.2 A More Complex System
希望组合手段能够帮助我们去构建更加复杂的东西。面临的问题是：我们提供的这些组合手段，构建出来的这些东西是不是能继续参与构建，再构建出一个更复杂的东西。
2.2.1 Vector and Segment
左图是用序对表示平面中的一个点，make_vector是构造器，xcor和ycor是选择器。基于点可以再构建线段，如右图所示。
2.2.2 Operations
这时，就可以构造基于线段上的操作。比如，求解线段的中间点，求解线段的长度。
Faye：上图左边有点笔误，应该是make_vector(average(xcor(P), xcor(Q)), average(ycor(P), ycor(Q))).
-module(segment).
-compile(export_all).
make_vector(X, Y) -> [X|Y].
xcor(P) -> hd(P).
ycor(P) -> tl(P).
make_seg(P, Q) -> [P|Q].
seg_start(S) -> hd(S).
seg_end(S) -> tl(S).
midpoint(S) ->
P = seg_start(S),
Q = seg_end(S),
make_vector(average(xcor(P), xcor(Q)),
average(ycor(P), ycor(Q))).
slength(S) ->
P = seg_start(S),
Q = seg_end(S),
Dx = xcor(P) - xcor(Q),
Dy = ycor(P) - ycor(Q),
fixed_points:sqrt(square(Dx) + square(Dy)).
average(X, Y) -> (X + Y) / 2.
square(X) -> X * X.
test() ->
[2.0|1.0] = midpoint(make_seg(make_vector(0, 0), make_vector(4, 2))),
5.0 = slength(make_seg(make_vector(0, 0), make_vector(4, 3))),
test_ok.
2.2.3 Layered System
同样的，也是一个分层的系统。数据抽象可以给我们提供表达力构建出这样一个分层的系统。每个层次上都会有数据抽象的边界来隔离上面的应用和下面的实现。
2.3 Closure
如果要用数据组合手段来组合数据的时候，要考虑一个问题：当我们用一个组合手段，比如：Pair序对，构建出来一个东西的以后，这个东西能不能继续用Pair再参与组合构建更复杂的东西。如果能的话，可以说这个语言提供的组合手段是封闭的。
凭空争论语言好坏没有意义，试金石——语言好坏的衡量标准。找一个语言都不支持的领域，来看这个语言提供的组合手段能不能帮助我们把语言提供的原生的东西有效地组合起来去构建领域概念，它提供的抽象手段能不能帮助我们去提升程序在设计时候的语义层次。给它一个合适的名字，能够让它参与更多的构建，能不能在更高的抽象层次，给它一个语义层次的名字。看语言的组合手段和抽象手段是否足够有力。
考虑一个语言提供的组合手段是不是非常好，要看它提供的组合手段构建出来的东西是不是封闭的，整个集合对这个操作是不是封闭的。如果Pair仅仅只能把两个整数揉捏到一起，不能再参与更大的构建的话，那它组合出来的数据是非常有限的，可能在语言中就需要提供非常多的其它的数据结构，而不是一种数据结构、或者说一种数据表现形式能够完成很多的复杂数据构造。现在看Pair可能觉得显而易见，但其实在大多数语言中提供的组合手段都是不封闭的。有可能只能构造出一级，很少能够构造出多级，而且还能继续构建。
2.4 What is the Essence of Data Abstraction?
现在来看，数据抽象本身到底是什么？
2.4.1 What is a Rational Number Really?
左图的上面是有理数的操作，下面是内建的一个序对，中间是抽象层，用make_rat、numer、denom表示了有理数的存在。只要有这么三个函数代表有理数，上面所有有理数操作就都可以去做了，不管下面提供了什么样的具体实现。所谓抽象是说，无论提供什么样的实现都不影响上面的操作，都能基于这样一个抽象去操作，但并不是说随便三个函数都能用。
提供的三个Procedure代表有理数，一定要满足如下条件：
给定两个整数N、D构造出来一个有理数，从有理数中取出的分子除上分母，要等于开始给定的N除上D。这就是我们和George之前的协议。
上图也是数学意义上有理数的定义、公理，也是我们跟Geroge签的协议。
2.4.2 What are Pairs Really?
前面，用构造器和选择器来表示数据抽象、表示存在这样一个数据对象，并且给构造器、选择器加上一些特定的条件，使得它们能够成为数据对象的一个合法的表示。
这个思想不仅可以用于构建有理数，同理，也可以用于序对。
如上图所示，对任何一个X、Y，如果我们构建出一个[X|Y]，取出它的hd就是X，取出tl就是Y。这就是序对的协议。
-module(pairs).
-compile(export_all).
my_cons(X, Y) ->
fun(0) -> X;
(1) -> Y
end.
my_hd(P) ->
P(0).
my_tl(P) ->
P(1).
test() ->
P = my_cons(1, 2),
1 = my_hd(P),
2 = my_tl(P),
test_ok.
这是一个纯的抽象，完全用“过程性的表示”表示了我们对于数据的抽象，下面并没有一个“聚合物”的存在，它能够满足协议就可以了。
使用了pairs的Rational Number如下：
-module(rational_number_with_pair).
-compile(export_all).
-import(pairs, [my_cons/2, my_hd/1, my_tl/1]).
make_rat(N, D) ->
Gcd = gcd(N, D),
pairs:my_cons(N div Gcd, D div Gcd).
numer(R) -> pairs:my_hd(R).
denom(R) -> pairs:my_tl(R).
'+rat'(X, Y) ->
make_rat(numer(X) * denom(Y) + denom(X) * numer(Y),
denom(X) * denom(Y)).
'*rat'(X, Y) ->
make_rat(numer(X) * numer(Y),
denom(X) * denom(Y)).
% Euclid's algorithm for greatest common divisor
gcd(X, 0) -> X;
gcd(X, Y) ->
gcd(Y, X rem Y).
test() ->
S = '+rat'(make_rat(1, 2), make_rat(1, 4)),
3 = numer(S),
4 = denom(S),
M = '*rat'(make_rat(1, 2), make_rat(2, 3)),
1 = numer(M),
3 = denom(M),
test_ok.
当然，在语言中间一般不会这样来实现，考虑到效率上的原因。但不可否认，这是一个完全合法的、满足协议的实现。更重要的是，如果你愿意的话，在你构建的系统中可以完全没有数据结构，完全基于“过程的表示”来表示所有的数据。而且，基于其上构建的系统跟下面用“聚合物”构建的系统没有任何差别。这就是抽象的强大魅力之所在！
Data？Procedure？到底是数据呢？还是过程呢？ 在传统意义上，我们总是区分数据是被动的、过程是主动的，过程是去操作数据的，过程描述了操作数据的规则。但实际上，这个界限会越来越模糊。只有把界限模糊了以后，一些非常强大的设计技术才会体现出来。
2.5 List：a Convention for Representing a Sequence
2.5.1 List
List structure是一个粘合剂，完成了序对的构建，但是它为什么叫List呢？还是有一些约定俗成的方式的，这样可以有一些惯用法来对序对进行处理。
比如：序对1,2,3,4，可能有多种表示方式，上图中画出了两种。
把序对全部串起来，chain of pairs，这就是列表。真正的语法表现形式是拿序对构建出来的“[1|[2|[3|[4|[]]]]]”，“[1,2,3,4]”是“[1|[2|[3|[4|[]]]]]”这种表示方法的语法糖衣。还有一种说法是“Well-formed List”，一个序对中间的tail部分也是一个List，这样构建出来的List叫做“Well-formed List”。序对的强大之处在于它是可以封闭的。
2.5.2 Conventional Operations on List
hd
tl
lists:last(List)
lists:nth
L = [E1, E2|T]
lists:map
lists:foreach
lists:foldr
lists:filter
上面列出了基于List的一些高阶函数和Pattern Matching。
lists:map、lists:foreach、lists:foldr、lists:filter是基于List的高阶函数，高阶函数帮助我们抽取计算中的Common Pattern，提升编程的语义层次，把列表或者序列当作一整个元素来考虑。
比如lists:map，考虑的是一个列表变换，在这个层次上考虑问题会使你不会去考虑如何去控制它的控制结构，专注于列表作为聚合物的这样一个操作。
2.6 More Operations Using Vectors
向量的加法、向量的伸缩。
-module(vector).
-compile(export_all).
make_vector(X, Y) -> [X|Y].
xcor(P) -> hd(P).
ycor(P) -> tl(P).
add_vector(X, Y) ->
make_vector(xcor(X) + xcor(Y), ycor(X) + ycor(Y)).
scale_vector(M, X) ->
make_vector(M * xcor(X), M * ycor(X)).
test() ->
[4|6] = add_vector(make_vector(1, 2), make_vector(3, 4)),
[2|4] = scale_vector(2, make_vector(1, 2)),
test_ok.
2.7 Complement
谈到抽象，往往会关注语言层面的抽象，比如C++比C好，它有OO、接口、模板、class。其实在老师讲的有理数的例子中，make_rat、numer、denom等可以采用Procedure的方式实现，可以采用Interface实现，可以采用模板方式实现，可以采用各种各样的方式实现。但要知道，不管采用哪种方式实现，这些方式都不是真正的抽象，不是说把make_rat、numer、denom定义一个抽象接口就是抽象了，那不是抽象的根本，只是实现抽象层次的技术。什么是真正的抽象呢？下面图中的才是真正的抽象。
这两点一定要区分好，在学习过程中，往往会把两者模糊掉。把很多语言特性当作设计、当成抽象。语言强大的好处在于有了抽象的本质以后，抽象很容易实现。如果没有抽象的本质，语言越强大、系统越复杂，是一个坏的设计。语言越强大可能会带来越多的复杂性。
学习语言的误区，一定要知道那些仅仅是有了抽象以后、表达抽象的技术而已，不是抽象的本身。抽象的本身是那些性质。建模的时候，首先从业务出发，把业务的性质拿出来，那些和语言没有关系，只是说这个语言表达出来更容易，那个语言表达出来稍微麻烦一点，但这不是问题的关键。
Data？Procedure？ Data和Procedure还是语言层面的概念，Pair和有理数是真正的业务抽象概念。所以一旦说有理数是Data还是Procedure，还是寄希望于用一个语言实现层面的技术去替代一个抽象。最终实现的时候，一定要做一个选择的，但在我们做设计的时候，千万不要做这种假定。一旦做了这种假定，就关上了很多原本可以更好地建立系统模型的大门。
3 Escher’s Square Limit
Escher的名画《Square Limit》(方形的极限)，体现了计算机科学的递归美。
3.1 A General Thinking to Learn a New Language
- Primitive Elements
- Means of Combination
- Means of Abstraction
以上是看待、学习和构建语言的三个要素。
Peter Henderson创建了一门语言，专门用来构建Escher的名画《Square Limit》。
3.2 Henderson’s Picture Language
3.2.1 Primitive
在Henderson’s Picture Language这个语言中，原生的元素就一个，叫Picture。
能够在指定的矩形框中间，把自己适配(伸缩)以后画出来，这就叫做Picture。
上图中的三个图是同一个Picture。为什么说这三个图是同一个Picture呢？因为这三个是在不同的矩形框中通过伸缩把自己画出来，它自己就是这么个东西，叫做G。
3.2.2 Means of Combination
用数据抽象的方法来思考，先不要去想怎么画出来的，要有一个比较高层次的思维。
- rotate_90(G)：把G逆时针转90度
- flip_horiz(G)：向上翻转
- flip_vert(G)：向左翻转
以上都是基于一个Picture元素的组合。
- beside(G, G, 0.5)
- beside(G, G, 0.25)
- above(G, G, 0.25)
以上都是基于两个Picture元素的组合手段。
- P = above(flip_horiz(G), G, 0.5)
- Q = beside(flip_vert(P), P, 0.5)
3.2.3 The Picture’s World is Closed
在这么短的时间里，原生的元素、组合的手段能够帮助我们构建出这么复杂的东西，为什么这么快地能够达到这个效果？ 原因就是：提供的组合手段是封闭的。组合出来的仍然还是一个Picture，Picture还能再参与到组合手段中，构建出来的还是一个Picture。整个Picture世界对于操作是封闭的。
可以想象，如果一个语言提供的组合手段是能够封闭的，那么它就能够高效地帮助你构建出非常非常复杂的东西。
3.3 Implementation (Rectangle)
3.3.1 Primitive
3.3.1.1 Rectangle
现在要来实现Picture语言，先来考虑有哪些基本的元素？回顾一下原生的元素Picture，能够通过伸缩把自己适配到矩形框中。那么，在Picture语言中，至少要考虑的一个关键要素是矩形框，至少先把矩形框描述出来。
上图左边：
- origin：一个原点
- horiz：一个行向量
- vert：一个纵向量 之所以画成现在的样子，是因为拿Erlang语言来实现，在Erlang语言画布中选取了跟Erlang画布坐标一致的方向，不需要再对坐标进行转换。
上图右边是数据抽象。
-module(picture_rectangle).
-compile(export_all).
make_vector(X, Y) -> [X|Y].
xcor(P) -> hd(P).
ycor(P) -> tl(P).
add_vector(X, Y) ->
make_vector(xcor(X) + xcor(Y), ycor(X) + ycor(Y)).
scale_vector(M, X) ->
make_vector(M * xcor(X), M * ycor(X)).
make_seg(P, Q) -> [P|Q].
seg_start(S) -> hd(S).
seg_end(S) -> tl(S).
make_rect(Origin, Horiz, Vert) -> {Origin, Horiz, Vert}.
origin({Origin, _Horiz, _Vert}) -> Origin.
horiz({_Origin, Horiz, _Vert}) -> Horiz.
vert({_Origin, _Horiz, Vert}) -> Vert.
test_vector() ->
[4|6] = add_vector(make_vector(1, 2), make_vector(3, 4)),
[2|4] = scale_vector(2, make_vector(1, 2)),
test_vector_ok.
test_segment() ->
Seg = make_seg(make_vector(1, 2), make_vector(3, 4)),
[1|2] = seg_start(Seg),
[3|4] = seg_end(Seg),
test_segment_ok.
test_rect() ->
Rect = make_rect(make_vector(1, 2), make_vector(3, 0), make_vector(0, 4)),
[1|2] = origin(Rect),
[3|0] = horiz(Rect),
[0|4] = vert(Rect),
test_rect_ok.
test() ->
test_vector(),
test_segment(),
test_rect(),
test_ok.
需要注意的是，Horiz和Vert都是相对于Origin的相对向量，不是相对于绝对原点(0, 0)的绝对向量。
3.3.1.2 Rectangle Defines Scaling Transformation
一个矩形框是什么？到底意味着什么？ 一个矩形框定义了一个伸缩变换。这个伸缩变化得有一个从哪儿(源头)变换到哪儿(目的地)。源头是unit square，目的地是给定的矩形框。
上图左边就是unit square，右边就是给定的矩形框。 每个矩形框都定义了一个从单位square到它自己本身的坐标转换的变换。
(x, y) => origin + x * horiz + y * vert 是向量的伸缩。 平面上的一个点就是一个向量。
3.3.1.3 coord_map
一个Rectangle定义了一个坐标变换。所以coord_map的输入是一个Rect，输出是一个坐标变换或者说是向量变换。
向量变换本身首先是一个函数过程，接受一个向量，这个向量可能是某一个点，希望把这个点通过变换映射到Rectangle中的一个点，返回一个向量。
round和计算本身没有本质的关系，只是因为要画图，像素不能是浮点数。
coord_map(Rect) ->
fun(P) ->
OriV = add_vector(
origin(Rect),
add_vector(
scale_vector(xcor(P), horiz(Rect)),
scale_vector(ycor(P), vert(Rect)))),
make_vector(round(xcor(OriV)), round(ycor(OriV)))
end.
test_coord_map() ->
Rect = make_rect(make_vector(1, 2), make_vector(3, 0), make_vector(0, 4)),
CoordMap = coord_map(Rect),
[4|6] = CoordMap(make_vector(1, 1)),
test_coord_map_ok.
Rectangle定义了坐标的变换、映射的过程。同样是Picture G，因为Rectangle不一样，所以映射的结果也不一样。
test_coord_map() ->
Rect = make_rect(make_vector(1, 2), make_vector(3, 0), make_vector(0, 4)),
CoordMap = coord_map(Rect),
[4|6] = CoordMap(make_vector(1, 1)),
Rect2 = make_rect(make_vector(2, 1), make_vector(4, 0), make_vector(0, 3)),
CoordMap2 = coord_map(Rect2),
[6|4] = CoordMap2(make_vector(1, 1)),
test_coord_map_ok.
可以看到，同样是(1, 1)向量，用不同的Rectangle转换以后映射出不同的结果。
3.3.1.4 How to Make a Picture?
给Rectangle定义了一个映射，怎样去构建一个Picture呢？
Picture本身由线段组成，可以由一组线段来初始化，即使是曲线也是连得很密的一组线段。
Picture是这么一种东西，能够把自己通过伸缩适配到指定的矩形框中去。
落实到语言层次，Picture表现为一个函数过程，首先接收一组线段，能把自己初始化，把自己初始化成一个函数过程，这个函数过程能够接收一个Rectangle，就可以把自己画出来了。
老师给出的代码如下：
make_pict(Segs) ->
fun(Rect) ->
CM = coord_map(Rect),
lists:foreach(fun(Seg) ->
drawline(CM(seg_start(Seg)), CM(seg_end(Seg)))
end,
Segs)
end.
也可以把drawline作为参数，多加一个抽象层次：
make_pict(Segs) ->
fun(Rect) ->
fun(Draw) ->
CM = coord_map(Rect),
lists:foreach(fun(Seg) ->
Draw(CM(seg_start(Seg)), CM(seg_end(Seg)))
end,
Segs)
end
end.
以上是我们对于Picture Language的原生手段的描述。
为什么把Picture实现成一个Procedure，把Erlang语言中的Procedure作为一个组合手段呢？ 我们希望组合手段是封闭的，用Procedure来实现Picture，那么对组合来说就非常简单，只要实现同样签名的函数过程，这样组合出来的东西就又可以参与到更多的组合。
3.3.1.5 How to Use Picture?
老师的代码如下：
draw_pict() ->
Segs = [make_seg(make_vector(0, 0), make_vector(0.5, 0)),
make_seg(make_vector(0, 0), make_vector(0.25, 0.5)),
make_seg(make_vector(0.25, 0.5), make_vector(0.5, 0)),
make_seg(make_vector(0.5, 1), make_vector(0.75, 0.5)),
make_seg(make_vector(0.5, 1), make_vector(1, 1)),
make_seg(make_vector(0.75, 0.5), make_vector(1, 1)),
make_seg(make_vector(0.25, 0.5), make_vector(0.75, 0.5))],
P = make_pict(Segs)
Rect = make_rect(Origin, Horiz, Vert),
(P(Rect))(fun(X, Y) ->
...
end).
3.3.1.6 How to Draw Picture?
这一部分内容，孙鸣老师的讲课内容中没有提及，我按我自己的想法补充了一下。
因为这个问题中只需要画简单的线段，所以选择Erlang的egd库来绘制图形。
画一条线段的代码如下：
-module(draw).
-compile(export_all).
drawline(StartP, EndP) ->
Image = egd:create(200, 200),
Blue = egd:color({0, 0, 255}),
egd:line(Image, StartP, EndP, Blue),
egd:save(egd:render(Image, png), "./test1.png"),
egd:destroy(Image).
需要注意的是StartP和EndP的数据结构都是坐标的tuple。
可以看到，Image、Blue、ege:save()和edg:destroy()都是针对整幅画的。原来的make_pict()实现和画图代码不容易结合。 所以，修改make_pict()实现，把绘制逻辑挪出去，make_pict()中只实现构建picture的逻辑，返回经过Rectangle转换后的线段列表。
修改后的make_pict()：
make_pict(Segs) ->
fun(Rect) ->
CM = coord_map(Rect),
[make_seg(CM(seg_start(Seg)), CM(seg_end(Seg))) || Seg <- Segs]
end.
这样修改后，也可以单元测试了：
segs() ->
[make_seg(make_vector(0, 0), make_vector(0.5, 0)),
make_seg(make_vector(0, 0), make_vector(0.25, 0.5)),
make_seg(make_vector(0.25, 0.5), make_vector(0.5, 0)),
make_seg(make_vector(0.5, 1), make_vector(0.75, 0.5)),
make_seg(make_vector(0.5, 1), make_vector(1, 1)),
make_seg(make_vector(0.75, 0.5), make_vector(1, 1)),
make_seg(make_vector(0.25, 0.5), make_vector(0.75, 0.5))].
test_make_pict() ->
Rect1 = make_rect(make_vector(0, 0), make_vector(600, 0), make_vector(0, 600)),
[[[0|0],300|0], [[0|0],150|300], [[150|300],300|0],
[[300|600],450|300], [[300|600],600|600], [[450|300],600|600],
[150](/xiaoxianfaye/Learning/wiki/300],450|300) = (make_pict(segs()))(Rect1),
Rect2 = make_rect(make_vector(0, 0), make_vector(500, 0), make_vector(0, 300)),
[[[0|0],250|0], [[0|0],125|150], [[125|150],250|0],
[[250|300],375|150], [[250|300],500|300], [[375|150],500|300],
[125](/xiaoxianfaye/Learning/wiki/150],375|150) = (make_pict(segs()))(Rect2),
Rect3 = make_rect(make_vector(0, 0), make_vector(300, 0), make_vector(0, 500)),
[[[0|0],150|0], [[0|0],75|250], [[75|250],150|0],
[[150|500],225|250], [[150|500],300|500], [[225|250],300|500],
[75](/xiaoxianfaye/Learning/wiki/250],225|250) = (make_pict(segs()))(Rect3),
Rect4 = make_rect(make_vector(50, 50), make_vector(300, 0), make_vector(0, 500)),
[[[50|50],200|50], [[50|50],125|300], [[125|300],200|50],
[[200|550],275|300], [[200|550],350|550], [[275|300],350|550],
[125](/xiaoxianfaye/Learning/wiki/300],275|300) = (make_pict(segs()))(Rect4),
test_make_pict_ok.
绘制图形的代码如下：
draw_pict(Segs, PictFileName) ->
Image = egd:create(601, 601),
Color = egd:color({0, 0, 255}),
lists:foreach(fun(Seg) ->
egd:line(
Image,
vector_to_point(seg_start(Seg)),
vector_to_point(seg_end(Seg)), Color)
end, Segs),
egd:save(egd:render(Image, png), PictFileName),
egd:destroy(Image).
vector_to_point(P) ->
{xcor(P), ycor(P)}.
因为绘制线段需要的数据结构是坐标的tuple，所以通过vector_to_point将向量转成tuple。
Image大小为(601, 601)，如果不多一个1，下底边的横线段画不出来。
绘制图形的集成测试代码如下：
test_draw_pict() ->
Segs = [make_seg(make_vector(0, 0), make_vector(300, 300)),
make_seg(make_vector(300, 300), make_vector(400, 300))],
draw_pict(Segs, "test_draw_pict_0.png"),
Rect = make_rect(make_vector(0, 0), make_vector(600, 0), make_vector(0, 600)),
CMSegs = (make_pict(segs()))(Rect),
draw_pict(CMSegs, "test_draw_pict_1.png"),
Rect2 = make_rect(make_vector(0, 0), make_vector(500, 0), make_vector(0, 300)),
CMSegs2 = (make_pict(segs()))(Rect2),
draw_pict(CMSegs2, "test_draw_pict_2.png"),
Rect3 = make_rect(make_vector(0, 0), make_vector(300, 0), make_vector(0, 500)),
CMSegs3 = (make_pict(segs()))(Rect3),
draw_pict(CMSegs3, "test_draw_pict_3.png"),
Rect4 = make_rect(make_vector(50, 50), make_vector(300, 0), make_vector(0, 500)),
CMSegs4 = (make_pict(segs()))(Rect4),
draw_pict(CMSegs4, "test_draw_pict_4.png"),
...
3.3.2 Means of Combination on Pictures
3.3.2.1 beside
前面说了，之所以把Picture实现成一个Procedure，用Procedure作为一个实现的方法，就是为了获得在组合上更大的方便性。
比如，在实现beside这样一个组合的时候，实现同样签名的函数过程，就具备了跟Primitive Picture一样的特性。
beside要做的事情，就是把左右两个矩形框指定出来，左边的矩形框给P1用，右边的给P2用。
beside(Pict1, Pict2, Ratio) ->
fun(Rect) ->
CMSegs1 = Pict1(make_rect(
origin(Rect),
scale_vector(Ratio, horiz(Rect)),
vert(Rect))),
CMSegs2 = Pict2(make_rect(
add_vector(origin(Rect), scale_vector(Ratio, horiz(Rect))),
scale_vector(1 - Ratio, horiz(Rect)),
vert(Rect))),
CMSegs1 ++ CMSegs2
end.
test_beside() ->
Rect = make_rect(make_vector(0, 0), make_vector(600, 0), make_vector(0, 600)),
Pict = make_pict(segs()),
[[[0|0],150|0], [[0|0],75|300], [[75|300],150|0],
[[150|600],225|300], [[150|600],300|600], [[225|300],300|600],
[[75|300],225|300],
[[300|0],450|0], [[300|0],375|300], [[375|300],450|0],
[[450|600],525|300], [[450|600],600|600], [[525|300],600|600],
[375](/xiaoxianfaye/Learning/wiki/300],525|300) = (beside(Pict, Pict, 0.5))(Rect),
test_beside_ok.
test_draw_pict() ->
...
Pict = make_pict(segs()),
Rect5 = make_rect(make_vector(0, 0), make_vector(600, 0), make_vector(0, 600)),
CMSegs5 = (beside(Pict, Pict, 0.5))(Rect5),
draw_pict(CMSegs5, "test_draw_pict_5.png"),
...
3.3.2.2 above
above同理。
above(Pict1, Pict2, Ratio) ->
fun(Rect) ->
CMSegs1 = Pict1(make_rect(
origin(Rect),
horiz(Rect),
scale_vector(Ratio, vert(Rect)))),
CMSegs2 = Pict2(make_rect(
add_vector(origin(Rect), scale_vector(Ratio, vert(Rect))),
horiz(Rect),
scale_vector(1 - Ratio, vert(Rect)))),
CMSegs1 ++ CMSegs2
end.
test_above() ->
Rect = make_rect(make_vector(50, 50), make_vector(400, 0), make_vector(0, 400)),
Pict = make_pict(segs()),
[[[50|50],250|50], [[50|50],150|100], [[150|100],250|50],
[[250|150],350|100], [[250|150],450|150], [[350|100],450|150],
[[150|100],350|100],
[[50|150],250|150], [[50|150],150|300], [[150|300],250|150],
[[250|450],350|300], [[250|450],450|450], [[350|300],450|450],
[150](/xiaoxianfaye/Learning/wiki/300],350|300) = (above(Pict, Pict, 0.25))(Rect),
test_above_ok.
test_draw_pict() ->
...
Rect6 = make_rect(make_vector(50, 50), make_vector(400, 0), make_vector(0, 400)),
CMSegs6 = (above(Pict, Pict, 0.25))(Rect6),
draw_pict(CMSegs6, "test_draw_pict_6.png"),
...
3.3.2.3 rotate_90
逆时针旋转90度。新的原点是原来的原点加上V，现在的H是原先的-V，现在的V是原来的H。
%% turn left 90 degrees
rotate_90(Pict) ->
fun(Rect) ->
Pict(make_rect(
add_vector(origin(Rect), vert(Rect)),
scale_vector(-1, vert(Rect)),
horiz(Rect)))
end.
test_rotate_90() ->
Rect = make_rect(make_vector(50, 50), make_vector(400, 0), make_vector(0, 400)),
Pict = make_pict(segs()),
[[[50|450],50|250], [[50|450],250|350], [[250|350],50|250],
[[450|250],250|150], [[450|250],450|50], [[250|150],450|50],
[250](/xiaoxianfaye/Learning/wiki/350],250|150) = (rotate_90(Pict))(Rect),
test_rotate_90_ok.
test_draw_pict() ->
...
Rect7 = make_rect(make_vector(50, 50), make_vector(400, 0), make_vector(0, 400)),
CMSegs7 = (rotate_90(Pict))(Rect7),
draw_pict(CMSegs7, "test_draw_pict_7.png"),
...
3.3.2.4 flip_horiz and flip_vert
flip_horiz：沿水平中轴线向上翻转。 flip_vert：沿垂直中轴线向左翻转。
flip_horiz：
flip_horiz(Pict) ->
fun(Rect) ->
Pict(make_rect(
add_vector(origin(Rect), vert(Rect)),
horiz(Rect),
scale_vector(-1, vert(Rect))))
end.
test_flip_horiz() ->
Rect = make_rect(make_vector(50, 50), make_vector(300, 0), make_vector(0, 300)),
Pict = make_pict(segs()),
[[[50|350],200|350], [[50|350],125|200], [[125|200],200|350],
[[200|50],275|200], [[200|50],350|50], [[275|200],350|50],
[125](/xiaoxianfaye/Learning/wiki/200],275|200) = (flip_horiz(Pict))(Rect),
test_flip_horiz_ok.
test_draw_pict() ->
...
Rect8 = make_rect(make_vector(50, 50), make_vector(300, 0), make_vector(0, 300)),
CMSegs8 = (flip_horiz(Pict))(Rect8),
draw_pict(CMSegs8, "test_draw_pict_8.png"),
...
flip_vert：
flip_vert(Pict) ->
fun(Rect) ->
Pict(make_rect(
add_vector(origin(Rect), horiz(Rect)),
scale_vector(-1, horiz(Rect)),
vert(Rect)))
end.
test_flip_vert() ->
Rect = make_rect(make_vector(50, 50), make_vector(300, 0), make_vector(0, 300)),
Pict = make_pict(segs()),
[[[350|50],200|50], [[350|50],275|200], [[275|200],200|50],
[[200|350],125|200], [[200|350],50|350], [[125|200],50|350],
[275](/xiaoxianfaye/Learning/wiki/200],125|200) = (flip_vert(Pict))(Rect),
test_flip_vert_ok.
test_draw_pict() ->
...
Rect9 = make_rect(make_vector(50, 50), make_vector(300, 0), make_vector(0, 300)),
CMSegs9 = (flip_vert(Pict))(Rect9),
draw_pict(CMSegs9, "test_draw_pict_9.png"),
...
3.3.3 Complement
基于这个层次思考，远远比基于坐标思考层次要高得多。这里的复杂性属于业务本身的复杂性。通过数据抽象，直接把语言的语义层次提升了，直接用这个语义来表达业务本身的逻辑。如果没有这个抽象的话，用非常低层次的Pair、数组来表达这种概念的话，就会发现业务层面本身就比较复杂，代码实现又增加了很多额外的复杂性，整个问题的复杂性就放大了，很难控制，很难做对。
最重要的一点，Rect定义了一个坐标变换，在这个层次上，当我们再去做其它的位置关系的变换时，考虑的已经不再是基于坐标的变换，考虑的是Rectangle本身的变换。这个语义层次被提高了。否则，如果全部打散，具体到一个个坐标的话，是没有这么强的表达能力的。
3.3.4 So Wonderful: Embedding Language
当把Picture用一个函数过程来体现，用实现同样签名的Procedure作为组合手段。这里的精妙之处在于，你获得了Erlang语言本身能够提供给你的、所有的、对于组合手段的封闭性。因为Procedure只要是同样的函数签名，就肯定是封闭的。所以，我把它实现为Erlang语言本身的Procedure，就自动获得了Erlang语言对于这种组合手段的封闭性。
我们刚才一直谈论原生的、组合的手段，Picture语言的组合手段是因为用了Erlang语言内置给我们带来的。更为精妙的是，我们用了这个方式实现以后，抽象手段也是Erlang语言内置可以带给我们的。它对于所有Procedure本身的抽象都可以为我们所用，这就是我们说的Embedding Language，内嵌在语言中间的。
一定要深入理解什么叫内嵌在语言中。它就变成像你自己的左右手，它的组合手段和抽象手段都能为你所用，跟你融为一体，这才叫内嵌，而不是仅仅说用这个语言(Erlang)去实现了这个语言(Picture)。
Picture语言是内嵌在Erlang语言中的，因为Picture语言用Erlang语言本身提供的组合手段Procedure来表示它的原生元素和组合手段。所以，我们可以很方便地来做一个抽象，最简单的抽象——给函数过程一个命名，一个语义层次上有意义的名字。
3.3.4.1 flip_pairs
给这幅图起一个有意义的名字flip_pairs。给一个基础图形，就能得到一个组合过的图形。
flip_pairs(Pict) ->
Pict1 = above(flip_horiz(Pict), Pict, 0.5),
beside(flip_vert(Pict1), Pict1, 0.5).
test_draw_pict() ->
...
Rect10 = make_rect(make_vector(50, 50), make_vector(300, 0), make_vector(0, 300)),
CMSegs10 = (flip_pairs(Pict))(Rect10),
draw_pict(CMSegs10, "test_draw_pict_10.png"),
...
从这里开始，单元测试代码线段太多了，就不写单元测试了。
这就是内嵌在Erlang语言中，Erlang语言所能够给我们提供的、非常强大的在抽象上的手段。
由于视频只录到这里，以下内容是根据老师的PPT，我根据自己的理解总结的内容。
3.3.4.2 Recursive Means of Combination on Pictures
3.3.4.2.1 right_push
right_push(Pict, 0, _Ratio) -> Pict;
right_push(Pict, N, Ratio) ->
beside(Pict, right_push(Pict, N - 1, Ratio), Ratio).
test_draw_pict() ->
...
Rect11 = make_rect(make_vector(0, 0), make_vector(600, 0), make_vector(0, 600)),
CMSegs11 = (right_push(Pict, 4, 0.5))(Rect11),
draw_pict(CMSegs11, "test_draw_pict_11.png"),
...
3.3.4.2.2 below_push
below_push(Pict, 0, _Ratio) -> Pict;
below_push(Pict, N, Ratio) ->
above(Pict, below_push(Pict, N - 1, Ratio), Ratio).
test_draw_pict() ->
...
Rect12 = make_rect(make_vector(0, 0), make_vector(600, 0), make_vector(0, 600)),
CMSegs12 = (below_push(Pict, 4, 0.5))(Rect12),
draw_pict(CMSegs12, "test_draw_pict_12.png"),
...
3.3.4.2.3 corner_push
corner_push(Pict, 0, _Ratio) -> Pict;
corner_push(Pict, N, Ratio) ->
TopLeft = below_push(Pict, N - 1, Ratio),
BottomRight = right_push(Pict, N - 1, Ratio),
TopRight = corner_push(Pict, N - 1, Ratio),
above(beside(Pict, above(BottomRight, BottomRight, 0.5), Ratio),
beside(beside(TopLeft, TopLeft, 0.5), TopRight, Ratio),
Ratio).
test_draw_pict() ->
...
Rect13 = make_rect(make_vector(0, 0), make_vector(600, 0), make_vector(0, 600)),
CMSegs13 = (corner_push(Pict, 4, 0.5))(Rect13),
draw_pict(CMSegs13, "test_draw_pict_13.png"),
...
3.3.4.3 Square Limit
square_limit(Pict, N, R) ->
flip_pairs(corner_push(Pict, N, R)).
test_draw_pict() ->
...
Rect14 = make_rect(make_vector(0, 0), make_vector(600, 0), make_vector(0, 600)),
CMSegs14 = (square_limit(flip_pairs(Pict), 4, 0.5))(Rect14),
draw_pict(CMSegs14, "test_draw_pict_14.png"),
...
3.3.4.4 Capture Common Pattern
仔细观察right_push、below_push：
right_push(Pict, 0, _Ratio) -> Pict;
right_push(Pict, N, Ratio) ->
beside(Pict, right_push(Pict, N - 1, Ratio), Ratio).
below_push(Pict, 0, _Ratio) -> Pict;
below_push(Pict, N, Ratio) ->
above(Pict, below_push(Pict, N - 1, Ratio), Ratio).
它们之间存在一种公共模式，在这个公共模式中有两个要素：组合手段和将组合手段重复作用于Picture。两种xxx_push都把组合手段重复了N次。right_push中的组合手段是beside、below_push中的组合手段是above。
push(Comb) ->
fun(Pict, N, Ratio) ->
(repeated(
fun(P) ->
Comb(Pict, P, Ratio)
end,
N))(Pict)
end.
repeated(_Fun, 0) ->
fun(Pict) ->
Pict
end;
repeated(Fun, N) ->
fun(Pict) ->
Fun((repeated(Fun, N - 1))(Pict))
end.
right_push和below_push可以改为：
right_push_2(Pict, N, Ratio) ->
(push(fun beside/3))(Pict, N, Ratio).
below_push_2(Pict, N, Ratio) ->
(push(fun above/3))(Pict, N, Ratio).
test_draw_pict() ->
...
Rect15 = make_rect(make_vector(0, 0), make_vector(600, 0), make_vector(0, 600)),
CMSegs15 = (right_push_2(Pict, 4, 0.5))(Rect15),
draw_pict(CMSegs15, "test_draw_pict_15.png"),
Rect16 = make_rect(make_vector(0, 0), make_vector(600, 0), make_vector(0, 600)),
CMSegs16 = (below_push_2(Pict, 4, 0.5))(Rect16),
draw_pict(CMSegs16, "test_draw_pict_16.png"),
...
corner_push是否也能修改为调用push呢？ corner_push不能直接使用目前的repeated，因为目前的repeated中的Fun是不需要N的，而corner_push中除了TopRight，TopLeft和BottomRight都需要N，因此repeated需要修改一下，才能为corner_push所用，要传入并返回N。具体怎么改，我还没想出来。。。
3.3.5 Structuring the System as Creating Language
结构化系统 v.s. 层次语言的设计与实现。
把系统构建过程看作语言构造过程。
3.4 Implementation (Frame)
当图形中的基本元素不再是矩形(Rectangle)，该如何实现呢？
3.4.1 Language of primitive picture
3.4.1.1 Rectangle is just a Specific Frame
Edge1和Edge2都是相对于frame原点的相对向量。而角向量是相对绝对坐标原点的绝对向量。
3.4.1.2 Vector
与picture_rectangle代码相比，Vector相关的代码多了一个sub_vector()，其它都是一样的：
-module(picture_frame).
-compile(export_all).
%% Language of primitive picture
% Vector
make_vector(X, Y) -> [X|Y].
xcor(P) -> hd(P).
ycor(P) -> tl(P).
add_vector(P1, P2) ->
make_vector(xcor(P1) + xcor(P2), ycor(P1) + ycor(P2)).
sub_vector(P1, P2) ->
make_vector(xcor(P1) - xcor(P2), ycor(P1) - ycor(P2)).
scale_vector(Scale, P) ->
make_vector(Scale * xcor(P), Scale * ycor(P)).
test_vector() ->
[4|6] = add_vector(make_vector(1, 2), make_vector(3, 4)),
[2|3] = sub_vector(make_vector(3, 5), make_vector(1, 2)),
[2|4] = scale_vector(2, make_vector(1, 2)),
test_vector_ok.
3.4.1.3 Segment
Segment相关的代码与picture_rectangle中的代码是一样的：
% Segment
make_seg(StartP, EndP) -> [StartP|EndP].
seg_start(Seg) -> hd(Seg).
seg_end(Seg) -> tl(Seg).
test_seg() ->
Seg = make_seg(make_vector(1, 2), make_vector(3, 4)),
[1|2] = seg_start(Seg),
[3|4] = seg_end(Seg),
test_seg_ok.
3.4.1.4 Frame
与picture_rectangle中的make_rect()类似，frame也使用tuple数据结构来保存Origin、Edge1和Edge2：
% Frame
make_frame(Origin, Edge1, Edge2) -> {Origin, Edge1, Edge2}.
origin({Origin, _Edge1, _Edge2}) -> Origin.
edge1({_Origin, Edge1, _Edge2}) -> Edge1.
edge2({_Origin, _Edge1, Edge2}) -> Edge2.
test_frame() ->
Frame = make_frame(make_vector(1, 2), make_vector(3, 0), make_vector(0, 4)),
[1|2] = origin(Frame),
[3|0] = edge1(Frame),
[0|4] = edge2(Frame),
test_frame_ok.
3.4.1.5 coord_map
与Rectangle类似，一个Frame定义了一个坐标变换。所以coord_map的输入是一个Frame，输出是一个坐标变换或者说是向量变换。
与Rectangle同理，向量变换本身首先是一个函数过程，接受一个向量，这个向量可能是某一个点，希望把这个点通过变换映射到Frame中的一个点，返回一个向量。
与Rectangle同理，round和计算本身没有本质的关系，只是因为要画图，像素不能是浮点数。
% Coordination mapping from the unit square to the frame
coord_map(Frame) ->
fun(P) ->
OriV = add_vector(
origin(Frame),
add_vector(
scale_vector(xcor(P), edge1(Frame)),
scale_vector(ycor(P), edge2(Frame)))),
make_vector(round(xcor(OriV)), round(ycor(OriV)))
end.
test_coord_map() ->
Frame1 = make_frame(make_vector(1, 2), make_vector(3, 0), make_vector(0, 4)),
CoordMap1 = coord_map(Frame1),
[4|6] = CoordMap1(make_vector(1, 1)),
Frame2 = make_frame(make_vector(1, 2), make_vector(3, 1), make_vector(2, 4)),
CoordMap2 = coord_map(Frame2),
[6|7] = CoordMap2(make_vector(1, 1)),
Frame3 = make_frame(make_vector(2, 1), make_vector(4, 1), make_vector(2, 3)),
CoordMap3 = coord_map(Frame3),
[8|5] = CoordMap3(make_vector(1, 1)),
test_coord_map_ok.
3.4.1.6 make_painter
所谓Painter，就是给我一个Frame，我可以画出自己(或者说可以计算出绘制坐标)。
与picture_rectangle的make_pict()类似，Painter本身由线段组成，可以由一组线段来初始化。给Painter一个Frame，它能够把自己通过伸缩适配到这个Frame中去，就可以画出自己或者说可以计算出绘制坐标。
picture_frame的make_painter()与picture_rectangle的make_pict()代码几乎一模一样：
% Painter
make_painter(Segs) ->
fun(Frame) ->
CM = coord_map(Frame),
[make_seg(CM(seg_start(Seg)), CM(seg_end(Seg))) || Seg <- Segs]
end.
%% Segments which are used to make painter
segs() ->
[make_seg(make_vector(0, 0), make_vector(0.5, 0)),
make_seg(make_vector(0, 0), make_vector(0.25, 0.5)),
make_seg(make_vector(0.25, 0.5), make_vector(0.5, 0)),
make_seg(make_vector(0.5, 1), make_vector(0.75, 0.5)),
make_seg(make_vector(0.5, 1), make_vector(1, 1)),
make_seg(make_vector(0.75, 0.5), make_vector(1, 1)),
make_seg(make_vector(0.25, 0.5), make_vector(0.75, 0.5))].
test_make_painter() ->
Frame1 = make_frame(make_vector(0, 0), make_vector(600, 0), make_vector(0, 600)),
[[[0|0],300|0], [[0|0],150|300], [[150|300],300|0],
[[300|600],450|300], [[300|600],600|600], [[450|300],600|600],
[150](/xiaoxianfaye/Learning/wiki/300],450|300) = (make_painter(segs()))(Frame1),
Frame2 = make_frame(make_vector(50, 50), make_vector(350, 100), make_vector(200, 450)),
[[[50|50],225|100], [[50|50],238|300], [[238|300],225|100],
[[425|550],413|350], [[425|550],600|600], [[413|350],600|600],
[238](/xiaoxianfaye/Learning/wiki/300],413|350) = (make_painter(segs()))(Frame2),
test_make_painter_ok.
3.4.1.7 draw
绘制图形的代码和picture_rectangle的绘制图形代码是一样的：
% Draw
draw(Segs, FileName) ->
Image = egd:create(601, 601),
Color = egd:color({0, 0, 255}),
lists:foreach(fun(Seg) ->
egd:line(
Image,
vector_to_point(seg_start(Seg)),
vector_to_point(seg_end(Seg)), Color)
end, Segs),
egd:save(egd:render(Image, png), FileName),
egd:destroy(Image).
vector_to_point(P) ->
{xcor(P), ycor(P)}.
test_draw() ->
Painter = make_painter(segs()),
Rectangle = make_frame(make_vector(0, 0), make_vector(600, 0), make_vector(0, 600)),
Diamond = make_frame(make_vector(50, 50), make_vector(350, 100), make_vector(200, 450)),
...
3.4.2 Language of Geometric Positions
3.4.2.1 beside
参考picture_rectangle相关的beside实现，很容易写出picture_frame的beside实现：
beside(P1, P2, Ratio) ->
fun(Frame) ->
CMSegs1 = P1(make_frame(
origin(Frame),
scale_vector(Ratio, edge1(Frame)),
edge2(Frame))),
CMSegs2 = P2(make_frame(
add_vector(origin(Frame), scale_vector(Ratio, edge1(Frame))),
scale_vector(1 - Ratio, edge1(Frame)),
edge2(Frame))),
CMSegs1 ++ CMSegs2
end.
test_beside() ->
Frame1 = make_frame(make_vector(0, 0), make_vector(600, 0), make_vector(0, 600)),
Painter1 = make_painter(segs()),
[[[0|0],150|0], [[0|0],75|300], [[75|300],150|0],
[[150|600],225|300], [[150|600],300|600], [[225|300],300|600],
[[75|300],225|300],
[[300|0],450|0], [[300|0],375|300], [[375|300],450|0],
[[450|600],525|300], [[450|600],600|600], [[525|300],600|600],
[375](/xiaoxianfaye/Learning/wiki/300],525|300) = (beside(Painter1, Painter1, 0.5))(Frame1),
Frame2 = make_frame(make_vector(50, 50), make_vector(350, 100), make_vector(200, 450)),
Painter2 = (make_painter(segs())),
[[[50|50],138|75], [[50|50],194|288], [[194|288],138|75],
[[338|525],281|313], [[338|525],425|550], [[281|313],425|550],
[[194|288],281|313],
[[225|100],313|125], [[225|100],369|338], [[369|338],313|125],
[[513|575],456|363], [[513|575],600|600], [[456|363],600|600],
[369](/xiaoxianfaye/Learning/wiki/338],456|363) = (beside(Painter2, Painter2, 0.5))(Frame2),
test_beside_ok.
test_draw() ->
...
BesidePainter = beside(Painter, Painter, 0.5),
draw(BesidePainter(Rectangle), "test_draw_painter_3.png"),
draw(BesidePainter(Diamond), "test_draw_painter_4.png"),
...
3.4.2.2 transform_painter (rewrite beside)
关于beside()，我们可以换一个思路：在Unit Square Painter和Frame Painter之间做一个转换(变形)。
实现beside的时候，先在Unit Square上定义好beside需要的两个Painter，再经过一个转换(变形)映射到Frame上，得到Frame上的两个Painter。
transform_painter
% Transform unit square painter to frame painter
transform_painter(Painter, Origin, Corner1, Corner2) ->
fun(Frame) ->
CM = coord_map(Frame),
NewOri = CM(Origin),
Edge1 = sub_vector(CM(Corner1), NewOri),
Edge2 = sub_vector(CM(Corner2), NewOri),
Painter(make_frame(NewOri, Edge1, Edge2))
end.
test_transform_painter() ->
Painter = make_painter(segs()),
Frame1 = make_frame(make_vector(0, 0), make_vector(600, 0), make_vector(0, 600)),
TransPainter1 = transform_painter(Painter, make_vector(0, 0), make_vector(1, 0), make_vector(0, 1)),
[[[0|0],300|0], [[0|0],150|300], [[150|300],300|0],
[[300|600],450|300], [[300|600],600|600], [[450|300],600|600],
[150](/xiaoxianfaye/Learning/wiki/300],450|300) = TransPainter1(Frame1),
Frame2 = make_frame(make_vector(50, 50), make_vector(350, 100), make_vector(200, 450)),
TransPainter2 = transform_painter(Painter, make_vector(0, 0), make_vector(1, 0), make_vector(0, 1)),
[[[50|50],225|100], [[50|50],238|300], [[238|300],225|100],
[[425|550],413|350], [[425|550],600|600], [[413|350],600|600],
[238](/xiaoxianfaye/Learning/wiki/300],413|350) = TransPainter2(Frame2),
Frame3 = make_frame(make_vector(0, 0), make_vector(600, 0), make_vector(0, 600)),
TransPainter3 = transform_painter(Painter, make_vector(0, 0), make_vector(0.5, 0), make_vector(0, 1)),
[[[0|0],150|0], [[0|0],75|300], [[75|300],150|0],
[[150|600],225|300], [[150|600],300|600], [[225|300],300|600],
[75](/xiaoxianfaye/Learning/wiki/300],225|300) = TransPainter3(Frame3),
Frame4 = make_frame(make_vector(0, 0), make_vector(600, 0), make_vector(0, 600)),
TransPainter4 = transform_painter(Painter, make_vector(0.5, 0), make_vector(1, 0), make_vector(0.5, 1)),
[[[300|0],450|0], [[300|0],375|300], [[375|300],450|0],
[[450|600],525|300], [[450|600],600|600], [[525|300],600|600],
[375](/xiaoxianfaye/Learning/wiki/300],525|300) = TransPainter4(Frame4),
test_transform_painter_ok.
用transform_painter()改写beside()：
beside(P1, P2, Ratio) ->
fun(Frame) ->
TransP1 = transform_painter(P1, make_vector(0, 0), make_vector(Ratio, 0), make_vector(0, 1)),
TransP2 = transform_painter(P2, make_vector(Ratio, 0), make_vector(1, 0), make_vector(Ratio, 1)),
TransP1(Frame) ++ TransP2(Frame)
end.
这样改写以后，在实现类似beside的组合手段时，只需要在Unit Square上考虑组合方式即可，相比之前的实现方式，程序更容易写对。
老师的PPT中的beside()稍微有点不一样，运行效果应该是一样的，但是不好单元测试。
beside(P1, P2, Ratio) ->
TransP1 = transform_painter(P1, make_vector(0, 0), make_vector(Ratio, 0), make_vector(0, 1)),
TransP2 = transform_painter(P2, make_vector(Ratio, 0), make_vector(1, 0), make_vector(Ratio, 1)),
fun(Frame) ->
fun(Draw) ->
(TransP1(Frame))(Draw),
(TransP2(Frame))(Draw)
end
end.
3.4.2.3 above
above(P1, P2, Ratio) ->
fun(Frame) ->
TransP1 = transform_painter(P1, make_vector(0, 0), make_vector(1, 0), make_vector(0, Ratio)),
TransP2 = transform_painter(P2, make_vector(0, Ratio), make_vector(1, Ratio), make_vector(0, 1)),
TransP1(Frame) ++ TransP2(Frame)
end.
test_above() ->
Frame1 = make_frame(make_vector(0, 0), make_vector(600, 0), make_vector(0, 600)),
Painter1 = make_painter(segs()),
[[[0|0],300|0], [[0|0],150|75], [[150|75],300|0],
[[300|150],450|75], [[300|150],600|150], [[450|75],600|150],
[[150|75],450|75],
[[0|150],300|150], [[0|150],150|375], [[150|375],300|150],
[[300|600],450|375], [[300|600],600|600], [[450|375],600|600],
[150](/xiaoxianfaye/Learning/wiki/375],450|375) = (above(Painter1, Painter1, 0.25))(Frame1),
Frame2 = make_frame(make_vector(50, 50), make_vector(350, 100), make_vector(200, 450)),
Painter2 = (make_painter(segs())),
[[[50|50],225|100], [[50|50],163|132], [[163|132],225|100],
[[275|213],338|182], [[275|213],450|263], [[338|182],450|263],
[[163|132],338|182],
[[100|163],275|213], [[100|163],263|357], [[263|357],275|213],
[[425|550],438|407], [[425|550],600|600], [[438|407],600|600],
[263](/xiaoxianfaye/Learning/wiki/357],438|407) = (above(Painter2, Painter2, 0.25))(Frame2),
test_above_ok.
test_draw() ->
...
AbovePainter = above(Painter, Painter, 0.25),
draw(AbovePainter(Rectangle), "test_draw_painter_5.png"),
draw(AbovePainter(Diamond), "test_draw_painter_6.png"),
...
3.4.2.4 rotate_90
% anti-clockwise
rotate_90(P) ->
fun(Frame) ->
TransP = transform_painter(P, make_vector(0, 1), make_vector(0, 0), make_vector(1, 1)),
TransP(Frame)
end.
仔细查看rotate_90()的函数体，发现接受一个Frame，又将TransP应用到了Frame上，因此这层Frame参数可以去掉：
老师的PPT中的rotate_90()稍微有点不一样，但最后都可以简化成下面的代码。
rotate_90(P) ->
RP = transform_painter(P, make_vector(0, 1), make_vector(0, 0), make_vector(1, 1)),
fun(Frame) ->
fun(Draw) ->
(RP(Frame))(Draw)
end
end.
rotate_90(P) ->
transform_painter(P, make_vector(0, 1), make_vector(0, 0), make_vector(1, 1)).
test_rotate_90() ->
Frame1 = make_frame(make_vector(0, 0), make_vector(600, 0), make_vector(0, 600)),
Painter1 = make_painter(segs()),
[[[0|600],0|300], [[0|600],300|450], [[300|450],0|300],
[[600|300],300|150], [[600|300],600|0], [[300|150],600|0],
[300](/xiaoxianfaye/Learning/wiki/450],300|150) = (rotate_90(Painter1))(Frame1),
Frame2 = make_frame(make_vector(50, 50), make_vector(350, 100), make_vector(200, 450)),
Painter2 = (make_painter(segs())),
[[[250|500],150|275], [[250|500],375|438], [[375|438],150|275],
[[500|375],275|213], [[500|375],400|150], [[275|213],400|150],
[375](/xiaoxianfaye/Learning/wiki/438],275|213) = (rotate_90(Painter2))(Frame2),
test_rotate_90_ok.
test_draw() ->
...
Rotate90Painter = rotate_90(Painter),
draw(Rotate90Painter(Rectangle), "test_draw_painter_7.png"),
draw(Rotate90Painter(Diamond), "test_draw_painter_8.png"),
...
3.4.2.5 flip_horiz and flip_vert
flip_horiz：沿水平中轴线向上翻转。 flip_vert：沿垂直中轴线向左翻转。
flip_horiz：
flip_horiz(P) ->
transform_painter(P, make_vector(0, 1), make_vector(1, 1), make_vector(0, 0)).
test_flip_horiz() ->
Frame1 = make_frame(make_vector(0, 0), make_vector(600, 0), make_vector(0, 600)),
Painter1 = make_painter(segs()),
[[[0|600],300|600], [[0|600],150|300], [[150|300],300|600],
[[300|0],450|300], [[300|0],600|0], [[450|300],600|0],
[150](/xiaoxianfaye/Learning/wiki/300],450|300) = (flip_horiz(Painter1))(Frame1),
Frame2 = make_frame(make_vector(50, 50), make_vector(350, 100), make_vector(200, 450)),
Painter2 = (make_painter(segs())),
[[[250|500],425|550], [[250|500],238|300], [[238|300],425|550],
[[225|100],413|350], [[225|100],400|150], [[413|350],400|150],
[238](/xiaoxianfaye/Learning/wiki/300],413|350) = (flip_horiz(Painter2))(Frame2),
test_flip_horiz_ok.
test_draw() ->
...
FlipHorizPainter = flip_horiz(Painter),
draw(FlipHorizPainter(Rectangle), "test_draw_painter_9.png"),
draw(FlipHorizPainter(Diamond), "test_draw_painter_10.png"),
...
flip_vert：
flip_vert(P) ->
transform_painter(P, make_vector(1, 0), make_vector(0, 0), make_vector(1, 1)).
test_flip_vert() ->
Frame1 = make_frame(make_vector(0, 0), make_vector(600, 0), make_vector(0, 600)),
Painter1 = make_painter(segs()),
[[[600|0],300|0], [[600|0],450|300], [[450|300],300|0],
[[300|600],150|300], [[300|600],0|600], [[150|300],0|600],
[450](/xiaoxianfaye/Learning/wiki/300],150|300) = (flip_vert(Painter1))(Frame1),
Frame2 = make_frame(make_vector(50, 50), make_vector(350, 100), make_vector(200, 450)),
Painter2 = (make_painter(segs())),
[[[400|150],225|100], [[400|150],413|350], [[413|350],225|100],
[[425|550],238|300], [[425|550],250|500], [[238|300],250|500],
[413](/xiaoxianfaye/Learning/wiki/350],238|300) = (flip_vert(Painter2))(Frame2),
test_flip_vert_ok.
test_draw() ->
...
FlipVertPainter = flip_vert(Painter),
draw(FlipVertPainter(Rectangle), "test_draw_painter_11.png"),
draw(FlipVertPainter(Diamond), "test_draw_painter_12.png"),
...
3.4.3 Language of Schemes of Combination
Language of Geometric positions中的beside、above、rotate_90、flip_horiz、flip_vert虽然变化了，但不影响Language of schemes of combination。
之前写过的flip_pairs、right_push、below_push、corner_push和square_limit的代码不用做任何修改。可以看到“分层设计”带来的好处。
3.4.3.1 flip_pairs
%% Language of schemes of combination
flip_pairs(P) ->
NewP = above(flip_horiz(P), P, 0.5),
beside(flip_vert(NewP), NewP, 0.5).
test_draw() ->
...
FlipPairsPainter = flip_pairs(Painter),
draw(FlipPairsPainter(Rectangle), "test_draw_painter_13.png"),
draw(FlipPairsPainter(Diamond), "test_draw_painter_14.png"),
...
3.4.3.2 right_push
push()和repeated()：
push(Comb) ->
fun(P, N, Ratio) ->
(repeated(
fun(P1) ->
Comb(P, P1, Ratio)
end, N))(P)
end.
repeated(_F, 0) ->
fun(P) ->
P
end;
repeated(F, N) ->
fun(P) ->
F((repeated(F, N - 1))(P))
end.
right_push()：
right_push(P, N, Ratio) ->
(push(fun beside/3))(P, N, Ratio).
test_draw() ->
...
RightPushPainter = right_push(Painter, 4, 0.5),
draw(RightPushPainter(Rectangle), "test_draw_painter_15.png"),
draw(RightPushPainter(Diamond), "test_draw_painter_16.png"),
...
3.4.3.3 below_push
below_push(P, N, Ratio) ->
(push(fun above/3))(P, N, Ratio).
test_draw() ->
...
BelowPushPainter = below_push(Painter, 4, 0.5),
draw(BelowPushPainter(Rectangle), "test_draw_painter_17.png"),
draw(BelowPushPainter(Diamond), "test_draw_painter_18.png"),
...
3.4.3.4 corner_push
corner_push(P, 0, _Ratio) ->
P;
corner_push(P, N, Ratio) ->
TopLeft = below_push(P, N - 1, Ratio),
BottomRight = right_push(P, N - 1, Ratio),
TopRight = corner_push(P, N - 1, Ratio),
above(beside(P, above(BottomRight, BottomRight, 0.5), Ratio),
beside(beside(TopLeft, TopLeft, 0.5), TopRight, Ratio),
Ratio).
test_draw() ->
...
CornerPushPainter = corner_push(Painter, 4, 0.5),
draw(CornerPushPainter(Rectangle), "test_draw_painter_19.png"),
draw(CornerPushPainter(Diamond), "test_draw_painter_20.png"),
...
3.4.3.5 square_limit
square_limit(P, N, Ratio) ->
flip_pairs(corner_push(P, N, Ratio)).
test_draw() ->
...
SquareLimitPainter = square_limit(flip_pairs(Painter), 4, 0.5),
draw(SquareLimitPainter(Rectangle), "test_draw_painter_21.png"),
draw(SquareLimitPainter(Diamond), "test_draw_painter_22.png"),
...
3.4.3.6 Big and Small
bigAndSmall有两种实现方法：
- empty、beside()、above()
- shrink_to_bottom
3.4.3.6.1 empty beside above
empty() ->
fun(_Frame) ->
[]
end.
big_and_small(P) ->
beside(P, above(empty(), P, 0.5), 0.5).
test_draw() ->
...
BigAndSmallPainter = big_and_small(Painter),
draw(BigAndSmallPainter(Rectangle), "test_draw_painter_25.png"),
draw(BigAndSmallPainter(Diamond), "test_draw_painter_26.png"),
...
3.4.3.6.2 shrink_to_bottom
shrink_to_bottom(P) ->
transform_painter(P, make_vector(0, 0.5), make_vector(1, 0.5), make_vector(0, 1)).
big_and_small_2(P) ->
beside(P, shrink_to_bottom(P), 0.5).
test_shrink_to_bottom() ->
Frame1 = make_frame(make_vector(0, 0), make_vector(600, 0), make_vector(0, 600)),
Painter1 = make_painter(segs()),
[[[0|300],300|300], [[0|300],150|450], [[150|450],300|300],
[[300|600],450|450], [[300|600],600|600], [[450|450],600|600],
[150](/xiaoxianfaye/Learning/wiki/450],450|450) = (shrink_to_bottom(Painter1))(Frame1),
Frame2 = make_frame(make_vector(50, 50), make_vector(350, 100), make_vector(200, 450)),
Painter2 = (make_painter(segs())),
[[[150|275],325|325], [[150|275],288|413], [[288|413],325|325],
[[425|550],463|463], [[425|550],600|600], [[463|463],600|600],
[288](/xiaoxianfaye/Learning/wiki/413],463|463) = (shrink_to_bottom(Painter2))(Frame2),
test_shrink_to_bottom_ok.
test_draw() ->
...
BigAndSmall2Painter = big_and_small_2(Painter),
draw(BigAndSmall2Painter(Rectangle), "test_draw_painter_27.png"),
draw(BigAndSmall2Painter(Diamond), "test_draw_painter_28.png"),
...
3.4.3.7 squash_inwards
squash_inwards(P) ->
transform_painter(P, make_vector(0, 0), make_vector(0.35, 0.65), make_vector(0.65, 0.35)).
test_draw() ->
...
SquashInwardsPainter = squash_inwards(Painter),
draw(SquashInwardsPainter(Rectangle), "test_draw_painter_29.png"),
draw(SquashInwardsPainter(Diamond), "test_draw_painter_30.png"),
...
3.4.3.8 Squash in Square Limit
test_draw() ->
...
SquashInSquareLimitPainter = square_limit(flip_pairs(squash_inwards(Painter)), 4, 0.5),
draw(SquashInSquareLimitPainter(Rectangle), "test_draw_painter_31.png"),
draw(SquashInSquareLimitPainter(Diamond), "test_draw_painter_32.png"),
SquashInSquareLimitPainter2 = square_limit(flip_pairs(squash_inwards(Painter)), 6, 0.5),
draw(SquashInSquareLimitPainter2(Rectangle), "test_draw_painter_33.png"),
draw(SquashInSquareLimitPainter2(Diamond), "test_draw_painter_34.png"),
...
3.5 Complement
- 对问题的理解，抽取Common Pattern、用更好的方法表达语义；
- High-order Procedure：高阶思维、高阶语言。
4 Summary
4.1 Pieces
- 如果能把要构建的语言内嵌在宿主语言中，可以获得宿主语言的抽象和组合手段。
- 数据和过程：能够表示、提供抽象和组合手段。数据是指程序语言中很清楚的数据。一般意义的数据是抽象的概念。
起源于LISP
4.2 Practices
《SICP》 P39 定积分的例子，练习1.29中也有一个定积分的改进算法。 《SICP》 P32 GCD欧几里得算法的时间复杂度
4.3 Faye’s Summary
正如本次课程开场白中讲到的，本次课程包括了三部分内容：
- 高阶过程
- 复合数据
- Picture Language (元语言抽象)
4.3.1 High Procedure
在这部分内容里，通过“sum”和“平方根”的例子展示了如何抽取Common Pattern，并用高阶函数来表达的过程，并再次展示了用“黑盒抽象”这种魔法在控制软件系统复杂性上的魔力。
在“平方根”的例子中，搭建了一个分层系统(Layered System)来求解平方根。分层系统的层与层之间都会有一个抽象的边界(Abstraction Boundary)。抽象边界的关键之处在于：把“构建系统的事情”跟“如何构建系统每个部分的事情”分离开，这一点非常重要。
用这种思维方式思考时，隔离了不同层次的关注点，能够聚焦于核心逻辑，构建出分层的系统，系统中的每一层都有一个抽象边界，不用关心底下如何实现，分离了使用和实现。
4.3.2 Compound Data
在这部分内容里，用构造器和选择器来表示数据抽象，并给构造器和选择器加上一些特定的条件，使得他们能够成为数据对象的一个合法表示。比如序对->有理数、序对->向量->线段等。
可以完全用“过程性的表示”来表示数据抽象，下面并没有一个所谓“聚合物”的存在，只要能够满足协议即可。这样的话，在构建的系统中可以完全没有数据结构，完全基于“过程性的表示”来表示所有的数据。重要的是，基于其上构建的系统跟下面用“聚合物”构建的系统没有任何差别。这体现了抽象的魔力。
做一名架构师，经常做的事情不是“做决策”，而应该是“要不要做决策”。考虑“要不要做决策”的难点在于很难分清“推迟做决策”和“拖延不做决策”。数据抽象是一个非常强有力的手段，它使得你可以假装已经对某件事情做出了决策，并且用Wishful Thinking给这件事情起一个名字，然后就可以在整个系统中去使用它了，直到你对系统的了解越来越深入、对它的各方面细节知识越来越清楚，这时再对“如何去做这件事情”做出决策。这样既保存了系统构建时的灵活性，又能不受限于做出的决策对后面可能产生的制约。
要注意区分语言层面的抽象和本质的抽象。不是说用了Interface、Template等OO技术就是抽象了，这些只是实现抽象层次的技术。抽象的本质是那些性质。建模的时候，首先从业务出发，把业务的性质拿出来，而这些性质和语言没有关系。语言强大的好处在于有了抽象的本质以后，抽象很容易实现而已。如果没有抽象的本质，语言越强大，系统越复杂，越容易产生坏的设计，因为语言越强大可能会带来越多的复杂性。还记得在第一次课程中，孙鸣老师提醒过“不要混淆了事情的本质和做这件事情所使用的工具”，真是一针见血。
凭空争论语言的好坏没有意义，有一块试金石——看语言的组合手段和抽象手段是否足够有力。找一个所有语言都不支持的领域，看看语言提供的组合手段能否把语言提供的原生要素有效地组合起来去构建领域概念，并且具有闭包性质；看看语言提供的抽象手段能否提升设计的语义层次。
4.3.3 Picture Language
“Primitive Elements”、“Means of Combination”和“Means of Abstraction”是看待、学习和构建语言的三要素。
对于Picture Language来说，Primitive Elements只有一个，就是Picture。rotate_90、flip_horiz、flip_vert等是基于一个Picture元素的组合，beside和above是基于两个Picture元素的组合，right_push、below_push和corner_push是基于一个Picture元素的递归组合。
当用一个函数过程来表达Picture这个原生元素时，就可以用一个同样签名的函数过程来表达组合手段。正因如此，天然获得了Erlang语言本身能够提供的、所有的、对于组合手段的封闭性。因为函数过程只要是同样的函数签名，就肯定是封闭的。与此同时，Erlang语言对于函数过程本身的抽象也都可以为我所用。因此，Picture语言是内嵌在Erlang语言中的(Embedding Language)，而不仅仅是用Erlang语言实现了Picture语言。Picture语言用Erlang语言本身提供的组合手段“Procedure”来表示它的原生元素和组合手段。所以，我们可以很方便地来做一个抽象，最简单的抽象——给函数过程一个命名，一个语义层次上有意义的名字。
把系统构建过程看作语言构造过程：