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 ...
tsleyson's user avatar
  • 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 ...
chi's user avatar
  • 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 ...
David Richerby's user avatar
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....
Raphael's user avatar
  • 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 ...
David Richerby's user avatar
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 ...
Pseudonym's user avatar
  • 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: ...
jmite's user avatar
  • 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 ...
jmite's user avatar
  • 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 $$ ...
Yuval Filmus's user avatar
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. ...
Derek Elkins left SE's user avatar
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 ...
jmite's user avatar
  • 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.
gnasher729's user avatar
  • 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 ...
Pseudonym's user avatar
  • 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 ...
Nat's user avatar
  • 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 ...
user253751's user avatar
  • 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 ...
Paul Draper's user avatar
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 ...
Evil's user avatar
  • 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 ...
Jörg W Mittag's user avatar
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 ...
Pseudonym's user avatar
  • 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 ...
Derek Elkins left SE's user avatar
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 ...
Derek Elkins left SE's user avatar
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) ...
Raphael's user avatar
  • 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 ...
zpavlinovic's user avatar
  • 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 ...
Brian Tompsett - 汤莱恩's user avatar
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 ...
Brian Tompsett - 汤莱恩's user avatar
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 ...
ComFreek's user avatar
  • 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 ...
Juho's user avatar
  • 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 ...
rici's user avatar
  • 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 ...
babou's user avatar
  • 19.4k

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