Пользователь
0,0
рейтинг
21 мая 2012 в 13:25

Разработка → F# Хвостовая рекурсия. Подводные грабли. Часть 1


Винни Пух: Ой, что это случилось с твоим хвостом?
Иа: А что с ним могло случится?
Винни Пух: Его нет.
Иа: Ты не ошибся?
Винни Пух: Хвост или есть или нет совсем! Тут нельзя ошибиться.
Иа: А что же тогда там есть?
Винни Пух: Ничего!


У нас в проекте, в одном из серверных компонентов, после очередного рефакторинга начала течь память. Казалось бы .NET, F#, менеджед код, сборка мусора, все дела, но память, куда-то утекала. Ценой бессонных ночей и попорченных нервов, источник утечки был найден. Оказалось что проблема вызвана куском кода, который был, чуть ли не один к одному скопирован из учебника по F#.

Все дело было в хвостовой рекурсии, вернее, как оказалось в ее отсутствии в неожиданных местах.

Хвостовая рекурсия


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

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

Хвостовая рекурсия это частный случай рекурсии, когда рекурсивный вызов может быть заменен итерацией. С одной стороны на совести программиста остается написание логики в «хвостовом» стиле, с другой стороны компилятор тоже должен «обнаружить» хвостовую рекурсию и раскрутить рекурсию в итерацию.

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

Давайте рассмотрим первый такой случай и сформулируем правило, с помощью которого можно избежать «неприятностей».

Давайте, для начала возьмем простую функцию, которая суммирует числа все числа от одного до N:
let rec sum i =
    if i <= 0L then 0L
    else i + sum (i - 1L) 

> sum 10L;;
val it : int64 = 55L

Все хорошо, за исключением одной момента. Если мы попробуем посчитать сумму хотя бы для 100000, то получим в лоб StackOverflowException. Т.е. у нас банально не хватило стека для вычислений:
> sum 100000L;;

Process is terminated due to StackOverflowException.

Ответ на эту проблему, использование аккумулятора, как аргумента рекурсивной функции:
let sumTailRec i =
    let rec loop acc i =
        if i <= 0L then acc
        else loop (acc + i) (i - 1L) 
    loop 0L i

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

Проиллюстрировать порядок вычисления (для аргумента 5) можно так. Без хвостовой рекурсии:
sum: 5 + (4 + (3 + (2 + (1 + (0))))) – тут мы идем сначала в одну сторону, а потом, дойдя до нуля возвращаемся и суммируем. Как раз для того чтобы возвращаться и нужен стек.

С хвостовой рекурсией:
sumTailRec: (((0 + 5) + 4) + 3) + 2) + 1) – здесь, мы идем только в одну сторону, и ответ у нас накапливается в аккумуляторе, поэтому собственно стек нам и не нужен.

Новая функция уже может переварить сколь угодно большое число (пока хватит разрядности int64).
> sumTailRec 10000000L;;
val it : int64 = 50000005000000L

Теперь, давайте немного напишем более обобщенную функцию, которая суммирует не сами числа, а результат некоторой заданной функции от текущего числа.
let sumFTailRec f i =
    let rec loop acc i =
        if i <= 0L then acc
        else loop (acc + f i) (i - 1L) 
    loop 0L i

В новой версии у нас появился еще один параметр – функция, результат вычисления которой нужно суммировать. Вот вариант, который суммирует сами числа:
> sumFTailRec (fun i -> i) 10000000L

val it : int64 = 50000005000000L

А вот, который суммирует квадраты:
> sumFTailRec (fun i -> i*i) 10000000L

val it : int64 = 1291990006563070912L

Пока все хорошо. Но есть небольшой нюанс, функция которая передается, может «кинуть» исключение. Вот пример:
> let someProblemFun i = i/((i+1L) % 1000L)

> sumFTailRec someProblemFun 10000000L

System.DivideByZeroException: Attempted to divide by zero.
Stopped due to error

Проблема


При значении i = 999, у нас возникает деление на ноль. Предположим, что мы хотим при исключении, не аварийно завершать вычисление, а просто игнорировать проблемный элемент. Нам понадобится обработка исключения. Само собой напрашивается вполне логичное и ожидаемое решение:
let sumFTailRecWithTry f i =
    let rec loop acc i =
        if i <= 0L then acc
        else
            try 
                loop (acc + f i) (i - 1L) 
            with 
                exc -> 
                    printfn "exn raised:%s" exc.Message
                    loop acc (i - 1L) 
    loop 0L i

