О хвостовой рекурсии

90%? Везет тебе.

если в 90% случаев ты будешь юзать ХР - тебе тоже так «повезёт». Вот только нужно-ли это в рабочей программе? Да и не слишком понятно преимущество 100500 строчек выхлопа отладчика, перед 100500 строчками выхлопа отладочной printf()?

Я про отладчик, который по твоим словам «не нужен».

ну открой топик «нежен/ненужен отладчик?». Здесь мы про другое - про нужность ХР.

Ты как всегда в свое репертуаре — позорно слил и в кусты/на другую тему.

разуй глазки и прочитай сабж, куда ты пишешь (точнее сливаешь).

«Нужность» стека ХР в продакшене как раз очень хорошо раскрывает «нужность» отладчика. Это всего лишь одна и не главная причина ненужности отладчика в большинстве случаев, то, что ХР не нужна сама по себе, и её «удобство отладки» тоже не нужно. А о других причинах давай поговорим в другой теме.

ну открой топик «нежен/ненужен отладчик?». Здесь мы про другое - про нужность ХР.

Тебе в очередной раз надо напоминать что же ты сказал? Я напомню: «если честно, но в open source дебагер попросту не нужен... Не, это действительно так...»

разуй глазки и прочитай сабж, куда ты пишешь (точнее сливаешь).

Ты с темы то не уходи и не виляй, а наконец ответь за свои слова.

Тебе в очередной раз надо напоминать что же ты сказал? Я напомню: «если честно, но в open source дебагер попросту не нужен... Не, это действительно так...»

ты если хочешь обсуждать (не)нужность дебагера - открывай тему про (не)нужность. Мне дебагер действительно очень редко когда нужен, если твоё мнение другое - давай его обсудим. Но не в этой теме.

Ты с темы то не уходи и не виляй, а наконец ответь за свои слова.

с темы уходишь как раз ты. Мы про ХР. Но если тебе интересно - изволь, ответить могу, причём легко - мне отладчик не нужен. Тебе нужен? Расскажи: зачем? Ты избавился от 100500 printf()? Молодец. У меня их и не было.

если в 90% случаев ты будешь юзать ХР - тебе тоже так «повезёт»

Норкоман, уходи.

мне отладчик не нужен.

Вот так и пиши, что _тебе_ не нужен, ты же смеешь свой бред обобщать на весь opensource

Расскажи: зачем? Ты избавился от 100500 printf()?

Уже написал зачем. Научись наконец читать.

О ненужности говнооптимизации хвостовых говновызовов хорошо Гвидо написал:

http://neopythonic.blogspot.ru/2009/04/tail-recursion-elimination.html?m=1

I don't believe in recursion as the basis of all programming. This is a fundamental belief of certain computer scientists, especially those who love Scheme and like to teach programming by starting with a «cons» cell and recursion. But to me, seeing recursion as the basis of everything else is just a nice theoretical approach to fundamental mathematics (turtles all the way down), not a day-to-day tool.

+100500

остальное это питонопроблемы.

Гвидо? Смешно, правда

Вот так и пиши, что _тебе_ не нужен, ты же смеешь свой бред обобщать на весь opensource

в _моих_ постах выражено ТОЛЬКО _моё_ _личное_ мнение. Open source тут при том, что в проприентарной НЁХ отладчик для меня был незаменимым и полезным инструментом - без него никак.

А тебе - может и нужен, если ты, например, не понимаешь, как работает твой код, то отладчик тебе поможет.

вот например:

Уже написал зачем. Научись наконец читать.

Я открою дамп в _отладчике_, посмотрю просмотрю стек и исправлю проблемное место.

а я и так _знаю_, ЧТО будет в моём дампе. Потому просто исправлю ошибку.

а я и так _знаю_, ЧТО будет в моём дампе. Потому просто исправлю ошибку.

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

Гвидо? Смешно, правда

почему?

Ага, а знание приходит тебе при помощи libastral. Ты просто феерический бред постоянно пишешь.

