3 ms·

I'm aware, but it really doesn't make any difference. The BCPL compiler, an early example of a retargetable compiler, itself featured an early example of an IR

I'm aware, but it really doesn't make any difference. The BCPL compiler, an early example of a retargetable compiler, itself featured an early example of an IR based on a VM [0]: OCODE [1]. In "BCPL: The Language and Its Compiler", Martin Richards, the creator of BCPL, describes OCODE: > The intermediate form for BCPL is called OCODE, and follows this pattern. ... It can be regarded as the assembly language of a simple abstract machine for BCPL. That sounds rather similar to LLVM to me! Richards then goes on to describe a stack machine and its instruction set, giving examples of how snippets of BCPL will look after the front end has finished generating the IR assembly language. He also discusses optimization concerns in the back-end as transformations on the instruction stream, and finally native code generation from the result. Point is, whether the VM instructions get interpreted or further translated has no bearing on the fact that they represent instructions for some machine. That doesn't interfere with the VM code's ability to serve as an intermediate language. Do note, however, that not all IRs are defined in terms of an abstract machine (last I checked, admittedly quite some time ago, GCC's was not, for example). Even in the case that a VM was intended to function via bytecode interpretation, it is still possible to treat its code as an IR. For example, Google has done this on Android for some time now: when an application is installed from the app store, the system AOT-compiles the Dalvik bytecodes into native code. Of course, some machines are better-suited for native-code translation than others, but translation is always possible regardless. [0]: I continue to follow common practice here and use "VM" as a synonym for either virtual machine or abstract machine; the distinction between the two is unimportant here. Also, I'm lazy and "VM" is fewer keystrokes. Wait, did I just obviate those savings with this footnote? Eh, who cares :) [1]: I'd mistakenly written "O-code" in my previous comment, but looking through Martin Richards's book now, I see that he in fact called it "OCODE".

ZenoArrow 10y ago
> "I continue to follow common practice here and use "VM" as a synonym for either virtual machine or abstract machine; the distinction between the two is unimportant here." The distinction between them is important. If you want definitions that separate the two, virtual machines rely on runtime emulation of said machine, abstract machines are machines that only exist as a specification. You may not like those definitions but they line up with common uses for these terms. If you want to argue that intermediate representations that compilers use for optimisations can be virtual machines go ahead, but to me that waters down the definition of what a virtual machine is.
- groovy2shoes 10y ago
  You're trying to draw a line between them, but there is no line. Virtual machines are abstract machines, but not necessarily the other way around. The most common distinction I've seen, when a distinction has been made at all, is that a virtual machine is either 1) a software simulation of a physical machine; or 2) a software simulation of an abstract machine (as is the case for the JVM, for example). More often, though, I've witnessed the terms be used interchangeably. Case in point, in the example of OCODE, the BCPL machine does not exist only as a specification -- OCODE had both an interpreter and a multitude of native-code translators by the time the book was published -- yet Richards refers to it as an abstract machine. Frontends for the Amsterdam Compiler Kit (ACK) by Andrew Tanenbaum (once the native compiler toolchain for MINIX -- I'm not sure if that is still the case) have an IR analogous to OCODE called EM, but the papers describing it refer to it as code for a virtual machine, rather than as code for an abstract machine as Richards described it. Your definition is not incompatible with the definition I give above. By such a definition, any abstract machine will immediately become a virtual machine as soon as someone implements the specification. In my mind, that makes the distinction even less important, as the only thing standing between the two is someone spending a few hours writing code. I get a feeling that the two terms likely originate from two independent discoveries of the same concept, but I'm not that well-versed in their history. > If you want to argue that intermediate representations that compilers use for optimisations can be virtual machines go ahead, but to me that waters down the definition of what a virtual machine is. First, not every intermediate representation constitutes code for an abstract/virtual machine. There are high-level IRs where it would be a bit of a stretch to specify a machine which directly accepts that code. An example is code where the only translation has been to expand derived forms (for example, macro expansion). This code is technically in IR, but often remains at nearly the same level as the original code. Another example might be the CPS representation commonly used by Scheme compilers (among others), though I'm willing to bet an abstract machine could be described for such code. Typically, the IR intended to be fed into a code generator will be suitable for simulation by an abstract machine. Second, the IR itself is not a virtual machine. The IR represents code for an abstract/virtual machine. This is necessarily the case because the IR must preserve the meaning of the program it represents, and the execution of the program involves the operation or simulation of some machine [0]. It is then the case that, so long as the IR is too low-level to qualify as a high-level programming language (and in some other cases regardless, see above), the IR represents code for an abstract machine, and vice versa. The LLVM IR qualifies. [0]: This follows from the Church-Turing thesis coupled with the fact that the programs are intended to eventually be executed by machine. It then follows that any time a representation of the program is lowered into a lower-level representation, its description becomes more suitable for direct execution by some machine.

