Positioning SICP 4: Metalinguistic Abstraction

Positioning SICP 4: Metalinguistic Abstraction #

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

0.前言 #

1）从这一章开始，我们进入了SICP的“解释”部分。即，对于lisp这个语言的支撑。而之前都是用lisp这个语言在进行构建。构建是往上层走。解释是往下层走。
2）Why 为什么要学习lisp语言的解释？因为，我想知道这个世界上的奥秘。而lisp是对世界的浓缩抽象。通过理解lisp的解释，就可以类比的理解整个世界的运行规律。
3）Why？ 为什么要构建语言的抽象？因为，我们的根本目的是模拟复杂的真实世界。当lisp语言无法满足模拟某些领域的时候，针对这个领域开发一种新语言（中间层）则是一个更有效的思路。所以，我们要研究如何构建语言。
4）How？如何研究构建新语言呢？我们先从构建lisp自身开始，构建lisp的本质就是写一个lisp expression的解释器，解释器的本质就是一段程序，输入就是一个表达式结构的Data。然后我们再来通过改造这个解释器来体会构建语言的妙处。例如通过改造解释器实现一种新的求值order，即，Normal order evaluation。通过改造解释器实现一种新的语言：logic language。
5）How？学习构建语言抽象的意义是什么？答案是，丰富视角，从更抽象的通用视角来看待整个计算机科学，万物都是解释器。普通程序也是解释器。普通程序就是支撑具体一个业务的语言。所以，我们可以将任何算法都称为语言。语言的本质就是规则的载体。用这个语言构建的业务，就可以看成是遵守了某个规则下的游戏。

Chapter 4.1 The Metacircular Evaluator #

1.Why lisp can evaluate itself?为什么可以用lisp来构建lisp的解释器？ #

1）因为，解释器本质就是规则，lisp可以构建规则，当然可以构建lisp解释器。
但是，有一个关键点，新的lisp解释器中用到了一个原始的procedure即apply，这个地方，新的lisp解释器没有自己实现，不知道为什么？不能自己实现吗？
因为，求值的最底层就是bate-reduction，如何用lisp来描述bate-reduction呢？也许做不到吧。
2）What is metacircular: An evaluator that is written in the same language that it evaluates is said to be metacircular.

What - lisp解释器的本质： #

LISP解释器的本质载体就是这两个简单的程序：eval和apply，解释器就像其他普通程序一样处理的是Data，只不过这里的data要符合解释器定义的语言规则（也就是编程语言表达式expression）
用户输入一段代码也就是expression，先进入到eval，eval干的事就是：分。 分完之后，将分好的多个data传给apply。apply干的事就是合，合在一起之后，将合的data再传给eval。eval在重复上面的逻辑继续分，然后传给apply。他俩就这么一分一合，直到data成为无法分/合的归一。

1）解释器的本质就是分/合的递归，直到无法分/合的归一。
2）eval代表分，apply代表合
3）物理视角的伪代码：
eval的分：将expression分为procedure和arguments两句，再传给apply
(apply
(operator expression)
(operands expression))
apply的合：将算法和数据合并为一句到eval中去
(eval expression environment)
;; expression代表算法
;; environment代表数据
4）procedure就是data，data就是procedure，色即是空，空即是色。
色隐喻着procedure，空隐喻着data。
同时空又有一层表达，物质的存在不是有更小的物质组合而成，而是有什么都没有的虚空模拟而成。
data的最基本概念为Pair，pair的定义是基于cons/car/cdr这三个procedure。
procedure的构成又是基于list，list的本质就是pair的变形，
看代码：
1.data由procedure模拟而成：
(define (cons x y)
(lambda (m) (m x y)))

(define (car z)
(z (lambda (p q) p)))

(define (cdr z)
(z (lambda (p q) q)))
2.procedure由data模拟而成：
(define (make-procedure parameters body env)
(list ‘procedure parameters body env))

5）信息，是procedure和data的统一视角。
6）计算机科学的第一性原理就是解释器，解释器的第一性原理就是信息的分/合的递归。见下图：
(img)
7）抽象到宇宙观，宇宙的第一性原理也是信息的分/合，宇宙的本质就是信息，宇宙的行为就是信息的分/合。从宏观来看，宇宙就是在做着如同呼吸一样的扩张（分）与收缩（合）
8）所以，我们解决任何问题的思路，无非就是分/合。一切尽在分/合之间。

