@TECHREPORT{func-vis2:bryan-theo,
AUTHOR = "Bryan Chadwick and Therapon Skotiniotis and Karl Lieberherr",
TITLE = "{Functional Visitors Revisited}",
YEAR = "2006",
INSTITUTION = "Northeastern University, Boston",
MONTH = "May",
NUMBER = "NU-CCIS-06-03
}
Notes by Karl:
The paper has been significantly improved in 2007 and was submitted to GPCE 2007. See file gpce07*.pdf.
The technical report fails to reference the "Scrap Your Boilerplate" literature started by a TLDI 2003 paper by Ralf Laemmel and Simon Peyton Jones. The abstract says: Our technique allows most of this boilerplate to be written once and for all, or even generated mechanically, leaving the programmer free to concentrate on the important part of the algorithm. These generic programs are much more adaptive when faced with data structure evolution because they contain many fewer lines of typespecific code. -- end quote This motivation is what motivated us to develop Demeter. Several papers have picked up on this theme: A recent one by Ralf Hinze and A. Loeh: Scrap your boilerplate' revolutions. We need to compare those papers with our work. SYB Papers to review. Ralf Laemmel writes in his Scrap your XML-plate paper. in section 5: "... the AP setup is specifically meant to enable powerful meta-data-aware optimization that lets traversals cease as early as possible. Generic functional programming (including SYB) should feel some urgency about catching up with AP in this area". AP is not only good for optimization but also for flexible expression of where to go in a value. Acording to Therapon Skotiniotis, FP should not only catch up with AP, but AP should also catch up with FP. This paper on functional visitors achieves some of the catch up and our ECOOP 2006 paper on Demeter interfaces also plays catch up in another direction. Our ECOOP paper is addressing a fundamental problem with SYB: when you scratch your boiler plate your code might work with a new data type of the same kind but sometimes it does not. Our paper formalizes static conditions that need to hold for the SYB program to work.
What is a generic function? Ralf Hinze writes in Scrap Your Boilerplate Reloaded: "A generic function is a function that is defined once, but works for many data types. It can adapt itself to the structure of data types." This is exactly the definition of a propagation pattern that has been used in AP since 1991.
Here is a comparison with the paper by Ralf Hinze et al. Generic Programming, Now! (2006). I also bring in our paper on data-type generic programming at ECOOP 2006. http://www.ccs.neu.edu/research/demeter/biblio/demeter-interf.html Here are rough correspondences to the "Generic Programming, Now" paper: kinds: we call them interface class graphs (ICG). An ICG defines an infinite family of types. types: classes because we are in an object-oriented context. generic functions: Demeter interface consisting of an ICG and a set of constraints on the allowed types satisfying the ICG plus traversals and computation to be done during the traversals. Hinze et al. say: A generic function works for all types, including types that the programmer is yet to define. We say: A generic function works for all types satisfying a Demeter interface. This includes types that the programmer is yet to define. However, we also define functions that work on all types: for those we use the class graph of class graphs and use AP at the meta level. This gives us pretty printers, copiers, equality checkers etc. It seems that there are many connections between the two lines of work that we need to explore further. We have practiced this style of programming for 15 years in our Demeter project. Demeter addresses similar conceptual problems that the datatype-generic programming community addresses. (The term datatype-generic programming was coined by Jeremy Gibbons (to distinguish from parametric polymorphism).
Additional note: The paper is written in a Demeter independent style but of course the ideas can be applied beautifully in the Demeter tools, especially DJ. Here is a more DJ-specific description of the paper: Visitors are popular ingredients of many programs. Interesting programming subtasks can be expressed by tg.traverse(o,v1, ... ,vn) where tg is an object that defines a traversal of object o and v1, ... ,vn are visitor objects that perform the processing. Each visitor returns an application object (like an integer) and the call to traverse returns what v1 returns. We show in this paper that a better approach is to have each visitor be functional and always to return a visitor and to give only two arguments to traverse but compensate by a visitor combinator library. The expression becomes: tg.traverse(o,E(v1, ... ,vn)) where E is a visitor combinator expression that returns a visitor. This paper makes the following contributions. We show that functional visitors simplify programming tasks by promoting more modular programs and that a small combinator library is sufficient for many tasks. We provide an implementation of functional visitors for Java 1.5 that relies on reflection and generics.