From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=AWL autolearn=disabled version=3.1.3 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 0C5F9BC50 for ; Tue, 3 Oct 2006 02:51:47 +0200 (CEST) Received: from smtp3.adl2.internode.on.net (smtp3.adl2.internode.on.net [203.16.214.203]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id k930piUB023206 for ; Tue, 3 Oct 2006 02:51:46 +0200 Received: from rosella (ppp229-164.lns3.syd7.internode.on.net [59.167.229.164]) by smtp3.adl2.internode.on.net (8.13.6/8.13.5) with ESMTP id k930ovjZ098039; Tue, 3 Oct 2006 10:21:13 +0930 (CST) (envelope-from skaller@users.sourceforge.net) Subject: Re: [Caml-list] More problems with memoization From: skaller To: Andrej.Bauer@andrej.com Cc: Diego Olivier FERNANDEZ PONS , caml-list@inria.fr In-Reply-To: <45219A06.6080909@fmf.uni-lj.si> References: <20060930200125.bjpzgnh7kkkogkgk@webmail.etu.upmc.fr> <200610010123.48846.jon@ffconsultancy.com> <20061002172902.93z4c75nj4c8c884@webmail.etu.upmc.fr> <45219A06.6080909@fmf.uni-lj.si> Content-Type: text/plain Date: Tue, 03 Oct 2006 10:50:56 +1000 Message-Id: <1159836656.8435.91.camel@rosella.wigram> Mime-Version: 1.0 X-Mailer: Evolution 2.6.1 Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 4521B420.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; memoization:01 andrej:01 recursive:01 fib:01 memoizing:01 recursion:01 variants:01 ocaml:01 compiler:01 fib:01 compiler:01 fib':01 fib':01 camlp:01 recursions:01 On Tue, 2006-10-03 at 01:00 +0200, Andrej Bauer wrote: > A recursive function _is_ the fixed point of a non-recursive one with an > "extra" argument. You may hide this fact if you wish, but I think it's > more honest to admit it to yourself. The "untied" version of fib has the > advantage that you can do many cool things to it: memoizing is just one > possibility. There is, however, a good reason this is not practical in general: for a recursion of N entities (either functions or polymorphic variants in Ocaml can be 'open-recursioned') you need an extra N arguments .. and the result is unreadable, as well as possibly incurring a performance hit. I wonder if one can add compiler support: for example given let rec fib x = match x with | 0 -> 0 | 1 -> 1 | n -> fib (n - 1) + fib (n - 2) The compiler silently generates: let @fib fib' x = match x with | 0 -> 0 | 1 -> 1 | n -> fib' (n - 1) + fib' (n - 2) let fib = make_rec @fib and now you have fib as written .. but you ALSO can do: let fib = make_mem @fib to create a memoised version. That's for one argument and can clearly be done easily by the compiler (in fact, camlp4). However the extension to multiple arguments is not clear. Maybe labelled arguments would help, perhaps using a record. Andrei said: "You may hide this fact if you wish, but I think it's more honest to admit it to yourself." but I think this is misleading: there's a good reason NOT to open the recursions. There's a fundamental principle of software design: the open/closed principle (OOSC) which is not obeyed by either the closed or open form. We need a form that is simultaneously closed and ready to use but which is also open and amenable to extension. FYI: the case that most interests me at the moment is neither type recursion nor functional recursion -- I'm interested in whether it is possible to design an open-recursive grammar, this seems to need both recursive data types *and* recursive functions in open/closed form. Interestingly in this case I have actually implemented one already, allowing Felix to extend it's own parser by combining an Ocamlyacc parser with an executable RD parser .. but this really isn't the same as systematic static extension where, for example you write a basic grammar, and then extensions to it. -- John Skaller Felix, successor to C++: http://felix.sf.net