From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.6.10/8.6.6) id LAA05579 for caml-redistribution; Wed, 24 Apr 1996 11:01:47 +0200 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.6.10/8.6.6) with ESMTP id AAA20293 for ; Wed, 24 Apr 1996 00:16:10 +0200 Received: from storm.certix.fr (storm.certix.fr [194.51.232.32]) by nez-perce.inria.fr (8.7.1/8.7.1) with SMTP id AAA00986 for ; Wed, 24 Apr 1996 00:16:06 +0200 (MET DST) Received: from client1.sct.fr (client1.sct.fr [194.2.128.31]) by storm.certix.fr (8.6.12/8.6.12) with SMTP id AAA09865; Wed, 24 Apr 1996 00:12:27 +0200 Date: Wed, 24 Apr 1996 00:12:27 +0200 Message-Id: <199604232212.AAA09865@storm.certix.fr> X-Sender: tarizzo@worldnet.fr X-Mailer: Windows Eudora Light Version 1.5.2 Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable To: "QUERCIA Michel (T) Math" From: Tarizzo Martial Subject: Re: recursive definition Cc: Pierre Weis Sender: weis At 12:16 22/04/1996 PDT, you wrote: >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =20 > >En francais : > >Il a ete explique dans un post precedent que "let rec x =3D f(x)" >n'est compilable que si "x" est une fonction ou si la compilation >de "f(x)" ne depend pas de "x". Il me semble que Caml-Light n'admet pas d'appel de fonction dans la partie droite d'un let rec, mais seulement des def du type fun ou function (cf doc). Je pense (mais j'attends l'avis d'un expert en compilation CAML) que cette limite est imposee par le mecanisme de typage. Le probleme est qu'une table de memorisation est une structure de donnees mutable, ce qui fait rarement bon menage avec la programmation= fonctionnelle. Si on veut avoir une memorisation pour une fonction recursive, les operations de mutations doivent se faire pour une structure d=E9finie en dehors du calcul proprement dit. Voila une solution, en conservant remember : (* fib1 est mutable au top-level.=20 def uniquement pour le typage lors de l'appel UNIQUE a remember *) let fib1 =3D ref (fun x -> x);; (* def de fib1, par mutation ! *) fib1 :=3D remember (fun x -> printf__fprintf stderr "appel fib1 %d\n" x; flush stderr; if x < 2 then 1 else !fib1(x-1) + !fib1(x-2) );; (* sucre syntaxique maintenant *) let fib =3D !fib1;; on peut encapsuler les choses par : let fib =3D=20 let fib1 =3D ref (fun x -> x) in fib1 :=3D remember (fun x -> printf__fprintf stderr "appel fib1 %d\n" x; flush stderr; if x < 2 then 1 else !fib1(x-1) + !fib1(x-2) ); !fib1;; >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =20 > >In english : > >I remember a post where it was explained that "let rec x =3D f(x)" is =20 >handled >only when "x" is a function or when "f(x)" may be compiled with no =20 >knowledge >of "x". > >So, what is wrong with the following attempt to define "fib" ? It seems to me that Caml-Light don't accept function calls in the right side of a let rec, but only fun or function definitions (cd doc). I think (but I expect a compilation expert advice) that this limitation is a consequence of the type system. A remember table is a mutable structure, which don't fit well with functionnal programming. If one want to memorize for a recursive function, mutation operations must concern a structure defined outside the recursive computation. Here is a solution, using remember : (* fib1 is mutable at the top-level.=20 used by the type system when remember is called only once *) let fib1 =3D ref (fun x -> x);; (* def of fib1 *) fib1 :=3D remember (fun x -> printf__fprintf stderr " fib1 called %d\n" x; flush stderr; if x < 2 then 1 else !fib1(x-1) + !fib1(x-2) );; (* syntactic sugar *) let fib =3D !fib1;; All in one : let fib =3D=20 let fib1 =3D ref (fun x -> x) in fib1 :=3D remember (fun x -> printf__fprintf stderr "appel fib1 %d\n" x; flush stderr; if x < 2 then 1 else !fib1(x-1) + !fib1(x-2) ); !fib1;; >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =20 > > >> Caml Light version 0.7 > ># (* +----------------------+ > | Fonction a memoire | > +----------------------+ *) > > >let remember(f) =3D > let t =3D hashtbl__new(17) in > fun x -> try hashtbl__find t x > with Not_found -> let y =3D f(x) in hashtbl__add t x y; y >;; >remember : ('a -> 'b) -> 'a -> 'b =3D ... >let rec fib =3D remember(fun x -> > if x < 2 then 1 else fib(x-1) + fib(x-2) >);; >Entr=E9e interactive: >>..............remember(fun x -> >> if x < 2 then 1 else fib(x-1) + fib(x-2) >>)....... >Ce genre d'expressions n'est pas autoris=E9 comme membre droit d'un "let = =20 >rec". ********************************* Tarizzo Martial Lycee Jean MOULIN - FORBACH 47 rue des anciens comb. d'AFN - 57000 METZ Tel : 87 55 95 89 Email: tarizzo@worldnet.fr 74014.3307@compuserve.com Compuserve : 74014,3307 *********************************