Levi's Lisp Log

Guy Steele

Bookpool.com, an online computer bookseller, has put together a section where computer book authors list their favorite computer books from the last ten years. I wasn't familiar with many of the participating authors, but I was pleased to find Guy Steele among them.

His list of favorite books reveals a lot about him, and I hope to pick up some of them. The list is pretty well-rounded, from Knuth's Computers & Typesetting collection to The Annotated Alice and The Art of the Incredibles. Interesting stuff!

WireWorld Computer

You've probably heard of cellular automata before, at least in the form of Conway's Game of Life. There's another intereating cellular automaton called WireWorld, which performs a model of electrical signal propagation across a grid.

A couple of dedicated souls decided to create a fully-functioning simulated computer in Wireworld. This is a wholly remarkable feat, considering the simplistic nature of Wireworld itself. The computer has another interesting property in that it only has a single instruction, yet is fully Turing-complete thanks to special-purpose registers.

Denotational Semantics

A friend of mine showed me some examples of the qualifying exams he'll have to take to get accepted into his Ph.D. program, and the Programming Language exams all asked the examinee to give the denotational semantics of a simple language for which the syntax was given.

Although I'm somewhat familiar with what it means to talk about semantics (as opposed to syntax and pragmatics), I'd definitely like to have a better understanding of how one actually gives a formal semantics of a language.

To this end, I did a little bit of searching, and found an out-of-print textbook entitled Denotational Semantics: A Methodology For Language Development. I've read through the first couple of chapters and the table of contents, and it seems like it's exactly what I was looking for.

So far, the introduction to the concepts has been clear, and the mathematics have been built up without too much prior knowledge expected. Some other CS theory textbooks have lost me in their heavy math from the get-go, so I'm glad my lack of experience with mathematical notation isn't holding me back on this one.

Wirth's Compiler Construction

PLT Online has added a new text to the library: Niklaus Wirth's Compiler Construction. This is a remarkably short book, yet it covers the essentials of building a compiler, from lexical analysis to code generation. The source and target languages used are now pretty obscure (though they should look familiar to anyone who's seen Pascal), but the great thing about theory is that it transcends implementation details. This would be a good text for a self-study student to use as an introduction to compiling.

SICP

I finally got around to picking up my copy of Structure and Interpretation of Computer Programs again, and I finished reading through the first chapter, Building Abstractions with Procedures. I've been programming in Scheme for a while, so the language concepts were mostly review, but the presentation was enlightening. Abelson and Sussman show how procedures, and later higher-order procedures, can be used to abstract complex numerical processes into simple, clear programs.

The second chapter covers data abstractions, which should be interesting. I'll probably work a few more of the exercises in this chapter than I did in the first. The temptation to just keep reading is pretty strong, but the exercises are where the bulk of the learning happens.

I imagine most people who would read a blog explicitly about Lisp are already somewhat familiar with the book, but if by chance you are not, I highly recommend reading it. And since it is available in full online, there's no excuse not to!