High vs. Low Level Languages

There's a lot of mistaken impressions about high level languages, both in terms of their attributes and their benefits. Allow me to elucidate.

After someone read my Rexx teaser, an interesting debate about what constitutes a "high level" language erupted.  Specifically one person expressed surprise after I opined that Python was a mid-level language, not a high-level one.

 

To illustrate why I think this is the case I'm going to present a simple challenge.  I've got code for a very common sort algorithm here, presented in two languages.  The first is Python, the second is Haskell.  Neither has been written in any tricksy optimized fashion.  The only alteration I have made is that I filed off the serial numbers; I've renamed variables, functions, etc. such that nobody can just read the variable names to figure out what's going on.

The challenge?  Identify the algorithm.

It's that simple, yes.  Just figure out which algorithm I've got here from the code.  First try it from the Python version.  Then try it from the Haskell version.

In the first corner, wearing the blue trunks, Python!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def sort(a, start, end):
    for i in xrange(start, end + 1):
        v = a[i]
        for j in xrange(i-1, -1, -1):
            if a[j] <= v:
                a[j + 1] = v
                break
            a[j + 1] = a[j]
        else:
            a[0] = v
    return a

In the second corner, wearing the red trunks, Haskell!

1
2
3
4
5
6
7
sort p [] = []
sort p (x:xs) = f p x (sort p xs)
  where
    f p x [] = [x]
    f p x (y:ys) =
        |  p x y = (x:y:ys)
        |  otherwise = y:(f p x ys)

Interlude: what "high level" doesn't mean

The error the Python user made, in my opinion, is a very insidious one.  He confused "high level" with "looks like natural language".  The implication is that "high level" code is readable like plain old (in his case) English.

 

Let's look at a Cobol implementation of the same algorithm.  Cobol was designed to read like English.  This was based on a delusion that coding is something that could be done by non-coders, you see.  It was very quickly proved wrong.  You can see why here:

       C-PROCESS SECTION.
           PERFORM E-SORT VARYING WB-IX-1 FROM 1 BY 1
                          UNTIL WB-IX-1 > WC-SIZE.

      * Unnecessary declarations elided.  The data division's entries
      * can be inferred from the code.

       E-SORT SECTION.
       E-000.
           MOVE WB-ENTRY(WB-IX-1) TO WC-TEMP.
           SET WB-IX-2 TO WB-IX-1.
 
           PERFORM F-PASS UNTIL WB-IX-2 NOT > 1 OR
                                WC-TEMP NOT < WB-ENTRY(WB-IX-2 - 1).
 
           IF WB-IX-1 NOT = WB-IX-2
              MOVE WC-TEMP TO WB-ENTRY(WB-IX-2).
 
       E-999.
           EXIT.
 
       F-PASS SECTION.
       F-000.
           MOVE WB-ENTRY(WB-IX-2 - 1) TO WB-ENTRY(WB-IX-2).
           SET WB-IX-2                DOWN BY 1.
 
       F-999.
           EXIT.

Despite this version being done in things that look a lot more like English words than the purportedly "high level" (which, recall, is conflated with meaning "English-like") Python, it is, if anything, even harder to figure out what algorithm is being presented.

The rumble!

Both the Python and the Haskell version of this code are easy to read.  The formatting is good and, insofar as they work within their paradigms, both languages are actually very clean.  It's easy to write readable code in both.

 

That being said, after a bit of unscientific testing, even experts I showed the Python code to had to puzzle out the algorithm's workings (and thus identify it) by effectively executing the algorithm manually.  They ran (in effect) a Python emulator in their brain and from the observed state changes in it, combined with, naturally, knowledge of algorithms, inferred which algorithm was being expressed.  Indeed their approach showed little difference from Python novices.  They just knew how to do it more quickly.

 

