Решил протестировать способность Nemerle преобразоовать рекурсию в цикл. Написал простую функцию для вычисления n-го числа Фибоначчи:

using System;
using System.Console;
using Nemerle.Utility;

module Program
{
  Main() : void
  {
    def Fib(num : uint)
    {
      | 0U | 1U => 1 :> ulong
      | n => Fib(n - 1) + Fib(n - 2)
    }  
  
    WriteLine(Fib(100));
    ReadLine();
  }
}

Судя по скорости выполнения никакого преобразования в цикл не произошло (IL не изучал). Аналогичная программа на С# c использованием циклов выполняется мгновенно:

using System;

namespace ConsoleApplication10
{
  class Program
  {
    static void Main(string[] args)
    {
      ulong prev = 1;
      ulong next = 1;

      for (int i = 0; i < 99; i ++)
      {
        ulong tempNext = next;
        next = prev + next;
        prev = tempNext;
      }

      Console.WriteLine(next);
      Console.ReadLine();
    }
  }
}

Скорей всего для вычисления факториала было бы то же самое.

Здравствуйте, igor-booch, Вы писали:

IB>Решил протестировать способность Nemerle преобразоовать рекурсию в цикл. Написал простую функцию для вычисления n-го числа Фибоначчи:
IB> | n => Fib(n — 1) + Fib(n — 2)
IB>Судя по скорости выполнения никакого преобразования в цикл не произошло (IL не изучал).

В цикл преобразуется только хвостовая рекурсия. А это не хвостовая.

Здравствуйте, igor-booch, Вы писали:

<skipped/>

заменитк реализацию на использующую хвостовую рекурсию, и все будет

    private Fib(n : int) : long
    {
        def fib(v, x, y)
        {
            if (v == n)
                x
            else
                fib(v + 1, y, x + y)
        }
        
        fib(0, 1L, 1L)
    }

Здравствуйте, igor-booch, Вы писали:
IB> | n => Fib(n — 1) + Fib(n — 2)

IB>программа на С#
IB> ulong tempNext = next;
IB> next = prev + next;
IB> prev = tempNext;

Программы не эквивалентны.
Про хвостовую тебе уже сказали.

Спасибо, кажется понял.

Неспособность компилятора преобразовать в цикл нехвостовую рекурсию
является просто нереализованной фичей или есть какие-то фундаментальные (теоретические) ограничения? Если есть то какие?
Можно ли автоматически преобразовать нехвостовую рекурсию в хвостовую, а потом в цикл?

Здравствуйте, igor-booch, Вы писали:

IB>Спасибо, кажется понял.

IB>Неспособность компилятора преобразовать в цикл нехвостовую рекурсию
IB>является просто нереализованной фичей или есть какие-то фундаментальные (теоретические) ограничения? Если есть то какие?
Хвостовая рекурсия имеет такое свойство, что после рекурсивого вызова состояние локальных переменных не используется, поэтому оно может быть отброшено. Это позволяет не выполнять вызов рекурсивно, а заменить текущее состояние локальных переменных на то, которое бы они приняли будь такой вызов произведен, и просто передать управление на начало алгоритма.
Если локальные переменные нужны после рекурсивного вызова, то есть в случае нехвостовой рекурсии, то их пришлось бы сохранять и потом востанавливать, а это как раз то, что и так за нас делает любой вызов функции.

Здравствуйте, igor-booch, Вы писали:
IB>Можно ли автоматически преобразовать нехвостовую рекурсию в хвостовую, а потом в цикл?
Да. Например, с помощью т.н. cps-преобразования. Такое преобразование выполняют многие компиляторы scheme. Но там на то немного другие причины.
Однако простейшие преобразования не могут изменить space complexity. Т.е. если у тебя был факториал без хвостовой рекурсии с O(n) по памяти — то после cps O(n) никуда не денется.
Чтобы автоматически улучшать O(что-то) (например, чтобы переписать "неправильный" нехвостовой факториал на хвостовой вариант с аккумулятором) нужно не только распознавать такие вот "неправильные" функции, но и знать свойства выполняемых этими функциями операций. Подобную оптимизацию умеют всякие умные компиляторы (недавно был тред, где наблюдалась такая способность у gcc).

