作者：何岩，recreating.org出品，谢绝转载。
阅读SICP，站在Lisp发明者的上帝视角来思考：“我为什么要这么设计Lisp？”

0.前言：Why I design those concepts—Modularity, Objects, and State?为什么我要设计模块化，对象和状态这些概念？

为了，更简单的模拟物理世界。
我们看世界的视角有两种:
1）将世界看成由彼此对立的物质对象组成，即，Object View
2）将世界看成彼此始终相互作用的信息流构成，即，Stream View
虽然真实的世界是Stream的。但是如果我们人脑用Stream View很难理解和模拟试卷，所以为了简化，降低人脑负荷，我们采用Object View来简化的模拟真实世界。

而，我们生下来被教育的也正是Object View，对象世界观，我们都习惯于此，误以为真实的世界就真的只是Object组成，却不知道，还有另一种看世界的方式Stream View，而，佛经里的世界观就是Stream View，所以很难理解，但是又那么自洽。

我们用代码来对比一下Object view和Stream View，给自己找点感觉先：
有这样一个需求：银行账户account，取款withdraw，显示余额balance。
1）Bank Account with Object View

(define balance 100)

(define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
            balance)
        "Insufficient funds"))

2）Bank Account with Stream View

(define (stream-withdraw balance amount-stream)
    (cons-stream
        balance
            (stream-withdraw 
                (- balace (stream-car amount-stream))
                (stream-cdr amount-stream))))

我只是想让你感官体验一下，对于同样一个需求，两种世界观的编码不同，后面我们会再解释这个例子。
这两种视角不分好坏，而是，要根据具体的场景来选择。

WHAT - Object View的关键点是有状态
1）Object View和Stream View的本质不同就在于是否“有状态”，Object View认为任何对象都有自己的状态，而状态也是对象的本质。状态是可以静止的存在于时间之中的。只有当其他对象发来干涉，状态才被改变。改变后的状态在时间这个载体上可以继续维持（静态保持），所以，在Object View来看，对象是大多数时间不动的。
2）而Stream View不这么看世界，Stream View认为这个世界不存在时间，也就不存在静止不动的所谓的“状态”，世界里的所有事物都是一刻不停的在运动中，哪怕那些看上去没有变化的石头，在量子视角来看，每个组成石头的最小单元都在随机的量子态运动。所以，时间并不存在，时间概念只是对于世界中的事物运行的虚幻感知，是一种interface。我们抓不住时间，也看不见时间，我们只能用钟表的机械运转（变化）来模拟一种根本不存在的“时间”。所以，真实的世界一直都只有一刻，就是现在，没有过去也没有未来，只有一刻，在这一刻上，世界在运行，就好比一个人站在此刻站在刀锋上，一直在做着动作，却没有失去平衡掉下来，世界就是一个站在刀锋上平衡运行的人。

3）Object View中对于“有状态”的另一层意思是，对象之间是独立的，只有相互发消息的时候才会改变彼此的状态。
4）而Stream View认为时间万物都是相互作用的，而且是持续的在互相作用中，这种复杂程度根本无法用计算机建模，也就无法完全客观模拟。所以才无法被人理解，也不适合工程化。但是，我们需要模拟，只能降低清晰度，模糊的构建事物之间的关系。
而，能够感知到时间万物都在相互效力的设备就是我们的心。

5）在Object View中，为了保存状态，我们需要创造一个存储空间，这就是environment。衍生出来的概念体系是：environment model.

6）人们的焦虑/兴奋本质上只不过是为了增加/保护那个虚幻的“状态”STATE。财富是个State，地位是个State，总之可以用一个数字简单代表的就是State，而这个评估因为来自于他人，所以我们才那么在乎他人，因为如果让他人讨厌，我们的state就会很低，我们的自我存在感就会很低。这就是受制于人。
7）但是有些智者活在Stream View世界观下，他们不在乎已经取得的成绩，他们更关注每一天的做事的行为，有没有比之前更好，即关注改变。改变就是掌控感，从掌控感中直接获得快感和自我意义，这就不再受制于人，而只取决于自己的评估，即，面对当下情况，老我如何做，新我如何做，改变就这么被感知到了，成就感随即产生。
所以说，Object View下的人关注存量（数值的多少），Stream View下的人关注改变（变化本身，增量，节奏，信息），这也是有限和无限游戏的本质不同。
所以，想要转变成Stream View世界观，信息是个关键词。
关注获得的信息，而不要关注身外之物。

