Lisp的七个部分：用Erlang制作口译员

我想写一个计算机程序，威廉·伯德（William Byrd）博士将其描述为有史以来最漂亮的程序，您可能会在他关于计算机的精彩演讲中听到所有这些信息。

这是用Scheme编写的Lisp解释程序，它本身就是Lisp的方言。在纸上和文本编辑器中将程序完整写了数十遍之后，我决定从Racket开始将其带到新的地方。如此稍微更改Byrd博士（用Chez-Scheme编写）所讨论的实现到Racket程序的主要好处是，我能够利用Racket的内置模式匹配，因此一切都很好。框。然后，您还可以使用Racket提供的其他所有功能（很多）。但是Racket本身是基于Scheme的，所以我想知道将它带到其他地方会是什么样子。某个地方有些不同。球拍的模式匹配非常有用，因此也许是一种支持该语言的语言。函数式编程语言可能有意义，或者至少对函数作为值具有良好的支持。目标语言Lisp意味着我们将处理列表，因此使列表变得有趣的语言可能是个主意。我确定这听起来很多种语言，但在我个人所知的语言中，所有语言都指向Erlang。

Erlang中的列表看起来与Scheme中的列表没有什么不同：

可以使用lambda定义函数，其后是参数列表，然后是函数体。上面的函数称为身份函数，因为它仅返回其唯一的参数x。

尽管在本文中lambda是用于创建函数的术语，但该术语是任意的，因此您可以使用所需的任何术语代替它。

上面是一个将其参数加1的函数（假定已经定义了sum）。它被应用于5，因此我们知道在这种情况下，表达式的计算结果为6。

就像在Scheme中一样，可以通过将运算符及其操作数放在括号中来调用函数。例如，在Scheme中，可以通过将+运算符应用于两个操作数来将两个数字加在一起，如下所示：

这些被称为S表达式。一般规则是，函数（也称为运算符或过程）首先运行，然后跟随其参数，每个参数之间用空格分隔。

这种语言可以评估表达式，定义然后将函数应用于自变量，这种语言是图灵完备的。从这一点出发，任何可以用逻辑表达的东西都可以这种形式表达。在对标识函数的调用中可以看到上述每个组件的作用，在该调用中，标识函数作为参数传递：

也就是说，定义了一个函数（lambda（x）x），该函数本身以括号括起来，这意味着将使用参数（lambda（y）y）对其进行调用。

上面是我命名为interp的Erlang模块。在Erlang中，模块是存储代码的地方。文件名和模块必须匹配。 eval_expr是我在此模块中定义的一个函数，它带有2个参数Expr和_Env。此函数已导出，这意味着可以从其模块外部调用它。当is_number是一个保护对象时，在上述情况下，仅当Expr确实是一个数字时，才匹配此函数。之所以是_Env而不是Env的原因是，如果我们不打算在函数体内使用函数的参数，则它是一个未使用的变量，必须用前导下划线表示。您可能现在只是忽略_Env的实际含义。该函数的主体写在-＆gt;之后在这种情况下，返回Expr就是这样。

在Erlang中，您可以多次定义相同的函数，并使用Erlang的内置模式匹配根据其参数与它们进行匹配。

开和关不是变量。它们被称为原子。简单代表自己的事物。它们通常以小写字母开头，而变量以大写字母开头。即hello是一个原子，其中Hello是变量的名称。也可以将以上内容写为：

但是，为什么在第一种情况下可以进行模式匹配时就麻烦那么麻烦呢？函数中要计算的最后一个表达式是该函数将返回的内容。在这种情况下，它是if语句的结果，或者在前面的示例中为1或0。

Scheme使用其所谓的符号作为其变量的名称。在Erlang中，符号可以与原子相同。代表自己的东西以及两种语言之间的东西看起来有点相似。

一个新的附加eval_expr定义，但这一次它与Expr匹配，成为具有其保护作用的原子。然后，它将这个原子传递给Env，看起来像是一个函数调用。这必须意味着Env是一个函数。

环境就是环境。您可能熟悉如何在操作系统上存储和检索环境变量，从而可以使program-x运行并有权访问系统的环境变量，而program-y如果在相同环境中运行也可以访问相同的环境变量。环境在此解释器中将要使用的功能之一是变量的存储和检索，将作为函数参数传递的值映射到函数体内的相应标识符。 Scheme中的一个示例：

