289
votes
Accepted
How can a language whose compiler is written in C ever be faster than C?
There is no necessary relation between the implementation of the compiler and the output of the compiler. You could write a compiler in a language like Python or Ruby, whose most common ...
- 3,108
104
votes
Accepted
Why are some programming languages "faster" or "slower" than others?
In programming language design and implementation, there is a large number of choices that can affect performance. I'll only mention a few.
Every language ultimately has to be run by executing machine ...
- 14.4k
101
votes
How can a language whose compiler is written in C ever be faster than C?
How can a machine built by a man be stronger than a man? This is exactly the same question.
The answer is that the output of the compiler depends on the algorithms implemented by that compiler, not ...
- 81.4k
94
votes
How can a language whose compiler is written in C ever be faster than C?
I want to make one point against a common assumption which is, in my opinion, fallacious to the point of being harmful when choosing tools for a job.
There is no such thing as a slow or fast language....
- 71.9k
86
votes
Accepted
Why don't compilers automatically insert deallocations?
Because it's undecidable whether the program will use the memory again. This means that no algorithm can correctly determine when to call free() in all cases, which ...
- 81.4k
58
votes
Why don't compilers automatically insert deallocations?
As David Richerby rightly noted, the problem is undecidable in general. Object liveness is a global property of the program, and may in general depend on the inputs to the program.
Even precise ...
- 21.3k
57
votes
Proof that dead code cannot be detected by compilers
It all comes from undecidability of the halting problem. Suppose we have a "perfect" dead code function, some Turing Machine M, and some input string x, and a procedure that looks something like this:
...
- 29.6k
57
votes
Are there programs that can 'translate' source code between any two languages?
TLDR; this is possible but not practical.
(assuming the translator has access to the requisite libraries)?
This ends up being the tricky bit, and is part of why things like this don't end up being ...
- 29.6k
57
votes
Accepted
Why are ambiguous grammars bad?
Consider the following grammar for arithmetic expressions:
$$
X \to X + X \mid X - X \mid X * X \mid X / X \mid \texttt{var} \mid \texttt{const}
$$
Consider the following expression:
$$
a - b - c
$$
...
- 274k
43
votes
Accepted
What is a batch compiler?
A JIT (Just-In-Time) compiler compiles code at run-time, i.e. as the program is running. Therefore the cost of compilation is part of the execution time of the program, and so should be minimized.
...
33
votes
Accepted
How do computers remember where they store things?
I'd suggest you look into the wonderful world of Compiler Construction! The answer is that it's a bit of a complicated process.
To try to give you an intuition, remember that variable names are ...
- 29.6k
33
votes
Accepted
Assembly writer vs compiler in VLIW architecture
The "assembly writer" in that book is a human software developer who writes code in assembler language.
- 27.8k
32
votes
Accepted
Would it be wrong to say that the processor (and hardware) is the implementation of an interpreter for machine language?
It's not such a bad way of looking at things.
On most modern CPUs, the instruction set architecture (ISA for short) is abstract, in the sense that it doesn't dictate that it must be implemented using ...
- 21.3k
30
votes
Why don't compilers automatically insert deallocations?
It's an incompleteness problem, not an undecidability problem
While it's true that the optimal placement of deallocation statements is undecidable, that's simply not the issue here. Since it's ...
- 1,341
24
votes
How do computers remember where they store things?
When a computer stores a variable, when a program needs to get the variable's value, how does the computer know where to look in memory for that variable's value?
The program tells it. Computers do ...
- 1,685
24
votes
Why don't compilers automatically insert deallocations?
Currently, none of the posted answers are fully correct. It's not impossible to do this, but adding that feature would restrict mermory allocation patterns.
Why don't compilers automatically insert ...
- 396
23
votes
How can a language whose compiler is written in C ever be faster than C?
There is one forgotten thing about optimisation here.
There was longish debate about fortran outperforming C. Putting apart malformed debate: the same code was written in C and fortran (as testers ...
- 9,385
20
votes
Why are some programming languages "faster" or "slower" than others?
What governs the "speed" of a programming language?
There is no such thing as the "speed" of a programming language. There is only the speed of a particular program written by a particular progammer ...
- 5,821
18
votes
Accepted
What is the name of this type of program optimization where two loops operating over common data are combined into a single loop?
It's called "loop fusion".
It's often more efficient, in the sense of doing more work per loop iteration and sometimes (as you say) other advantages. On the other hand, the fused loop in ...
- 21.3k
16
votes
Accepted
Why is static-single assignment preferred over continuation passing style in many industry-used compilers?
I imagine many compiler implementers for typical imperative languages simply weren't that familiar with CPS and CPS-based compilation techniques. In the functional programming community both CPS and ...
15
votes
Accepted
What property of cons allows elimination of tail recursion modulo cons?
While GCC likely uses ad-hoc rules, you can derive them in the following way. I'll use pow to illustrate since you're foo is so ...
14
votes
Proof that dead code cannot be detected by compilers
This is a twist on jmite's answer that circumvents the potential confusion about non-termination. I'll give a program that always halts itself, may have dead code but we can not (always) ...
- 71.9k
14
votes
Accepted
Do we create a programming language by writing a compiler?
The short answer is no.
You can think of a programming language as a mathematical formalism used for expressing computation. A compiler/interpreter is a just a piece of an actual software that ...
- 1,644
13
votes
What is a batch compiler?
The meaning is implied within the quote you give! It stems from the computing term batch processing which is used when the task is not performed in real-time, but it scheduled for later execution by ...
- 1,833
13
votes
Accepted
Finite State Automata Within A Compiler
What you have asked: "Do I need to understand more than this to write a compiler?" then answer is basically, No - but it does depend on the compiler!
You need to know a lot of theory about a lot of ...
- 1,833
13
votes
Why are ambiguous grammars bad?
In contrast to the other existing answers [1, 2], there is indeed a field of application, where ambiguous grammars are useful. In the field of natural language processing (NLP), when you want to parse ...
- 438
13
votes
Do you ever "download" a language?
A programming language is a formal language, informally speaking a collection of words with a well-formed set of specific rules. As such, you can write down the definition of a formal language and ...
- 22.4k
13
votes
Accepted
Break keyword outside a loop is syntax error or semantic error?
Both work, so how you do it is up to you. But there are a couple of reasons to consider doing it during a post-parse analysis:
While it is certainly possible to define two different types of ...
- 11.8k
12
votes
How can a language whose compiler is written in C ever be faster than C?
The previous answers give pretty much the explanation, though mostly
from a pragmatic angle, for as much as the question makes sense, as excellently explained by Raphael's answer.
Adding to this ...
- 19.4k
Only top scored, non community-wiki answers of a minimum length are eligible