Date: Wed, 24 Apr 1996 00:12:27 +0200
Message-Id: <199604232212.AAA09865@storm.certix.fr>
To: "QUERCIA Michel (T) Math" <querciam@l-carnot1.ac-dijon.fr>
From: Tarizzo Martial <tarizzo@worldnet.fr>
Subject: Re: recursive definition
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 <fun>
...
>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
*********************************