Re: [Caml-list] A G'Caml question" + additional info

Re: [Caml-list] A G'Caml question" + additional info

[Krishnaswami, Neel]

Brian Rogoff [mailto:bpr@best.com] wrote:
> >
> > For instance, I recently wrote yet another set 
> > implementation, because the functorial interface to the Set module 
> > in the standard library wouldn't let me use it in a fully polymorphic
> > fashion. If the Set library had been written using OCaml's object
> > system, then I would not have had to redo my own. 
> 
> That's odd. If the Set library had been implemented using the object
> system, it seems that you would have less (parametric) polymorphism 
> since OCaml doesn't (yet?) have polymorphic methods. 

I don't know enough type theory to argue, except that in practice
I seem to be getting more polymorphic types with objects than with 
functors. I guess I'll go ahead and post the example -- it's possible
that I just don't know enough yet! 

So, let's take the example of a priority queue implemented using a
binary search tree. The usual functorial approach to this looks like:

module type ORD =
  sig
    type t
    val cmp : t -> t -> bool
  end

module Queue(Elt : ORD) =
  struct
    type elt = Elt.t
    type t = Nil | Tree of t * elt * t

    let empty = Nil

    let rec min = function
        | Nil -> raise Not_found
        | Tree(Nil, x, r) ->  x
        | Tree(l, x, r) -> min l 

    let rec add x = function
      | Nil ->
          Tree(Nil, x, Nil)
      | Tree(l, y, r) as t ->
          if Elt.cmp x y then
            Tree(add x l, y, r)
          else if Elt.cmp y x then
            Tree(l, y, add x r)
          else
            Tree(l, x, r)
  end

To specialize this a structure satisfying the ORD signature is 
applied to the functor. The obvious approach with classes looks 
very similar, except that the Elt functor argument becomes a method 
to be overridden: 

type 'a tree = Nil | Tree of 'a tree * 'a * 'a tree

