High Level Languages
C, Java, C# et. al. (imperative with poor type systems) languages are low level languages. Many people are not aware of this fact, especially those who are only aware of languages that are imperative with poor type systems. This behaviour is probably best described by Psychologists than I will attempt, so I will not attempt any explanations for it.
I refer to pages 58-61 of Types and Programming Languages (0-262-16209-1) on the chapter about the untyped lambda calculus where author Benjamin Pierce notes that the the value false for the Church Boolean encoding is the same as the value zero for the Church Numeral encoding.
λt. λf. f
λs. λz. z
Pierce then goes on to note that:
Similar “puns” are common in assembly languages, where the same pattern of bits may represent many different values — an int, a float, an address, four characters, etc. — depending on how it is interpreted, and in low-level languages such as C [emphasis mine], which also identifies
0andfalse.
I wonder if the aforementioned programmers — those aware of only low-level languages, therefore call languages of “the highest level that I am aware of”, high-level languages — are willing to claim that Pierce has made a grave mistake, or if it will invoke the possibility that maybe there are more levels out there.
If, for just one person, it is the latter, then the objective of this post has been achieved 
July 24th, 2007 at 12:59 pm
Are you just rephrasing the Blub paradox of which you are so fond of berating?
Languages can support imperative programming, not have an elaborate type system built in, but be high level. Lisp is such a beast.
July 24th, 2007 at 3:25 pm
Lisp has a type system built in, just not a very good one.
Therefore, no.
July 24th, 2007 at 7:09 pm
Er, correction after a reread.
Yes, I am possibly rephrasing the infamous Blub paradox.
However, Lisp does have a type system, just not a very good one (hence, it is quite low on the Blub spectrum itself). Note that all functional programming languages support imperative programming, since imperative programming is just a special type of functional programming.
I’ve been searching for the paper that helps support this point, since it was so good, that I forgot the name (and therefore, I am struggling to bring it up in Google). If anyone can point me to it, I’d most appreciate it! It was something about reasoning about imperative programs as referentially transparent functions.
July 25th, 2007 at 2:01 pm
Imperative programming is not just a special type of functional programming. This is untrue.
First, imperative knowledge generally describes “how to”. This is consistently how it is described in various CS disciplines.
In Expert Systems theory, imperative rules tell the knowledge system “how to” behave. A related declarative rule would tell the knowledge system what it could believe, but would leave how unspecified. (Most knowledge systems have rulesets that combine imperative and declarative knowledge, but also might include exclamatory knowledge and interrogative knowledge.)
In Programming Languages theory, imperative statements describe how the program will do something.
Second, a functional program can have a high degree of imperative expressiveness. I usually associate precise control structures with imperative expressiveness. foldl and foldr in Haskell are excellent examples of precise control structures. However, “expressiveness” is such a qualitative term that someone could view imprecise control structures like basic loops as more expressive because they are so adaptable.
Third, declarative expressiveness should be our goal when programming complex systems: Program to an interface, not an implementation.
Fourth, Google has a “Note It” feature on search results. If you find a PDF that is really good, then “Note It”. You will come to love this feature, because you will never misplace a journal article again.
July 25th, 2007 at 3:38 pm
> Imperative programming is not just a special type of functional programming. This is untrue.
I’d like to correct this statement.
It is indeed true. One possible correction is, “This is not initially obvious to most intuitions”.
Next time you use Haskell, put *everything* inside IO and use IORef to emulate in-place updates i.e. imperative programming; the specific type of functional programming. Equational Reasoning is your friend
July 26th, 2007 at 1:41 pm
I don’t care what nouns are my friend or foe. I care about correct arguments.
Note that you said: “Note that all functional programming languages support imperative programming, since imperative programming is just a special type of functional programming.” This is an awkward statement. If imperative programming is a subset of a functional paradigm, then it is not certain that all functional programming languages support imperative programming. In other words, you are making an unsupported statement.
However, I think that the issue here is we are inadvertently talking past each other. If you only wish to say that you can express imperative knowledge in a functional program, then you are correct. However, procedural languages can do this too. That is why I huffed at the suggestion imperative programming is “just” a special type of functional programming. It’s more accurate to say that imperative thoughts can be expressed in a functional paradigm… as well as a procedural or even object-oriented paradigm.
Look at it this way: knowing what to believe without ever being able to grok how-to is an incomplete paradigm. Categorizing a scientific paradigm in such a way to suggest that you can’t convey certain knowledge types is an ill-defined paradigm. Being able to define various kinds of knowledge is just better science.
July 26th, 2007 at 2:02 pm
Just to sum this up in case I didn’t hit a home run there…
The first rule of programming is ‘Figure out what you want to say before you figure out how to say it’. Talking down to imperative programming by making it a category within functional programming is incorrect. It treats imperative knowledge like it is part of the implementation, when it is more likely an artefact of the design requirements of the software you are building. Similarly, identifying declarative knowledge belongs in the phase of software development before implementation.
The ability to translate declarative knowledge and imperative knowledge into programmatic statements necessarily falls under control of the language and the skill of the programmer. Many people feel it’s important to make this separation apparent, with the belief that it contributes to quality assurance.
For this reason, pointing me to some Haskell examples does not mean much to me. I usually (not always) know when I am unnecessarily conflating different control structures in my implementation language, and when I can easily express an imperative thought because there is a convenient mechanism in the language to do so. At the same time, because I have this knowledge, I can usually (not always) translate the design requirements to any language.
July 26th, 2007 at 2:47 pm
I think it is best to just smile and nod at this point
July 26th, 2007 at 3:02 pm
>I usually associate precise control structures with imperative
>expressiveness. foldl and foldr in Haskell are excellent examples of
>precise control structures.
Wuuuuurht?
July 26th, 2007 at 3:19 pm
Think about what I said instead, unless you are smiling because you agree (but I get the sense that we might still be inadvertently talking past each other).
Also, although a fold is not a control structure in the traditional sense, like the categories described by Niklas Wirth, it is a control structure with very precise and unambiguous meaning. Keep in mind Wirth was describing the minimum amount of control abstraction necessary.
Truly great advances in program architecture seem to occur because people are thinking about data flow, instead of merely data structures and especially instead of merely algorithms. Consider Wirth’s book Algorithms + Data Structures = Programs. He put the “Algorithms” part first, reflecting an emphasis on algorithms. Lately, we have reversed the phrase to say Data Structures & Algorithms, because the structure can determine the algorithms you implement. However, what really makes sense is to model the data flow and go from there.
August 18th, 2007 at 10:27 am
With regard to C/C++, what Pierce is saying here doesn’t really hold. C and C++, despite being “low-level” (no debate about that) just define certain implicit (and certain explicit) conversions between values of certain types. But they don’t identify them with each other. For example, while 0 and false implicitly convert into each other, the result of accessing an int variable holding the value 0 through an expression of type pointer-to-bool is undefined. Meaning that C/C++ implementations are allowed to throw a type error, for example. Even if the bit pattern happens to be the same.