Was ist die Erklärung für Übung 1.6 in SICP?

70

Ich fange gerade an, SICP durchzuarbeiten (alleine; dies ist nicht für eine Klasse), und ich habe seit ein paar Tagen mit Übung 1.6 zu kämpfen, und ich kann es einfach nicht herausfinden. Dies ist derjenige, den Alyssa neu definiert ifin Bezug auf cond:

(define (new-if predicate then-clause else-clause)
    (cond (predicate then-clause)
          (else else-clause))

Sie testet es erfolgreich in einigen einfachen Fällen und verwendet es dann, um das Quadratwurzelprogramm neu zu schreiben (was gut funktioniert hat if):

(define (sqrt-iter guess x)
    (new-if (good-enough? guess x)
            guess
            (sqrt-iter (improve guess x)
                       x)))

Die Frage lautet dann: "Was passiert, wenn Alyssa versucht, damit Quadratwurzeln zu berechnen? Erklären Sie." [Falls nötig, ich bin glücklich , die anderen Verfahren zu reproduzieren ( good-enough?, improveusw.), lassen Sie es mich wissen.]

Jetzt weiß ich, was passiert: Es gibt niemals einen Wert zurück, was bedeutet, dass das Programm unendlich rekursiv ist. Ich kann einfach nicht erklären, warum das passiert. Was auch immer feiner Unterschied besteht zwischen ifund new-ifist eluding ich. Jede Hilfe wird sehr geschätzt.

Alex Basson
quelle
2
Die Verbform von "rekursiv" ist "rekursiv", also "rekursiv".
Greg Hewgill
Vergleiche auch mit 4.25: community.schemewiki.org/?sicp-ex-4.25
mihai

Antworten:

91

new-ifist eine Funktion. Was macht Scheme beim Aufruf einer Funktion als erstes mit der Argumentliste? Es wertet alle Argumente aus.

Greg Hewgill
quelle
1
OP hätte dieses Problem in Haskell nicht! (Er hätte eine Schiffsladung anderer Probleme ...)
Davidbak
45

new-ifist ein Verfahren, und das Schema verwendet die Bewertung der anwendbaren Reihenfolge (1.1.5). Bevor new-ifes tatsächlich durchgeführt wird, muss es zuerst alle Argumente bewerten, nämlich guessund (sqrt-iter (improve guess x) x). Sie können sehen, dass das letztere Argument eine Rekursion ist, die eine neue new-ifProzedur aufruft. So tritt die Endlosschleife auf.

Das Gewöhnliche ifmuss seine Argumente nicht zuerst bewerten, sondern nur den Weg gehen, dies ist der Unterschied zwischen ifund new-if. :) :)

Junjie Zhang
quelle
1
Das new-ifVerfahren hat drei Argumente: predicate, then-clauseund else-clause. Wenn also new-ifheißt, (good-enough? guess x), guess, und (sqrt-iter (improve guess x))werden ausgewertet. Ist das richtig ? Dies ändert nichts am Ergebnis, da nur die Bewertung sqrt-iterder Probleme verursacht. Aber imo hast du ein Argument vergessen ...
Benjamin Crouzier
25

Zunächst müssen Sie den Unterschied zwischen der Bewertung der anwendbaren Bestellung und der normalen Bestellung verstehen . Lisp verwendet die anwendbare Reihenfolge, aber bedingte Ausdrücke werden nicht wie normale Funktionen ausgewertet ( sicp Kapitel 1.1.6 ):

(if <predicate> <consequent> <alternative>)

Um einen if-Ausdruck auszuwerten, bewertet der Interpreter zunächst den <predicate>Teil des Ausdrucks. Wenn der <predicate>Wert einen wahren Wert ergibt, wertet der Interpreter den <consequent>Wert aus und gibt seinen Wert zurück. Andernfalls wertet es das aus <alternative>und gibt seinen Wert zurück.

alex vasi
quelle
1
Vielen Dank, dass Sie den Link zur Buchreferenz hinzugefügt haben. Der Link ist unterbrochen, aber dies sollte funktionieren mitpress.mit.edu/sites/default/files/sicp/full-text/book/…
Abstract Class
7

