5
$\begingroup$

I want to explore the notion of quantifying the amount of succinctness a programming language provides. That is, the amount a high-level language reduces the complex.

This idea of "simplification" is a factor of text-wise reduction (fewer characters needed to express a complex concept, à la Algorithmic Information Theory) and another, less easy-to-quantify concept of maintainability. Fleshing out this latter concept, it is clear it has to do with how easily one can establish programmer consensus for the given task (i.e. how many programmers of the language would put it back the same way you've expressed it or otherwise agree on the best implementation between different implementations of the same problem?).

I will define the "Kolmogorov Quotient" so that higher numbers for a given language denote a reduction in the complexity of solving the problem in the given language.

The metric for "text-wise reduction" should incorporate a constant factor based on (non-identifier) symbols used in the language and source text. These factors will be the same across all languages implemented (i.e. designed) for a given architecture (e.g. VonNeumann architecture vs. Symbolics) and will be a measure of the significance of the symbol; i.e. the topology of the language tokens. (These terms, alas, will also need to be fleshed out and defined.)

Once the basic premise and a methodology above is agreed to, it is only a matter of a rough constant of difference for any specific implementation/architecture. (That is, as long as the architecture is the same across all measurements, the number should be valid and comparable between languages.)

But it could go something like this: Pick a language "close to the machine", like C or Assembly, and measure the amount of bytes of machine code it used to implement a standard suite(*) of common, non-threaded programming tasks (base_language_count). Then code the exact same functionality in the language you are wanting to measure (without using external libraries) and count the number of bytes of source code (test_language_count).

KQuotient = (base_language_count / test_language_count) / number_of_equal_programs.

"number_of_equal_programs" is the number of programs fluent programmers of the language agree that are the best and equal solutions to the problem. (I will define "equal programs" as those who's output is the same for every input.)

The first ratio should always be greater than 1.0. My only concern is that for each programming language, one could reduce the KQuotient number simply by changing each keyword to a single character.

(*) "standard suite of common programming tasks...": I see two main categories:

  1. Data-processing suite, limited to simple text I/O (computation towards the machine)
  2. GUI suite (computation towards the user)

The purpose of this idea is to end the tiring "language wars" about whose language is the best. By giving a quantitative metric, people can at least argue better.

Improve this question
$\endgroup$
11
  • 3
    $\begingroup$ I don't see any question in your post. $\endgroup$
    – Kaveh
    Commented Jun 10, 2013 at 4:10
  • 7
    $\begingroup$ You might want to explore another name for what you're looking at. Expressiveness has been previously discussed PL research. See Fellesien's "On the Expressive Power of Programming Languages". $\endgroup$
    – Logan Mayfield
    Commented Jun 10, 2013 at 11:46
  • 1
    $\begingroup$ @MartinBerger I mentioned Felleisen's paper not because it solves his problem, but because if he pursues his idea he might want to find another name for what he's measuring or at least something to differentiate it from Felleisen's expressiveness. $\endgroup$
    – Logan Mayfield
    Commented Jun 10, 2013 at 12:27
  • 1
    $\begingroup$ what you define as reduction vs maintainability are arguably two sometimes orthogonal/not-fully-overlapping concepts. however, have noticed also how languages tend to build on each other in a sort of pyramidal structure, which nobody seems to have studied or quantified much. $\endgroup$
    – vzn
    Commented Jun 14, 2013 at 21:12
  • $\begingroup$ @MarkJ: The definition of "external libraries" seems tricky to me. For example, lists are essentially built in to languages like scheme or haskell, but are a library for C (assembly, etc.), and are part of the "standard library" (not usually considered external) for Java. Maybe one could consider implementations of a given algorithm given a black box for some data structure (like lists etc.) In a similar vein, for any function f I could define a (admittedly unnatural) language which had f as a basic primitive, hence would not be external and would have a very short program in that language. $\endgroup$
    – Joshua Grochow
    Commented Jun 21, 2013 at 3:24

3 Answers 3

Reset to default
7
$\begingroup$

The ideas the question expresses are interesting but maybe insufficiently fleshed out. I can see a couple of points that deserve further refinement.

  • It is difficult to "code the exact same functionality". In part that is because what counts as "the exact same functionality" depends on the chosen notion of program equivalence. For terminating programs in sequential programming languages there's a canonical definition, but when you move to concurrent, non-terminating programs, canonicity vanishes, and you are left with multiple, reasonable choices that are mutually incompatible. Secondly, but related to the first point, different programming languages are fundamentally different: things you can do in a low-level language can often not be done in a high-level language. A typical example is to do with speed. Certain tasks can be solved intrinsically faster in assembly language than in e.g. Prolog or Javascript (assuming conventional compilation).

  • The KQuotient is subjective, in the sense that for any given task, programmers A and B will likely have different length base and test language implementations.

  • Moreover, the KQuotient is also task dependent, meaning that, given a pair of languages, the KQuotient for Task A will in general be different from the KQuotient of Task B.

Finally, even though I find the idea of measuring maintainability via query numbers to reach consensus intriguing, I suggest to be more clear about what kind of queries are relevant here (syntax? semantics?), and how the concept of programmer consensus can be made precise.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I was speaking of "functionality" in a non-parallel, synchronous fashion where output can arrive predictably. I will have to make that clearer, because I don't believe the concept can be extended to multi-threaded programs running concurrently. On the second point, I addressed this somewhat by the concept of "maintainability". $\endgroup$
    – Mark Rosenblitt-Janssen
    Commented Jun 11, 2013 at 19:08
  • 1
    $\begingroup$ @MarkJ: I like your ideas! But a word of caution. Even in a sequential synchronous fashion where output can arrive predictably, defining "functionality" takes some care. Think about implementing, say, mergesort vs bubblesort. They have the same input-output behavior but look very different even in the same language. If you want an example where they both have similar resource usage, then compare mergesort and quicksort (or heapsort or ...). To get around M. Berger's point about different programmers, you could consider an average over programmers with "sufficient experience." $\endgroup$
    – Joshua Grochow
    Commented Jun 21, 2013 at 3:19
  • $\begingroup$ @JoshuaGrochow How does considering an average over programmers with "sufficient experience" avoid subjectivity? In order to formalise query complexity of programs, or related concepts, one would have to rely on syntactic features of programs only. $\endgroup$
    – Martin Berger
    Commented Jun 21, 2013 at 9:26
  • $\begingroup$ @MartinBerger: I didn't mean to say it completely avoids subjectivity, just that it helps reduce it. I agree that the notions of expressiveness and maintainability are subjective - perhaps even necessarily so. So completely avoiding subjectivity probably shouldn't be a goal. But one still wants to avoid the subjective bias of any single programmer. $\endgroup$
    – Joshua Grochow
    Commented Jun 21, 2013 at 14:59
  • $\begingroup$ @JoshuaGrochow I agree that practically relevant notions of expressiveness are strongly related with programmer knowledge, hence subjective. However, I think some of the ideas on programming language expressiveness (via compression and 'maintainability') suggested by Mark might be formalisable, and have interesting formal properties. $\endgroup$
    – Martin Berger
    Commented Jun 21, 2013 at 15:26
4
$\begingroup$

here is a project Rosetta Code somewhat similar or adaptable to some of your goals [which as others point out are not very specific/objective/concise/clearcut yet], a database involving quantification of languages on the same task for comparison. the post "Code Length Measured in 14 Languages" is an example of the quantitative analysis possible with this database, mostly focused on Mathematica versus other languages.

Rosetta Code is a programming chrestomathy site. The idea is to present solutions to the same task in as many different languages as possible, to demonstrate how languages are similar and different, and to aid a person with a grounding in one approach to a problem in learning another. Rosetta Code currently has 676 tasks, 102 draft tasks, and is aware of 503 languages, though we do not (and cannot) have solutions to every task in every language.

Improve this answer
$\endgroup$
1
1
$\begingroup$

the Rosetta Code repository has been used for a new comprehensive scientific/ academic study of language succinctness among other comparisons of properties. announced at "Analyzing Programming Languages using Rosetta Code"

Sometimes debates on programming languages are more religious than scientific. Questions about which language is more succinct or efficient, or makes developers more productive are discussed with fervor, and their answers are too often based on anecdotes and unsubstantiated beliefs. In this study, we use the largely untapped research potential of Rosetta Code, a code repository of solutions to common programming tasks in various languages, to draw a fair and well-founded comparison. Rosetta Code offers a large data set for analysis. Our study is based on 7087 solution programs corresponding to 745 tasks in 8 widely used languages representing the major programming paradigms (procedural: C and Go; object-oriented: C# and Java; functional: F# and Haskell; scripting: Python and Ruby). Our statistical analysis reveals, most notably, that: functional and scripting languages are more concise than procedural and object-oriented languages; C is hard to beat when it comes to raw speed on large inputs, but performance differences over inputs of moderate size are less pronounced and allow even interpreted languages to be competitive; compiled strongly-typed languages, where more defects can be caught at compile time, are less prone to runtime failures than interpreted or weakly-typed languages. We discuss implications of these results for developers, language designers, and educators,

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.