Lisp源代码重写系统

Question

Lisp源代码重写系统

macrospattern-matchinglispelispreduction

4

我想将已进行宏展开的Emacs Lisp代码进行反宏展开。我在Emacs论坛上询问过，但没有得到成功的回答。具体请参见： https://emacs.stackexchange.com/questions/35913/program-rewriting-systems-unexpanded-a-defmacro-given-a-list-of-macros-to-undo 然而，人们可能会认为这种S表达式转换正是Lisp所擅长的领域。而且，像Emacs Lisp一样，Lisp中也有defmacro。

因此，肯定有可以适应这里的程序转换系统或术语重写系统。

理想情况下，在某些情况下，这样的工具将能够直接从defmacro上进行模式查找和替换。即使我必须手动提供特定的搜索和替换模式以添加到转换系统中，拥有这样一个框架仍将非常有用。 目前为止的结果摘要：尽管有一些探索有趣可能性的答案，但现在还没有明确的结论。因此，我认为最好保持开放态度。我将总结一些建议。（我已经点赞了所有实际回答而非难度评论的答案。）

首先，许多人建议考虑仅进行扩展的特殊宏形式，或者按Drew的说法：

宏扩展（即不是Lisp求值后的扩展）。宏扩展是另一种说法，即规约语义或重写。

我心目中目前的领先者是Phil在帖子中使用的一种似乎特定于Emacs的模式匹配工具：pcase。我将探索这一点，并发布我的研究结果。如果其他人对此有想法，请发表意见。

Drew编写了一个名为FTOC的程序，其目的是将Franz Lisp转换为Common Lisp；谷歌搜索出现了 comp.lang.lisp posting。

我发现了一个名为optima的Common Lisp包，其中包含fare-quasiquote。保罗认为，由于它不直接处理回溯，所以可能不够强大，但可以手动编程实现。尽管回溯的普遍性可能很好，但我并不确定在最常用的情况下是否需要它。 附注：一些人似乎对引起我兴趣的具体应用感到不满。（但请注意，在研究中，好的解决方案经常被应用于最初没有设想的方式。）

所以，在这种精神下，这里有几个更改最终应用程序的建议。对于这些问题的一个好的解决方案可能会转化为Emacs Lisp的解决方案。（如果假装我对Emacs Lisp不感兴趣有助于你，那对我来说也没关系）。与其为Emacs Lisp编写反编译器，不如考虑为clojure或某些Common Lisp系统编写反编译器。或者根据Sylwester的回答建议，假设我想通过考虑使用现有的或已经得到改进的更简洁宏的好处来自动重构我的代码。请记住，一段时间内Emacs Lisp没有“when”或“unless”宏。

- rocky

6个回答

3

一般来说，我认为您不能做到这一点。lisp宏的扩展是图灵完备的，因此您必须能够预测具有任意输入的程序的输出结果。

有一些简单的事情可以做。带有反引号形式的defmacro在输出形式上看起来相当相似，可能会被检测到。这种启发式方法可能会让您走得更远。

我不理解的是您的用例。代码块的宏展开版本通常仅存在于已编译（或在emacs-lisp字节编译）形式中。

- Phil Lord

你可以从这个答案中去掉“think”：你不能做这件事。 - user5920214

1

使用案例是字节码反编译器。请参见 https://github.com/rocky/elisp-decompile。是的，许多有趣的事情都是图灵完备的，或者如果不是那样，那么就是P空间难的，或者NP完全的，或指数级别的。尽管如此，解决问题的需求仍然很大。因此，信息S表达式重写系统或更具体的启发式方法将受到赞赏。 - rocky

@rocky 在emacs的背景下，这甚至比一般情况更疯狂：这是emacs，你拥有制作字节码的源代码，因为你拥有GPL。 - user5920214

2

@tfb 是的，我知道似乎不可想象源代码可能不存在，因为它是GPL。源代码可用并不意味着在最需要时可以访问源代码。很多时候在回溯中我得到的是字节码。一个Lisp回溯会更好。即使它没有宏展开。 - rocky

2

我想将已经宏扩展的Emacs Lisp代码还原成未宏扩展的形式。

宏会生成任意表达式，其中可能包含递归的宏。您没有通用的方法来恢复转换，因为它不是基于模式的。

即使宏是基于模式的，它们仍然可能是无限的。

即使宏不是无限的，它们肯定会在从未匹配的模式扩展中包含错误。给定任意代码尝试解开，它可能会匹配一个看起来像代码的扩展，并尝试恢复到其模式。即使没有错误，您仍然可以滥用这一点。

