Re: recursive definition

Re: recursive definition

[Tarizzo Martial]

At 12:16 22/04/1996 PDT, you wrote:
>==========================================================================  
>
>En francais :
>
>Il a ete explique dans un post precedent que "let rec x = 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éfinie en
dehors du calcul proprement dit.

Voila une solution, en conservant remember :
(* fib1 est mutable au top-level. 
   def uniquement pour le typage lors de l'appel UNIQUE a remember *)
let fib1 = ref (fun x -> x);;
(* def de fib1, par mutation ! *)
fib1 :=
  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 = !fib1;;

on peut encapsuler les choses par :
let fib = 
  let fib1 = ref (fun x -> x)
  in
  fib1 :=
    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;;
>==========================================================================  
>
>In english :
>
>I remember a post where it was explained that "let rec x = f(x)" is   
>handled
>only when "x" is a function or when "f(x)" may be compiled with no   
>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. 
   used by the type system when remember is called only once *)
let fib1 = ref (fun x -> x);;
(* def of fib1 *)
fib1 :=
  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 = !fib1;;

All in one :
let fib = 
  let fib1 = ref (fun x -> x)
  in
  fib1 :=
    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;;

>==========================================================================  
>
>
>>       Caml Light version 0.7
>
>#                        (* +----------------------+
>                            |  Fonction a memoire  |
>                            +----------------------+ *)
>
>
>let remember(f) =
>  let t = hashtbl__new(17) in
>  fun x -> try hashtbl__find t x
>           with Not_found -> let y = f(x) in hashtbl__add t x y; y
>;;
>remember : ('a -> 'b) -> 'a -> 'b = <fun>
...
>let rec fib = remember(fun x ->
>  if x < 2 then 1 else fib(x-1) + fib(x-2)
>);;
>Entrée interactive:
>>..............remember(fun x ->
>>  if x < 2 then 1 else fib(x-1) + fib(x-2)
>>).......
>Ce genre d'expressions n'est pas autorisé comme membre droit d'un "let   
>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
*********************************

Re: recursive definition

[Xavier Leroy]

[English summary: Caml's restrictions on let rec are not there just to
bug the users, but to ensure that a fixpoint is actually computed at
run-time. The proper ways to do recursive memo functions are: 1- don't
do it, 2- do it in-line, and 3- go through a memo fixpoint combinator.]

> Soit. Mais alors, pourquoi est-il si simple de coder l'exemple de M Quercia
> en SCHEME, pour lequel (dans le probleme qui nous occuppe) la principale
> difference me semble etre l'absence de typage ?

La grande difference est que Scheme n'offre aucune garantie a la
compilation que le let rec ne va pas provoquer une erreur a
l'execution, ni meme qu'il va bien calculer un point fixe. Les
restrictions syntaxiques de Caml, pour aussi drastiques qu'elles
paraissent, garantissent que le let rec s'execute sans erreurs et
calcule bien un point fixe.

Il n'y a essentiellement qu'une maniere de compiler des definitions
recursives complexes (c.a.d. pas de la forme let rec f x = ...):

compilation de let rec x = e:
        - initialiser x avec une valeur bidon bien choisie
        - calculer e avec cette valeur de x
        - identifier (par manipulation de pointeurs convenable)
          la valeur obtenue pour e et la valeur initiale de x

Pour que ca marche, il faut etre certain que le calcul de e ne va pas
avoir besoin de la "vraie" valeur de x, mais traite x
(essentiellement) de maniere abstraite. Par exemple, si x est de type
fonction, il faut etre sur que l'evaluation de e ne va pas effectuer
un appel a x.

