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 声明语言类型
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.41
匿名函数,用法同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 9
let表达式,注意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>)