RE: Visitor pattern w/ separate iterator (like fold) need ideas

"Ralf Lammel" <Ralf.Lammel@microsoft.com>
10 Apr 2006 00:17:50 -0400

          From comp.compilers

Related articles
Visitor pattern w/ separate iterator (like fold) need ideas cfc@shell01.TheWorld.com (Chris F Clark) (2006-04-08)
Re: Visitor pattern w/ separate iterator (like fold) need ideas vesa.karvonen@cs.helsinki.fi (Vesa Karvonen) (2006-04-09)
RE: Visitor pattern w/ separate iterator (like fold) need ideas Ralf.Lammel@microsoft.com (Ralf Lammel) (2006-04-10)
Re: Visitor pattern w/ separate iterator (like fold) need ideas cfc@shell01.TheWorld.com (Chris F Clark) (2006-04-12)
| List of all articles for this month |

From: "Ralf Lammel" <Ralf.Lammel@microsoft.com>
Newsgroups: comp.compilers
Date: 10 Apr 2006 00:17:50 -0400
Organization: Compilers Central
References: 06-04-051 06-04-066
Keywords: functional
Posted-Date: 10 Apr 2006 00:17:49 EDT

Chris wrote,


> However, and this is the spark for my question, I come to an
> interesting situation with statements that contain other statements
> nested within them, e.g. if-then-elses and loops. The trivial
> solution is to start a new iterator on the tree, that executes those
> statements within the context of executing that statement they are
> nested within.
> [...]
> This is fairly simple, straight-forward and does what I want.
> However, it has the disadvantage of creating new iterators to walk the
> then or the else clauses. It would be much better, if I could
> somehow, change the xqt-iterator for the if-then-else-stmt to execute
> the desired then or else clause.


At least for my eyes, your pseudo code and your explanations do not
provide enough details to resolve some questions I would have;
apologies, if this sounds like a complain -- it's not; I would just love
to fully understand what you are trying to accomplish.


Why do you bother about these new iterators? I guess, for efficiency,
right? So then, why do you need to new up iterators in your current
design? This would only be necessary, if they were carrying some state,
but why would they? As you are referring to functional maps and folds,
they shouldn't. Conceptually, iterators (maps/folds) are just functions
that take a data structure as argument, and a "visitor" (the fold
algebra) to be applied, again an argument -- so no state! The singleton
design pattern should be good enough to reuse iterators and visitors,
no? Depending on your OO language of choice, you may actually avoid
instances *entirely*, and use static functions all-over, just as one
would expect in Haskell.


I have seen designs were visitors carry state because this state is used
to aggregate the result of a fold, but this is clearly an unnecessarily
imperative design; a functional visitor is just fine. BTW, I am guessing
here that you are interested to operate in an object-oriented language.
If this is a wrong guess, the following recommendation makes less sense.


I recommend looking into Joost Visser's work on visitor combinators [1],
more generally into strategic programming, where traversal strategies
are programmer-definable abstractions that are derived from single
primitives such as traversal of immediate children; there is a lot of
related work on Eelco Visser's, Joost Visser's and my web sites, but I
refer to [2] most specifically because it describes the notion of
strategic programming with some useful reference to OO programming, and
it also refers to adaptive programming, which is something you as well
could want to review for the purposes of your design.


[1] http://doi.acm.org/10.1145/504282.504302


[2] http://doi.acm.org/10.1145/643603.643621


Ralf Laemmel
Microsoft Corp.
http://homepages.cwi.nl/~ralf/


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.