List [CTL]
Scheme的特点
语法简洁统一
语法采用S-expression，所有语法元素都是广义表
数字运算使用前缀表达式，这样就可以把所有的运算符当作函数，也就可以消除运算符这个概念
整体的语法简洁统一，不举例了，详见rnrs
面向求值
语句都有返回值（语句而不是函数），函数返回值为最后一条语句计算的值
(define foo (if #t 1 2))
递归
无for, while等循环语句，用递归替代循环。rnrs要求必需实现严格尾递归优化，所以只要代码写的没问题一般不会出现OOM
习惯用named-let实现循环
(let loop ((lst lst))
(if (null? lst)
'end
(let ((ele (car lst)))
(printf "~s\n" ele)
(loop (cdr lst)))))
双范式
Scheme并不像传统函数式语言一样只有函数式数据结构，它还提供了set!
包括record类型可以声明可变字段
(define-record-type foo (fields (mutable x)))
(define f (make-foo 1))
(foo-x-set! f 2)
还有显得完全乱入的hashtable，list, vector等其它复合类型实现不了下面的例子
(define h (make-eq-hashtable))
(define lst `(,h))
(hashtable-set! (car lst) 'k 'v)
(eq? (hashtable-ref h 'k 'null)
(hashtable-ref h 'k 'null))
语法并不是绝对统一
语法中有一个元素叫form
(case 1
(1 '1))
(case 1
((1) '1))
(define fn (lambda () 1))
(case 1
(fn '1))
(case 1
((fn) '1))
(case 1
(((fn)) '1))
歧义出现了
又或者说cond的语法（我个人更愿意用cond代替if）：
(if 1
(begin
(display 1)
(display 2))
(begin
(display 3)
(display 4)))
(cond
((= 1 1) (display 1)
(display 2))
(else (display 1)
(display 2)))
看到了吗，因为if的语法限制导致多条语句中必须使用begin，而不能直接((display 1) (display 2))，如果这样写实际的求值顺序也是UB：
> (if #t ((display 1) (display 2)) 'F)
21
而在cond里，每一个condition的body中都可以添加随意数量的语句，所以在保持语法统一上，cond更优。但实际上某些Scheme实现里会用if来实现cond
Metaprogramming & S-expression
Scheme中代码与数据都是S-expression
(define code '(display 1))
(eval code)
得益于语法的统一，代码数据没有绝对的界限
Continuation
中文译为延续，解释为：
During the evaluation of a Scheme expression, the implementation must keep track of two things: (1) what to evaluate and (2) what to do with the value. … We call “what to do with the value” the continuation of a computation.
continuation涉及到CPS(Continuation-Passing-Style)风格，此处不详细介绍
说白了，就是将evaluation时的环境和后续计算打包保存下来
(* 3 (call/cc
(lambda (k)
(k 2))))
continuation可以实现generator，也就是像Python中yield的语法，进而实现coroutine
假如说要用pure C实现，是不可能的。因为C语言中函数返回控制权只能是return后，也就意味着函数栈帧销毁了。所以想实现只能在汇编层面，将局部变量以及执行位置存入寄存器。ucontext.h和longjmp/setjmp就是这样实现的
在Scheme中，得益于continuation是个一级对象，可以利用它来实现coroutine
;; http://deathking.github.io/yast-cn/contents/chapter16.html
;; abbreviation
(define call/cc call-with-current-continuation)
;; queue
(define (make-queue)
(cons '() '()))
(define (enqueue! queue obj)
(let ((lobj (list obj)))
(if (null? (car queue))
(begin
(set-car! queue lobj)
(set-cdr! queue lobj))
(begin
(set-cdr! (cdr queue) lobj)
(set-cdr! queue lobj)))
(car queue)))
(define (dequeue! queue)
(let ((obj (car (car queue))))
(set-car! queue (cdr (car queue)))
obj))
;; coroutine
(define process-queue (make-queue))
(define (coroutine thunk)
(enqueue! process-queue thunk))
(define (start)
((dequeue! process-queue)))
(define (pause)
(call/cc
(lambda (k)
(coroutine (lambda () (k #f)))
(start))))
;; example
(coroutine (lambda ()
(let loop ((i 0))
(if (< i 10)
(begin
(display (1+ i))
(display " ")
(pause)
(loop (1+ i)))))))
(coroutine (lambda ()
(let loop ((i 0))
(if (< i 10)
(begin
(display (integer->char (+ i 97)))
(display " ")
(pause)
(loop (1+ i)))))))
(newline)
(start)
Hygienic Macro
译为卫生宏，与C中不卫生的宏不同，卫生宏展开时不会污染命名空间，即变量捕获是没有问题的；而不卫生宏就是一个简单的文本替换
#define MACRO(foo) do { \
int bar = 1; \
printf("%d", foo * bar); \
} while(0)
int main() {
int foo = 2;
int bar = 3;
MACRO((bar + 1));
}
(define-syntax macro
(syntax-rules ()
((_ foo)
(let ((bar 1))
(display (* foo bar))))))
(define foo 2)
(define bar 3)
(macro (+ bar 1))
输出分别为2和4，虽然Scheme的宏也是在编译器展开，及展开时不涉及求值，但(macro (+ bar 1))中bar的定义来源于调用处的scope
Scheme不适合工程开发
无拿得出手的开发工具
我用vsc插件vscode-chez v0.1.2，功能基本只有一些常见结构的snippets，诸如格式化，定义跳转都没有，连高亮也是个残次品（字符串中的注释符都被识别为注释）
Scheme的S-expression解析起来很方便，但还是没有人做开发工具，也从侧面印证了生态不行
生态差
不说了，什么轮子都自己造。当然，调用C语言的链接库还是挺方便的，所以很多Scheme库都是仅用Scheme做上层接口
针对这一点，Lisp方言中Clojure应该是最好的选择，CL也会优于Scheme
动态类型
不多说，动态类型的通病
代码难以用肉眼parse
))))))))))))))))))))))))))))))))))))))
ChezScheme debug反人类
chezscheme是一个神一样的编译器，编译速度和编译生成的代码速度都很快，脚本语言中无压力吊打lua。王垠说能媲美C，这点当然用脚趾头想都知道真假
快是它的优点，但是，…，它编译后代码中所有的runtime exception都没有行号，也就意味着写完了代码，运行后报错，但它不告诉你是哪一行，又没有合适的debugger，所以就得在程序的执行流中print，
如何写解释器
吐槽完了，说说如何写解释器吧
目标是使用Scheme完成一个类C语言的解释器，特性是：
- 动态语言
- 强类型
- lexical scoping
- with class
repo地址是https://github.com/EddieIvan01/yakult
由于2020年新型肺炎，在家为消磨时间开了坑，之后发现工作量太大，写起来心累，于是👴果断决定暂弃坑
Lexer => Parser => Interpreter
Lexer其实很简单，就是一个简单的分词器，去掉空格注释换行之类的，将源码解析为token流即可，一个有限状态机即可搞定（或者用regexp来做也可以，但会做不必要的回溯损失性能）
我在解析时维护一个pointer来递归，这样就可以方便的任意移动。而如果用car/cdr来做递归的话，就比较麻烦了
yakult里的分词阶段把所有的特殊符号归类到token::symbol中了，其实这里可以做更细粒度的划分，比如划分token::paren-open / token::paren-close等等，但这里不做留到paser里判断也是可以的
它的输入输出是这样的：
(import (lexer))
(define code "let a = 2 * (1 + 3)")
(printf "~s" (scan code))
OUTPUT:
(#[#{token::keyword ettq95xxtz6ic726sbbnaqs44-7} let] #[#{token::ident ettq95xxtz6ic726sbbnaqs44-8} a] #[#{token::symbol ettq95xxtz6ic726sbbnaqs44-9} "="] #[#{token::number ettq95xxtz6ic726sbbnaqs44-10} 2] #[#{token::symbol ettq95xxtz6ic726sbbnaqs44-9} "*"] #[#{token::symbol ettq95xxtz6ic726sbbnaqs44-9} "("] #[#{token::number ettq95xxtz6ic726sbbnaqs44-10} 1] #[#{token::symbol ettq95xxtz6ic726sbbnaqs44-9} "+"] #[#{token::number ettq95xxtz6ic726sbbnaqs44-10} 3] #[#{token::symbol ettq95xxtz6ic726sbbnaqs44-9} ")"] #[#{token::endline ettq95xxtz6ic726sbbnaqs44-11}] #[#{token::eof ettq95xxtz6ic726sbbnaqs44-12}])
Parser负责解析Lexer的输出，也就是接受token流为输入，以endline为分割解析成AST，最后的输出是每条语句的AST
像这样：
(import (parse))
(import (lexer))
(import (ast))
(define code "let a = 2 * (1 + 3);")
(define t (scan code))
(define a (parse t))
(printf "~s" a)
OUTPUT:
(#[#{ast::define daqf9vsq5uvx5qezt929ps0q9-7} a (#[#{ast::* daqf9vsq5uvx5qezt929ps0q9-8} #[#{token::number daqf9vsq5uvx5qezt929ps0q9-9} 2] #[#{ast::+ daqf9vsq5uvx5qezt929ps0q9-10} #[#{token::number daqf9vsq5uvx5qezt929ps0q9-9} 1] #[#{token::number daqf9vsq5uvx5qezt929ps0q9-9} 3]]])])
这个其实也很简单，唯一的难点是需要设计好每一条分支，尽可能复用代码（前期我没有仔细斟酌，导致代码逻辑分支有冗余，不够完善）
Interpreter接受AST为输入，解释执行即可，解释执行的过程是重点，后面讲
Lexical scoping
lexical scoping相对于dynamic scoping，区别在于捕获自由变量时的行为
lexical scoping在函数调用时从函数定义处的scope获取变量，而dynamic scoping则从函数的调用栈往上捕获变量
A = 1
func foo() {
print A
}
func bar() {
A = 5
foo()
}
当调用bar时，lexical scoping会输出1，而dynamic scoping会输出5
为了实现lexical scoping，需要将函数定义处的环境保存在函数对象里，也就是closure，而函数调用时的自由变量，应当从当前函数的闭包中获取
当扩展环境形成新作用域时只需要从旧作用域扩展即可，而一个环境只会扩展自一个环境，所以所有环境其实可以表示为一个树形结构
GLOBAL-ENV
/ \
ENV-0 ENV-1
/
ENV-2
而针对这棵树的查询操作只会从叶向根，所以只需要用一个列表保存所有的节点，每个节点中保存父节点的索引即可
env.ss中定义了env的相关操作
(define-record-type env (fields vars ref))
(define-syntax new-env
(syntax-rules ()
((_ all-env)
(define env (make-env (make-eq-hashtable) 'null))
(set! all-env (append all-env `(,env)))
env)))
(define-syntax ext-env
(syntax-rules ()
((_ ref-env all-env)
(define env (make-env (make-eq-hashtable) ref))
(set! all-env (append all-env `(,env))))))
(define-syntax env-set!
(syntax-rules ()
((_ env-index name val all-env)
(let ((value (hashtable-ref
(env-vars
(list-ref all-env env-index))
name 'null)))
(cond
((eq? value 'null)
(let ((ref (env-ref (list-ref all-env env-index))))
(cond
((eq? 'null ref) (halt "Undefined"))
(else (let loop ((env (list-ref all-env ref)))
(define h (env-vars env))
(define value (hashtable-ref h name 'null))
(case value
('null (loop (list-ref all-env (env-ref env))))
(else
(hashtable-set! h name val))))))))
(else (hashtable-set!
(env-vars
(list-ref all-env env-index)
name val))))))))
(define env-lookup
(lambda (env-index name all-env)
(define env (list-ref all-env env-index))
(let ((value (hashtable-ref
(env-vars env)
name 'null)))
(cond
((eq? value 'null)
(let ((ref (env-ref env)))
(cond
((eq? 'null ref) 'null)
(else (env-lookup ref name all-env)))))
(else value)))))
这里的new-env, ext-env, env-set!为什么我要用宏而不是函数，我猜你肯定明白
immutable实现mutable的问题
为什么会有这个问题？假如只需要实现函数式数据结构（比如用Scheme实现Scheme），那么就不需要上一条里的三个宏了
正则序和应用序
虽然Scheme是个解释型语言，但它的宏也不可以递归
实际等同于编译期替换，即先扩展后求值。更佳的解释是宏是正则序，而函数是应用序
你可以试下下面这段代码，会无限展开
(define-syntax foo
(syntax-rules ()
((_ lst)
(if (null? lst)
'end
(begin
(printf "~s\n" (car lst))
(foo (cdr lst)))))))
(define lst '(1 2 3 4 5))
(foo lst)