Warum ist Perl so viel Angst vor "deep recursion"?

Stolperte ich kürzlich über das Buch Higher-order Perl, die im Grunde zeigt Wege, Dinge zu tun, in Perl in einem funktionalen Weg. Der Autor erklärt, dass Perl 6 von 7 Kern-features von Lisp, während C keine hat.

Hatte ich ein problem, das aussah wie ein guter Kandidat für eine rekursive Lösung, und ich codiert es in diesem Mode. Aber Perl beschwerte sich über "deep recursion". Ich habe ein wenig gegoogelt und fand ein Perl-Mönch erklärt, dass "Perl ist nicht Haskell". Apperently Sie erhalten eine Beschwerde standardmäßig, wenn die Rekursionstiefe von mehr als 100 Ebenen.

Dort sind Möglichkeiten zu erweitern, diese zu begrenzen oder deaktivieren Sie es vollständig, aber meine Frage ist:

  • Gibt es einen Grund, dass Perl ist so nervös über Rekursion, während Haskell überhaupt nicht?
InformationsquelleAutor Martin Drautzburg | 2013-12-20
  1. 29

    Weil in Haskell, wir haben Faulheit & bewacht Rekursion und tail-call-Optimierung und Perl hat weder.

    Dies bedeutet im wesentlichen, dass jedem Funktionsaufruf weist eine festgelegte Menge an Speicher, genannt "Stapel", bis die Funktion zurückgibt. Beim schreiben von rekursiven code, erstellen Sie eine riesige Menge an Speicher, da dieser verschachtelte Funktionsaufrufe und schließlich kann die stack-überlauf. TCO ermöglicht es die ungenutzte chunks optimiert werden entfernt.

    Ohne diese ist es nicht wirklich eine gute Idee, auf die Sie sich verlassen Rekursion. Zum Beispiel, sagen, Sie schrieb eine rekursive version von map, es würde Abstürzen mit jeder anständigen Liste. In Haskell, bewacht Rekursion bedeutet, dass mit großen Listen, die rekursive Lösung ist viel schneller als eine "Schleife" like-Funktion.

    TLDR: Haskell-Implementierungen sind darauf ausgelegt, eine funktionale/rekursive Stil und perl-Implementierung ist nicht und zurück in die guten alten Tage, 100 Ebenen von Funktionsaufrufen war eine vernünftige Grenze.

    • nicht einverstanden; während perl nicht automatische Rekursion-Optimierungen, die 100 Grenze ist mehr von einer Annahme aus, dass es würde bedeuten, einen Fehler im Programm, als dass etwas schlimmes passieren würde (obwohl offensichtlich vor Jahrzehnten der Speicher war mehr ein Anliegen als jetzt). Sie können schreiben, rekursiven code, und es wird die Verwendung von Speicher, aber nicht eine "große" Menge.
    • für manche Arten der Rekursion wäre es egal, wenn Sie die TCO, die z.B. einen recursive-descent-parser verwenden, Speicher proportional zu der Größe des Programms, so oder so. Also ich weiß nicht, ob es unbedingt ein Fehler ist.
    • Perl hat tail-call-Optimierung - es ist nur nicht automatisch - Sie müssen verwenden Sie die goto Schlüsselwort zu tun, einen Schwanz nennen.
    • ist das nicht einen Anruf. Aber TCO führt oft zu ähnlichem code, gotos. Auch, wenn es nicht automatisch es ist nicht wirklich eine Umsetzung Optimierung
    • Die goto Schlüsselwort in Perl führt mehrere verschiedene Aufgaben. goto LABEL wirkt wie eine traditionelle "springen". goto $coderef und goto &subname tun, einen Schwanz nennen. Wischen Sie alle Spuren der aktuellen sub aus dem Stapel und rufen Sie dann die coderef/sub. (In der Tat, intern realisiert werden Sie als eine sofortige Rückkehr, gefolgt von einem normalen sub-Aufruf.)
    • Könnte genauso gut schreiben Sie einfach eine while/for-Schleife.
    • Explizite tailcalls sind in der Regel für andere Dinge als implizite Einsen.
    • Sie können auch Sub::Call::Tail machen viel ordentlicher Schwanz-Anruf mit code.

    InformationsquelleAutor jozefg
  2. 24

    Den "deep recursion" Warnung ist optional, und ein Indikator, dass etwas schief gegangen sein: die meisten der Zeit, eine Funktion ruft sich selbst immer und immer wieder nicht gedacht (Perl ist ein multi-Paradigma Sprache, und viele Menschen nicht verwenden funktionale Idiome). Und auch, wenn bewusst die Beschäftigung von Rekursion, es ist viel zu leicht zu vergessen, der base case.

    Es ist leicht zu schalten Sie die "deep recursion" Warnung aus:

    use warnings;
