Re: recursive definition

[Tarizzo Martial <tarizzo@worldnet.fr>]

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