IB>Неспособность компилятора преобразовать в цикл нехвостовую рекурсию
IB>является просто нереализованной фичей или есть какие-то фундаментальные (теоретические) ограничения? Если есть то какие?
Если хитрых оптимизаций в компиляторе не реализовано, то простые тогда ни к чему. Сделаешь, например, cps-преобразование — и вместо роста стека вызовов получишь растущую функцию-континуацию. Шило на мыло.
За тем, чтобы рекурсия была хвостовой, там, где это необходимо (где нужно O(1) по памяти), обязан следить сам программист. Например, твоя реализация Фибоначчи на Nemerle имеет экспоненциальную сложность по памяти (сравни с константной на шарпе). Ну куда это годится?

Здравствуйте, igor-booch, Вы писали:

IB>Спасибо, кажется понял.

IB>Неспособность компилятора преобразовать в цикл нехвостовую рекурсию
IB>является просто нереализованной фичей или есть какие-то фундаментальные (теоретические) ограничения? Если есть то какие?
IB>Можно ли автоматически преобразовать нехвостовую рекурсию в хвостовую, а потом в цикл?

Можно, но в данном случае это не поможет — хвостовая рекурсия сэкономит стек, но для x = Fib(N) все равно понадобится примерно Fib(N) вызовов функции. Можно запоминать промежуточные результаты, как в вашей итеративной версии — тогда и с рекурсией будет очень быстро: N вызовов вместо Fib(N).

Здравствуйте, z00n, Вы писали:

Z>Можно, но в данном случае это не поможет — хвостовая рекурсия сэкономит стек, но для x = Fib(N) все равно понадобится примерно Fib(N) вызовов функции.

Можно написать алгоритм, имеющий сложность по времени O(Log(N)).

MC> Например, твоя реализация Фибоначчи на Nemerle имеет экспоненциальную сложность по памяти

По времени сложность тоже экспонентциальная:



Непонимаю почему, как на 50 простых рекурсивных вызовов может требоваться 15 (!) минут. Кто-нибудь может объяснить? Что происходит в районе 45 числа? Почему зависимость экспонетциальная?



Вот программа с помощью которой строился график:

using System;
using System.Console;
using Nemerle.Utility;

module Program
{
  Main() : void
  {
    def Fib(num : uint)
    {
        | 0U | 1U => 1 :> ulong
        | n => Fib(n - 1) + Fib(n - 2)
    }  
    
    mutable fibStatistics : string;
    mutable fibStatisticsLine : string;
    mutable startTicks : Int64;
    mutable finishTicks : Int64;
    
    for (mutable i = 0U; i <= 60; i++)
    {
        startTicks = DateTime.Now.Ticks;
        mutable fib = Fib(i);
        finishTicks = DateTime.Now.Ticks;
        
        
        fibStatisticsLine = string.Empty;
        fibStatisticsLine = fibStatisticsLine + i.ToString() + " ";
        fibStatisticsLine = fibStatisticsLine + fib.ToString() + " ";        
        fibStatisticsLine = fibStatisticsLine + (finishTicks - startTicks).ToString() + " ";   
        
        WriteLine(fibStatisticsLine);
        
        fibStatistics = fibStatistics + fibStatisticsLine + System.Environment.NewLine;    
    }
    
    ReadLine();
  }
}

Здравствуйте, igor-booch, Вы писали:
IB>По времени сложность тоже экспонентциальная:
Потому что ты такой алгоритм написал:
IB> | n => Fib(n — 1) + Fib(n — 2)
fib(n) = fib(n-1) + fib(n-2) = [fib(n-2) + fib(n-3)] + [fib(n-3) + fib(n-4)] = ...
Заметь, что fib(n-3) раздвоился. Т.е. алгоритм делает кучу повторных вычислений.

