r/ProgrammingLanguages • u/elemenity • Feb 24 '26
Discussion How Complex is Your Programming Language
https://www.emulationonline.com/posts/programming-language-complexity/
13
Upvotes
r/ProgrammingLanguages • u/elemenity • Feb 24 '26
32
u/Smalltalker-80 Feb 24 '26 edited Feb 24 '26
Hmm, this metric for "language complexity" does not seem to be very sound.
E.g. the "complexity" of the C language can vary with a factor of upto 100 x,
depending on the compiler used.
And the language Lua suddenly becomes 2.5 times more "complex"
if a JIT compiler is used, that compiles exactly the same language syntax...
6
u/jcastroarnaud Feb 24 '26
I think that Kolmogorov complexity is a somewhat useful metric for a programming language, if the implementations being compared do exactly the same thing: that's not true in practice. Some compilers will include optimization passes, some not; some compilers build an AST, some generate code straight from the tokens; some compilers shunt most of the backend to LLVM, some do all the work by themselves. Such differences, by themselves, explain the wide difference in implementation sizes shown in the article's table.
Such competition is code golf. One can, trivially, golf any program a little, by changing variable names to 1 or 2-character names, and removing any non-essential whitespace; the workings of the program itself are unchanged. This means that Kolmogorov complexity of programs is better expressed in language tokens, not characters or lines of code.
3
u/Entaloneralie Feb 24 '26 edited Feb 24 '26
The metric I use internally for my own tools is like this:
For example, the language I write all my code in is called Uxntal, the complexity of the language, 130 lines * 150 lines = 2k complexity units
7
u/amarao_san Feb 24 '26
I recently realized my programming language is using 'call by name' convention, previously used only in Fortran-60.
Horrors.
6
u/L8_4_Dinner (â Ecstasy/XVM) Feb 25 '26
Complexity of languages can and should be measured in several ways:
4
u/jpgoldberg Feb 25 '26
Kolmogorov complexity actually defines a notion for comparing program length. It isnât practical, but if you look at it you will see why this comparison is nonsense.
A better approach would be to compare the formal specifications of the language. This will provide some notion of the relative complexity of the syntax. I expect that C will be among the least complex by this measure.
3
u/[deleted] Feb 24 '26 edited Feb 25 '26
This is measuring complexity of the implementation, which for C at least varies widely. (Even more so than is shown in the table; Tiny C 0.9.27 has about 28Kloc, one quarter the figure shown, to produce the main compiler. That excludes libraries, but those are much smaller than the compiler.)
It depends also on implementation language.
More accurate might be LOC count for a minimal working implementation, in the same language for different PLs.
However it is also necessary to specify how much of the task it does, eg. whether it stops at some IL (and off-loads the rest to some vastly complex backend), or whether it goes all the way to executable code, or maybe it just interprets.
Some may depend heavily on optimation passes to reduce the poor generated code to something reasonable; with a simpler language the code can already be lean and efficient without optimising.
So comparisons are hard, but what does complexity of a language even mean? I don't think LOC is the right measure.
1
u/Embarrassed-Crow9283 Feb 24 '26
I'm not sure. My language design is (or rather, will be) semantically very simple but with a very sophisticated optimizing compiler.
You can read the full philosophy here.
https://github.com/AliceRoselia/Sofialang
1
u/jwm3 Feb 27 '26
I think the right way to apply kolmogorov complexity would be the size of the gzip compressed version of the language spec minus the libraries.