почему-же? даже дворник знает, КОГДА надо чистить его помойку. Причём без всякой телеметрии и прочего. Достаточно её(помойку) 20 лет чистить (:

Я просто не понимаю как ты можешь программировать что-либо, уверен, что ничего сложнее хело-ворлда ты не писал.

меня мало волнует твоё мнение о моей квалификации. Смирись.

почему-же? даже дворник знает, КОГДА надо чистить его помойку. Причём без всякой телеметрии и прочего. Достаточно её(помойку) 20 лет чистить (:

Во-первых, КОГДА!=КАК. Во-вторых, ты сравнил свою работу с работой дворника, молодец.

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

Как правильно писал Гвидо, «the idea that TRE is merely an optimization, which each Python implementation can choose to implement or not, is wrong. Once tail recursion elimination exists, developers will start writing code that depends on it, and their code won't run on implementations that don't provide it». То есть, семантика до и после такой «оптимизации» разная. Так что те, кто тут вякают, что мол для отладки можно ее и отключить - те просто дебилы.

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

Во-первых, КОГДА!=КАК.

в данном случае и КОГДА, и КАК.

Во-вторых, ты сравнил свою работу с работой дворника, молодец.

ну... что поделать...

То есть, семантика до и после такой «оптимизации» разная.

Давай, расскажи мне про семантику, я посмеюсь.

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

Гвидо - малограмотный чувак, а что?

Давай, расскажи мне про семантику, я посмеюсь.

Поведение кода с глубиной вызовов за 100500 до «оптимизации» - упасть по stack overflow.

После оптимизации семантика меняется: код исполняется, stack overflow не происходит.

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

Вывод: TCO - мразь и говно.

У-тю-тю. Ты не стоишь и обслюнявленного им окурка, салага!

Как правильно писал Гвидо, «the idea that TRE is merely an optimization, which each Python implementation can choose to implement or not, is wrong. Once tail recursion elimination exists, developers will start writing code that depends on it, and their code won't run on implementations that don't provide it».

ну это питонопроблема, на самом деле.

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

ну не дебилы конечно, но да, в питонокоде это действительно проблема.

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

вот не надо - в сишечке вот вставили - как необходимую меру по борьбе с быдлокодерством. И при чём тут сишечка? Гвидо вообще не прав в том, что _всех_ программистов считает законченными быдлокодерами, которых на до ЗАСТАВЛЯТЬ делать отступы и не юзать ХР. ХР в питоне и сишечке == быдлокод, ибо обратное не доказано (сторонники могли-бы привести просто и понятный код, который иллюстрирует нужность ХР, но _никто_ этого сделать не смог, смог только предоставить ссылки на статьи из 100500 букв)

Вообще говоря, хвостовая рекурсия практически эквивалентна циклу, потому непонятна твоя ненависть к тому, что компилятор этот цикл разворачивает явно. Фактически ХР эквивалентна

while(true)
{

}

Все правильно. Писать хвостовые вызовы можно для всяких поисков по древовидной структуре, просто для них не всегда сразу есть ФВП, особенно для самодельных всяких. А так это просто «good way for reasoning about code for mathematicians»

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

а) Такая проблема есть практически у любой оптимизации. Внезапно, правда?

б) ты плохо представляешь себе, что такое семантика

Гвидо - малограмотный чувак, а что?

«малограмотный чувак» скорее ты, если так говоришь. Кстати, где ты был в 1982ом, когда Гвидо университет закончил? Я вот в школу пошёл...

в режиме дебага просто сдохнет.

Такая проблема есть практически у любой оптимизации.

и как люди только дебажатся )

а) Такая проблема есть практически у любой оптимизации. Внезапно, правда?

Нет, салага. Такие «проблемы» при оптимизации недопустимы. Компилятор не имеет права менять семантику при оптимизациях, и никакие другие оптимизации этого не делают.

б) ты плохо представляешь себе, что такое семантика

У-тю-тюшечки, и это мне какая-то салага говорит? Ну расскажи, салага, что такое «семантика», и почему у кода с exception и кода без exception вдруг оказывается одинаковая семантика?

ну это питонопроблема, на самом деле.

Че?!? Вот прикинь, начнут люди на Си писать рассчитывая на наличие TCO в компиляторе. Тогда их код точно так же не будет работать там, где такой говнооптимизации нет.

вот не надо - в сишечке вот вставили

Оно там срабатывает в очень редких случаях, так что не считается. Например, для:

int f(int (*g)(int), int x) { return g(x); }

никакой компилятор C никакого TCO не сделает. Так что никто и не будет писать говнокод, рассчитывая на такое поведение.

Вообще говоря, хвостовая рекурсия практически эквивалентна циклу

Еще один, путающий хвостовые вызовы вообще с хвостовой рекурсией в частности. Откуда тут столько ламья?!?

т.е. тривиальный случай цикла

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

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

ну с этим согласен - деревья рекурсивная структура по определению, и потому рекурсивный алгоритм для дерево - вполне естественно. Тут я вынужден согласится, что применять рекурсию тут можно и нужно. Пусть даже хвостовую, просто для того, что-бы вообще не мучится с отладкой. Ну и никакие факапы нам с деревом не грозят - программа всё равно неминуемо рухнет при вырождении дерева, применяем мы ХР, или нет, и разворачиваем её мы, компилятор, или вообще оно так и остаётся. Хотя-бы потому, что кроме хвостовой в дереве будет и не хвостовая, иначе это не дерево, а список.

А так это просто «good way for reasoning about code for mathematicians»

