Работает ли “Анонимная рекурсия” в .NET?Это происходит в моно

StackOverflow https://stackoverflow.com/questions/5488015

Вопрос

Я занялась серфингом в этот сайт несколько дней назад на тему "Анонимная рекурсия в C#".Суть статьи заключается в том, что следующий код не будет работать на C#:

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

Затем в статье подробно рассказывается о том, как использовать приготовление карри и Y-комбинатор вернемся к "анонимной рекурсии" в C#.Это довольно интересно, но, боюсь, немного сложно для моего повседневного программирования.По крайней мере, на данный момент...

Мне нравится все видеть своими глазами, поэтому я открыл Mono CSharp REPL и вошел в эту строку.Ошибок нет.Итак, я вошел fib(8);.К моему большому удивлению, это сработало!Представитель ответил в ответ: 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));
    }
}

Он тоже был построен и работал идеально!

Я запускаю Mono 2.10 на Mac.Сейчас у меня нет доступа к компьютеру с Windows, поэтому я не могу протестировать это на .NET в Windows.

Было ли это исправлено и в .NET, или это скрытая функция Mono?Статье уже пару лет.

Если это только Mono, я не могу дождаться следующего собеседования, на котором меня попросят написать функцию Fibinocci на языке по моему выбору (Mono C#), где я должен указать оговорку, что .NET не будет работать.Ну, вообще-то я могу подождать, так как люблю свою работу.И все же интересно...

Обновление:

Mono на самом деле не выполняет "анонимную" рекурсию, поскольку использует fib как именованный делегат.Моя вина.Тот факт, что компилятор Mono C# предполагает null ценность для fib перед назначением возникает ошибка, как указано ниже.Я говорю "компилятор", потому что .NET CLR запустила бы результирующую сборку просто отлично, даже если компилятор .NET C# не скомпилировал бы код.

Для всех этих нацистов, дающих интервью:

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#.Некоторые могли бы предложить использовать запоминание но, поскольку это все еще медленнее, чем итеративный метод, они могут просто быть придурками.:-)

Однако на данный момент это становится скорее рекламой функционального программирования, чем чего-либо еще (поскольку рекурсивная версия намного приятнее).На самом деле это не имеет никакого отношения к моему первоначальному вопросу, но некоторые ответы показались мне важными.

Это было полезно?

Решение

Это жук в компиляторе Mono.Это нарушает раздел §12.3.3 Закона спецификация.Переменная выдумка не может использоваться в инициализаторе переменной, поскольку она определенно не назначена.

Другие советы

Как я отметил в комментарии выше, если Mono делает это, значит, у них ошибка.В спецификации ясно указано, что это должно быть обнаружено как ошибка.Ошибка, конечно, в основном безвредна и большую часть времени делает то, что вы хотите.Мы рассматривали возможность изменения правил, чтобы сделать такого рода рекурсию законной;по сути, нам пришлось бы добавить особый случай в спецификацию, в котором говорится, что этот узко определенный случай является законным.Однако это никогда не было достаточно высоким приоритетом.

Подробнее об этом читайте в моей статье на эту тему:

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

И, кстати, я бы не стал нанимать никого, кто дал бы мне прямую рекурсивную реализацию fib на собеседовании.Это чрезвычайно неэффективный;время его работы пропорционально размеру его выходных данных, и fib растет экспоненциально.Чтобы сделать это эффективным, используйте рекурсию с запоминанием, или реализовать очевидное итеративное решение.

попробуй это...

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

...Проблема в том, что fib не определен, когда вы пытаетесь использовать его в приведенном выше методе, поэтому статический анализатор сообщает об ошибке компилятора.

Похоже, что в своем волнении я в корне ошибся.Ни .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 просто указывает на текущее определение fib (делегат) и не у себя.Таким образом, Mono на самом деле просто предварительно присваивает значение null к fib во время первоначального присвоения, чтобы это присвоение было действительным.

Я гораздо предпочитаю удобство, заключающееся в том, что мне не нужно объявлять null так что мне действительно нравится такое поведение.Тем не менее, на самом деле это не то, о чем говорится в оригинальной статье.

В компиляторе Microsoft C# это будет работать только в том случае, если вы сначала установите fib к null.

В противном случае это выдаст ошибку, потому что fib используется до того, как оно будет назначено.
Компилятор Mono достаточно "умен", чтобы избежать этой ошибки (другими словами, он нарушает официальную спецификацию).

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top