The Stack Overflow podcast is back! Listen to an interview with our new CEO.
61

The distinction between interpreted and compiled code is probably a fiction, as underlined by Raphael's comment: the claim seems to be trivially wrong without further assumptions: if there is an interpreter, I can always bundle interpreter and code in one executable ... The fact is that code is always interpreted, by software, by hardware or a combination ...


17

The question is not actually about compilation being impossible. If a language can be interpreted¹, then it can be compiled in a trivial way, by bundling the interpreter with the source code. The question is asking what language features make this essentially the only way. An interpreter is a program that takes source code as input and behaves as specified ...


13

I think the authors are assuming that compilation means the source program doesn't need to be present at run-time, and no compiler or interpreter needs to be present at run-time. Here are some sample features that would make it problematic if not "impossible" for such a scheme: If you can interrogate the value of a variable at run-time, by referring to ...


8

it is possible the current replies are "overthinking" the statement/ answers. possibly what the authors are referring to is the following phenomenon. many languages have an "eval" like command; eg see javascript eval and its behavior is commonly studied as a special part of CS theory (eg say Lisp). the function of this command is to evaluate the string in ...


8

Depending on the language, there can be many development challenges: Pointers: If a language doesn't have pointers, it will be a challenge to do relatively-easy tasks. For example, you can use pointers to write to VGA memory for printing to the screen. However, in a managed language, you will need some kind of "plug" (from C/C++) to do the same. Assembly: ...


8

Yes, it is certainly possible. There are compilers that will compile from code to circuits. Classic examples would be VHDL or AHDL compilers, but you can certainly do this for any other language, to the extent that you have an upper bound on the running time of the program or that you have an upper bound on the memory use of the program and are willing to ...


7

"Scripting" languages are typically interpreted, not compiled. That means that there will be a program called the "interpreter" for that language, which reads the programs written in the language, and executes them. You can start reading about interpreters from the Wikepedia entry: http://en.wikipedia.org/wiki/Interpreter_(computing) A compiler, on the ...


7

No, and yes. The answer is "no", in the sense that the vast majority of computers have no hardware that does what you typically expect a compiler to do; compilers are written in software. Obviously this ultimately runs on hardware, but we're talking general-purpose hardware. However, the answer is "yes", in the sense that the machine code that is actually ...


7

If the stack machine is only allowed to access the top of the stack, and apart from the stack it only has a finite amount of storage, then it's a pushdown automaton. Pushdown automata are not Turing-complete; non-deterministic pushdown automata can only recognize context-free languages, and deterministic ones even less. With two stacks, such that the ...


7

I'm not aware of anything exactly like this, but there are some things that are arguably related. For specifically sorting this is related to the Schwartzian transform, though with a very different goal. In the Schwartzian transform, you run through the input applying an expensive function and pairing the input and output together, then sorting on the ...


6

Scripting languages are a class of programming languages. This class is rather fuzzily defined. One possible definition is that they're languages that are designed to automate small tasks, rather than to write large, complex programs. Because they are small tasks, the author tends to spend some time tweaking them, so it makes sense to make the path from ...


5

I believe most interpreted regular expression matchers start with Thompson's construction algorithm to turn the regular expression into a non-deterministic finite automata. The article that first described these is: Ken Thompson, "Programming Techniques: Regular expression search algorithm", Communications of the ACM, 11(6):419-422, June 1968. But that ...


5

I have heard it claimed (by a researcher working on a competing microkernel technique) that very little is known about how to evaluate security of systems that are extensible through managed code. The problem is that the kinds of bugs that might cause a security hole are very different than security researchers are used to. In a traditional microkernel all ...


4

Yes and no. Yes, you could structure a compiler this way, but most of the benefits you are hoping for would not materialize. There may be some benefits, such as a powerful compile-time meta-language. There are also costs like a complete loss of the ability to make meaningful guarantees about code that isn't completely self-contained (e.g. takes in objects ...


3

You are confusing stack-oriented programming languages (resp. their interpretation model) with pushdown automata. The former can be Turing-complete because they can access an (infinite) random-access memory; the latter does not have any memory but the (one) stack. The description of your machine (model) is not very clear. I think you can decide its power on ...


3