ZenoArrow 10y ago

> "I continue to follow common practice here and use "VM" as a synonym for either virtual machine or abstract machine; the distinction between the two is unimportant here." The distinction between them is important. If you want definitions that separate the two, virtual machines rely on runtime emulation of said machine, abstract machines are machines that only exist as a specification. You may not like those definitions but they line up with common uses for these terms. If you want to argue that intermediate representations that compilers use for optimisations can be virtual machines go ahead, but to me that waters down the definition of what a virtual machine is.

groovy2shoes 10y ago
You're trying to draw a line between them, but there is no line. Virtual machines are abstract machines, but not necessarily the other way around. The most common distinction I've seen, when a distinction has been made at all, is that a virtual machine is either 1) a software simulation of a physical machine; or 2) a software simulation of an abstract machine (as is the case for the JVM, for example). More often, though, I've witnessed the terms be used interchangeably. Case in point, in the example of OCODE, the BCPL machine does not exist only as a specification -- OCODE had both an interpreter and a multitude of native-code translators by the time the book was published -- yet Richards refers to it as an abstract machine. Frontends for the Amsterdam Compiler Kit (ACK) by Andrew Tanenbaum (once the native compiler toolchain for MINIX -- I'm not sure if that is still the case) have an IR analogous to OCODE called EM, but the papers describing it refer to it as code for a virtual machine, rather than as code for an abstract machine as Richards described it. Your definition is not incompatible with the definition I give above. By such a definition, any abstract machine will immediately become a virtual machine as soon as someone implements the specification. In my mind, that makes the distinction even less important, as the only thing standing between the two is someone spending a few hours writing code. I get a feeling that the two terms likely originate from two independent discoveries of the same concept, but I'm not that well-versed in their history. > If you want to argue that intermediate representations that compilers use for optimisations can be virtual machines go ahead, but to me that waters down the definition of what a virtual machine is. First, not every intermediate representation constitutes code for an abstract/virtual machine. There are high-level IRs where it would be a bit of a stretch to specify a machine which directly accepts that code. An example is code where the only translation has been to expand derived forms (for example, macro expansion). This code is technically in IR, but often remains at nearly the same level as the original code. Another example might be the CPS representation commonly used by Scheme compilers (among others), though I'm willing to bet an abstract machine could be described for such code. Typically, the IR intended to be fed into a code generator will be suitable for simulation by an abstract machine. Second, the IR itself is not a virtual machine. The IR represents code for an abstract/virtual machine. This is necessarily the case because the IR must preserve the meaning of the program it represents, and the execution of the program involves the operation or simulation of some machine [0]. It is then the case that, so long as the IR is too low-level to qualify as a high-level programming language (and in some other cases regardless, see above), the IR represents code for an abstract machine, and vice versa. The LLVM IR qualifies. [0]: This follows from the Church-Turing thesis coupled with the fact that the programs are intended to eventually be executed by machine. It then follows that any time a representation of the program is lowered into a lower-level representation, its description becomes more suitable for direct execution by some machine.