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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
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....
user avatar
  • 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 ...
user avatar
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: ...
user avatar
  • 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: ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 $$ ...
user avatar
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 ...
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. ...
user avatar
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.
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
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 ...
user avatar
  • 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 ...
user avatar
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 ...
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
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) ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar

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