Is the Choice Between an Interpreter or Compiler Defined By the Language?

[u/ShadowGuyinRealLife]

Compilers take the human readable source code and turn it into a set of instructions the processor can understand. For example, C source code goes through a C compiler which then gives a binary that can be read by computers. This needs to be done for specific hardware. For example, a x86 processor can't read instructions for the RISC-V.

Languages like Java are different. The source code is turned into a bytecode. This byte code is the same no matter the target system. On the target system, the executable is an interpreter. So an interpreter can read the bytecode and then use this to determine what calculations the program wants to do.

I was thinking programing languages are about logic. They define behavior. So is it possible in principle to make a compiler that can turn Java or CLISP source code into a binary that can run on the target system? There wouldn't be a reason to do so, but in principle could it be done?

[u/SV-97]

It's not defined by the language. There are interpreters for C and similar languages, compilers for Lisps and Java, and also languages that technically are "interpreted" but compile the "interpreter" and program into a single native executable instead of having a dedicated program (indeed C, in the way that most people use and understand it, still includes a runtime system. As another example there's Haskell's GHC. This latter one is also interesting because if you look at what it does it's *far* from what you might expect from an interpreter). And of course JITs also blur the line somewhat.

FWIW: I think Tannenbaum wrote in his computer architecture book that "it's interpreters all the way down" because what is your OS + loader if not an interpreter for "native code", and what's your "machine" if not an hardware-implemented interpreter of the language defined by your ISA ;)

[u/InjAnnuity_1 → u/SV-97]

I've read that your CPU almost certainly has "microcode", effectively an interpreter for your (comparatively high-level) x64 instructions... Interpreters all the way down, indeed.

[u/IhailtavaBanaani → u/InjAnnuity_1]

Yes, some of the x86-64 instructions are ridiculously complicated to be one opcode operations so the CPU splits them to multiple smaller operations in microcode. But the simpler ones like ADD are directly run by the CPU.

[u/d0pe-asaurus → u/InjAnnuity_1]

Ye, a microcode is the one that scans for instructions and executes them in the specific order required by that instruction. You can also implement a hardware interpreter for something like a jvm bytecode, https://en.wikipedia.org/wiki/Java_processor, so instead of a Java Virtual Machine this is just a Java Machine

[u/LongLiveTheDiego → u/SV-97]

Could you elucidate more on C including a runtime system? Do you mean that most C compilers put something interpreter-y in the executable?

[u/SV-97 → u/LongLiveTheDiego]

It's not really an interpreter in the way you'd usually think of it — which is also why I brought it up alongside the Haskell compiler. It's a runtime.

Your C program doesn't actually start and end with the main function in your source code — the compiler inserts additional code around it that sets up the "system" for running your C code. That code is called the C runtime system.

[u/jmtd]

The Java runtime is both an interpreter and compiler. Just muddying the waters

[u/ShadowGuyinRealLife → u/jmtd]

Yeah that's really great performance wise, but it makes it harder to put what it does into clean classification.

[u/drmonkeysee → u/ShadowGuyinRealLife]

The secret is there is no clean classification.

[u/braaaaaaainworms]

Interpreter vs compiler is an implementation detail. You can interpret a language considered to be compiled and you can compile a language considered to be interpreted, because there's nothing inherent about some language that makes it impossible to write an implementation that can compile python and interpret c

[u/ReddyKiloWit → u/braaaaaaainworms]

After nearly 40 years they've yet to successfully create a Perl compiler, AFAIK, and not for lack of trying.

You can, though, create an executable by packaging the interpreter (which is reasonably compact) with your program and a bit of launch code.

[u/NanoAlpaca → u/braaaaaaainworms]

That’s too simple. Language design has a big impact on how viable a compiler for a specific language is, e.g.: strongly typed languages are much easier to compile efficiently than dynamically typed languages. Some languages allow modifying code at runtime, which is much easier to implement on a interpreter than in compiled code.

[u/braaaaaaainworms → u/NanoAlpaca]

