From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 D36B5BC32 for ; Wed, 16 Mar 2005 02:38:22 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j2G1cMun030763 for ; Wed, 16 Mar 2005 02:38:22 +0100 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 CAA31387 for ; Wed, 16 Mar 2005 02:38:21 +0100 (MET) Received: from kurims.kurims.kyoto-u.ac.jp (kurims.kurims.kyoto-u.ac.jp [130.54.16.1]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j2G1cJPQ030754 for ; Wed, 16 Mar 2005 02:38:20 +0100 Received: from localhost (suiren [130.54.16.25]) by kurims.kurims.kyoto-u.ac.jp (8.13.1/8.13.1) with ESMTP id j2G1cHob024161; Wed, 16 Mar 2005 10:38:17 +0900 (JST) Date: Wed, 16 Mar 2005 10:38:11 +0900 (JST) Message-Id: <20050316.103811.103748923.garrigue@math.nagoya-u.ac.jp> To: padiolea@irisa.fr Cc: caml-list@inria.fr Subject: Re: [Caml-list] OCaml troll on Slashdot From: Jacques Garrigue In-Reply-To: <32977.131.254.50.45.1110920621.squirrel@mail.irisa.fr> References: <200503152036.45894.jon@ffconsultancy.com> <32977.131.254.50.45.1110920621.squirrel@mail.irisa.fr> X-Mailer: Mew version 4.2 on Emacs 21.3 / Mule 5.0 (SAKAKI) Mime-Version: 1.0 Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 42378E0E.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at concorde with ID 42378E0B.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 ocaml:01 irisa:01 ocaml:01 functionnal:01 sumii:01 functionnal:01 trolls:01 associative:01 memoization:01 memoized:01 integers:01 trivial:01 arrays:01 memoization:01 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.2 X-Spam-Level: Well, since it seems difficult to hide that I'm an anonymous coward, I add a few comments for the list. From: padiolea@irisa.fr > Yes but this ocaml code use array ? > In that case it supports what the "troll" said, that is > the resulting code is no more "functionnal". > I agree with eijro sumii that ocaml is not just about functionnal > programming but in the mind of many people advocating ocaml is advocating > functionnal programming. > > I think the way to answer to those trolls is to teach them the way > to do, in that case to use Map instead of associative list, and > not to be pretentious and to tell that he is just a newbie. > He is not a newbie, this garden optimization problem is not that simple. In this particular case, I believe the trouble is rather that the problem is really geared toward a specific solution. Efficient memoization requires efficient access to memoized results, which in this case can be obtained by mapping states to integers. And there happens to be a trivial mapping. Then any solution will have to iterate on the states. If you look at my translation, I do not mutate arrays (except for memoization), and use no references. That is, the mapping from states to integers is actually produced in a purely functional way, and arrays are only there to provide O(1) access. Moreover state representation uses lists and natural sharing, so that it is reasonably space efficient. I also use lists, pattern matching, and recursion, so I believe this fulfills his requirement about being written in functional style. Out of curiosity, I also wrote a purely functional version, where memoizing is done through an array of lazy values. http://wwwfun.kurims.kyoto-u.ac.jp/~garrigue/garden3.ml The code is actually slightly shorter. Performance is rather close. On a Pentium M 1.8, for a 8x8 garden, I obtain (including memory usage) Garden.cpp 5.8s 6.1MB (g++ -O) Garden.cpp 4.5s 6.2MB (g++ -O3) garden2.ml 5.9s 8.3MB (ocamlopt) garden3.ml 10s 27.4MB (ocmalopt) So you can see that garden2, while being almost purely functional, is really equivalent in performance to his C++ code (which is a bit dumb, but garden2 doesn't try to be more clever), while garden3 uses more memory (as expected). The only thing this example shows is that writing in a functional language doesn't dispense you of doing a complexity analysis. In particular the use of structural equality and association lists may cost a lot in practice. Some people may have a mystical belief that the compiler will automatically improve your code through program transformation, but at least in ocaml the situation is simple: the compiler does no transformation whatsoever, so you get what you write. And of course, SICP is a good reading before starting to write in a functional programming language; I suppose all the structures I used are explained there in detail. Jacques Garrigue