在将x和x应用于mul时，函数体需要知道x在运行时实际上是什么，以便将其自身相乘。这就是环境的所在。现在请记住这一点，接下来我们将继续对lambda进行一些模式匹配。

-module（interp）.- export（[eval_expr / 2]）。eval_expr（Expr，_Env）当is_number（Expr）-＆gt; expr;当is_atom（Expr）->时，eval_expr（Expr，Env） Env（Expr）; eval_expr（[lambda，[X]，Body]，Env）-> fun（Arg）-＆gt; eval_expr（Body，fun（Y）-> X的情况Y-> Arg; _-> Env（Y）结束）结束。

现在，您可能会开始注意到代码中的一些易变的模式，例如[lambda，[X]，Body]，经过一些语法修改后，它可以像Lisp形式读为（lambda（x）body）。

与到目前为止相比，这是Erlang模式匹配的一个更好的例子。这个新的eval_expr没有防护措施，但是我们希望只有在包含原子lambda的列表中传递该函数时，才调用此函数。一个包含未知变量X和函数体Body的列表。

在Erlang中，也可以使用fun关键字创建函数，上面的函数是一个在调用时将返回Arg + 1的函数。

在此解释器中，我们将在评估“身体”时扩展环境。这是通过在对eval_expr的调用中传入新环境来完成的。让我们看一下扩展环境的外观：

eval_expr（[lambda，[X]，Body]，Env）-> fun（Arg）-＆gt; eval_expr（Body，fun（Y）-> X的情况Y-> Arg; _-> Env（Y）结束）结束。

请记住，当评估一个原子时，通过将该原子作为参数传递时调用Env可以查找该值。

在环境本身内部，将传递给环境的参数Y与X进行比较，X是在函数体内查找的变量的标识符。一个例子：

当将1和myArg应用于+时，我们需要知道myArg是什么。相对于上面的eval_expr（[lambda，[X]，Body]…]块，在这里您可能会说：

如果X == Y，那么我们要寻找的参数Arg将返回环境查询。如果X和Y不相同，即传递给函数调用的变量的标识符与函数主体中的标识符不匹配，我们称Env（Y），其中Env来自最初传递给eval_expr的东西。

这部分代码只剩下最后一部分。那就是功能应用。换句话说，是一个函数调用。现在我们可以创建函数，让我们通过模式匹配看起来像函数调用的样式来添加调用它们的功能。

-module（interp）.- export（[eval_expr / 2]）。eval_expr（Expr，_Env）当is_number（Expr）-＆gt; expr;当is_atom（Expr）->时，eval_expr（Expr，Env） Env（Expr）; eval_expr（[lambda，[X]，Body]，Env）-> fun（Arg）-＆gt; eval_expr（Body，fun（Y）-> X的情况Y-> Arg; _-> Env（Y）end）end; eval_expr（[Rator，Rand]，Env）-> Rator1 = eval_expr（Rator，Env），Rand1 = eval_expr（Rand，Env），Rator1（Rand1）。

如果我们对包含两个内容的列表（操作符和操作数）进行模式匹配，我们将对它们进行评估，然后将rator应用于rand。即在传递rand作为参数时调用rator。现在可以创建和调用lambda。

创建和传递初始环境的帮助程序函数将很适合与此解释器一起使用。让我们导出一个我们将定义的新函数eval / 1。

默认环境没有要查找的任何变量值。因此，如果在函数体内找到未定义的变量，则将返回该变量，该列表包含两个原子，错误和variable_unbound。这些原子是任意的，可以命名为任何您想要的名称。

到目前为止，我们的目标语言语法在Erlang中表示为列表。这是传递了数字50的身份函数：

现在有了一个辅助函数，我们可以打开一个新的Erlang外壳，编译interp模块，然后使用Erlang的列表调用传入一个小的Lisp程序的eval函数。

现在已经实现了核心逻辑，剩下要做的就是构建一个简单的前端，这样我们就可以使用Lisp编写实际程序。您可能已经注意到，在构建此解释器时，实际上是从中间向外构造的。过去，我经常要执行编写解释器的任务，而我首先是从分词器开始的，然后是解析器，然后是实际的解释，依此类推……与运行时的执行顺序相同。乍一看，以相同的顺序实际编写程序可能很有意义。使一件作品可以工作，进行测试，移至下一件作品，将这两件作品依此类推，以线性方式进行。