class virtual ['a] q =
  object(self)
    val tree = Nil

    method virtual cmp : 'a -> 'a -> bool

    method min =
      let (<) = self#cmp in
      let rec loop = function
        | Nil -> raise Not_found
        | Tree(Nil, x, r) -> x
        | Tree(l, x, r) -> loop l
      in loop tree

    method add x =
      let (<) = self#cmp in
      let rec loop = function
        | Nil ->
            Tree(Nil, x, Nil)
        | Tree(l, y, r) as t ->
            if x < y then
              Tree(loop l, y, r)
            else if y < x then
              Tree(l, y, loop r)
            else
              Tree(l, x, r)
      in
      {< tree = loop tree >}
  end

To specialize this we just subclass and add a cmp method. So far
so good.

However, suppose I have a type 

type 'a tag = int * 'a

This is a value that has an integer priority plus some arbitrary 
data, and I'd like to make a priority queue that stores tagged 
values. Since the type 'a tag is polymorphic, AFAICT there's no 
way of writing a structure that satisfies the ORD signature.

However, writing a class that can accept this is easy --

class ['a] taggedq =
  object
    inherit ['a] q
    constraint 'a = 'b tag

    method cmp = fun a b -> (fst a) < (fst b)
  end

will Just Work(tm). This is why I called the class "more polymorphic."
If my terminology is wrong, corrections will be gratefully accepted. 


--
Neel Krishnaswami
neelk@cswcasa.com
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] A G'Caml question" + additional info

[Brian Rogoff]

On Wed, 11 Jul 2001, Krishnaswami, Neel wrote:
> Brian Rogoff [mailto:bpr@best.com] wrote:
> > >
> > > For instance, I recently wrote yet another set 
> > > implementation, because the functorial interface to the Set module 
> > > in the standard library wouldn't let me use it in a fully polymorphic
> > > fashion. If the Set library had been written using OCaml's object
> > > system, then I would not have had to redo my own. 
> > 
> > That's odd. If the Set library had been implemented using the object
> > system, it seems that you would have less (parametric) polymorphism 
> > since OCaml doesn't (yet?) have polymorphic methods. 
> 
> I don't know enough type theory to argue, except that in practice
> I seem to be getting more polymorphic types with objects than with 
> functors. I guess I'll go ahead and post the example -- it's possible
> that I just don't know enough yet! 

In the example you post you write the classes polymorphically yet you 
write the module definition monomorphically, so of course the class will 
be more polymorphic. What you want is a polymorphic set (which you can
hack from the source to the library) to be part of the library. 

> So, let's take the example of a priority queue implemented using a
> binary search tree. The usual functorial approach to this looks like:
> 
> module type ORD =
>   sig
>     type t
>     val cmp : t -> t -> bool
>   end

try 

module type PolyOrdSig = sig 
  type 'a t val 
  cmp : 'a t -> 'a -> bool 
end

and modify Queue in a similar fashion. 

This 

> module Queue(Elt : ORD) =
>   struct
>     type elt = Elt.t
>     type t = Nil | Tree of t * elt * t

etc. 

is something you have to explicitly instantiate. It's like an Ada generic  
or C++ class template but it isn't polymorphic. This is 

> module Queue(Elt : ORD) =
>   struct
>     type 'a elt = 'a Elt.t
>     type 'a t = Nil | Tree of 'a t * 'a elt * 'a t

what the top of your polymorphic queue module will look like. 

> To specialize this a structure satisfying the ORD signature is 
> applied to the functor. The obvious approach with classes looks 
> very similar, except that the Elt functor argument becomes a method 
> to be overridden: 

> type 'a tree = Nil | Tree of 'a tree * 'a * 'a tree
> 
> class virtual ['a] q =
>   object(self)
>     val tree = Nil

The analogous design would use a concrete type, and maybe be wrapped in a
functor if you wanted to generalize the element type without making it
polymorphic :-).

[...snip..]
> However, suppose I have a type 
> 
> type 'a tag = int * 'a

If you hadn't declared your class with a 'a but had used some concrete
type instead you'd be stuck in the class case too. 

> will Just Work(tm). This is why I called the class "more polymorphic."
> If my terminology is wrong, corrections will be gratefully accepted. 

Your terminology is fine, but I think if you create polymorphic modules 
you'll find that there is more parametric polymorphism available there.
If you have a sequential collection class parameterized by the element
type how would you write a fold method? 

That's not to say that objects don't have other compensating features...

-- Brian


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] A G'Caml question" + additional info

[Krishnaswami, Neel]

Markus Mottl [mailto:markus@mail4.ai.univie.ac.at] wrote:
> 
> Having tried RedBlackSet as presented in Okasaki's book a while ago,
> I was rather disappointed. It didn't perform faster (rather slower)
> than the Set-module (balanced binary trees) on some quick 
> examples that I had tried. But maybe my simple tests were not
> representative.

He has some timing data comparing splay trees, balanced binary 
trees, Patricia tries, and red-black trees in his paper "Fast 
Mergeable Integer Maps." To summarize, red-black trees were the 
fastest on lookup, and second-fastest on insertion. But they don't
perform very well on the merge operation. (These are all fairly
tuned implementations, though.)

I've been curious about implementing randomized treaps and seeing
how well they do, since they seem simpler than any other balanced 
binary tree implementation.

> > > Note that the non-polymorphic version also has advantages for 
> > > users: e.g. they don't have to pass around comparison functions 
> > > all the time.
> > 
> > ??? I don't understand this. In both the object version I posted 
> > and the functorial version that Brian Rogoff posted, a hacker
> > only needs to mention the comparison function when creating the
> > type, and then never again when making or using trees.
> 
> In the functorial version you naturally have to use a functor 
> application. I meant a polymorphic implementation without functors, 
> since I think you had complained somewhere about having to apply 
> functors. This was probably not obvious from my text.

Applying a functor doesn't bother me. What I find annoying is the
need to functorize my own code if I want to write functions that 
work independently of the element type. It doesn't take very many
of these before my source contains more functor declarations than
actual code. 

A sufficiently powerful include facility for G'Caml can make this
problem go away, since you could define a generic and have each 
functor instantiation add its specialized methods automatically
to the generic. 

> > In fact, my first experiment along these lines was to use a record
> > with a tree and a comparison function in it. But even there, one
> > could use currying to mention the function comparison only once.
> > (I rejected it because it permitted trees with different but type-
> > compatible comparison functions to intermix.)
> 
> But you have to manually curry every Set-function you want to use at
> least once. The functor application creates the closures for the whole
> Set-module at once.

Oh, I see what you mean. That's true but since I'd only implement the
Set once I don't much care. I tend to worry more about cruft associated
with code that uses the library.

--
Neel Krishnaswami
neelk@cswcasa.com
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] A G'Caml question" + additional info

