March 26, 2009

P-Cos Blew My Mind

This post contains my impressions about the rest of ILC 2009. I'll start off with something that really impressed me.

One of the things I have been thinking about lately is database schema evolution. The flip side of database schema changes are the corresponding changes in the client code they entail. Combining the two with live system upgrades can potentially give rise to inconsistencies. Even ignoring databases, loading code into a multithreaded Lisp image can result in undesired behaviour since the loading is non-atomic.

This problem was discussed on comp.lang.lisp several years ago, with the general consensus being that some sort of atomic loading mechanism was needed to address the problem.

However atomic loading alone does not eliminate inconsistencies for systems providing services via asynchronous protocols, such as web applications. Any users in the middle of a workflow consisting of a chain of requests to HTTP resources will be affected if any of those HTTP resources are changed.

Pascal Costanza came to the rescue by presenting (during a lightning talk) a solution utilizing context-oriented programming. Each set of updates was integrated into the system as a new layer. Atomicity is provided by the fact that layers can be (are?) activated atomically, and can be made completely independent of each other. By associating layers with web application sessions, Pascal was able to preserve consistency for those users in the middle of a session during the time of update.

In a fascinating discussion on protocol versioning on Jane Street's OCaml blog a while back someone advocated essentially the same approach to the problem by utilizing two servers running different versions of the application. Pascal's context-oriented approach not only eliminates the need for the extra hardware (one server for each version of the protocol), but also provides an elegant way to structure the code for multi-version protocols, and to apply other, orthogonal updates that would affect users of all protocols provided by the system, which would otherwise require backporting patches.

If database access is implemented as an abstraction layer that acts as a protocol, the same technique can be applied to schema changes as well.

From the above discussion it is easy to overlook a really neat fact, but Nick Levine's lightning talk came to the rescue: load and fasls make a really great patch distribution mechanism. You can view the code from his talk here.

Shriram Krishnamurthi gave a very nice talk about hooking kids on Scheme by letting disadvantaged inner-city middle-schoolers put lambdas in their lambdas so they can make videogames in their cellphones. Purely functional programming a-la How to Design Programs turns out to be a really great way to teach algebra. Shriram also dislikes the OLPC project and thinks Etoys is weak.

Gerald Sussman gave a talk that essentially argued against formal methods for systems design, and for extensible systems with flexible failure modes.

One of the key reasons why MIT shifted its introductory CS curriculum away from the SICP-style bottom-up abstractions building approach is that the behaviour of modern systems components is too complicated for it to be practical for them to either be well-specified, or modelled in a reductionist way. A lot of the time engineers have to resort to an empirical approach to discovering the actual semantics of a sub-component.

To manage this complexity, Sussman argued for open systems that permit a great degree of extensibility and continue to function under various failure modes. An example he used was an autopilot system: it should continue to work under unexpected conditions such as control surface failures. This echoes some of the ideas of Richard Gabriel about mob software. Although Gabriel was at the conference, the term itself never came up, but Richard did object to macros at the macros debate by mentioning that they would be a hindrance to constructing systems worked on by thousands of programmers.

Fail-fast behaviour of a whole system under unexpected circumstances is something that formal specifications cannot avoid. A great quote from Sussman was: "proofs considered harmful." What Sussman was arguing for, in his words, was high-quality abstract specifications, not low-quality well-specified ones.

Sussman presented several ideas about taking inspiration from biological systems, among them biological degeneracy, which can best be summed up as "doing different things to get the same result," and the fact that a relatively small number of genes are responsible for common physiological structures in organisms.

The bio-mimetic argument was echoed again in a lightning talk by someone whose name I unfortunately cannot recall or look up (as the full list of lightning talks has not yet been posted anywhere). One of the things mentioned was parallelism in multi-cellular systems - of course I had to jump in and point out that the best lesson we can take away from parallelism in the real world is a rejection of the concept of global state (more on that in an upcoming post).