no warnings 'recursion';

sub recurse {
  my $n = shift;
  if ($n) {
    recurse($n - 1);
  }
  else {
    print "look, no warnings\n";
  }
}

recurse(200);

    Ausgabe:

    look, no warnings

    Es ist wahr, dass Perl nicht ausgeführt tail-Rekursion Optimierung, denn das würde Sie versauen die caller Ausgang (was wichtig ist für einige Dinge wie pragmas oder Carp). Wenn Sie möchten, führen Sie manuell einen Schwanz nennen, dann

    return foo(@args);

    wird

    @_ = @args; # or something like `*_ = \@args`
goto &foo;

    obwohl schlechte Dinge passieren können, wenn Sie dummerweise localniert @_.

    InformationsquelleAutor amon
  3. 3

    Runaway Rekursion Absturz wird entweder ein Perl-Programm oder ein Haskell-Programm nach unbegrenzter Zuteilung schließlich erschöpft den verfügbaren Speicher. Beide Sprachen sich mit diesem Potenzial Fallstrick in unterschiedlicher Weise.

    Perl

    Perl ist eine multi-Paradigma Sprache, sondern prozedurale am Herzen, und deep stack-Tiefe in diesem Paradigma kann zeigen, runaway Rekursion. Die perldiag-Dokumentation auf diese Diagnose-Staaten so viel, Hervorhebung Hinzugefügt.

    • Tiefe der Rekursion auf anonyme subroutine
    • Deep recursion on subroutine "%s"

      (W-Rekursion) Dieses Unterprogramm aufgerufen hat, sich selbst (direkt oder indirekt) 100 mal mehr als es zurückgegeben wurde. Dies bedeutet vermutlich eine unendliche Rekursion, es sei denn Sie schreiben seltsame benchmark-Programme, in welchem Fall es gibt etwas anderes.

    Es ist lediglich eine Laufzeit-Warnung, so dass, wenn Sie glauben, dass es unecht ist, deaktivieren Sie es mit einem pragma.

    sub known_deep_recursion {
  no warnings 'recursion';

  ...;
}

    Einen drastischeren und offenbar unnötige Weg, um den gleichen Effekt erzielen, ist beschrieben in dem gleichen Abschnitt der Perl-Dokumentation.

    Diese Schwelle kann geändert werden, von 100, die durch die Neukompilierung der perl binäre, Einstellung der C pre-Prozessor-makro PERL_SUB_DEPTH_WARN auf den gewünschten Wert.

    Haskell

    Haskell ist eine rein funktionale Sprache ist, wo die Rekursion wesentlich ist. Schreiben Haskell tail-rekursiv, wie in

    Einer rekursiven Funktion tail-rekursiv, wenn das endgültige Ergebnis des rekursiven Aufrufs ist das Ergebnis der Funktion selbst. Wenn das Ergebnis des rekursiven Aufrufs muss weiter bearbeitet werden (z.B. durch hinzufügen von 1 oder consing ein weiteres element auf den Anfang), es ist nicht tail-rekursiv.

    nutzt die compiler-Unterstützung für lazy evaluation und bewacht, Rekursion, was bedeutet, gut geschriebenen Haskell-code kann sowohl prägnant und haben ausgezeichnete Leistung.

    Aber Haskell ist nicht immun gegen Ausreißer Zuweisungen Bezug auf die Rekursion. Schlecht geschrieben von Haskell-code stack-Probleme auch, wie erwähnt, auf die - Stack overflow Seite auf HaskellWiki.

    Gibt es keine call-stack in Haskell. Stattdessen finden wir ein Muster-matching-stack, deren Einträge sich im wesentlichen case-Ausdrücke, die darauf warten, dass Ihre scrutinee ausgewertet werden genug, dass Sie mithalten können einen Konstruktor (WHNF).

    Wenn GHC ist die Bewertung eines thunked [das heißt, ungewichtete] Ausdruck es verwendet einen internen stack. Diese innere stack für thunk Bewertung ist das eine, die kann überlauf in der Praxis.

    Haskell nicht über einen call-stack wie prozeduralen Sprachen, also diese Abstürze sind bezeichnet als space leaks.

    Haskell-Programme werden manchmal verbrauchen viel mehr Speicher als notwendig, und dies wird oft durch zu viel oder zu wenig Faulheit.

    Z.B. die einfache Haskell-Programm unter

    mysum :: [Integer] -> Integer
