I am designing a course called Principles of Programming Languages, and in preparation I have been searching for months, actually years, for a standalone recommended textbook. So, I was quite excited when I saw the title of this monograph, part of a very respectable series of books targeted at undergraduate students. In fact, “Springer’s UTiCS Series” has already given us several related books, including another by the same author [1].

The table of contents for this book roughly corresponds to my teaching plan: mathematical background, followed by a toy imperative language with its abstract syntax and operational semantics, and then a toy functional language that introduces types and a semantics for calls. Looking at the detailed contents, the chapters on imperative features, using the toy language SIMP, seem suitable and offer an excellent introduction. Chapter 3 is quite informal and one could argue that it covers concepts that students with programming experience would typically be aware of. Chapter 4 introduces a formal syntax for SIMP and both small-step and big-step semantics. The coverage is traditional, with a de-referencing operator (!) used to distinguish variables as values from addresses.

I am less convinced with the approach taken to cover functional programming. Chapter 5 introduces functional programming via Haskell, rather than the more conceptual approach taken in chapter 3 for imperative features. While Haskell is certainly useful to introduce the concepts of polymorphism, type checking, type inference, and data types, its use within this book is problematic: the coverage is too brief for people who haven’t programmed in a functional language before, and, alas, there are many computing students in this category. What is even more vexing is that the author says that the notation used in the book is “similar to Haskell’s syntax,” which implies it is not Haskell code. In my opinion, when concrete syntax is used, it would be sensible to provide code that can be run; if not, it may be best to keep to a clean, more abstract notation, such as that used in chapter 3.

Haskell is a great language, but it requires a better introduction than provided here. To start with, one problem is that simply typing the first example code given in the book (the definition of the square function) into an interpreter fails, and a new user would not know why this is so: the obscure reason is that function definitions cannot be typed directly into the interpreter’s prompt, but need to be saved into a file that is then loaded. My approach has been to introduce functional programming with CAML, which I am able to run interactively on the screen without needing to store definitions in files; therefore, I am able to present a more pleasant and direct experience to students. (A more subjective reason for my choice of CAML is that I find the syntax more intuitive than Haskell’s syntax, but I acknowledge this is a matter of taste.)

The operational semantics of functional languages are introduced in chapter 6 by making use of a new toy language, called SFUN. A curious decision was made by the author not to make use of lambda calculus and anonymous functions, but requiring functions to always be explicitly named. This probably simplifies the definition of its operational semantics, but is not the most natural flavor of functional programming.

An extension called FUN presented in Section 6.4 does allow functions to be considered first-class objects; however, instead of using lambdas, the author has definitions of functions with formal parameters while uses are in a purely Curryfied form, with an explicit Ap operator for function application. I feel that this lack of functional abstraction makes the treatment much more complicated than it needs to be. It is not as if the lambda notation is omitted completely: it is used when giving the operational semantics for FUN, but in a much more complicated way than needed. In fact, I feel the semantics for FUN as presented is unreasonably complicated for typical students, particularly in Section 6.4.3, and this detracts from its use as an introductory undergraduate module on semantics.

Once the operational semantics of FUN is discussed in chapter 6, it would be good to relate this back to Haskell. This would help students relate the theory to practical matters and unify the chapters. However, this is not done, and in chapters 7 and 8 Fernández moves on to an introduction to logic programming and the principles of unification and resolution. These are very interesting concepts and it would be worth including them in a leisurely semester-long offering; it would probably be difficult to fit them within a ten-week term, where students may already be struggling with several language paradigms and semantic notions. An alternative would have been to look at notions of objects and classes, which are probably more relevant to current programming cultures.

How could functional programming be introduced in a more intuitive way? I prefer the more traditional approach taken by Dowek and Lévy in another book in the same UTiCS collection [2]. There, we have PCF with nameless Curryfied functions, used to define and compare call strategies, big-step and small-step semantics, type inference, references, and assignments. It provides more in-depth coverage at the cost of breadth: there is no introduction to functional programming practice, or logic programming. But this may be easier to use within a focused ten-week term.

There is a minor point that is, to me, quite serious: all of these UTiCS books seem to have been formatted by the authors themselves, without enough attention to readability. LaTeX is great as it allows more direct control of typesetting by authors, and it is good that publishers allow authors to take responsibility for formatting. I’m sure it reduces cost as well. But this devolution of the typesetting role does bring responsibility to the author to invest some thought into making the final product as clear and pleasant to read as possible. In both books (Fernández, and Dowek and Lévy), the authors make extensive use of typewriter font in presenting semantics, which in my opinion is a very bad decision. It makes the material much less pleasant to read and increases the effort for understanding. Also, it is not enough to put formulas in a math environment and hope for the best; one of the most egregious failures is on page 138, where spacing isn’t introduced within the term T r u e y x. I’m sure that not everyone is so sensitive to typesetting, but I find that it is a good investment toward a really readable output.

Overall, there are many things in this book that would lead to its recommendation as a course textbook: it provides a good breadth of material, and a stepping stone from programming experience to more theoretical aspects of programming languages. Some of the chapters are very accessible and can be followed easily. However, chapters 5 and 6, which cover the most challenging material, have several flaws that make the book’s use as a standalone textbook for undergraduates problematic. On the other hand, it would be an excellent addition to a reference list that could be used to inform a solid understanding of programming language theory.