Chapter 1

General-purpose computers have the amazing property that a single piece of hardware can do any computation imaginable. Before general-purpose computers existed, there were special-purpose computers for arithmetic calculations, which had to be manually reconfigured to carry out different calculations. A general-purpose computer, on the other hand, has the configuration information for the calculation in the computer memory itself, in the form of a program. The designers realized that if they equipped the computer with the program instructions to access an arbitrary memory location, instructions to branch to a different part of the program based on a condition, and the ability to perform basic arithmetic, then any computation they desired to perform was possible within the limits of how much memory, and patience waiting for the result, they had.

These initial computer programs were in machine language, a sequence of bit patterns. Humans understood this language as assembly language, a textual version of the bit patterns. So, these machine languages were the first programming languages, and went hand-in-hand with general-purpose computers. So, programming languages are a fundamental aspect of general-purpose computing, in contrast with e.g., networks, operating systems, and databases.

1.1 The Pre-History of Programming Languages

The concept of general-purpose programming in fact predates the development of computers. In the field of mathematical logic in the early 20th century, logicians created their own programming languages. Their motivation originally sprang from the concept of a proof system, a set of rules in which logical truths could be derived, mechanically. Since proof rules can be applied mechanically, all of the logically true facts can be mechanically enumerated by a person sitting there applying all of the rules in every order possible. This means the set of provable truths are recursively enumerable. Logicians including Frege, Church, and Curry wanted to create a more general theory of logic and proof; this led Church to define the lambda -calculus in 1932, an abstract language of functions which also defined a logic. The logic turned out to be inconsistent, but by then logicians had discovered that the idea of a theory of functions and their (abstract) computations was itself of interest. They found that some interesting logical properties (such as the collection of all truths in certain logical systems) were in fact not recursively enumerable, meaning no computer program could ever enumerate them all. So, the notion of general-purpose computation was first explored in the abstract by logicians, and only later by computer designers. The lambda-calculus is in fact a general-purpose programming language, and the concept of higher-order functions, introduced in the Lisp programming language in the 1960’s, was derived from the higher-order functions found in the lambda-calculus.

1.2 A Brief Early History of Languages

There is a rich history of programming languages that is well worth reading about; here we provide a terse overview.

The original computer programming languages, as mentioned above, were so-called machine languages: the human and computer programmed in same language. Machine language is great for computers but not so great for humans since the instructions are each very simple and so many, many instructions are required. High-level languages were introduced for ease of programmability by humans. FORTRAN was the first high-level language, developed in 1957 by a team led by Backus at IBM. FORTRAN programs were translated (compiled) into machine language to be executed. They didn’t run as fast as hand-coded machine language programs, but FORTRAN nonetheless caught on very quickly because FORTRAN programmers were much more productive. A swarm of early languages followed: ALGOL in ’58, Lisp in the early 60’s, PL/1 in the late 60’s, and BASIC in 1966.

Languages have developed on many fronts, but there is arguably a major thread of evolution of languages in the following tiers:

  1. Machine language: program directly in the language of the computer
  2. FORTRAN, BASIC, C, Pascal, ...: first-order functions, nested control structures, arrays.
  3. Lisp, Scheme, ML: higher-order functions, automated garbage collection, memory safety; strong typing in ML

Object-oriented language development paralleled this hierarchy.

  1. (There was never an object-oriented machine language)
  2. Simula67 was the original object-oriented language, created for simulation. It was FORTAN-like otherwise. C++ is another first-order object-oriented language.
  3. Smalltalk in the late 70’s: Smalltalk is a higher-order object-oriented language which also greatly advanced the concept of object-oriented programming by showing its applicability to GUI programming. Java is partly higher order, has automated garbage collection, and is strongly typed.

Domain-specific programming languages (DSLs) are languages designed to solve a more narrow domain of problems. All languages are at least domain-specialized: FORTRAN is most highly suited to scientific programming, Smalltalk for GUI programming, Java for Internet programming, C for UNIX system programming, Visual Basic for Microsoft Windows. Some languages are particularly narrow in applicability; these are called Domain-specific languages. SNOBOL and Perl are text processing languages. UNIX shells such as sh and csh are for simple scripting and file and text hacking. Prolog is useful for implementing rule-based systems. ML is to some degree a DSL for language processing. Also, some languages aren’t designed for general programming at all, in that they don’t support full programmability via iteration and arbitrary storage allocation. SQL is a database query language; XML is a data representation language.

1.3 This Book

In this book, our goal is to study the fundamental concepts in programming languages, as opposed to learning a wide range of languages. Languages are easy to learn, it is the concepts behind them that are difficult. The basic features we study in turn include higher-order functions, data structures in the form of records and variants, mutable state, exceptions, objects and classes, and types. We also study language implementations, both through language interpreters and language compilers. Throughout the book we write small interpreters for toy languages, and in Chapter 7 we write a principled compiler. We define type checkers to define which programs are well-typed and which are not. We also take a more precise, mathematical view of interpreters and type checkers, via the concepts of operational semantics and type systems. These last two concepts have historically evolved from the logician’s view of programming.

Now, make sure your seat belts are buckled, sit back, relax, and enjoy the ride...