Lambda the Ultimate

SICP gets many nods when it comes to introductory texts to programming and the study of PLs. I've been slowly working my way through SICP in a number of different PLs, most notably Oz and Alice ML. In that process, I've come across Eli Bendersky's methodical solutions to the SICP Exercises in a series of blog posts. His review of SICP is instructive of the role of the exercises:

A word about exercises in SICP. They are numerous, some of them are hard, but the exercises are the best way to really understand what the book tries to teach. In a manner, they’re as integral part of the book as the text itself. The exercises are very well prepared and lead the reader through the examples coded by the authors into greater understanding of the topics taught. At times, it feels like the exercises are specifically designed to force you to think about the essence of the topics, and not just grasp them superficially.

Highly recommended reading for anyone that is working their way through SICP. Unlike my own work, which concentrates solely on code, his explanations are quite good. He uses mostly Common Lisp for the solutions, though resorting to Scheme when it makes for more concise solutions.

Translating code from one programming language to another is a black art. Even if successful in capturing functionality, each PL has its own styles, idioms and community morals. Doing automated translations (which I have done) has more misses than hits. Doing it manually gets you closer but it can require an inordinate amount of time to get it just right. Even so, PL translations are something that I personally enjoy as it is particularly instructive in teaching the strengths and limitations of expressing different concepts (though I usually catch flak for violating the social values of the target language).

My latest postings into this gray area are translations of the remaining Little Books to Oz - consisting of The Little Schemer, The Seasoned Schemer, The Little MLer and A Little Java, A Few Patterns (previous LtU post on The Reasoned Schemer in Oz). The Little Books are the antithesis to recipe books. There's not much code here that can be plugged into a project. The aim is to systematically teach programming thought processes. The books are useful for those wanting to learn Scheme (or ML). But the lessons are also useful even if those are not your particular language(s) of choice. Such didactic material may not be everyone's cup of tea, but they do represent a unique manner in which to teach (and still hoping for The Little Haskeller).

Along a similar line, I've started in on Introduction to Algorithms in Oz. Previously, I made a weak attempt at Knuth which I'll get back to one of these years, but found that translating MIX to higher level languages was tedious and time consuming. The CLRS book is a bit easier to translate, but the language they chose to express algorithms in doesn't seem to map to any exact known programming language in the universe. The language is concise, which was their aim, but it takes some shortcuts and has some peculiarities. Also, like Knuth, the algorithms are very much oriented to having mutable state. (Purely Functional Data Structures is in my queue). Anyhow, I find it interesting that the authors of the two best known book(s) on algorithms chose to invent their own language rather than use an existing PL.

Paul McJones alerts us that the ACM posted PDF versions of some books in its Classic Books Series, which are available to anyone who creates a free ACM Web Account.

Among the currently available books, LtU readers are likely to be particularly interested in Hoare and Jones's Essays in computing science, Adele Goldberg and David Robson's Smalltalk-80: the language and its implementation, and Dahl, Dijkstra, and Hoare's Structured programming.

Long time readers will also know that I highly recommend Papert's Mindstorms: children, computers, and powerful ideas to anyone interested with the effect computers might have on education. Papert's Logo remains to this day the best children oriented programming language, but even if you disagree with me about this, his book is a must read.

A draft textbook by Theodore Sider aimed at philsophy graduate students that while not as technical as computer scientists are used to, may be of interest due to the explicit discussion of extensions (e.g., modal operators), deviations (e.g., multi-valued logic) and variations (such as the Sheffer Stroke) on basic propositional logic.

The book includes chapters on counterfactuals and two-dimensional modal logic that may include material new to PLT wonks.

To quote Richard Zach:

CSLI Lecture Notes are now part of the Stanford Medieval and Modern Thought Digitization Project. That means books such as Unger's Cut-elimination, Normalization, and the Theory of Proofs, Troelstra's Lectures on Linear Logic, Aczel's Non-well-founded Sets, van Benthem's Manual of Intensional Logic, and Goldblatt's Logics of Time and Computation are now available online and for free. (HT: Shawn)

Also of interest here will be McCarthy's Defending AI research, and Modal logic and process algebra : a bisimulation perspective, edited by Venema, de Rijke and Ponse.

Leo Brodie's books Thinking Forth and Starting Forth are now available for download and the first is back in print. This material had been hard to find for a long time!

Shriram Krishnamurthi's excellent book, Programming Languages: Application and Interpretation (PLAI), long available in PDF form, is now available in paperback.

There's also a paid download available, "in case you want to reward the author in kind". A free PDF of the latest version is still available, which "really is the entire book, with no strings attached." The book is now licensed under a Creative Commons license which allows it to be adapted ("remixed") to fit a course.

Here's an overview of the book's approach:

This book unites two approaches to teaching programming languages, one based on a survey of languages and the other on writing definitional interpreters.

Each approach has significant advantages but also huge drawbacks. The interpreter method writes programs to learn concepts, and has at its heart the fundamental belief that by teaching the computer to execute a concept we more thoroughly learn it ourselves. While this reasoning is internally consistent, it fails to recognize that understanding definitions does not imply we understand the consequences of those definitions. For instance, the difference between strict and lazy evaluation, or between static and dynamic scope, is only a few lines of interpreter code, but the consequences of these choices is enormous. The survey of languages school is better suited to understand these consequences.

The book is used as the textbook for the programming languages course at Brown University, taken primarily by 3rd and 4th year undergraduates and beginning graduate (both MS and PhD) students. It seems very accessible to smart 2nd year students too. The book has been used as a textbook at over a dozen other universities as a primary or secondary text.

When published, this collection of essays edited by Greg Wilson and Andy Oram will likely be of interest to LtU readers.

Among the contributors are Brian Kernighan, Simon Peyton Jones (whose contribution we already discussed) and Kent Dybvig.

Take a look at the ToC and let us know which essay titles intrigue you the most...

This will be of interest to LtU readers in India and maybe for others as well.

I just noticed the existence of this O'Reilly book penned, so it seems, by Maurice Naftalin and (believe it or not) Philip Wadler! Is this for real, or a very elaborate hoax? It seems possible, if you remember the history of Java generics, so I guess it's true, but if someone actually saw a copy I'd be reassured...

The blurb, by the way, is from Gilad Bracha who says that this is a crystal-clear tutorial that starts with the basics and ends leaving the reader with a deep understanding of both the use and design of generics. Ya think?!