Chapter 3.1 Assignment and Local State

1）为了，可以操控State，需要我们设计一种新概念，即，Assignment赋值。
前两章，变量不可以被修改，只能创建变量。所有procedure都是无状态的，即，只要参数不变，不管调用多少次，结果也不变。

2）所以，真实的世界本不存在状态，真实世界是都是由无状态的procedure叠加构成，我们看到的每一个“色”的背后都叠加了我们无法感知到的超级复杂的procedure相互效力。所以，真实世界是一个无法想象数量级的并发系统。

3）因为计算机系统资源有限，无法处理过多的的并发，只能简单的模拟“色”而不能模拟产生色的所有叠加因素procedure。

4）而，bitcoin的utxo模型则是stream view下的产物，交易永远在叠加，交易不可改，每笔交易都是无状态的。所以，bitcoin更加符合宇宙模型。

5）关于状态，是在Object之中的，所以叫做Local State

6）为了表示对State的操作，我们增加一个操作符：SET!

1.为了解释得更清楚，我们用银行取款的例子来讲解。

— Chapter 3.1.1 Local State Variables
假设我们初始余额为100，我们希望的效果是，对于interface withdraw 每次调用之后，显示的余额都发生变化。

(withdraw 25)
75

(withdraw 25)
50

(withdraw 60)
"Insufficient funds"

(withdraw 15)
35

同样的参数，同样的procedure，每次调用后结果不同，这就是和前两章不同所在。
HOW - withdraw的实现代码如下：

(define balance 100)

(define (withdraw amount)
    (if (>= balance amount)
        (begin (set! balance (- balance amount))
            balance)
        "Insufficient funds"))

;;Decrementing balance is accomplished by the expression
(set! balance (- balance amount))

;;This uses the set! special form, whose syntax is 
(set! <name> <new-value>)

Here <name> is a symbol and <new-value> is any expression. Set! changes <name> so that its value is the result obtained by evaluating <new-value>.
SET!的本质就是其他语言中的等号“=”，可以看出“=”只是一个语法糖。从SICP里我们可以看到各种语法糖背后的本质，即，获得物理视角。

Why - I need “begin”?
因为，begin类似一个时间锁，在begin这个block中，时间是单线流转的。

(begin <exp1> <exp2> ... <expk>)

the value of the final expression <expk> to be returned as the value of the entire begin form.

HOW - 升级withdraw为具有Local State，为了让balance变成私有，不被其他procedure引用。

(define new-withdraw
    (let ((balance 100))
        (lambda (amount)
            (if (>= balance amount)
                (begin (set! balance (- balance amount))
                    balance)
                "Insufficient funds"))))

这就是一个闭包。

HOW - 升级为一个完整的账户操作模块