[Markus Mottl]

On Fri, 13 Jul 2001, Krishnaswami, Neel wrote:
> He has some timing data comparing splay trees, balanced binary 
> trees, Patricia tries, and red-black trees in his paper "Fast 
> Mergeable Integer Maps." To summarize, red-black trees were the 
> fastest on lookup, and second-fastest on insertion. But they don't
> perform very well on the merge operation. (These are all fairly
> tuned implementations, though.)

As usual, never trust statistics that you haven't faked yourself...

Such things can be pretty language and compiler dependent. At least
what concerns Patricia trees, I can assert that they really perform
very well in OCaml. This is obviously not true for red-black trees:
on my simple tests with random numbers, insertion took longer than with
balanced binary trees, and lookup also didn't seem competitive. Anyway,
I don't claim that my statistics are faked better than his... ;)

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] A G'Caml question" + additional info

[Krishnaswami, Neel]

Markus Mottl [mailto:markus@mail4.ai.univie.ac.at] wrote:
> On Wed, 11 Jul 2001, Krishnaswami, Neel wrote:
> > For instance, I recently wrote yet another set 
> > implementation, because the functorial interface to the Set module 
> > in the standard library wouldn't let me use it in a fully polymorphic
> > fashion.
> 
> This is a shortcoming of the standard library that there are no
> polymorphic implementations of "Set" and similar. It's very easy to
> extract a polymorphic (module-) version from the existing code. 

Are there any plans to add them? I /really/ need them, and while
their lack has led to me learning an awful lot about red-black
trees, Patricia tries and treaps, I can't help but feel that I've
been busy reinventing the wheel. :)

If desired, I can offer a red-black tree implementation that 
implements the whole Map and Set interfaces. (I wonder how many 
other people have been inspired by that Okasaki paper?) 

> Note that the non-polymorphic version also has advantages for 
> users: e.g. they don't have to pass around comparison functions 
> all the time.

??? I don't understand this. In both the object version I posted 
and the functorial version that Brian Rogoff posted, a hacker
only needs to mention the comparison function when creating the
type, and then never again when making or using trees.

In fact, my first experiment along these lines was to use a record 
with a tree and a comparison function in it. But even there, one 
could use currying to mention the function comparison only once. 
(I rejected it because it permitted trees with different but type-
compatible comparison functions to intermix.)

--
Neel Krishnaswami
neelk@cswcasa.com
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] A G'Caml question" + additional info

[Markus Mottl]

On Thu, 12 Jul 2001, Krishnaswami, Neel wrote:
> If desired, I can offer a red-black tree implementation that implements
> the whole Map and Set interfaces. (I wonder how many other people have
> been inspired by that Okasaki paper?)

Having tried RedBlackSet as presented in Okasaki's book a while ago,
I was rather disappointed. It didn't perform faster (rather slower)
than the Set-module (balanced binary trees) on some quick examples that
I had tried. But maybe my simple tests were not representative.

> > Note that the non-polymorphic version also has advantages for 
> > users: e.g. they don't have to pass around comparison functions 
> > all the time.
> 
> ??? I don't understand this. In both the object version I posted 
> and the functorial version that Brian Rogoff posted, a hacker
> only needs to mention the comparison function when creating the
> type, and then never again when making or using trees.

In the functorial version you naturally have to use a functor application.
I meant a polymorphic implementation without functors, since I think
you had complained somewhere about having to apply functors. This was
probably not obvious from my text.

> In fact, my first experiment along these lines was to use a record
> with a tree and a comparison function in it. But even there, one
> could use currying to mention the function comparison only once.
> (I rejected it because it permitted trees with different but type-
> compatible comparison functions to intermix.)

