compiler-construction - Lisp 如何既是动态的又是编译的？

Question

好的，首先要解决这个问题：我已阅读以下答案：

但我真的不明白它的答案。

在像 Python 这样的语言中，表达式：

x = a + b

无法真正编译，至于“编译器”，不可能知道 a 和 b 的类型（因为类型仅在运行时才知道），因此无法知道如何添加它们。

这就是没有类型声明就无法编译像 Python 这样的语言的原因，对吗？通过声明，编译器知道例如 a 和 b 是整数，因此知道如何添加它们，并将其转换为本机代码。

那么如何：

(setq x 60)
(setq y 40)
(+ x y)

工作？

编译被定义为本地提前编译。

编辑

实际上，这个问题更多是关于是否可以编译没有类型声明的动态语言，如果可以，如何编译？

编辑 2

经过大量研究（即狂热的维基百科浏览），我想我了解以下内容：

动态类型语言是在运行时检查类型的语言
静态类型语言是在编译程序时检查类型的语言
类型声明允许编译器使代码更高效，因为它可以使用更多本机“函数”而不是一直进行 API 调用（这就是为什么您可以向 Cython 代码添加类型声明以加速它，但没有到，因为它仍然可以只调用 C 代码中的 Python 库）
Lisp 中没有数据类型；因此没有要检查的类型（类型是数据本身）
Obj-C 既有静态声明也有动态声明；前者在编译时进行类型检查，后者在运行时进行

如果我在上述任何一点上错了，请纠正我。

score 26 · Accepted Answer

示例代码：

(setq x 60)
(setq y 40)
(+ x y)

使用 Lisp 解释器执行

在上面的基于解释器的 Lisp 中，将是 Lisp 数据，解释器查看每个表单并运行评估器。由于它运行的是 Lisp 数据结构，所以每次看到上面的代码时都会这样做

得到第一个表格
我们有一个表达
它是一个 SETQ 特殊形式
评估 60，结果为 60
查找变量 x 的位置
将变量 x 设置为 60
获取下一个表格......
我们有一个函数调用 +
评估 x -> 60
评估 y -> 40
用 60 和 40 -> 100 调用函数 + ...

现在+是一些代码，它实际上找出了要做什么。Lisp 通常具有不同的数字类型，并且（几乎）没有处理器支持所有这些：fixnums、bignums、ratio、complex、float ......所以+函数需要找出参数的类型以及它可以做些什么来添加他们。

使用 Lisp 编译器执行

编译器将简单地发出机器代码，机器代码将执行操作。机器代码将完成解释器所做的一切：检查变量、检查类型、检查参数数量、调用函数……

如果您运行机器代码，它会快得多，因为不需要查看和解释 Lisp 表达式。解释器需要解码每个表达式。编译器已经完成了。

它仍然比某些 C 代码慢，因为编译器不一定知道类型，而只是发出完全安全和灵活的代码。

所以这个编译的 Lisp 代码比运行原始 Lisp 代码的解释器快得多。

使用优化的 Lisp 编译器

有时它不够快。然后你需要一个更好的编译器并告诉 Lisp 编译器它应该在编译中投入更多的工作并创建优化的代码。

Lisp 编译器可能知道参数和变量的类型。然后，您可以告诉编译器忽略运行时检查。编译器还可以假设+始终是相同的操作。所以它可能会内联必要的代码。由于它知道类型，它可能只为这些类型生成代码：整数加法。

但是 Lisp 的语义仍然不同于 C 或机器操作。A+不仅处理各种数字类型，它还会自动从小整数 (fixnums) 切换到大整数 (bignums) 或在某些类型的溢出时发出错误信号。您还可以告诉编译器忽略它，而只使用本机整数加法。然后你的代码会更快——但不像普通代码那样安全和灵活。

这是使用 64 位 LispWorks 实现的完全优化代码的示例。它使用类型声明、内联声明和优化指令。你看我们必须告诉编译器一点：

(defun foo-opt (x y)
  (declare (optimize (speed 3) (safety 0) (debug 0) (fixnum-safety 0))
           (inline +))
  (declare (fixnum x y))
  (the fixnum (+ x y)))

然后代码（64 位 Intel 机器代码）非常小，并且针对我们告诉编译器的内容进行了优化：

       0:      4157             push  r15
       2:      55               push  rbp
       3:      4889E5           moveq rbp, rsp
       6:      4989DF           moveq r15, rbx
       9:      4803FE           addq  rdi, rsi
      12:      B901000000       move  ecx, 1
      17:      4889EC           moveq rsp, rbp
      20:      5D               pop   rbp
      21:      415F             pop   r15
      23:      C3               ret   
      24:      90               nop   
      25:      90               nop   
      26:      90               nop   
      27:      90               nop

