From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id XAA14605 for caml-red; Mon, 6 Nov 2000 23:15:13 +0100 (MET) 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 OAA03052 for ; Mon, 6 Nov 2000 14:16:10 +0100 (MET) Received: from ext.lri.fr (ext.lri.fr [129.175.15.4]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id eA6DGA104512 for ; Mon, 6 Nov 2000 14:16:10 +0100 (MET) Received: from pc803.lri.fr (IDENT:root@pc803 [129.175.8.114]) by ext.lri.fr (8.9.3/jtpda-5.3.2) with ESMTP id OAA04428 ; Mon, 6 Nov 2000 14:16:07 +0100 (MET) Received: by pc803.lri.fr (8.9.3/feuille) id OAA27252 ; Mon, 6 Nov 2000 14:16:06 +0100 X-Authentication-Warning: localhost.localdomain: filliatr set sender to filliatr@pc803 using -f From: Jean-Christophe Filliatre MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <14854.44822.43851.623717@pc803> Date: Mon, 6 Nov 2000 14:16:06 +0100 (MET) To: Chris Hecker Cc: caml-list@inria.fr Subject: Re: practical functional programming In-Reply-To: <4.3.2.7.2.20001103055229.00ab6880@shell16.ba.best.com> References: <4.3.2.7.2.20001103055229.00ab6880@shell16.ba.best.com> X-Mailer: VM 6.49 under Emacs 20.4.1 Reply-To: Jean-Christophe.Filliatre@lri.fr (Jean-Christophe Filliatre) Sender: weis@pauillac.inria.fr In his message of Fri November 3, 2000, Chris Hecker writes: > However, after reading Okasaki's papers about functional > datastructures, I'm not sure I get why someone would go to all that > trouble. In other words, I can trivially write an O(1) queue using > imperative languages (or imperative features of a funcional > lanugage, like caml's queue.ml). Okasaki goes to a _lot_ of trouble > to implement an O(1) queue in a pure functional way, using all sorts > of lazy optimizations and scheduling and whatnot. He acheives O(1), > but the constant is going to be rather large compared to shuffling a > pointer/ref around in C/caml. > > So, what does all this trouble buy you? The answer to your question is "persistence". Indeed, there is no need using a purely functional datastructure when there is an easy imperative solution. And I think that most programmers on this mailing list are not extremists of purely functional programming and will agree with me on that point. But there is sometimes a need for persistence when programming. As explained in Okasaki's book, persistence is the property of a structure to remain valid after an operation (e.g. an insertion) have been performed on it. Purely functional datastructures are persistent. (The converse is not true: you may have persistent datastructures which are implemented in a purely functional way.) Consider for instance the problem of traversing the syntax tree of a program to do type checking. If the language require the use of a symbol table, you may choose between a persistent or a non-persistent implementation. With a non-persistent implementation, you are likely to add things in your table before going into a deeper subterm and to remove them when done with the subterm, like this: | Let (x,e1,e2) -> let ty1 = typecheck e1 in add x ty1; let ty2 = typecheck e2 in remove x; ty2 With a persistent datastructure, you only have to carry the current symbol table along and you never have to undo anything: | Let (x,e1,e2) -> let ty1 = typecheck st e1 in typecheck (add st x ty1) e2 This is a very silly example but there are many real situations where persistence is needed (I encountered many of them in practice). Then you look for efficient persistent datastructures and Okasaki's book provides good practical solutions for some of them and, above all, generic methods to build others. Hope this helps, -- Jean-Christophe FILLIATRE mailto:Jean-Christophe.Filliatre@lri.fr http://www.lri.fr/~filliatr