But you have to manually curry every Set-function you want to use at
least once. The functor application creates the closures for the whole
Set-module at once.

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] A G'Caml question" + additional info

[Krishnaswami, Neel]

Markus Mottl [mailto:markus@mail4.ai.univie.ac.at] writes:
> On Wed, 11 Jul 2001, Bruce Hoult wrote:
> > But the language itself seems to be starting to rival C++ for sheer
> > complexity. When you want to do something you seem to have a choice
> > of using this feature, or *this* one, or *this* newly developed one.
> 
> Having choices is not necessarily bad, being forced to using many
> alternatives is. I think that OCaml has succeeded quite well so far in
> keeping different features apart as one can see in the standard library,
> which can be used with the core language + modules alone. I hope this
> will stay so!

Permit me to disagree. I find nearly all of OCaml's features highly
useful and orthogonal, and I am only working on medium size projects. 

For instance, I recently wrote yet another set implementation, because 
the functorial interface to the Set module in the standard library 
wouldn't let me use it in a fully polymorphic fashion. If the Set 
library had been written using OCaml's object system, then I would 
not have had to redo my own. From this experience I conclude that the 
right thing is to use the features that offer the nicest degree of
modularity and reusability.

I can offer a demonstration if you are interested, but to illustrate 
I'd need to show both approaches in about 75 lines of code, which may 
be too much for a public email. 

--
Neel Krishnaswami
neelk@cswcasa.com
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] A G'Caml question" + additional info

[Brian Rogoff]

On Wed, 11 Jul 2001, Krishnaswami, Neel wrote:
> Markus Mottl [mailto:markus@mail4.ai.univie.ac.at] writes:
> > On Wed, 11 Jul 2001, Bruce Hoult wrote:
> > > But the language itself seems to be starting to rival C++ for sheer
> > > complexity. When you want to do something you seem to have a choice
> > > of using this feature, or *this* one, or *this* newly developed one.
> > 
> > Having choices is not necessarily bad, being forced to using many
> > alternatives is. I think that OCaml has succeeded quite well so far in
> > keeping different features apart as one can see in the standard library,
> > which can be used with the core language + modules alone. I hope this
> > will stay so!
> 
> Permit me to disagree. I find nearly all of OCaml's features highly
> useful and orthogonal, and I am only working on medium size projects. 

Good point, I was going to disagree with Bruce on the C++ comparison. 
OCaml is still orthogonal, with the major exception being the overlap
between the object system and the module system. I guess that's still
research. 

> For instance, I recently wrote yet another set implementation, because 
> the functorial interface to the Set module in the standard library 
> wouldn't let me use it in a fully polymorphic fashion. If the Set 
> library had been written using OCaml's object system, then I would 
> not have had to redo my own. From this experience I conclude that the 
> right thing is to use the features that offer the nicest degree of
> modularity and reusability.

That's odd. If the Set library had been implemented using the object
system, it seems that you would have less (parametric) polymorphism 
since OCaml doesn't (yet?) have polymorphic methods. 

But, I agree that there should be polymorphic versions of some of the 
functorial libraries. There is no way to directly have a recursive 
type definition/functor instantiation, so if you want to implement what 
OOers call the Component pattern you have to use the parameterization 
trick which requires a polymorphic functor. This has bit me a few times
already. This is pretty high on my "I sure hope this gets fixed one day" 
list. 

BTW, if you really like OO style libraries, point your browser this-a-way 

	http://wwwfun.kurims.kyoto-u.ac.jp/soft/olabl/classes/

-- Brian


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] A G'Caml question" + additional info

[Markus Mottl]

On Wed, 11 Jul 2001, Krishnaswami, Neel wrote:
> For instance, I recently wrote yet another set implementation, because
> the functorial interface to the Set module in the standard library
> wouldn't let me use it in a fully polymorphic fashion.

This is a shortcoming of the standard library that there are no
polymorphic implementations of "Set" and similar. It's very easy to
extract a polymorphic (module-) version from the existing code. Note
that the non-polymorphic version also has advantages for users: e.g. they
don't have to pass around comparison functions all the time.