(define (make-account balance)
    (define (withdraw amount)
        (if (>= balance amount)
            (begin (set! balance (- balance amount))
                balance)
            "Insufficient funds"))
    
    (define (deposit amount)
        (set! balance (+ balance amount))
        balance)

    (define (dispatch m)
        (cond 
            ((eq? m 'withdraw) withdraw)
            ((eq? m 'deposit) deposit)
            (else (error "Unknown request -- MAKE-ACCOUNT" 
                m)))

    dispatch)   ;;return interface procedure dispatch

这就是一个Object，dispatch就是interface，唯一入口，因为procedure只能返回一个procedure，所以只能返回dispatch作为分发入口。这里用到的概念是消息驱动message-passing style.
下面是演示如何使用make-account

(define acc (make-account 100))

((acc 'withdraw) 50)
50

((acc 'withdraw) 60)
"Insufficient funds"

((acc 'deposit) 40)
90

((acc 'withdraw) 60)
30


;; another call to make-account
(define acc2 (make-account 100))
;; will produce a completely separate account object, which maintains its own local balance.
;; Why? 因为会分配独立的frame

Exercise 3.1 实现make-accumulator,累加
设计效果如下：

(define A (make-accumulator 5))

(A 10)
15

(A 10)
25

代码实现如下：

(define (make-accumulator x)
    (let ((localvale x))
        (lambda (y)
            (begin 
                (set! localvalue (+ localvalue y))
                localvalue))))

Exercise 3.2 实现make-monitored，监控f的执行次数
为了测试procedure，我们要实现一个第三方的procedure：make-monitored。
每次procedure执行一次，计数器counter就加一。
我们使用消息驱动，如果消息是how-many-calls?则返回计数器的值
如果消息是reset-count则重置counter为0.
其他消息则返回procedure的值。
设计效果如下：

(define s (make-monitored sqrt))

(s 100)
10


(s 'how-many-calls?)
1

实现思路如下：
1）如何感知到procedure的执行？换句话说如果是一个递归procedure 如何计数？
2）或者我理解错了，计数不是要记录procedure的递归次数，而是make-monitored被调用的次数。这样是可以通过不侵入procedure的代码来实现计数。
具体代码实现如下：

(define (make-monitored f)
    (let ((count 0))
        (define (how-many-calls?)
            (count))

        (define (reset-count)
            (set! count 0))

        (define (other)
            (set! count (+ 1 count))
            f)

        (define (dispatch m)
            (cond
                ((eq? m 'how-many-calls?)
                    how-may-calls?)
                ((eq? m 'reset-count)
                    reset-count)
                (else
                    other)))
        dispatch))

Exercise 3.3 实现账户密码功能
效果如下：

(define acc (make-account 100 'secret-password))


((acc 'secret-password 'withdraw) 40)
60

((acc 'some-other-password 'deposit) 50)
"Incorrect password"

具体实现代码如下：

(define (make-account balance password)
    (define (withdraw amount)
        (if (<= amount balance)
            (begin
                (SET! balance (- balance x)
                    balance)
        (else
            ("Insufficient funds")))

    (define (deposit amount)
        (SET! balance (+ balance amount)))

    (define (dispatch pwd m)
        (cond
            ((eq? pwd password) 
                (cond 
                    ((eq? m 'withdraw) withdraw)
                    ((eq? m 'deposit) deposit)
                    (else (error "Unknow request -- MAKE-ACCOUNT" m))))         
            (else "Incorrect password")))
    dispatch)    

Exercise 3.4 升级上一个例子，加入一个入参call-the-cops，即，如果密码错误超过7次则调用call-the-cops的procedure
代码如下：

(define (make-account balance password call-the-cops)
    (let ((incorrectTimes 0))
        (define (withdraw amount)
            (if (<= amount balance)
                (begin
                    (SET! balance (- balance x)
                        balance)
            (else
                ("Insufficient funds")))
    
        (define (deposit amount)
            (SET! balance (+ balance amount)))
    
        (define (dispatch pwd m)
            (cond
                ((eq? pwd password) 
                    (cond 
                        ((eq? m 'withdraw) withdraw)
                        ((eq? m 'deposit) deposit)
                        (else (error "Unknow request -- MAKE-ACCOUNT" m))))         
                (else 
                    (begin 
                        (SET! incorrectTimes (+ 1 incorrectTimes)
                        (error "Incorrect password, incorrectTimes now is:" incorrectTimes)))))
        dispatch))  

2.What is the benefits of Introducing Assignment? 赋值语句的好处是什么？

— Chapter 3.1.2 The Benefits of Introducing Assignment
Assignment can create random number。
这个是pure procedure搞不定的事情。
WHAT - 随机数的本质是什么？
不可重复性。
而pure procedure是可重复的。

3.What is the costs of Introducing Assignment?引入赋值语句的成本是什么？

— Chapter 3.1.3 The Costs of Introducing Assignment
assignment的引入，procedure不再等价于数学函数mathematical functions
前两章，没有assignment之前，所有的procedure都符合面向函数编程：functional programming
我们来对比一下，这两种编程方式的不同效果：
1）assignment：相同的参数，不同的结果

(define (make-simplified-withdraw balance)
    (lambda (amount)
        (set! balance (- balance amount))
        balance))

(define W (make-simplified-withdraw 25))

(W 20)
5

(W 10)
-5

2）not use set! ： 相同的参数，相同的结果

(define (make-decrementer balance)
    (lambda (amount)
        (- balance amount)))

(define D (make-decrementer 25))

(D 20)
5

(D 20)
5

(D 10)
15

我们用substitution model 来解释make-decrementer的运行

((make-decrementer 25) 20)

((lambda (amount) (- 25 amount)) 20)

(- 25 20)

5

如果我们用类似的substitution来分析make-simplified-withdraw

((make-simplified-withdraw 25) 20)

((lambda (amount) (set! balance (- 25 amount)) 25) 20)

(set! balance (-25 20)) 25

25

WHY - I need Environment model
如果用类似的substitution model则返回了错误答案25.
因为，在set!作用之前，balance的值就已经被替换了。正确的做法应该是等SET!之后再替换balance的值。
所以，引入了SET!的procedure就不再可以使用substitution model
而要使用一种新的model，即，Environment model.
SET!的关键点，就是需要有一个地方来存储状态STATE，并且执行SET!之后可以替换。Enviroment就是这个空间。

Exercise 3.7 实现make-joint
效果如下：

(define paul-acc
    (make-joint peter-acc 'open-sesame 'rosebud))

实现思路：
方案1:
1）refer make-account
2）改造make-account用一个list来存储多个密码
方案2:
1）不用refer make-account
2）只是在make-joint中用Higer-Order插入一层映射层，将pwd1和pwd2做映射，如果pwd2等于之前的pwd2则映射到pwd1在调用acc1，剩下的事全部有acc1去做，这样的好处是不侵入代码，只是增加一个代理层来解决。

(define (make-joint acc1 pwd1 pwd2)
    (lambda (password m)    ;;lambda的意义：代表返回的procedure接受参数
        (cond
            ((eq? m pwd2)
                (acc1 pwd1 m))
            (else
                "Incorrect the second password"))

这里可以看到Higher-Order的意义，加入一个lambda作为代理procedure来接受本来应该返回的procedure相同的参数。这样，使用者就以为自己在使用本应该返回的procedure。其实只是外面包裹了一层逻辑的匿名procedure。

Chapter3.2 The Environment Model of Evaluation

1.Why I design The Environment Model of Evaluation?为什么我要设计环境求值模型？

因为，SET!让过去的Substitution Model不再适用，所以，需要开辟一个新Model。
WHAT - Model从抽象上来看是什么？
规则，世界运转的规律，选择不同的视角来理解世界，就是选择不同的规则。
在一定范围内，两种规则都适用，都是自洽体系。甚至不那么准确的规则更实用。

两种规则对于applying的描述对比：what is meant by applying a procedure to arguments
1）Substitution model of evaluation: To apply a compound procedure to arguments, evaluate the body of the procedure with each formal parameter replaced by the corresponding argument.

2）Environment model of evaluation: In the presence of assignment, a variable can no longer be considered to be merely a name for a value. Rather, a variable must somehow designate a “place” in which values can be stored. In our new model of evaluation, these places will be maintained in structures called environments.

本质的区别在于：变量变得不同，前者是a name for a value，后者是designate a “place” in which values can be stored.

2.What is the Rules for Evaluation

— Chapter 3.2.1 The Rules for Evaluation
Substitution model
1）Evaluate the subexpressions of the combination.
2）Apply the value of the operator subexpression to the values of the operand subexpressions
3）To apply a compound procedure to arguments, evaluate the body of the procedure with each formal parameter replaced by the corresponding argument.

Environment model
1）A procedure object is applied to a set of arguments by constructing a frame, binding the formal parameters of the procedure to the arguments of the call, and then evaluating the body of the procedure in the context of the new environment constructed. The new frame has as its enclosing environment the environment part of the procedure object being applied.
2）A procedure is created by evaluating a lambda expression relative to a given environment. The resulting procedure object is a pair consisting of the text of the lambda expression and a pointer to the environment in which the procedure was created.

两者本质的区别在于，apply的时候，前者是replace，后者是bind。即，to apply a procedure to argument, create a new environment containing a frame that binds the parameters to the values of the arguments.

HOW - 用square来示意

(define (square x) (* x x))

;;等价于

(define square
    (lambda (x) (* x x)))

1）A procedure is created如下图：shows the result of evaluating this define expression.
[图片上传失败...(image-cf6df7-1602681248227)]
2）A procedure object is applied如下图：shows the procedure be applied: (square 5)
[图片上传失败...(image-61528c-1602681248227)]
Define就像是模型，Apply就像是实例化

3.Applying Simple Procedures

— Chapter 3.2.2 Applying Simple Procedures

为了实践Environment Model，我们定义如下procedures

(define (square x)
    (* x x))

(define (sum-of-squares x y)
    (+ (square x) (square y)))

(define (f a)
    (sum-of-squares (+ a 1) (* a 2)))

下图为Procedures be created
[图片上传失败...(image-349e5-1602681248227)]
下图为Procedure objects be applied:(f 5)
[图片上传失败...(image-621b6e-1602681248227)]

Exercise 3.9 : 用Environment Model来解释factorial procedure

;; 1.recursive version
(define (factorial n)
    (if (= n 1)
        1
        (* n (factorial (- n 1)))))

思路：
首先来看recursive version
1）Procedure create，parameters：n，body：（if (= n 1)…(factorial…)
2）Procedure create，global environment中将factorial bind到procedure object
3）Procedure object be applied，(factorial 6)，创建一个E1，n：6，evaluate body：

(if (= 6 1)
        1
        (* 6 (factorial (- 6 1)))))

(* 6 (factorial 5))))

(* 6 (body... 5))))

4）Procedure object be applied，(factorial 5)，创建E2，n：5，evaluate body

(* 6 (* 5 (body... 4)))))

…
直到

(* 6 (* 5 (* 2 1)))))

再来看interactive version

;; 2.iteractive version
(define (factorial n)
    (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
    (if (> counter max-count)
        product
        (fact-iter 
            (* counter product)
            (+ counter 1)
            max-count)))

1）Procedure create，env bind factorial和fact-iter
2）Procedure object applied，E1 中n：6 ， (fact-iter 1 1 6)
3）Procedure object applied，E2中product:1, counter:1, max-count:6,

(fact-iter (* 1 1) (+ 1 1) 6)

(fact-iter 1 2 6)

4）Procedure object applied，E3中product:1, counter:2, max-count:6

(fact-iter (* 1 2) (+ 2 1) 6)

(fact-iter 2 3 6)

…直到 counter > max-count

4.HOW - 如何用frames来存储Local State

Environment Model就是为了处理Local State而创造的，所以之前我们演示了简单的部分，即，本来可以用Substitution Model搞定的simply procedure，下面我们进入真正的主角，处理拥有assignment的procedure

(define (make-withdraw balance)
    (lambda (amount)
        (if (>= balance amount)
            (begin (set! balance (- balance amount))
                balance)
            "Insufficient funds")))

(define W1 (make-withdraw 100))

(W1 50)
50

1）Result of defining make-withdraw in the global environment
[图片上传失败...(image-9e3b13-1602681248227)]

2）Result of evaluating (define W1 (make-withdraw 100))
We see that E1 serves as the “place” that holds the local state variable for the procedure object W1
[图片上传失败...(image-4bad0d-1602681248227)]

3. Environment created by applying the procedure object W1
   [图片上传失败...(image-7dbf61-1602681248227)]

4）Environments after the call to W1
When the set! is executed, the binding of balance in E1 is changed.
本质上，拥有SET!和不用SET!在构建frame层面没有变化，唯一变化的点只是SET!可以去改之前frame中的值。而没有SET!的只有创建新的E里面再绑定新的value。
[图片上传失败...(image-4b100a-1602681248227)]

5）Using (define W2 (make-withdraw 100)) to create a second object.
[图片上传失败...(image-6e67a2-1602681248227)]

Exercise 3.10 如果用了let，模型会如何构建
答案是多了一层E，因为let的本质就是多包了一层lambda

(define (make-withdraw initial-amount)
    (let ((balance initial-amount))
        (lambda (amount)
            (if (>= balance amount)
                (begin (set! balance (- balance amount))
                    balance)
                "Insufficient funds"))))

(let ((<var> <exp>)) <body>)
;;is interpreted as an alternate syntax for
((lambda (<var>) <body>) <exp>)

(define (make-withdraw initial-amount)
    (lambda (balance)
        (lambda (amount)
            (if (>= balance amount)
                (begin (set! balance (- balance amount))
                    balance)
                "Insufficient funds"))))
    ) (initial-amount)

多了一层E，如下图：
[图片上传失败...(image-c76fdb-1602681248227)]

5. Why I need Internal Definitions？ 我为什么需要内部定义？

— Chapter 3.2.4 Internal Definitions
因为，internal Definitions更加模块化,不污染global environment

(define (sqrt x)
    (define (good-enough? guess)
        (< (abs (- (square guess) x)) 0.001))
    (define (improve guess)
        (average guess (/ x guess)))
    (define (sqrt-iter guess)
        (if (good-enough? guess)
            guess
            (sqrt-iter (improve guess))))
    (sqrt-iter 1.0))

[图片上传失败...(image-405e15-1602681248227)]

Internal Definitions的优点：
1）The names of the local procedures do not interfere with names external to the enclosing procedure, because the local procedure names will be bound in the frame that the procedure creates when it is run, rather than being bound in the global environment. (不运行则指存在于Procedure Object的body部分中）
2）The local procedures can access the arguments of the enclosing procedure, simply by using parameter names as free variables. This is because the body of the local procedure is evaluated in an environment that is subordinate to the evaluation environment for the enclosing procedure.

Chapter 3.3 Modeling with Mutable Data

1.Why I import this concept that Modeling with Mutable Data?

因为，要用Mutable Data来代表State。
又因为，State需要修改，所以Data就需要变成Mutable Data。
而，之前的Data都只有constructor和selector无法修改，如果变化只有创建。

WHY - 为什么需要Mutable Data来代表状态？
因为，模块化的思想，简单的Data无法足够好的模拟真实的复杂对象的状态。
也就是说，真实世界的对象的状态很复杂，需要用复杂的Data来模拟，又因为State的本质就是要可修改SET!，所以Data要称为Mutable Data。

例如：对于如下复杂数据的修改：
1）List ，通过set-car! 和 set-cdr!进行修改
2）Queue，通过insert-queue! 和 delete-queue!进行修改
3）Table，通过insert!进行修改

这些修改操作符就叫做mutators
这些Data objects就叫做mutable data objects

2.HOW - 如何让List变成可修改呢？

— Chapter 3.3.1 Mutable List Structure
通过set-car!和set-cdr!
set-car!和set-cdr!的本质就是操纵Pair中的指针Pointer
数据早已存在，改变指针其实是很小的动作。
过去不用的数据，会有GC回收。
类比真实世界，转念就是改变指针。
真正改变命运不需要我们费劲的去构建数据，而只需要轻松的改变指针，将底层假设一变，我们自己的世界就变化了。
影响我们的不是世界，而是我们对世界的看法。
而，传统的观念是，改变的本质是改变数据，或者创造新的数据。这样就很费劲。
其实好的数据已经存在，只需要我们免费的改变指针指向它们。

这本质上需要对Data和Pointer的理解更加深入。
Pointer代表了关系。
Data代表了虚拟的实体。
真正起到决定作用的反而是看起来更轻的关系Pointer。

WHAT - Mutation is just assignment
对比 Data is just Procedure
Mutation的本质就是SET!

之前对于Pair的实现，如下：

(define (cons x y)
    (define (dispatch m)
        (cond 
            ((eq? m 'car) x)
            ((eq? m 'cdr) y)
            (else (error "Undefined operation -- CONS" m))))
    dispatch)

(define (car z) (z 'car))

(define (cdr z) (z 'cdr))

改造后的Pair可以实现修改，如下：

(define (cons x y)
    (define (set-x! v) (set! x v))
    (define (set-y! v) (set! y v))
    (define (dispatch m)
        (cond 
            ((eq? m 'car) x)
            ((eq? m 'cdr) y)
            ((eq? m 'set-car!) set-x!)
            ((eq? m 'set-cdr!) set-y!)
            (else (error "Undefined operation -- CONS" m))))
    dispatch)

(define (car z) (z 'car))

(define (cdr z) (z 'cdr))

(define (set-car! z new-value)
    ((z 'set-car!) new-value)
    z)

(define (set-cdr! z new-value)
    ((z 'set-cdr!) new-value)
    z)

3.HOW - 如何构建Queues

Queue的设计效果如下：

Operation                   Resulting Queue

(define q (make-queue))
(insert-queue! q 'a)        a
(insert-queue! q 'b)        a b
(delete-queue! q)           b
(insert-queue! q 'c)        b c
(insert-queue! q 'd)        b c d
(delete-queue! q)           c d

Queue的设计如下：

;; a consturctor:
(make-queue)

;; two selectors:
(empty-queue? <queue>)

(front-queue <queue>)

;; two mutators:
(insert-queue! <queue> <item>)

(delete-queue! <queue>)

Queue的设计图，如下：
[图片上传失败...(image-421231-1602681248227)]

WHAT - QUEUE的设计思想符合分层思想，通过增加一层控制层来实现效率的增加。如果用少一层的list来实现也可以，不过效率会变低，复杂度微O(n)，而增加一层控制层，复杂度就变成了O(1)

HOW - 启发是什么？
资源都在，只需要重新设计一下，组织一下指针，神奇的事情就会发生。
这就是定位的本质。
真正的控局者是指针控制者，或者称为指针设计者。

QUEUE的具体实现代码如下：

;; 控制层pointer
(define (front-ptr queue) (car queue))

(define (rear-ptr queue) (cdr queue))

(define (set-front-ptr! queue item) (set-car! queue item))

(define (set-rear-ptr! queue item) (set-cdr! queue item))

;; 对body的控制
(define (empty-queue? queue) (null? (front-ptr queue)))

(define (make-queue) (cons '() '()))

(define (front-queue queue)
    (if (empty-queue? queue)
        (error "FRONT called with an empty queue" queue)
        (car (front-ptr queue))))

(define (insert-queue! queue item)
    (let ((new-pair (cons item '())))
        (cond 
            ((empty-queue? queue)
                (set-front-ptr! queue new-pair)
                (set-rear-ptr! queue new-pair)
                queue)
            (else
                (set-cdr! (rear-ptr queue) new-pair)
                (set-rear-ptr! queue new-pair)
                queue))

(define (delete-queue! queue)
    (cond 
        ((empty-queue? queue)
            (error "DELETE! called with an empty queue" queue))
        (else
            (set-front-ptr! queue (cdr (front-ptr queue)))
        queue)))

4.HOW - 如何构建Table

one-dimensional table单维表
a:1
b:2
c:3
设计图如下：
[图片上传失败...(image-6115fc-1602681248227)]

代码实现如下：

(define (lookup key table)
    (let ((record (assoc key (cdr table))))
        (if record
            (cdr record)
            false)))

(define (assoc key records)
    (cond
        ((null? records) false)
        ((equal? key (caar records)) (car records))
        (else (assoc key (cdr records)))))

(define (insert! key value table)
    (let ((record (assoc key (cdr table))))
        (if record
            (set-cdr! record value)
            (set-cdr! table
                (cons (cons key value) (cdr table)))))
    'ok)

(define (make-table)
    (list '*table*))

Two-dimensional tables 二维表

math:
    +: 43
    -: 45
    *: 42
letters:
    a: 97
    b:98

设计图如下：
[图片上传失败...(image-b15af3-1602681248227)]

我们可以看到通过Pair的自由组合，可以构建任意的复杂Data
本质上，自由组合基于Pair的粘性，即，最小可组合性。
具体代码实现：

(define (lookup key-1 key-2 table)
    (let ((subtable (assoc key-1 (cdr table))))
        (if subtable
            (let ((record (assoc key-2 (cdr subtable))))
                (if record
                    (cdr record)
                    false))
            false)))

(define (insert! key-1 key-2 value table)
    (let ((subtable (assoc key-1 (cdr table))))
        (if subtable
            (let ((record (assoc key-2 (cdr subtable))))
                (if record
                    (set-cdr! record value)
                    (set-cdr! subtable
                        (cons (cons key-2 value)
                              (cdr subtable)))))
            (set-cdr! table
                (cons (list key-1 (cons key-2 value))
                      (cdr table)))))
    'ok)

HOW - creating local tables

(define (make-table)
    (let ((local-table (list '*table*)))
        (define (lookup key-1 key-2)
            (let ((subtable (assoc key-1 (cdr local-table))))
                (if subtable
                    (let ((record (assoc key-2 (cdr subtable))))
                        (if record
                            (cdr record)
                            false))
                    false)))
        (define (insert! key-1 key-2 value)
            (let ((subtable (assoc key-1 (cdr local-table))))
                (if subtable
                    (let ((record (assoc key-2 (cdr subtable))))
                        (if record
                            (set-cdr! record value)
                            (set-cdr! subtable 
                                (cons (cons key-2 value)
                                      (cdr subtable)))))
                    (set-cdr! local-table
                        (cons (list key-1
                                    (cons key-2 value))
                              (cdr local-table)))))
            'ok)

        (define (dispatch m)
            (cond
                ((eq? m 'lookup-proc) lookup)
                ((eq? m 'insert-proc!) insert!)
                (else (error "Unknown operation -- TABLE" m))))
        dispatch))


;; how to use it
(define operation-table (make-table))
(define get (operation-table 'lookup-proc))
(define put (operation-talbe 'insert-proc!))