λ演算
https://en.wikipedia.org/wiki/Lambda_calculus
'x
(lambda (x) x)
((lambda (x) x) 'y)
match (模式匹配)
这种感觉，更详细的自行看文档。
(define (lambda->lumbda x)
(match x
[a #:when (symbol? a) a]
[`(lambda (,x) ,body) `(lumbda (,x) ,(lambda->lumbda body))]
[`(,rator ,rand) `(,(lambda->lumbda rator)
,(lambda->lumbda rand))]))
关于quote和quasiquote
https://docs.racket-lang.org/guide/quote.html?q=quote
https://docs.racket-lang.org/guide/qq.html?q=quote
helper function
我们都知道编程要搞helper function，这样方便维护，方便理清程序脉络。
可是真正实践起来就很难知道把哪一部分当成helper了，结果就是spaghetti code。
这个作业里也是一样。前面要实现的函数是后面一些函数的helper，可是怎么去用 helper 就是难点了。需要开动脑筋，还要意识到已经实现的东西很可能能当成helper使用。这就是所谓的灵感吧。
作业这样已经很仁慈了，一般第N题是个helper，第N+1题就用到那个helper。自己写东西面对一张白纸的时候就很难找到那么完美的helper了。
感觉规律就是越是一般、general 的东西越容易当作helper使用。比如集合运算啊，封装好的数据结构啊，数学库之类的。
还有一种就是先写个很长很乱的实现。然后强行把其中一些段落抽出来当作helper，这种只是为了方便替换某一部分的实现而已。
(后面的作业做了很多这类工作。)
Free and Bound
free variable ,自由变量，（我觉着就是未定义变量。。。）
Bound variable, 被某个 lambda 绑定着的变量。
我的理解
在λ演算里，所有变量都是靠 λ 引入的。
一个变量要么是free的，要么是bound的。
（这次作业有个题叫找到所有既是free又是bound的符号。但那只是不同变量名字一样而已。）
> (unique-free-vars 'x)
(x)
> (unique-free-vars '(lambda (x) (x y)))
(y)
> (unique-free-vars '((lambda (x) ((x y) e)) (lambda (c) (x (lambda (x) (x (e c)))))))
(y e x)
> (unique-bound-vars 'x)
()
> (unique-bound-vars '(lambda (x) y))
()
> (unique-bound-vars '(lambda (x) (x y)))
(x)
> (unique-bound-vars '((lambda (x) ((x y) e)) (lambda (c) (x (lambda (x) (x (e c)))))))
(x c)
> (unique-bound-vars '(lambda (y) y))
(y)
> (unique-bound-vars '(lambda (x) (y z)))
()
De Bruijn index
https://en.wikipedia.org/wiki/De_Bruijn_index
对应作业的第13题
> (lex '(lambda (x) x) '())
(lambda (var 0))
> (lex '(lambda (y) (lambda (x) y)) '())
(lambda (lambda (var 1)))
> (lex '(lambda (y) (lambda (x) (x y))) '())
(lambda (lambda ((var 0) (var 1))))
> (lex '(lambda (x) (lambda (x) (x x))) '())
(lambda (lambda ((var 0) (var 0))))
> (lex '(lambda (y) ((lambda (x) (x y)) (lambda (c) (lambda (d) (y c))))) '())
(lambda ((lambda ((var 0) (var 1))) (lambda (lambda ((var 2) (var 1))))))
意思就是说，我根本没必要给 λ abstraction 里的变量起名字，用数数代替就行了。也就是index，
0代表离我这个bound variable是离我最近的λ引入的
1代表 是离我最近的λ外面那个λ 引入的。
以此类推。
(wiki上从1开始数，这里从0开始数)
( 厚颜无耻的贴个自己的实现。。。
(define (lex s acc)
(match s
[v #:when (symbol? v) `(var ,(index-of acc v))]
[`(lambda (,x) ,body) #:when (symbol? x) `(lambda ,(lex body (cons x acc)))]
[`(,rator ,rand) `(,(lex rator acc) ,(lex rand acc))]))
这里有个 undefined behavior，就是对 free variable 应该给个什么 index ，这个实现会直接给个 #f ，这个是 index-of 的行为。
一般程序越短，用的别人的helper越多，undefined/unexpected behavior 就越多。
考虑了越多 corner case ， 按理说程序应该更可靠，更清晰。但是篇幅会变长，源程序可读性下降。但是程序的行为可读性上升。
)
闲聊/扯淡/乞讨
C311前两次作业只是热身而已，让你熟悉一下写递归程序、match、s-exp。
第三次~第九次作业讲了实现一个解释器的方方面面。
naive版，
dynamic scoping版。
不同传参数方法。（call by value,call by reference,call by name,lazy evaluation），
然后是怎么做到不同实现可替换。（environment，closure，continuation）
然后介绍了怎么把解释器写成continuation passing style，
乃至可以被工具转成C代码的版本。
照例吐槽找不到工作啊。。。我到底想干啥呢，开发，产品经理还是游戏策划？
（有公司要就不错了，不好意思找家里要钱啊。。。T_T）
继续厚颜无耻贴自己的答案(我从未见过，有如此，厚颜无耻之人 -_-)
https://github.com/hgztheyoung/c311/blob/master/c311recap/a2.rkt
乞讨
我 hgz92929@sina.com 数额随意。
7块可以吃个鸡腿饭。 -_-
转载本文请附带乞讨链接
