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 声明语言类型

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>)

  1. http://mitpress.mit.edu/sicp/ ↩︎
  2. http://davidlau.me/2015/05/11/notes-on-The-Free-Launch-Is-Over/ ↩︎
  3. http://www-formal.stanford.edu/jmc/recursive.html ↩︎
  4. http://en.wikipedia.org/wiki/Lisp_(programming_language) ↩︎
  5. http://c2.com/cgi/wiki?LispSchemeDifferences ↩︎

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 微信读书冷启动用户书籍推荐初探:一个借助微信用户画像的方法

    刘笑江
  • Activation

    刘笑江
  • 编程珠玑II C12笔记: rand num generator

    刘笑江
  • iOS开发中常用的宏

    剑行者
  • 如何构建更好的数据立方体系统(Cube)

    看到了kylin关于cube的设计,难以抑制的觉得这部分设计得太巧妙了,确实比我们的产品要好上很多,不得不学习一下!!!

    麒思妙想
  • 「基础编程学习」 「PHP7数组详解」:第1章 (6)循环结构

    循环,这个太常用了。我们为什么使用计算机,而不是手动一个一个处理,就是因为计算机善于处理循环的结构。把最枯燥的部分,扔给机器,它喜欢这样。

    程序员小助手
  • Spark内部原理

    Spark中的Shuffle、宽依赖窄依赖、RDD持久化、共享变量

    俺也想起舞
  • 微服务的灾难(3) -- 拆分

    在之前写事故驱动开发的时候,提到过,在企业中的项目进行开发时,只要是自己方便,一个人可以用拆分和收敛同时作为自己的标准。所以大家都是双标狗。

    iTesting
  • 浅谈MSF渗透测试

    在渗透过程中,MSF漏洞利用神器是不可或缺的。更何况它是一个免费的、可下载的框架,通过它可以很容易地获取、开发并对计算机软件漏洞实施攻击。它本身附带数百个已知软...

    FB客服
  • 浅谈MSF渗透测试

    在渗透过程中,MSF漏洞利用神器是不可或缺的。更何况它是一个免费的、可下载的框架,通过它可以很容易地获取、开发并对计算机软件漏洞实施攻击。它本身附带数百个已知软...

    小老鼠

扫码关注云+社区

领取腾讯云代金券