это как раз тот случай, когда математиков к коду лучше не подпускать - потому-что код с ХР эквивалентен только аналитически. IRL стек ограничен, а команды вызовов CPU для этого попросту не существуют. В итоге те-же деревья имеет использовать лишь в том случае, когда число эл-тов логично считать бесконечно большим, как полагают математики.

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

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

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

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

Пусть даже хвостовую

А вот хвостовой рекурсии ни в одном из этих алгоритмов-то и нету!

когда математиков к коду лучше не подпускать

Их никогда к программированию нельзя подпускать.

а) Такая проблема есть практически у любой оптимизации. Внезапно, правда?

неа. Не любой. Гвидо писал о том, что ХР развёрнутая в цикл это НЕ тоже самое, что не развёрнутая. Если речь только про _идеальные_ операторы в _идеальных_ ЯП, то эквивалентность имеется, но только в _идеальном_ случае. К примеру, _первый_ переход к началу цикла предсказывается правильно и НЕ приводит к оверхеду. А переход к функции - вещь непредсказуемая, и приведёт к оверхеду, даже если на самом деле мы переходим к началу этой функции. Для CPU это НОВЫЙ код, со всеми вытекающими, ибо CPU не в курсе про ФП.

б) ты плохо представляешь себе, что такое семантика

ну вот ты нам сейчас и расскажешь, что это такое.

Поиск элемента в дереве при заданом пути вполне себе хвостовой, и нечего загаживать стек. В некоторых языках нет неявного TCO и это не оптимизация, это отдельное ключевое слово, которое вешается на функцию и если оно там есть, то компилятор обязан ее производить и должен выдавать ошибку компиляции если функция не хвосто-рекурсивная. В любом ЯП есть coding conventions. Если код написан в стиле использования иммутабельных данных, то while ясное дело будет выходить за пределы стиля, строгий явный гарантированный TCO тут поможет и даст ту же эффективность. А пример с деревом - пример когда особо и ФВП нету подходящей, хотя можно навелосипедить

намного эффективнее будет вручную раскрытая в цикл рекурсия с явным стеком

))) Особенно со стеком из библиотеки коллекций и горой вызовов, иногда виртуальных

Их никогда к программированию нельзя подпускать.

А, ну все понятно

31. Довольно долго считалось, что хвостовая рекурсия — особый трюк в оптимизирующих компиляторах. Ясное семантическое основание хвостовой рекурсии было найдено Карлом Хьюиттом (Hewitt 1977), который выразил ее в терминах модели вычислений с помощью «передачи сообщений» (мы рассмотрим эту модель в главе 3). Вдохновленные этим, Джеральд Джей Сассман и Гай Льюис Стил мл. (см. Steele 1975) построили интерпретатор Scheme с поддержкой хвостовой рекурсии. Позднее Стил показал, что хвостовая рекурсия является следствием естественного способа компиляции вызовов процедур (Steele 1977). Стандарт Scheme IEEE требует, чтобы все реализации Scheme поддерживали хвостовую рекурсию.

если Гвидо застрял в 60-х, это его проблемы.

Для CPU это НОВЫЙ код, со всеми вытекающими, ибо CPU не в курсе про ФП.

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

если Гвидо застрял в 60-х, это его проблемы.

Ну и кому нах нужна твоя говносхема? Кого волнует мнение ламеров Стила и Сассмана?

Особенно со стеком из библиотеки коллекций и горой вызовов, иногда виртуальных

Вертихуев признался, что стек на chunk-ах реализовывать не умеет. Так и запишем!

Будет быстрее аппаратного стека? Наверное ядро можно ускорить в 10 раз (tm)

Будет быстрее аппаратного стека?

Не исключено, особенно если это Java (чем больше стек, тем дольше stop the world от GC).

Ты слился, не пиши чепухи в следующий раз

Че?!? Вот прикинь, начнут люди на Си писать рассчитывая на наличие TCO в компиляторе. Тогда их код точно так же не будет работать там, где такой говнооптимизации нет.

да пусть начинают! Они уже 40 лет быдлокод тормозной и глючный пишут, а потом его часами дебажут, доставляя костыли по мере надобности там и сям. Пойми простую вещь: не знаю как в пайтоне (судя по словам Гвидо - плохо), но в Си можно с лёгкостью отследить, рушит семантику ХР или не рушит. А если таки рушит, компилятор её тупо не будет делать. Вот и всё. Говнокод будет работать, хотя и медленно, впрочем как обычно, а всякие деятели будут его дебажить, не понимая, что они сделали не так(на уровне сишечки это незаметно ессно, нужно на машинный код смотреть, но куда уж!)

никакой компилятор C никакого TCO не сделает. Так что никто и не будет писать говнокод, рассчитывая на такое поведение.

будет. Примеры см. выше - дебажить проще, костыли подставлять тоже проще. А медленный код из-за говнокомпилятора и говноязычка. Вот в схеме _обязано_ ТСО.

