From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by yquem.inria.fr (Postfix) with ESMTP id 04CD0BDC5 for ; Sat, 20 Aug 2005 03:57:35 +0200 (CEST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j7K1vX8W021612 for ; Sat, 20 Aug 2005 03:57:34 +0200 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 DAA28835 for ; Sat, 20 Aug 2005 03:57:33 +0200 (MET DST) Received: from smtp3.adl2.internode.on.net (smtp3.adl2.internode.on.net [203.16.214.203]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j7K1vVU4010145 for ; Sat, 20 Aug 2005 03:57:32 +0200 Received: from rosella (ppp12-25.lns2.syd7.internode.on.net [59.167.12.25]) by smtp3.adl2.internode.on.net (8.12.9/8.12.9) with ESMTP id j7K1vNrV040960; Sat, 20 Aug 2005 11:27:25 +0930 (CST) Subject: Re: [Caml-list] recursive polymorphic variants? From: skaller To: Jacques Garrigue Cc: nr@eecs.harvard.edu, caml-list@inria.fr In-Reply-To: <20050819.065118.03980029.garrigue@math.nagoya-u.ac.jp> References: <20050818212744.94BD41EB0C3@labrador.eecs.harvard.edu> <20050819.065118.03980029.garrigue@math.nagoya-u.ac.jp> Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="=-lUUKMp+4sOlusBFT8SFM" Date: Sat, 20 Aug 2005 21:57:19 +1000 Message-Id: <1124539039.6850.20.camel@localhost.localdomain> Mime-Version: 1.0 X-Mailer: Evolution 2.2.1.1 X-Miltered: at nez-perce with ID 43068E0D.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 43068E0B.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 recursive:01 variants:01 variants:01 recursive:01 reuse:01 recursion:01 typecode:01 btyp:01 btyp:01 pointer:01 typecode:01 recursions:01 inference:01 debugging:01 X-Attachments: type="application/pgp-signature" name="signature.asc" X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: * X-Spam-Status: No, score=1.2 required=5.0 tests=DATE_IN_FUTURE_06_12 autolearn=disabled version=3.0.3 --=-lUUKMp+4sOlusBFT8SFM Content-Type: text/plain Content-Transfer-Encoding: quoted-printable On Fri, 2005-08-19 at 06:51 +0900, Jacques Garrigue wrote: > From: nr@eecs.harvard.edu (Norman Ramsey) >=20 > > I'm trying to write a small, extensible interpreter, and I'd like to > > use polymorphic variants as the extension mechanism.=20 > > Is there some way to define a recursive, *extensible* type using > > polymorphic variants? =20 >=20 > "Code reuse through polymorphic variants" at > http://www.math.nagoya-u.ac.jp/~garrigue/papers/ This paper is good but very skimpy .. :) Open recursion is used, and types are inferred from functions. It is possible to use the same techniques to define the required types explicitly too, basic Felix bound term type definition uses this: (** value typing *) type 't b0typecode_t' =3D=20 [ | `BTYP_inst of bid_t * 't list=20 | `BTYP_tuple of 't list =20 | `BTYP_unitsum of int | `BTYP_sum of 't list=20 | `BTYP_function of 't * 't | `BTYP_pointer of 't=20 | `BTYP_lvalue of 't=20 | `BTYP_array of 't * 't=20 | `BTYP_void =20 | `BTYP_fix of int =20 | `BTYP_var of int =20 ] (** meta typing *) type 't b1typecode_t' =3D [ | `BTYP_apply of 't * 't=20 | `BTYP_typefun of (int * 't) list * 't * 't | `BTYP_type | `BTYP_type_tuple of 't list | `BTYP_type_match of 't * ('t * 't) list ] (** general typing *) type 't btypecode_t' =3D [ | 't b0typecode_t' | 't b1typecode_t' ] type b0typecode_t =3D 't b0typecode_t' as 't type btypecode_t =3D 't btypecode_t' as 't Unfortunately, whilst I could use this technique for many terms other than typecodes, I haven't because it is somewhat clumbsy to write out terms with all the required added parameters and then close the recursions. For just one extension over one variable we have a 1 parameter overhead in the type definitions, and 9 lines for the closure. Inference removes the need to write out the types, but it makes debugging virtually impossible. In addition, type inference isn't strong enough to deduce the "correct" typing for all expressions, coercions are sometimes required, and in practice to write them abbreviations are necessary. Having warned you .. I would never go back to ordinary variants after using polymorphic ones: Felix uses them almost exclusively, and even though I don't use the features heavily, knowing that it is possible to refine the typing later seems a major software engineering plus. --=20 John Skaller --=-lUUKMp+4sOlusBFT8SFM Content-Type: application/pgp-signature; name=signature.asc Content-Description: This is a digitally signed message part -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.5 (GNU/Linux) iD8DBQBDBxqfsRp8/9aGVGsRAnAwAJ96v/hJsjeYglJ7Pe1IQTW/XHhWbgCdG8TK vayKtZiwxmI3/tMDqf8/6F4= =8Pac -----END PGP SIGNATURE----- --=-lUUKMp+4sOlusBFT8SFM--