Skip to main content
Share Your Experience: Take the 2024 Developer Survey
105 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.6k
100 votes

What is a safe programming language?

There is no formal definition of "safe programming language"; it's an informal notion. Rather, languages that claim to provide safety usually provide a precise formal statement of what kind of safety ...
D.W.'s user avatar
  • 161k
82 votes
Accepted

Paradox? Pure Prolog is Turing-complete and yet incapable of expressing list intersection?

Turing-complete means "can compute every function on natural numbers that a Turing machine can compute". It means exactly that and only that. A list is not a natural number, and list ...
Jörg W Mittag's user avatar
74 votes
Accepted

Are modern programming languages context-free?

Practically no programming language, modern or ancient, is truly context-free, regardless of what people will tell you. But it hardly matters. Every programming language can be parsed; otherwise, it ...
rici's user avatar
  • 12k
71 votes
Accepted

Why are some programming languages Turing complete but lack some abilities of other languages?

Turing complete languages can compute the same set of functions $\mathbb{N}^k \rightarrow \mathbb{N}$, which is the set of general recursive partial functions. That's it. This says nothing about the ...
chi's user avatar
  • 14.6k
64 votes

How does Tarjan's pseudocode work (explained to someone familiar with C or Java)?

Table of Contents I will divide my explanation of Tarjan's pseudocode into the following sections: Tarjan's If-else Blocks (the -> & ...
Toothpick Anemone's user avatar
62 votes
Accepted

What is the earliest use of the "this" keyword in any programming language?

Simula 67 is generally considered the first object-oriented language and predates Smalltalk by a number of years. It also used the this keyword for the same ...
Brian Tompsett - 汤莱恩's user avatar
59 votes
Accepted

How can I explain to my parents that I study programming languages?

If you have a few minutes, most people know how to add and multiply two three-digit numbers on paper. Ask them to do that, (or to admit that they could, if they had to) and ask them to acknowledge ...
Lieuwe Vinkhuijzen's user avatar
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 ...
Joey Eremondi's user avatar
56 votes

Why do more powerful programming languages tend to have slower implementations?

This is simply not true. And part of why it's false is that the premise isn't well formed. There is no such thing as a fast or slow language. The expressive power of a language is purely a function of ...
Joey Eremondi's user avatar
54 votes
Accepted

Are all turing complete languages interchangeable

Turing-completeness says one thing and one thing only: a model of computation is Turing-complete, if any computation that can be modeled by a Turing Machine can also be modeled by that model. So, ...
Jörg W Mittag's user avatar
52 votes

How do computers perform operations on numbers that are larger than 64 bits?

in school you (probably) memorized the common operations (addition, subtraction, multiplication and division) for decimal 1 digit numbers. Then you learned how to do operations on larger numbers using ...
ratchet freak's user avatar
49 votes

Why are some programming languages Turing complete but lack some abilities of other languages?

Turing completeness is an abstract concept of computability. If a language is Turing complete, then it is capable of doing any computation that any other Turing complete language can do. This does ...
Cort Ammon's user avatar
  • 3,351
45 votes
Accepted

Do any programming languages use general recursive functions as their basis?

Direct answer to the question: yes, there are esoteric and highly impractical PLs based on $\mu$-recursive functions (think Whitespace), but no practical programming language is based on $\mu$-...
xuq01's user avatar
  • 1,190
45 votes
Accepted

Is there any reason why the modulo operator is denoted as %?

The earliest known use of % for modulo was in B, which was the progenitor of C, which was the ancestor (or at least godparent) of most languages that do the same, ...
Foo Bar's user avatar
  • 536
42 votes

What is a safe programming language?

If you can get your hands on a copy of Benjamin Pierce's Types and Programming Languages, in the introduction, he has a good overview on various perspectives on the term "safe language". One ...
martin's user avatar
  • 545
40 votes
Accepted

What is the formal, rigorous definition of a programming language?

To taper expectations a little bit, I will first note that the term "programming language" is deliberately broad: it is intended to be open to some interpretation. It means, no more and no ...
Caleb Stanford's user avatar
33 votes
Accepted

Can we ever achieve Turing completeness?

As far as I know we say something is turing complete (eg: a programming language) when it can compute any function and can do any task. No. A model of computation is Turing-complete if it can compute ...
Jörg W Mittag's user avatar
32 votes
Accepted

Why must a function with polymorphic type `forall t: Type, t->t` be the identity function?

The first thing to note is that this isn't necessarily true. For example, depending on the language a function with that type, besides being the identity function, could: 1) loop forever, 2) mutate ...
Derek Elkins left SE's user avatar
32 votes
Accepted

What is a safe programming language?

When we call a language “safe” in some respect, that formally means that there’s a proof that no well-formed program in the language can do something we consider dangerous. The word “safe” is also ...
Davislor's user avatar
  • 1,241
31 votes
Accepted

What are some interesting/important Programming Language Concepts I could teach myself in the coming semester?

Very good explanations of programming paradigms and the programming concepts from which those paradigms are built are found in Peter van Roy's works. Especially in the book Concepts, Techniques, and ...
Jörg W Mittag's user avatar
28 votes
Accepted

Visual programming tools, why don’t they work with the AST directly?

Many of these tools do work directly with the abstract syntax tree (or rather, a direct one-to-one visualisation of it). That includes Blockly, which you've seen, and the other block-based languages ...
Michael Homer's user avatar
28 votes

How are variables stored in and retrieved from the program stack?

Storing local variables on a stack is an implementation detail – basically an optimization. You can think of it this way. When entering a function, space for all local variables is allocated somewhere....
Yuval Filmus's user avatar
26 votes

Why are some programming languages Turing complete but lack some abilities of other languages?

Think of programming languages as different land vehicles: bicycles, cars, hovercars, trains. Turing Completeness says "this vehicle can go anywhere any other vehicle can go." That is, you can ...
Joey Eremondi's user avatar
26 votes

How are variables stored in and retrieved from the program stack?

Having y on the stack doesn't physically prevent x from being accessed, which, as you pointed out, makes computer stacks ...
aebabis's user avatar
  • 361
24 votes
Accepted

Which other programming languages apart from Python and predecessor are out there using indentation to define code blocks?

Wikipedia has an extensive list of languages that use the off-side rule1: ABC Boo BuddyScript Cobra CoffeeScript Converge Curry Elixir (, do: ...
Bergi's user avatar
  • 608
21 votes
Accepted

Why do we have to trade abstraction for speed?

Debunking some myths There is no such thing as a fast langauge. A language can generally produce fast code, but different languages will excel on different benchmarks. We can rank languages on a ...
Joey Eremondi's 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 ...
Jörg W Mittag's user avatar
20 votes

What is a safe programming language?

Safe is not binary, it's a continuum. Informally speaking, safety is meant by opposition to bugs, the 2 most often mentioned being: Memory Safety: the language and its implementation prevent a ...
Matthieu M.'s user avatar
20 votes
Accepted

Halting problem theory vs. practice

Languages that are guaranteed to halt have seen wide spread use. Languages like Coq/Agda/Idris are all in this category. Many many type systems are in fact ensured to halt such as System F or any of ...
Jake's user avatar
  • 3,800

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