怎样写一个解释器(雾)

在lisp中大量使用的S-表达式具有'(+ 1 3)的形式，在python中以列表表示，即["+", 1, 3]，操作符放在最前面。

这个S-表达式就是我们解释器的输入

有了一个输入后要解析表达式，方便起见所有表达式都只有最多三个参数，而且除if外最多两个。实际上一个就行，在Haskell，F#等语言中只有一元函数，多元函数是通过Currying实现的。

所以只需要判断第一个元素，然后进行运算即可。
以["+", 1, 3]为例，我们发现第一个元素是"+"，”+”需要两个参数(这里忽略了一元+和错误处理)分别为1和3，所以进行运算1+3，得到结果4

完成了以上步骤的解释器只是一个普通的计算器，下面我们给它加上”变”量。由于我们对环境的操作，这里的”变”量实际上是不可变的，但我们可以重复绑定。

“环境”由一个单向列表实现，每个表达式都有自己的环境，这使得我们自然的使用了静态作用域。新的变量绑定被添加到源环境的后边形成新环境。由于每个表达式都会先从最内层的作用域开始查找变量，自然的实现了变量的遮蔽。

另外由于实现了变量，而函数也是变量(lambda表达式)，所以函数也是可用的了。

但是我们的语言只能顺序执行，下面添加一个条件判断。

加入条件判断其实很简单，在解析的基础上加上判断表达式if即可。

原文没有条件判断，if是我诌的……不要加上if以后大概就是图灵完备的了233

原文的效果为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

(r2 '(+ 1 2))
;; => 3
(r2 '(* 2 3))
;; => 6
(r2 '(* 2 (+ 3 4)))
;; => 14
(r2 '(* (+ 1 2) (+ 3 4)))
;; => 21
(r2 '((lambda (x) (* 2 x)) 3))
;; => 6
(r2
'(let ([x 2])
   (let ([f (lambda (y) (* x y))])
     (f 3))))
;; => 6
(r2
'(let ([x 2])
   (let ([f (lambda (y) (* x y))])
     (let ([x 4])
       (f 3)))))
;; => 6

我做出来是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

print(lisp(["+", 1, 2]))
print(lisp(["*", 2, 3]))
# -> 6
print(lisp([["λ", "x", ["*", "x", 3]], 3]))
# -> 9
print(lisp(["λ", "x", ["*", "x", 3]]))
# -> Closure{x:x, exp:["*", "x", "3"], env:[]}
print(lisp(
["let",
    ["x", 2],
    ["let",
        ["f", ["λ", "y", ["*", "x", "y"]]],
        ["f", 3]]]
))
# => 6
print(lisp(["let", ["f", ["λ", "x", ["*", "x", 2]]], ["f", 4]]))
# => 8
print(lisp(
["let",
    ["x", 2],
    ["let",
        ["f",
            ["λ", "y", ["*", "x", "y"]]],
        ["let",
            ["x", 4],
            ["f", 3]]]]
))
# => 6

嗯，自我感觉还算可以😂