[Caml-list] Pure visitor patterns
Jason Hickey
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
_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
Jacques Garrigue
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
Jason Hickey
>> From: Jason Hickey <j...@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
_______________________________________________
brogoff
> From: Jason Hickey <j...@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