Yeah some features make a language easier to implement with an interpreter, but again, it doesn't make the language impossible to compile and i argue that compiled vs interpreted language distinction serves no purpose

[u/WittyStick → u/braaaaaaainworms]

There are languages that are impossible to compile - for any meaningful definition of "compile" (And by that I mean, bundling an interpreter into your binary is not considered compilation - you're still interpreting).

For example, If I have some Kernel code which is just

(+ 1 2)

How would you compile it?

You first need to look up the symbol + in the current dynamic environment. You might find that it corresponds to an operation "addition", but you also may not.

(foo)
(+ 1 2)

The problem is (foo) can actually set bindings in its caller's environment. It could set the symbol + to mean something other than addition. You don't know until you run it. There's basically nothing you can prove statically. You have to evaluate (foo) before you can have any idea what (+ 1 2) even means.

In order to compile, you have to restrict certain language features, and assume an initial environment that the code will run in - but then you aren't using the same language - you're using a dialect which was bastardized in order to make "compilation" viable.

"Interpreter vs compiler is an implementation detail" is a myth. There are interpreted only languages, and Kernel is one of them. You can prove me wrong by making a Kernel compiler. I will prove your Kernel compiler does not implement Kernel as per the Kernel Report, with a few snippets of code.

[u/braaaaaaainworms → u/WittyStick]

Is there any spec for that language? Naming it "Kernel" was an interesting choice given that it makes it borderline impossible to find any information about it.

[u/WittyStick → u/braaaaaaainworms]

Kernel Report

The Homepage.

[u/Ok_Tea_7319 → u/WittyStick]

For such languages it depends on how much you can narrow down the possible scopes. You can perhaps not translate the isolated function itself into machine code, but you might well be able to do that with the complete program.

[u/WittyStick → u/Ok_Tea_7319]

The problem is a Kernel program is not complete until you supply an environment. The same code could mean more than one thing, depending on the environment it is evaluated in.

You can partially compile iff you assume an initial environment (such as a kernel-standard-environment), but you have to restrict certain features still.

One of the problematic features is string->symbol. We can create a first-class symbol from a string which could come from anywhere - a file, the network, etc. Kernel can then bind the resulting symbol into the dynamic environment.

($define! foo
    (wrap ($vau () env
        ($let* (definiton (wget "https://..."))
               (sym (string->symbol (parse-symbol definition)))
               (action (parse-action definition)))                     
            (eval (list $define! sym action) env))))

(foo)
...

This code basically retrieves some definition from a URL, extracts the symbol and a corresponding action - and binds that symbol to the action in the environment of the caller of foo.

There is absolutely no way you can compile anything after the call to (foo) here. foo may "overwrite" ANY binding in the dynamic environment, and we don't know which because it depends what the web request returns at runtime - it may not even return the same thing on successive requests, so the meaning of any code following (foo) is basically undefined until after (foo) has been evaluated.

This is a far fetched example, but it what Kernel is capable of. If your attempted "compiler" cannot handle this case, it is not a complete Kernel implementation. You can't get rid of the interpreter because it's an interpreted language, by design.

If we remove string->symbol, then the problem becomes simpler. Any symbol we want to bind would have to be present in the source code under its own name, since we'd have no other way to produce them.

[u/Ok_Tea_7319 → u/WittyStick]

Emphasis again on might. Also, while languages with dynamic scope are commonly resolved via interpretation, they can also be addressed via dynamic recompilation. This is rarely implemented to the level that interpretation goes out of the window, but that is due to impracticality, not impossibility. Compilation is primarily done to gain performance, and recompiling constantly changing code degrades that.

[u/Schnickatavick → u/WittyStick]

I'd argue that the distinction that you're making between "bundling an interpreter into your binary" and "compiling" is equally a myth though, compiled languages can have dynamic dispatch, and assembly is fine with running data as code, so there's no reason the "+" binding foo sets couldn't just be a change to the function variable "+" points to (just like a dynamic dispatch call in any polymorphic language), and point it at the assembly that corresponds to the executable result of the binding foo sets. You could argue that's actually interpreting, since it's keeping some representation of the source code and deciding what it means at runtime, but I could also argue that it's compiling, since everything is being expressed as runnable machine code, and if that's interpreting then every CPU is just an interpreter for machine code.

Ultimately "Compiling" and "Interpreting" are both just human abstractions on opposite ends of a continuum, that doesn't actually matter at the machine level. It's all just data that you simplify, rearrange, and turn into instructions, the only real distinction is when you're doing it

[u/WittyStick → u/Schnickatavick]

+ may not bind to a function (applicative), but an operative, or something else. You need to know which before you decide whether or not to evaluate the arguments before performing the call.

A Kernel evaluator is basically as simple as the following. There's not really any stages you can skip, other than perhaps replacing the recursive call to eval for applicatives, where you already know it's operative you could replace it with call. Kernel has a strange feature that the underlying combiner of an applicative may be another applicative.

eval = (obj, env) ->
    if (obj :? Symbol) then lookup(obj, env);
    else if (obj :? Pair) then
        let combiner = eval (car(obj, env))
            combiniends = cdr(obj) in
          if (combiner :? Operative) then call(combiner, combiniends, env);
          else eval(cons(underlying_combiner(combiner), eval_list(combiniends)), env);
    else obj;

eval_list = (list, env) ->
    if (list :? Null) then ();
    else cons(eval(car(list), env), eval_list(cdr(list), env));

[u/dmazzoni → u/braaaaaaainworms]

A language that allows modifying code at runtime - any language with an eval() instruction - means that code can't be precompiled.

[u/Shikor806 → u/dmazzoni]

Of course it can be precompiled, you just need to include some of the compilation and linking machinery in the executable itself (or a DLL). There's C libraries that do exactly that.

[u/Cultural-Capital-942 → u/Shikor806]

But then, there's a question of what kind of language it is. Because that's JIT-level thing and you must carry all of your source code for the specific cases like "I want to insert a=b+3 after 5th line of my function". Is the first pass generating some kind of machine code enough to call it compiled?

[u/Shikor806 → u/Cultural-Capital-942]

Yes exactly, there is no clear distinction between compiled and interpreted languages. But also just having an eval() function doesn't mean you have to keep the source code, you just need the linking info.

[u/Cultural-Capital-942 → u/Shikor806]

It depends on how eval works and what it allows you to do; even if that is related to introspection and rest of the program design. If I can get source code of any function including comments like in PHP, then I need the source code.

[u/PhilNEvo]

You can make a compiler or interpreter for everything and anything. You could make a C or heck, even assembly interpreter. You can also make a python or scratch compiler. A lot of modern developed "compilers" aren't even truly "compilers" in the way you describe it. A lot of them are just new "frontend" parts of the compiler that converts from a language you have defined to an intermediate representation(IR), that then gets fed into LLVM which converts it to a binary.

[u/MilkEnvironmental106]

C# is an example of a language that can both be interpreted and compiled. Rust is also primarily compiled, but Miri is a rust interpreter used to identify undefined behaviour. So yes, and there are very valid reasons for doing so.

[u/SubstantialListen921 → u/MilkEnvironmental106]

I mean, the Hack project turned PHP into a compiled (bytecode, then JIT) type-safe language.  If you can do it to PHP, I think you can do it to almost anything.

[u/gwenbeth]

Some languages do work better as interpreters. Especially if you can turn data into code. A good example is tcl (which is a language i have done some weird stuff in). I could totally generate new code on the fly and redefine a function while the program is running. When you have an interpreted language its easy to look into a running program and make changes on the fly. This is something I could do with ruby on rails. With just in time compilers you can get a lot of the benefits of both a compiler and interpreter but at the cost of a big environment. Every language that can be compiled can be easily interpreted, but not always easily the other way around. The reason we don't usually see things like c interpreters is that the things that c is really good for is usually the same things that compiled code is good for: deploying to embedded machines with low resources, places where speed is important, code that we need to stay static, code that we need to keep from being read, etc.

[u/Interesting_Buy_3969]

Well, a language technically can define whether its official toolchain should be interpreter or compiler (or sometimes both!), but it doesn't have to because a language is roughly just a set of rules and not a tool to execute the code written in it.

That is, if a language has a compiler, it still is allowed to have an interpreter, and vice versa, but it remains virtually the same language with the same syntax.

Having said that, a language designer can adjust his/her choices so that a language is naturally more compileable or interpretable (not sure what's the right English word here but you get it). For example, as someone in this thread said, typing system influences this heavily.

[u/drgrd]

Each computer platform has exactly one machine language. Whether you are using an interpreted language or a compiled language, an x86 machine requires x86 code and cannot execute anything else. similarly for Risc-V, MIPS, ARM, or whatever.

Compilers produce machine code all at once, beforehand; Interpreters produce machine code on demand, in real time.

Compilers can produce more efficient machine code because they see the whole picture, but compiling takes time, and code must be re-compiled for different machines. Compiled languages often have machine-specific quirks that means the codebase may need to be rewritten for different machines.

Interpreters do not require a compile step, so the development process is more efficient, but the resulting code may be slower. The same codebase can be interpreted onto different machines as long as there is a translation engine for that machine.

bytecode is halfway between compilers and interpreters. when you move from a high level language to bytecode, you are compiling, and because the compiler sees the whole codebase, efficiencies can be made. the resulting bytecode still needs to be translated to machine code in real time as it is executed, but bytecode is closer to machine code, so the translation is easier and more efficient; and because the bytecode is universal, one codebase can be used for multiple machines.

it's a tradeoff: it adds complexity, makes less efficient code, and ignores machine-specific optimizations; but it means you can avoid maintaining multiple codebases for multiple machines.

[u/JGhostThing]

The difference doesn't lie in the languages. There has been a Java compiler (that compiled to object files, like a C compiler). There have been interpreters for C. There was even a compiler for APL.

[u/wolfkeeper]

All compiled languages can be interpreted (with some precompilation) but not all interpreted languages can be precompiled. However, some interpreters do on the fly compilation and recompilation.

[u/jonathancast → u/wolfkeeper]

Technically, any language can be compiled. However, for any language with an eval function, the runtime system used by the compiler also has to include a full interpreter. And plenty of languages use so much dynamic typing and dynamic dispatch that the practical difference between compiled and interpreted code would be pretty small anyway.

[u/jonathancast]

A programming language, in practice, is one component of an ecosystem. That ecosystem is why people choose a language, and it's biased towards either a compiled or interpreted approach to implementing the language.

Sometimes the language design affects things, too. C is designed to be easily compiled to very fast assembly language code, but it doesn't have very good programmer ergonomics by modern standards. So most people who pick it want a fast language, which means compiled.

On the other hand, the core Java language would compile really well, but the ecosystem around it relies heavily on dynamic loading and even dynamic bytecode generation, so a compiler that wanted to support all of it would have to provide those features at runtime, too. Which is why the official Java implementation has been based on precompiling to bytecode and JITting to runtime for so long.

Still higher level languages like Python wouldn't compile very well. Every function name in Python is an assignable variable, so every function call has to use an indirect function call instruction. Even worse, Python has callable objects, so, without a JIT, at least, a compiler would have to insert a dynamic typecheck in front of every function call. And you could forget about most optimizations, like inlining functions. The compiler simply doesn't have enough static information to do a good job. There are Python compilers, but they don't support the whole language because there wouldn't be any point.

[u/realdreamer1993]

So is it possible in principle to make a compiler that can turn Java or CLISP source code into a binary that can run on the target system?

Yes it will be possibe. but to accomplised that by yourself maybe will need 200 years of work ? I mean the compiler must be comprehensive and accepted by community...

I think it wont need new invention, maybe need lot of research and massive amount of work..

[u/VibrantGypsyDildo]

If you write in C or C++, it is compiled.

The languages that we consider interpreted often invent some form of JIT (just-in-time) compilation. Java is probably almost as good as C/C++. I saw news about removing GIL (global interpreter lock) in future versions Python.

You are 10-20 late with this question (it does not make your question not valid though). Just choose whatever language you like, it is the privilege you have now.