What - lisp解释器的本质update：定位出解释器的概念体系。 #

1）lisp的解释器由eval/apply这两个procedure来承载。
2）从抽象视角来看，eval/apply本质上就是再实现lambda演算中的Beta-Reduction，即，((λx.M) E) → (M [x:= E])，Replacing the bound variables with the argument expression in the body of the abstraction.

3）Beta-Reduction本质上就是在做组装，将参数装入到Lambda的body中。
4）计算的本质就是Beta-Reduction的这一组装/变形的动作。
5）只不过Eval/Apply将这个组装动作进行了分解：
首先，一个像这样的最简单的application：((lambda (x) (x)) 3)，作为expression传入到Eval中。
然后，Eval对这个expression做分解，将((lambda (x) (x)) 3)分解为连个部分：
procedure部分：(operator expression) 对应着 (lambda(x) (x))
argument部分：(operands expression) 对应着 3
再将这两部分传给Apply
Apply干了两件事：1.将procedure提取出body部分：(x)，2.将procedure中的parameter：x，绑定argument：3，也就是将x=3存入到一个table中，即，env出现。
Apply再将body和env传入给Eval
Eval，拿到body和env干的事，才是真正的组装，即，发现body中遇到的变量x，去evn中寻找x对应的value：3，然后将value装入到body中(x)就变成了最终的结果：3.
所以说，eval/apply将lambda演算中的Bate-Reduction进行了分解动作。
6）Why？为什么要分解动作？难道不能用一个procedure直接的进行Bata-Reduction的组装吗？即，直接将expression中的operand组装到operator中去。
答案是，因为要兼容赋值模型Assignment，eval运行时并不知道一个procedure的body中是否包含Assignment，所以要兼容，当作可能有Assignment来处理。Assignment就不能直接将operand直接装入到operator中去，因为body中的变量可能随时被别人修改。所以要引入Env来由一个中间环节来存储body中的变量。
当然，如果能够确定，要处理的所有expression都没有assignment，那么解释器就可以简化成，不再需要evn。
7）所以，抽象来看解释器的精髓点就是Beta-Reduction的实现。
8）当然，解释器的非核心部分还实现了Lambda演算中的其他概念：变量variable，抽象体abstraction，应用application。
9）所以，更全面，但是没有精髓感的说，抽象来看解释器就是Lambda演算的实现。
10）Lisp解释器与Lambda演算的对应关系：
1.变量Variable的实现对应的代码是：
((variable? exp) (lookup-variable-value exp env))
2.抽象体Abstraction的实现对的代码是：
((lambda? exp)
(make-procedure (lambda-parameters exp)
(lambda-body exp)
env))
3.应用Application的实现对应的代码是：
((application? exp)
(apply (eval (operator exp) env)
(list-of-values (operands exp) env)))
11）Lisp解释器为了让语言更加高效而加入的衍生规则，当然这些衍生规则都可以用上面的那三个原则来推演而得。但是为了构建逻辑更加高效，而增加的中间层。
1.原始元素：数字(1,2,3等）和数字运算操作符(+ - 等)
((self-evaluationg? exp) exp)
2.字符串
((quoted? exp) (text-of-quotation exp))
3.赋值语句
((assignment? exp) (eval-assignment exp env))
4.定义
((definition? exp) (eval-definition exp env))
5.条件语句
((if? exp) (eval-if exp env))
;; and
((cond? exp) (eval (cond->if exp) env))
6.begin语句
((begin? exp)
(eval-sequence (begin-actions exp) env))

2.HOW - 如何设计lisp的求值器/解释器？ #

1）分解：eval
2）组装：apply
3）两者的递归循环，直到分解到primitive 元素。
4）分解：eval就是解释，解释就是映射，就是将一种符号按照规则映射成另一种符号
5）组装：apply就是变形，当面对不是单一符号的时候，而是一个lambda和参数的时候，就需要先组装，然后再次调用eval来解释。如此递归。
6）eval/apply就像是漩涡模型的内环，支撑起来的外环就是lisp的各种expressions也就是lisp语言。
(img)
1）eval的代码如下：
eval的本质就是对各种类型的expression的处理
(define (eval exp env)
(cond
((self-evaluationg? exp) exp)
((variable? exp) (lookup-variable-value exp env))
((quoted? exp) (text-of-quotation exp))
((assignment? exp) (eval-assignment exp env))
((definition? exp) (eval-definition exp env))
((if? exp) (eval-if exp env))
((lambda? exp)
(make-procedure (lambda-parameters exp)
(lambda-body exp)
env))
((begin? exp)
(eval-sequence (begin-actions exp) env))
((cond? exp) (eval (cond->if exp) env))
((application? exp)
(apply (eval (operator exp) env)
(list-of-values (operands exp) env)))
(else
(error “Unknown expression type – EVAL” exp))))

2）apply的代码如下：
apply的本质就是将lambda和参数组装在一起
(define (apply procedure arguments)
(cond
((primitive-procedure? procedure)
(apply-primitive-procedure procedure arguments))
((compound-procedure? procedure)
(eval-sequence
(procedure-body procedure)
(extend-environment
(procedure-parameters procedure)
arguments
(procedure-environment procedure))))
(else
(error
“Unknown procedure type – APPLY” procedure))))

3）procedure arguments
(define (list-of-values exps env)
(if (no-operands? exps)
’()
(cons (eval (first-operand exps) env)
(list-of-values (rest-operands exps) env))))

4）conditionals
(define (eval-if exp env)
(if (true? (eval (if-predicate exp) env))
(eval (if-consequent exp) env)
(eval (if-alternative exp) env)))

5）sequences
The value returned is the value of the final expression.
(define (eval-sequence exps env)
(cond
((last-exp? exps) (eval (first-exp exps) env))
(else (eval (first-exp exps) env)
(eval-sequence (rest-exps exps) env))))

6）Assignments and definitions
(define (eval-assignment exp env)
(set-variable-value!
(assignment-variable exp)
(eval (assignment-value exp) env)
env)
‘ok)

;; definitions of variables are handled in a similar manner.
(define (eval-definition exp env)
(define-variable! (definition-variable exp)
(eval (definition-value exp) env)
env)
'ok)

3.HOW to representing expressions #

— Chapter 4.1.2 Representing Expressions
expression的表达，是有test来定义的，也就是说，是反着来的，先有test。不用先有构建语句，因为大多数expression不是构建出来的，而是用户输入的。
但是，如果是元编程，那么就需要expression的构建操作符了。

1）self-evaluating items are numbers and strings
(define (self-evaluating? exp)
(cond ((number? exp) true)
((string? exp) true)
(else false)))

2）variables are represented by symbols:
(define (variable? exp) (symbol? exp))

3）Quotations have the form (quote )
(define (quoted? exp)
(tagged-list? exp 'quote))

(define (text-of-quotation exp) (cadr exp))

(define (tagged-list? exp tag)
(if (pair? exp)
(eq? (car exp) tag)
false))

4）Assignments have the form (set! )
(define (assignment? exp)
(tagged-list? exp 'set!))

(define (assignment-variable exp) (cadr exp))

(define (assignment-value exp) (caddr exp))

5）Definitions have the form
(define )
;; or the form
(define ( ... )
)

;; the latter form (standard procedure definition) is syntactic sugar for
(define
(lambda ( ... )
))

(define (definition? exp)
(tagged-list? exp 'define))

(define (definition-variable exp)
(if (symbol? (cadr exp))
(cadr exp)
(caadr exp)))

(define (definition-value exp)
(if (symbol? (cadr exp))
(caddr exp)
(make-lambda
(cdadr exp) ;formal parameters
(cddr exp)))) ;body

6）Lambda expressions are lists that begin with the symbol lambda:
(define (lambda? exp) (tagged-list? exp 'lambda))

(define (lambda-parameters exp) (cadr exp))

(define (lambda-body exp) (cddr exp))

;;constructor for lambda expression:
(define (make-lambda parameters body)
(cons 'lambda (cons parameters body)))

7）conditionals begin with if
(define (if? exp) (tagged-list? exp 'if))

(define (if-predicate exp) (cadr exp))

(define (if-consequent exp) (caddr exp))

(define (if-alternative exp)
(if (not (null? (cdddr exp)))
(cadddr exp)
'false))

;; constructor for if expressions
(define (make-if predicate consequent alternative)
(list 'if predicate consequent alternative))

8）Begin
(define (begin? exp) (tagged-list? exp 'begin))

(define (begin-actions exp) (cdr exp))

(define (last-exp? seq) (null? (cdr seq)))

(define (first-exp seq) (car seq))

(define (rest-exps seq) (cdr seq))

;; constructor sequence->exp (for use by cond->if)
(define (sequence->exp seq)
(cond
((null? seq) seq)
((last-exp? seq) (first-exp seq))
(else (make-begin seq))))

(define (make-begin seq) (cons 'begin seq))

9）application
(define (application? exp) (pair? exp))

(define (operator exp) (car exp))

(define (operands exp) (cdr exp))

(define (no-operands? ops) (null? ops))

(define (first-operand ops) (car ops))

(define (rest-operands ops) (cdr ops))

Derived expressions
衍生的expressions,解决的思路类似于Data类型的强制转换。
(cond ((> x 0) x)
((= x 0) (display 'zero) 0)
(else (- x)))

;; 强制转换成如下
（if（> x 0)
x
(if (= x 0)
(begin (display 'zero)
0)
(- x)))
转换cond->if
(define (cond? exp) (tagged-list? exp 'cond))

(define (cond-clauses exp) (cdr exp))

(define (cond-else-clause? clause)
(eq? (cond-predicate clause) 'else))

(define (cond-predicate clause) (car clause))

(define (cond-actions clause) (cdr clause))

(define (cond->if exp)
(expand-clauses (cond-clauses exp)))

(define (expand-clauses clauses)
(if (null? clauses)
'false
(let ((first (car clauses))
(rest (cdr clauses)))
(if (cond-else-clause? first)
(if (null? rest)
(sequence->exp (cond-actions first))
(error "ELSE clause isn't last -- COND->IF" clauses))
(make-if (cond-predicate first)
(sequence->exp (cond-actions first))
(expand-clauses rest))))))

4.HOW to evaluator Data Structures #

— Chapter 4.1.3 Evaluator Data Structures

1）Testing of predicates
(define (true? x)
(not (eq? x false)))

(define (false? x)
(eq? x false))

2）Representing procedures
Procedure as Data
Data as Procedure
(define (make-procedure parameters body env)
(list 'procedure parameters body env))

(define (compound-procedure? p)
(tagged-list? p 'procedure))

(define (procedure-parameters p) (cadr p))

(define (procedure-body p) (caddr p))

(define (procedure-environment p) (cadddr p))

3）Operations on Environments
我们操纵environments的procedures如下
(lookup-variable-value )

(extend-environment )

(define-variable! )

(set-variable-value! )
对environment的具体实现：
(define (enclosing-environment env) (cdr env))

(define (first-frame env) (car env))

(define the-empty-environment '())
frame的实现
(define (make-frame variables values)
(cons variables values))

(define (frame-variables frame) (car (frame))

(define (frame-values frame) (cdr frame))

(define (add-binding-to-frame! var val frame)
(set-car! frame (cons var (car frame)))
(set-cdr! frame (cons val (cdr frame))))

(define (extend-environment vars vals base-env)
(if (= (length vars) (length vals))
(cons (make-frame vars vals) base-env)
(if (< (length vars) (length vals))
(error "Too many arguments supplied" vars vals)
(error "Too few arguments supplied" vars vals))))

(define (lookup-variable-value var env)
(define (env-loop env)
(define (scan vars vals)
(cond
((null? vars)
(env-loop (enclosing-environment env)))
((eq? var (car vars))
(car vals))
(else (scan (cdr vars) (cdr vals)))))
(if (eq? env the-empty-environment)
(error "Unbound variable" var)
(let ((frame (first-frame env)))
(scan (frame-variables frame)
(frame-values frame)))))
(env-loop env))

(define (set-variable-value! var val env)
(define (env-loop env)
(define (scan vars vals)
(cond ((null? vars)
(env-loop (enclosing-environment env))
((eq? var (car vars))
(set-car! vals val))
(else (scan (cdr vars) (cdr vals)))))
(if (eq? env the-empty-environment)
(error "Unbound variable -- SET!" var)
(let ((frame (first-frame env)))
(scan (frame-variables frame)
(frame-values frame)))))
(env-loop env))

(define (define-variable! var val env)
(let ((frame (first-frame env)))
(define (scan vars vals)
(cond
((null? vars)
(add-binding-to-frame! var val frame))
((eq? var (car vars))
(set-car! vals val))
(else (scan (cdr vars) (cdr vals)))))
(scan (frame-variables frame)
(frame-values frame))))

5.HOW to run the evaluator #

— Chapter 4.1.4 Running the Evaluator as a Program
1）最后的闭合，需要运行之前构建的evaluator
2）evaluator本质上就是一个程序，只要构建一个无限循环的程序，监听用户的输入即可。输入的data当作expression输入给evaluator
3）启动evaluator之前，要构建一些初始data

1.构建初始的environment #

(define (setup-environment)
(let ((initial-env
(extend-environment
(primitive-procedure-names)
(primitive-procedure-objects)
the-empty-environment)))
(define-variable! 'true true initial-env)
(define-variable! 'false false initial-env)
initial-env))

(define the-global-environment (setup-environment))

2.构建primitive procedure #

(define (primitive-procedure? proc)
(tagged-list? proc 'primitive))

(define (primitive-implementation proc) (cadr proc))

(define primitive-procedures
(list
(list 'car car)
(list 'cdr cdr)
(list 'cons cons)
(list 'null? null?)

))

(define (primitive-procedure-names)
(map car
primitive-procedures))

(define (primitive-procedure-objects)
(map (lambda (proc) (list 'primitive (cadr proc)))
primitive-procedures))

(define (apply-primitive-procedure proc args)
(apply-in-underlying-scheme ;;这里借用原始lisp解释器的地方
(primitive-implementation proc) args))

3.启动常驻循环 #

(define input-prompt ";;; M-Eval input:")
(define output-prompt ";;; M-Eval value:")

(define (driver-loop)
(prompt-for-input input-prompt)
(let ((input (read)))
(let ((output (eval input the-global-environment)))
(announce-output output-prompt)
(user-print output)))
(driver-loop))

(define (prompt-for-input string)
(newline) (newline) (display string) (newline))

(define (announce-output string)
(newline) (display string) (newline))

(define (use-print object)
(if (compound-procedure? object)
(display (list
'compound-procedure
(procedure-parameters object)
(procedure-body object)
'))
(display object)))

(define the-global-environment (setup-environment))

(driver-loop)

;;; M-Eval input:
(define (append x y)
(if (null? x)
y
(cons (car x)
(append (cdr x) y))))
;;; M-Eval value:
ok

;;; M-Eval input;
(append '(a b c) '(d e f))
;;; M-Eval value:
(a b c d e f)

HOW - 举个例子，实际看一下eval/apply求值过程
对下面这段expression求值:
(eval
'(((lambda (x) (lambda (y) (+ x y))) 3) 4)

我们首先看到expression是一个字符串，因为解释器的参数是符号，字符串可以代表符号。
eval判断这个expression是一个application，所以调用apply
并将expression分解为operator和operand两部分
(apply
(eval '((lambda (x) (lambda (y) (+ x y))) 3) )
(list-of-values '(4)))
首先对operand求list-of-values
(apply
(eval '((lambda (x) (lambda (y) (+ x y))) 3) )
(cons (eval '4 env)
'()))

;; then
(apply
(eval '((lambda (x) (lambda (y) (+ x y))) 3) )
(cons 4 '()))

;; then
(apply
(eval '((lambda (x) (lambda (y) (+ x y))) 3) )
'(4))
然后，在对operator求值，我们发现operator还是一个application
(apply
(apply
(eval '(lambda (x) (lambda (y) (+ x y))) )
(list-of-values '(3))
'(4))
然后，对第二个list-of-values求值
(apply
(apply
(eval '(lambda (x) (lambda (y) (+ x y))) )
'(3))
'(4))
然后，对lambda expression求值，进入到make-procedure分支。
make-procedure就是构建一个list
(apply
(apply
(make-procedure
'(x)
'(lambda (y) (+ x y))
env)
'(3)
'(4))

;;then
(apply
(apply
('procedure '(x) '(lambda (y) (+ x y)) )
'(3)
'(4))
然后，开始对apply求值，将procedure转换成body，将procedure和env转换成env-1，本质上就是在构建继承的新环境
(apply
(eval
'(lambda (y) (+ x y))
(extend-environment
'(x)
'(3)
)
'(4))

;;then
(apply
(eval
'(lambda (y) (+ x y))
(cons (cons '(x) '(3)) )
'(4))

;;then 我们用来代替(cons (cons '(x) '(3)) )
(apply
(eval
'(lambda (y) (+ x y))
)
'(4))

继续用eval对body求值,body还是个lambda，所以继续调用make-procedure
(apply
(make-procedure
'(y)
'(+ x y)
)
'(4))

;;then
(apply
('procedure '(y) '(+ x y) )
'(4))
然后，轮到apply了
(eval
'(+ x y)
(cons (cons '(y) '(4)) ))

;; then
(eval
'(+ x y)
)
接着，进入到eval求值表达式(+ x y),
(apply
(eval '+ )
(list-of-value '(x y) ))

;;then
(apply
(eval '+ )
(cons (eval 'x )
(eval 'y )))

(apply
(eval '+ )
'(3 4))

(apply + '(3 4))

(apply-primitive-rocedure + '(3 4))

7
可以看出，最后的求值body （+ x y)的时候，x y才去evn中寻找value。才进行真正的参数组装。

6.Why I design Data as Programs?我为什么要将Data等价成程序？ #

1）这是一种视角，思路
2）如果Data等价于programs，我们就有了统一视角，即，Data视角。
3）有了这样一个抽象的更高维度的统一视角，我们就可以打破思想的框架，来进行元编程等事情。
4）Lisp解释器就是一个处理Program的data处理器。
5）换一个角度，任何处理data的东西都可以看成是解释器。
6）所以，万物都是解释器。
7）解释器的精髓就是求值。求值的物理视角就是组装，就是beta-reduction
8）解释器就是Lambda演算的代码实现。Lambda演算就是业务规则。

7. 用解释器这个通用视角来定位计算机科学 #

1）终极目的是模拟真实/想象的世界
2）抽象这个目的到根上就是计算
3）Lambda演算是计算的解释器，或者说Lambda演算模拟了计算
4）Lisp是Lambda演算的改进，增加了语法糖，所以说Lisp语言是Lambda演算的等级物。
5）Lisp interpreter是lisp语言的解释器。
6）Lisp interpreter的载体具有两个版本，软件版本和硬件版本。软件版本即用lisp语言来描述lisp interpreter。硬件版本即用寄存器来描述lisp interpreter
7）寄存器机器，是lisp的解释器
8）继电器是寄存器的解释器
9）电磁效应是继电器的解释器。
10）总体来说，抽象到极致，计算—>Lambda演算—>寄存器机器—>电磁效应
11）如果可以发现一种更加接近Lambda演算模型的物理材料，例如叫做盒子效应。那么计算机科学就可以如此定位：计算—>Lambda演算—>盒子效应。
12）计算是对世界的本质进行的抽象/模拟。用软件来模拟硬件，结果最后变成了由继电器来模拟计算，即，用硬件来模拟软件。所以，这是一个无始无终的循环：硬件软件的彼此模拟。
13）我们日常工作中，干的事情，用解释器的视角来看，一个业务存在，对业务的建模就是对业务的抽象，然后对抽象的解释器，就是用底层语言进行构建解释器的过程。所以，构建解释器，就是编程，即包含构建（strucutre）又包含解释（Iterpretation）所以编程的本质就是构建与解释，这也是SICP这本书的书名所揭示的核心。

8.通过构建解释器来构建不同的业务需求 #

1）An Interpreter with Lazy Evaluation,通过改变解释器来实现Lazy的业务
2）Nondeterministic Computing，通过改变解释器来实现多种分支的计算
3）Logic Programming Language，通过改变解释器来实现Logic语言，也即是SQL语言的源头。