Meaning of Machine in Compiler Theory

Question

Can anyone tell me what does "machine" means in Compiler Theory? Does it mean computer in general or operating system? Actually, the problem is I understand the definition of machine language as "the language understand by the computer". But does machine here refers to anything specific other than computer.

I was reading dragon book Compilers: Principles, Techniques, and Tools. In the class professor told that Java is both compiled and interpreted language. I didn't understand the definition so I referred to the book. I still don't get the following paragraph:

Java language processors combine compilation and interpretation, as shown in Fig. 1.4. A Java source program may first be compiled into an intermediate form called bytecodes. The bytecodes are then interpreted by a virtual machine. A benefit of this arrangement is that bytecodes compiled on one machine can be interpreted on another machine, perhaps across a network.

Answer 1

Machine is computer. But, the machine is not necessarily hardware.

Usually the machine is just hardware. If not, we speak of a virtual machine. Then the machine is software. The bottom line is that the machine executes software (a program).

Here it may start to become a little hazy because we have since long had interpreters, which we do not call virtual machines. So what is the difference? A virtual machine is software that executes the kind of software that was traditionally executed by hardware.

Java adds to the confusion because Java as a platform has a history. It started out as what you quote but grew into a compiled language over time, as it gained traction and people demanded better performance.

Answer 2

Can anyone tell me what does "machine" means in Compiler Theory? Does it mean computer in general or operating system? Actually, the problem is I understand the definition of machine language as "the language understand by the computer". But does machine here refers to anything specific other than computer.

In general, if you want to know what a specific term means in a specific context, or when used by a specific person, then you need to ask that person which used the term to provide a definition.

In Computer Science, like all science, a term means precisely what it is defined to mean, no more, no less.

If I were to give a very broad definition, that applies to all the different usages of the word in different subfields of CS, and all the different contexts, I would say that a machine is "something that can execute something". Now, that sounds very vague, and that is because it is very vague: the meaning of the term "machine" is very broad and might differ between different subfields of CS.

Just as an example: bot the C and the C++ language specification have as one of their core concepts the Abstract Machine. The specification describes how programs are executed by this Abstract Machine. It is the job of the programmer to write their C (or C++) programs against the rules and restrictions of this Abstract Machine. And it is the job of the compiler writer to ensure that operations of this Abstract Machine are correctly translated to operations on whatever concrete machine they are writing a compiler for, and that those operations behave the same.

This machine is not a real computer. It is not even a virtual machine. It is simply a mathematical / logical construct created purely for the purpose of specifying the behavior of the C (or C++) programming language. In fact, contrary to my own definition above, it doesn't really "execute something", it's more that it describes what would happen, if it were to execute something.

Actually, very programming language gives rise to an Abstract Machine for that language, even if the specification for that language does not explicitly describe one. (Likewise, every machine gives rise to a language in which programs running on that machine are expressed!)

Edit: I was reading dragon book Compilers: Principles, Techniques, and Tools. In the class professor told that Java is both compiled and interpreted language.

This is a terrible, terrible statement. It is so bad that it is Not Even Wrong. It is non-sensical.

There is no such thing as a compiled language or an interpreted language. Compilation and interpretation are traits of a compiler or an interpreter (duh!), not a programming language. Those two terms live on two different layers of abstraction. If English were a typed language, the term "compiled language" would be a Type Error!

Every language can be implemented by a compiler and every language can be implemented by an interpreter. Many languages have multiple implementations, and for many languages, some of those implementations are compilers and some are interpreters. For example, there are interpreters for C and C++, and there are compilers for ECMAScript, PHP, Python, and Ruby. In fact, all currently existing mainstream implementations of those four languages have at least one compiler, some even have multiple compilers.

Here's an example: the V8 ECMAScript execution engine developed by Google, which powers both Chrome and Node.js went through several revisions of its internal architecture. The first version was a pure compiler, it compiled ECMAScript directly to native machine code. This was an optimizing compiler that produced reasonably fast code while itself running reasonably fast as well.

The second iteration of V8 still compiled ECMAScript directly to native machine code, but it had two compilers: a fast compiler which produced slow code, and a slow compiler which produced fast code. The first compiler would compile the code quickly so that the application would start up fast; it would also inject profiling instrumentation into the compiled code. The second compiler would use the profiling information gathered while the program was running to then compile the sourcecode again to very highly optimized code.

After that, came an iteration that replaced the first compiler with an interpreter. Now, the code would start up being interpreted and then later compiled.

So: is ECMAScript a compiled language or an interpreted language? It should be obvious now that this term simply doesn't make sense, if the exact same piece of code executed by the exact same execution engine may at the same time both be interpreted and compiled! It should be clear that this has nothing to do with the language but rather with how a particular version of a particular implementation chooses to execute a particular piece of code.

I didn't understand the definition so I referred to the book. I still don't get the following paragraph:

"Java language processors combine compilation and interpretation, as shown in Fig. 1.4. A Java source program may first be compiled into an intermediate form called bytecodes. The bytecodes are then interpreted by a virtual machine. A benefit of this arrangement is that bytecodes compiled on one machine can be interpreted on another machine, perhaps across a network."

Again, this is a terrible, terrible way to describe it.

It is simply wrong. There is nothing in the Java Language Specification that says that Java must be compiled to JVM bytecode. And, in fact, there are implementations of Java that do not use JVM bytecode, such as the native compilation mode of (the now no longer maintained) GNU Compiler for Java. Actually, there is nothing in the JLS which says that Java must be compiled at all.