即使您可以还原宏扩展，有些宏会扩展为相同的代码。一种方法是在所有还原扩展等于减去运算符的情况下发出警告并提供重启，以便如果重启不处理信号，则选择第一个扩展；否则发出错误并提供重启，以便如果重启不处理信号，则发生错误。或者您可以根据代码所在的软件包配置它以在某些条件下选择某些宏。

实际上，很少有情况需要还原扩展。它可能是一个有用的开发工具，可以建议宏，但我通常不会依赖它进行整个源代码的转换。

你想要实现的一种方法是通过控制模式匹配来实现。你可以最初手动创建模式，这些模式已经直接处理你关心的情况，比如你提到的情况：

将 (if (not <cond>) <expr>) 和 (if (not <cond>) (progn <&expr>)) 翻译为 (unless <cond> <&expr>)。你需要决定 null 是否等同于 not。我个人不会混淆 nil 的布尔含义和空列表或其他内容（例如没有结果、未找到、空对象、指示符等）。但也许像 Emacs 中那样老的 Lisp 代码会互换使用它们。
将 (if <cond> <expr>) 和 (if <cond> (progn <&expr>)) 翻译为 (when <cond> <&expr>)。
如果您觉得需要改进代码，请包括只有一个条件的 cond。并且要小心只有条件的 cond 子句。

你应该再多准备几十个模式，以查看在时间（CPU）和空间（内存）方面匹配更多模式时的模式匹配行为。

从fare-quasiquote的描述中可以知道，optima不支持回溯，而您可能需要它。

但是，您可以使用复杂内部模式上的递归进行optima回溯，如果没有匹配项，则返回控制值以保持从外部输入搜索匹配模式。

另一种方法是将模式视为状态机的描述，并处理每个新令牌以推进当前状态机，直到其中一个达到结尾，丢弃无法推进的状态机。此方法可能会消耗更多的内存，具体取决于模式的数量、相似性（如果许多模式具有相同的起始标记，则将生成许多状态机），模式的长度以及最后但并非最不重要的是输入（s表达式）的长度。

这种方法的优点是，您可以交互式地使用它来查看哪些模式匹配了最多的标记，并且您可以为模式分配权重而不仅仅是使用第一个匹配项。

缺点是，很可能需要花费一些精力来开发它。

编辑：我刚刚笨拙地描述了一种trie或radix tree。

一旦你得到了可用的东西，也许可以尝试自动获取模式。这真的很难，你可能需要将其限制在简单的反引号上，并接受这样一个事实：你无法为包含更复杂代码的任何内容进行概括。

我相信最困难的是代码遍历，在源代码上已经很难了，但在宏展开的代码上更加困难。也许如果你能进一步扩大整个图片以理解目标，也许有人可以建议除了操作宏扩展代码之外更好的方法。

然而，人们会认为这种事情，S表达式转换，正是Lisp所擅长的领域。而且defmacro似乎在Lisp中和Emacs Lisp中都可用。

因此，肯定存在程序转换系统或术语重写系统，可以在此处进行适应。

从使用“defmacro”扩展代码到所有这些泛化的步骤是巨大的。大多数Lisp开发人员至少都知道卫生宏，至少在符号作为变量方面。

但是仍然存在符号作为运算符的卫生宏¹，代码行走，与包含宏的交互（通常使用“macrolet”），等等。这太过复杂了。

通用Lisp在词法环境中计算复合形式的运算符，可能每个人都会制作假定使用符号的全局宏或函数定义的宏。但实际情况可能并非如此：

(defmacro my-macro-1 ()
  `1)

(defmacro my-macro-2 ()
  `(my-function (my-macro-1)))

(defun my-function (n)
  (* n 100))

(macrolet ((my-macro-1 ()
             `2))
  (flet ((my-function (n)
           (* n 1000)))
    (my-macro-2)))

那最后一行将扩展为(my-function (my-macro-2))，这将被递归地扩展为(my-function 2)。当评估时，它将产生2000。

为了正确的操作符卫生，你需要做这样的事情：

(defmacro my-macro-2 ()
  ;; capture global bindings of my-macro-1 and my-function-1 by name
  (flet ((my-macro-1-global (form env)
           (funcall (macro-function 'my-macro-1) form env))
         (my-function-global (&rest args)
           ;; hope the compiler can optimize this
           (apply 'my-function args)))
    ;; store them globally in uninterned symbols
    ;; hopefully, no one will mess with them
    (let ((my-macro-1-symbol (gensym (symbol-name 'my-macro-1)))
          (my-function-symbol (gensym (symbol-name 'my-function))))
      (setf (macro-function my-macro-1-symbol) #'my-macro-1-global)
      (setf (symbol-function my-function-symbol) #'my-function-global)
      `(,my-function-symbol (,my-macro-1-symbol)))))

