@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
}

Paper.

Implementation.

Notes by Karl:

The paper has been significantly improved in 2007 and was submitted to GPCE 2007. See file gpce07*.pdf.

SCRAP YOUR BOILER PLATE

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.

Datatype-Generic Programming

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.