“麦克斯韦软件方程式”考查(2008)

最近的一篇帖子引用了艾伦·凯(Alan Kay)的一句话，即表达Lisp本身就是麦克斯韦的软件方程式：是的，这是我在研究生院时得到的一个重大启示--当时我终于明白，Lisp1.5手册第13页底部的半页代码本身就是Lisp。这就是“麦克斯韦软件方程式！”

这句话出现在网络上的许多地方，但代码本身更难找到。这令人惊叹的半页代码是什么？由John McCarthy等人在1961年编写的Lisp1.5手册可以在softwarepresvation.org上找到。在它中，麦克斯韦方程式定义了一个可以计算任何给定函数通用Lisp函数值：WHERE APPLY[FN；x；a]=[ATOM[FN；Car]->；[eq[FN；Car]->；caar[x]；eq[fn；cdr]->；cdar[x]；eq[fn；cons]->；cons[CAR[x]；eq[fn；cdar[x]；eq[fn；cons]->；cons[car[x]；eq[fn；eq]->；eq[car[x]；cadr[x]；T->；Apply[eval[fn；a]；x；a]；eq[car[fn]；lambda]->；eval[caddr[fn]；pairlis[cadr[fn]；x；a]]；eq[car[fn]；label]->；Apply[caddr[Fn]；pairlis[cadr[fn]；x；a]]；eq[car[fn]；label]->；Apply[caddr[Fn]；pairlis[cadr[fn]；x；a]]。A]=[ATOM[e]->；Cdr[Assoc[e；a]]；ATOM[CAR[e]]->；[eq[CAR[e]，报价]->；cadr[e]；eq[CAR[e]；Cond]->；evcon[Cdr[e]；a]；T->；Apply[CAR[e]；evlis[Cdr[e]；a]；a]]；T-。a]]evcon[c；a]=[eval[caar[c]；a]->；eval[Cadar[c]；a]；T->；evcon[Cdr[c]；a]]evlis[m；a]=[null[m]->；nil；T->；cons[eval[car[m]；a]；evlis[Cdr[m]；a]。

上面的代码是用元语言(M-表达式)定义的，可以直接翻译成S-表达式。M表达式中的函数使用方括号，参数由分号分隔。m表达式条件语句的形式为[谓词->；值；谓词->；值；.]。m表达式标签类似于去有趣或定义。所有这一切的要点是，M表达式是对S表达式数据进行操作的代码，但是M表达式元语言和S表达式数据实际上是一致的。因此，在Lisp中，代码和数据是一回事，在给定几个原语(car、cdr、cons、eq、atom)的情况下，半页代码就足以用Lisp定义一个基本的Lisp解释器。代码为Lisp提供了一个元循环求值器；有关元循环求值器的更多详细信息，请参阅(SICP第4.1章。(不幸的是，这并不能免费为您提供一个可以正常工作的Lisp解释器；垃圾收集器、列表原语和解析等内容需要在某个地方实现。还要注意，这个元循环求值器不会给您提供像算术这样的细节。))。要理解上面的代码，Apply接受一个函数和参数，而eval作用于一个表单。这些参数的最后一个参数是环境的关联列表，该列表存储绑定值和函数名的值。简而言之，就原语而言，Apply实现了CAR、CDR、CONS、ATOM和EQ。它通过将变量和参数配对并将它们传递给eval来实现lambda。它通过将函数名称和定义添加到关联列表来实现Label(定义函数)。eval的代码以一种简单的方式处理表单。它通过返回引用值来处理报价表单。它通过在evcon的帮助下计算谓词来处理cond。否则，它将原子解释为变量并返回值。如果给出一个列表，它会将其解释为函数应用程序；参数由valis求值，函数由Apply求值。上面的代码并不十分完整；它依赖于之前在手册中定义的其他一些简单函数，例如equals和cadr。不太明显的函数是pairlis[x；y；a]将列表x和y配对并将它们添加到关联列表A中。assoc[x；a]在关联列表A中查找x。subis[a；y]将关联列表a视为变量到值的映射，并将S表达式y中的变量替换为关联变量。这些函数可以直接从原始函数构建。(顺便说一句，我非常肯定eq[car[e]，引用]中的逗号是个打字错误，但原文就是这样。)