From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.4 required=5.0 tests=SPF_NEUTRAL autolearn=disabled version=3.1.3 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 222E4BC69 for ; Wed, 14 Nov 2007 13:45:34 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAANZ8OkdA6bjlmGdsb2JhbACPAAEBBwQGJw X-IronPort-AV: E=Sophos;i="4.21,416,1188770400"; d="scan'208";a="19278231" Received: from concorde.inria.fr ([192.93.2.39]) by mail4-smtp-sop.national.inria.fr with ESMTP; 14 Nov 2007 13:45:34 +0100 Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id lAECjXig025117 (version=TLSv1/SSLv3 cipher=RC4-SHA bits=128 verify=OK) for ; Wed, 14 Nov 2007 13:45:34 +0100 X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAANZ8OkdA6bjlmGdsb2JhbACPAAEBBwQGJw X-IronPort-AV: E=Sophos;i="4.21,416,1188770400"; d="scan'208";a="19278229" Received: from wr-out-0506.google.com ([64.233.184.229]) by mail4-smtp-sop.national.inria.fr with ESMTP; 14 Nov 2007 13:45:32 +0100 Received: by wr-out-0506.google.com with SMTP id 37so159137wra for ; Wed, 14 Nov 2007 04:45:31 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=beta; h=domainkey-signature:received:received:from:reply-to:to:subject:date:user-agent:references:in-reply-to:content-type:content-transfer-encoding:content-disposition:message-id; bh=ydNxSh2Z6g/PxQRSe5yjTeSuLtl+6NXUttBG4GuAFMc=; b=fDW/Fe96OX9eTTFdneaanmiPqO2WCs4QkpfoN409wnAf74/NENIxKGvRoS16A97LslPLLXkk7dL+z5P5jbo6og0ALHuL7Pg1VXlJMy+Y8FMy9cnGNX3DgE4V4nUl++QKQOsJ7ZsCyq0sn5ANdQX/fZotHHnaI2QEzeiYGUAxAP8= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=beta; h=received:from:reply-to:to:subject:date:user-agent:references:in-reply-to:content-type:content-transfer-encoding:content-disposition:message-id; b=Xh5YcyEQmp6bzv0cziqTnYlMNV4OynaEZRjMO6W5uMv4TEIP6ZFSoUlQYAj0IB2NJSf+jvOx9trL//uBGOBy8IyCqcpUkhNAQTB/tpC/w4EAQBe6SyYPUnsdTX/iE4klk/9TK6oC162rvAdd3rwsiukYlYCmkH58FXtggSDBsLA= Received: by 10.90.95.11 with SMTP id s11mr2991847agb.1195044331480; Wed, 14 Nov 2007 04:45:31 -0800 (PST) Received: from lawn-128-61-27-196.lawn.gatech.edu ( [128.61.27.196]) by mx.google.com with ESMTPS id n26sm816051ele.2007.11.14.04.45.30 (version=TLSv1/SSLv3 cipher=OTHER); Wed, 14 Nov 2007 04:45:30 -0800 (PST) From: Peng Zang Reply-To: peng.zang@gmail.com To: caml-list@inria.fr Subject: Re: [Caml-list] polymorphic lists, existential types and asorted other hattery Date: Wed, 14 Nov 2007 07:45:25 -0500 User-Agent: KMail/1.9.7 References: <200711131227.18910.peng.zang@gmail.com> <20071114.134840.39171294.garrigue@math.nagoya-u.ac.jp> In-Reply-To: <20071114.134840.39171294.garrigue@math.nagoya-u.ac.jp> Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit Content-Disposition: inline Message-Id: <200711140745.29151.peng.zang@gmail.com> X-Miltered: at concorde with ID 473AEDED.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; existential:01 hash:01 existential:01 yaron:01 haskell:01 rework:01 camlp:01 haskell:01 ocaml:01 ocaml:01 haskell's:01 encodings:01 subtyping:01 avoided:01 subtyping:01 -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Wow, alright. First I want to thank everyone for replying to my post. You guys have been extremely helpful and I have definitely gained a better understanding of this issue. Jacques, your explanation of how existential types are really just a way of encoding objects helps me understand both a lot better. I never understood the connection before. I also appreciate your tip on speeding up method calls. Arnaud, your trick for encoding existencial types is fascinating. I haven't followed through your reference thread through yet, but I'm sure I'll be doing that later today. Dmitri and Benjamin, the OO examples and benchmarking makes it clear to me that objects can be quite fast. I don't know where I read about objects being slow but that's clearly not the case here. Overall I think the OO solution is what I am looking for. I had been under the impression that OO was slower and that it was some thing unpleasant from various readings (eg. Yaron Minsky's summary http://www.haskell.org/sitewiki/images/0/03/TMR-Issue7.pdf [pg. 30]) Perhaps however, I have been getting the wrong impression. I am going to rework my code base using objects and see how it turns out. On this note, does anyone know of a way to automatically generate the object of a module? Ie. I have three modules A,B and C which all implement the same module type X, but I really want three objects a,b and c for those modules which implement the same class type x, so that I can stick all objects in the same list and map over them etc.. I can do this by hand (not difficult, just a little tedious), but I wonder if there's not some camlp4 trick that can take the values in a module and just create a passthrough object which exposes those values. Thanks again for all your replies. They have helped enormously, Peng On Tuesday 13 November 2007 11:48:40 pm Jacques Garrigue wrote: > From: Peng Zang > > > I've come across a way to do this in haskell using what they call > > "existential types". > > > > http://www.haskell.org/haskellwiki/Existential_type > > > > I don't really understand existential types however and don't know if > > OCaml has them nor how to use them. > > Notwithstanding your reluctance to use them, objects in ocaml are > really what amounts to Haskell's existential types, particularly > those for which a type class is specified. Put the other way round, > most examples of constrained existential types (i.e. where there is a > type class specifiying the existential) are just encodings for > objects. The encoding of objects through existentials has been known > for a long time. OCaml doesn't need this encoding because it has > primitive objects. > > From an implementation point of view, constrained existentials need to > be accompanied by their dictionaries, which is exactly the same thing > as the method table in an object, so even the implementation is very > similar. > > Method calls on arbitrary objects can be slow. This is because, due to > subtyping, in some situations there is no way to know where the method > will be in the table, and a binary search has to be done. However, > this overhead can be avoided if all objects used in a specific method > call have the same methods. That is, they should have the same > interface, without using subtyping. That way, the method will be at > the same position in all objects, and this position is cached (for > native code). > (Note that this also means that any benchmark on the performance of > objects shall consider the impact of cacheing, which can be hard to > evaluate in micro-benchmarks.) > > Dmitri's example had this property, so it should display good > performance (as good as explicit existential encodings.) > > Jacques Garrigue -----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.7 (GNU/Linux) iD8DBQFHOu3pfIRcEFL/JewRAnwXAKCqWM5BJ6J44jXMHzmonP5iRhqUtgCgoq6/ rg54JaQONgB/DCVf4RP4aPc= =NP4X -----END PGP SIGNATURE-----