根据这个定义，例子将会得到100。

Common Lisp有一些限制来避免这种情况，但它仅说明当在全局或局部重新定义common-lisp包中的符号时，后果是未定义的。它不要求发出错误或警告。（原文链接）

- acelent

虽然我很感激你描述这个问题的困难之处所付出的所有努力，详细说明为什么通常情况下无法解决它，但这并没有进一步解决问题。从这个意义上说，这不是一个“答案”。相反，为什么不专注于找到可处理的特定子集问题的解决方案，甚至可能可以自动化？例如，具有恒定替换形式的宏，例如用这个替换那个或者可能使用简单参数进行替换的宏，可以轻松解决。实际上，其他真正的答案也已经提出了这种建议。 - rocky

你可能需要一些模式匹配。稍后我会回顾答案并包括相关内容。 - acelent

2

好的，其他人指出这个问题一般是不可能解决的。这个问题有两个难点：一个是通过宏找到某个代码片段的预像可能需要很多工作，并且无法确定是否调用了宏——有一些例子可以写出从宏中产生的代码，而不使用该宏。为了说明，想象一下 sha 宏，它会将传递给它的字符串文字的 SHA 哈希值扩展出来。那么，如果你在扩展的代码中看到一些 sha 哈希值，尝试还原它显然是愚蠢的。但是也有可能哈希值被放入了代码中作为文字，例如引用 git 仓库历史记录中的特定点，因此取消宏的扩展也没有任何帮助。

可处理的子问题

让我先说一下，虽然这些问题可能有点容易处理，但我仍然不会尝试解决这个问题。

我们先忽略所有做怪异事情的宏（比如上面的例子）以及所有与原始代码相反的宏（例如 cond 和 if）以及生成复杂代码的宏，这些看起来很难理解（例如 loop、do 和反引号。令人讨厌的是，这些困难案例中，你可能最想取消宏的扩展）。这样留下来的类型（我想重点关注的）是基本上只减少样板代码的宏，例如 save-excursion 或 with-XXXX。它们的实现方式可能包括生成一些新符号（通过 gensym）然后有一个大而简单的反引号代码块。我仍然认为从 defmacro 自动转换到函数以进行取消扩展会太困难，但我认为你可以逐个攻击其中的一些问题。方法是查找宏生成的表单，这些表单定界（即开始/结束）扩展代码。除此之外，我无法提供更多帮助。这仍然是一个很难的问题，我认为任何现有解决方案（针对其他问题）都不会让你在这个问题上走得太远。

我理解还有一个进一步的复杂性，即你不是从宏扩展的代码开始，而是从字节码开始。如果对 elisp 编译器一无所知，我担心在编译步骤中失去更多信息，并且你需要撤销编译步骤，例如可能很难确定哪些代码进入 let 中，甚至在 let 开始时，或者字节码开始使用类似于 goto 的特性，尽管 elisp 没有这些特性。

您建议展开宏的原因是为了反编译在Emacs调试器中出现的字节码，这将非常有用，因为尽管理论上源代码是可用的，但并不总是随手可得。我向您提出，如果您想使Elisp调试更容易，那么弄清楚如何让Emacs调试器始终带您到内部函数的源代码会更值得。这可能涉及安装额外的调试相关包或下载Emacs源代码，并设置一些变量，以便Emacs知道在哪里找到它，或者从源代码自己编译Emacs。我不太清楚，但我敢打赌，在过去的三十年中，被抛入字节码而不是源代码已经足够成为Emacs开发人员的一个问题，因此解决该问题的方案已存在。

如果您真正想做的是尝试实现Elisp反编译器，那么我想那就是您应该做的。最后，一个观察结果是，虽然Lisp提供了使操作Lisp代码变得容易的功能，但这对反编译没有多大帮助，因为所有这些功能都可以在编译中使用，因此可能要检测的模式比例如C反编译器中要多得多。也许类似于scheme的宏会更容易展开，尽管它们仍然很难。

