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

высота более-менее сбалансированного дерева растёт пропорционально логарифму

А какого лешего должно быть «сбалансированным», например, parse tree?

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

да, но согласись, вероятность успеха тут будет таки меньше, чем вероятность «прыгнуть на 10 байт назад». То, что было 10 байт назад таки ближе и роднее. К тому-же, код должен влезть в _одну_ линию кеша, которая обычно всего 64 байта. Если у нас цикл, то в 64и байта влезет даже довольно сложный цикл, но если это рекурсия, то в 64и байта нужно впихнуть _всю_ функцию.

А больше всех в пролете тут оказывается OOP с его обилием виртуальных вызовов.

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

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

покажи как ты считаешь сумму чисел от 1 до N? Я вот так:

int sum = 0;
for(int j = 1; j <= N; j++)
    sum += j;

Полагаю, он сейчас какое-то тошнотворное функциональное говно предложит, вроде

foldl (+) 0 [0 .. N]

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

и я о том: рекурсия - важный частный случай.

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

facepalm

(define (factorial& n k)
 (=& n 0 (lambda (b)
          (if b                    ; growing continuation
              (k 1)                ; in the recursive call
              (-& n 1 (lambda (nm1)
                       (factorial& nm1 (lambda (f)
                                        (*& n f k)))))))))

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

сабж и есть цикл.

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

хуже ИМХО. лапша с goto хотя-бы автору понятна (на этапе написания конечно).

это ты мне предлагаешь столько НЁХ писать, что-бы факториал вычислить? Зачем? Хвастать перед другими задротами?

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

А функциональщики вот CPS обожают. Они так не руками пишут, конечно же, а кодогенераторами убогими. Зачем - не знаю, чего-то бздят про functional reactive programming. Но достали!

сабж и есть цикл.

Опять. Сабж может запросто сводиться к irreducible CFG. Цикл же всегда reducible.

А какого лешего должно быть «сбалансированным», например, parse tree?

ЕМНИП вполне можно доказать, что размер parse tree не более того, что парсится помноженное на константу(потому размер его небольшой). Такое дерево делать на своём велосипедном стеке есть смысл разве что если не получилось доказать, что его высота не может быть слишком большой.

На что? )))

(0 to N).sum ?

n*(n-1)/2

спасибо, я тоже учился в школе. Эту формулу помню.

Ну распарсь (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((1))))))))))))))))))))))))))))))))))))))))))))))))))))))))))

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

судя по коду, который ты привёл, - не помнишь.

Гаусс, выйди из класса и не мешай остальным детям учиться!

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

почему? пусть будет ещё один детектор быдлокодера...

А функциональщики вот CPS обожают. Они так не руками пишут, конечно же, а кодогенераторами убогими. Зачем - не знаю, чего-то бздят про functional reactive programming. Но достали!

хм... а мне вот наоборот интересно... Лишь-бы в продакшен не лезли...

Ну распарсь (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((1)))))))))))))))))))))))))))))))))))))))))))))))))))))))))) Глубина дерева будет почти половина от длины строки. А строка может быть сколь угодно длинной.