Es gibt drei Möglichkeiten, wie ein Formular im Schema bewertet werden kann:

  1. Anwendbare Bestellung
    • Bewerten Sie die Argumente und wenden Sie sie dann an
    • gegeben f(x)=x+x: 3*f(1)*f(1)3*2*2
  2. Normale Reihenfolge
    • vollständig erweitern und dann reduzieren
    • gegeben f(x)=x+x: 3*f(1)*f(1)3*(1+1)*(1+1)(auch in "Lazy Evaluation" verwendet)
  3. Sonderformulare Zum Beispiel:
    • Boolesche andund or. Zum Beispiel: (and <e1> ... <en>)wertet Links → Rechts aus. Wenn einer Wert als falsch ausgewertet wird, ist der Wert von und Ausdruck falsch, und die übrigen Werte <e>werden nicht ausgewertet.
    • Bedingungen wie ifundcond
      • (if <predicate> <consequent> <alternative>): Wenn der <predicate>Wert einen wahren Wert ergibt, wertet der Interpreter den <consequent>Wert aus und gibt seinen Wert zurück. Andernfalls wertet es das aus <alternative>und gibt seinen Wert zurück
      • (cond (<p1> <e1>) ... (<pn> <en>)): Das Prädikat <p1>wird zuerst ausgewertet. Wenn sein Wert falsch ist, <pn>wird ausgewertet. Wenn <pn>der Wert ebenfalls falsch ist, <pn+1>wird er ausgewertet. Bei wahrem Prädikat gibt der Interpreter den Wert des entsprechenden nachfolgenden Ausdrucks zurück <e>.

Im Fall von Übung 1.6:

  • new-ifist ein normales Verfahren. In Scheme (und vielen anderen Sprachen) werden Argumente vollständig ausgewertet, bevor die Prozedur aufgerufen wird. Dies wird als anwendbare Reihenfolge bezeichnet . ∴ sqrt-iterwird jedes Mal new-ifaufgerufen, was zu einer Endlosschleife führt.
  • Für die Erbauung des Lesers sind normale ifs eine spezielle Form . Die rekursive Anweisung wird nur ausgewertet, wenn die <alternative>aufgerufen wird.
Schmudde
quelle
4

Frühere Antworten sind großartig. Ich werde eine weitere hinzufügen, die ausführlicher erklärt.

Eine andere Art, sich diesen Unterschied vorzustellen, ist folgende : Wie wird die Rekursion verwendet if, indem irgendwann gestoppt wird, und die Rekursion, die für immer eine new-ifSchleife verwendet?

Zuerst werden wir sehen , wie diese beiden , wenn die Arbeit im Allgemeinen und dann , wie sie für diesen Fall arbeiten.

if

Dies wird durch @ alex-vasi erklärt :

Um einen if-Ausdruck auszuwerten, bewertet der Interpreter zunächst den <predicate>Teil des Ausdrucks. Wenn der <predicate>Wert einen wahren Wert ergibt, wertet der Interpreter den <consequent>Wert aus und gibt seinen Wert zurück. Andernfalls wertet es das aus <alternative>und gibt seinen Wert zurück.

new-if

Dies wird von @Schmudde erklärt :

Alle Argumente werden vollständig ausgewertet, bevor die Prozedur aufgerufen wird.

Wie wird die Rekursion verwendet if, um irgendwann anzuhalten?

Es hört auf, weil wir an dem Punkt, an dem guessdas gut genug ist (dh (good-enough? guess x)ist true), haben werden:

(if (good-enough? guess x)
    guess
    (sqrt-iter (improve guess x)
               x)))

Und da das predicatejetzt ist true, wertet der Interpreter das consequent(was ist guess) aus, gibt seinen Wert zurück und bewertet das alternative(was ist (sqrt-iter (improve guess x) x)) nicht mehr .

Also iftatsächlich (sqrt-iter (improve guess x) x)rekursiv auswerten bis das guessgut genug ist. Dann stoppt es die Rekursion.

Wie ist die Rekursion mit new-ifLooping für immer?

Wie bei ifwird mit new-if (sqrt-iter (improve guess x) x)rekursiv ausgewertet, bis das guessgut genug ist.

Aber dann wird es immer (sqrt-iter (improve guess x) x)wieder ausgewertet . Warum? Denn bei der Bewertung:

(new-if (good-enough? guess x)
    guess
    (sqrt-iter (improve guess x)
               x)))

Da new-ifes sich um eine Prozedur handelt, wird nicht geprüft, ob sie (good-enough? guess x)wahr ist oder nicht, um zu entscheiden, ob entweder guessoder bewertet werden soll (sqrt-iter (improve guess x)). Was es tun wird, ist, dass es ausgewertet wird (good-enough? guess x), guessund (sqrt-iter (improve guess x))weil dies die Argumente des Verfahrens sind. Selbst wenn guesses gut genug ist, wird es immer wieder (sqrt-iter (improve guess x))rekursiv aufgerufen: /.

salvarico
quelle
0

Ex1.6. neu-wenn:

(define (new-if predicate then-clause else-clause)
     (cond (predicate then-clause)
                (else else-clause)))

Unterschied zu 'if-Anweisungen': if-Anweisungen werden einzeln anhand des Prädikats -> konsequent -> alternativ ausgewertet,

Das 'new-if' muss jedoch alle Parameter auswerten, auch bekannt als Argumente, die der MOMENT aufgerufen hat (was bedeutet, dass 'else-Klausel' zu Beginn ausgewertet wird !!).

und somit verursacht dies eine Endlosschleife, wenn sich einer dieser Parameter in eine iterative Schleife aufruft


quelle