Wann verflechtet ein Programm Definition und Verwendung?

Oct 01 2020

In Fußnote 28 des SICP heißt es:

Eingebettete Definitionen müssen in einem Prozedurkörper an erster Stelle stehen. Das Management ist nicht verantwortlich für die Folgen der Ausführung von Programmen, die Definition und Verwendung miteinander verflechten.

Was genau bedeutet das? Ich verstehe:

  • " Definitionen " beziehen sich sowohl auf Prozedurerstellungen als auch auf Wertzuweisungen.
  • " ein Verfahrenskörper " gemäß Abschnitt 1.1.4 . Es ist der Code, der nach der Liste der Parameter in der Definition einer Prozedur steht.
  • " Eingebettete Definitionen müssen in einem Prozedurkörper an erster Stelle stehen " bedeutet " alle Definitionen, die im Körper einer Prozedur erstellt und verwendet werden, müssen vor allem anderen stehen ".
  • " Definition und Verwendung verflechten " bedeutet " Aufrufen einer Prozedur oder eines zugewiesenen Werts, bevor diese definiert wurde ".

Dieses Verständnis scheint jedoch den Antworten auf diese Frage zu widersprechen , die Antworten enthält, die ich zusammenfassen kann: „ Der Fehler, auf den sich Ihr Zitat bezieht, besteht darin, Definitionen am Anfang eines Verfahrenskörpers zu verwenden , die auf Definitionen beruhen, die sich ebenfalls in der Anfang dieses Körpers '. Das hat mich dreifach verwirrt:

  1. Diese Interpretation widerspricht eindeutig dem, was ich oben gesagt habe, scheint aber starke Beweise - Compiler-Regeln - dahinter zu haben.
  2. SICP scheint glücklich zu sein, Definitionen in einen Körper mit anderen Definitionen zu setzen, die sie verwenden. Schauen Sie sich das sqrtVerfahren direkt über der Fußnote an !
  3. Auf den ersten Blick scheint mir der eigentliche Fehler des Autors der verknüpften Frage darin zu liegen, ihn num-prodals Wert in seiner Definition numund nicht als Verfahren zu behandeln. Der Autor hat es jedoch eindeutig zum Laufen gebracht, also irre ich mich wahrscheinlich.

Also, was ist wirklich los? Wo ist das Missverständnis?

Antworten

3 WillNess Oct 04 2020 at 02:51

In der Definition / dem Code einer bestimmten Prozedur

  • "interne Definitionen" sind Formen, die mit beginnen define.
  • "ein Prozedurkörper" sind alle anderen Formen nach den Formen, die mit beginnen define.
  • "Eingebettete Definitionen müssen in einem Prozedurkörper an erster Stelle stehen" bedeutet, dass alle internen defineFormulare zuerst und dann alle anderen internen Formulare verwendet werden müssen. Sobald ein nicht defineinternes Formular angezeigt wird, kann danach kein internes Formular mehr angezeigt werden define.
  • "keine miteinander verflochtene Verwendung" bedeutet, dass kein Name verwendet wird, bevor er definiert ist. Stellen Sie sich vor, alle internen defineFormulare werden zu einem Äquivalent zusammengefasst letrecund befolgen dessen Regeln.

Wir haben nämlich,

(define (proc args ...)
   ;; internal, or "embedded", definitions
   (define a1 ...init1...)
   (define a2 ...init2...)
   ......
   (define an ...initn...)
   ;; procedure body
   exp1 exp2 .... )

Beliebig kann in jedem der Ausdrücke verwendet werden, jedoch nur innerhalb eines Lambda-Ausdrucks. (*) Andernfalls würde es sich auf den Wert von while beziehen, der definiert wird, und das ist verboten, da alle Namen als noch nicht definiert betrachtet werden, während einer der Ausdrücke ausgewertet wird.aiinitjaiajaiinitj


(*) Denken Sie daran, dass dies (define (foo x) ...x...)dasselbe ist wie (define foo (lambda (x) ...x...)). Aus diesem Grund sind die Definitionen in dieser sqrtProzedur in dem von Ihnen erwähnten Buch in Ordnung - sie sind alle lambdaAusdrücke, und die Verwendung eines Namens in einem Lambda-Ausdruck bezieht sich nur dann tatsächlich auf den Wert dieses Namens, wenn der Wert des Lambda-Ausdrucks - eine Lambda-Funktion - dies tut aufgerufen werden, nicht wenn dieser Lambda-Ausdruck ausgewertet wird, wodurch die Lambda-Funktion erzeugt wird, die sein Wert ist.


Das Buch ist zunächst etwas vage mit der genauen Semantik seiner Sprache, aber im Schema entspricht der obige Code

(define proc 
   (lambda (args ...)
      ;; internal, or "embedded", definitions
      (letrec ( (a1 ...init1...)
                (a2 ...init2...)
                ......
                (an ...initn...) )
        ;; procedure body
        exp1 exp2 .... 
        )))

wie man zum Beispiel hier , hier oder hier erklären kann .


Beispielsweise,

                                   ;; 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))))