ага. как раз тот случай, когда есть смысл оптимизировать быдлокод - никому не нужные быдлоданные. Ты IRL такое видел? Любой нормальный _человек_ тупо запутается в этих скобках. А если какой-то говноалгоритм такое генерит, то яйца аффтора этого алгоритма нужно заменить на единичку, а скобки - на тиски, затянутые на соответствующее число оборотов. (:

судя по коду, который ты привёл, - не помнишь.

помню. Именно потому и код такой - ибо функциональщики сейчас родят какую-то НЁХ, работу которой я хотя-бы проверить смогу.

Ты IRL такое видел?

В каждом втором говно-XML такое. Я уж не говорю про всякие бинарные форматы.

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

В каждом втором говно-XML такое. Я уж не говорю про всякие бинарные форматы.

зачем ты парсишь говноXMLи и придумываешь бинарные велосипеды? Может ты Леннарт? Тогда отсылаю 100500 лучей поноса тебе лично (: А иначе - юзай готовые либы, коих уже Over9000.

Кроме того, парсер не имеет права падать по stack overflow - иначе возможны всякие нехорошие варианты атаки.

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

зачем ты парсишь говноXMLи

Затем, что они есть.

и придумываешь бинарные велосипеды?

Я их не придумываю, они есть и их надо парсить.

А иначе - юзай готовые либы, коих уже Over9000.

Але, дятел, после парсинга с деревом что делать будешь? Естественно писать парсер XML никто не станет, их полно готовых (в том числе и хороших, со стеком на кучке).

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

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

Я их не придумываю, они есть и их надо парсить.

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

Але, дятел, после парсинга с деревом что делать будешь? Естественно писать парсер XML никто не станет, их полно готовых (в том числе и хороших, со стеком на кучке).

откуда я знаю, что ты там делаешь?

Ну и как ты, дятел, платформонезависимо определишь, сколько раз можно входить безнаказанно?

в точности также, как и размер кучи - никак.

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

ну. Будет у тебя #define MAX_STACK 100500, и чем это лучше моего #define? Поверь - ничем.

И да, отстань от парсера, дятел - я их не пишу. Потому ты конечно их пишешь круче.

если ты хочешь от функциональщиков редуцирование списка значений то получишь простой (p)?fold(l|r), который является обычной ФВП. Причём конкретная функция будет зависеть от контекста, для твоего случая это будет foldr (+) 0 [1..N], ну или foldl' (+) [1..N] 0.

Причем как обычно возникает вопрос чего ты пытаешься добиться этим вопросом?

а какая сука их придумывает

Да тысячи их было, на последние лет 40-50.

Может ей взять, и уеб...?

Я давно мечтаю о третьей мировой войне. Но пока что-то не получается.

откуда я знаю, что ты там делаешь?

Знаешь, как тут не знать-то. Обычно дерево потом обходить приходится. Рекурсивно. И не один раз. Возможно, переписывая во что-то другое по ходу дела. Или просто банальный depth-first поиск. В любом случае, «готовым» воспользоваться нельзя. Надо писать свой обход дерева, и при этом понимать, что системным стеком лучше не пользоваться, и что любая рекурсия суть есть мразь и сука, и связываться с рекурсией уважающий себя программист не станет никогда.

в точности также, как и размер кучи - никак.

Размер кучи всегда намного больше чем размер стека. С самодельным стеком мы можем определить заранее, получилось ли выделить нужную глубину, или сразу отваливаться.

ну. Будет у тебя #define MAX_STACK 100500, и чем это лучше моего #define? Поверь - ничем.

Тем, что я могу сказать malloc(sizeof(stack_node_t)*MAX_STACK) и точно знать, получилось ли получить нужный кусок кучи.

отстань от парсера, дятел - я их не пишу

И их тоже не пишу. Но я использую результат работы парсера. А это практически всегда рекурсивный обход дерева.

Причем как обычно возникает вопрос чего ты пытаешься добиться этим вопросом?

что из этого родит компилятор схемы?

компилятор схемы наверное выругается и сдохнет, а вот ghc выдаст нечто вроде такого: http://bpaste.net/show/57951/ (без оптимизаций). Только дальше то что?

т.е. надеюсь ты понимаешь разницу в языках и то, что будет «изкоробки» в программе на haskell и что будет в программе на си. И понимаешь задачи какого уровня надо, а какого не надо сравнивать.

нет. я не знал, не знаю, и похоже не узнаю, за кой хрен городить антиоптимизацию в надежде, что мой цикл завёрнутый в ХР компилятор развернёт обратно в цикл. Ты можешь сказать ЗАЧЕМ заворачивать цикл в ХР? Зачем его обратно разворачивать - мне понятно.

При чем тут ХР, дурилка? TCO - это не только XP. TCO оптимизирует вызовы _любой функции_. TCO - значит не хранить в стеке информацию, которая уже не понадобится по ходу выполнения программы.

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

Тогда вообще никаких оптимизаций по использованию памяти делать нельзя. Т.к. до оптимизации программа упадет из-за нехватки памяти, а после - не упавдет.

сторонники могли-бы привести просто и понятный код, который иллюстрирует нужность ХР, но _никто_ этого сделать не смог, смог только предоставить ссылки на статьи из 100500 бук

ХР делает код более лаконичным. Вот код с ХР:

(define (f x y z) (f (g1 x y z) (g2 x y z) (g3 x y z)))

А вот эквивалентная функция через цикл:

(define (f x y z) 
(= x1 x) 
(= y1 y) 
(= y1 z)
(while #t
  (= x2 x1)  
  (= y2 y1)
  (= z2 z1)
  (= x1 (g1 x2 y2 z2))
  (= y1 (g2 x2 y2 z2))
  (= z1 (g3 x2 y2 z2))))

Размер кучи всегда намного больше чем размер стека. С самодельным стеком мы можем определить заранее, получилось ли выделить нужную глубину, или сразу отваливаться.

к сожалению, это как раз не так: например на архитектуре x86 мы можем хоть и криво-костыльно но задать/узнать размер стека, а размер памяти в куче узнать мы не можем - если попросить Over9000 мб памяти, система их даст. Виртуальных. О том, что их НЕТ, мы узнаем ВНЕЗАПНО. А то, что в куче больше - дык то не принципиально - кривой быдлокод пожрёт _любое_ количество памяти.

И их тоже не пишу. Но я использую результат работы парсера. А это практически всегда рекурсивный обход дерева.

это особый, частный случай дерева.

А вообще - стек реализован на аппаратном уровне, со всеми плюсами и минусами. Основной плюс - оно тупо БЫСТРЕЕ. Но, таки меньше. И это не баг, а фича, если сделать большой стек, он будет ничем не лучше кучи. Ну а деревья в явном виде обычно используются для того, что-бы реализовывать древовидные структуры, т.е. такие, которые подразумевают наличие более одного потомка у каждого узла. Иначе это скорее список, а не дерево. Потому вырождение дерево в список - это плохо, и не только и не столько потому, что стека не хватает.

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

рекурсия для программиста == водка для русского. Личинкам программиста нельзя использовать рекурсию, и больным людям - тоже нельзя. И ещё есть фанатики трезвого образа жизни. Сам догадываешься - фанатизм это плохо. Всегда. И с рекурсией тем более.

И да, рекурсия затягивает тем, что кажешься крутым и всесильным. Как и от водки. И как и от водки - это только кажется. Такие дела.

Что вы все прицепились к этой рекурсией и носитесь с ней. Кого-то внезапно сделала всесильным, а у кого-то - гарант быдлокода. Жесть

компилятор схемы наверное выругается и сдохнет, а вот ghc выдаст нечто вроде такого: http://bpaste.net/show/57951/ (без оптимизаций).

мне хочется с оптимизацией.

Только дальше то что?

то, что это называется «через жопу», уж извини.

Вот тебе пример вычисления факториала:

int fac_times (int n, int acc) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}
 
int factorial (int n) {
    return fac_times (n, 1);
}

любопытно, что gcc умудрился таки распарсить данную НЁХ(оставил только 1 цикл), вот только проще повесится, чем поддерживать ТАКОЙ код.

а размер памяти в куче узнать мы не можем - если попросить Over9000 мб памяти, система их даст

Вот не надо заливать-то. У всех приличных прогромистов давно уже свой wrapper поверх malloc, который делает сначала malloc, а потом memset, с отловом соответствующего сигнала.

это особый, частный случай дерева.

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

стек реализован на аппаратном уровне, со всеми плюсами и минусами. Основной плюс - оно тупо БЫСТРЕЕ

Але, приплыли. Даже на x86 он давно уже не такой уж и «аппаратный», инструкция «movl чегой-то, кудай-то(%rsp)» для процессора ничем не отличается от «movl чегой-то, кудай-то(%любойдругойрегистр)», так что выделенный ручками chunk по производительности ничем не будет отличаться от обращений к куску памяти, адресуемому относительно %rsp.

При чем тут ХР, дурилка? TCO - это не только XP. TCO оптимизирует вызовы _любой функции_. TCO - значит не хранить в стеке информацию, которая уже не понадобится по ходу выполнения программы.

ну и зачем писать так, что с виду кажется, что нужно хранить, а на самом деле - не нужно? Давай ещё такой код напишем:

#define true ~false
#define false 17
if(17 != true)
///

а у кого-то - гарант быдлокода

А найди-ка, Вертихуев, хотя бы один пример не-быдлокода, где применялась бы рекурсия. Обломаешься, я гарантирую это.

Все очевидно, что короче. Нет?

нет. Не понял ни того, ни другого.

И да, «короче» не аргумент - синтаксис С позволяет писать любую программу в одну строчку. Ну и что?

Вот не надо заливать-то. У всех приличных прогромистов давно уже свой wrapper поверх malloc, который делает сначала malloc, а потом memset, с отловом соответствующего сигнала.

...в отладочной версии

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

ну это у тебя так. не всем-же парсеры писать?

Але, приплыли. Даже на x86 он давно уже не такой уж и «аппаратный», инструкция «movl чегой-то, кудай-то(%rsp)» для процессора ничем не отличается от «movl чегой-то, кудай-то(%любойдругойрегистр)», так что выделенный ручками chunk по производительности ничем не будет отличаться от обращений к куску памяти, адресуемому относительно %rsp.

1. стек всегда лежит в кеше. А «чё-то где-то» никогда. Во всяком случае нужное тебе начало стека только было вытеснено из кеша твоими нулями, записанными твоим wrapper'ом.

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

А найди-ка, Вертихуев, хотя бы один пример не-быдлокода, где применялась бы рекурсия. Обломаешься, я гарантирую это.

что-то вроде

void del_tree(node *n)
{
  if(n)
  {
    del_tree(n->left);
    del_tree(n->right);
  }
  free(n);
}

не катит?

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

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

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

После этого я перестал воспринимать разговор серьезно, тут уже не вылечишь.

А после фразы про рекурсию и водку ты никого не перестал воспринимать всерьез?

Вообще да, это тоже был facepalm

мне хочется с оптимизацией.

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

то, что это называется «через жопу», уж извини.

через жопу это твой ход мысли.

любопытно, что gcc умудрился таки распарсить данную НЁХ(оставил только 1 цикл), вот только проще повесится, чем поддерживать ТАКОЙ код.

ты вообще о чём? У тебя в голове мысли последовательность мышления примерно такая: http://tinyurl.com/bw2l49u

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

...в отладочной версии

Нет, конечно же. В релизе. Например, во всей embedded разработке это обязательное требование.

ну это у тебя так. не всем-же парсеры писать?

Я парсеры не пишу, я получаю дерево от готового XML-парсера. И это делают если не все, то подавляющее большинство. Других применений деревьям в современном программировании нет.

1. стек всегда лежит в кеше. А «чё-то где-то» никогда.

Какая редкостная, незамутненная чушь! Кешу плевать, что фетчить - для него все регистры абсолютно равноправны.

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

Их до хера, на самом деле, и аллокатор их прекрасно раздает.

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

не катит?

Не катит. Быдлокод.

тред вошел в хвостовую... ))

покажи как ты считаешь сумму чисел от 1 до N?

sum(xrange(N))

Вот тебе пример вычисления факториала:

отличный пример кстати, при n==-1 в дебаге он упадет, а в релизе (для gcc) - зависнет

Кстати, может кто подробнее объяснить, в чём эти ограничения JVM, и почему scala не может их в полной мере обойти?

Желательно чтобы мне не пришлось досконально изучать как устроен этот JVM, java компилятор и т.п. %)

в чём эти ограничения JVM

Не существует способа сказать VM, что вызов должен быть хвостовым (т.е., stack frame текущего метода должен быть уничтожен). В .NET для этих целей есть префикс-инструкция .tail.

А после фразы про рекурсию и водку ты никого не перестал воспринимать всерьез?

а ты после этой фразы разве не понял, что посты на ЛОРе, это не резюме?