Likewise, there is nothing in the Java Virtual Machine Specification that says that JVM bytecode must be intepreted. In fact, all currently existing mainstream JVM implementations have at least one compiler. Excelsior.JET is a purely ahead-of-time compiled JVM implementation that has no interpreter and no JIT compiler. The early versions of the Maxine Research JVM were purely JIT compiled, they had no interpreter. (Although an interpreter was added later to improve performance.)

For a typical Java implementation, such as Oracle's JDK, the process is roughly as follows: the developer writes the program in Java. She then uses the Oracle javac Java compiler to translate the Java sourcecode to JVM bytecode. This JVM bytecode is what gets shipped to the users.

The user uses the Oracle HotSpot JVM to execute the JVM bytecode. The HotSpot JVM has multiple execution components: it starts out by interpreting the bytecode. Also, while interpreting, it collects statistics about the code. Using those statistics, it finds the parts of the code that are executed most often (the so-called "hot spots"). It compiles these hotspots into native machine code using the C1 JIT compiler. If there are very hot hot spots, it will at some point again compile those using the C2 JIT compiler. Also, both the C1 and the C2 JIT compiler are allowed to perform speculative optimizations that cannot be proven correct. If it turns out that one of those optimizations were illegal, the particular code in question gets "de-optimized", which basically means it gets thrown away, and the interpreter takes over again.

So, as you can see, the statement that "the bytecodes are interpreted" is a gross mis-characterization of what is actually happening. They may or may not be interpreted at the very beginning of the execution, depending on the exact JVM used, and they may or may not be interpreted later on, depending on whether they are hot or cold, and whether they get de-optimized or not. The exact same piece of code may flip back and forth between interpreted and compiled multiple times during a single run of the program.

Answer 3

@Martin's answer is correct — and allow me to expand on the subject.

But does machine here refers to anything specific other than computer.

In this context, machine refers to the interface and contract between the execution environment — often hardware itself — and the software that is trying to accomplish some higher level purpose (e.g. a program in Java or C# or other language).

The machine, represented by an Instruction Set Architecture, offers capabilities of storage, computation, and decision making, embodied in machine code or machine language, which is the language at the interface between the hardware and software.  An ISA specifies all the instructions that the machine is capable of.  These instructions are encoded in binary as numbers and they are interpreted (efficiently) by the hardware.

In the class professor told that Java is both compiled and interpreted language.

To execute, Java programs undergo two translation phases.

The first phase of translation of a java program is traditionally called compilation, and this compilation phase takes source code and translates it into Java byte code intermediate (class) format.  This format is machine code but for an abstract or theoretical machine called the JVM (Java Virtual Machine) rather than actual hardware (though some have endeavored to make hardware for the byte codes).

The JVM consumes the byte code representation of a program and runs it.  Some will call this interpretation, however, under the covers we will typically find a Just In Time Compiler (shortened as "JIT") that takes the byte code instructions and translates them into true hardware machine code instructions for the actual processor the JVM is running on.  While it is possible to interpret the byte code instructions, it is much more efficient (for loops and repeatedly called procedures) to perform translation of the byte codes into native hardware machine instructions (these translations are reused by the program's continued execution, whereas an interpreter will work to execute the byte codes directly without the reuse benefit of translation).

Java programs, with their intermediate Java byte code format, offer an independence from the hardware as compared with some other compiled languages, like C and C++.  Java could be a purely compiled language like C or C++, however some of its features benefit from the two stage compilation, in particular dynamic class loading and unloading.

C programs typically suffer a few extra instructions when using functions from different DLLs (dynamically loaded libraries) whereas Java programs usually don't (as a result of the second compilation phase that happens dynamically at runtime, it can optimize cross library calls and classes because the late phase JIT has more information).

C++ systems generally bake in so much knowledge of the classes into the compiled program that they don't support (C++) classes crossing DLL boundaries — the whole program is best recompiled if changes are made in even in what might seem to be isolated areas.

---

In Java's JIT system, dynamically loaded code is known to the JVM — the sizes of base classes and subclasses, the locations of methods are all well-known constants at the time of (just in time) code generation.  Whereas for C, locations of methods must be treated as variables since their values are not known until load time (and there is no secondary code generation phase to optimize code sequences).  C++, for efficiency, makes the assumption that sizes of base and subclasses, as well as field offsets are known at compile time and because machine code is generated this way, it this precludes Java-style dynamic class loading (in Java a base class can change size for a bug fix and only the relevant class file needs to be redistributed, not the whole application.)

Answer 4

The quote can be confusing because it uses "machine" in two slightly different ways. First it talks about the Java Virtual Machine (JVM) which executes the Java bytecode. In the last sentence it talks about the physical CPU which the JVM runs on. So Jave bytecode can indirectly be executed on different CPU's ("machines") because it is executed in a software virtual machine. Of course the JVM itself have to be compiled for different CPU's to make this possible.

A machine is just something which executes low-level code. This can be a physical CPU or a virtual machine implemented in software or even a purely theoretical construct like a Turing Machine. From a theoretical standpoint these are similar, since you can always emulate a physical processor in hardware and vice versa, even if it is impractical.

(An operating system is not typically considered a machine though since it doesn't directly execute code, it just provides some services for the CPU.)

Outside of compiler theory, machine typically just means computer.