但请记住，上面的代码所做的事情与解释器或安全代码所做的事情不同：

它只计算fixnums
它会默默地溢出
结果也是一个fixnum
它没有错误检查
它不适用于其他数字数据类型

现在未优化的代码：

       0:      49396275         cmpq  [r10+75], rsp
       4:      7741             ja    L2
       6:      4883F902         cmpq  rcx, 2
      10:      753B             jne   L2
      12:      4157             push  r15
      14:      55               push  rbp
      15:      4889E5           moveq rbp, rsp
      18:      4989DF           moveq r15, rbx
      21:      4989F9           moveq r9, rdi
      24:      4C0BCE           orq   r9, rsi
      27:      41F6C107         testb r9b, 7
      31:      7517             jne   L1
      33:      4989F9           moveq r9, rdi
      36:      4C03CE           addq  r9, rsi
      39:      700F             jo    L1
      41:      B901000000       move  ecx, 1
      46:      4C89CF           moveq rdi, r9
      49:      4889EC           moveq rsp, rbp
      52:      5D               pop   rbp
      53:      415F             pop   r15
      55:      C3               ret   
L1:   56:      4889EC           moveq rsp, rbp
      59:      5D               pop   rbp
      60:      415F             pop   r15
      62:      498B9E070E0000   moveq rbx, [r14+E07]   ; SYSTEM::*%+$ANY-CODE
      69:      FFE3             jmp   rbx
L2:   71:      41FFA6E7020000   jmp   [r14+2E7]        ; SYSTEM::*%WRONG-NUMBER-OF-ARGUMENTS-STUB
  ...

您可以看到它调用了一个库例程来进行添加。这段代码完成了解释器会做的所有事情。但它不需要解释 Lisp 源代码。它已经编译成相应的机器指令。

为什么编译的 Lisp 代码很快（呃）？

那么，为什么编译的 Lisp 代码很快呢？两种情况：

未优化的 Lisp 代码：Lisp 运行时系统针对动态数据结构进行了优化，无需解释代码
优化的 Lisp 代码：Lisp 编译器需要信息或推断信息，并做大量工作来生成优化的机器代码。

作为一名 Lisp 程序员，您大部分时间都希望使用未经优化但已编译的 Lisp 代码。它足够快并且提供了很多舒适。

不同的执行模式提供选择

作为 Lisp 程序员，我们有以下选择：

解释代码：慢，但最容易调试
编译代码：运行时速度快，编译速度快，编译器检查很多，调试难度稍大，完全动态
优化的代码：运行时非常快，运行时可能不安全，各种优化的大量编译噪音，编译速度慢

通常我们只优化那些需要速度的代码部分。

请记住，在很多情况下，即使是好的 Lisp 编译器也无法创造奇迹。一个完全通用的面向对象程序（使用 Common Lisp 对象系统）几乎总是会有一些开销（基于运行时类的调度，...）。

动态类型和动态不一样

另请注意，动态类型和动态是编程语言的不同属性：

Lisp 是动态类型的，因为类型检查是在运行时完成的，并且默认情况下可以将变量设置为各种对象。为此，Lisp 还需要附加到数据对象本身的类型。
Lisp 是动态的，因为 Lisp 编程语言和程序本身都可以在运行时更改：我们可以添加、更改和删除函数，我们可以添加、更改或删除语法结构，我们可以添加、更改或删除数据类型（记录、类，...），我们可以通过各种方式改变 Lisp 的表面语法，等等。Lisp 也是动态类型的，以提供其中一些特性。

用户界面：编译和反汇编

ANSI Common Lisp 提供

编译代码的两个标准函数：编译和编译文件
加载源代码或编译代码的一种标准函数：加载
反汇编代码的一个标准函数：disassemble

score 7 · Accepted Answer

编译是从一种语言到另一种语言的简单翻译。如果你能用语言A和语言表达同一个东西B，你就可以把这个用语言表达的东西编译A成用语言表达的同一个东西B。

一旦你用某种语言表达了你的意图，它就会通过被解释来执行。即使在使用 C 或其他一些编译语言时，您的声明也是：

翻译自 C -> 汇编语言
从汇编翻译-> 机器码
由机器解释。

