Please note that these are only notes towards a book that will probably never be finished. The "book" is only about 1% there. Perhaps these notes will make interesting reading in the meantime. -- bayle

Table of Contents for Programming Languages: a survey

This book grew out of a laundry list of constructs found in different programming languages. There were three motivations for that list. First, I like to collect ideas. Second, i am interested in cognition, even if our brain is just a universal Turing machine, it seems like the algorithm of our mind must make use a very different programming paradigm than the way we usually write programs; so it seems useful to me for someone who wants to think about cognition to look at different ways to think about programming. Third, i spend a lot of time writing software, and so i wanted to learn about what programming languages are out there so that i can use the best ones.

I'm not an expert on programming languages, and I've never used many of the languages and constructs that i discuss in this book. I've never been trained in this, and I'm just making notes as I learn about it myself, and I thought that maybe others could benefit from these notes. You'll notice that many of my sources are random comments in forum discussions. Perhaps when you notice incorrect information, you could email me so that i could fix it.

This book is intended for the intermediate level programmer who knows a few languages and wants to know what else is out there, or who wants to know the basics of programming language design. It's not one of those books with a coherent idea that it is teaching you; it's more of a laundry list of 'what's out there'. But it's not an encyclopedia; it's short enough to read cover-to-cover. Unlike many books on the subject of programming languages, i don't focus on the technology for implementing a programming language, nor on the formal theory, although there are sections on the very basics of each of these. My focus is on comparing multiple languages, and on practical issues affecting language users (as opposed to the practical issues that arise for language implementors). Whenever possible i try to mention the costs of various language design decisions, not just their benefits; and i do include biased and subjective opinions on what people seem to like and to dislike.

Other books that you may prefer to read over this one:

- see http://lambda-the-ultimate.org/node/272
- SICP. Everyone's favorite.
- Pierce's book on type systems
- Programming Languages: Application and Interpretation
- if you don't like reading books which are merely regurgitations of wikipedia and blog posts, perhaps you would prefer to read wikipedia and blog posts over this book
- see Links and external resources and https://en.wikipedia.org/wiki/Programming_language#External_links and http://alexott.net/en/fp/books/ and http://homes.cs.washington.edu/~csgordon/books.html for more

A programming language is an executable convention for specifying computation.

You might start with: "a programming language is a language for telling a computer what to do."

However, people also use programming languages to talk to each other formally about specific things that a computer could do. So we want a word for that topic, so we can say "a programming language is for describing ___". The sorts of things that a computer could do is called "computation", and describing something specific and formally is 'specification', so we get: "A programming language is a language for specifying computation."

What is a language? It's a convention for the representation of meaning by content in some medium. In particular, a programming language is a convention for the specification of computations.

But sometimes you can define a computation in a way that doesn't make it apparent how to carry that computation out, and that wouldn't be useful for telling a computer what to do (for example, by giving information that uniquely determines an algorithm in the mathematical sense without actually saying what the algorithm is), so to combine these first two definitions we need to add "...in a way that can be executed by a computer". We can shorten this to 'executable'.

Putting all this together, we get the definition at the beginning of this chapter.

Models of computation are mathematical constructs. They try to boil the notion of "computation" down to a concise construct with few parts and little or no redundancy. Models of computation are essentially formally definited, minimalistic programming languages. All generally accepted mathematical models of computation are formally equivalent, in that any program that you can write for one of them can be transformed to a program for any of the others. The Churchâ€“Turing? thesis (which is generally accepted) asserts that these formal models accord with the informal notion of 'computation'.

Because of their conciseness, it is a pain to actually write programs for these models. Models of computation are small/simple/spartan for two reasons. First, their primary use is to prove theorems about computability, for which purpose it's nice not to have too many cases to have to separately prove in the theorems. Second, their purpose is to try and grasp the underlying essence of computation.

One problem with models of computation is that, when you see them, your first thought might be, 'that's TOO simple -- can that really be made to run any ordinary program?'. And when you are shown the sort of constructions needed to write useful programs in these models, you might think, 'That's overly complicated, and the essence of the program is obscured by the formalism.' Therefore, in order to really understand how to compute in one or another model of computation, it may be easier to work with a different programming language, one which shares the essence of the model, but which is not quite so spartan.

ISAs, short for "instruction set architectures", are the programming languages used to instruct the hardware on a computer. The syntax of an ISA itself is defined at the level of bits, but each ISA typically has one or more associated 'assembly languages' which are a nicer syntax for writing programs using the ISA. In the old days, people used to write programs in these (both ISAs and assembly) directly, but now most people write in higher-level languages which are compiled down to an ISA. ISAs have a close affinity to the architecture of the hardware that they are designed for.

ISAs can be seen as more practical variants of models of computation. Most computing architectures have a close affinity to one of the extant models of computation. There exist 'toy ISAs' for educational or other purposes which are intended to teach ISAs, but which can also be used as more usable variants of the mathematical models of computation.

A 'target language' is a language that another language compiles down to. When a higher-level language like the language 'C' are compiled, they are compiled to a target language, which is an ISA. In addition to ISA target languages, there are also intermediate 'target languages', languages which are compiled to by a higher-level language and which themselves can be compiled to an ISA. The intermediate target languages tend to abstract away from hardware details, sometimes with the goal of providing portability across ISAs. Intermediate target languages are typically written with one higher-level 'source' language in mind, and often can be thought of as somewhat minimalistic models of the semantic primitives of that source language.

In general, target languages are concerned to closely matching hardware and with efficiency in mind; since they are read and written by computers not people, it doesn't matter if the expression of common programming idioms in a target language are tedious or obscure. In contrast, we have the high-level languages, which are designed for the purpose of of allowing humans to specify computations.

So, to get a feel for the different fundamental primitives of computation, which should you learn? The high-level languages attempt to provide constructs that allow one to clearly and concisely express programs. But the models of computation have the virtue of being minimalistic, allowing one to more easily distinguish fundamental primitives from mere syntactic (and semantic) sugar. However, the mathematical models are so spartan that programs written in them are obscure. The ISAs alleviate this problem but contain additional 'accidental complexity' by conforming to their underlying hardware. The target languages have the virtue of abstracting away from the peculiarities of individual hardware architectures, while still being more minimalistic than the high-level languages which they support.

So these are all interesting to learn. For the purpose of learning the essence of computation and its most fundamental primitives, what should you study? You ultimately want to learn models of computation. But instead of learning a model of computatation directly, learning an affiliated ISAs or other target language first (or even a very clean high level language) might be more useful because the programs written in these are clearer (if still tedious). After you know how to write programs in that, then go learn the mathematical model of computation. For example, in order to learn about the Turing machine, I would first learn a toy assembly language, and only then read about the Turing machine model itself. In order to learn about lambda calculus, I would first learn basic Haskell, and only then read about lambda calculus itself. In order to learn combinatorial calculus, I would first learn Nock, and only then read about the SKI combinator calculus. I don't know of any language that implements something too close to te mu-recursive function model of computation, but knowing basic mathematics and also some programming languages that use lots of expressions and which use recursion for iteration (such as Haskell) is probably a good start.