Работает ли "Анонимная рекурсия" в .NET? Это в моно - PullRequest
Новая
       64

Работает ли "Анонимная рекурсия" в .NET? Это в моно

5 голосов
/ 30 марта 2011

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

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

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

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

Ответы [ 5 ]

7 голосов
/ 30 марта 2011

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

7 голосов
/ 30 марта 2011

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

Чтобы узнать больше об этой проблеме, см. Мою статью на эту тему:

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

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

3 голосов
/ 30 марта 2011

try this ... 

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

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

1 голос
/ 30 марта 2011

Кажется, что в своем волнении я в корне ошибся. Ни .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, поэтому мне нравится такое поведение. Тем не менее, это не совсем то, о чем идет речь в оригинальной статье.

0 голосов
/ 30 марта 2011

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

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

...