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 concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 92E1BBB9A for ; Tue, 25 Oct 2005 17:51:59 +0200 (CEST) Received: from cgpsrv2.cis.mcmaster.ca (univmail.CIS.mcmaster.ca [130.113.64.46]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j9PFpwD8018147 for ; Tue, 25 Oct 2005 17:51:59 +0200 Received: from [130.113.68.27] (account carette@univmail.cis.mcmaster.ca [130.113.68.27] verified) by cgpsrv2.cis.mcmaster.ca (CommuniGate Pro SMTP 4.1.8) with ESMTP id 107648576; Tue, 25 Oct 2005 11:51:57 -0400 Message-ID: <435E54A9.9060903@mcmaster.ca> Date: Tue, 25 Oct 2005 11:52:09 -0400 From: Jacques Carette User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: skaller Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] how to implement generic operators References: <1130131250.28443.79.camel@rosella> <435D35B7.2080905@mcmaster.ca> <1130204602.18325.54.camel@rosella> In-Reply-To: <1130204602.18325.54.camel@rosella> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 435E549E.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 n-tuples:01 sequences:01 sequences:01 n-tuples:01 polymorphism:01 datatype:01 datatype:01 polymorphism:01 ocaml:01 haskell:01 wrote:01 polymorphic:01 short:01 expression:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.3 skaller wrote: >Do you provide lists directly in the term calculus? >Or are they just constructed from products and sums? > > Short answer: yes, lists are provided in the term calculus. Long answer: Maple has no linked lists (ie lists based on nil and cons). It has "automatically flattened n-tuples" - they are called "expression sequences". When you see (a list) [a,b,c] (a set) {a,b,c} (a function call) f(a,b,c) all 3 contain the expression sequence a,b,c. Two additional points: 1) expression sequences (and their contents) are uniquified [ie stored only once] 2) they are stored in contiguous memory, so that they are more array-like than list-like While you may want your term language to support lists, supporting 'flattened' n-tuples can be much simpler from a polymorphism point of view. The idea here is that a tagged datatype is just a pair tag + expression sequence, and you can defined all your polymorphic operators to "map into" the datatype by mapping onto the expression sequence. Experience shows that this is mightily convenient. And most likely difficult as all #$%#$% to ``type''. On the other hand, I was able to reflect this high degree of polymorphism in parts of my toy interpreter, where I could 'factor' a lot of my code quite nicely. If only that 'tags' of an algebraic datatype were also first-class functions in Ocaml [as they are in Haskell], I would make my code considerably more elegant. Jacques C.