Programing Languages and Their Computational Models

By Xah Lee. Date: . Last updated: .

As years go by, i get more insights about programing languages. For computation to happen, you need: (1) A machine. (2) Instruction set. (this is the programing language) (3) recipe, using the lang (this is the algorithm, or actual source code.)

Because lang needs a machine, and machine can be very different. Example • CPU/Chipset • Abacus (japanese, chinese, number of columns, or 2 piles of stones on sand) [see Abacus] • Cellular automata [see Notes on A New Kind of Science] • Molecules (dna comp) • Traditional axiomatic math. The lang can be quite different.

On the surface, different langs are similar. e.g. perl python ruby. All have function, variable, list, hashtable. But often they are really quite different. Because, they are for different machines. A high level abstract ideal machine, we say “computational model”.

For example, both perl and python have object as in OOP. However, “object” is a core concept of python, but does not exist in perl. Rather, perl has concept of reference, from which, programer notion of OOP object is based on.

In lisp, object of OOP sense does not exist in the lisp language model. The lang does have concept of object, but it means roughly compiled code. The programer sense of OOP object, is done as so-called multi-dispatch system or “common lisp object system”.

[see Meaning of Object in Computer Languages]

[see Polymorphism, Dispatch, and the Tale of Poly-Tinting]

In lisp and Wolfram Language, these lang have a concept of symbols, often said to be symbolic languages. It is a core element of the lang. It means, the whole lang, is based on processing sequence of symbols (for non-lispers, it roughly mean manipulating tokens identifiers keywords.)

It's most easy to see language's model (i.e. The machine it is designed for), by looking at assembly languages. Here, we don't even speak of “computational model” anymore. Because, their model is directly a machine, a specific cpu chip.

Ok. The point of this thread so far, is that: (1) the 3 things computation needs. (2) specifically, each language has a associated machine it's designed for. (3) the machine of a high level langs, are often called its “computational model”

Now, “computational model” of a programing language is almost never explicitly defined. Never a formal spec. At best, you can see the lang doc/spec describing it in fuzzy English. try read python doc, JavaScript spec, lisp doc, java spec, perl doc. Nor haskell, nor clojure.

Most programing language don't have any explicit notion nor exact spec of their computational model, because, most just grew out of practice. Example: Perl came from shell script. Php came from perl scripts. Ruby's conceived as improving perl. Almost no high level lang began with a model.

now let's look at some lang specs.

Note that they are bewilderingly different in what they seems to cover. You'd think they all high level languages in about the same field so that their spec should have the same structure/topics that only differ in detail.

For practical programing, you can work in the industry for few years without knowing the computational model of the language. A string, is a string in any lang. You just learn the syntax to manipulate string. A array is a array in any lang, with little differences how you access them, or whether length can be changed. But to master a language, you have to know the language's computational model well. e.g. Python semantics is about objects. JavaScript objects are key value pairs. Lisp is about processing list of symbols, each symbol has cells.

Programing Languages and their Machines