wertet zuerst den Lambda-Ausdruck aus (lambda () a)und bindet den Namen fooan das Ergebnis, eine Funktion; diese Funktion wird auf den Wert beziehen , a wenn (foo)aufgerufen wird , so dass es OK ist , dass es zu einer Referenz ist ainnerhalb dieses Lambda - Ausdrucks - denn wenn der Lambda - Ausdruck ausgewertet wird, kein Wert awird sofort benötigt, nur der Verweis auf seinen zukünftigen Wert, unter dem Namen aist dort vorhanden; dh der Wert, a der nach allen Namen in der letrecinitialisiert wird, und der Körper von letrecwird eingegeben. Oder mit anderen Worten, wenn alle internen defines abgeschlossen sind und der eigentliche Körper der Prozedur my-proceingegeben wird.

Wir sehen also, dass dies foodefiniert ist, aber während der Initialisierungen nicht verwendet wird. awird definiert, aber während der Initialisierungen nicht verwendet; damit ist alles gut. Aber wenn wir zB hätten

(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)

dann wird hier foosowohl definiert als auch während der Initialisierungen der internen oder "eingebetteten" defines verwendet; Dies ist im Schema verboten. Dies ist, worüber das Buch warnt: Die internen Definitionen dürfen nur Dinge definieren, aber ihre Verwendung sollte für später verzögert werden, wenn wir mit den internen defines fertig sind und den gesamten Hauptteil der Prozedur eingeben.

2 codybartfast Oct 01 2020 at 16:07

Dies ist subtil, und wie die Fußnote und die Frage, auf die Sie verweisen, implizieren, können die Feinheiten je nach Implementierung einer bestimmten Sprache variieren.

Diese Probleme werden später in diesem Buch (Kapitel 3 und 4) ausführlicher behandelt, und im Allgemeinen werden im Text keine internen Definitionen verwendet, sodass diese Probleme vermieden werden können, bis sie eingehend untersucht werden.

Ein wesentlicher Unterschied zwischen dem Code über der Fußnote:

(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))

und der Code in der anderen Frage:

(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))

ist , dass alle in defintions ersteren Verfahren Definitionen, während numund denomist Wert defintions. Der Hauptteil einer Prozedur wird erst ausgewertet, wenn diese Prozedur aufgerufen wird. Eine Wertedefinition wird jedoch ausgewertet, wenn der Wert zugewiesen wird.

Mit einer Wertdefinition:

(define sum (add 2 2))

(add 2 2)wird ausgewertet, wenn die Definition ausgewertet wird, falls dies addbereits definiert sein muss. Aber mit einer Verfahrensdefinition:

(define (sum n m) (add n m))

Ein Prozedurobjekt wird zugewiesen, sumaber der Prozedurkörper ist noch nicht ausgewertet. Er addmuss nicht definiert werden, wenn er sumdefiniert ist, sondern muss zum Zeitpunkt des sumAufrufs sein:

(sum 2 2)

Wie ich schon sagte, es gibt viel Subtilität und viel Variation, daher bin ich mir nicht sicher, ob das Folgende immer für jede Variation des Schemas gilt, aber innerhalb des 'SICP-Schemas' kann man sagen ..

Gültig (Reihenfolge der Bewertung von defines nicht signifikant):

;procedure body
(define (sum m n) (add m n))
(define (add m n) (+ m n))
(sum 2 2)

Auch gültig:

;procedure body
(define (sum) (add 2 2))
(define (add m n) (+ m n))
(sum)

Normalerweise ungültig (Reihenfolge der Bewertung von defines ist signifikant):

;procedure body
(define sum (add 2 2))
(define (add m n) (+ m n))

Ob Folgendes gültig ist, hängt von der Implementierung ab:

;procedure body
(define (add m n) (+ m n))
(define sum (add 2 2))

Und schließlich ein Beispiel für die Verflechtung von Definition und Verwendung , ob dies funktioniert, hängt auch von der Implementierung ab. IIRC, dies würde mit dem in Kapitel 4 des Buches beschriebenen Schema funktionieren, wenn das Scannen implementiert wurde.

;procedure body
(sum)
(define (sum) (add 2 2))
(define (add m n) (+ m n))

Es ist kompliziert und subtil, aber die wichtigsten Punkte sind:

  1. Wertedefinitionen werden anders bewertet als Prozedurdefinitionen.
  2. Das Verhalten innerhalb von Blöcken kann sich von dem außerhalb von Blöcken unterscheiden.
  3. Es gibt Unterschiede zwischen den Schemaimplementierungen.
  4. Das Buch ist so konzipiert, dass Sie sich bis Kapitel 3 nicht viel darum kümmern müssen.
  5. Das Buch wird dies in Kapitel 4 ausführlich behandeln.
alinsoar Oct 01 2020 at 16:46

Sie haben eine der Schwierigkeiten des Schemas entdeckt. Und von Lisp. Aufgrund dieser Art von Henne- Ei- Problem gibt es kein einzelnes Lispeln, aber es traten viele Lisps auf.

Wenn die Bindungsformulare im Code in einer letrec-logic in R5RS und letrec*-logic in R6RS nicht vorhanden sind , ist die Semantik undefiniert . Das heißt, alles hängt vom Willen des Implementierers des Schemas ab.

Siehe das Papier Fixing Letrec: Eine zuverlässige und dennoch effiziente Implementierung des rekursiven Bindungskonstrukts des Schemas .

Sie können auch die Diskussionen aus der Mailingliste von 1986 lesen , als zwischen den verschiedenen Implementierern des Schemas kein allgemeiner Konsens bestand.

Außerdem wurden am MIT zwei Versionen des Schemas entwickelt - die Studentenversion und die Entwicklungsversion der Forscher, und sie verhielten sich in Bezug auf die Reihenfolge der defineFormulare unterschiedlich.