Olin Shivers gave essentially the same talk about his system for expressing scoping and iteration in terms of graphs as he did at Danfest, and this time wasn't any more exciting. Someone actually fell asleep and started snoring loudly a few rows down from me. The discussion at the end was quite good though, one of the things Shivers emphasized that echoed Sussman's keynote was the fact that unspecified behaviour actually gave you more opportunity for expressive power.

I gave a lightning talk based on a blog post I made previously, arguing that the criteria for whether language X is a Lisp should be how well you can write a metacircular evaluator for that language. No one booed or threw things at me, and some very smart people made insightful comments, so I think it went ok. The question of static typing came up, and after the talk I had a big argument with a couple of people trying to explain what type systems are and what they do. Typed calculi need to be taught as part of an undergrad CS cirriculum - most people have a very skewed understanding of what type systems are and this lets language "designers" get away with doing a lot of stupid shit.

March 24, 2009

ILC 09 Pt. 0

Flew into Boston on Monday, arrived at the Stata Center just after the conference lunch. Highlights so far:

Michael Greenberg's lightning talk about TRAC, both for being probably the most well-prepared 5 minute talk ever, and for explaining the key essence (self-modifying code) of pure macro languages. Later during the macros debate Greenberg made the very insightful point that conceptually the Lisp language and Lisp macros are two distinct systems and need to be reasoned about as such.

Joe Marshall's daughter's insight about the subject of his talk: "[continuations are] just autosave for your program!"

Pascal Costanza's superhuman knowledge of Lisp history, wit, and strong opinions.

Some things that have been done to death and should be irrelevant but still managed to be somewhat entertaining: the "future of Lisp" panel and the "are macros bad" debate.

March 15, 2009

Parenscript birthday present

A while ago I mentioned I was going to announce some exciting news about web development tools. Shortly thereafter my priorities changed, and I shelved the project with the intention of picking it up again in the future. Then I remembered about LispNYC's participation in the Google Summer of Code program - if I can't do the project now, why not try to get funding from Google to have a student work on it?

Here is what all this is about:

The PSDE project aims to develop an Emacs-based JavaScript programming and debugging tool for AJAX-based RIAs. The implementation will provide an unobtrusive client-side script that can be loaded alongside any JavaScript web application, and an Emacs interface (REPL) that will enable debugging of remote and mobile clients, including the possibility of no-reload drop-in for live user sessions.

Along with an interactive prompt/REPL, PSDE will provide a profiler, tracing and logging facilities, a DOM inspector, a completion and documentation system for DOM symbols, and other useful web programming tools, both by using the reflective capabilities of JavaScript, and by providing hooks (a la Open Implementation) into the Parenscript compiler to provide metaprogram information that cannot be gleamed using runtime techniques or analysis of JavaScript code.

In addition to providing a valuable tool to the web development community, the OI extensions to the Parenscript compiler included as part of the PSDE project will be useful in their own right to those wishing to create other web development tools based on Parenscript, or web developers using Parenscript and needing advanced JavaScript generation capabilities.

The project has its roots in the "browser Comet REPL" demo I gave during my talk about Parenscript at LispNYC in September 2007, but the idea of making a "browser SLIME" didn't occur to me until this past November, when Daniel Gackle told me: "Why don't you make a browser SLIME?"

If you are a student that might be interested in this project and qualify to participate in Google SoC, or know of such an individual, get in touch: I'll be happy to answer any questions and help you with preparing an application. Google will start accepting student applications March 23rd, with the cut-off date being April 3rd.

UPDATE: LispNYC has not been selected as a mentoring organization for SOC 2009. I would like to fund this project myself, but currently cannot afford it.

March 14, 2009

Parenscript's 4th birthday

Today is a day of many celebrations. As most of you are aware March 14 is π Day. It also happens to be Einstein's birthday.

Four years ago, Manuel Odendahl announced the release of Parenscript to the public. Reflecting on the original post in the context of what Parenscript is today, the power and appropriateness of Manuel's design have more than proven themselves, but also I see the amount of exciting work that is still ahead.

March 13, 2009

I think I finally understand what Alan Kay is saying about Lisp

