Levi's Lisp Log

The Problem With Threads

I just read a Technical Report from UC Berkeley's EE/CS department entitled The Problem With Threads, which succinctly and clearly captures the problems with the concurrency mechanisms in our currently popular programming languages. It should be very readable to a lay programmer, since only a small section contains formalisms and most unfamiliar terms are defined in the text or footnotes.

To sum it up, threads (shared-memory concurrency) are an inappropriate method of bringing concurrency to a program because they destroy the inherent determinism of sequential programming languages. The tools we have to help deal with the nondeterminism only chip away at the combinatorial explosion of program interleavings, leaving so much opportunity for error that designing reliable and robust multithreaded software is futile.

The report notes that solutions to the problem that retain as much determinism as possible have existed for years, but have not caught on. The author suggests that instead of creating new programming languages, new coordination languages should be used to coordinate components written in familiar languages.

It's a very thought-provoking paper, and I think the conclusions are right on, as much as I'd like a new language to catch on. Massive concurrency is coming, and our current languages are not equipped to tackle it alone.

Goedel's Famous Proof

Kurt Goedel shattered the hopes of mathematicians who aimed to create a comprehensive formal theory under which all true statements of mathematics could be proved by proving that such a system could not exist. This incompleteness theorem has repercussions for computer science, since a limitation on formal systems is also a limitation on computer programs.

Martin Herzel has provided a translation of Goedel's famous proof from German to English and from Goedel's notation to more familiar contemporary notation. After reading about this proof from numerous other sources, it's great to be able to read it (almost) directly myself.

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!

Markdown for Common Lisp

I've finally got my implementation of the Markdown text formatting language to a state where it's usable. It complies with almost all of the Markdown syntax specification, such as it is, and is comparable in execution time to the perl and python versions I tried it against.

It takes a string of Markdown-formatted text, processes it, and spits out an s-expression that can be fed into an HTML generator such as Peter Seibel's FOO (described here and part of this source package).

I'd be interested to get feedback on it; some bug-fixes, or suggestions for stylistic improvement would be appreciated. This is only my second Common Lisp program of any size, so it's bound to be sub-optimal. If you want to try it out or take a look at it, you can download it.