Funktioniert „Anonyme Rekursion“ in .NET?Das ist in Mono der Fall

Question

Ich bin reingesurft Das Website vor ein paar Tagen zum Thema „Anonyme Rekursion in C#“.Der Kernpunkt des Artikels ist, dass der folgende Code in C# nicht funktioniert:

Func<int, int> fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;

Anschließend geht der Artikel näher auf die Verwendung ein Curry und das Y-Kombinator um zur „Anonymen Rekursion“ in C# zurückzukehren.Das ist ziemlich interessant, aber für mein alltägliches Programmieren etwas komplex, fürchte ich.Zumindest zu diesem Zeitpunkt...

Da ich mir die Dinge gerne selbst ansehe, habe ich das Mono geöffnet CSharp REPL und gab diese Zeile ein.Keine Fehler.Also trat ich ein fib(8);.Zu meiner großen Überraschung hat es funktioniert!Die REPL antwortete mit 21!

Ich dachte, das sei vielleicht etwas Zauberhaftes mit der REPL, also habe ich „vi“ gestartet, das folgende Programm eingegeben und es kompiliert.

using System;

public class Program
{
    public static void Main(string[] args)
    {
        int x = int.Parse(args[0]);
        Func<int, int> fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
        Console.WriteLine(fib(x));
    }
}

Es baute und lief auch perfekt!

Ich verwende Mono 2.10 auf einem Mac.Ich habe derzeit keinen Zugriff auf einen Windows-Computer und kann dies daher nicht unter .NET unter Windows testen.

Wurde dies auch in .NET behoben oder ist dies eine stille Funktion von Mono?Der Artikel ist ein paar Jahre alt.

Wenn es sich nur um Mono handelt, kann ich das nächste Vorstellungsgespräch kaum erwarten, bei dem ich gebeten werde, eine Fibinocci-Funktion in der Sprache meiner Wahl (Mono C#) zu schreiben, wobei ich den Vorbehalt angeben muss, dass .NET nicht funktionieren wird.Eigentlich kann ich warten, da ich meinen Job liebe.Trotzdem interessant...

Aktualisieren:

Mono führt nicht wirklich eine „anonyme“ Rekursion durch, wie es verwendet wird fib als benannter Delegierter.Mein Fehler.Die Tatsache, dass der Mono C#-Compiler a null Wert für fib Vor der Zuweisung liegt ein Fehler vor, wie unten erwähnt.Ich sage „Compiler“, weil die .NET CLR die resultierende Assembly problemlos ausführen würde, auch wenn der .NET C#-Compiler den Code nicht kompilieren würde.

Für alle Interview-Nazis da draußen:

Func<int, int> fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;

kann durch eine iterative Version ersetzt werden:

Func<int, int> fib = n => 
{
    int old = 1;
    int current = 1;
    int next;

    for (int i = 2; i < n; i++)
    {
        next = current + old;
        old = current;
        current = next;
    }
    return current;
};

Möglicherweise möchten Sie dies tun, da die rekursive Version in einer Sprache wie C# ineffizient ist.Einige schlagen möglicherweise die Verwendung vor Auswendiglernen Da dies jedoch immer noch langsamer ist als die iterative Methode, sind sie möglicherweise nur Wichser.:-)

An diesem Punkt wird dies jedoch eher zu einer Werbung für funktionale Programmierung als zu irgendetwas anderem (da die rekursive Version so viel schöner ist).Es hat wirklich nichts mit meiner ursprünglichen Frage zu tun, aber einige der Antworten hielten es für wichtig.

Answer 1

Das ist ein Insekt im Mono-Compiler.Es verstößt gegen Abschnitt §12.3.3 des Spezifikation.Die Variable Flunkerei kann nicht im Variableninitialisierer verwendet werden, da es nicht definitiv zugewiesen ist.

Answer 2

Wie ich oben in einem Kommentar bemerkt habe, liegt ein Fehler vor, wenn Mono das tut.Aus der Spezifikation geht klar hervor, dass dies als Fehler erkannt werden soll.Der Fehler ist natürlich größtenteils harmlos und macht meistens das, was Sie wollen.Wir haben darüber nachgedacht, die Regeln zu ändern, um diese Art der Rekursion legal zu machen.Grundsätzlich müssten wir der Spezifikation einen Sonderfall hinzufügen, der besagt, dass dieser eng definierte Fall legal ist.Die Priorität war jedoch nie hoch genug.

Weitere Gedanken zu diesem Thema finden Sie in meinem Artikel zu diesem Thema:

http://blogs.msdn.com/b/ericlippert/archive/2006/08/18/706398.aspx

Und übrigens würde ich niemanden einstellen, der mir in einem Vorstellungsgespräch eine direkte rekursive Implementierung von Fib gegeben hätte.Es ist äußerst ineffizient;seine Laufzeit ist proportional zur Größe seiner Ausgabe, und fib wächst exponentiell.Um es effizient zu machen, verwenden Sie die Rekursion mit Memoisierung, oder implementieren Sie die offensichtliche iterative Lösung.

Answer 3

Versuche dies...

Func<int, int> fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n; 

...Das Problem besteht darin, dass fib nicht definiert ist, wenn Sie versuchen, es in der oben genannten Methode zu verwenden, sodass der statische Analysator einen Compilerfehler meldet.

Answer 4

Es scheint, dass ich mich in meiner Aufregung grundlegend geirrt habe.Weder .NET noch Mono bieten „Anonyme Rekursion“ in der Art und Weise, wie es der Originalartikel bedeutet.Du konntest nicht herumgehen fib als eigenständige Einheit.

Schauen Sie sich die folgende Sequenz in der Mono C# REPL an:

csharp> Func<int, int> fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n; 
csharp> fibCopy = fib;
csharp> fib(6);
8
csharp> fibCopy(6);
8
csharp> fib = n => n * 2;
csharp> fib(6);
12
csharp> fibCopy(6);
18

Das ist weil:

fib = n => n * 2;
fibCopy = n > 1 ? fib(n - 1) + fib(n - 2) : n;

Mit anderen Worten,

fibCopy = n > 1 ? (n - 1) * 2 + (n - 2) * 2 : n;    // at the moment

Deutlich, fibCopy verweist nur auf die aktuelle Definition von fib (der Delegierte) und nicht an sich selbst.Mono weist also eigentlich nur einen Wert von vorab zu null Zu fib bei der Erstzuweisung, damit die Zuweisung gültig ist.

Ich bevorzuge die Bequemlichkeit, keine Erklärung abgeben zu müssen null also mir gefällt dieses Verhalten.Dennoch ist es nicht wirklich das, worüber im Originalartikel gesprochen wird.

Answer 5

Im C#-Compiler von Microsoft funktioniert es nur, wenn Sie es zuerst festlegen fib Zu null.

Andernfalls wird ein Fehler ausgegeben, weil fib wird verwendet, bevor es zugewiesen wird.
Der Compiler von Mono ist „intelligent“ genug, um diesen Fehler zu vermeiden (mit anderen Worten, er verstößt gegen die offizielle Spezifikation).