社区首页 >专栏 >SCIP学习笔记

SCIP学习笔记

刘笑江

发布于 2018-05-28 05:42:29

1.7K00

代码可运行

文章被收录于专栏：刘笑江的专栏刘笑江的专栏

运行总次数：0

代码可运行

引言

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基本语法

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

Lambda构造过程

匿名函数，用法同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>)