是否有可能创建一种通用的中间编程语言?

Is it possible to create a universal intermediate programming language?

我的意思是,是否有一种语言或者可以设计一种语言,使得所有高级编程语言都可以编译成这种中间语言?

这不包括机器语言。

每一种 Turing-complete 的通用语言都是通用编程语言。

如果两种语言(或机器)的任何程序都可以编译成另一种的程序,则这两种语言(或机器)被认为是图灵等价的。如果一种语言与图灵机等价,则该语言是图灵完备的。

为了形式化计算的概念,早期进行了几次尝试;图灵机是一个,lambda 演算是另一个,一般递归函数的 class 第三个。 Alonzo Church 和 Alan Turing 证明了所有这三种形式化都是图灵等价的;图灵机的任何程序都可以编译为 lambda 演算,反之亦然,因为任何一般递归函数都可以由 lambda 演算或图灵机实现,反之亦然。

Church-Turing thesis 假设可以在任何形式系统中表达的任何计算都可以转换为可以在图灵机上 运行 的程序;或等效地,可以在无类型的 lambda 演算中表示,或者是一般递归的,基于上述等价性。

这只是一个假设,无法得到正式证明,因为无法正式描述受其影响的 class 计算(没有循环推理,将它们定义为 class 可以由图灵机执行的计算),但从来没有提出过任何无法用图灵机计算的计算模型。

因为您可以用几乎任何通用语言编写图灵机模拟器(或 lambda 演算的实现),同样,这些语言可以编译为图灵机上的程序 运行ning,几乎所有通用语言都是图灵完备的。

但是,有些语言不是图灵完备的;正则表达式就是一个例子。它们可以用图灵机模拟,但它们不能反过来模拟图灵机。

请注意,none 这涉及效率或对主机系统资源的访问;只是可以表达相同的计算,并且它最终会提供相同的答案。有些语言是图灵完备的,但其中存在一些 cannot be computed at the same asymptotic efficiency as in other languages 的问题。有些语言提供对外部资源的访问,如文件系统、I/O、网络等,而其他语言只允许在内存中进行计算,但在任何图灵完备的语言中,都可以添加一个 API 或操作内存的方法允许它访问这些外部资源,因此无法访问系统资源不是根本限制,只是实现的限制。

作为一个更实际的问题,有几种语言被设计为可移植的中间语言,它们是编译的目标。 LLVM IR is one commonly used example, C-- is another. Also, any bytecode for a language runtime acts this way, the JVM is a compilation target for many languages, the CLR 是另一个。最后,许多语言都编译为 C,因为 C 编译器广泛可用并且代码比机器代码更可移植。

最近,随着网络的出现以及 JavaScript 成为一种可在每个网络浏览器中使用的语言,JavaScript 已成为流行的编译目标,这两种语言都是旨在像 CoffeeScript and Dart, but also existing languages that were originally design to compile to machine code, via projects like Emscripten. Recognizing this usage, there has been effort to specify a subset of JavaScript, with more strict rules, known as asm.js 一样向下编译为 JavaScript,这为编译提供了更好的目标,同时仍然允许相同的代码向后兼容与不知道任何事情的常规 JavaScript 引擎关于 asm.js.