Lisp如何既动态又编译？

Question

好的,首先要解决这个问题:我已经阅读了以下答案:

Lisp是如何动态编译的？

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

在像Python这样的语言中,表达式为:

x = a + b

无法真正编译,因为"编译器"不可能知道a和b的类型(因为类型只在运行时知道),因此如何添加它们.

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

那怎么做:

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

工作？

编译被定义为本机提前编译.

编辑

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

编辑2

经过大量研究(即狂热的维基百科浏览),我想我理解以下内容:

• 动态类型语言是在运行时检查类型的语言
• 静态类型语言是在编译程序时检查类型的语言
• 类型声明允许编译器使代码更有效,因为它不是一直进行API调用而是可以使用更多的本机"函数"(这就是为什么你可以为Cython代码添加类型声明来加速它,但是没有to,因为它仍然只能在C代码中调用Python库)
• Lisp中没有数据类型; 因此没有要检查的类型(类型是数据本身)
• Obj-C有静态和动态声明; 前者在编译时进行类型检查,后者在运行时进行

如果我在上述任何一点上错了,请纠正我.

Answer 1

示例代码:

(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)或在某些类型的溢出时发出信号错误.您还可以告诉编译器省略它,只使用本机整数.那么你的代码会更快 - 但不像普通代码那样安全和灵活.

这是使用64Bit 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提供

• 编译代码的两个标准函数:编译和编译文件
• 一个标准函数来加载源代码或编译代码:load
• 一个标准函数来反汇编代码:反汇编

Answer 2

编译是从一种语言到另一种语言的简单翻译.如果你能用语言A和语言表达同样的东西B,你可以用语言A将这种用语言​​表达的东西编译成同样的东西B.

一旦用某种语言表达了你的意图,就会通过解释来执行.即使在使用C或其他编译语言时,您的陈述是:

1. 翻译自C - >汇编语言
2. 从汇编翻译 - >机器码
3. 由机器解释.

计算机实际上是一种非常基本的语言的翻译.由于它是如此基础和如此难以使用,人们提出了更容易使用的其他语言,并且可以很容易地翻译成机器代码中的等效语句(例如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 int[10],C编译器将精确分配内存字节),但这并不是完全必需的.事实上,大多数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,然后转换为机器代码.

我希望它能让它更清晰!记得:

1. 最终解释所有代码
2. 编译器将代码转换为更容易/更快解释的代码.它们通常在整个过程中执行优化,但这不是定义的一部分