Joe Marshall recently wrote a series of very entertaining blog posts telling the story of his first experiences with Lisp:

I had a similar experience with Lisp - I didn't go to MIT or take 6.001, but reading the first couple of chapters of SICP changed my entire outlook on computer programming. By the time that happened (the summer of 2002, right before I started university), I was already somewhat proficient with C, although I wasn't particularly interested in computer programming as an activity in and of itself.

The funny thing is I was exposed to Scheme my first year of high school through Mike Zamansky's MCS1 at Stuy. That experience wasn't particularly memorable, even less so was one of the other programming languages used in the course (Python, I think?). On the other hand the course also taught a whole bunch of really neat stuff in StarLogo, which as they say in Canada was the cat's ass.

An even more amusing fact is that after going to see the professor before the start of the first term and taking the challenge exam that would give me credit for the first computer science course, I decided that since the university computer science courses didn't look anything like SICP, I would probably be better off investing my time in a math degree. The algebra and calculus examples in SICP were my first exposure to elegant computational mathematics, and a key reason for choosing math and not something else.

What does this have to do with Alan Kay?

Yesterday before falling asleep I was plagued by the question: why don't I enjoy using Haskell as much as Lisp? Haskell is purely functional, it features a really neat and unobtrusive type system, which when taken together with the great pattern-directed invocation programming style provides a better alternative to object-oriented programming. It's a really great programming language.

Could the reason be the ugly syntax? No, that's easy to fix. The type system doesn't bother me. There's a template system for both Haskell and Liskell syntax that provides preprocessor-style macros, but monads actually provide a much more powerful way of building control abstractions than macros do.

The only thing I could think of that Lisp has that Haskell can't provide is a dynamic runtime system. It's as if Lisp comes with a really neat invisible virtual machine.

Among the many nice things Alan Kay says about Lisp, the term late binding comes up often. Practitioners of programming languages that Alan Kay did not have in mind when he invented the term "object-oriented" have taken it upon themselves to equate this to the concept they term dynamic binding, which they define to be type-directed dispatch done at runtime.

This is a textbook example of cargo cult programming. Dynamic types and runtime dispatch are not axioms of Lisp and Smalltalk, they are the emergent properties of self-describing computational systems. The key is that the definition of Lisp is written in Lisp. The "invisible virtual machine" in Lisp is Lisp. That is what Alan Kay means by late binding.

Well, this insight did take almost seven years, but at least now I have a snappy label for the dynamic languages du jour whose existence helps put a lot of computer book publishers' editors' kids through college and kills hundreds of thousands of trees every year: cargo cult programming languages.

The question that remains unanswered is why isn't Haskell self-describing? The reason is that there are actually two computational systems behind Haskell: one for the language itself, and one underlying the type system for the language. If type systems could be expressed in a metacircular way by the systems they were trying to type, they wouldn't be able to express anything about types (restrictions on computational power) of that system.

You can read more about the metacircular definition of Lisp in several books. The first of these is the original Lisp 1.5 Programmer's Manual; Alan Kay has called the metacircular definition of Lisp provided there "Maxwell's Equations of Software." SICP includes a section on constructing a metacircular evaluator, and a whole chapter based around extending that evaluator with non-determinism and logic programming. The most thorough examination of the metacircular evaluation formulation of Lisp is present in John Allen's highly recommended 1978 book, Anatomy of Lisp.

March 12, 2009

Frameworks and the conjunction fallacy

Frameworks are great. After all, some helpful way to do X combined in some helpful way with some helpful way to do Y must be a whole lot more helpful than just a way to do X and just a way to do Y, right?

Wait a minute, anyone who has used a framework might say, what if someone wants to do Z instead of Y? Why, of course, say the framework "architects," we'll just provide a helpful way to help you choose helpful ways.

How helpful! Now not only do you have to know how to do X and how to do Y and how the framework helps you do X in a helpful way with doing Y, but you also need to know the helpful mechanisms behind letting you choose the helpful ways.

Clearly the original argument for helpfulness broke down somewhere. But where, and why?

