Pure visitor patterns

Pure visitor patterns

[Jason Hickey]

I've been trying to write pure visitors (visitors that compute without
side-effects).  The main change is that a visitor returns a value.
Here is a (failed) example specification based on having only one kind
of thing "foo".

     class type ['a] visitor =
       object ('self)
         method visit_foo : foo -> 'a
       end

     and foo =
       object ('self)
         method accept : 'a. 'a visitor -> 'a
         method examine : int
       end

This fails because the variable 'a escapes its scope in the method  
accept.
It can be fixed by breaking apart the mutual type definition.

     class type ['a, 'foo] visitor =
       object ('self)
         method visit_foo : 'foo -> 'a
       end

     class type foo =
       object ('self)
         method accept : 'a. ('a, foo) visitor -> 'a
         method examine : int
       end

The second form works, but it is hard to use because of the number
of type parameters needed for the visitor (in general).

Here are my questions:

    - Why does 'a escape its scope in the recursive definition?
    - Is there some other style that would solve this problem?

Thanks!

Jason

P.S. Here is an alternate scheme with non-polymorphic visitors, where
the returned value is just a visitor.  The accept method needs to
preserve the type, so this one also has the "escapes its scope"
problem.

     class type visitor =
       object ('self)
         method visit_foo : foo -> 'self
       end

     and foo =
       object ('self)
         method accept : 'a. (#visitor as 'a) -> 'a
       end
     ...

--
Jason Hickey                  http://www.cs.caltech.edu/~jyh
Caltech Computer Science      Tel: 626-395-6568 FAX: 626-792-4257

Re: [Caml-list] Pure visitor patterns

[Jacques Garrigue]

From: Jason Hickey <jyh@cs.caltech.edu>

> I've been trying to write pure visitors (visitors that compute without
> side-effects).  The main change is that a visitor returns a value.
> Here is a (failed) example specification based on having only one kind
> of thing "foo".
> 
>      class type ['a] visitor =
>        object ('self)
>          method visit_foo : foo -> 'a
>        end
> 
>      and foo =
>        object ('self)
>          method accept : 'a. 'a visitor -> 'a
>          method examine : int
>        end
> 
> This fails because the variable 'a escapes its scope in the method  
> accept.
> It can be fixed by breaking apart the mutual type definition.
> 
>      class type ['a, 'foo] visitor =
>        object ('self)
>          method visit_foo : 'foo -> 'a
>        end
> 
>      class type foo =
>        object ('self)
>          method accept : 'a. ('a, foo) visitor -> 'a
>          method examine : int
>        end
> 
> The second form works, but it is hard to use because of the number
> of type parameters needed for the visitor (in general).
> 
> Here are my questions:
> 
>     - Why does 'a escape its scope in the recursive definition?

Because during recursive definitions parameters of these definitions
are handled as monomorphic. So you cannot generalize the 'a locally.

>     - Is there some other style that would solve this problem?

Not really. Using private rows and recursive allow for some more
expressiveness (in particular you can then define pure visitors on
extensible on an extensible collection of classes), but they are a bit
tricky to use in this context, so I'm not sure this is an improvement
for simple cases.

Another trick to make this pattern more scalable is to use constraints
for parameters.

class type ['a, 'cases] visitor =
  object ('self)
    constraint 'cases = <foo: 'foo; bar: 'bar; ..>
    method visit_foo : 'foo -> 'a
    method visit_bar : 'bar -> 'a
  end
class type foo =
  object ('self)
    method accept : 'a. ('a, cases) visitor -> 'a
    method examine : int
  end
and bar =
  object ('self)
    method accept : 'a. ('a, cases) visitor -> 'a
    method examine : bool
  end
and cases = object method foo : foo method bar : bar end

> P.S. Here is an alternate scheme with non-polymorphic visitors, where
> the returned value is just a visitor.  The accept method needs to
> preserve the type, so this one also has the "escapes its scope"
> problem.
> 
>      class type visitor =
>        object ('self)
>          method visit_foo : foo -> 'self
>        end
> 
>      and foo =
>        object ('self)
>          method accept : 'a. (#visitor as 'a) -> 'a
>        end
>      ...

Same reason: #visitor has an hidden type parameter, so it cannot be
generalized in a mutually recursive definition.

Jacques Garrigue

Re: [Caml-list] Pure visitor patterns

[Jason Hickey]

> On 12/27/06, Jacques Garrigue <garrigue@math.nagoya-u.ac.jp> wrote:
>> From: Jason Hickey <jyh@cs.caltech.edu>
>>
>> > Here are my questions:
>> >
>> >     - Why does 'a escape its scope in the recursive definition?
>>
>> Because during recursive definitions parameters of these definitions
>> are handled as monomorphic. So you cannot generalize the 'a locally.

Ah, that makes perfect sense.  If I understand correctly, the  
quantifiers in a mutual recursive class definition are hoisted, like  
this:

The definition
    class type ['a] c1 = ... and ['b] c2 = ...
is really more like the following (pardon my notation):
    ['a, 'b] (class type c1 = ... and c2 = ...)

The mistake is to think of it like simple recursive type definitions,  
like the following (rather useless) definition.

     type 'a visitor =
        { visit_foo : 'a -> foo -> 'a;
          visit_bar : 'a -> bar -> 'a
        }
     and foo = { accept : 'a. 'a -> 'a visitor -> 'a; examine : int }
     and bar = { accept : 'a. 'a -> 'a visitor -> 'a; examine : bool };;

I'm not complaining--the fact that you can write any of these types  
is very cool.

>> Another trick to make this pattern more scalable is to use  
>> constraints
>> for parameters.

Very good suggestion.  This makes it _much_ easier to deal with the  
multiplicity of types, since the constraints are linear, not  
quadratic, in the number of cases.

Many thanks for your explanation!

Jason

--
Jason Hickey                  http://www.cs.caltech.edu/~jyh
Caltech Computer Science      Tel: 626-395-6568 FAX: 626-792-4257

Re: [Caml-list] Pure visitor patterns

[brogoff]

On Thu, 28 Dec 2006, Jacques Garrigue wrote:
> From: Jason Hickey <jyh@cs.caltech.edu>
> > I've been trying to write pure visitors (visitors that compute without
> > side-effects).

I'm curious, what's the application? I asked a similar question to yours
a while ago and Jacques (I believe?) suggested that I would be better
off using an imperative approach in OCaml so all my visitors would have
foo -> unit types. I was disappointed at the time but I think it was a
very good suggestion. My visitors are rather complicated and I found it
useful to have open_foo/close_foo (before_visit/after_visit) methods
with different types than the visits. I decided that using side effects
is better than getting too complex with types.

> >     - Is there some other style that would solve this problem?
>
> Not really. Using private rows and recursive allow for some more
> expressiveness (in particular you can then define pure visitors on
> extensible on an extensible collection of classes), but they are a bit
> tricky to use in this context, so I'm not sure this is an improvement
> for simple cases.

I guess you mean recursive modules above. My usual issue with rows is
that they force you to write a lot of stuff out by hand when you wish
there was a way to assemble them from pieces, if you get my meaning.
A petty complaint, to be sure, but there you have it.

BTW, I assume that the virtual instance variables in the next OCaml are
for extensible visitors, right?

> Another trick to make this pattern more scalable is to use constraints
> for parameters.

That's a nice trick! I knew every little piece of it from reading the
docs and knowing how to break some recursions, but I never put it all
together. Thanks. It would be great if you could flesh out a few of
these non-obvious tricks and put them in the OCaml manual.

> class type ['a, 'cases] visitor =
>   object ('self)
>     constraint 'cases = <foo: 'foo; bar: 'bar; ..>
>     method visit_foo : 'foo -> 'a
>     method visit_bar : 'bar -> 'a
>   end
> class type foo =
>   object ('self)
>     method accept : 'a. ('a, cases) visitor -> 'a
>     method examine : int
>   end
> and bar =
>   object ('self)
>     method accept : 'a. ('a, cases) visitor -> 'a
>     method examine : bool
>   end
> and cases = object method foo : foo method bar : bar end

-- Brian