mysum = foldr (+) 0

main = print (mysum [1..10000000000])

    wenn auf meiner Maschine zum laufen — wenn es nicht auf deiner, erhöhen die Obergrenze, bis es funktioniert — die Ergebnisse in der

    mysum: Out of memory

    Ändern Sie das Programm, um

    import Data.List (foldl')

mysum :: [Integer] -> Integer
mysum = foldl' (+) 0

main = print (mysum [1..10000000000])

    dauert eine Weile ausgeführt, aber schließlich bricht mit dem richtigen Ergebnis. Überlegungen zu einem Haskell-Programm die Verwendung des Platzes kann schwierig sein, für Anfänger. Rooting-out-Raum Lecks mit dem profiler ist ein Thema für fortgeschrittene.

    Zusammenfassung

    Beide sind hervorragende Sprachen, besonders in Ihren jeweiligen Nischen. Wir Programmierer machen manchmal Fehler. Die Ressourcenknappheit und die Halteproblem immer draußen gegen uns verschworen. Programmiersprachen beschäftigen sich mit diesen Einschränkungen in Ihrer eigenen Art und Weise.

    InformationsquelleAutor Greg Bacon
  4. 1

    Der Standard-Grenzwert ist zu niedrig, aber angemessen war für die kleineren Maschinen Perl ursprünglich lief auf. Jetzt 100, ist lächerlich, wenn Sie dabei schwere rekursive Arbeit, aber wie Sie sagen, es kann abgestimmt werden. Ich gehe davon aus Haskell hat eine andere Art zu fangen unendliche Rekursion?

    • Das ist realistischer in diesen Tagen. Wusste nicht, es wurde geschubst. Thx.
    • Ich würde davon ausgehen, dass Haskell optimiert tail-Rekursion in eine Schleife. In einer mehr imperativen Sprache wie perl, die Sie gerade sagen, die Menschen zu schreiben, eine Schleife selbst 😉
    • Eigentlich haskell hat tail-call-Optimierung, nicht nur für die Rekursion. Dies ist nicht möglich, mit fake einfach eine Schleife.
    • (Sorry, es wurde nicht geändert, von 100. Eine ähnliche Einstellung im debugger geändert wurde, um 1000. Ich meinte, Sie zu ändern, die für die Perl-Warnung zu.)
    • Unendliche Rekursion ist nicht gefangen in Haskell für genau den gleichen Gründen, die Endlosschleifen sind nicht gefangen in imperativen Sprachen.
    InformationsquelleAutor Bill Ruppert
Schreibe einen Kommentar