Quand un programme «entrelace-t-il définition et utilisation»?
La note de bas de page no 28 du SICP dit ce qui suit:
Les définitions intégrées doivent venir en premier dans un corps de procédure. La direction n'est pas responsable des conséquences de l'exécution de programmes qui mêlent définition et utilisation.
Qu'est-ce que cela signifie exactement? Je comprends:
- « définitions » pour désigner à la fois les créations de procédures et les attributions de valeur.
- " un organe de procédure " tel que défini dans la section 1.1.4 . C'est le code qui vient après la liste des paramètres dans la définition d'une procédure.
- « Les définitions intégrées doivent venir en premier dans un corps de procédure » pour signifier « toutes les définitions qui sont faites et utilisées dans le corps d'une procédure doivent venir avant toute autre chose ».
- " entrelacer la définition et l'utilisation " pour signifier " appeler une procédure ou une valeur assignée avant qu'elle n'ait été définie ;"
Cependant, cette compréhension semble contredire les réponses à cette question , qui a des réponses que je peux résumer comme `` l'erreur à laquelle votre citation fait référence concerne l'utilisation de définitions au début du corps d'une procédure qui reposent sur des définitions qui sont également à la début de ce corps ». Cela me confond trois fois:
- Cette interprétation contredit clairement ce que j'ai dit ci-dessus, mais semble avoir des preuves solides - des règles de compilation - derrière elle.
- SICP semble heureux de mettre la définition dans un corps avec d'autres définitions qui les utilisent. Regardez simplement la
sqrtprocédure juste au-dessus de la note de bas de page ! - En un coup d'œil, il me semble que la véritable erreur de l'auteur de la question liée était de traiter
num-prodcomme une valeur dans sa définition denumplutôt que comme une procédure. Cependant, l'auteur l'a clairement fait fonctionner, donc je me trompe probablement.
Alors qu'est-ce qui se passe vraiment? Où est le malentendu?
Réponses
Dans la définition / le code d'une procédure donnée,
- Les "définitions internes" sont des formes commençant par
define. - "un corps de procédure" est toutes les autres formes après les formes qui commencent par
define. - «Les définitions intégrées doivent venir en premier dans un corps de procédure» signifie que tous les
defineformulaires internes doivent être placés en premier, puis tous les autres formulaires internes. Une fois qu'undefineformulaire non interne apparaît, il ne peut plus apparaître dedefineformulaire interne après cela. - "aucune utilisation entrelacée" signifie aucune utilisation d'un nom avant sa définition. Imaginez que toutes les
defineformes internes sont rassemblées en un seul équivalentletrecet suivez ses règles.
À savoir, nous avons,
(define (proc args ...)
;; internal, or "embedded", definitions
(define a1 ...init1...)
(define a2 ...init2...)
......
(define an ...initn...)
;; procedure body
exp1 exp2 .... )
Any peut être utilisé dans n'importe laquelle des expressions, mais uniquement dans une expression lambda. (*) Sinon, cela ferait référence à la valeur de while est en cours de définition, ce qui est interdit, car tous les noms sont considérés comme non encore définis pendant que l'une des expressions est en cours d'évaluation.aiinitjaiajaiinitj
(*) N'oubliez pas que (define (foo x) ...x...)c'est la même chose que (define foo (lambda (x) ...x...)). C'est pourquoi les définitions de cette sqrtprocédure dans le livre que vous mentionnez sont correctes - ce sont toutes des lambdaexpressions, et l'utilisation de tout nom dans une expression lambda ne fera en réalité référence à la valeur de ce nom que lorsque la valeur de l'expression lambda - une fonction lambda - sera être appelée, pas lorsque cette expression lambda est en cours d'évaluation, produisant cette fonction lambda qui est sa valeur.
Le livre est un peu vague au début avec la sémantique précise de son langage mais dans Scheme le code ci-dessus équivaut à
(define proc
(lambda (args ...)
;; internal, or "embedded", definitions
(letrec ( (a1 ...init1...)
(a2 ...init2...)
......
(an ...initn...) )
;; procedure body
exp1 exp2 ....
)))
comme on peut le voir expliqué, par exemple, ici , ici ou ici .
Par exemple,
;; or, equivalently,
(define (my-proc x) (define my-proc
(lambda (x)
(define (foo) a) (letrec ( (foo (lambda () a))
(define a x) (a x) )
;; my-proc's body ;; letrec's body
(foo)) (foo))))
évalue d'abord l'expression lambda (lambda () a), et lie le nom fooau résultat, une fonction; cette fonction fera référence à la valeur de a when (foo)sera appelée , donc c'est OK qu'il y ait une référence à l' aintérieur de cette expression lambda - car lorsque cette expression lambda est évaluée, aucune valeur de an'est immédiatement nécessaire, juste la référence à sa valeur future , sous le nom a, y est présent; c'est-à-dire la valeur qui a aura après tous les noms qui letrecsont initialisés, et le corps de letrecest entré. Ou en d'autres termes, lorsque tous les defines internes sont terminés et que le corps propre de la procédure my-procest inscrit.
On voit donc que fooc'est défini, mais n'est pas utilisé lors des initialisations; aest défini mais n'est pas utilisé lors des initialisations; donc tout va bien. Mais si nous avions par exemple
(define (my-proc x)
(define (foo) x) ; `foo` is defined as a function
(define a (foo)) ; `foo` is used by being called as a function
a)
alors ici fooest à la fois défini et utilisé lors des initialisations des s internes, ou «embarqués» define; ceci est interdit dans Scheme. C'est ce à quoi le livre met en garde: les définitions internes ne sont autorisées qu'à définir des choses, mais son utilisation devrait être retardée pour plus tard, lorsque nous aurons fini avec les defines internes et que nous entrons dans le corps de la procédure complète.
C'est subtil, et comme l'indiquent la note de bas de page et la question que vous faites référence, les subtilités peuvent varier en fonction de l'implémentation d'un langage particulier.
Ces questions seront traitées de manière beaucoup plus détaillée plus loin dans le livre (chapitres 3 et 4) et, généralement, le texte évite d'utiliser des définitions internes afin que ces problèmes puissent être évités jusqu'à ce qu'ils soient examinés en détail.
Une différence clé entre le code au-dessus de la note de bas de page:
(define (sqrt x)
(define (good-enough? guess)
(< (abs (- (square guess) x)) 0.001))
(define (improve guess)
(average guess (/ x guess)))
(define (sqrt-iter guess)
(if (good-enough? guess)
guess
(sqrt-iter (improve guess))))
(sqrt-iter 1.0))
et le code dans l'autre question:
(define (pi-approx n)
(define (square x) (* x x))
(define (num-prod ind) (* (* 2 ind) (* 2 (+ ind 1)))) ; calculates the product in the numerator for a certain term
(define (denom-prod ind) (square (+ (* ind 2 ) 1))) ;Denominator product at index ind
(define num (product num-prod 1 inc n))
(define denom (product denom-prod 1 inc n))
est que toutes les définitions dans le premier sont des définitions de procédure , alors que numet denomsont des définitions de valeur . Le corps d'une procédure n'est pas évalué tant que cette procédure n'est pas appelée. Mais une définition de valeur est évaluée lorsque la valeur est attribuée.
Avec une définition de valeur:
(define sum (add 2 2))
(add 2 2)sera évalué lorsque la définition est évaluée, si tel est le cas, elle adddoit déjà être définie. Mais avec une définition de procédure:
(define (sum n m) (add n m))
un objet de procédure sera assigné summais le corps de la procédure n'est pas encore évalué et addn'a donc pas besoin d'être défini quand sumest défini, mais doit l'être au moment où sumest appelé:
(sum 2 2)
Comme je l'ai dit, il y a beaucoup de sous-vêtements et beaucoup de variations, donc je ne suis pas sûr que ce qui suit est toujours vrai pour chaque variante de schéma, mais dans le `` schéma SICP '', vous pouvez dire ...
Valide (ordre d'évaluation de defines non significatif):
;procedure body
(define (sum m n) (add m n))
(define (add m n) (+ m n))
(sum 2 2)
Aussi valable:
;procedure body
(define (sum) (add 2 2))
(define (add m n) (+ m n))
(sum)
Habituellement invalide (l'ordre d'évaluation de defines est significatif):
;procedure body
(define sum (add 2 2))
(define (add m n) (+ m n))
La validité de ce qui suit dépend de l'implémentation:
;procedure body
(define (add m n) (+ m n))
(define sum (add 2 2))
Et enfin un exemple d' entrelacement de la définition et de l'utilisation , si cela fonctionne dépend également de l'implémentation. IIRC, cela fonctionnerait avec Scheme décrit dans le chapitre 4 du livre si la numérisation a été implémentée.
;procedure body
(sum)
(define (sum) (add 2 2))
(define (add m n) (+ m n))
C'est compliqué et subtil, mais les points clés sont:
- les définitions de valeur sont évaluées différemment des définitions de procédure,
- le comportement à l'intérieur des blocs peut être différent de celui des blocs extérieurs,
- il y a une variation entre les implémentations de schéma,
- le livre est conçu pour que vous n'ayez pas à vous en soucier avant le chapitre 3,
- le livre couvrira cela en détail au chapitre 4.
Vous avez découvert une des difficultés du schéma. Et de lisp. En raison de ce type de problème de poulet et d'œuf , il n'y a pas de lisp, mais beaucoup de lisps sont apparus.
Si les formes de liaison ne sont pas présentes dans le code dans une letrec-logic dans R5RS et letrec*-logic dans R6RS, la sémantique n'est pas définie . Ce qui signifie que tout dépend de la volonté de l'implémenteur du schéma.
Voir l'article Fixing Letrec: A Faithful Yet Efficient Implementation of Scheme's Recursive Binding Construct .
En outre, vous pouvez lire les discussions de la liste de diffusion de 1986 , quand il n'y avait pas de consensus général entre les différents implémenteurs de schéma.
De plus, au MIT, 2 versions du schéma ont été développées - la version étudiante et la version développement des chercheurs, et elles se sont comportées différemment en ce qui concerne l'ordre des defineformulaires.