284
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,058
103
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.1k
100
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 ...
- 80.1k
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....
- 70.8k
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 ...
- 80.1k
64
votes
Accepted
What properties of a programming language make compilation impossible?
The distinction between interpreted and compiled code is probably a
fiction, as underlined by Raphael's comment:
...
- 19.1k
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.1k
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.1k
57
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 ...
- 18.8k
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
$$
...
- 269k
53
votes
Accepted
Time complexity of a compiler
The best book to answer your question would probably be: Cooper and Torczon, "Engineering a Compiler," 2003. If you have access to a university library you should be able to borrow a copy.
In a ...
- 17.3k
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.
...
- 11.8k
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.
- 24.9k
32
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.1k
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,331
30
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 ...
- 18.8k
26
votes
Accepted
What determines the "speed" of a programming language?
There are many reasons that may be considered for choosing a language
X over a language Y. Program readability, ease of programming,
portability to many platforms, existence of good programming
...
- 19.1k
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 ...
- 860
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,325
23
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 ...
- 356
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,096
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 ...
- 18.8k
17
votes
Time complexity of a compiler
Actually, some languages (like C++, Lisp, and D) are Turing-complete at compile time, so compiling them is undecidable in general. For C++, this is because of recursive template instantiation. For ...
- 509
17
votes
What properties of a programming language make compilation impossible?
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 ...
16
votes
What determines the "speed" of a programming language?
While everything is eventually run on the CPU*, there are various differences between different languages. Here are some examples.
Interpreted languages Some languages are interpreted rather than ...
- 269k
14
votes
Accepted
Why separate lexing and parsing?
You don't have to separate them. People combine them into scannerless parsers.
The key disadvantage of scannerless parsers appears to be that the resulting grammars are rather complicated -- more ...
- 8,168
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) ...
- 70.8k
14
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 ...
- 11.8k
13
votes
How does an operating system implement the C library?
It's hard to give a full answer to this question, as it would basically amount to an introductory text in operating system design, so I will try to give some pointers.
First of all, if you really ...
- 421
Only top scored, non community-wiki answers of a minimum length are eligible