有史以来最漂亮的程序——用 Lisp 编写的 Lisp 解释器

2021-08-09 18:42:11

这是我第 5 次尝试关注此视频,事情终于开始在我脑海中响起。所以我想如果我把视频里讲的东西写下来,那么我可以再读15遍我的博客文章而不是看视频,这样会很方便。好的,这是它的要点。这家伙正在用Scheme 编写Scheme 解释器。让我们先从设置环境开始,然后我们可以输入。本次演讲使用的编程语言是Scheme Chez Scheme的方言,您可以从这里下载并安装它。在talk pmatch 中使用了一个模式匹配库,你可以从这里找到源代码。如果您从未使用过 Lisp,REPL 代表 Read Eval Print and Loop,它是一个交互式编程环境,允许您在输入时执行程序。现在我们只需在终端中输入 scheme 即可启动 REPL。或者如果你像我一样使用 Emacs,你可以只使用 Mx 运行方案。引用任何东西都会给你回那个东西的象征。 Symbol 有点像其他语言中的变量,它可能绑定到某个值,也可能没有。

无效的?是一个函数,如果其 arg 为 null 则返回 true,否则返回 false。 lambda 是一种定义函数的方式,例如 (lambda (x) x) 表示这是一个返回它所接受内容的函数。换句话说,它是恒等函数。正如我们所见,它试图将给定的表达式模式匹配到 ´n´,其中 n 是数字,如果找到匹配项,它会返回 n 本身。可以看到我们使用 Scheme 中的 add1 来实现我们语言中的 add1。注意那里的递归 eval-expr,以便我们可以处理像 (add1 (add1 6)) 这样的嵌套表达式。 ,rator 代表运算符,而 ,rand 代表操作数。这相当简单,我们首先评估运算符表达式,然后评估操作数表达式并将前者应用于后者。现在让我们尝试添加 lambda 表达式。这是最困难的部分,所以不要指望一口气理解它。甚至你认为你理解它,你可能没有。我发现了解更高层次上发生的事情更为重要,这将使阅读代码变得更加容易。

所以我们试图解释 lambda 表达式,但结果是什么?是的,一个我们可以稍后调用的过程,准确地说是一个 Scheme 过程。那么我们如何创建一个 Scheme 过程呢?你猜对了,拉姆达!因此,我们语言中的 lambda 将被解释为 Scheme 中的 lambda。举个例子,假设我们要解释表达式 (lambda (x) (* x 2)),x 是什么?它并不真正意味着任何单独的东西,而是一个将与主体 (* x 2) 结合使用的指标。那么x的值是多少?我们还不知道,正如所说它只是一个指标,一个符号,还没有分配给它的值。但是什么时候会知道价值呢?当然,当我们调用它时。因此,根据我们现在所知道的,可以将 lambda 表达式解释为这样的 Scheme 过程:这里的 arg 是什么?这将是调用此 lambda 的参数。这里有问题。当我们评估主体时,在这种情况下看起来像 (eval-expr '(* x 2)),我们如何将 arg 5 连接到 x?换句话说,在运行时,当 Scheme lambda 被 5 调用时?解释器怎么知道现在 x 应该被评估为 5?答案是引入环境env。 env 是一个接受一个参数的过程。因此,当我们尝试在环境中查找符号时,我们只需使用符号来调用它:(env x)。那么现在回到问题上来,在评估body时我们只需要提供合适的环境,这样当我们稍后查找x时,它会产生5,这就是arg。现在有了所有这些知识,你可以阅读代码,看看你是否能更好地理解它。 (define factorial ((lambda (!) (lambda (n) ((! ! ) n ))) (lambda (! ) (lambda (n ) ( if (zero? n ) 1 (* n ((! ! ) ( sub1 n )))))))))

好吧,如果没有,那就回去重新阅读这篇博文或重新观看视频,直到一切都变得清晰为止。警告,如果您一直考虑所有嵌套的 lambda,您可能会在夜间醒来或错过公交车站。除此之外,你会没事的。