Итак пробуем:
> sumFTailRecWithTry someProblemFun     10000L

exn raised:Attempted to divide by zero.
...
exn raised:Attempted to divide by zero.
val it : int64 = 351405L

Результат получили, исключения отловили, вроде все нормально. Теперь пробуем скормить более серьезное число:
> sumFTailRecWithTry someProblemFun 10000000L

exn raised:Attempted to divide by zero.
...
exn raised:Attempted to divide by zero.

Process is terminated due to StackOverflowException.

Упс… В чем же дело? На первый взгляд у нас функция с хвостовой рекурсией, почему вдруг закончился стек?

Как можно догадаться, проблема в конструкции try … with. Дело в том, что если рекурсивный вызов выполняется в блоке try, то у хвостовой рекурсии «отваливается» хвост, и она становится обычной рекурсией. Почему? Потому что в любом из последующих рекурсивных вызовов loop, теоретически может выпасть исключение, а т.к. нам надо его будет обработать, то нужно запомнить в стеке место, куда нужно вернуться при «выпадении» исключения.

Решение


Какой из такой неприятной ситуации выход? Очень простой, не нужно оборачивать рекурсивный вызов блоком try… with, ведь исключение мы ожидаем только при вызове «внешней» функции f, значит оборачивать нужно только этот вызов:
let sumFReallyTailRecWithTry f i =
    let rec loop acc i =
        if i <= 0L then acc
        else
            let fRes = 
                try f i
                with exc ->
                    //printfn "exn raised:%s" exc.Message
                    0L
            loop (acc + fRes) (i - 1L) 
    loop 0L i

Пробуем:
> sumFReallyTailRecWithTry someProblemFun 10000000L
val it : int64 = 374200932236L

Вуаля! Стека на этот раз хватило, вернее он остался не тронутый.

Итак, правило: никогда не помещайте хвостовой вызов в блок try… with.

