本文有两个目的: 一是讲述实现计算机语言解释器的通用方法，另外一点，着重展示如何使用Python来实现Lisp方言Scheme的一个子集。我将我的解释器称之为Lispy (lis.py)。几年前，我介绍过如何使用Java编写一个Scheme解释器，同时我还使用Common Lisp语言编写过一个版本。这一次，我的目的是尽可能简单明了地演示一下Alan Kay所说的“软件的麦克斯韦方程组” (Maxwell's Equations of Software)。
Lispy支持的Scheme子集的语法和语义
大多数计算机语言都有许多语法规约 (例如关键字、中缀操作符、括号、操作符优先级、点标记、分号等等)，但是，作为Lisp语言家族中的一员，Scheme所有的语法都是基于包含在括号中的、采用前缀表示的列表的。这种表示看起来似乎有些陌生，但是它具有简单一致的优点。 (一些人戏称”Lisp”是”Lots of Irritating Silly Parentheses“——“大量恼人、愚蠢的括号“——的缩写；我认为它是”Lisp Is Syntactically Pure“——“Lisp语法纯粹”的缩写。) 考虑下面这个例子：
/* Java */
if(x.val() > 0) {
z = f(a*x.val() + b);
}
/* Scheme */
(if (> (val x) 0)
(set! z (f (+ (* a (val x)) b))))
Copy after login
注意上面的惊叹号在Scheme中并不是一个特殊字符；它只是”set!“这个名字的一部分。(在Scheme中)只有括号是特殊字符。类似于(set! x y)这样以特殊关键字开头的列表在Scheme中被称为一个特殊形式 (special form)；Scheme的优美之处就在于我们只需要六种特殊形式，以及另外的三种语法构造——变量、常量和过程调用。
class Env(dict):
"An environment: a dict of {'var':val} pairs, with an outer Env."
def __init__(self, parms=(), args=(), outer=None):
self.update(zip(parms,args))
self.outer = outer
def find(self, var):
"Find the innermost Env where var appears."
return self if var in self else self.outer.find(var)
def read(s):
"Read a Scheme expression from a string."
return read_from(tokenize(s))
parse = read
def tokenize(s):
"Convert a string into a list of tokens."
return s.replace('(',' ( ').replace(')',' ) ').split()
def read_from(tokens):
"Read an expression from a sequence of tokens."
if len(tokens) == 0:
raise SyntaxError('unexpected EOF while reading')
token = tokens.pop(0)
if '(' == token:
L = []
while tokens[0] != ')':
L.append(read_from(tokens))
tokens.pop(0) # pop off ')'
return L
elif ')' == token:
raise SyntaxError('unexpected )')
else:
return atom(token)
def atom(token):
"Numbers become numbers; every other token is a symbol."
try: return int(token)
except ValueError:
try: return float(token)
except ValueError:
return Symbol(token)
def to_string(exp):
"Convert a Python object back into a Lisp-readable string."
return '('+' '.join(map(to_string, exp))+')' if isa(exp, list) else str(exp)
def repl(prompt='lis.py> '):
"A prompt-read-eval-print loop."
while True:
val = eval(parse(raw_input(prompt)))
if val is not None: print to_string(val)
Copy after login
下面是函数工作的一个例子：
>>> 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)
9332621544394415268169923885626670049071596826438162146859296389521759999322991
5608941463976156518286253697920827223758251185210916864000000000000000000000000
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
Copy after login
Lispy有多小、多快、多完备、多优秀？
我们使用如下几个标准来评价Lispy：
*小巧：Lispy非常小巧：不包括注释和空白行，其源代码只有90行，并且体积小于4K。(比第一个版本的体积要小，第一个版本有96行——根据Eric Cooper的建议，我删除了Procedure的类定义，转而使用Python的lambda。) 我用Java编写的Scheme解释器Jscheme最小的版本，其源代码也有1664行、57K。Jscheme最初被称为SILK (Scheme in Fifty Kilobytes——50KB的Scheme解释器)，但是只有计算字节码而不是源代码的时候，我才能保证 (其体积) 小于该最小值。Lispy做的要好得多；我认为它满足了Alan Kay在1972年的断言：他声称我们可以使用“一页代码”来定义“世界上最强大的语言”。
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
