3 ms·

APL and co kind of undermine that metric, wouldn't you say?

naasking 9y ago
Kolmogorov complexity is "ideal compression", in that it bundles the axioms and the expression to reproduce the desired output using those axioms. So it really is a perfect measure for this type of thing. Gzip is an approximation of this metric of course, and the only flaw in the benchmark suite is that it should really include the size of the runtime which provides the programming language's axioms. APL is also a good example of why it's important to include various programs in the suite for a valid comparison. Some APL programs are longer than more expressive equivalents when APL is ill-suited to the problem, and once you include the axioms.
- vanderZwan 9y ago
  I know what Kolmogorov complexity is, I was trying to get at something else: removing boilerplate is one thing, but the other extreme isn't all that helpful either. When discussing information theory, one should always remember that white noise has the maximum amount of information, so the theoretical best scoring programming language of your measurement would be indistinguishable from white noise. Hardly productive, right? One of the key things about higher programming languages is that they add structure and patterns - in information theory terms: redundancy - to make it easier for programmers to follow what is going on. I mentioned APL because programs in it usually consist of a handful of symbols with very little repetition. The symbols/performance ratio is really good for APL. Or to be even more on the nose: think of code golfing languages[0]. [0] https://en.wikipedia.org/wiki/Code_golf#Dedicated_golfing_languages https://en.wikipedia.org/wiki/Code_golf#Dedicated_golfing_la...
  - naasking 9y ago
    > so the theoretical best scoring programming language of your measurement would be indistinguishable from white noise. The compressed program is necessarily shorter than the output it's trying to reproduce, unless the output is itself pure noise. Therefore noise and programs must be distinguishable. > One of the key things about higher programming languages is that they add structure and patterns - in information theory terms: redundancy - to make it easier for programmers to follow what is going on. Structures and abstractions don't introduce redundancy, they are actually compression. A while loop is clearly more compressed than an infinite sequence of if-statements repeatedly testing the termination condition. An abstraction, like a list or monad, eliminates significant boilerplate that would be needed to reproduce the output of the list or monad. Adding redundancy makes things harder to follow because you need to keep more state in your head. Adding the right kind of compression makes things easier for humans to follow (obviously there are bad kinds of compression, like alpha conversion to random strings).

Kolmogorov complexity is "ideal compression", in that it bundles the axioms and the expression to reproduce the desired output using those axioms. So it really is a perfect measure for this type of thing. Gzip is an approximation of this metric of course, and the only flaw in the benchmark suite is that it should really include the size of the runtime which provides the programming language's axioms. APL is also a good example of why it's important to include various programs in the suite for a valid comparison. Some APL programs are longer than more expressive equivalents when APL is ill-suited to the problem, and once you include the axioms.

vanderZwan 9y ago
I know what Kolmogorov complexity is, I was trying to get at something else: removing boilerplate is one thing, but the other extreme isn't all that helpful either. When discussing information theory, one should always remember that white noise has the maximum amount of information, so the theoretical best scoring programming language of your measurement would be indistinguishable from white noise. Hardly productive, right? One of the key things about higher programming languages is that they add structure and patterns - in information theory terms: redundancy - to make it easier for programmers to follow what is going on. I mentioned APL because programs in it usually consist of a handful of symbols with very little repetition. The symbols/performance ratio is really good for APL. Or to be even more on the nose: think of code golfing languages[0]. [0] https://en.wikipedia.org/wiki/Code_golf#Dedicated_golfing_languages https://en.wikipedia.org/wiki/Code_golf#Dedicated_golfing_la...
- naasking 9y ago
  > so the theoretical best scoring programming language of your measurement would be indistinguishable from white noise. The compressed program is necessarily shorter than the output it's trying to reproduce, unless the output is itself pure noise. Therefore noise and programs must be distinguishable. > One of the key things about higher programming languages is that they add structure and patterns - in information theory terms: redundancy - to make it easier for programmers to follow what is going on. Structures and abstractions don't introduce redundancy, they are actually compression. A while loop is clearly more compressed than an infinite sequence of if-statements repeatedly testing the termination condition. An abstraction, like a list or monad, eliminates significant boilerplate that would be needed to reproduce the output of the list or monad. Adding redundancy makes things harder to follow because you need to keep more state in your head. Adding the right kind of compression makes things easier for humans to follow (obviously there are bad kinds of compression, like alpha conversion to random strings).