Вообще говоря, хвостовая рекурсия практически эквивалентна циклу

Еще один, путающий хвостовые вызовы вообще с хвостовой рекурсией в частности. Откуда тут столько ламья?!?

хвостовой вызов вообще - общий случай ХР. Я их не путаю, просто на примере ХР всё наглядно и понятно, в отличие от хвостового вызова. Пример «хвостового вызова вообще» тоже можно _придумать_, но что он даёт нового по сравнению с хвостовым вызовом этой же функции? Ты думаешь, я ламо, и чего-то не вижу? Ну расскажи, раз такой умный.

Тривиальные случаи вообще никого не колышат. Не интересно.

нетривиальные случаи ничего существенного не дают.

Говнофункциональщики-то требуют гарантированной оптимизации всех хвостовых вызовов. Потому как вся эта мразь любит всякий там CPS применять, например. И рекурсия тут только жалкий и не представляющий практического интереса частный случай.

А у говнофункциональщиков больше и нет ничего, кроме функций. Ну нет в ФП циклов. У них цикл == хвостовая рекурсия (в самом примитивном варианте). Не, понятно, что while(true); нафиг не нужно в чистом виде, но для нас важно то, что это полностью «эквивалентно» (с т.з. математика) конструкции

int foo(int x){ return foo(x); }

У них цикл == хвостовая рекурсия

В сверхкастомном варианте, а так нужно пользоваться ФВП

Как раз таки всяческие варианты рекурсивного обхода дерева к хвостовой рекурсии в общем виде и не сводятся практически никогда.

да ладно! Вот центрированный обход: посетить левое поддерево - посетить корень - посетить правое поддерево. Специально для тебя выделил ХР.

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

нет. Ибо

1. железный стек всё равно быстрее.

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

3. высота более-менее сбалансированного дерева растёт пропорционально логарифму, а это очень медленно. Подумай сам: сможешь найти 128 ячеек для стека, под дерево в 18 446 744 073 709 551 616 элементов? Что тебя больше волнует - само дерево, или стек? А если дерево не сбалансировано, то тебе твоя куча не поможет, ибо во первых и она не резиновая, а во вторых, ты не доживёшь до завершения операции.

А вот хвостовой рекурсии ни в одном из этих алгоритмов-то и нету!

есть. Но в паре(как минимум) с обычной.

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

он не хвостовой, а вполне циклический. Ну и он никому нафиг не сдался сам по себе.

1. тебе нужно найти не только конкретный узел, а некое множество узлов, ибо в противном случае выгоднее юзать хеш, а не дерево. Спуститься-то ты сможешь, но вернуться - уже нет. Стека нет, и КУДА возвращаться - неясно.

2. А если не нашёл? Надо вставить, ваш К.О. А может и удалить, если нашёл. Однако, структура порушится, и придётся возвращаться, её исправляя.

Если код написан в стиле использования иммутабельных данных, то while ясное дело будет выходить за пределы стиля,

этого не понял. что за стиль-то?

31. Довольно долго считалось, что хвостовая рекурсия — особый трюк в оптимизирующих компиляторах. Ясное семантическое основание хвостовой рекурсии было найдено Карлом Хьюиттом (Hewitt 1977), который выразил ее в терминах модели вычислений с помощью «передачи сообщений» (мы рассмотрим эту модель в главе 3).

а ты главу 3 прочитал? Вот почитай. А потом задумайся о том, ЗАЧЕМ ограничивать себя такими ограничениями, как это сделал твой Хьюитт? Для упрощения анализа? Принято. А куда ты со своим упрощённым анализом в продакшен лезешь? Даже подход «метод тыка с дебагером в руках» и то даёт IRL лучший результат. Догадываешься почему?

если Гвидо застрял в 60-х, это его проблемы.

не. он главу 3 читал, в отличие от.

хвостовой вызов вообще - общий случай ХР

Чего? Хвостовой вызов вообще совершенно не обязательно рекурсивный.

Я их не путаю, просто на примере ХР всё наглядно и понятно, в отличие от хвостового вызова.

Да куда уж проще-то? Просто последовательность вызовов. Смотри сюда:

http://en.wikipedia.org/wiki/Continuation-passing_style

нетривиальные случаи ничего существенного не дают.

Нетривиальные случаи - это CPS, это всякий там functional reactive programming, который теперь зачем-то тащат даже в шарп.

Ну нет в ФП циклов.

Да что ты к циклу-то прицепился, как будто никаких других видов control flow не знаешь?!?

Кстати, все это говно функциональное еще и тем плохо, что CFG запросто получается irreducible, что невозможно при следовании правилам структурного программирования. Вызов функции, получается, по опасности эквивалентен goto, позволяет такую же бесформенную лапшу делать.

Не нарывайся, вертихуев.