Call by Need und Standard C Output?

Question

Der folgende Code ist hier mit halten die C Sprache Syntax:

#include <stdio.h> 
int func(int a, int b){ 
if (b==0) 
return 0; 
else return func(a,b); 
} 

int main(){ 
printf("%d \n", func(func(1,1),func(0,0))); 
return 0; 
} 

Was die Ausgabe dieses Codes auf 1) läuft mit Standard-C, 2) mit einem beliebigen Sprache, die Call-by-Bedarf Eigenschaft hat Dann:

in (1) die Programme Schleife in unendlichen Anruf und in (2) haben wir output Null! Dies ist ein Beispiel von TA in Programmiersprache Kurs gelöst, jede Idee zu beschreiben es für mich? Dank

Answer 1

den ersten Teil zu adressieren,

Der C Entwurf, 6.5.2.2-> 10 (Funktionsaufrufe) sagt

Die Reihenfolge der Auswertung von ... den tatsächlichen Argumente. .. ist nicht spezifiziert.

und für einen solchen Grund, etwas wie

printf("%d%d",i++,++i); 

hat Verhalten nicht definiert, weil

• beide ++i und i++ Nebenwirkungen hat, dh den Wert von i um eins erhöht wird.
• Das Komma in printf ist nur ein Trennzeichen und kein [ sequence point ].
• Obwohl der Funktionsaufruf selbst ein Sequenzpunkt ist, ist aus dem obigen Grund die Reihenfolge, in der zwei Modifikationen von i stattfinden, nicht definiert.

In Ihrem Fall

func(func(1,1),func(0,0)) 

aber haben die Argumente für äußere func dh func(1,1) oder func(0,0) keinen Einfluss auf einander im Gegensatz zu dem Fall, der oben gezeigt. Jede Reihenfolge der Auswertung dieser Argumente führt schließlich zu unendlicher Rekursion und so stürzt das Programm aufgrund des erschöpften Speichers ab.

Answer 2

Mit C, in der Regel ist es nicht die Reihenfolge der Argumente a und b Auswertung mit einer Funktion wie int func(int a, int b)

Offensichtlich Auswertung definiert func(1,1) problematisch ist und der Code leidet an diesen unabhängig davon, ob func(1,1) vor/nach ausgewertet/gleichzeitig mit func(0,0)

---

Analyse von func(a,b) basierend auf Notwendigkeit kann dem Schluss, dass, wenn b==0 , müssen Sie nicht func() anrufen und dann durch 0 ersetzen.

printf("%d \n", func(func(1,1),func(0,0))); 
// functionally then becomes 
printf("%d \n", func(func(1,1),0)); 

Applied wieder und

// functionally then becomes 
printf("%d \n", 0); 

Natürlich ist diese Schlussfolgerung nicht sicher, wie die Analyse von b != 0 und else return func(a,b); führt zu Endlosschleife. Ein solcher Code einen nützlichen gewünschten Nebeneffekt (zB Stack-Überlauf und Systemreset.) So kann die Analyse konservativ sein muß und nicht nimmt func(1,1) werden jemals Rückkehr und nicht sogar den Anruf optimieren, wenn es kann optimiert den func(0,0) Anruf.

---

Answer 3

1) In C (die strict evaluation semantics verwendet) wir unendliche Rekursion, weil in strikter Auswertung Argumente erhalten ausgewertet werden, bevor eine Funktion aufgerufen wird. Also in f(f(1,1), f(0,0))f(1,1) und f(0,0) werden vor der äußeren f ausgewertet (welche der beiden Argumente zuerst ausgewertet wird, ist in C nicht spezifiziert, aber das spielt keine Rolle). Und da f(1,1) eine unendliche Rekursion verursacht, erhalten wir eine unendliche Rekursion.

2) In einer Sprache, die non-strict evaluation verwendet (seien es Call-by-Name oder Call-by-Need), werden Argumente in den nicht ausgewerteten Funktionskörper eingesetzt und nur ausgewertet, wenn und wenn sie benötigt werden. So ist die äußere Aufruf f wird zunächst als solche bewertet:

if (f(0, 0) == 0) 
return 0; 
else return f(f(1,1), f(0,0)); 

Also, wenn die if Auswertung, müssen wir f(0,0), bewerten, die einfach auf 0 auswertet So gehen wir in die dann Zweig des if und nie Führe den else-Zweig aus. Da alle Aufrufe an f nur im else-Zweig verwendet werden, werden sie nie benötigt und daher nie ausgewertet. Also gibt es keine Rekursion, unendlich oder anders, und wir erhalten nur 0.