Да уж, в очередной раз разочаровлся в функциональном программировании. Его продвигатели говорят, что функциональному программисту достаточно переписать на функциональный язык математематическое определение (то есть ответ на вопрос "Что нужно сделать?"), а компилятор сам сам определит "Как это сделать?", то есть сгенирует алгоритм. На практике получается если например перевести на функциональный язык математическое определение чесел Фибоначчи, генерируется тупой алгоритм и нужно думать как наставлить компилятор функционально языка на путь истинный. Не легче сразу использовать императивный язык и быть уверенным в том, что компилятор сделает то, что задумал программист?
Кто-нибудь сталкивался ещё с такими случаями когда по программе на ФЯ, представляющей собой математическое определение, генирится какой-нибудь плохой алгоритм?

Да уж, в очередной раз разочаровлся в функциональном программировании. Его продвигатели говорят, что функциональному программисту достаточно переписать на функциональный язык математематическое определение (то есть ответ на вопрос "Что нужно сделать?"), а компилятор сам сам определит "Как это сделать?", то есть сгенирует алгоритм. На практике получается если например перевести на функциональный язык математическое определение чесел Фибоначчи, генерируется тупой алгоритм и нужно думать как наставлить компилятор функционально языка на путь истинный. Не легче сразу использовать императивный язык и быть уверенным в том, что компилятор сделает то, что задумал программист?
Кто-нибудь сталкивался ещё с такими случаями когда по программе на ФЯ, представляющей собой математическое определение, генирится какой-нибудь плохой алгоритм?

Здравствуйте, igor-booch, Вы писали:
IB>Его продвигатели говорят, что функциональному программисту достаточно переписать на функциональный язык математематическое определение (то есть ответ на вопрос "Что нужно сделать?"), а компилятор сам сам определит "Как это сделать?", то есть сгенирует алгоритм.
Ни разу такого не слышал.

IB>компилятор сам сам определит "Как это сделать?", то есть сгенирует алгоритм.
Это не всегда возможно. Например, функция Fib могла производить побочный эффект, поэтому компилятор не имеет права мемоизировать значения Fib(n) и потом повторно их использовать. По крайней мере — в nemerle, где наличие побочного эффекта никак не декларируется (сравни с хаскелем). Впрочем, и хаскель тоже автоматически не особо ничего не мемоизирует — в компиляторе сложно угадывать, нужно ли сохранять вычисленные значения или нет — такие такие вещи программист должен определять сам.

Здравствуйте, igor-booch, Вы писали:

IB>Да уж, в очередной раз разочаровлся в функциональном программировании. Его продвигатели говорят, что функциональному программисту достаточно переписать на функциональный язык математематическое определение (то есть ответ на вопрос "Что нужно сделать?"), а компилятор сам сам определит "Как это сделать?", то есть сгенирует алгоритм. На практике получается если например перевести на функциональный язык математическое определение чесел Фибоначчи, генерируется тупой алгоритм и нужно думать как наставлить компилятор функционально языка на путь истинный. Не легче сразу использовать императивный язык и быть уверенным в том, что компилятор сделает то, что задумал программист?
IB>Кто-нибудь сталкивался ещё с такими случаями когда по программе на ФЯ, представляющей собой математическое определение, генирится какой-нибудь плохой алгоритм?

Ещё один классический пример — quicksort на Хаскелле, который описывается очень коротко:

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

Но имеет плохие показатели при практическом использовании.

К сожалению, использование императивных языков дает лишь ложную уверенность в том, что компилятор сделает то, что задумал программист, с максимальной эффективностью. Как пример приведу обход прямоугольного массива в C и Паскале. В обоих языках это реализуется вложенным циклом. Но в одном языке во внутреннем цикле эффективнее «накручивать» первый индекс массива a[inner, outer], а в другом — второй: a[outer, inner]. Если вы о таких тонкостях не знаете, вам будет сложно найти в коде обхода проблему.