计算机实际上是一种非常基本的语言的解释器。由于它是如此基础且难以使用，人们想出了其他更容易使用的语言，并且可以很容易地翻译成机器代码（例如 C）中的等效语句。然后，您可以通过像 JIT 编译器那样“即时”执行翻译来劫持编译阶段，或者通过编写您自己的解释器直接执行您的高级语言（例如 LISP 或 Python）中的语句。

但请注意，解释器只是直接执行代码的捷径！如果解释器不执行代码，而是打印它将进行的任何调用，它是否会执行代码，您将拥有...一个编译器。当然，那将是一个非常愚蠢的编译器，它不会利用它拥有的大部分信息。

实际的编译器会在生成代码之前尝试从整个程序中收集尽可能多的信息。例如，下面的代码：

const bool dowork = false;

int main() {
    if (dowork) {
        //... lots of code go there ... 
    }
    return 0;
}

理论上会生成if分支内的所有代码。但是一个聪明的编译器可能会认为它无法访问并忽略它，利用它知道程序中的所有内容并且知道dowork它将永远存在的事实false。

除此之外，一些语言还具有类型，可以帮助调度函数调用，在编译时确保一些事情，并帮助翻译成机器代码。像 C 这样的一些语言要求程序员声明其变量的类型。LISP 和 Python 之类的其他语言只是在设置变量时推断变量的类型，如果您尝试使用某种类型的值，如果需要另一种类型（例如，如果您(car 2)在大多数 lisp 解释器中编写，它会引发一些错误告诉你一对是预期的）。类型可用于在编译时分配内存（例如10 * sizeof(int)，如果需要分配 a ，C 编译器将准确分配内存字节int[10]），但这不是完全必需的. 事实上，大多数 C 程序使用指针来存储数组，它们基本上是动态的。在处理指针时，编译器将生成/链接到代码，这些代码在运行时将执行必要的检查、重新分配等。但底线是动态和编译不被反对。Python 或 Lisp 解释器是已编译的程序，但仍可作用于动态值。事实上，汇编语言本身并没有真正的类型化，因为计算机可以对任何对象执行任何操作，因为它“看到”的只是位流和位操作。高级语言引入了任意类型和限制，以使事情更具可读性并防止您做完全疯狂的事情。但这只是为了帮助你，不是绝对的要求。

现在哲学咆哮结束了，让我们看看你的例子：

(setq x 60)
(setq y 40)
(+ x y)

让我们尝试将其编译为有效的 C 程序。一旦完成，C 编译器比比皆是，因此我们可以翻译 LISP -> C -> 机器语言，或几乎任何其他语言。请记住，编译只是翻译（优化也很酷，但可选）。

(setq

这分配了一个值。但是我们不知道什么分配给什么。让我们继续

(setq x 60)

好的，我们将 60 分配给 x。60 是一个整数文字，所以它的 C 类型是int. 由于没有理由假设x是另一种类型，这相当于 C：

int x = 60;

同样对于(setq y 40)：

int y = 40;

现在我们有：

(+ x y)

+是一个函数，根据实现的不同，它可以接受多种类型的参数，但我们知道它x是y整数。我们的编译器知道存在一个等效的 C 语句，即：

x + y;

所以我们只翻译它。我们最终的 C 程序：

int x = 60;
int y = 40;
x + y;

这是一个完全有效的 C 程序。它可以变得比这更棘手。例如，如果x和y非常大，大多数 LISP 不会让它们溢出，而 C 会，因此您可以将编译器编码为具有自己的整数类型作为整数数组（或任何您认为相关的）。如果您能够+在这些类型上定义通用操作（如），那么您的新编译器可能会将以前的代码转换为：

int* x = newbigint("60");
int* y = newbigint("40");
addbigints(x, y);

使用您的函数newbigint并addbigints在其他地方定义，或由编译器生成。它仍然是有效的 C，所以它会编译。事实上，你自己的解释器可能是用一些低级语言实现的，并且在它自己的实现中已经有 LISP 对象的表示，所以它可以直接使用这些。

顺便说一句，这正是Cython编译器对 Python 代码所做的：)

您可以在 Cython 中静态定义类型以获得一些额外的速度/优化，但这不是必需的。Cython 可以将您的 Python 代码直接翻译成 C，然后再翻译成机器代码。

我希望它使它更清楚！记住：

ALL 代码最终被解释
编译器将代码翻译成更容易/更快解释的东西。他们经常在此过程中执行优化，但这不是定义的一部分

compiler-construction - Lisp 如何既是动态的又是编译的？

2 回答 2

Related

Reference