Date: Thu, 25 Apr 1996 23:41:04 +0200
Message-Id: <199604252141.XAA23450@storm.certix.fr>
To: Pierre Weis <Pierre.Weis@inria.fr>
From: Tarizzo Martial <tarizzo@worldnet.fr>
Subject: Re: recursive definition
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
*********************************