APL — функциональный язык программирования, известный своей лаконичностью. В нём явное использование оператора цикла является плохим программистким тоном. Во время исполнения интерпретатор выбирает наилучшую реализацию той или иной функции, рассчитанную именно на тот тип данных, над которым проводится операция. В результате, интерпретированные «однострочники» над динамично типизированными данными не уступают по эффективности аналогичным программам на С, не говоря уже о наследниках APL (например, J или K), которые ещё и автоматически распараллеливают вычисления.

Здравствуйте, Mr.Cat, Вы писали:

MC>Здравствуйте, igor-booch, Вы писали:
IB>>Его продвигатели говорят, что функциональному программисту достаточно переписать на функциональный язык математематическое определение (то есть ответ на вопрос "Что нужно сделать?"), а компилятор сам сам определит "Как это сделать?", то есть сгенирует алгоритм.
MC>Ни разу такого не слышал.

Насколько я понимаю, главный принцип декларативного программирования заключается в том, что программист декларирует в программе результат, который должен быть достигнут, не указывая (не приказывая) компилятору как должен быть достигнут результат (то есть алгоритм достижения результата). В императивном программировании программист приказавает (как император) компилятору как должен быть достигнут результат, то есть описывает алгоритм решения. При этом компилятор просто выполняет приказы программиста и ничего не знает о что будет достигнуто в рзультате выполнения этих приказов.
Именно этим отличием меня и привлекло декларативное программирование, но получается что этот принцип на практике до конца не реализуется.



MC>Это не всегда возможно. Например, функция Fib могла производить побочный эффект, поэтому компилятор не имеет права мемоизировать значения Fib(n) и потом повторно их использовать. По крайней мере — в nemerle, где наличие побочного эффекта никак не декларируется (сравни с хаскелем). Впрочем, и хаскель тоже автоматически не особо ничего не мемоизирует — в компиляторе сложно угадывать, нужно ли сохранять вычисленные значения или нет — такие такие вещи программист должен определять сам.

Почему сложно угадывать? Если функция продекларирована как чистая, и вызывается два раза с одними и теме же параметрами, то второй раз её значение можно не расчитывать. Кстати почему в это не делается в хаскеле и почему в nemercle нелязя декларировать чистоту функций?

Здравствуйте, igor-booch, Вы писали:

IB>Почему сложно угадывать? Если функция продекларирована как чистая, и вызывается два раза с одними и теме же параметрами, то второй раз её значение можно не расчитывать. Кстати почему в это не делается в хаскеле и почему в nemercle нелязя декларировать чистоту функций?

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

Допустим, у нас есть чистая функция вычисляющая длину вектора и мы хотим обработать ей несколько гигов данных. Если эта функция начнёт запоминать результаты, то у нас просто кончится память.

Don't save anything you can calculate.

Здравствуйте, igor-booch, Вы писали:

IB>Здравствуйте, Mr.Cat, Вы писали:

MC>>Здравствуйте, igor-booch, Вы писали:
IB>>>Его продвигатели говорят, что функциональному программисту достаточно переписать на функциональный язык математематическое определение (то есть ответ на вопрос "Что нужно сделать?"), а компилятор сам сам определит "Как это сделать?", то есть сгенирует алгоритм.
MC>>Ни разу такого не слышал.

IB>Насколько я понимаю, главный принцип декларативного программирования заключается в том, что программист декларирует в программе результат, который должен быть достигнут, не указывая (не приказывая) компилятору как должен быть достигнут результат (то есть алгоритм достижения результата). В императивном программировании программист приказавает (как император) компилятору как должен быть достигнут результат, то есть описывает алгоритм решения. При этом компилятор просто выполняет приказы программиста и ничего не знает о что будет достигнуто в рзультате выполнения этих приказов.
IB>Именно этим отличием меня и привлекло декларативное программирование, но получается что этот принцип на практике до конца не реализуется.
Именно так, только никто вам не обещает, что реализация будет лучше написанной вручную. Ручной асм тоже не сразу обогнали. Главное, чтобы вы всё-таки могли реализацию переписать на более эффективную, если это потребуется.