在许多情况下，程序的构建顺序很重要。也许在理想世界中没关系。但是，如果要去编写一些代码并且不首先在代码的各个部分之间如何交互之间预先定义一些可靠的接口，那么您首先开始编写的部分可能会影响接下来编写的部分。如前所述，这种效果是基于程序员不必过多考虑接口而仅从上至下的角度关注程序。在我们的案例中，除了使用Erlang的内置列表来表示目标语言的列表以及使用Erlang函数来表示lambda之外，我们对此口译器的界面只字未提。这些是我为了使事情简单而做出的选择。从本质上讲，它是目标语言中的概念到宿主语言中存在的功能和数据结构的映射，即

目标语言-＆gt;主机语言lambda-＆gt;一个Erlang有趣的数字-＆gt; Erlang符号中的数字-> Erlang（1 2 3）中的一个原子-> Erlang中的列表，即[1,2,3]

例如，您可能希望在lambda中存储某种形式的元数据，因此与其使用Erlang函数来表示我们的lambda，不如使用Erlang中的列表来包含该函数和其他元数据。这样定义lambda意味着您还需要修改函数调用或函数应用程序的工作方式，以考虑新的列表数据结构并从该列表中获取函数以执行。这类数据结构超出了该解释程序的范围，但是没有什么阻止您进行此操作。

尽管不是本文的重点，但仍将将S-Expression从字符串解析为Erlang列表的方法已经编写出来，以便我们可以使用Lisp的语法编写程序来测试该新解释程序。您可以自己阅读解析代码，也可以将其复制并粘贴到文件中并运行它。在这里，您将可以按自己的方向带口译员，添加功能。甚至可以用您喜欢的语言来实现它。

-module（interp）.- export（[run / 1，eval_expr / 2，eval / 1]）。运行（ExprStr）-＆gt; eval（parse_string（ExprStr））。eval（Expr）-> eval_expr（Expr，fun（_Y）-> [error，variable_unbound] end）。eval_expr（Expr，_Env）is_number（Expr）-> expr;当is_atom（Expr）->时，eval_expr（Expr，Env） Env（Expr）; eval_expr（[lambda，[X]，Body]，Env）-> fun（Arg）-＆gt; eval_expr（Body，fun（Y）-> X的情况Y-> Arg; _-> Env（Y）end）end; eval_expr（[Rator，Rand]，Env）-> Rator1 = eval_expr（Rator，Env），Rand1 = eval_expr（Rand，Env），Rator1（Rand1）。 parse_string（Expr）-＆gt;列表：nth（1，parse（tokenize（Expr），[]））。parse（[]，Acc）-> Acc; parse（[[[$（] | Rest]，Acc）-> {Rem，SubTree} = parse（Rest，[]），parse（Rem，[SubTree | Acc]）; parse（[[$）] | Rest]，Acc）-＆gt; {Rest，lists：reverse（Acc）}； parse（[[[] | Rest]，Acc）-＆gt; parse（Rest，Acc）; parse（[H | T]，Acc）-> parse（T，[parse_token（H）| Acc]）。parse_token（Tkn）-> true的case is_string_an_integer（Tkn）-＆gt; list_to_integer（Tkn）; _-＆gt; list_to_atom（Tkn）end.is_string_an_integer（＆＃34;＆＃34;）-＆gt; false; is_string_an_integer（Str）-＆gt; list：all（fun（D）-> D＆gt; = $ 0并且D =＆lt; $ 9 end，Str）.tokenize（Expr）-＆gt; pad_tokens（Expr，[＆＃34;（＆＃34 ;,＆＃34;）＆＃34;]）。pad_tokens（Str，[]）-＆gt; string：split（lists：flatten（Str），＆＃34;＆＃34;全部）; pad_tokens（Str，[Tkn | Rest]）-＆gt; pad_tokens（string：replace（Str，Tkn，＆＃34;＆＃34; ++ Tkn ++＆＃34;＆＃34;全部），Rest）。

解析代码和新的运行功能是运行此程序并进行测试所需的最后几位。

$ erlEshell V11.0（用^ G终止）1＆gt; c（interp）。{ok，interp} 2＆gt; F ＝ interp：run（＆gt;（（λ（x）x）（λ（y）y））＆＃34;）。＃Fun＆lt; interp.1.99366422＆gt; 3＆gt; F（10）.10 如果您喜欢阅读本书籍，可以免费订阅并直接在收件箱中获取其他内容。