The underlying fallacy behind the majority of software design today is the belief that computer systems can be "useful" and "helpful." Useful and helpful for doing what? For doing what they were designed to do. Stated in these terms it is immediately apparent that this mindset is a tautology. Completely useless as a basis for reasoning.

Is there a better way of thinking about software? Let's start by asking why. The entire motivation underlying our enterprise is the desire to accomplish X and Y. Each step we take can either bring us closer to that goal, or not. Given that time and other resources are finite, each step that does not bring us closer to the goal is "unhelpful" - it gets in the way of what we want to do.

I believe the right way to think about computer systems is as things that get in the way of what you want to accomplish. This way the goal of software design becomes not getting in the way of what you want to do.

Given this approach it immediately becomes obvious that the argument presented at the start of this post is simply a conjunction fallacy. Likewise many other "reasonable assumptions" about software that are not borne out by experience can be shown to be flawed a priori. Most importantly, this mindset helps prevent such "reasonable assumptions" from being taken up in the first place.

While this post debunked one of the arguments used to both justify the development of frameworks and their use, the decisions surrounding the latter are also driven by other logical fallacies, and, like the vast majority of human decision-making, by emotions. In a forthcoming post I will examine some of these factors.

[Major thanks to Ryan Holiday for providing the inspiration for this blog post.]

Assorted Lisp news

