data-structures - 将非类型化 Lisp 数据映射为类型化二进制格式以用于编译函数

Question

背景:我正在用 Haskell 编写玩具 Lisp(Scheme)解释器。我正处于我希望能够使用 LLVM 编译代码的地步。我花了几天时间想出各种方法，将未类型化的 Lisp 值提供给编译函数，这些函数期望知道传入数据的格式。我突然想到我不是第一个需要解决这个问题的人。

问题:将非类型化数据映射为高效二进制格式的历史上有哪些成功的方法。

附录:事实上，我确实知道数据是十几种不同类型中的哪一种，只是不知道哪一种可能会在编译时发送给函数。函数本身需要一种方法来确定它得到了什么。

Answer 1

您的意思是，“我只是不知道在运行时 可能会将哪种 [type] 发送给函数”？并不是没有输入数据；而是没有输入数据。当然 1 和 '() 有不同的类型。相反，数据不是静态类型的，即在编译时不知道给定变量的类型是什么。这叫做 dynamic typing .

你是对的，你不是第一个需要解决这个问题的人。规范的解决方案是标记每个运行时值及其类型。例如，如果您有十几种类型，请按如下方式编号:

• 0 = 整数
• 1 = cons 对
• 2 = 向量
• 等等

完成此操作后，为标签保留每个单词的前四位。然后，每次将两个对象传递给 + 时，首先执行一个简单的位掩码来验证两个对象的前四位是否为 0b0000，即它们都是整数。如果不是，则跳转到错误消息；否则，您继续添加，并确保结果也被相应地标记。

该技术实质上使每个运行时值成为一个手动- tagged union ，如果你使用过 C，你应该很熟悉。事实上，它也就像一个 Haskell 数据类型，只是在 Haskell 中，标记性要抽象得多。

如果您正在尝试编写 Scheme 编译器，我猜您对指针很熟悉。为避免限制您的可用内存空间，使用底部(最低有效)四位而不是顶部四位可能更明智。更好的是，因为对齐的双字指针在底部已经有三个无意义的位，你可以简单地为你的标签选择这些位，只要你取消引用实际地址，而不是标记的地址。

这有帮助吗？