Lisp学习笔记——Common Lisp简单求值器的编写(3)
之前开发的准备工作已经做好了,接下来我们要做的便是最后一步,实现这个求值器。
在开始之前,我把容易混淆的内容先提取出来,尽量解释清楚。
1.我们使用的语言是Common Lisp语言,它和C语言,C++语言一样,属于编程语言,我们可以通过它们来编写程序。
2.我们要编写的"求值器",不过就是一个普通的函数而已。它和其他函数一样,由形参接受实参的值,并对传递近来的数据做某种处理,返回一个值。
3.我们编写的这个"求值器"程序,它所接受的实参有点特殊。一个形参所接受的实参值是一个Lisp表达式。而我们这个程序可以根据这一个表达式,进行一种叫做"求值"的处理,返回一个值,并把这个值叫做这个Lisp表达式的值。从这里,我们可以开始体会到Common Lisp的一种神奇之处——代码与数据并没有明确区分,它们有着同样的结构,这样我们就可以轻松的把代码表示成为数据,并且像处理数据一样处理代码。这里,建议大家多多动手实验之后,再回头看看,就会有一种恍然大悟的感觉了,光靠说,理解还是比较困难的。
在这里,我们使用Common Lisp来编写这个求值器程序,而这个求值器程序本身又是用来解释Common Lisp表达式的。大家在看的过程当中,希望能够把这个关系搞清楚。
那么首先让我们着眼于基本表达形式。
在我们的"求值器"程序中,所接受到的代码是一个Lisp表达式,我们可以通过相应的操作,取出我们所需要的数据部分,而它们就是相应的原子或者列表形式。即我们利用母语言(我们用来编写求值器的语言)中数据的表现形式作为我们所要解释语言中的数据表现形式。与此同时,我们把几大基本操作过程也用母语言中过程予以代替。这里可能不太好理解,我会在下面结合代码进行描述。
最重要的就是第二部分的内容,关于组合方式的内容。
在前面的内容当中,我们已经了解了如何构造LISP表达式的方法,并且知道每一个Lisp表达式都一个对应的值。而求值器的作用就是用来求出这个值,求值规则我们也在前面进行了介绍。
在这里,我们需要明白,构成表达式的方法即组合方式是来指导我们如何写出合法的表达式,而求值规则则是求值器用来解析这些合法表达式的依据。即,人遵循组合方式来书写“语句”,求值器程序按照求值规则来解析这些“语句”。而求值规则又是由组合方式确定的。
因为这部分内容不涉及抽象定义新过程,所以我们需要处理的问题是基本过程的组合表达式以及原子的求值。
按照求值规则,原子的求值除了符号是它代表的变量的值,其他的都是自求值。这里,我们需要采取一种手段将符号以及它所对应的变量的值关联起来。这里采用的是属性表(alist)数据结构。
这种数据结构的形式如图所示:
每一个节点都是一个点对单元,点对单元的第一个元素是符号名,第二个元素是符号对应的变量的值。所有的符号与变量的对应关系都是存放在一个叫做环境(environment)的属性表(alist)中的。
让我们跟着求值规则处理第一种组合表达式的情况——原子求值。
代码如下(CSDN没有Lisp的代码风格,我只能用其他风格来代替):
(defun label-call (exp env) (my-eval-1 (label-to-lambda exp) (label-to-env exp env)))(defun label-to-lambda (exp) (cons (third (car exp)) (cdr exp)))(defun label-to-env (exp env) (append (reverse (pairlis (list (second (car exp))) (list (third (car exp))))) env))(defun evcon (exp env) (if (my-eval-1 (first (first exp)) env) (my-eval-1 (second (first exp)) env) (evcon (cdr exp) env)))(defun my-eval-1 (exp env) (cond ((atom exp) (cond ((numberp exp) exp) ((stringp exp) exp) (t (cdr (assoc exp env))))) ((atom (car exp)) (cond ((eq (car exp) 'quote) (second exp)) ((eq (car exp) 'atom) (atom (my-eval-1 (second exp) env))) ((eq (car exp) 'eq) (eq (my-eval-1 (second exp) env) (my-eval-1 (third exp) env))) ((eq (car exp) 'car) (car (my-eval-1 (second exp) env))) ((eq (car exp) 'cdr) (cdr (my-eval-1 (second exp) env))) ((eq (car exp) 'cons) (cons (my-eval-1 (second exp) env) (my-eval-1 (third exp) env))) ((eq (car exp) 'cond) (evcon (cdr exp) env)) (t (my-eval-1 (cons (cdr (assoc (car exp) env)) (cdr exp)) env)))) ((eq (car (car exp)) 'lambda) (lambda-call exp env)) ((eq (car (car exp)) 'label) (label-call exp env)) (t (error "Unkonwn form!"))))(defun lambda-call (exp env) (my-eval-1 (third (car exp)) (append (reverse (pairlis (second (car exp)) (evlis (cdr exp) env))) env)))(defun evlis (exp env) (if (null exp) nil (cons (my-eval-1 (car exp) env) (evlis (cdr exp) env))))
整个求值器就这样完成了,虽然经过一些测验无误,但也不敢保证完全没有问题。这一块内容,我讲的比较模糊,因为自己的理解也还有限,再加上语言描述能力还不行。在后面的学习的当中,随着理解的更加深入,这些基础的东西应该能解释的更好。
这一部分的内容,算是提前预习,按照自己的粗浅理解写了这么一个求值器。下一个阶段的任务,是按照SCIP书上的内容,开始好好学习求值器的编写。