Во второй серии будут шокирующие разоблачения касающиеся хвостовой рекурсии для async { … } и MailboxProcessor.
Артем Присяжнюк @temaHT
карма
25,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (67)

  • +1
    И вообще, бросать и ловить собственные исключения что классу, что функции — неправильно.
    • 0
      Насчет дотнета соглашусь. Ибо в дотнете, во первых, исключение — это исключение. А во вторых механизм исключений довольно тормознутый. Но есть языки где исключения, один из механизмов control flow.
      К примеру, OCaml (папа F#) — там исключения рассматривается как нормальная практика построения логики. Не могу сказать что мне такой подход по душе, но тем не менее.
  • +3
    Я далёк от F# и функционального программирования вообще, но код

    let rec sum i =
        if i <= 0L then 0L
        else i + sum (i - 1L)
    

    мне кажется простым и лаконичным, а код, оптимизированный под хвостовую рекурсию

    let sumFTailRec f i =
        let rec loop acc i =
            if i <= 0L then acc
            else loop (acc + f i) (i - 1L) 
        loop 0L i
    

    выглядит напичканным советами для компилятора. Нельзя как-то переписать код в стиле первого куска, чтобы компилятор догадался до цикла сам? Условия, вызовы, параметры переставить местами или ещё какой-нибудь ахалай-махалай сотворить? Красота же теряется.
    • +1
      Как то так:
      let sumTailRec acc i =
              if i <= 0L then acc
              else sumTailRec (acc + i) (i - 1L) 
      

      Вызов:
      > sumTailRec 0L i
      

      Нюанс такой, что в таком более кратком варианте, у функции появляется дополнительный параметр — аккумулятор. В данном случае, это даже полезно, ибо мы можем пробрасывать начальное значение. Но очень часто, аккумулятор нет смысла показывать наружу, поэтому организуется внутренний цикл — функция loop, которая работает с аккумулятором.
      Кроме того когда в функции более 5-ти строк, то эффект не такой драматический, как в данном случае когда размер кода увеличился почти на 100% :-)
      • +1
        Можно сделать так (по крайней мере в ocaml):
        let rec sumTailRec ?(acc=0) i =
            if i <= 0 then acc
            else sumTailRec ~acc:(acc+i) (i-1);;
        

        И вызывать:
        # sumTailRec 5;;    
        - : int = 15
        # sumTailRec ~acc:5 5;;
        - : int = 20
        • 0
          Не сыпте соль на рану. К сожалению в таком виде как в камле, опциональных параметров в F# нету.
          • 0
            Не переживайте, в окамле зато нельзя сделать «OL + 1L».
            • 0
              Я в курсе, я лет пять на окамле сидел. Но это меня не сильно напрягало, но к опциональным параметрам, привязался… :-)
      • 0
        поэтому стоит просто создать вторую функцию с одним аргументом путем частичного применения нуля на первое место ;)
    • +1
      Нет, нельзя. В идеале хотелось бы, чтобы оптимизатор сам определял, как преобразовать исходный вариант в функцию с хвостовой рекурсией. А на деле оказывается, что эта задача в общем случае является неразрешимой, потому в реальной жизни разворачивание рекурсии в хвостовую перекладывают на плечи программистам. Но на самом деле, программистам оно нафиг не надо, потому что тот же пример можно переписать как-то так:

      let sumFirst n = foldl (fun a b -> a + b) 0 [1..n]
      


      Впрочем, я недостаточно хорошо помню F#. Может, там прокатит трюк с заменой fun a b -> a + b на (+)

      А вообще, можно и так:

      let sumFirst n = sum [1..n]
      


      или даже так:

      let sumFirst n = (n + 1) * n / 2
      
  • –2
    Решение: используйте C# вместо F#

    Если не секрет, а где вы используйте F#, где он удобнее чем императивные языки программирования? Просто первый раз вижу, чтобы им кто-то пользовался в коммерческих целях.
    • 0
      Ой, в первой строчке парсер съел тег «sarcasm» :)
    • 0
      Не секрет, используем здесь.

      Чем удобней? А вы не задумывались откуда в C# генерики, лямбды, LINQ?

      Будем первыми :-). Но на самоом деле все хорошо с коммерческим ииспользованием. Так на вскидку — 2008 год. Сейчас если погуглить, то можно найти массу примеров.
      • 0
        >откуда в C# генерики
        от шаблонов С++, нет?
        • 0
          Нет.

          Starting with Microsoft in 1998, Don also created Generics in C# and in the .NET Common Language Runtime. He has been a functional programmer since 1989.

          Don Syme — автор F#

        • 0
          От шаблонов С++ там только элементы синтаксиса.
          • 0
            Извините, я не вижу принципиальных отличий шаблонов С++ от дженериков С#. Не могли бы Вы просветить меня?
            • +3
              Если в одном предложении — то темлейты это система макросов работающая во время компиляции, а генерики это полноценные классы с поддержкой рантайма. Как сказал Один известный дядя:

              Anders Hejlsberg: To me the best way to understand the distinction between C# generics and C++ templates is this: C# generics are really just like classes, except they have a type parameter. C++ templates are really just like macros, except they look like classes.

              Ну и более Подробно.
              • +1
                Ну и я бы добавил, что благодаря рантайму доступны специфичные фичи — msdn.microsoft.com/en-us/library/ee207183.aspx

                Не говоря уже про рефлекшн.
            • 0
              Основное отличие в том, что дженерики C# используют строгую типизацию и не дают доступа к статическим членам, а шаблоны C++ используют утиную типизацию, дают доступ к статическим членам, а также поддерживают переопределение для частных случаев.
  • –3
    Вообще сколько мне не говорили про рекурсию, что код при ней становится более красивым и легких для восприятия, по факту ее вообще стоит почти всегда избегать, потому что памяти потребляет больше, а производительность меньше.
    • 0
      Ну так это C#, в котором, насколько я помню, как раз компилятор ничего не знает про хвостовую рекурсию. Поэтому и память жрется, и глубина вложенности ограничена.
    • +1
      Ну, если хвостовая рекурсия трансформируется в итерацию, то и производительность не теряется, разве не так?
      • –1
        Возможно. Но хотелось бы увидеть тесты для F#.
    • +1
      Существуют рекурсивные структуры данных и, соответственно, алгоритмы работы с ними. Зачем изголяться и изобретать итерацию там, где есть рекурсия? В функциональных языках, где реализована нормальная рекурсия, проблем с производительностью быть не должно.
      • 0
        >> В функциональных языках, где реализована нормальная рекурсия, проблем с производительностью быть не должно.

        Интересно. Но все равно хотелось бы увидеть тесты на F#, особенно для более сложных случаев, чем факториал или числа Фибоначчи.
    • 0
      Уже немного оффтоп.
      Меня всегда интересовал вопрос: существуют ли такие программы для преобразования рекурсивных методов в итеративные и наоборот на уровне кода, возможно используя ANTLR, Gold Parser и другие генераторы парсеров? Было бы интересно с теоретической точки зрения их посмотреть.
      Ведь любая рекурсия может быть преобразована в итерацию, даже не хвостовая.
      • +1
        > Ведь любая рекурсия может быть преобразована в итерацию, даже не хвостовая.

        Ну да. Путем явного создания вспомогательного стека :)
        Видел я подобное в школьном учебнике по Паскалю.
        var
          stack : array [1..maxstack] of TStackFrame;
        

        и прочий ужас.

        Существуют алгоритмы, которые принципиально невозможно реализовать в итеративной форме (в основном это dfs и обработка деревьев). Да, они могут быть переписаны с использованием вспомогательного стека или при помощи модификации структуры данных, и это будет даже аккуратнее чем ужас выше, но это уже будет другой алгоритм.
        А все формальные методы не дадут выигрыша в результате преобразования.
        • 0
          Ерунда! Я писал и могу сейчас написать без стека DFS. O(1) по памяти и O(1) (амортизированно) по времени к переходу на следующий узел.
          • 0
            А ваш dfs реентерабельный?
            Рекурсивный алгоритм — да.
            • 0
              Да. Вот код: pastebin.com/pJt3pUDf
              Это симметричный обход дерева (ну все как обычно, структура — узел + указатели на детей и родителя). Да, это не DFS, родитель возвращается после левого ребенка, но до правого, но понятное дело, что это легко исправить. Задача была в симметричном.

              Никаких статических данных, побочных эффектов и так далее.

              На деле мне для итератора нужен 1 указатель — текущего узла. Указатели на самого левого сына дерева и самого правого нужны для проекта, но не этого класса, их можно игнорировать.

              Основная идея вот в чем: если у текущего узла есть левый сын — в него идти не надо, ибо мы были в нем раньше (иначе нарушен правильный порядок). Если есть правый сын — идем сначала в него, а потом спускаемся по левым детям. Если правого сына нет — поднимаемся по родителям пока узел является правым сыном.

              Кажется все описал, может что-то и забыл — посмотрите в коде. Он 100% рабочий, протестирован десятком разных задачек.
              • +1
                Спасибо, я знаю этот алгоритм.

                Проблема в том, что это — симметричный обход дерева, а не dfs.
                DFS — это обход графа, вообще-то.
                • 0
                  Ах, не подумал, да, признаю ошибку. Обычно первое что приходит в голову это частный случай в виде дерево. Тогда или рекурсия или с доп памятью, наверное — не реализовывал, не знаю.

                  Правда на практике я бы не обходил граф рекурсивно. Ведь дерево обычно балансируется и глубина рекурсии — логарифм. А значит для дерева даже с 2**32 узлов глубина стека будет порядка 32. А даже если каждый бит 1 узел и дерево содержит 2**64 узлов — всего 64, что ерунда.

                  А вот у графов нет никакой балансировки и там можно переполнение стека словить. Возможно, хвостовая рекурсия и спасет, но это надо по коду смотреть.
                  • 0
                    > А значит для дерева даже с 2**32 узлов глубина стека будет порядка 32.
                    Маленькая поправка: так ни одно дерево не балансируется. Реальная оценка глубины — 64.

                    По поводу графов: хвостовой рекурсией тут не обойтись. Классическое решение проблемы с переполнением стека — выделение вспомогательного стека в куче.
                    • 0
                      >> Маленькая поправка: так ни одно дерево не балансируется. Реальная оценка глубины — 64.
                      Это понятно. Речь шла о порядках, константы не в счет, а они небольшие. Для КЧД — 2, например.

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

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

                        Была еще небольшая статья на Хабре на эту тему.
                        • 0
                          Ну, если вы считаете катоморфизм простым и понятным кодом, то да, в ФП эта проблема, можно сказать, решена.

                          И не надо тут говорить про автоматическую генерацию катаморфизмов — ее даже Haskell не делает. )
                          • 0
                            >> Но тут сразу код жуткий.

                            Ключевая фраза.

                            Если мы говорим о достаточно сложных рекуррентных алгоритмах, то всяко лучше катоморфизм нежели императивный путь.

                            Чудес, к сожалению не бывает. Но зато после достаточно долго курения катаморфизма, часто наступает просветление.
              • 0
                Самое интересное это методы operator++ и operator--. Это переход на следующий и предыдущий узлы соответственно. Все что выше них — это всякое служебное. Все что ниже — собственно переход по узлам как я описал в предыдущем комментарии.

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

                То есть рекурсивное сразу жадно все обходит, а итерратор — лениво. При этом сделать из ленивого жадный — дело одного цикла, а вот обратное — сомневаюсь, что выполнимо.
                • 0
                  Обратное вполне выполнимо, например при помощи микронитей. Правда, CLR всячески сопротивляется принудительному переключению контекста, но в C# есть генераторы, а это еще лучше.

                  А по поводу вашего алгоритма я уже написал выше.
                  • 0
                    (долбанные 5 минут, разговор растягивается на часы)

                    Генератор — это yield? Да, это сказка, итераторы в разы проще писать. Это как раз пример, когда и код простой и, чуть-чуть поправив, компилятор сделает хороший результат. В джаве и плюсах их очень сильно не хватает. При том, что реализовать их подержку в компиляторе при имеющихся замыканиях — совсем не сложно. Контекст уже умеем сохранять, анонимный локальный класс тоже. Но похоже совсем этого не дождемся. На следующий стандарт запланировано сильное расширение стандартной библиотеки, а фич, считается, что и так достаточно.
                    • 0
                      Не сказал бы, что это — очень простая фича.
                      В генераторах главная проблема — не замыкания, а автоматическое преобразование кода из структурного в автоматный.

                      Кстати, полностью эту проблему так и не решили.
                      В C# до сих пор нельзя писать yield и await внутри блоков catch и finally. А еще нельзя писать yield внутри блока try, для которого указан finally. Меня постоянно раздражают эти ограничения…
                      • 0
                        *А еще нельзя писать yield внутри блока try, для которого указан catch
                      • 0
                        Автоматный, что?
                        Под yield скрывается нечно большее, чем сохранение контекста (значений переменных и номера строки, или на уровне асма — вершины стека (или регистров) и IP, SP?

                        Ну положим, почему в catch нельзя писать это понятно. Пошла раскрутка стека и не до выхода уже. А вот почему в try с имеющимся catch — сходу не соображу, несмотря на то, что неплохо себе представляю обработку исключений на уровне CIL-кода.

                        Расскажите поподробнее, пожалуйтса, или ссылочку бы…
                        • 0
                          > Автоматный, что?
                          Различают четыре парадигмы программирования — автоматную, структурную, объектно-ориентированную и функциональную (парадигмы не являются чем-то, жестко зависимым от языка; на любом языке можно писать, используя любую комбинацию парадигм).

                          Код метода-генератора является, по сути, структурным кодом (хотя он и может обращаться к другим объектам, но эти обращения сводятся просто к вызовам сторонних подпрограмм и не подлежат преобразованию).

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

                          Маленькое замечание: я не говорю «конечный автомат», так как получившийся автомат, строго говоря, конечным не является.

                          > Под yield скрывается нечто большее, чем сохранение контекста?

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

                          А именно,
                          1) Создается новый класс, реализующий IEnumerable<> и IEnumerator<>
                          2) Все локальные переменные и аргументы переносятся в этот класс как поля
                          3) Вводятся новые переменные (назовем их state и current).
                          4) Весь код метода превращается в один гигантский switch (state). При этом выражение yield return foo; превращается в
                          state = ...;
                          current = foo;
                          return true;
                          

                          5) Отдельного слова стоит обработка ошибок — каждый блок try...finally генерирует, помимо собственно блока try...finally, дополнительный switch, а также новый метод.

                          > Расскажите поподробнее, пожалуйтса, или ссылочку бы…
                          Могу порекомендовать способ самостоятельных исследований:
                          1) скачиваем ILSpy;
                          2) открываем в нем исходники System.Linq.Enumerable из библиотеки System.Core;
                          3) переключая настройку «decompile enumerators (yield return)» сравниваем код стандартный методов Linq с использованием yield и преобразованный;
                          4) также можно писать свои генераторы и декомпилировать их.
                          • 0
                            Про существование парадигм я знаю. Не знал про преобразование в автоматную, спасибо за ликбез.

                            Все равно не понимаю, почему не MSIL не может запомнить просто номер (адрес) инструкции (ну и возможно состояние верхушки стека от текущей фукнции) и нужен свитч.

                            Но я больше с++-разработчик. Там все в асм генерится. И регистры (в том числе SP/IP) там сохранить не проблема.

                            • 0
                              Наверное ответ на мой вопрос состоит в том, что решение, описанное выше (применяемое в MSIL) — высокоуровневое. Оно не опирается на особенности CIL-кода (отстуствие регистров, стек вычислений), а использует генерацию, доступную в языке — мы сами руками можем написать такой же класс с полями и добавить swtich. То есть yield выступает этаким высокоуровневым макросом, а не фичей языка.
                            • 0
                              > Все равно не понимаю, почему не MSIL не может запомнить просто номер (адрес) инструкции (ну и возможно состояние верхушки стека от текущей фукнции) и нужен свитч.

                              Потому что MSIL — компилируемый язык, и такой вещи, как номер текущей инструкции, в природе не существует. Можно было бы расширить JIT компилятор, но в Microsoft предпочли переложить эту задачу на компилятор более высокого уровня, поскольку это проще.

                              > Но я больше с++-разработчик. Там все в асм генерится. И регистры (в том числе SP/IP) там сохранить не проблема.

                              Да, не проблема. Но не настолько, как кажется поначалу.
                              Сохранять (E)SP — не вариант, так как текущий фрейм стека мы обязаны освободить. Лучшим вариантом будет размещение фрейма стека в возвращаемой структуре, это достижимо всего лишь изменением пролога с эпилогом. Но где размещать саму структуру? Хорошо, что бы можно было указывать место для размещения (стек или куча) при создании генератора, т. е. создание генератора будет иметь семантику конструктора.
                              Таким образом, мы получаем новый тип данных — инстанс генератора, являющийся скрытой структурой. Но какой размер у этой структуры? Он зависит от используемых локальных переменных, т.е. от реализации. Теперь представим, что генератор определен в одном модуле, а используется — в другом. Но тогда создание инстанса генератора будет иметь семантику выделения памяти под переменную неизвестного размера, а в текущем стандарте языка это невозможно.

                              Таким образом, я считаю, появление нормальных и гибких генераторов станет возможным только после появления экспорта аллокаторов, т.е. когда станет допустимым следующий код:
                              class Sample 
                              {
                                struct Implementation;
                                Implementation impl;
                              public:
                                Sample();
                              };
                              
                              ...
                              
                              new Sample(); // Сейчас эта строчка не скомпилируется - компилятору нужен размер Sample
                              
            • 0
              Извиняюсь, под «реентерабельностью» я подразумевал «не мешает работе других алгоритмов». Строго говоря, рекурсивный dfs тоже реентерабельностью не отличается.

              Эквивалентная постановка вопроса: «хватает ли для реализации dfs всего двух битов в каждой вершине?»
  • –4
    Извините но даже для далёкого человека от функицонального програмирования как я, ваши выводы кажутся ошибочными.
    Ваша проблема, ваши функции для оптимизации с помощью хвостовой рекурсии не должны иметь побочных эфектов. Неторые языки даже заставят вас писать в таком стиле( Erlang например).
    • +1
      Гм… Простите а где Вы тут видите пообочные эффекты?
      • –1
        Сохранение состояния есть побочным эфектом. В чисто функциональном стиле, всё что вам нужно между вызовами вы должны передать параметрами функций. Функция не должна зависеть от количества вызовов, а только от параметров, в не зависимости от количества вызовов функции, вызов с одними и теми же параметрами должен возвращать один и тот же результат. Это азы функционального програмирования.
        На основе которых можно строить более сложные концепции вроде карринга и частичного применения функций. Функции «с состоянием» (побочными эфектами) ломают всё.
        • 0
          Ок убедили. Но Давайте конкретику: 1) приведите строки из примеров в которых по вашему мнению пообочный эффект; 2) как их по вашему эти проблемные места следует переписать?
          • 0
            Я не владею F# в достаточно мере, но немного понимаю теорию функционального исчисления. Вы сами написали правильный вариант, передавая акумулятор как параметр вы получили «чистую» функцию, выход которой зависит только от входа. С исключением та же проблема.

            • 0
              Коллега, функция чистые во всех приведенных случаях. Извините, но я б на вашем месте, все таки еще раз прошелся по теории и закрепил бы ее на практике, перед тем как не к месту вставлять «вумные» цитаты, уж простите.
          • 0
            Насчёт акумулятора был не прав, это не побочный эфект не разобрался в коде.

            Насчёт блока try with, это ограничение by-design:
            blogs.msdn.com/b/fsharpteam/archive/2011/07/08/tail-calls-in-fsharp.aspx
            The call takes place in a try-catch or try-finally block (note that these calls aren’t really in tail position, by definition)
            • 0
              Кстати в этой статье приводится список случаев когда хвостовая рекурсия может быть применена
              A tail call is a call within a function whose result is immediately used as the output of the function — в случае с акумулятором(с статье привед'н схожий пример), исспользование оператора (+) не позволяет применить хвостовую рекурсию.
        • 0
          Какая из функций сохраняет состояние? И где?

          PS Если вы еще не догадались, аккумулятор — это и есть совершенно обычный аргумент функции
    • 0
      Тут нет побочных эффектов.
      printfn не считается (он только для отладки, в начальной и конечной версиях его нет).
  • 0
    А всё потому, что не надо изобретать велосипед. Есть же map, filter, foldl, take, takeWhile и т.п. Соответственно, они уже реализованы наилучшим для данного языка образом. И надо лишь понимать, какие функции могут разворачиваться в цикл (как map, filter или foldl), а какие — не могут (foldr, reverse).
    • 0
      Примитивы, да реализованы. Но это ведь только списки или последовательности. А что делать с деревьями, графами?
      Кстати reverse, зря вы обидели, да и foldr тоже наверно.
      • 0
        При обходе деревьев (тех, когда родительский узел хранит ссылки на дочерние) всё равно придётся вовлекать стек и хвостовая рекурсия тут вряд ли сильно поможет, зато реальный выигрыш от неё совсем небольшой получится. Графы вообще в чисто функциональном стиле могут по-разному храниться (и как следствие — деревья). Например, если в виде списка рёбер, то и обрабатываем с помощью соответствующих примитивов.

        А как же это можно reverse и foldr реализовать так, чтобы они были с хвостовой рекурсией без извращений? Даже если извратиться, будет хвостовая рекурсия, но копия списка всё равно будет храниться, пусть в куче, а не в стеке.
        • 0
          Про деревья, немного выше есть ответ с сылкой на континуацию и катаморфизм. Они как раз и преднозначены чтобы работать с графами,/деревьями без стека, на хвостовой рекурсии.

          А в чем проблема с reverse?
          let rec reverse acc lst =
            match lst with
            | [] -> acc
            | hd :: tl -> reverse (hd :: acc) tl
          


          Если у нас уже есть foldl и reverse
          let foldl f lst =  List.fold f (List.rev lst)
          

          • 0
            В случае с катаморфизмом, боюсь, что путь от корня к текущему узлу будет просто храниться не в стеке, а в замыканиях неявным образом. Но всё равно, храниться будет. Нельзя обойти дерево без затрат памяти, пропорциональных высоте, если в дереве каждый узел не хранит ссылки на родителя. А в случае немутабельных структур так не получится, если только не хранить дерево в виде списка рёбер, о чём я писал выше.
  • 0
    Надо же. Начинаю ценить отсутствие *неявной* хвостовой рекурсии в Clojure.
  • 0
    Поработаю-ка я pingback-ботом. dsorokin.blogspot.com/2012/05/blog-post.html
    • 0
      Спасибо. Про асинки будет во второй части. Там есть некоторые нюансы, хотя принцип тотже.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.