打算实现一个lisp解释器,纯做娱乐.
Lisp 七公理
Lisp一开始是作为理论推倒被提出的,只是后来发现它恰好可以真的实现成为编程语言而已. (这看起来就像,python是恰好可以运行的伪代码)
因此它的形式上具备极高的美感(当然,有戏言称lisp程序的最后一页全是右括号,不过要知道那么长的程序,不管什么语言都不会看着很让人愉悦).
在黑客与画家中提到,lisp当年所提出的一些理念,到很多年后才在新生代的编程语言中得到大规模的应用.关于这些理念是什么暂且按下,我们先看一看lisp语言的基础结构.
就像平面几何的五个公理(把平行线公理换掉可以推导出另外的几何体系,这不禁让人想象,如果把lisp的原语换成另外一组会怎么样), lisp有七个公理,是七个基础操作符.
(quote x) => x
quote操作符返回其参数本身,不对其求值,在lisp中通常简写为’x
(atom x) => t | ()
在lisp中,习惯以t表示真,以空表()表示假
atom操作符在x是一个原子或者空表时返回t, 否则返回()
(eq x y) => t | ()
eq操作符即相等操作符,作用不言自明
(car x)
car要求x是一个表,它返回x的第一个元素
(cdr x)
cdr同样要求x是一个表,返回x中除了第一个元素以外的所有元素
(cons x y)
要求y是一个表.返回一个表,其第一个元素是x,后面的元素为y中的所有元素
(cond (p1 e1) (p2 e2) … (pn en))
cond是条件表达式,其复杂程度就像欧几里得的第五个公理.cond将p1到pn依次求值, 直到找到第一个值为t的pi,把对应的ei作为整个表达式的值返回.
七个操作符中,除了quote和cond, 其它操作符会对它的所有参数求值.
lisp 实现
在这里,我要尝试从零开始用python实现一个lisp解释器.
之前说的是那些基本的列表操作,然而通过它们并不足以构建出一个lisp语言,现在引入一些额外的符号.
(define var exp):
定义var,其值为exp求值的结果(lambda (p1 p2 … pn) exp):
表达式的求值结果为一个函数,pi为其参数,exp为其函数体
好吧经过一段时间的学习，我仍是没有完成lisp的实现……不过已经快了。
整个项目放在github上，实现了七个基本原语当中的除cond以外的六个。
前段时间读了读SICP，发觉自己对于lisp的理解还是有很大的偏差，很多我以为是函数的东西，事实上应当被叫做“special form”。这样很多东西就好解释了。
我也曾试图用yacc和lex来处理，后来由于对于lisp理解的偏差没能成功，最后还是用裸写的方式。
有时间再继续吧。