Αναδρομή

Οι subs μπορούν να καλούν τον εαυτό τους, η μία την άλλη, ή - με λίγη τελετουργία - να αντικαθιστούν το δικό τους πλαίσιο κλήσης και να περνούν τον έλεγχο αλλού χωρίς να μεγαλώνει η στοίβα. Αυτή η σελίδα καλύπτει τους τέσσερις μηχανισμούς: απλή αναδρομή, αμοιβαία αναδρομή, κλήσεις ουράς goto &fn, και __SUB__ για ανώνυμη αυτο-αναφορά. Καλύπτει επίσης το όριο βάθους στο οποίο θα φτάσετε αν τα αγνοήσετε.

Απλή αναδρομή

sub factorial {
    my ($n) = @_;
    return 1 if $n <= 1;
    return $n * factorial($n - 1);
}

factorial(10);                   # 3628800

Κάθε αναδρομική κλήση προσθέτει ένα νέο πλαίσιο στη στοίβα κλήσεων της Perl. Η στοίβα κοστίζει μνήμη και ένα σταθερό κόστος ανά κλήση· για ρηχή αναδρομή αυτό είναι αμελητέο, για βαθιά αναδρομή είναι το σημείο συμφόρησης.

Η Perl εκπέμπει μια προειδοποίηση «Deep recursion on subroutine X» όταν μια sub αναδράμει πέρα από 100 επίπεδα βάθους (κατώφλι μεταγλώττισης, PERL_SUB_DEPTH_WARN). Η προειδοποίηση ανήκει στην κατηγορία recursion - η no warnings 'recursion' την αποσιωπά. Το μόνο σκληρό όριο είναι η στοίβα του OS, τυπικά 8 MiB εξ ορισμού, ρυθμιζόμενο με ulimit -s.

Για βαθιούς, δομικά αναδρομικούς φόρτους εργασίας, προτιμήστε ένα από τα:

• Μια ρητή ουρά εργασίας (επαναδιατύπωση σε επαναληπτική μορφή).

• Αναδρομή ουράς μέσω goto &fn (βλέπε παρακάτω).

• Ένα trampoline (βλέπε παρακάτω).

Αμοιβαία αναδρομή

Δύο subs που καλούν η μία την άλλη:

sub is_even {
    my ($n) = @_;
    return 1 if $n == 0;
    return is_odd($n - 1);
}

sub is_odd {
    my ($n) = @_;
    return 0 if $n == 0;
    return is_even($n - 1);
}

is_even(10);                     # 1

Η αμοιβαία αναδρομή δεν έχει ειδική μεταχείριση από τον χρόνο εκτέλεσης - είναι απλώς δύο subs που τυχαίνει να καλούν η μία την άλλη. Ισχύει το ίδιο όριο βάθους.

Αν η is_even ορίζεται πρώτη και αναφέρεται στην is_odd πριν υπάρξει η is_odd, θα δείτε «Bareword not allowed» ή «Called undefined subroutine» ανάλογα με τη μορφή κλήσης. Προδηλώστε για να το διορθώσετε:

sub is_odd;                      # forward declaration
sub is_even { ... is_odd($n-1) }
sub is_odd  { ... is_even($n-1) }

goto &fn - προώθηση κλήσης ουράς

Η μορφή goto &SUBROUTINE αντικαθιστά το τρέχον πλαίσιο με μια κλήση σε άλλη sub. Το τρέχον πλαίσιο εξαφανίζεται - δεν βρίσκεται στη στοίβα - οπότε η κλήση δεν μεγαλώνει τη στοίβα:

sub api_v2 {
    my @args = @_;
    push @args, deprecated => 1;
    @_ = @args;
    goto &api_v1;                # tail-call: api_v1 sees the modified @_
}

Αυτό είναι το σωστό εργαλείο όταν:

• Μια sub-περιτύλιγμα χρειάζεται να προωθήσει σε πραγματική υλοποίηση χωρίς να αφήσει πλαίσιο στοίβας πίσω. Decorators, shims καταγραφής, AUTOLOAD dispatchers.

• Μια αναδρομική sub μπορεί να εκφράσει την αναδρομή της ως «κάνε κάποια δουλειά, μετά γίνε αυτή η άλλη κλήση». Κλασική αναδρομή ουράς:

  sub factorial_tail {
      my ($n, $acc) = @_;
      $acc //= 1;
      return $acc if $n <= 1;
      @_ = ($n - 1, $n * $acc);
      goto &factorial_tail;
  }
  
  factorial_tail(20);            # 2432902008176640000, no stack growth
  

Η μηχανική: το @_ γίνεται ο πίνακας ορισμάτων της καλούμενης sub, το τρέχον πλαίσιο ξετυλίγεται, ο έλεγχος πηδά. Ο καλών της τρέχουσας sub θα δει το αποτέλεσμα της sub στην οποία έγινε goto, ποτέ αυτής που κάλεσε.