The results for the Haskell version were far more interesting.  The people I showed it to ranged from having no experience whatsoever in Haskell (but having experience in Haskell's functional paradigm from the MLs, Erlang or even Lisps) to people with reasonable passing familiarity with Haskell's syntax and semantics.  All of them, with no exceptions, worked out which algorithm it was from just looking at the code briefly.  As one of the people involved opined:

You need to walk through the python version to be able to read it.  Do it in your head.  For the haskell version, you can almost just read it.

Therein lies, for me, the key distinction between a high-level and a low- level language.

Where's Mario when you need him?

The Python version is lower-level code than the Haskell version because of the plumbing.  There is a lot of the implementation details of the algorithm exposed that have to be manually addressed.  You have to tell the language how to step through the values of the array, for example.  You have to move values back and forth between memory cells.  You're not concerning yourself with just the definition of the algorithm, you're also concerning yourself with telling the computer, step by step, what it has to do to actually work through the algorithm.  This is the essence of the "imperative" style of programming: a focus on statements, statement order, commands, etc.  The plumbing of the software.

 

In contrast there's very little plumbing visible in the Haskell version.  The most visible plumbing, in fact, is the (x:xs) stuff in the function parameters.  (It means "take the head of the list and call it x, putting the remainder into xs).  The rest is pretty much just a definition.  Which is, in the end, the whole point of the "declarative" style of programming.  In declarative programming the ideal (which doesn't exist yet, keep in mind!) is that you state the problem and the answer comes from it.

Who cares?

Well, if you care about understanding code quickly and more accurately you should care.  Go back to the quote I cited above: for the haskell version, you can almost just read it.  I know it's all the rage in programming to care most about how easy it is to write code, but in reality the most important thing in programming isn't the writing of code, it's in the reading (and, specifically, the understanding of it).  The closer the code matches your problem domain, the better the code is.  End of story.

 

In most problem domains, the plumbing of imperative coding interferes with code reading and comprehension.  The code is littered with flow control commands.  If you want to double each element in an array, for example, the actual operation is trivial and badly outweighed by the surrounding infrastructure for stepping over the values.  In a declarative language like Haskell the plumbing is almost invisible: map (*2) [1,2,3,4,5].  (The definition of the map function itself—seen below—is similarly concise and devoid of plumbing should you feel that using a function is cheating.  Part of Haskell's power lies in how easily you compose functions, after all.)

map f  []               =  []
map f (x:xs)            =  f x : map f xs

So what about natural language then?  Surely it's not low-level!

Well, actually, yes it is.  Some are lower level than others, but natural language is very low level at times.  Let's consider the following English sentence:

I'm going to be going to Shanghai.

Talk about a mess.  We've got the verb "to be" used in its guise of "am" (then conflated with the subject of the sentence) just for starters.  We've altered the verb into something that appears and sounds radically different all for a useless piece of grammatical plumbing: subject/verb agreement.  Oh, and wait.  That "to be" we just mangled is only there as an auxilliary verb used to modify the verb "to go" to make it in the future tense.  Which we do by modifying the base form of "go" still further by adding "ing" as a suffix.


We're two words into the sentence and we've hit four pieces of plumbing that has nothing to do with what we're communicating; I haven't even addressed the various punning uses of "to go" that are in this one simple sentence.  Nor the punning uses of the word "to".  There are seven (or eight, depending on how you want to count) words in this sentence and there's easily that much plumbing interfering with the actual topic.

 

There's a reason why mathematicians, doctors, engineers, computer scientists, lawyers, etc. use jargon it turns out.

TL;DR

So there you have it.  A high level language has nothing to do with it being "English-like" (or, more broadly, like natural language).  It has to do with how naturally you can express the abstractions of your problem domain without introducing irrelevant features.  It is for this reason that I don't consider languages like Python to be high level languages.  They're higher level than C++ or Java or C or their ilk obviously, but as you can see from the algorithm challenge above, it's still obfuscatory when compared to true high level languages like, say, Haskell.