The Scheme Programming Language 读书笔记，chapter 3.
Chapter 3. Going Further
Section 3.1. Syntactic Extension
前面提到，scheme有核心语法和扩展语法。后者可以展开变成前者。核心语法应该覆盖多大范围是一个有争议的问题。
下面描述了scheme的最简单的核心语法：
<program> --> <form>*
<form> --> <definition> | <expression>
<definition> --> <variable definiotion> | (begin <definition>*)
<variable definition> --> (define <variable> <expression>)
<expression> --> <constant>
| <variable>
| (quote <datum>)
| (lambda <formals> <expression> <expression>*)
| (if <expression> <expression> <expressION>)
| (set! <variable> <expression>)
| <application>
<constant> --> <boolean> | <number> | <character> | <string>
<formals> --> <variable>
| (<variable>*)
| (<variable> <variable>* . <variable>)
<application> --> (<expression> <expression>*)
上述语法具有二义性，因为<application>跟其他语法冲突。
语法扩展使用define-syntax定义。下面是let的例子：
(define-syntax let
(syntax-rules () ; 这个连对用来指定额外的关键字，默认为空，非空的例子为cond的else
[(_ ((x e) ...) b1 b2 ...) ; 模式
((lambda (x ...) b1 b2 ...) e ...) ; 模板
])
上述除了下划线和省略号之外的标识符，除非是指定为关键字，否则就是模式变量。像pat ...这种记述方式表示pat可以匹配零至多个表达式。像expr ...这种记述方式表示可以输出零至多个表达式。在let的语法扩展定义中出现了b1 b2 ...，这表明至少需要一个形式的输入。然后需要住的的是模式中的(x e) ...在模板中拆开成了x ...以及e ....。另外模式中的pat ...到了模板中也必须带有省略号。
下面是语法扩展and的定义：
(define-syntax and
(syntax-rules ()
[(_) #t]
[(_ e) e]
[(_ e1 e2 e3 ...) (if e1 (and e2 e3 ...) #f)]))
可以看到语法扩展是可以递归调用自己的。
注意，下面的简化版是错误的：
(define-syntax and ; incorrect!
(syntax-rules ()
[(_) #t]
[(_ e1 e2 ...)
(if e1 (and e2 ...) #f)]))
or语法扩展的定义如下：
(define-syntax or
(syntax-rules ()
[(_) #f]
[(_ e) e]
[(_ e1 e2 e3 ...)
(let ([t e1])
(if t t (or e2 e3 ...)))]))
同样，下面or的简化版是错误的：
(define-syntax or ; incorrect!
(syntax-rules ()
[(_) #f]
[(_ e1 e2 ...)
(let ([t e1])
(if t t (or e2 ...)))]))
Section 3.2. More Recursion
let绑定的变量，在变量的求值中不可见。所以下面的递归是错误的：
(let ([sum (lambda (ls)
(if (null? ls)
0
(+ (car ls) (sum (cdr ls)))))])
(sum '(1 2 3 4 5)))
一个变通的办法是让sum接收自己作为参数。但是scheme提供了另一个更简单的办法，那就是使用letrec：
(letrec ([sum (lambda (ls)
(if (null? ls)
0
(+ (car ls) (sum (cdr ls)))))])
letrec的一个限制是，每个expr求值的时候不借助与var…的值。所以大部分时候，letrec要绑定的是lambda。下面的例子是不行的：
(letrec ([y (+ x 2)]
[x 1])
y)
显示的错误是：
Exception: attempt to reference undefined variable x
let的另外一种语法格式，运行定义一个额外的名字，这个名字在绑定的变量的求值过程中可见：
(let name ((var expr) ...)
body1 body2 ...)
上面的let叫做俱名let，等价于：
((letrec ((name (lambda (var ...) body1 body2 ...)))
name)
expr ...)
或者也可以写成：
(letrec ((name (lambda (var ...) body1 body2 ...)))
(name expr ...))
scheme中的尾递归会被转化为jump语句。如何判断一个函数调用是不是尾递归呢？就是当某个函数调用返回之后，没有其他语句需要执行了，那就就可以对这个函数调用进行尾递归转化。一些其他例子，if语法形式的consequent或者alternative部分；and或者or表达式的最后一个子表达式；let或者letrec的最后一个表达式。
下面这个版本的factorial不是尾递归版本：
(define factorial
(lambda (n)
(let fact ([i n])
(if (= i 0)
1
(* i (fact (- i 1)))))))
下面这个版本的factorial是尾递归版本，它使用了变量a作为累加器：
(define factorial
(lambda (n)
(let fact ([i n] [a 1])
(if (= i 0)
a
(fact (- i 1) (* a i))))))
对于斐波那契数列，下列的版本是非尾递归的：
(define fibonacci
(lambda (n)
(let fib ([i n])
(cond
[(= i 0) 0]
[(= i 1) 1]
[else (+ (fib (- i 1)) (fib (- i 2)))]))))
下列版本是尾递归的：
(define fibonacci
(lambda (n)
(if (= n 0)
0
(let fib ([i n] [a1 1] (a2 0))
(if (= i 1)
a1
(fib (- i 1) (+ a1 a2) a1))))))
基本上尾递归的版本都需要使用额外的变量，避免函数调用以后需要对齐返回值做额外的操作。
练习略过。
Section 3.3. Continuations
对表达式求值的时候，要记录两个点：1）求值的对象；2）求值的操作。求值的操作可以算作continuation of computation。所以对于求值的每个时刻，都有某个待完成的求值操作。
对于表达式(if (null? x) (quote ()) (cdr x))，可以抽离出六个表达式：
(if (null? x) (quote ()) (cdr x))的总体值(null? x)的值null?的值x的值cdr的值x的值
scheme允许使用call/cc来捕捉continuation。call/cc接受一个只有单个形参的执行诀。call/cc会把捕捉到的当前的continuation作为参数传给这个执行诀，这个传入的continuation是另一个可以被调用的执行诀。当传入的执行诀被调用的时候，需要提供一个值，然后那个值就变成了传入的continuation的调用值。
下面的例子的返回结果是6：
(+ 2 (call/cc
(lambda (k)
(* 5 (k 4)))))
感觉有点像C语言中的return，但是和C语言不同，scheme中return以后的continuation依然能保持
(let ([x (call/cc (lambda (k) k))])
(x (lambda (ignore) "hi")))
上面的continuation首先绑定到了x，然后通过参数(lambda (ignore) "hi")来调用x，恢复continuation的执行。
(((call/cc (lambda (k) k)) (lambda (x) x)) "HEY!")
上面的表达式返回“HEY！”。
所以continuation更像是一个可以恢复执行的断点。它的用途之一是用来实现多任务。书中给了一个"light weight process"的例子。
练习略。
Section 3.4. Continuation Passing Style
调用非尾递归的函数的时候，会隐式传入一个当前函数剩余部分的continuation，以及返回当前函数的continuation。
尾递归调用的时候则只需剩余部分的continuation。
看一个例子：
(letrec ([f (lambda (x) (cons 'a x))]
[g (lambda (x) (cons 'b (f x)))]
[h (lambda (x) (g (cons 'c x)))])
(cons 'd (h '())))
(d b a c)
可以把隐式的continuation传递改成显示的：
(letrec ([f (lambda (x k) (k (cons 'a x)))]
[g (lambda (x k)
(f x (lambda (v) (k (cons 'b v)))))]
[h (lambda (x k) (g (cons 'c x) k))])
(h '() (lambda (v) (cons 'd v))))
上面的这种手法叫做CPS（continuation passing style）。CPS比较复杂，但是允许给continuation传递多个结果给，因为实现continuation的执行诀可以带任意参数个数。采用call/cc的代码可以被改写成CPS样式，但是需要把程序全部改头换面。
练习略。
Section 3.5. Internal Definitions
define也可以出现在lambda，let内部，产生局部的定义。
(let ([x 3])
(define f (lambda (y) (+ y x)))
(f 4))
内部define的定义之间可以互相调用，就像letrec那样：
(let ()
(define even?
(lambda (x)
(or (= x 0)
(odd? (- x 1)))))
(define odd?
(lambda (x)
(and (not (= x 0))
(even? (- x 1)))))
(even? 20))
变量定义一定是从左到右执行，letrec中的绑定却可以按任意次序执行。但是可以使用letrec来保证变量定义从左到右求值，就像let那样。
顶层define和内部define可以联合起来，对代码进行组织，达到模块化效果。
练习略。
Section 3.6. Libraries
展示了一个库(grades)（是的，这个库的名字是带花括号的）。(grades)导出了一个变量gpa->grade以及一个关键字gpa。然后库的实现导入了(rnrs)这个标准库。
练习略。
（本篇完）