Les restrictions syntaxiques sur le let rec de Caml garantissent cela. 
Votre code Scheme respecte aussi cette propriete (mais il faut le
prouver a la main). Cependant, si on le modifie un peu (pour que
"remember" calcule a l'avance les valeurs de f en 0, 1 et 2 par exemple),
vous allez obtenir une erreur a l'execution, car f va etre appelee
trop tot:

> (define (remember f)
>   (let ((t (list (cons 0 (f 0)) (cons 1 (f 1)) (cons 2 (f 2)))))
>     (lambda l
>       (let ((a (assoc l t)))
>         (if a
>           (cdr a)
>           (let ((y (apply f l)))
>             (set! t (cons `(,l . ,y) t))
>             y))))))

Revenons au probleme initial de faire des memos-fonctions recursives.

1- Je comprends mal cette fixation sur les memos-fonctions,
qui sont une bidouille peu recommandable pour programmeur trop
paresseux pour trouver un algorithme naturellement efficace pour son
probleme.

2- La maniere la plus claire d'ecrire une memo-fonction
recursive reste d'expanser dans la definition de la fonction le code
de memoisation:

let memo_fib = hashtbl__new 17;;
let rec fib n =
  if n < 2 then 1 else begin
    try
      hashtbl__find memo_find n
    with Not_found ->
      let r = fib(n-1) + fib(n-2) in
      hashtbl__add memo_find n r;
      r
  end;;

Au moins, on comprend quand les choses sont evaluees. Ceci evite en
particulier les bugs d'eta-expansion sauvage qui font perdre tout
comportement memo sans que le programmeur s'en rende compte, comme
nous l'avons vu dans des messages precedents de cette liste.

3- Si on veut absolument avoir une fonctionnelle de memoisation qui
marche pour des fonctions recursives, il faut ecrire un combinateur de
point fixe a memoire:

let memo_fix func =
  let memo = hashtbl__new 17 in
  let rec f x =
    try
      hashtbl__find memo x
    with Not_found ->
      let res = func f x in
      hashtbl__add memo x res;
      res
  in f;;

let fib = memo_fix (fun fib n -> print_int n; print_newline();
                                 if n < 2 then 1 else fib(n-1) + fib(n-2));;

(* #fib 5;;
5
3
1
2
0
4
- : int = 8 *)

Mais par pitie ne montrez pas ca a vos eleves.

- Xavier Leroy

Re: recursive definition

[Tarizzo Martial]

At 21:17 24/04/1996 +0200, Damien.Doligez@inria.fr (Damien Doligez) wrote:
(English version below)

...
>Il est garanti que "let rec x = Expr" est compilable si "Expr" est
>de la forme "fun z...y -> ..." ou "function y -> ...", et c'est tout.
>
>L'implementation actuelle de Caml Light va un peu plus loin et accepte
>de compiler si "Expr" est un constructeur de type concret (ou de
>paire, de liste, de record, de tableau) ou une constante.
>
>On accepte aussi un "let v = E1 in E2" a condition que E1 et E2
>verifient aussi la condition, ca c'est alors equivalent a
>"let rec x = E2 and v = E1".  Peut-etre qu'il y a d'autres cas que
>j'ai oublies dans les coins.
>
>Cette restriction nous est imposee par la technique de compilation du
>"let rec", elle n'a rien a voir avec le systeme de types.  Le seul
>rapport avec le typeur, c'est que c'est le typeur qui detecte les
>erreurs a ce niveau.  On aurait pu le faire dans le parseur, et alors
>le message d'erreur serait "Erreur de syntaxe".
Soit. Mais alors, pourquoi est-il si simple de coder l'exemple de M Quercia
en SCHEME, pour lequel (dans le probleme qui nous occuppe) la principale
difference me semble etre l'absence de typage ?
Exemple de code (teste avec Scheme->C, conforme au R4RS) :
(define (remember f)
  (let ((t '()))
    (lambda l
      (let ((a (assoc l t)))
        (if a
          (cdr a)
          (let ((y (apply f l)))
            (set! t (cons `(,l . ,y) t))
            y))))))

(define fib
  (remember (lambda (x)
              (display "appel : ")(display  x)(newline)
              (if (< x 2)
                1
                (+ (fib (- x 2))
                  (fib (- x 1)))))))

>--------------
...
>The only guarantee is that "let rec x = Expr" will be accepted if
>"Expr" is an expression of the form "fun z...y -> ..." or
>"function y -> ...".
>
>The current implementation has an extension that will also accept it
>if "Expr" is a constructor for a concrete type (or pair, list, record,
>array), or a constant.
>
>It also accepts "let v = E1 in E2" for "Expr", if E1 and E2 also have
>the same form, because this is equivalent to "let rec x = E2 and v = E1".
>There may be some other cases, I don't remember.
>
>This restriction comes from the compilation technique used for "let
>rec".  It has nothing to do with the type system.  The only connection
>with types is that the type checker is used to detect problems in "let
>rec".  We could have changed the grammar and let the parser handle
>them, you would get a syntax error.
>
OK. But why is it so easy to code the M Quercia's example in SCHEME, the
main difference being in my point of view (for this particular problem) the
lack of typing between the two laguages ?
Sample code (tested with Scheme->C, R4RS conformant) :
(define (remember f)
  (let ((t '()))
    (lambda l
      (let ((a (assoc l t)))
        (if a
          (cdr a)
          (let ((y (apply f l)))
            (set! t (cons `(,l . ,y) t))
            y))))))

(define fib
  (remember (lambda (x)
              (display "Called : ")(display  x)(newline)
              (if (< x 2)
                1
                (+ (fib (- x 2))
                  (fib (- x 1)))))))

*********************************
 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
*********************************

Re: recursive definition

[Damien Doligez]

(English version below)

>From: "QUERCIA Michel (T) Math" <querciam@l-carnot1.ac-dijon.fr>

>Il a ete explique dans un post precedent que "let rec x = f(x)"
>n'est compilable que si "x" est une fonction ou si la compilation
>de "f(x)" ne depend pas de "x".

En un mot, c'est une explication boguee.

Il est garanti que "let rec x = Expr" est compilable si "Expr" est
de la forme "fun z...y -> ..." ou "function y -> ...", et c'est tout.

L'implementation actuelle de Caml Light va un peu plus loin et accepte
de compiler si "Expr" est un constructeur de type concret (ou de
paire, de liste, de record, de tableau) ou une constante.

On accepte aussi un "let v = E1 in E2" a condition que E1 et E2
verifient aussi la condition, ca c'est alors equivalent a
"let rec x = E2 and v = E1".  Peut-etre qu'il y a d'autres cas que
j'ai oublies dans les coins.

Cette restriction nous est imposee par la technique de compilation du
"let rec", elle n'a rien a voir avec le systeme de types.  Le seul
rapport avec le typeur, c'est que c'est le typeur qui detecte les
erreurs a ce niveau.  On aurait pu le faire dans le parseur, et alors
le message d'erreur serait "Erreur de syntaxe".

Ca n'a rien a voir avec le typage, ce qui explique que le message
d'erreur parle de "genre" d'expression et non de "type".

Avec un peu de chance, il y a un moyen d'ecrire un "remember_rec" qui
integre un combinateur de point fixe dans "remember".

--------------

>I remember a post where it was explained that "let rec x = f(x)" is
>handled only when "x" is a function or when "f(x)" may be compiled
>with no knowledge of "x".

That post was wrong.

The only guarantee is that "let rec x = Expr" will be accepted if
"Expr" is an expression of the form "fun z...y -> ..." or
"function y -> ...".

The current implementation has an extension that will also accept it
if "Expr" is a constructor for a concrete type (or pair, list, record,
array), or a constant.

It also accepts "let v = E1 in E2" for "Expr", if E1 and E2 also have
the same form, because this is equivalent to "let rec x = E2 and v = E1".
There may be some other cases, I don't remember.

This restriction comes from the compilation technique used for "let
rec".  It has nothing to do with the type system.  The only connection
with types is that the type checker is used to detect problems in "let
rec".  We could have changed the grammar and let the parser handle
them, you would get a syntax error.

Again, this has nothing to do with typing, which explains that the
error message says "kind of expression" and not "type of expression".

There may be a way of writing a "remember_rec" to combine the
fix-point combinator with memoization.

-- Damien

Re: recursive definition

[Doug Currie, Flavors Technology, Inc.]

>let rec fib = remember(fun x ->
>  if x < 2 then 1 else fib(x-1) + fib(x-2)
>);;
>EntrHe interactive:
>>..............remember(fun x ->
>>  if x < 2 then 1 else fib(x-1) + fib(x-2)
>>).......
>Ce genre d'expressions n'est pas autorisH comme membre droit d'un "let
>rec".

How about:

#let rec fib x = remember(fun x ->
  if x < 2 then 1 else fib(x-1) + fib(x-2)
) x ;;

e

recursive definition

[QUERCIA Michel (T) Math]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 2425 bytes --]



==========================================================================  

En francais :

Il a ete explique dans un post precedent que "let rec x = f(x)"
n'est compilable que si "x" est une fonction ou si la compilation
de "f(x)" ne depend pas de "x".

Qu'est-ce qui ne va pas dans la definition de "fib" ci dessous ?

==========================================================================  

In english :

I remember a post where it was explained that "let rec x = f(x)" is   
handled
only when "x" is a function or when "f(x)" may be compiled with no   
knowledge
of "x".

So, what is wrong with the following attempt to define "fib" ?

==========================================================================  


>       Caml Light version 0.7

#                        (* +----------------------+
                            |  Fonction a memoire  |
                            +----------------------+ *)


let remember(f) =
  let t = hashtbl__new(17) in
  fun x -> try hashtbl__find t x
           with Not_found -> let y = f(x) in hashtbl__add t x y; y
;;
remember : ('a -> 'b) -> 'a -> 'b = <fun>
#


let premier = remember(fun x ->
  printf__fprintf stderr "appel %d\n" x; flush stderr;
  let y = ref(2) in
  while !y * !y < x & x mod !y > 0 do incr y done;
  !y * !y > x
);;
premier : int -> bool = <fun>
#
map premier [1;2;3;4;5;6;7;8;9;10];;
appel 10
appel 9
appel 8
appel 7
appel 6
appel 5
appel 4
appel 3
appel 2
appel 1
 - : bool list =
 [true; true; true; false; true; false; true; false; false; false]
#
map premier [1;2;3;4;5;6;7;8;9;10];;
 - : bool list =
 [true; true; true; false; true; false; true; false; false; false]
#


let rec fib = remember(fun x ->
  if x < 2 then 1 else fib(x-1) + fib(x-2)
);;
Entrée interactive:
>..............remember(fun x ->
>  if x < 2 then 1 else fib(x-1) + fib(x-2)
>).......
Ce genre d'expressions n'est pas autorisé comme membre droit d'un "let   
rec".
#quit();;

Process inferior-caml finished

==========================================================================  


PS : J'ai aussi essaye :

let rec fib(x) = let g = remember(fun x -> ...) in g(x);;

Ca marche (a la compilation) mais il n'y a pas memorisation
des resultats puisque g est reconstruite a chaque appel.

==========================================================================  


Michel Quercia
Lycee Carnot
Dijon

email = querciam@ac-dijon.fr
Cc = quercia@u-bourgogne.fr