SCIP学习笔记
引言
SCIP(Structure and Interpretation of Computer Programs)[1]是MIT自1984年起的编程入门教程，尽管最近他们用Python的课程取代了Lisp语言，但是随着工业界越来越多的应用函数编程语言，如Clojure、Scala、Racket，以及软件开发使用并发的趋势(见文章[2]），重读SCIP是很有意义的。
SCIP分五章：构造过程抽象，构造数据抽象，模块化、对象和状态（涉及并发），源语言抽象，寄存器机器里的计算（编译器如何工作）
环境
OS X下使用IDE DrRacket及其语法插件#PLaneT neil sicp.plt
在文件头使用 #lang planet neil/sicp 声明语言类型
DrRacket Screen Shot
Lisp基本语法
Lisp的原始定义在John McCarthy1960发表的论文[3]。
Lisp[4]是一个语言族，包括Common Lisp和Scheme，二者区别见[5]。
过程定义
(define (<name> <formal parameters>) <body>)
e.g.
(define (square x) (* x x))
(square 13) ; 169
```
### 代换模型
> 1. 正则序求值：完全展开后规约
>
> 2. 应用序求值：先求值参数而后应用，通过替换去模拟，避免重复求值 （Scheme使用）
### 条件表达式
``` scheme
(cond (<p1> <e1>)
(<p2> <e2>)
...
(<pn> <en>))
(cond (<p1> <e1>)
(else <e2>))
(if <predicate> <consequent> <alternative>)
e.g.
(define (abs x)
(cond ((> x 0) x)
((= x 0) 0)
((< x 0) (- x))))
```
### 谓词
``` scheme
((<|=|>) <e1> ... <en>)
(and <e1> ... <en>)
(or <e1> ... <en>)
(not <e1> ... <en>)以上是Scheme的主要语法，可以容易而优雅地生成语法树，没有语法糖。那么递归和迭代怎么用？使用上面的语法规则即可。
; 递归法求阶乘
(define (factotrial n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
; 迭代法求阶乘
(define (fact 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)))高阶函数
过程作为参数
# define ∑f(n), n∈[a,b]
; style 1
(define (sigma f a next b)
(if (> a b)
0
(+ (f a) (sigma f (next a) next b))))
; style 2
(define (sigma_ f a next b)
(define (iter a result)
(if (> a b)
0
(iter (next a) (+ result (f a)))))
(iter a 0))
; calc ∑sqrt(n), n∈[1,4]
(define (inc x) (+ x 1))
(sigma sqrt 1 inc 4) ; 3.41
(sigma sqrt_ 1 inc 4) ; 3.41Lambda构造过程
匿名函数，用法同Python
(lambda <formal-parameters> <body>)
(lambda <formal-parameters> <body> <values>)
e.g.
(define plus6 (lambda (x) (+ x 6))) ; returns a func
(lambda (x y) (+ x y) 4 5) ; return 9let表达式，注意var不是变量是常量，无副作用。
(let ( (<var1> <exp1>)
(<var2> <exp2>)
...
(<varn> <expn>))
<body>)
e.g.
(define (circle-len d)
(let ( (π 3.14)
(Ω 1))
(* d π)))工具函数
打印
(define (print x)
(newline)
(display x))
(print 3)
;
; 3以上是Lisp的主要语法规则，非常简练。
至此，SCIP第一章结束，其中有许多练习，余不一一。
构造数据抽象
闭包
（这里指的不是匿名函数）
是在处理符合数据中的一个关键思想：用于组合数据对象的粘合剂，不但能用于组合基本的数据对象，同样也可以用复合数据的对象。
其中，粘合剂指：程序设计语言应该提供的，把一些数据对象组合起来，形成更复杂的数据对象的操作。
Wiki: 闭包是引用了自由变量的函数
序对
用来粘合两个对象，用法：
(define x (cons 1 2))
(car x)
; 1
(cdr x)
; 2序对的一种定义：
(define (cons_ x y)
(define (dispatch m)
(cond ((= m 0) x)
((= m 1) y)
(else (error "ar not 0 or 1 -- CONS" m))))
dispatch)
(define (car_ z) (z 0))
(define (cdr_ z) (z 1))另一种定义：
(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)))
e.g.
(car__ (cons__ 33 99)) ;33
(cdr__ (cons__ 33 99)) ;99序列（列表）
可看做嵌套的序对：
(list <a1> <a1> ... <an> nil)
等价于
(cons <a1> (cons <a2> ... (cons <an> nil) ...))
表操作：
; list[0]
(car list)
; list[2:n]
(cdr list)
; list[2]
(car (cdr <list>))
(cadr <list>)
; list[n-1]
(list-ref <list> <n>)
; len(list)
(length <list>)
; list1.append(list2)
(append <list1> <list2>)
; Map
(map <list> <process>)
(reduce <list> <process>)
- http://mitpress.mit.edu/sicp/ ↩︎
- http://davidlau.me/2015/05/11/notes-on-The-Free-Launch-Is-Over/ ↩︎
- http://www-formal.stanford.edu/jmc/recursive.html ↩︎
- http://en.wikipedia.org/wiki/Lisp_(programming_language) ↩︎
- http://c2.com/cgi/wiki?LispSchemeDifferences ↩︎
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-05-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录