The paper this is based on, “On the Expressive Power of Programming Languages” by Matthias Felleisen, is a large part of why Shriram Krishnamurthi picked Matthias as his PhD advisor :-)
Wirth’s Oberon system had a useful benchmark that was essentially, does adding this feature to the compiler make compiling the entire system slower? If so, it’s reverted. There’s a paper about Oberon floating around and one of the people working on it spent considerable time improving the symbol table type in the compiler from a linked list to something “better”, and then had to remove it because it slowed down compiling the overall system. It turned out that usually symbol tables were small.
I think talking about expressive power ends up going down the wrong rabbit hole. There is a (moderately large) finite set of programs that are useful (or, if you want to be pedantic [which, to be fair, I usually do] of observable behaviours of programs that are useful, since there are an infinite number of equivalent programs and determining whether two programs are equivalent is not decidable in the general case). There is an infinite set of programs that are not useful.
The goal of a programming language is to make it easier to express useful programs than non-useful ones, while making it easy to mechanically translate those programs into some other model of computation that is amenable to direct implementation as a physical machine.
The differences in programming languages arise from differences in the definitions of the words ‘useful’ and ‘easy’ in the above sentence.
The paper this is based on, “On the Expressive Power of Programming Languages” by Matthias Felleisen, is a large part of why Shriram Krishnamurthi picked Matthias as his PhD advisor :-)
This seems like a useful tool to radically improve programming language design. You might design a language in a red-green-refactor TDD-like way:
Pareto optimally hill-climb into a local maxima programming language. 🫣
Wirth’s Oberon system had a useful benchmark that was essentially, does adding this feature to the compiler make compiling the entire system slower? If so, it’s reverted. There’s a paper about Oberon floating around and one of the people working on it spent considerable time improving the symbol table type in the compiler from a linked list to something “better”, and then had to remove it because it slowed down compiling the overall system. It turned out that usually symbol tables were small.
I think talking about expressive power ends up going down the wrong rabbit hole. There is a (moderately large) finite set of programs that are useful (or, if you want to be pedantic [which, to be fair, I usually do] of observable behaviours of programs that are useful, since there are an infinite number of equivalent programs and determining whether two programs are equivalent is not decidable in the general case). There is an infinite set of programs that are not useful.
The goal of a programming language is to make it easier to express useful programs than non-useful ones, while making it easy to mechanically translate those programs into some other model of computation that is amenable to direct implementation as a physical machine.
The differences in programming languages arise from differences in the definitions of the words ‘useful’ and ‘easy’ in the above sentence.
This is wonderfully lucid and clear.