Can every language be compiled? And can every language be interpreted? [duplicate]

I was wondering whether every interpreted language can be compiled? And can every compiled language be interpreted?

Every language possible must support both compilation and interpretation by definition

The trick is in the underlying meanings of the idea of “compilation” and “interpretation.”

Interpretation is “take this program written in language X, and create a process which applies the rules of language X to the program.” It’s a fancy way of saying “interpretation is running the program.”

Compiling is take this program written in language X, and write a new program in language Y which, if interpreted, would create the same results as interpreting the program in X directly. It is a mapping operation from one language to another. It’s a fancy way of saying “take some time to make a program that, at a later time, would do what I wrote, but faster.”

Every language can be mapped to another language. If not, then the language cannot really run on computers. Thus every language can technically be compiled. And, since any compiled program can be written in the form “interpret the act of compiling the program, then interpret the result,” every program can be interpreted as well.

The line is even fuzzy with assembly. One assumes that x86 code is interpreted, because the job of a CPU is to interpret your instructions. However, in reality, x86 is too slow if interpreted literally. Instead, every modern CPU will compile x86 into its own “native” microcode. This means that literally every “interpreted” language gets compiled at some point.

Some languages are hard to compile or interpret

Some languages do not lend themselves well to compiling or interpreting. One expectation of a “good” language is speed. Slow languages tend to be less desirable than fast languages. C++ has rules which take advantage of the fact that it is traditionally compiled rather than interpreting. It has very slow rules (such as function overloading resolution) which compilers can bake down into very fast assembly (with simple fast rules). A naiive C++ interpreter would spend a great deal of time repeatedly doing these slow rules.

Likewise, some languages do not lend themselves well to compiling. Python, for instance, relies on duck-typing for everything. These rules are much faster than C++’s compiling rules, but slower than assembly’s rules. Compiling Python wouldn’t buy you much because you couldn’t map Python into anything much simpler.

… or could you?

If you look at PyPy, Psyco, or IronPython, there is an effort to compile Python. They do techniques known as Just in Time Compiling (JIT) to find bits of Python which do reward compiling. They compile those parts, while interpreting parts which are hard to compile. In many commonly-occuring cases, the result of using IronPython to JIT compile Python code is as fast or faster than C++ or C#!

This shows just how blurry the line between compiled and interpreted actually is.

Yes. As a trivial example we can make every compiled language interpreted by having the interpreter interpret assembly or whatever the compiled result is. Dually, we can bundle the whole interpreter + the program into one executable giving a “compiled” result.

You didn’t say “compiled well” 🙂

It depends on your definitions of interpreted and compiled.

For example I recall that Perl has certain constructs that can only be interpreted at runtime, which makes it impossible to compile.

On the other hand interpretation usually implies that you don’t get to parse all the source code before the program is started. I cannot come up with an example from the top of my head, but I wouldn’t be surprised if this means some languages have to be compiled.

Finally it’s unclear how such features as source code generation (e.g. Lisp meta programming, C macros, Eclipse EMF) and bytecode manipulation (e.g. AspectJ) should fit into this picture.

For a C program there’s no reason the compiler can’t be wrapped in about the follow two lines:

cc -g source.c
./a.out

Which makes it pretty interpreted. I added the -g to emphasize that it’s possible to keep C code close to the source.

And any interpreted language can be compiled for efficiency. Javascript can be uglified. Python drops those lovely .pyc files.

In short: the dichotomy you have been taught is nonsense. Programming languages exist on the entire spectrum from native code to virtual machine code to DSLs that you can write in Java or Scala to interpreted chains of compiled code feeding into each other, which is precisely the Unix philosophy (and any Bash script).

Languages described as interpreted tend to not have “compile” time errors. But then there’s lint collectors which may as well be built into the compiler and halt if an error happens, much in the style of my toy code above.

Perhaps interpreted means more “dynamic,” which just means fewer things cause compile errors or runtime errors. But even a language like Java, which people call stricter, can load malformed classes and throw runtime errors.

And a “compiled” language like C compiles into assembly/machine code. And what is machine code if not code that is interpreted by the CPU? Compiled code has to land somewhere.

Which is just the same process that the Java compiler goes from Java source to Java bytecode, which is intepreted by the JVM in much the same way Python code is interpeted by the Python runtime. So we have a compiled language compiling into an interpreted one which runs on a virtual machine that is programmed in a native language (C++).

And of course toy languages like brainfuck you can implement in Java or C or Ruby, and they’re simple enough you can write them in assembly just as an exercise in learning assembly. But then again Ruby can be put on the JVM via JRuby, which makes Ruby a lot more like a compiled language.

Get it yet?

Filed under: softwareengineering - @ 21:37

Thẻ: compiler, interpreters

Thiết kế website giá rẻ

Danh mục

Can every language be compiled? And can every language be interpreted? [duplicate]

Every language possible must support both compilation and interpretation by definition

Some languages are hard to compile or interpret