上一集我们已经见到了一个Lisp程序的大致外貌,在文末,我提到这一集中我们将会用Lisp写一个Lisp解释器,事实上这个解释器并不太长,虽然它有可能是你至今为止见过的最长的一个。# }- f' V/ \' m9 m) h" X
1 w" d d" T% O" \( s3 i L我已经有点等不及了,让我们先来看一下整个程序,然后再来讲解:
; h/ z& D2 n$ P# B
8 m! Z# W( |- ]! P2 `! U3 T(defun eval (e a)8 _( v( s9 b6 L, g
(cond # U% E4 J; D3 Y
((atom e) (assoc e a))# _2 ^9 t; Q8 ~+ |' D
((atom (car e))( B* \$ k2 q. }5 W! a! J
(cond
) ^! q% G8 _) K9 o" P+ M ((eq (car e) 'quote) (cadr e))
% _& B; \' {2 I/ M& F% D ((eq (car e) 'atom) (atom (eval (cadr e) a)))
! z, e" c4 W/ m- d# s* J, l" |. s ((eq (car e) 'eq) (eq (eval (cadr e) a)
/ L' e/ |& c2 i, B5 F. B (eval (caddr e) a)))
0 `& M3 S: _# t/ d ((eq (car e) 'car) (car (eval (cadr e) a)))
6 S9 t0 g3 W$ P) } ((eq (car e) 'cdr) (cdr (eval (cadr e) a)))
! e8 `1 F% @, v6 A' @1 \ ((eq (car e) 'cons) (cons (eval (cadr e) a)# ]& ]' L1 @) ?# h7 W7 ~
(eval (caddr e) a)))& A3 q9 l* k: f- D6 o2 _8 P6 M
((eq (car e) 'cond) (evcon (cdr e) a)), Y M3 t: X) d
('t (eval (cons (assoc (car e) a)( ?2 H Y4 ? u8 E* K
(cdr e))% t2 y9 K1 f9 a' I [; m4 x
a))))
& | \9 q) b' p D7 k ((eq (caar e) 'label)
6 b, W( _! ~/ n# d- E4 I- w (eval (cons (caddar e) (cdr e))
5 F, [5 T& m6 x7 z, r2 A (cons (list (cadar e) (car e)) a)))4 I+ c' W6 `1 C u
((eq (caar e) 'lambda)
! A' C* q; s% B4 p$ ^# P. q% s6 o (eval (caddar e)
0 ]" ?9 j" U- \8 s- h, K5 `! I, c (append (pair (cadar e) (evlis (cdr e) a)), _# v' {, I3 f6 V( Z
a)))))5 N" ^* X& @$ H4 ]- {- B1 l, G
8 A8 j5 v w, Z" D4 g* i(defun evcon (c a)
- G# X. y3 K2 I2 e5 ^ (cond ((eval (caar c) a)7 [6 F; x7 A- {7 z* ^6 B z
(eval (cadar c) a))
1 O6 g- X4 P* G, Q7 M7 k ('t (evcon (cdr c) a))))9 }! ~, Z4 _% {
' g9 p; M v2 Y' I# r3 Z(defun evlis (m a)6 r& N) G, A+ u1 Y2 j% B
(cond ((null m) '())2 Y4 Y4 h9 M6 i4 q6 E: c6 s9 e
('t (cons (eval (car m) a)
; d7 h4 O; e8 K; l) _+ F (evlis (cdr m) a)))))/ ~/ k0 ^/ F y1 a
$ w; w1 n* l8 o, r* L W: C
(注:可能有的读者已经发现,Lisp并不要求你一定要在使用函数前先定义它)
: V0 \4 ]- m, {$ i/ q( E6 `1 _
. ~+ E- V3 k- {- S4 \$ u整个程序包含三个函数,主函数我们遵从Lisp(和Python、Perl)的惯例,叫它eval,它是整个程序的骨架。eval的定义比我们以前看到的任何一个函数都要长,让我们考虑它的每一部分是如何工作的。
0 J( k) l" ~0 q$ G& G
6 c8 P/ s* P Q0 reval有两个自变量:e是要求值的表达式,a是由一些赋给原子的值构成的表,这些值有点象函数调用中的参数。这个形如pair返回值的表叫做上下文,正是为了构造和搜索这种表我们才在前一章写了pair和assoc。
2 p1 _, i$ n U3 N$ L3 [. `% h. N# u' M) K! H* i* f7 t6 L
eval的骨架是一个有四个子句的cond表达式,如何对表达式求值取决于它的类型,第一个分支处理原子,如果e是原子, 我们在上下文中寻找它的值:) i# o' ?' X# B( \4 \0 r1 x2 a
8 ^+ X+ q+ \. c( H
> (eval 'x '((x a) (y b))) a% A' Y# g$ D% [0 R% N
第二个分支是另一个cond,它处理形如(a)的表达式,其中a是原子。这包括所有的基本操作符,每个对应一条分支。
$ w, t$ a& b: s7 a/ N; M8 t: H* @3 z$ _( o, d
> (eval '(eq 'a 'a) '()) t > (eval '(cons x '(b c)) '((x a) (y b))) (a b c)- r) G8 \$ Y$ y& o5 J3 B9 Z
这几个分支(除了quote)都调用eval来寻找自变量的值。
8 U3 F* W* z; S8 u: ]0 E0 L* ~0 t
最后两个分支更复杂些。为了求cond表达式的值我们调用了一个叫evcon的辅助函数。它递归地对cond分支进行求值,寻找第一个元素返回t的子句,如果找到了这样的子句,它返回此分支的第二个元素。
9 Q* {( Z3 B2 K! ^ B, `' b* K1 t* G+ l. {) q! u/ l1 q4 _( \
> (eval '(cond ((atom x) 'atom) ('t 'list)) '((x '(a b)))) list
& q& z4 N# E4 {$ a第二个分支的最后部分处理函数调用。它把原子替换为它的值(应该是lambda或label表达式)。然后对所得结果表达式求值。于是:# U: l' L- _( N& l2 V
& t: [0 B2 P$ F" I7 G( q- i& i(eval '(f '(b c)) '((f (lambda (x) (cons 'a x)))))0 E1 ?1 l; N0 ?
变为:1 q3 H0 k9 M( V& d. x( @, [! q
7 u* b2 ^/ I- A" N* I N, o, O3 b(eval '((lambda (x) (cons 'a x)) '(b c)) '((f (lambda (x) (cons 'a x)))))
9 G7 u [4 `4 k# N它返回(a b c) 0 l& O& R' N* z) J
* ]# m' F+ @. C+ m$ Y" v. D
eval的最后两个cond分支处理第一个元素是lambda或label的函数调。用为了对label表达式求值,先把函数名和函数本身压入上下文,然后调用eval对一个内部有lambda的表达式求值,即:
3 n5 e) q" H$ R
4 Z7 I; ^0 x, d+ V(eval '((label firstatom (lambda (x) (cond ((atom x) x) ('t (firstatom (car x)))))) y) '((y ((a b) (c d)))))& X2 r0 n/ L, j2 K( v
变为
8 |: @; \9 [' U6 l8 B% e3 e
) G5 A) X, U% K7 q(eval '((lambda (x) (cond ((atom x) x) ('t (firstatom (car x))))) y) '((firstatom (label firstatom (lambda (x) (cond ((atom x) x) ('t (firstatom (car x))))))) (y ((a b) (c d)))))/ W) G5 W4 }# R4 N0 B
最终返回a。+ ~1 E) `; A9 e
* X) l( I! B; C+ [' R# k i
最后,对形如((lambda (p1 p2 ... pn) e) a1 a2 ... an)的表达式求值,先调用evlis来求得自变量(a1 a2 ... an)对应的值(v1 v2 ... vn),把(p1 v1) (p2 v2) ... (pn vn)添加到上下文里,然后对e求值。于是:
- f) B, A. X' W# ~: ?3 ]3 _) @% m3 Z. d0 @4 U& U- y |
(eval '((lambda (x y) (cons x (cdr y))) 'a '(b c d)) '())4 J8 @) r. m+ w* T( s: U$ E
变为:
1 c0 {( Z% q5 G7 Z* V+ P) i# R* s! d% k
(eval '(cons x (cdr y)) '((x a) (y (b c d))))
! \# I( _/ _" ` l% C" U: h最终返回(a c d)。# \, G+ t! K' Z: s' j. K) F# P6 b- m
5 b0 l: W9 t% W! y9 t* H+ S% K# B, M讲了这么一大篇,如果你看懂了,说明你已经理解Lisp甚至FP的基本编程方式和思路,那么我们写了一个如此之长的程序究竟能干什么呢? W( M9 O2 V" w7 b. b0 `3 a9 ^
) h# f' `# ]( f我们在这里得到了一个非常优美的计算模型,eval函数实际上实现了整个语言,用它我们可以定义所需的任何其它函数。换句话说,我们现在有了一个自己的Lisp。# e! `( z J5 Q1 ]" a
; L2 r, }% M, y3 W% R% ~2 R(注:由此可见,递归下降的语法分析是多么美好啊,因为它意味着你可以用几十、最多不过一两百行程序搞定一个复杂的分析器,对比LALR你将更有体会)/ g3 V8 F3 D. \: T/ R5 r- J+ G. i
1 t3 {9 w t1 G( s- q3 c下面我们该去哪儿?这个问题,请读者自己去寻找答案。 |