当前位置：首页 > article >正文

Emacs折腾日记（十一）——求值规则

article 2025/3/1 15:31:36

截至到现在，我觉得我自己的elisp水平有了一定的提高，希望各位读者借助之前的文章也能有一些收获。现在已经可以尝试写一点elisp的程序了，但是如果想深入了解一下 lisp 是如何工作的，不妨先花些时间看看 lisp 的求值过程。

对于我这样一个日常使用C/C++的程序员来说，习惯了C/C++的语法和写法，初次见到lisp这样使用括号并且主要是S-表达式的语言，开始总会有点不习惯，但是在尝试自己写了这么些文章之后，对lisp有那么一点感觉。这篇我想就着求值规则这篇文章以及自己的一些理解来尝试梳理一下自己是如何理解elisp表达式的。

S表达式

要理解S表达式，我们先从如何解析四则运算开始。在之前我鸽了一个系列就是使用C来实现C语言解析器的系列。在那个系列中提到，一个普通的4则运算最终会生成一个抽象语法树，例如 a * b - (c + d) 最终可以生成如下的抽象语法树

        -
     /     \
   *         +
 /   \     /   \
a     b   c     d

二叉树的每个节点，或者是叶节点，或者有2个子节点，叶节点可以用来存储数据。而每颗子树的根节点存储操作符，或者说表示要对数据进行的操作，而如果操作符需要一个或者多个操作数，那么可以对抽象语法树进行调整。

可以用上面的图来表示树的话有些麻烦了，后来发明了点对表示法，如果只关心叶子节点，每颗子树的根节点采用.来表示，那么这颗二叉树可以表示为 ((a . b) . (c . d)) 。看到这里各位读者想到了什么呢？cons cell。

S表达式是点对表示法的形式定义：

原子 -> 数字 | 符号
S表达式 -> 原子 | (S表达式 . S表达式)

所以，S表达式或者是原子，或者是递归的由其他S表达式构成的点对。

虽然抽象语法树可以使用这种点对来描述，但是语法树大了，点的数量大了，其实也挺麻烦的，所以lisp中有一些简单的写法。回顾一下之前学习列表和cons cell的知识，简化也就得到了列表，例如

'((a . b) . (c . d)) ⇒ ((a . b) c . d)
'((a . b) . (c . (d . nil))) ⇒ ((a . b) c d)

如果我们考虑这颗树的根节点，并且采用先序遍历的方式访问，结果仍然采用点对来表示，那么将得到这样的结果 (- (* a b) (+ c d))。这样我们得到了计算这个四则运算的lisp代码，这个它可以作为列表，也可以让lisp解释器来执行。

到此为止，各位读者应该理解了S表达式。它其实就是对应了一颗语法树。现在看到S表达式也不那么恐惧了，解释器如何执行它似乎也慢慢的清晰起来了呢

S表达式的求值

理解了S表达式，再回过头来看看它的求值过程。

所有的表达式可以分为三种：符号、列表和其它类型。我们来分别说明

最简单的就是自求值表达式，前面说过数字、字符串、向量都是自求值表达式。还有两个特殊的符号 t 和 nil 也可以看成是自求值表达式。

第二种表达式是符号。符号的求值结果就是符号的值。如果它没有值，就会出现 void-variable 的错误。

第三种表达式是列表表达式。而列表表达式又可以根据第一个元素分为函数调用、宏调用和特殊表达式（special form）三种。根据上面对S表达式的理解，这里的第一个元素也就是放在语法树的每颗子树的根节点上，表示对它的子节点进行的操作，例如上面的加减乘除，或者使用car之类的函数。而它的子节点可以是一颗语法树，也可以是简单的值，对应在elisp中的话，就是这个操作可以针对上面两种自求值表达式或者符号值，也可以是另一个S表达式。

整个求值过程就是不断的求子树然后使用根节点来对子树进行操作，例如针对上面的二叉树可以写下这么一段伪代码来实现求值

float calc-ast(ast* pRoot)
{
	switch(pRoot->eOprType)
	{
	case function: //函数调用
		return function(calc-ast(pRoot->left), calc-ast(pRoot->right));
	case math: // 数学计算
		return calc-ast(pRoot->left) + calc-ast(pRoot->right); //这里以加法为例
		....
	default:
		calc-ast(pRoot->left);
		calc-ast(pRoot->right);
		break
	}
}