Peter Norvig 在他的個人網站上頭，寫了一篇 (How to Write a (Lisp) Interpreter (in Python))（註）， 他寫了約莫 100 行的 python script 來小小模擬一個簡化版的 Lisp Interpreter，看了不禁拍案叫絕。 下頭這個表格截取自他的網頁，指出他這 100 行的程式碼，所實作的 syntax 只有 9 個（註）。
-
var, variable reference
A symbol is interpreted as a variable name; its value is the variable’s value.
Example:x -
number, constant literal
A number evaluates to itself.
Examples:12or-3.45e+6 -
(quoteexp), quotationReturn the exp literally; do not evaluate it.
Example:(quote (a b c)) ⇒ (a b c) -
(iftest conseq alt), conditionalEvaluate test; if true, evaluate and return conseq; otherwise evaluate and return alt.
Example:(if (< 10 20) (+ 1 1) (+ 3 3)) ⇒ 2 -
(set!var exp), assignmentEvaluate exp and assign that value to var, which must have been previously defined (with a
defineor as a parameter to an enclosing procedure).
Example:(set! x2 (* x x)) -
(definevar exp), definitionDefine a new variable in the innermost environment and give it the value of evaluating the expression exp.
Examples:(define r 3)or(define square (lambda (x) (* x x))). -
(lambda (var…)exp), procedureCreate a procedure with parameter(s) named var… and the expression as the body.
Example:(lambda (r) (* 3.141592653 (* r r))) -
(beginexp…), sequencingEvaluate each of the expressions in left-to-right order, and return the final value.
Example:(begin (set! x 1) (set! x (+ x 1)) (* x 2)) ⇒ 4 -
(proc exp…), procedure callIf proc is anything other than one of the symbols
if, set!, define, lambda, begin,orquotethen it is treated as a procedure. It is evaluated using the same rules defined here. All the expressions are evaluated as well, and then the procedure is called with the list of expressions as arguments.
Example:(square 12) ⇒ 144
整個 interpreter 的核心：evaluator 只有如下的數行而已，實在很巧妙。
def eval(x, env=global_env):
"Evaluate an expression in an environment."
if isa(x, Symbol): # variable reference
return env.find(x)[x]
elif not isa(x, list): # constant literal
return x
elif x[0] == 'quote': # (quote exp)
(_, exp) = x
return exp
elif x[0] == 'if': # (if test conseq alt)
(_, test, conseq, alt) = x
return eval((conseq if eval(test, env) else alt), env)
elif x[0] == 'set!': # (set! var exp)
(_, var, exp) = x
env.find(var)[var] = eval(exp, env)
elif x[0] == 'define': # (define var exp)
(_, var, exp) = x
env[var] = eval(exp, env)
elif x[0] == 'lambda': # (lambda (var*) exp)
(_, vars, exp) = x
return lambda *args: eval(exp, Env(vars, args, env))
elif x[0] == 'begin': # (begin exp*)
for exp in x[1:]:
val = eval(exp, env)
return val
else: # (proc exp*)
exps = [eval(exp, env) for exp in x]
proc = exps.pop(0)
return proc(*exps)
測試方式：
- 下載程式碼。
- 執行 python lis.py。
- 呼叫 repl() 這個函式，進入 pseudo Lisp interactive shell。
- 一一試試下頭的 lisp expression。
>>> repl()
lis.py> (define area (lambda (r) (* 3.141592653 (* r r))))
lis.py> (area 3)
28.274333877
lis.py> (define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1))))))
lis.py> (fact 10)
3628800
lis.py> (fact 100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
lis.py> (area (fact 10))
4.1369087198e+13
lis.py> (define first car)
lis.py> (define rest cdr)
lis.py> (define count (lambda (item L) (if L (+ (equal? item (first L)) (count item (rest L))) 0)))
lis.py> (count 0 (list 0 1 2 3 0 0))
3
lis.py> (count (quote the) (quote (the more the merrier the bigger the better)))
4
連文章的標題都搞了一堆括號，可惜無法拿來執行 XD。 其實還有 +, -, *, / 算術運算子; not, >, <, >=, <=, =, equal?, eq? 邏輯運算子; length, car, cdr, cons, append, list, list?, null 這幾個 list 運算子。
