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 KAA17535; Mon, 23 Jun 2003 10:07:47 +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 KAA17555 for ; Mon, 23 Jun 2003 10:07:45 +0200 (MET DST) X-SPAM-Warning: Sending machine is listed in blackholes.five-ten-sg.com Received: from host07.ipowerweb.com (host07.ipowerweb.com [12.129.206.107]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h5N87iH16561 for ; Mon, 23 Jun 2003 10:07:44 +0200 (MET DST) Received: from bikini.inria.fr ([128.93.1.43] helo=rouaix.org) by host07.ipowerweb.com with asmtp (Exim 3.36 #1) id 19UMMV-0000AQ-00; Mon, 23 Jun 2003 01:07:39 -0700 Date: Mon, 23 Jun 2003 10:07:39 +0200 Subject: Re: [Caml-list] First order compile time functorial polymorphism in Ocaml Content-Type: text/plain; charset=US-ASCII; format=flowed Mime-Version: 1.0 (Apple Message framework v552) Cc: caml-list@inria.fr To: John Skaller From: Francois Rouaix In-Reply-To: <3EF5F48E.6010209@ozemail.com.au> Message-Id: Content-Transfer-Encoding: 7bit X-Mailer: Apple Mail (2.552) X-AntiAbuse: This header was added to track abuse, please include it with any abuse report X-AntiAbuse: Primary Hostname - host07.ipowerweb.com X-AntiAbuse: Original Domain - inria.fr X-AntiAbuse: Originator/Caller UID/GID - [0 0] / [0 0] X-AntiAbuse: Sender Address Domain - rouaix.org X-Spam: no; 0.00; caml-list:01 functorial:01 camlp:01 ioxml:01 compile-time:01 marshalling:01 adapting:01 reuse:01 mylist:01 functor:01 subterm:01 opaque:01 pervasives:01 ozemail:01 toxteth:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk John, Sounds like Camlp4 work to me. If you haven't seen IoXML, you might want to look at it. It generates type-specific code at compile-time to support marshalling to and from XML. Copy-pasting and adapting to morphisms should be a simple exercise. --f On Sunday, Jun 22, 2003, at 20:25 Europe/Paris, John Skaller wrote: > In ML style functional programming languages like Ocaml, > we have what is termed data polymorphism. This provides > a kind of code reuse we're all familiar with. > > However, there is another kind of polymophism > which Ocaml does not provide. Two things to consider here: > > 1. Every data structure has a map function. > 2. User defined algebraic type require a hand written map function > > It sure is inconvenient to have to remember the names > of all those map functions, not to mention having to hand > write them. Lets look at a map function: > > type 'a mylist = Empty | Cons of 'a * 'a list > > let rec map_mylist f a = match a with > | Empty -> Empty > | Cons (h,t) -> Cons (f h, map_mylist f t) > > It is clear from this example, that every inductive type > can have a map function generated by a purely mechanical > transformation on the type terms: that is, there > is no reason to ever write map functions again. > > The result extends easily to multiple type variables, > a map function then requires multiple function arguments. > > The result can *also* be extended to folds, iterators, > and other polymorphic algorithms (provided they're natural). > > Notation: I suggest > > polymap[t] > > denoted the map for an algebraic type, it has arity n+1 > where n is the arity of the type functor. > > Rules for generation of the map function > [brain dead non-tail recursive version] > > 1. We write let rec (mapname) (argumentlist) = function > > 2. If the type is a tuple, the result is a tuple of > mapped subterms (ditto for records). > > 3. If the type is a sum (either kind), the result is > a function with a list of match cases, the result > is the same constructor with mapped arguments. > > 4. If the type is a constant, the result is that constant > > 5. If the type is a type variable, the corresponding > mapping function applied to the subterm: 'f is replaced > by f x (where x names the subterm). > > 6. If the type is a functor application (type constructor), > the result is a polymap of the functor applied to the mapped > arguments and the corresponding match term. > > 7. Handling abstract types. In order to actually summon > the above code generations, we posit a new binding construction: > > let = polymap in > > if the definition of contains any opaque types, > including any abstract type of a module, primitive > not known in Pervasives, or, a class, then the client > must supply the mapping function as follows: > > let = polymap with polymap list = List.map in > etc. > > The same mechanism can be provided for folds, iterators, > etc. Because this is a first order system, we have to hand > write the functorial transformation each time. > > -- > John Max Skaller, mailto:skaller@ozemail.com.au > snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia. > voice:61-2-9660-0850 > > > ------------------- > 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 > > ------------------- 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