2010-07-02 28 views
3

Tenir compte de la mise en œuvre suivante d'une fonction pour calculer factoriel: [1]Pourquoi 'let` ne fonctionnera-t-il pas pour nommer les procédures internes récursives?

(define fac-tail 
    (lambda (n) 
    (define fac-tail-helper 
     (lambda (n ac) 
     (if (= 0 n) 
      ac 
      (fac-tail-helper (- n 1) (* n ac))))) 
    (fac-tail-helper n 1))) 

J'ai essayé de réécrire en utilisant let pour la définir intérieure:

(define fac-tail-2 
    (lambda (n) 
    (let ((fac-tail-helper-2 
      (lambda (n ac) 
       (if (= 0 n) 
        ac 
        (fac-tail-helper-2 (- n 1) (* n ac)))))) 
    (fac-tail-helper-2 n 1)))) 

Il n'y a pas d'erreur à define temps, mais exécution dans les résultats:

#;> (fac-tail-2 4) 
Error: undefined variable 'fac-tail-helper-2'. 
{warning: printing of stack trace not supported} 

Comment puis-je faire le travail de la version let?

version Scheme est SISC v 1.16.6

[1] Sur la base de la version itérative de factorial dans la section 1.2.1 de SICP http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1

+0

il est bon de savoir qu'il y a des gens qui piratent avec un système là-bas ... :) – galambalazs

Répondre

8

Comment puis-je faire le travail de la version let?

Utilisez letrec au lieu de let.

+0

La différence essentielle est que le corps d'une procédure letrec'd peut se référer à lui-même alors que le corps d'une procédure let'd ne peut pas. – erjiang

6

R. Kent Dvbvig dit:


En fait, une expression let est une extension syntaxique définie en termes d'application de lambda et de procédure, qui sont deux formes syntaxiques centrales. En général, toute expression de la forme

(let ((var expr) ...) body1 body2 ...) 

est équivalente à ce qui suit.

((lambda (var ...) body1 body2 ...) 
expr ...)" [1] 

Ce qui signifie que fac-tail-2 équivaut à:

(define fac-tail-2 
    (lambda (n) 
    ((lambda (fac-tail-helper-2) 
     (fac-tail-helper-2 n 1)) ;; <== scope where fac-tail-helper-2 is visible. 
    (lambda (n ac) ;; this lambda is assigned to fac-tail-helper-2 
     (if (= 0 n) 
      ac 
      (fac-tail-helper-2 (- n 1) (* n ac))))))) ;; <=== problem 

Et il est clair que le problème est que le nom fac-tail-helper-2 visible comme paramenter dans le corps du lambda souligné ci-dessus , mais n'est pas un nom au sein du lambda affecté au paramètre fac-tail-helper-2.

[1] L'article 2.5, "Expressions Lambda" de Le __gVirt_NP_NN_NNPS<__ langage de programmation Scheme, 4ème éditionhttp://scheme.com/tspl4/start.html#SECTGSLAMBDA

0

Deux autres alternatives, étant ajoutées par souci d'exhaustivité.

Le langage de programmation Scheme, 4e édition Section 3.2 a deux autres alternatives pour l'utilisation let et les fonctions récursives. http://scheme.com/tspl4/further.html#./further:h2

Le premier est intelligent et non recommandé. Il s'agit d'ajouter un paramètre au lambda qui est un lambda qu'il appelle, puis de se transmettre pour que tout soit démarré.

(define fac-tail-4 
    (lambda (n) 
    (let ((fac-tail-helper 
      (lambda (fac-tail-helper n ac) 
       (if (= 0 n) 
        ac 
        (fac-tail-helper fac-tail-helper (- n 1) (* n ac)))))) 
     (fac-tail-helper fac-tail-helper n 1)))) 

Et plus simple est le nom let qui pourrait être utilisé INSEAD de letrec pour récursion unique. Bien que cette version cache une définition lambda implicite qui est liée à fac-tail-helper.