Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 68
И вообще, бросать и ловить собственные исключения что классу, что функции — неправильно.
Насчет дотнета соглашусь. Ибо в дотнете, во первых, исключение — это исключение. А во вторых механизм исключений довольно тормознутый. Но есть языки где исключения, один из механизмов control flow.
К примеру, OCaml (папа F#) — там исключения рассматривается как нормальная практика построения логики. Не могу сказать что мне такой подход по душе, но тем не менее.
К примеру, OCaml (папа F#) — там исключения рассматривается как нормальная практика построения логики. Не могу сказать что мне такой подход по душе, но тем не менее.
Я далёк от 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
выглядит напичканным советами для компилятора. Нельзя как-то переписать код в стиле первого куска, чтобы компилятор догадался до цикла сам? Условия, вызовы, параметры переставить местами или ещё какой-нибудь ахалай-махалай сотворить? Красота же теряется.
Как то так:
Вызов:
Нюанс такой, что в таком более кратком варианте, у функции появляется дополнительный параметр — аккумулятор. В данном случае, это даже полезно, ибо мы можем пробрасывать начальное значение. Но очень часто, аккумулятор нет смысла показывать наружу, поэтому организуется внутренний цикл — функция loop, которая работает с аккумулятором.
Кроме того когда в функции более 5-ти строк, то эффект не такой драматический, как в данном случае когда размер кода увеличился почти на 100% :-)
let sumTailRec acc i =
if i <= 0L then acc
else sumTailRec (acc + i) (i - 1L)
Вызов:
> sumTailRec 0L i
Нюанс такой, что в таком более кратком варианте, у функции появляется дополнительный параметр — аккумулятор. В данном случае, это даже полезно, ибо мы можем пробрасывать начальное значение. Но очень часто, аккумулятор нет смысла показывать наружу, поэтому организуется внутренний цикл — функция loop, которая работает с аккумулятором.
Кроме того когда в функции более 5-ти строк, то эффект не такой драматический, как в данном случае когда размер кода увеличился почти на 100% :-)
Можно сделать так (по крайней мере в 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
поэтому стоит просто создать вторую функцию с одним аргументом путем частичного применения нуля на первое место ;)
Нет, нельзя. В идеале хотелось бы, чтобы оптимизатор сам определял, как преобразовать исходный вариант в функцию с хвостовой рекурсией. А на деле оказывается, что эта задача в общем случае является неразрешимой, потому в реальной жизни разворачивание рекурсии в хвостовую перекладывают на плечи программистам. Но на самом деле, программистам оно нафиг не надо, потому что тот же пример можно переписать как-то так:
Впрочем, я недостаточно хорошо помню F#. Может, там прокатит трюк с заменой fun a b -> a + b на (+)
А вообще, можно и так:
или даже так:
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
Решение: используйте C# вместо F#
Если не секрет, а где вы используйте F#, где он удобнее чем императивные языки программирования? Просто первый раз вижу, чтобы им кто-то пользовался в коммерческих целях.
Если не секрет, а где вы используйте F#, где он удобнее чем императивные языки программирования? Просто первый раз вижу, чтобы им кто-то пользовался в коммерческих целях.
Ой, в первой строчке парсер съел тег «sarcasm» :)
>откуда в C# генерики
от шаблонов С++, нет?
от шаблонов С++, нет?
Нет.
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#
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#
От шаблонов С++ там только элементы синтаксиса.
Извините, я не вижу принципиальных отличий шаблонов С++ от дженериков С#. Не могли бы Вы просветить меня?
Если в одном предложении — то темлейты это система макросов работающая во время компиляции, а генерики это полноценные классы с поддержкой рантайма. Как сказал Один известный дядя:
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.
Ну и более Подробно.
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.
Ну и более Подробно.
Ну и я бы добавил, что благодаря рантайму доступны специфичные фичи — msdn.microsoft.com/en-us/library/ee207183.aspx
Не говоря уже про рефлекшн.
Не говоря уже про рефлекшн.
Основное отличие в том, что дженерики C# используют строгую типизацию и не дают доступа к статическим членам, а шаблоны C++ используют утиную типизацию, дают доступ к статическим членам, а также поддерживают переопределение для частных случаев.
Вообще сколько мне не говорили про рекурсию, что код при ней становится более красивым и легких для восприятия, по факту ее вообще стоит почти всегда избегать, потому что памяти потребляет больше, а производительность меньше.
Ну так это C#, в котором, насколько я помню, как раз компилятор ничего не знает про хвостовую рекурсию. Поэтому и память жрется, и глубина вложенности ограничена.
Ну, если хвостовая рекурсия трансформируется в итерацию, то и производительность не теряется, разве не так?
Существуют рекурсивные структуры данных и, соответственно, алгоритмы работы с ними. Зачем изголяться и изобретать итерацию там, где есть рекурсия? В функциональных языках, где реализована нормальная рекурсия, проблем с производительностью быть не должно.
Уже немного оффтоп.
Меня всегда интересовал вопрос: существуют ли такие программы для преобразования рекурсивных методов в итеративные и наоборот на уровне кода, возможно используя ANTLR, Gold Parser и другие генераторы парсеров? Было бы интересно с теоретической точки зрения их посмотреть.
Ведь любая рекурсия может быть преобразована в итерацию, даже не хвостовая.
Меня всегда интересовал вопрос: существуют ли такие программы для преобразования рекурсивных методов в итеративные и наоборот на уровне кода, возможно используя ANTLR, Gold Parser и другие генераторы парсеров? Было бы интересно с теоретической точки зрения их посмотреть.
Ведь любая рекурсия может быть преобразована в итерацию, даже не хвостовая.
> Ведь любая рекурсия может быть преобразована в итерацию, даже не хвостовая.
Ну да. Путем явного создания вспомогательного стека :)
Видел я подобное в школьном учебнике по Паскалю.
и прочий ужас.
Существуют алгоритмы, которые принципиально невозможно реализовать в итеративной форме (в основном это dfs и обработка деревьев). Да, они могут быть переписаны с использованием вспомогательного стека или при помощи модификации структуры данных, и это будет даже аккуратнее чем ужас выше, но это уже будет другой алгоритм.
А все формальные методы не дадут выигрыша в результате преобразования.
Ну да. Путем явного создания вспомогательного стека :)
Видел я подобное в школьном учебнике по Паскалю.
var
stack : array [1..maxstack] of TStackFrame;
и прочий ужас.
Существуют алгоритмы, которые принципиально невозможно реализовать в итеративной форме (в основном это dfs и обработка деревьев). Да, они могут быть переписаны с использованием вспомогательного стека или при помощи модификации структуры данных, и это будет даже аккуратнее чем ужас выше, но это уже будет другой алгоритм.
А все формальные методы не дадут выигрыша в результате преобразования.
Ерунда! Я писал и могу сейчас написать без стека DFS. O(1) по памяти и O(1) (амортизированно) по времени к переходу на следующий узел.
А ваш dfs реентерабельный?
Рекурсивный алгоритм — да.
Рекурсивный алгоритм — да.
Да. Вот код: pastebin.com/pJt3pUDf
Это симметричный обход дерева (ну все как обычно, структура — узел + указатели на детей и родителя). Да, это не DFS, родитель возвращается после левого ребенка, но до правого, но понятное дело, что это легко исправить. Задача была в симметричном.
Никаких статических данных, побочных эффектов и так далее.
На деле мне для итератора нужен 1 указатель — текущего узла. Указатели на самого левого сына дерева и самого правого нужны для проекта, но не этого класса, их можно игнорировать.
Основная идея вот в чем: если у текущего узла есть левый сын — в него идти не надо, ибо мы были в нем раньше (иначе нарушен правильный порядок). Если есть правый сын — идем сначала в него, а потом спускаемся по левым детям. Если правого сына нет — поднимаемся по родителям пока узел является правым сыном.
Кажется все описал, может что-то и забыл — посмотрите в коде. Он 100% рабочий, протестирован десятком разных задачек.
Это симметричный обход дерева (ну все как обычно, структура — узел + указатели на детей и родителя). Да, это не DFS, родитель возвращается после левого ребенка, но до правого, но понятное дело, что это легко исправить. Задача была в симметричном.
Никаких статических данных, побочных эффектов и так далее.
На деле мне для итератора нужен 1 указатель — текущего узла. Указатели на самого левого сына дерева и самого правого нужны для проекта, но не этого класса, их можно игнорировать.
Основная идея вот в чем: если у текущего узла есть левый сын — в него идти не надо, ибо мы были в нем раньше (иначе нарушен правильный порядок). Если есть правый сын — идем сначала в него, а потом спускаемся по левым детям. Если правого сына нет — поднимаемся по родителям пока узел является правым сыном.
Кажется все описал, может что-то и забыл — посмотрите в коде. Он 100% рабочий, протестирован десятком разных задачек.
Спасибо, я знаю этот алгоритм.
Проблема в том, что это — симметричный обход дерева, а не dfs.
DFS — это обход графа, вообще-то.
Проблема в том, что это — симметричный обход дерева, а не dfs.
DFS — это обход графа, вообще-то.
Ах, не подумал, да, признаю ошибку. Обычно первое что приходит в голову это частный случай в виде дерево. Тогда или рекурсия или с доп памятью, наверное — не реализовывал, не знаю.
Правда на практике я бы не обходил граф рекурсивно. Ведь дерево обычно балансируется и глубина рекурсии — логарифм. А значит для дерева даже с 2**32 узлов глубина стека будет порядка 32. А даже если каждый бит 1 узел и дерево содержит 2**64 узлов — всего 64, что ерунда.
А вот у графов нет никакой балансировки и там можно переполнение стека словить. Возможно, хвостовая рекурсия и спасет, но это надо по коду смотреть.
Правда на практике я бы не обходил граф рекурсивно. Ведь дерево обычно балансируется и глубина рекурсии — логарифм. А значит для дерева даже с 2**32 узлов глубина стека будет порядка 32. А даже если каждый бит 1 узел и дерево содержит 2**64 узлов — всего 64, что ерунда.
А вот у графов нет никакой балансировки и там можно переполнение стека словить. Возможно, хвостовая рекурсия и спасет, но это надо по коду смотреть.
> А значит для дерева даже с 2**32 узлов глубина стека будет порядка 32.
Маленькая поправка: так ни одно дерево не балансируется. Реальная оценка глубины — 64.
По поводу графов: хвостовой рекурсией тут не обойтись. Классическое решение проблемы с переполнением стека — выделение вспомогательного стека в куче.
Маленькая поправка: так ни одно дерево не балансируется. Реальная оценка глубины — 64.
По поводу графов: хвостовой рекурсией тут не обойтись. Классическое решение проблемы с переполнением стека — выделение вспомогательного стека в куче.
>> Маленькая поправка: так ни одно дерево не балансируется. Реальная оценка глубины — 64.
Это понятно. Речь шла о порядках, константы не в счет, а они небольшие. Для КЧД — 2, например.
>> Классическое решение проблемы с переполнением стека — выделение вспомогательного стека в куче.
Ну то есть использование пользоватеского стека — это очевидное решение избавления от рекурсии, это понятно. Но тут сразу код жуткий. Интересно написать нормальный код, потом чуть его поправить для компилятора (как в статье) и получить нормальный код + нормальный результат (например, через оптимизацию хвостовой рекурсии).
Это понятно. Речь шла о порядках, константы не в счет, а они небольшие. Для КЧД — 2, например.
>> Классическое решение проблемы с переполнением стека — выделение вспомогательного стека в куче.
Ну то есть использование пользоватеского стека — это очевидное решение избавления от рекурсии, это понятно. Но тут сразу код жуткий. Интересно написать нормальный код, потом чуть его поправить для компилятора (как в статье) и получить нормальный код + нормальный результат (например, через оптимизацию хвостовой рекурсии).
В функциональном подходе это делается с помощью континьюэйшенов и катоморфизма.
Если с английским нормально, то очень советую вот эту серию статей. Там восемь частей, и разбираются подходы к рекурсивной обработке сложных структур данных.
Была еще небольшая статья на Хабре на эту тему.
Если с английским нормально, то очень советую вот эту серию статей. Там восемь частей, и разбираются подходы к рекурсивной обработке сложных структур данных.
Была еще небольшая статья на Хабре на эту тему.
Самое интересное это методы operator++ и operator--. Это переход на следующий и предыдущий узлы соответственно. Все что выше них — это всякое служебное. Все что ниже — собственно переход по узлам как я описал в предыдущем комментарии.
Плюс этого решения перед рекурсивным еще и то, что оно не вываливает сразу все вершины, а позволяет переходить к следующей по мере надобности.
То есть рекурсивное сразу жадно все обходит, а итерратор — лениво. При этом сделать из ленивого жадный — дело одного цикла, а вот обратное — сомневаюсь, что выполнимо.
Плюс этого решения перед рекурсивным еще и то, что оно не вываливает сразу все вершины, а позволяет переходить к следующей по мере надобности.
То есть рекурсивное сразу жадно все обходит, а итерратор — лениво. При этом сделать из ленивого жадный — дело одного цикла, а вот обратное — сомневаюсь, что выполнимо.
Обратное вполне выполнимо, например при помощи микронитей. Правда, CLR всячески сопротивляется принудительному переключению контекста, но в C# есть генераторы, а это еще лучше.
А по поводу вашего алгоритма я уже написал выше.
А по поводу вашего алгоритма я уже написал выше.
(долбанные 5 минут, разговор растягивается на часы)
Генератор — это yield? Да, это сказка, итераторы в разы проще писать. Это как раз пример, когда и код простой и, чуть-чуть поправив, компилятор сделает хороший результат. В джаве и плюсах их очень сильно не хватает. При том, что реализовать их подержку в компиляторе при имеющихся замыканиях — совсем не сложно. Контекст уже умеем сохранять, анонимный локальный класс тоже. Но похоже совсем этого не дождемся. На следующий стандарт запланировано сильное расширение стандартной библиотеки, а фич, считается, что и так достаточно.
Генератор — это yield? Да, это сказка, итераторы в разы проще писать. Это как раз пример, когда и код простой и, чуть-чуть поправив, компилятор сделает хороший результат. В джаве и плюсах их очень сильно не хватает. При том, что реализовать их подержку в компиляторе при имеющихся замыканиях — совсем не сложно. Контекст уже умеем сохранять, анонимный локальный класс тоже. Но похоже совсем этого не дождемся. На следующий стандарт запланировано сильное расширение стандартной библиотеки, а фич, считается, что и так достаточно.
Не сказал бы, что это — очень простая фича.
В генераторах главная проблема — не замыкания, а автоматическое преобразование кода из структурного в автоматный.
Кстати, полностью эту проблему так и не решили.
В C# до сих пор нельзя писать yield и await внутри блоков catch и finally. А еще нельзя писать yield внутри блока try, для которого указан finally. Меня постоянно раздражают эти ограничения…
В генераторах главная проблема — не замыкания, а автоматическое преобразование кода из структурного в автоматный.
Кстати, полностью эту проблему так и не решили.
В C# до сих пор нельзя писать yield и await внутри блоков catch и finally. А еще нельзя писать yield внутри блока try, для которого указан finally. Меня постоянно раздражают эти ограничения…
*А еще нельзя писать yield внутри блока try, для которого указан catch
Автоматный, что?
Под yield скрывается нечно большее, чем сохранение контекста (значений переменных и номера строки, или на уровне асма — вершины стека (или регистров) и IP, SP?
Ну положим, почему в catch нельзя писать это понятно. Пошла раскрутка стека и не до выхода уже. А вот почему в try с имеющимся catch — сходу не соображу, несмотря на то, что неплохо себе представляю обработку исключений на уровне CIL-кода.
Расскажите поподробнее, пожалуйтса, или ссылочку бы…
Под yield скрывается нечно большее, чем сохранение контекста (значений переменных и номера строки, или на уровне асма — вершины стека (или регистров) и IP, SP?
Ну положим, почему в catch нельзя писать это понятно. Пошла раскрутка стека и не до выхода уже. А вот почему в try с имеющимся catch — сходу не соображу, несмотря на то, что неплохо себе представляю обработку исключений на уровне CIL-кода.
Расскажите поподробнее, пожалуйтса, или ссылочку бы…
> Автоматный, что?
Различают четыре парадигмы программирования — автоматную, структурную, объектно-ориентированную и функциональную (парадигмы не являются чем-то, жестко зависимым от языка; на любом языке можно писать, используя любую комбинацию парадигм).
Код метода-генератора является, по сути, структурным кодом (хотя он и может обращаться к другим объектам, но эти обращения сводятся просто к вызовам сторонних подпрограмм и не подлежат преобразованию).
Но структурный код не может прерываться в любое время и продолжаться с этого места позднее, по крайней мере в CLR. Поэтому при компиляции происходит преобразование генератора в автомат.
Маленькое замечание: я не говорю «конечный автомат», так как получившийся автомат, строго говоря, конечным не является.
> Под yield скрывается нечто большее, чем сохранение контекста?
Именно, нечто большее. В MSIL невозможно полностью сохранить текущий контекст, а потом восстановить его. Поэтому к каждому «контексту» должна прилагаться функция перехода (а вместе они называются автоматом).
А именно,
1) Создается новый класс, реализующий IEnumerable<> и IEnumerator<>
2) Все локальные переменные и аргументы переносятся в этот класс как поля
3) Вводятся новые переменные (назовем их state и current).
4) Весь код метода превращается в один гигантский switch (state). При этом выражение yield return foo; превращается в
5) Отдельного слова стоит обработка ошибок — каждый блок try...finally генерирует, помимо собственно блока try...finally, дополнительный switch, а также новый метод.
> Расскажите поподробнее, пожалуйтса, или ссылочку бы…
Могу порекомендовать способ самостоятельных исследований:
1) скачиваем ILSpy;
2) открываем в нем исходники System.Linq.Enumerable из библиотеки System.Core;
3) переключая настройку «decompile enumerators (yield return)» сравниваем код стандартный методов Linq с использованием yield и преобразованный;
4) также можно писать свои генераторы и декомпилировать их.
Различают четыре парадигмы программирования — автоматную, структурную, объектно-ориентированную и функциональную (парадигмы не являются чем-то, жестко зависимым от языка; на любом языке можно писать, используя любую комбинацию парадигм).
Код метода-генератора является, по сути, структурным кодом (хотя он и может обращаться к другим объектам, но эти обращения сводятся просто к вызовам сторонних подпрограмм и не подлежат преобразованию).
Но структурный код не может прерываться в любое время и продолжаться с этого места позднее, по крайней мере в 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) также можно писать свои генераторы и декомпилировать их.
Про существование парадигм я знаю. Не знал про преобразование в автоматную, спасибо за ликбез.
Все равно не понимаю, почему не MSIL не может запомнить просто номер (адрес) инструкции (ну и возможно состояние верхушки стека от текущей фукнции) и нужен свитч.
Но я больше с++-разработчик. Там все в асм генерится. И регистры (в том числе SP/IP) там сохранить не проблема.
Все равно не понимаю, почему не MSIL не может запомнить просто номер (адрес) инструкции (ну и возможно состояние верхушки стека от текущей фукнции) и нужен свитч.
Но я больше с++-разработчик. Там все в асм генерится. И регистры (в том числе SP/IP) там сохранить не проблема.
Наверное ответ на мой вопрос состоит в том, что решение, описанное выше (применяемое в MSIL) — высокоуровневое. Оно не опирается на особенности CIL-кода (отстуствие регистров, стек вычислений), а использует генерацию, доступную в языке — мы сами руками можем написать такой же класс с полями и добавить swtich. То есть yield выступает этаким высокоуровневым макросом, а не фичей языка.
> Все равно не понимаю, почему не MSIL не может запомнить просто номер (адрес) инструкции (ну и возможно состояние верхушки стека от текущей фукнции) и нужен свитч.
Потому что MSIL — компилируемый язык, и такой вещи, как номер текущей инструкции, в природе не существует. Можно было бы расширить JIT компилятор, но в Microsoft предпочли переложить эту задачу на компилятор более высокого уровня, поскольку это проще.
> Но я больше с++-разработчик. Там все в асм генерится. И регистры (в том числе SP/IP) там сохранить не проблема.
Да, не проблема. Но не настолько, как кажется поначалу.
Сохранять (E)SP — не вариант, так как текущий фрейм стека мы обязаны освободить. Лучшим вариантом будет размещение фрейма стека в возвращаемой структуре, это достижимо всего лишь изменением пролога с эпилогом. Но где размещать саму структуру? Хорошо, что бы можно было указывать место для размещения (стек или куча) при создании генератора, т. е. создание генератора будет иметь семантику конструктора.
Таким образом, мы получаем новый тип данных — инстанс генератора, являющийся скрытой структурой. Но какой размер у этой структуры? Он зависит от используемых локальных переменных, т.е. от реализации. Теперь представим, что генератор определен в одном модуле, а используется — в другом. Но тогда создание инстанса генератора будет иметь семантику выделения памяти под переменную неизвестного размера, а в текущем стандарте языка это невозможно.
Таким образом, я считаю, появление нормальных и гибких генераторов станет возможным только после появления экспорта аллокаторов, т.е. когда станет допустимым следующий код:
Потому что MSIL — компилируемый язык, и такой вещи, как номер текущей инструкции, в природе не существует. Можно было бы расширить JIT компилятор, но в Microsoft предпочли переложить эту задачу на компилятор более высокого уровня, поскольку это проще.
> Но я больше с++-разработчик. Там все в асм генерится. И регистры (в том числе SP/IP) там сохранить не проблема.
Да, не проблема. Но не настолько, как кажется поначалу.
Сохранять (E)SP — не вариант, так как текущий фрейм стека мы обязаны освободить. Лучшим вариантом будет размещение фрейма стека в возвращаемой структуре, это достижимо всего лишь изменением пролога с эпилогом. Но где размещать саму структуру? Хорошо, что бы можно было указывать место для размещения (стек или куча) при создании генератора, т. е. создание генератора будет иметь семантику конструктора.
Таким образом, мы получаем новый тип данных — инстанс генератора, являющийся скрытой структурой. Но какой размер у этой структуры? Он зависит от используемых локальных переменных, т.е. от реализации. Теперь представим, что генератор определен в одном модуле, а используется — в другом. Но тогда создание инстанса генератора будет иметь семантику выделения памяти под переменную неизвестного размера, а в текущем стандарте языка это невозможно.
Таким образом, я считаю, появление нормальных и гибких генераторов станет возможным только после появления экспорта аллокаторов, т.е. когда станет допустимым следующий код:
class Sample
{
struct Implementation;
Implementation impl;
public:
Sample();
};
...
new Sample(); // Сейчас эта строчка не скомпилируется - компилятору нужен размер Sample
Извиняюсь, под «реентерабельностью» я подразумевал «не мешает работе других алгоритмов». Строго говоря, рекурсивный dfs тоже реентерабельностью не отличается.
Эквивалентная постановка вопроса: «хватает ли для реализации dfs всего двух битов в каждой вершине?»
Эквивалентная постановка вопроса: «хватает ли для реализации dfs всего двух битов в каждой вершине?»
Извините но даже для далёкого человека от функицонального програмирования как я, ваши выводы кажутся ошибочными.
Ваша проблема, ваши функции для оптимизации с помощью хвостовой рекурсии не должны иметь побочных эфектов. Неторые языки даже заставят вас писать в таком стиле( Erlang например).
Ваша проблема, ваши функции для оптимизации с помощью хвостовой рекурсии не должны иметь побочных эфектов. Неторые языки даже заставят вас писать в таком стиле( Erlang например).
Гм… Простите а где Вы тут видите пообочные эффекты?
Сохранение состояния есть побочным эфектом. В чисто функциональном стиле, всё что вам нужно между вызовами вы должны передать параметрами функций. Функция не должна зависеть от количества вызовов, а только от параметров, в не зависимости от количества вызовов функции, вызов с одними и теми же параметрами должен возвращать один и тот же результат. Это азы функционального програмирования.
На основе которых можно строить более сложные концепции вроде карринга и частичного применения функций. Функции «с состоянием» (побочными эфектами) ломают всё.
На основе которых можно строить более сложные концепции вроде карринга и частичного применения функций. Функции «с состоянием» (побочными эфектами) ломают всё.
Ок убедили. Но Давайте конкретику: 1) приведите строки из примеров в которых по вашему мнению пообочный эффект; 2) как их по вашему эти проблемные места следует переписать?
Я не владею F# в достаточно мере, но немного понимаю теорию функционального исчисления. Вы сами написали правильный вариант, передавая акумулятор как параметр вы получили «чистую» функцию, выход которой зависит только от входа. С исключением та же проблема.
Насчёт акумулятора был не прав, это не побочный эфект не разобрался в коде.
Насчёт блока 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)
Насчёт блока 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)
Кстати в этой статье приводится список случаев когда хвостовая рекурсия может быть применена
A tail call is a call within a function whose result is immediately used as the output of the function — в случае с акумулятором(с статье привед'н схожий пример), исспользование оператора (+) не позволяет применить хвостовую рекурсию.
A tail call is a call within a function whose result is immediately used as the output of the function — в случае с акумулятором(с статье привед'н схожий пример), исспользование оператора (+) не позволяет применить хвостовую рекурсию.
Какая из функций сохраняет состояние? И где?
PS Если вы еще не догадались, аккумулятор — это и есть совершенно обычный аргумент функции
PS Если вы еще не догадались, аккумулятор — это и есть совершенно обычный аргумент функции
Тут нет побочных эффектов.
printfn не считается (он только для отладки, в начальной и конечной версиях его нет).
printfn не считается (он только для отладки, в начальной и конечной версиях его нет).
А всё потому, что не надо изобретать велосипед. Есть же map, filter, foldl, take, takeWhile и т.п. Соответственно, они уже реализованы наилучшим для данного языка образом. И надо лишь понимать, какие функции могут разворачиваться в цикл (как map, filter или foldl), а какие — не могут (foldr, reverse).
Примитивы, да реализованы. Но это ведь только списки или последовательности. А что делать с деревьями, графами?
Кстати reverse, зря вы обидели, да и foldr тоже наверно.
Кстати reverse, зря вы обидели, да и foldr тоже наверно.
При обходе деревьев (тех, когда родительский узел хранит ссылки на дочерние) всё равно придётся вовлекать стек и хвостовая рекурсия тут вряд ли сильно поможет, зато реальный выигрыш от неё совсем небольшой получится. Графы вообще в чисто функциональном стиле могут по-разному храниться (и как следствие — деревья). Например, если в виде списка рёбер, то и обрабатываем с помощью соответствующих примитивов.
А как же это можно reverse и foldr реализовать так, чтобы они были с хвостовой рекурсией без извращений? Даже если извратиться, будет хвостовая рекурсия, но копия списка всё равно будет храниться, пусть в куче, а не в стеке.
А как же это можно reverse и foldr реализовать так, чтобы они были с хвостовой рекурсией без извращений? Даже если извратиться, будет хвостовая рекурсия, но копия списка всё равно будет храниться, пусть в куче, а не в стеке.
Про деревья, немного выше есть ответ с сылкой на континуацию и катаморфизм. Они как раз и преднозначены чтобы работать с графами,/деревьями без стека, на хвостовой рекурсии.
А в чем проблема с reverse?
Если у нас уже есть foldl и reverse
А в чем проблема с 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)
В случае с катаморфизмом, боюсь, что путь от корня к текущему узлу будет просто храниться не в стеке, а в замыканиях неявным образом. Но всё равно, храниться будет. Нельзя обойти дерево без затрат памяти, пропорциональных высоте, если в дереве каждый узел не хранит ссылки на родителя. А в случае немутабельных структур так не получится, если только не хранить дерево в виде списка рёбер, о чём я писал выше.
Надо же. Начинаю ценить отсутствие *неявной* хвостовой рекурсии в Clojure.
Поработаю-ка я pingback-ботом. dsorokin.blogspot.com/2012/05/blog-post.html
Кстати, вместо (fun i -> i) можно воспользоваться функцией id.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
F# Хвостовая рекурсия. Подводные грабли. Часть 1