Last week I came across Bartosz Milewski's blog post criticizing the proposed implementation of futures in the forthcoming C++ standard. Milewski's chief dissatisfaction was the absence of a mechanism for composition. PCall (which I've blogged about before) was in a similar position, so I decided to implement a mechanism for non-deterministic composition and send in a patch. Milewski's blog post also spawned an excellent discussion about futures on Lambda the Ultimate.

Today I rewrote the Parenscript tutorial to use the recently released 1.0 version of Hunchentoot instead of AllegroServe. Edi Weitz and Hans Hübner did a major redesign for the 1.0 release, breaking interface compatibility with previous versions of Hunchentoot. The new interface provides greater Open Implementation capabilities, and makes a sharp demarcation between methods intended for OI and those for regular server programming. I like it.

Beware that if you're not using LispWorks, the 1.0 release of Hunchentoot depends on certain library capabilities (I suspect it's usocket but haven't verified) that as of the time of writing haven't been made into official releases yet. This means that if you get Hunchentoot dependencies via ASDF-Install it will likely not work (for me, it just instantly dropped all incoming connections) - use clbuild to get the latest repository versions of the dependencies.

Earlier last year I found out about Doug Hoyte's Let Over Lambda and after reading the sample chapters promptly got excited. I visited the site recently and found out that the book was published a few months ago. This morning my copy arrived in the mail - I'll be posting a review here later. In the meantime you can obtain your own copy.

LispNYC is once again looking to participate in Google's Summer of Code program. The list of accepted organizations hasn't been announced yet, but you can start proposing summer projects on the LispNYC website.

Just found out about For a non-English generalist Lisp website the forum gets a fair amount of traffic.

March 10, 2009

Cassandra of Facebook, or A Tale of a Distributed Database, part 2

This is the third in my series of blog posts about Facebook's Cassandra distributed database. Part 0 discussed the background of the problem Cassandra is meant to address, while part 1 gave an overview of the distributed systems techniques employed by Cassandra. This post is a scattering of my observations from reading the code.

The most obvious feature of Cassandra's code is the pervasive presence of checksums in communication and data handling modules. Checksums are used both to detect data and message corruption, and as a means of finding out if replicated nodes are out of sync.

Cassandra is a production system with a large deployment and the management features present reflect this. There is code for measuring node statistics and sending them off to a collection server. Nodes register themselves with both Zookeeper and JMX cluster-management services, although exactly what both of those are used for at Facebook is unclear as their cluster-management tools have not been released as free software.

The mechanism for selecting nodes for replication can be customized to use metadata about machines to choose nodes on redundant networks/power grids/backplanes/etc to increase availability. The strategy provided in the code indicates that Facebook structures their Cassandra deployment using IPv4 addresses so that all the machines with the same third octet of an address are in the same rack, and all machines with the same second octet are in the same datacenter.

The gossip protocol, besides being used for failure detection, is also used for load-balancing the cluster. Workload is measured as the number of requests per number of keys in a given time window that are handled by a node responsible for a particular interval of the key ring, and is disseminated by each node to the others. To alleviate high load, a node may move itself around on the key ring to more evenly distribute the keys between itself and a lightly loaded neighbor. The approach is an implementation of Abdallah and Le's Scalable Range Query Processing for Large-Scale Distributed Database Applications.

The gossip protocol itself is rather interesting, featuring three stages (gossip message, ack, ack-ack).

An interesting artifact is the com.facebook.infrastructure.continuations package, which has some stubs based on the Javaflow bytecode continuation transformer. You would guess this would be used for the server code since it's based on non-blocking IO, but the server code is actually hand-coded staged event-driven. The stubs in the package aren't used anywhere else, which means that some other Facebook project must be using those. I wonder what for?

The code itself can be found at, but seems to be in the process of being moved to a different repository. In the meantime, there is an active git repository at that features community-submitted bugfixes and improvements.

To end on a light note, it is refreshing to find that the authors of Cassandra give a nod to the LOLspeak code commenting guidelines:

* 3. Set one of teh messages to get teh data and teh rest to get teh digest
// 4. SendRR ( to all the nodes above )
// 5. Wait for a response from atleast X nodes where X <= N and teh data node
* 6. If the digest matches return teh data.

Cassandra of Facebook, or A Tale of a Distributed Database, part 1

This is the second part of my examination of the Cassandra distributed database. Part 0 described the problem that Cassandra is trying to address; this post will describe the distributed systems techniques that it utilizes to that end.

The basis for this post is a presentation describing Cassandra by Prashant Malik, Karthnik Ranganathan, and Avinash Lakshman given to the Facebook staff and available online: (hosted on Facebook, an account is required for viewing). James Hamilton provides a summary of the presentation on his blog.

Underlying Cassandra is the technique of consistent hashing. Using consistent hashing, the key space can be modeled as a circle of the keys' hash values, and nodes assigned to points on that circle, so that a node is responsible for an interval of the circle of key hashes between itself and its next neighbor. Nodes leaving or joining only affect their previous neighbor, and lookup has a very low communication cost. Due to its great simplicity and robustness compared to other mechanisms, consistent hashing is probably the most significant development in distributed systems in the 1990s - virtually all current peer to peer systems are based on it.

Cassandra uses a gossip protocol for determining cluster membership and for failure detection (and for load-balancing, discussed in the next blog post). Failure detection in this context means the various failure detector mechanisms that can be used to achieve consensus in asynchronous distributed systems with unreliable nodes. Given unlimited time to finish a task, it is impossible to distinguish a dead node from one that is slow - failure detectors use timing assumptions and heartbeat messages between nodes to provide an answer (with some degree of uncertainty), something that would otherwise require a synchronous network between nodes. Cassandra implements a failure detector based on Hayashibara et alia's The φ Accrual Failure Detector; the presenter points out that some "ghetto" failure detectors with simpler mechanisms do not work very well in practice.

Each interval of the hash circle is replicated on a set number N of nodes. Cassandra provides a choice of replication scheme: optimistic replication, which gives eventual consistency, or stricter approaches for writes and reads: quorum write and sync on read. Optimistic replication allows writes even if all nodes that are responsible for storing the particular key are down: the node receiving the request logs it and later hands it to the appropriate nodes when they come back up. Under the quorum write scheme, a write is not successful until at least a specified x number of the N total replicas have performed the write. It would seem that if x=N, then we get both monotonic read and write consistency. Sync on read synchronizes all replicas on each read request, which gives monotonic write consistency.

March 6, 2009

Recommended Common Lisp tutorials.

Here are a couple of CL tutorials that I've recently rediscovered and I think are worth sharing:

The first is Chaitanya Gupta's tutorial on the CL condition system. The examples provide a good guide to how restarts work and how you can use them.

Next is Adam Petersen's tutorial on building web applications using Hunchentoot, CL-WHO and Elephant. It shows all the necessary basics from beginning to end, and I don't think I have to state twice that I like the no-framework approach to web development Adam is demonstrating. There's even a little use of Parenscript to generate JS. If someone asks for a tutorial on how to build web applications using Lisp, this is the one I'd refer them to.

March 5, 2009

Cassandra of Facebook, or A Tale of a Distributed Database, part 0

One of the most natural and popular tendencies in the application of distributed systems theory is the construction of distributed databases with the hopes of providing improved availability and scalability (in the number of requests processed per second) via data replication. While distributed queries and transactions are obviously needed for some kinds of databases, what underlies every database is the ability to read and write a sequence of bytes to some place denoted by another sequence of bytes. In database jargon this is commonly called a storage engine, while in a distributed system this can be seen as a type of distributed shared memory.

Any kind of database providing access to more than one client at a time must deal with concurrency issues and hence provide some kind of consistency model for data access and manipulation. This can make constructing distributed databases either easier or harder, as the underlying consistency model of a chosen distributed implementation can be exposed directly as that of the database, or several distributed mechanisms have to be combined in complicated ways to provide the properties mandated by the stated consistency model of the database.

Choosing a given consistency model involves large trade-offs in the performance, simplicity and ease of maintenance of the distributed database implementation. Ideally, all the nodes of the system would play the same role, and adding new nodes would incrementally improve the availability, capacity, and number of requests the system can handle. Because of the communication and synchronization overhead necessary for implementing stricter consistency models, the improvement in those aspects as a function of nodes in the system displays the quality of diminishing returns (and may in some cases provide negative ones).

Fortunately, many applications do not require strict consistency models of their database. The first to go is usually the requirement for multi-operation transactions with the ACID property. This provides the greatest improvement in potential scalability as both the locking and multi-version timestamping mechanisms for implementing transactions degrade in performance with increased contention between nodes.

The fad du jour in distributed databases is the distributed non-transactional non-relational database. It seems there is a new project implementing a distributed key-value, document-oriented, or "loose schema" database announced every couple of months.

Despite the hype, only a handful of these projects have large deployments. Even rarer is coming across someone who has worked on more than one such database. These facts alone make Facebook's Cassandra stand out. Cassandra was developed and is currently deployed inside Facebook to handle the user messaging feature. One of the developers of Cassandra, Avinash Lakshman, has previously worked on Amazon's internal Dynamo distributed database.

Fortunately for those of us who do not work on messaging at Facebook, the Cassandra source code has been released under the Apache 2.0 free software license. This is the first in a trilogy of blog posts examining Cassandra's use of modern distributed systems techniques and my observations from sitting down and reading the code.

Peer-to-peer synchronized simulations

It seems it's been a while since I wrote anything about distributed systems. The next few posts should hopefully make up for that.

To kick things off with some light observations, I've recently (thanks to a whole bunch of people in my network) come across this 2001 article describing the multiplayer system of Age of Empires.

The system is a peer-to-peer simulation where input from each player in the form of commands is synchronized across all nodes in discrete "game turn" steps, whose real-time duration is calculated as a function of latency between the nodes and the framerate at which the nodes can render the simulation.

It's interesting to compare the Age of Empires system to that of Croquet (I've blogged about Croquet before). Like Age of Empires, Croquet is a peer-to-peer system. The TeaTime architecture behind Croquet can be thought of as a distributed object simulation where messages between objects are what gets synchronized across nodes.

Where Croquet and the AoE multiplayer system differ is in how time and synchronization is handled. TeaTime extends Reed's multi-version timestamping with the notion of pseudo-real time and uses that notion to enable deadline-based scheduling for message processing, with synchronization being achieved via two-phase commit. This allows the decoupling of simulation rendering speed from message synchronization. Unlike the AoE system, this approach is unaccomodating to high-latency nodes.

One thing I found interesing about the AoE article is the large number of synchronization bugs (a lot of them relating to PRNG generation) that the developers encountered.