From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id SAA08738; Sun, 4 May 2003 18:48:42 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA07490 for ; Sun, 4 May 2003 18:48:41 +0200 (MET DST) Received: from grace.speakeasy.org (grace.speakeasy.org [216.254.0.2]) by concorde.inria.fr (8.11.1/8.11.1) with SMTP id h44GmeH24819 for ; Sun, 4 May 2003 18:48:40 +0200 (MET DST) Received: (qmail 29867 invoked by uid 36130); 4 May 2003 16:48:38 -0000 Received: from localhost (sendmail-bs@127.0.0.1) by localhost with SMTP; 4 May 2003 16:48:38 -0000 Date: Sun, 4 May 2003 09:48:38 -0700 (PDT) From: brogoff@speakeasy.net To: John Max Skaller cc: Mattias Waldau , "alc@PublicPropertySoftware.com" , "'caml Mailing List''" Subject: Re: [Caml-list] Two types of efficiency (Was Efficiency of 'a list) In-Reply-To: <3EB4C2BE.8020407@ozemail.com.au> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Spam: no; 0.00; brogoff:01 caml-list:01 mattias:01 waldau:01 stringset:01 struct:01 beginners:01 recursion:01 functor:01 faq:01 workarounds:01 filliatre:01 textual:01 functors:01 assertion:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Sun, 4 May 2003, John Max Skaller wrote: > Mattias Waldau wrote: > > Languages like PHP have more advanced built-in datastructures with > > language syntax to support them. In Ocaml, we can create the same > > program, however, there is no syntax support, and we have to add > > declarations like > > > > module StringSet = Set.Make(struct > > type t = string > > let compare = compare > > end) ;; > > > > It would be nice if the typechecker could deduce the type of the set and > > add the above declaration automatically to the program. That would make > > it easier for beginners to use the advanced datastructures of Ocaml. As someone else points out, you have the source, you can make polymorphic versions of sets/maps/... by coding polymorphic versions of the source and instantiating with modules based on polymorphic comparisons. > The problem is worse than that. There are places you need such > an animal but CANNOT have it. This occurs when there is type > recursion involved and the lack of orthogonality in Ocaml syntax > prevents you actually declaring the functor instance > at the point you need it. It isn't a syntax problem. I agree that the lack of recursion in the module system is a big problem that needs to be fixed (pun intended ;-) but I think you (and, more importantly, the FAQ maintainer) should mention that there ARE workarounds to these problems. There was a recent discussion on this topic here (and in comp.lang.ml, a 2 year long thread!) where you can see them. Briefly, the polymorphic sets I just mentioned can be used to build simple recursive structures using the parameterization trick at the level of types (i.e., a type variable is used to "defer" the instantiation and allow you to tie the knot. To build more complex ones, you need to recode Set (or whatever functor) to be a functor on an "open" ordered type; the comparison function must be parameterized so that you can close the recursion later. So, this is the parameterization trick allowed the level of types and functions simultaneously. Jean Claude Filliatre showed that one on his message on this topic. I haven't tried it with classes, so YMMV. The only minor annoyance with that trick is that it requires some textual duplication on account of the scope rules for "with type" constraints. This is annoying, and I think, syntactic. > Result: dont use functors, they're not properly > supported. Nonsense. There are places where there can be improvements, but this is as whacky as the "don't use lists" assertion. Why are you using classes? Are they properly supported? > I found this really annoying. It applies in > other parts of the language too, for example > polymorphic variants. Here again, the very > feature functional languages are supposed to > understand best -- recursion -- is actually > handled better in C++. Get outta here! > I need variants whose arguments include the variant > > type, and I can't have them together with subtyping. > Yet for someone representing > a programming language recursion is natural. > > type x = [`A | `B of y] > and y = [x | `C of x] > > There is no problem doing this with textual substitution: > > type x = [`A | `B of y] > and y = [`A | `B of y | `C of x] Yup, that's annoying. I was nailed by the same problem recently, and I used polymorphism to avoid having to write the tags more than once. Something like this type 'a x' = [`A | `B of 'a] type x = y x' and y = [y x' | `C of x] or something like that, I don't recall. Maybe Jacques will shed some light on this restriction. Someone else addresses your subtyping issue. I have to admit that I have found polymorphic variants puzzling at times, but the additional power is amazing and allows you to get at the extensibility of OO and beyond. Look up "The Expression Problem" on Google and see if you can find a discussion on the defunct Java Genericity mailing list. Or just take a look at Jacques Garrigues little paper on code reuse with variants. I'm using the same approach to model a different domain than lambda calculus evaluators, and while the (algorithmic) complexity of that domain makes the evaluator and types a bit more complex, the basic ideas translate easily. What a cool language! -- Brian ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners