Lambda the Ultimate

Cloning-Based Context-Sensitive Pointer Alias Analysis Using Binary Decision Diagrams, John Whaley and Monica S. Lam. PLDI 2004.

This paper presents the first scalable context-sensitive, inclusion-based pointer alias analysis for Java programs. Our approach to context sensitivity is to create a clone of a method for every context of interest, and run a context-insensitive algorithm over the ex-panded call graph to get context-sensitive results. For precision, we generate a clone for every acyclic path through a program's call graph, treating methods in a strongly connected component as a single node. Normally, this formulation is hopelessly intractable as a call graph often has 10^14 acyclic paths or more. We show that these exponential relations can be computed efficiently using binary decision diagrams (BDDs). Key to the scalability of the technique is a context numbering scheme that exposes the commonalities across contexts. We applied our algorithm to the most popular applications available on Sourceforge, and found that the largest programs, with hundreds of thousands of Java bytecodes, can be analyzed in under 20 minutes.

This paper shows that pointer analysis, and many other queries and algorithms, can be described succinctly and declaratively using Datalog, a logic programming language. We have developed a system called bddbddb that automatically translates Datalog programs into highly efficient BDD implementations. We used this approach to develop a variety of context-sensitive algorithms including side effect analysis, type analysis, and escape analysis.

Binary decision diagrams are one of the coolest data structures of the last 20 years, and are also one of the basic enabling data structures underlying modern SAT solvers. Using them to implement Datalog is a really clever idea.

EDIT: I relied on memory instead of Google, and got it wrong about BDDs and SAT solving. Modern DPLL-based SAT solvers generally do not use BDDs, because when your solutions are far apart in the solution space the representing BDD would get quite large. BDDs are widely used in verification, though, and are also still one my favorite data structures. :)

Although the majority of work in the AOSD community focuses on general-purpose aspect languages (e.g. AspectJ), seminal work on AOSD proposed a number of domain-specific aspect languages, such as COOL for concurrency management and RIDL for serialization, RG, AML, and others. A growing trend of research in the AOSD community is returning to this seminal work

Since it seems it is DSL week around here, and since Domain-Specific Aspect Languages were not discussed here before as far as I can remember, I think now may be an appropriate time to discuss this notion.

To begin the tour, head out to the web page of the first DSAL workshop: DSAL'06 which "approached domain-specific aspect languages from a language implementation point of view, where advances in the field of domain-specific language engineering were investigated to answer the implementation challenges of aspect languages," and then move over to DSAL'07 which dealt with the design and implementation of new domain-specific aspect languages in more detail.

Interesting report by Noel and his colleagues, that for some reason was announced on the PLT Scheme blog and not here...

A nice blog post about Erlang. Nothing new here for those following the Erlang story, but a nice summary of several important themes none the less. Some choice quotes:

The thing that bugs me about [Armstrong's] book (and about his talks) is that he make more fuss than he should about the functional language aspect of Erlang and not enough about the OO aspect. In fact, he denies that it is OO.

Processes in Erlang are objects. At the beginning of my course on OO design, I explain three views of OO programming. The Scandinavian view is that an OO system is one whose creators realize that programming is modeling. The mystical view is that an OO system is one that is built out of objects that communicate by sending messages to each other, and computation is the messages flying from object to object. The software engineering view is that an OO system is one that supports data abstraction, polymorphism by late-binding of function calls, and inheritance. Erlang is a perfect example of the actor model, which is an example of the mystical view.

Moreover, given several kinds of processes that have a common protocol and that share some things in common, it is easy to factor out the commonality into a function that they can both call. This is similar to class inheritance. So, you could even say that Erlang supports inheritance...