> If the Set library had been written using OCaml's object system,
> then I would not have had to redo my own.

I disagree: a lot of important functionality cannot be easily replicated
with objects alone - at least not in a reasonable way. Just imagine
using the "map" function on an object version of "Map":

The type system won't allow you to implement this function in its full
generality within the class. If you implement it outside with a normal
function, you either have to use very inefficient add-operations or
have to reveal the datastructure (breaks interfaces) or you have to do a
tricky module/class combination (function sees internals, module hides
representation using abstract types), which immediately eliminates the
benefits of objects (you'd have to use an abstract type anyway rather
than operate on object types).

> From this experience I conclude that the right thing is to use the
> features that offer the nicest degree of modularity and reusability.

Right. That's why I almost exclusively prefer modules over objects... ;)

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] A G'Caml question" + additional info

[John Max Skaller]

"Krishnaswami, Neel" wrote:

> Permit me to disagree. I find nearly all of OCaml's features highly
> useful and orthogonal, and I am only working on medium size projects.

I don't find that is entirely true.
First, there is quite a bit of sugar, such as fun/function/match,
if then else vs. matching.

Then, there are duplicated facilities: tuples and records,
standard variants and polymorphic ones. Then classes and modules
overlap.
Oh, and labelled arguments or not. To currify a function or use
a tuple .

Some syntax cannot be used as the 
basic grammar would suggest, and the constraints aren't documented.
For example, you can write:

	let x,y,z = (1,2,3) 
	let Some x = Some 1
	let (Some x) as y = Some 1

but not

	let (Some x) when true = Some 1

I'd give examples from the module system, if only I understood
how to use it properly.

In classes, you can write:

	x <- y

for 'assignment', but you have to write

	x := y

for a reference in ordinary code.

Many library components have both a functorial and
polymorphic interface. There are two versions
of some libraries (Unix, ThreadUnix). Some of the libraries
seem deficient (Str).

Then, there is a duplication of tools (native code
and bytecode compilers), label or standard mode.

The interaction of all these features with the type
system, particularly type inference, makes for some
really daunting error messages.

I'm NOT complaining, just disagreeing.
In my current project, I've been sticking to the basic
feature set. But I'm stronly tempted to switch to polymorphic
variants, because they'd provide much better typing for
my application. But I'm scared that I won't be able to 
understand the error messages, and quite concerned
that there's no way to catch spelling mistakes.
[Something which declared the variant names would be useful]
Switching over, to an _isomorphic_ program -- a mechanical
task -- will requires an almost complete rewrite, by hand.

There's no question that I have a difficult choice
between two non-orthogonal features. 
I'm glad to have the choice -- its much better than being stuck
in C++ without any representation of sums :-)

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au 
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
New generation programming language Felix  http://felix.sourceforge.net
Literate Programming tool Interscript     
http://Interscript.sourceforge.net
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] A G'Caml question" + additional info

[Alexander V. Voinov]

John Max Skaller wrote:
> 
> "Krishnaswami, Neel" wrote:
> 
> > Permit me to disagree. I find nearly all of OCaml's features highly
> > useful and orthogonal, and I am only working on medium size projects.
> 
> I don't find that is entirely true.
> First, there is quite a bit of sugar, such as fun/function/match,
> if then else vs. matching.
...
> I'm NOT complaining, just disagreeing.
> In my current project, I've been sticking to the basic
> feature set. But I'm stronly tempted to switch to polymorphic
> variants, because they'd provide much better typing for
> my application. ....

And in general, redundancy is certainly not an ontological evil when it
is properly structured. Otherwise we wouldn't make any use of poetry.

Alexander
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] A G'Caml question" + additional info

[John Max Skaller]

"Alexander V. Voinov" wrote:

> And in general, redundancy is certainly not an ontological evil when it
> is properly structured. Otherwise we wouldn't make any use of poetry.

	More generally, we know that Ocaml ISN'T properly
structured. If we knew it were, there'd be no point doing research :-)

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au 
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
New generation programming language Felix  http://felix.sourceforge.net
Literate Programming tool Interscript     
http://Interscript.sourceforge.net
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr