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 UAA10199 for caml-redistribution; Fri, 26 Apr 1996 20:41:51 +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 XAA17788 for ; Thu, 25 Apr 1996 23:44:53 +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 XAA18419 for ; Thu, 25 Apr 1996 23:44:45 +0200 (MET DST) Received: from rouen0-087.sct.fr (rouen0-087.sct.fr [194.206.158.87]) by storm.certix.fr (8.6.12/8.6.12) with SMTP id XAA23450 for ; Thu, 25 Apr 1996 23:41:04 +0200 Date: Thu, 25 Apr 1996 23:41:04 +0200 Message-Id: <199604252141.XAA23450@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="us-ascii" To: Pierre Weis From: Tarizzo Martial Subject: Re: recursive definition Sender: weis 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 *********************************