From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id E2595BCAF for ; Wed, 29 Jun 2005 10:32:33 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j5T8WX4b010223 for ; Wed, 29 Jun 2005 10:32:33 +0200 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id KAA28610 for ; Wed, 29 Jun 2005 10:32:33 +0200 (MET DST) Received: from hedwig1.umh.ac.be (hedwig2.umh.ac.be [193.190.193.73]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j5T8WWal001060 for ; Wed, 29 Jun 2005 10:32:32 +0200 Received: from poincare ([10.102.28.57]) by hedwig1.umh.ac.be (8.13.1/8.13.1) with ESMTP id j5T8WaVh2015336 for ; Wed, 29 Jun 2005 10:32:36 +0200 Received: from [127.0.0.1] (helo=localhost ident=trch) by poincare with esmtp (Exim 4.50) id 1DnQTw-0002Ua-0N; Wed, 29 Jun 2005 02:31:12 +0200 Date: Wed, 29 Jun 2005 02:31:11 +0200 (CEST) Message-Id: <20050629.023111.15476874.debian00@tiscali.be> To: "O'Caml Mailing List" Subject: Type abstraction and (polymorphic) equality From: Christophe TROESTLER Organization: Universite de Mons-Hainaut (http://math.umh.ac.be/an/) X-Spook: enigma Chobetsu beanpole MIT-LL Adriatic supercomputer White House high security cryptographic FSF X-Blessing: Om Ah Hum Vajra Guru Pema Siddhi Hum X-Operating-System: GNU/Linux (http://www.linux.org/) X-Mailer-URL: http://www.mew.org/ X-Mailer: Mew version 4.2.51 on Emacs 21.4 / Mule 5.0 (SAKAKI) Mime-Version: 1.0 Content-Type: Multipart/Mixed; boundary="--Next_Part(Wed_Jun_29_02_31_11_2005_474)--" Content-Transfer-Encoding: 7bit X-Scanned-By: MIMEDefang 2.1 (www dot roaringpenguin dot com slash mimedefang) X-Miltered: at concorde with ID 42C25CA1.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 42C25CA0.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; abstraction:01 christophe:01 troestler:01 compiler:01 val:01 bool:01 compiler:01 abstraction:01 ocaml:01 syntax:01 compilation:01 compilation:01 val:01 printf:01 printf:01 X-Attachments: name="a.mli" name="b.ml" name="a.ml" X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.5 required=5.0 tests=FROM_ENDS_IN_NUMS autolearn=disabled version=3.0.2 X-Spam-Level: ----Next_Part(Wed_Jun_29_02_31_11_2005_474)-- Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit Hi, I'd like here to present a problem that I think is fairly common (and likely probably discussed) to have suggestions about what is the best way to deal with it. Let me start with a little story that happened to me recently. Suppose one has a module A declaring an abstract type t and some functions. You are happy with the interface of A and have a working implementation so you go on and write programs using A. Later on, you realize that you could improve A implementation by attaching additional information to each variable of type t (this does not change the interface of A). Then all of a sudden, your programs start to die with Out_of_memory exceptions... The problem was that the attached information (an additional field in a record) was a cyclic data structure. From there on, all equality tests became deadly! (I would have preferred to have the exception Invalid_argument "equal: abstract value".) What made matters worse is that the compiler could not help me to find the locations of such problems -- which can be hidden e.g. in List.mem. Not a nice job to do... One may argue that its my fault: I should have declared from the start a function val eq : t -> t -> bool While that would have solved some of the problems I have, it would have introduced new ones. In particular, some functions relying on equality couldn't be used anymore (but, again, without the compiler helping to fund them). An example is List.mem. Of course, there is List.exists to achieve the same goal but maybe one uses a library declaring internally type 'a s = X | Y of 'a and using equality on values of type ['a s] (here the default structural equality is arguably what we want). You may not even be aware that the library does so if you did not write it. However, for values of type [t s] on needs a special equality... which in practice precludes the use of this library! Here one sees that the problems with equality stand in the way of abstraction and code reusability. Now the questions are: * Is there a solution in the current state of OCaml? (I'll be glad if there is.) * If the first answer is "no", is there a medium term perspective to bring a solution to this problem? I can see two: - one allows to redefine equality for new types, say with a syntax like type t = ... with compare x y = ... as this is already done for blocks with custom tags. (BTW, why aren't Big_int such blocks with an appropriate compare?) - One introduces the same capability of providing a special equality (comparison) for certain types but, during compilation, "expand" functions till the type for "=" is given by known functions (something like a "generic" equality). I guess however that that may cause problems with separate compilation... I'll be glad to hear similar experiences and comments about the above ideas. Regards, ChriS ----Next_Part(Wed_Jun_29_02_31_11_2005_474)-- Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="a.mli" type t val x : t val y : t ----Next_Part(Wed_Jun_29_02_31_11_2005_474)-- Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="b.ml" let () = Printf.printf "%b\n" (A.x = A.y) ----Next_Part(Wed_Jun_29_02_31_11_2005_474)-- Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="a.ml" type t = { a : int; b : t * t; (* extra info for optimization *) } let rec x = { a=1; b = (x, y) } and y = { a=1; b = (y,x) } ----Next_Part(Wed_Jun_29_02_31_11_2005_474)----