Warum lokale Arrays in Funktionen scheinen TCO zu verhindern?

Question

Sieht aus wie in Ihrer Funktion ein lokales Array mit Tail-Call-Optimierung auf es auf allen Compilern verhindert Ich habe habe es auf:

int foo(int*); 

int tco_test() { 
    // int arr[5]={1, 2, 3, 4, 5}; // <-- variant 1 
    // int* arr = new int[5]; // <-- variant 2 
    int x = foo(arr); 
    return x > 0 ? tco_test() : x; 
} 

Wenn variant 1 aktiv ist, gibt es einen wahren Aufruf tco_test() am Ende (gcc versucht, vorher etwas abzurollen, ruft aber am Ende immer noch die Funktion auf). Variant 2 führt TCO wie erwartet durch.

Gibt es in lokalen Arrays etwas, das es unmöglich macht, Tail Calls zu optimieren?

Answer 1

Wenn der Compiler sill TCO durchgeführt hat, dann würden alle externen foo(arr) Aufrufe den gleichen Zeiger erhalten. Das ist eine sichtbare Semantikänderung und somit keine reine Optimierung mehr.

Die Tatsache, dass die fragliche lokale Variable ein Array ist, ist hier wahrscheinlich ein Ablenkungsmanöver; es ist seine Sichtbarkeit nach außen über einen Zeiger, der wichtig ist.

dieses Programm vor:

#include <stdio.h> 

int *valptr[7], **curptr = valptr, **endptr = valptr + 7; 

void reset(void) 
{ 
    curptr = valptr; 

} 

int record(int *ptr) 
{ 
    if (curptr >= endptr) 
    return 1; 
    *curptr++ = ptr; 
    return 0; 
} 

int tally(void) 
{ 
    int **pp; 
    int count = 0; 

    for (pp = valptr; pp < curptr; pp++) 
    count += **pp; 

    return count; 
} 

int tail_function(int x) 
{ 
    return record(&x) ? tally() : tail_function(x + 1); 
} 

int main(void) 
{ 
    printf("tail_function(0) = %d\n", tail_function(0)); 
    return 0; 
} 

Als tail_function rekursiv, die es über einen Endrekursion der Fall ist, die record Funktion zeichnet die Adressen von verschiedenen Instanzen der lokalen Variablen x. Wenn es keinen Platz mehr hat, gibt es 1 zurück, und das löst tail_function aus, um tally aufzurufen und zurückzukehren. tally fegt durch die aufgezeichneten Speicherorte und fügt ihre Werte hinzu.

Wenn tally TCO unterliegen würde, dann würde es nur eine Instanz von x geben. Effektiv wäre es dies:

int tail_function(int x) 
{ 
tail: 
    if (record(&x)) 
    return tally(); 
    x = x + 1; 
    goto tail; 
} 

Und jetzt ist record die gleiche Stelle immer und immer wieder aufnehmen, wodurch tally einen falschen Wert statt der erwarteten 21 zu berechnen.

Die Logik der record und tally hängt von x auf jeder Aktivierung des Umfangs tatsächlich instanziiert wird, und dass die äußere Aktivierungen des Umfangs haben eine Lebensdauer, die bis die inneren enden erträgt. Diese Anforderung schließt aus, dass tail_function im konstanten Raum rekursiv ist; es muss separate x Instanzen zuweisen.