5

数日前、「C# での匿名再帰」についてこのサイトにアクセスしました。この記事の主旨は、次のコードは C# では機能しないということです。

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

次に、カリー化とY コンビネーターを使用して C# の「匿名再帰」に戻る方法について詳しく説明します。これは非常に興味深いですが、私の日常のコーディングには少し複雑です。この時点で少なくとも...

私は自分の目で見るのが好きなので、Mono CSharp REPLを開いてその行に入りました。エラーなし。ということで、入りfib(8);ました。驚いたことに、うまくいきました！REPL は21!で応答しました。

これは REPL の魔法かもしれないと思ったので、「vi」を起動し、次のプログラムを入力してコンパイルしました。

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));
    }
}

それも完璧に構築され、実行されました！

Mac で Mono 2.10 を実行しています。現在、Windows マシンにアクセスできないため、Windows 上の .NET でこれをテストすることはできません。

これは .NET でも修正されていますか、それとも Mono のサイレント機能ですか? 記事は数年前のものです。

Mono のみの場合、次の就職の面接が待ちきれません。そこでは、.NET が機能しないという警告を提供する必要がある言語 (Mono C#) でフィビノッチ関数を作成するように求められます。まあ、実際、私は仕事が好きなので待つことができます。それにしても面白い…

アップデート：

fib名前付きデリゲートとして使用しているため、Monoは実際には「匿名」再帰を行っていません。私の悪い。nullMono C# コンパイラが代入前の値を想定するという事実は、fib以下に示すバグです。私が「コンパイラ」と言ったのは、.NET C# コンパイラがコードをコンパイルしなくても、.NET CLR は結果のアセンブリを問題なく実行できるからです。

そこにあるすべてのナチスのインタビューについて：

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

反復バージョンに置き換えることができます:

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;
};

C# のような言語では再帰バージョンが非効率的であるため、これを実行する必要がある場合があります。メモ化の使用を提案する人もいるかもしれませんが、これは反復的な方法よりもまだ遅いため、単に気まぐれである可能性があります。:-)

ただし、この時点で、これは他の何よりも関数型プログラミングの宣伝になります (再帰バージョンの方がはるかに優れているため)。元の質問とはまったく関係ありませんが、回答の一部は重要だと考えていました。

4

5 に答える 5

7

上記のコメントで指摘したように、Mono がそれを行う場合、バグがあります。これをエラーとして検出する仕様になっているのは明らかです。もちろん、バグはほとんど無害であり、ほとんどの場合、あなたが望むことを行います。この種の再帰を正当化するためにルールを変更することを検討しました。基本的に、この狭義のケースが正当であるという特別なケースを仕様に追加する必要があります。しかし、それは十分に高い優先度ではありませんでした。

この問題の詳細については、この件に関する私の記事を参照してください。

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

ところで、インタビューで fib の再帰的な実装をストレートに教えてくれた人を雇うつもりはありません。非常に非効率的です。その実行時間は出力のサイズに比例し、fib は指数関数的に増加します。memoizationで再帰を効率的に使用するか、明らかな反復ソリューションを実装します。

于 2011-03-30T15:28:52.083 に答える
7

これは、Mono コンパイラのバグです。これは、仕様のセクション 12.3.3 に違反しています。変数fibは、確実に割り当てられていないため、変数初期化子では使用できません。

于 2011-03-30T15:34:40.263 に答える
3

これを試して...

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

... 問題は、上記の方法で fib を使用しようとしたときに fib が定義されていないため、静的アナライザーがコンパイラ エラーを報告することです。

于 2011-03-30T14:56:44.083 に答える
1

興奮した私は根本的に間違っていたようです。.NET も Mono も、元の記事が意味する方法で「匿名再帰」を提供しません。fib自己完結型のエンティティとして通過することはできませんでした。

Mono C# REPL で次のシーケンスを確認してください。

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

それの訳は：

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

言い換えると、

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

明らかに、それ自体ではなく、(デリゲート)fibCopyの現在の定義を指しているだけです。したがって、Mono は実際には、最初の割り当て中にtofibの値を事前に割り当てているだけなので、割り当てが有効になります。nullfib

私は宣言する必要がないという利便性を非常に好むnullので、この動作が気に入っています。それでも、それは実際には元の記事が話していることではありません。

于 2011-03-30T15:29:34.430 に答える
0

Microsoft の C# コンパイラでは、最初fibにnull.

fibそうしないと、が割り当てられる前に使用されるため、エラーが発生します。
Mono のコンパイラは、このエラーを回避するのに十分「スマート」です (つまり、公式の仕様に違反しています)。

于 2011-03-30T14:56:57.233 に答える