IB>Почему сложно угадывать? Если функция продекларирована как чистая, и вызывается два раза с одними и теме же параметрами, то второй раз её значение можно не расчитывать.
Вы на этапе компиляции можете узнать, что функция вызывается с одинаковыми аргументами? Я не про примитивную функцию, разумеется.
Если вы предлагаете мемоизировать всё, то вы меняете время на память. Только время у нас растяжимо, а память будет такими функциями пожираться постоянно.
Конкретную функцию вы можете мемоизировать вручную и без особых проблем.

IB>Кстати почему в это не делается в хаскеле и почему в nemercle нелязя декларировать чистоту функций?
Это не делается хотя бы потому, что эффект будет лишь в частных случаях, а зазря анализировать и тратить время компиляции — зачем?

Здравствуйте, igor-booch, Вы писали:

IB>Насколько я понимаю, главный принцип декларативного программирования заключается в том, что программист декларирует в программе результат, который должен быть достигнут, не указывая (не приказывая) компилятору как должен быть достигнут результат (то есть алгоритм достижения результата). В императивном программировании программист приказавает (как император) компилятору как должен быть достигнут результат, то есть описывает алгоритм решения. При этом компилятор просто выполняет приказы программиста и ничего не знает о что будет достигнуто в рзультате выполнения этих приказов.
IB>Именно этим отличием меня и привлекло декларативное программирование, но получается что этот принцип на практике до конца не реализуется.

Мое мнение — компиляторы пока недостаточно умны для таких задач.

Здравствуйте, VoidEx, Вы писали:

IB>>Почему сложно угадывать? Если функция продекларирована как чистая, и вызывается два раза с одними и теме же параметрами, то второй раз её значение можно не расчитывать.
VE>Вы на этапе компиляции можете узнать, что функция вызывается с одинаковыми аргументами? Я не про примитивную функцию, разумеется.
VE>Если вы предлагаете мемоизировать всё, то вы меняете время на память. Только время у нас растяжимо, а память будет такими функциями пожираться постоянно.
VE>Конкретную функцию вы можете мемоизировать вручную и без особых проблем.

Меморизация результатов вычисления функций можно повесить на среду выполнения, наподобии CLR у NET или VM у java. Среда выполнения может в зависимости от объёмы выделенной памяти принимать решении о меморизации результатов вычисления функций. Почти то же самое делает системный кэш Windows: дисковые данные, к которым производится частое обращение записываются в память. Объем этих данных зависит от объёма физической памяти.

Кстати кто-нибуть встречал компиляторы декларативных языков, генерирующие код для исполнения в средах выполнения?


IB>>Кстати почему в это не делается в хаскеле и почему в nemercle нелязя декларировать чистоту функций?
VE>Это не делается хотя бы потому, что эффект будет лишь в частных случаях, а зазря анализировать и тратить время компиляции — зачем?

На мой взгляд декларация чистоты может дать многое:
1. Разлиные оптимизации, в том числе оптимизация о которой мы говорим
2. Автоматическое распараллерирование
3. Упрощение и автоматизация тестирования
То есть мы сможем все преимущества функциональных языков, о которых говорится в статье: http://www.rsdn.ru/article/funcprog/fp.xml

Автор(ы): Вячеслав Ахмечет
Дата: 16.09.2006
Данная статья достаточно кратко и вполне доступно, используя примеры на Java (!), знакомит читателя с базовыми понятиями функционального программирования.

.

Программист должен стремиться к тому чтобы как можно больше кода было чистым. Декларация чистоты отделяет чистый код от нечистого. А так получается, что всё смешивается и мы не можем задействовать преимущества функциональных языков.

Кто-нибудь встречал императивно-декларативные языки с декларацией чистоты?