It depends on what you mean by "crucial", "feasible", and "interpreted." Certainly applications which many people consider to be crucial are written in C# and Java, so in some sense the answer to your question must be "Yes." But we can try to dig a little deeper. While it is true that Java and C# are both compiled into byte code, in general the byte code ...


3

LISP is a terrible example, as it was conceived as a sort of higher-level "machine" language as a base for a "real" language. Said "real" language never materialized. LISP machines were built on the idea of doing (much of) LISP in hardware. As a LISP interpreter is just a program, it is in principle possible to implement it in circuitry. Not practical, ...


3

That depends on a lot of factors. If it is a pure interpreter (like most shells), the interpreter reads each line/instruction, analyzes it, and executes it. If it is a pure compiler, the program (or a part of it) is read in, analyzed, and then the machine language is written out to run later. Many programming languages are implemented by compiling into a ...


3

It depends on how the language is defined. Language might be statically typed (like e.g. C, Java, Haskell, ...) or dynamically typed (like e.g. Python, Common Lisp, ...). In a statically typed language every expression has associated value and the semantic analyser checks whether the types match just after when the expressions are parsed. In a statically ...


3

I think the implication of your Tanenbaum quote is that there is no compiler for L1. In which case yes, the interpreter does have to be written in another language (how else would you run the interpreter?).[1] It doesn't have to be lower-level; you could write an interpreter for Haskell in ML, say, or vice-versa. You usually want to use a lower-level ...


2

Your understanding of the complexity of a switch or case statement is not correct. In most languages these statements make a decision based on the value of a single integer variable. If those integers are densely packed together (as they typically are when an interpreter is decoding an instruction opcode) then the compiler turns this into an $O(1)$ lookup ...


2

That sounds like a fine way to start, and you'll become familiar with the issues involved. How's it going? At a certain point, consider learning more about programming language implementation techniques from a book like Compilers: Principles, Techniques, and Tools (2nd Edition) open courseware for MIT's Computer Language Engineering course a MOOC like ...


2

The output of an interpreter is not a program in any language. An interpreter executes the input program. Its output is the program's output. In contrast, a compiler produces a program in some assembly language, for an actual or a virtual computer (for example, Java compilers generate code for the Java virtual machine). When writing interpreters, you don't ...


2

Interpreted languages are used because of their simplicity. A compiler will assemble all the parts and link them together as an executable. If there is a bug in any one of the parts the build will fail and there will not be any executable to run (missing symbols, missing libraries, incompatible libraries, etc). Also compiled programs often need to ...


2

Not in any straightforward way, because a tree transducer only accepts a single input, while an interpreter needs two inputs. An interpreter needs two inputs: a transducer $R$ and a tree $T$, and would output the $R(T)$. But a tree transducer can only accept one input. Consequently, there appears to be no way to build such an interpreter (unless you ...


2

As concluded via non-direct means in discussion interpreting a polytime program cannot be done in polynomial time in general. The following example shows this directly. The trick is that for the interpreter to run in polynomial time there must be an polynomial that bounds the running time for every input. This pretty obviously isn't going to hold for System-...


2

A literal is a piece of data which gets its value at compile time. I don't think that's a good definition of literals. A literal is a source-code token that represents a fixed value of some type. For example, in almost all programming languages, 23 is a literal representing the integer twenty-three. These aren't pieces of data that get their value at ...


2

It's a perfectly valid grammar, and it's certainly LL(1). But since it only generates three sentences, it's probably not what you are looking for. The three sentences: a < a a | a a / a For precision: As written, it's not quite correct. In order to achieve what I imagine you meant by the FIRST sets, you'd actually need to he a bit more precise. Instead ...


1

If a language can interpret itself then it is not total I take this to mean that if there is a universal machine for a class in the class itself, the class can not be total (i.e. there have to be non-total functions in the class). What you probably have in mind is that the class can not be the class of all total computable functions since we know that one ...


1

I know you mean, it is not an easy task, yet you can do it. For point 1: You can do that by: Quick reading the documentation of the programming language you want to learn. Practice on the topics you want to get the maximum benefits of. Mainly all of the programming languages have a lot of common specs, you can map the language you want to learn to a ...


Only top voted, non community-wiki answers of a minimum length are eligible