December 19, 2007

Origin of Advice

Apparently, Gary King needs advice a lot. This reminded me that I posted an article about the origin of advice some time ago in the AOSD mailing list. I think it's a good idea to repost it here to make it available to others as well, so here we go. (I have links for almost all the literature references at the bottom of this article.)

The notion behind advice can be traced back to a paper by Oliver Selfridge [Selfridge 1958]. He introduced the notion of demons that record events as they occur, recognize patterns in those events, and can trigger subsequent events according to patterns that they care about.

A first software system that was obviously heavily influenced by that paper was called PILOT and is described in Warren Teitelman's PhD thesis [Teitelman 1966]. The PhD thesis was supervised by Marvin Minsky, but additionally Warren Teitelman mentions Oliver Selfridge as a strong influence in his acknowledgements. Marvin Minsky and Oliver Selfridge worked both at MIT back then. Anyway, that is the work in which the notion of advice, very similar to before and after advice as we know them today, was actually first introduced. Warren Teitelman later added the concept of advice to BBN Lisp, which was then bought/licensed (?) by Xerox PARC and became Interlisp.

Later, the notion of demons was mentioned in a seminal paper by Marvin Minsky [Minsky 1974] that spawned an interest in framework-based knowledge representation systems. Among others, Daniel Bobrow and Terry Winograd developed and described KRL [Bobrow, Winograd 1976], which was based on the ideas in Marvin Minsky's paper. If I understand correctly, before/after demons played an important role in such systems.

A little bit later, Howard Cannon developed Flavors at MIT, the first object-oriented extension for Lisp, strongly influenced by Alan Kay's Smalltalk. Howard Cannon had written a very influential paper [Cannon 1979-2003] that was, unfortunately, never officially published. He explicitly mentions before/after demons, as do other publications about Flavors, for example [Weinreb, Moon 1980].

I have a copy of Howard Cannon's paper availabe, and I have asked him to make it publicly available, but he still hasn't done this (yet). His is a mind-blowing paper that introduces multiple inheritance, method combinations based on macros - i.e. before and after demons and a first precursor to around methods -, and the notion of meta-protocols that obviously later on turned into metaobject protocols.

The experiences with KRL and Flavors had then been integrated at Xerox PARC into LOOPS (Lisp Object-Oriented Programming System), foremostly by Daniel Bobrow and Mark Stefik, implemented in Interlisp. There is a nice overview page about LOOPS and a download page for the papers mentioned there.

Flavors and LOOPS were chosen as the main bases for the Common Lisp Object System (CLOS) as part of the ANSI standardization of Common Lisp. CLOS was developed by representatives of the various existing object-oriented extensions for Lisp. LOOPS / Xerox PARC was represented by Daniel Bobrow and Gregor Kiczales. This was around 1986 - 1988.

CLOS has before/after/around methods. I haven't been able to spot when around methods entered the scene, whether this was already part of LOOPS or whether this was an addition in CLOS. In Flavors, there were only before/after methods, but there was an extra concept called wrappers that effectively allowed one to express the same thing as around methods in CLOS.

One of the most impressive outcomes of the efforts behind LOOPS and CLOS is the book The Art of the Metaobject Protocol [Kiczales, des Rivières, Bobrow 1991], which I think is one of the most important books in the history of computer science (and Alan Kay seems to agree).

Crista Lopes' paper [Lopes 2002] describes the subsequent history how metaobject protocols were turned into what we think of as aspect-oriented programming today. The main motivations, as far as I understand them, were a) to move from a runtime-based approach, which is natural for metaobject protocols, towards a compile-time based approach and b) to make some of the benefits of being able to manipulate the meta-level available to purely base-level code. Advice play an important role in aspect-oriented programming, but instead of advising just single functions, you can advise whole pointcuts, which are essentially sets of functions described in (more or less) declarative ways.

Robert Hirschfeld, myself and others have taken a different turn with Context-oriented Programming, and focus on a more dynamic approach again. We have taken the idea of crosscutting concerns that emerged in the AOSD community, but dropped the idea of pointcuts, and instead concentrated on new and interesting ways to dynamically activate and deactivate layers, which are potentially crosscutting behavioral program variations. Since you can add new layers at any point in time, you can also effectively add new levels of before/after/around methods at runtime as needed, something that can be achieved in plain CLOS only statically through new user-defined method combinations, or requires recompilation in aspect-oriented language extensions like AspectJ. Here are some links for Context-oriented Programming:

I agree that advice are an important concept in programming, but we have still not seen all the possible and interesting variations yet. Although they have a long history already, there is still a future ahead for them.



Anonymous said...

This is really nice (and helpful!). Thank you.

Bob said...

Interlisp had before, after, and around advice, so around methods would have been a natural outgrowth, especially given the PARC involvement in Loops.

Pascal Costanza said...

[Gregor Kiczales commented on my blog post in private email. By kind permission, I repost it here as a comment. The following is his text.]

Its good to have this history posted, since the question comes up so often.

But I think there's a few pieces missing that you might want to fill in.

First is that the Lisp machines, as well as Maclisp I think, had a macro facility for adding advice to individual functions. Interlisp did as well, and using a combination of that and Masterscope, I believe you could even do things like advise calls within specific functions. In the MIT Lisps the idea was that it was just for debugging. In Interlisps there was more a sense that it could be used as parts of real systems. A key piece that was missing, that wasn't added until pointcuts was compositionality of the mechanism for identifying what we now call join points.

Second is that you are missing CommonLoops. Its important, because it isn't correct that Loops and Flavors were the basis of CLOS, it was CommonLoops and Flavors. CommonLoops was a very different thing than Loops. It was much smaller for one thing, including only OO functionality, not rules and frames etc. As you know, the implementation, PCL, was also written in CommonLisp and portable.

I also think the history between MOPs and AspectJ is mischaracterized. The real difference between MOPs and AspectJ is to provide the modular crosscutting without having an explicit meta-level. Compile time has much less or even nothing to do with it. For one thing, we already had compile time MOPs at the time. For another thing, AspectJ was explicitly designed to support a semantics in which all weaving was delayed to runtime (not just load-time, but actually at the point where each join point ran). For yet another thing, prior to AspectJ, but post MOPs we had the three other AOP languages: RG, D and AML.

I think the point you end with about context layers is important. Except for RG and AML, most of the innovation in the AOP space has been in ways to identify crosscuts (pointcuts, layers, slices). Most systems have stuck to something a lot like advice to talk about what to do at those points. That's not surprising, as I alluded to above, I think the most important mechanism innovation in AOP has been compositional means of talking about crosscutting. So naturally that's where we have all focused most.

Thanks again for writing down this history. I think its good for people to have access to the roots of the ideas.