Η goto &fn είναι η μόνη μορφή goto που εκτελεί κλήση ουράς. Η μορφή βασισμένη σε ετικέτα (goto LABEL) είναι άσχετη και πολύ πιο περιορισμένη.

Δείτε goto για πλήρη περιγραφή της δεσμευμένης λέξης και τους περιορισμούς μορφής.

__SUB__ - ανώνυμη αυτο-αναφορά

use feature 'current_sub';                # or use v5.16

my $factorial = sub {
    my ($n) = @_;
    return 1 if $n <= 1;
    return $n * __SUB__->($n - 1);
};

$factorial->(5);                 # 120

Η __SUB__ αποτιμάται σε αναφορά κώδικα προς την τρέχουσα εκτελούμενη sub. Είναι ο μόνος τρόπος να κάνετε αναδρομή σε ανώνυμη sub χωρίς να την αποθηκεύσετε πρώτα σε ονομαστική μεταβλητή (και χωρίς να διαρρέει ισχυρή αναφορά προς αυτή μέσα από τον εαυτό της, η κλασική μορφή διαρροής μνήμης).

Για ανώνυμες subs που δεν χρειάζεται να κάνουν αναδρομή, προτιμήστε την απλή ανώνυμη μορφή. Η __SUB__ υπάρχει ειδικά για την περίπτωση αναδρομής.

Trampolines

Όταν θέλετε αναδρομή με οριοθετημένη στοίβα αλλά η goto &fn είναι δύσχρηστη (επειδή η αναδρομή είναι αμοιβαία, ή διακλαδίζεται σε πολλές υπο-περιπτώσεις), το μοτίβο trampoline λειτουργεί:

sub trampoline {
    my $next = shift;
    while (ref $next eq 'CODE') {
        $next = $next->();
    }
    return $next;
}

sub even {
    my ($n) = @_;
    return $n == 0 ? 1 : sub { odd($n - 1)  };
}

sub odd {
    my ($n) = @_;
    return $n == 0 ? 0 : sub { even($n - 1) };
}

trampoline(even(10000));         # 1, no stack growth

Κάθε «αναδρομική» κλήση επιστρέφει ένα closure για να γίνει η επόμενη κλήση, αντί να καλεί τον εαυτό της απευθείας. Το trampoline οδηγεί τα closures σε βρόχο. Η στοίβα παραμένει σε βάθος 2 για πάντα.

Τα trampolines είναι βαρύτερα από τη goto &fn (μία δέσμευση closure ανά «κλήση»), αλλά γενικεύονται σε αυθαίρετη ροή ελέγχου - συμπεριλαμβανομένων continuations και κώδικα τύπου CPS. Για Perl παραγωγής, η goto &fn είναι η συνηθισμένη επιλογή· τα trampolines εμφανίζονται όταν η δομή της αναδρομής κάνει τη goto δυσεπίτακτη.

Το όριο βάθους, στην πράξη

sub recurse {
    my ($n) = @_;
    return $n if $n <= 0;
    return recurse($n - 1);
}

recurse(2000);                   # warning: Deep recursion on subroutine
                                 # (default limit 1000)

Η προειδοποίηση «Deep recursion» είναι ενημερωτική, όχι μοιραία - εκπέμπεται μία φορά ανά sub. Θα εξαντλήσετε τον πραγματικό χώρο στοίβας πολύ πριν φτάσετε κάποιο πρακτικό όριο στις περισσότερες πλατφόρμες. Αν δείτε αυτή την προειδοποίηση, η απάντηση είναι σχεδόν πάντα αναδιαμόρφωση (επαναληπτικός βρόχος, goto &fn, ή trampoline), όχι αύξηση του ορίου.

Αν έχετε ήδη επαληθεύσει ότι η αναδρομή είναι οριοθετημένη και απλώς θέλετε να αποσιωπήσετε τον θόρυβο, περιορίστε την κατηγορία προειδοποίησης:

no warnings 'recursion';

Αυτό αποσιωπά εντελώς την προειδοποίηση· δεν αλλάζει το όριο στοίβας του OS, το οποίο είναι αυτό που τελικά τερματίζει μια ανεξέλεγκτη αναδρομή ανεξάρτητα από τις προειδοποιήσεις.

Δείτε επίσης

• goto - η δεσμευμένη λέξη πίσω από τη goto &fn.

• caller - λειτουργεί μέσα από πλαίσια μετά από goto με την ίδια αρίθμηση όπως τα κανονικά πλαίσια.

• Ορίσματα και @_ - σημασιολογία @_ υπό goto &fn.

• Δήλωση - ανώνυμες subs, το υπόστρωμα για __SUB__ και trampolines.

• Εμβέλεια - closures, το υπόστρωμα για trampolines.