如果您正在反编译，因为您想给出比行更精确的子表达式的评估方式（通常Lisp调试器无论如何都是在表达式而不是行上工作），那么实际上查看扩展级别的代码可能会更有用而不是未展开的代码。或者最好同时看到两者，也许还有中间步骤。通过向前的宏展开跟踪各自的内容已经很困难和琐碎了。反过来做肯定不会更容易。祝好运！

编辑：考虑到您目前并没有使用Lisp，我想知道是否使用类似于Prolog之类的东西进行展开会更成功。您仍然需要手动编写规则，但我认为从宏定义中派生规则将需要大量的工作。

- Dan Robertson

1

我认为通常情况下不可能这样做，但是如果您为每个匹配提供撤销宏使用的代码，则可以将模式撤销回宏使用。混合了cond和if的代码最终只会成为if ，您的代码将删除所有if并将其转换为cond，使反向过程与起点不同。宏越多，它们相互扩展的次数就越多，起始点的最终结果就越不确定。

您可以设置规则，例如当您使用以下功能之一时，不会将if翻译为cond，例如：多个谓词或隐式progn，但是您不知道编码器是否实际上已经在所有地方使用了cond，因为他可能喜欢不一致。因此，您的取消宏实际上将更简化代码。

- Sylwester

这更像是一种观察而不是具体的解决方案。对于实现这一点，您有关于转换系统或框架的想法吗？ - rocky

@rocky 毫无头绪。我认为 optima 对于这个任务来说太简单了，因为你需要执行 (cons (cons ...，这会让你回到使用反引号之前的日子。 - Sylwester

我认为@rocky已经意识到这样一个系统的最终结果不能保证与原始代码的结构匹配，但是在问题中添加注释以澄清这一点可能是值得的。 - phils

1

我不相信有一个通用的解决方案，你肯定不能保证输出的结构与原始代码匹配，我也不会接受从宏定义中自动生成模式和期望转换的想法；但你可以使用Emacs自带的pcase模式匹配工具实现简单版本。

这是我能想到的最简单的例子：

参考when的定义：

(defmacro when (cond &rest body)
  (list 'if cond (cons 'progn body)))

我们可以使用pcase模式来转换代码，如下所示：

(let ((form '(if (and foo bar baz) (progn do (all the) things))))
  (pcase form
    (`(if ,cond (progn . ,body))
     `(when ,cond ,@body))
    (_ form)))

=> (when (and foo bar baz) do (all the) things)

显然，如果宏定义发生变化，那么您的模式将无法工作（但这是一种相当安全的失败）。

注意：这是我第一次编写pcase表单，我不知道自己不知道的东西。不过，它看起来像是按照预期工作的。

- phils

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Drew · Accepted Answer

大约30年前，我做了类似的事情，使用了macrolet（实际上，我使用的是defmacro，因为我们只有一个早期的Common Lisp实现，它还没有macrolet。但是macrolet是正确的选择）。我没有将宏展开的代码翻译成它所展开的内容，但是这个想法基本上是相同的。我预计你会遇到一些不同的困难，因为你的翻译距离一对一更远了。

我写了一个从当时的Franz Lisp到Common Lisp的翻译器，以帮助将大量现有代码移植到Lisp+Prolog机器项目中。当时的Franz Lisp仅具有动态作用域，而Common Lisp（通常）具有词法作用域。

当然，很明显没有一种通用的自动翻译Lisp代码（特别是考虑到它可以生成并评估其他代码 - 甚至忽略那个特殊情况），但是仍然可以完成许多有用的工作。如果生成的代码是自我记录的，告诉你它是从哪里派生出来的等等，那么在生成的上下文中，您可以决定如何处理可能棘手的这个或那个部分（例如，手动重新编写，从头开始或只是微调它）。在实践中，许多代码很容易从Franz转换为Common，这节省了很多重新编程的工作。

翻译程序是用Common Lisp编写的。它可以交互式地使用，也可以批处理使用。当交互使用时，它在Common Lisp之上提供了一个Franz Lisp解释器。

该程序仅使用宏展开（即不是展开后再进行Lisp评估）。宏展开是另一种说法是规约语义或重写。

输入Franz-Lisp代码通过函数定义映射宏进行宏展开，以生成Common-Lisp代码。对于翻译有问题的代码，在代码中标记了一个描述/分析，描述了这种情况。

该程序称为FTOC。我认为您仍然可以通过谷歌搜索（ftoc lisp）找到它，或者至少可以找到对它的引用。（这是我编写的第一个Lisp程序，我仍然对这个经历怀有美好的回忆。这是学习两种Lisp方言和Lisp的好方法。）

玩得开心！