Зачем нужна хвостовая рекурсия?

Н*я писать циклы через жопу, если их можно написать напрямую.

Но для этого ведь нужно мутабельное состояние, азазаза.

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

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

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

ну и лох.

/thread

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

То есть это единственная причина — ограничение языка?

Это не ограничение, это наоборот фича

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

Ну да. В том же хаскеле в монадическом коде можно сделать forM/forM_ со всеми плюшками

Например в SICP уделено ей немало, нсмотря на то, что scheme разрешает присваивания

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

Так зачем же она нужна? Дело опять в оптимизации?

В оптимизации. Обход дерева

(define (do-tree tree func)
   (unless (empty tree)
     (func (head tree))
     (do-tree (left tree))
     (do-tree (right tree))))

последний вызов do-tree хвостовой и не занимает стек. Если переписать в виде цикла будет не так красиво

(define (do-tree-loop tree func)
   (until (empty tree)
     (func (head tree))
     (do-tree-loop (left tree))
     (set! tree (right tree))))

С точки зрения разработчиков и большинства пользователей Scheme программа без set! всегда красивее, так как глядя на процедуру можно сразу увидеть ход (workflow) процедуры не прыгая взглядом назад (для цикла дойдя до (set! tree ...) приходится ещё раз посмотреть всё выше для оценки того, как изменится ход программы с новым значением tree.

И все таки, трудно назвать фичей, иммутабельность. Тут, как бы, перворачивается все с ног на голову. Вот например, если есть дрель с перфоратором (с биением), мы могди бы сказать, что дрель без префоратора — это фичастая дрель, а та что с прфорацией — ограничена в своих возможностях, потому что, например, может привести к сколам керамики при сверлении. Очевидно же, что это игра слов. Ведь режим с прфорацией никто не заставляет включать. Это Bondage and Discipline (SM:)) на уровне языка, так это следовало бы называть.

И все таки, трудно назвать фичей, иммутабельность.

Можно ли назвать фичей неиспользование goto? И, соответственно, необходимость конструкций цикла, выхода из середины цикла, группировки команд в условии? С неиспользованием изменения значений переменных аналогично — необходима рекурсия с хвостовой оптимизацией.

Можно ли назвать фичей неиспользование goto?

ИМХО нельзя. Это извращение логики. Фича — это когда что-то есть. Когда этого нет — это отсутствие фичи. То что наличие фичи не всегда хорошо — это уже другой вопрос.

Ну дык иммутабельность и есть фича в том плане, что в тех же плюсах, похапе и руби контроля сайд-эффектов нет, а в хаскеле - есть.

Фича — это когда что-то есть.

Здесь фича — хвостовая рекурсия.

Аналогичный вопрос: зачем конструкции структурного программирования? Как известно, они нужна для того, чтобы структурные переходы превращать в goto. Н*я писать goto через жопу, если их можно написать напрямую. Некоторые утверждают, что, якобы, структурные конструкции — более выразительное средство, чем goto...

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

Фича — это когда что-то есть. Когда этого нет — это отсутствие фичи.

Сталобыть строгая типизация, это отсутствие возможности сложить овец с носорогами (без конверсии), а значит, по вашей логике — отсутствие фичи?

Правильно продуманные искуственные ограничения — это самые крутые фичи.

строгая типизация, это отсутствие возможности сложить овец с носорогами (без конверсии), а значит, по вашей логике — отсутствие фичи?

Ты здесь в чем-то прав :)

И все таки, трудно назвать фичей, иммутабельность.

Для человека, которому в 17 лет не сломали мозг сишечкой, нет такого понятия как «мутабельность» или «переменная».

Тут, как бы, перворачивается все с ног на голову.

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

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

И еще, хвостовые вызовы никакого отношения к циклам не имеют. Про CPS слышал, ничтожество?

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

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

Само сабой, возможность сложить овец с носорогами без конверсии является фичей.

Ты тупое и необразованное говно. Дались тебе, сука, эти циклы? Хвостовой вызов может быть непрямым. Control flow может быть irreducible даже с прямыми вызовами (и все твои гомосяцкие циклы тут же идут в сраку).

Само сабой, возможность сложить овец с носорогами без конверсии является багом

fix

Про «более выразительные» ты где услышал?!? Структурные конструкции порождают только reducible cfg, тогда как с goto или рекурсией элементарно делается irreducible.

«угадай автора по заголовку»

/me выиграл

+1

Хвостовой вызов может быть непрямым

Ну ты и дебил. Хвостовой вызов по определению непрямой, если это н касается примитивных случаев. Любой CPS вызов является непрямым вызовом. Ты просто не понимаешь что такое функция, идиот.

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

Але, упорыш, я выше по треду показал, как даже ПРЯМЫЕ хвостовые вызовы могут вести к непримитивным случаям - то есть, к irreducible cfg.

Любой CPS вызов является непрямым вызовом.

Большая их часть таки потом оптимизируется обратно к прямым, смотри на всяких там Сталинов.

Про «более выразительные» ты где услышал

Там же, где и ТС.

Структурные конструкции порождают только reducible cfg, тогда как с goto или рекурсией элементарно делается irreducible.

Да ну? Ты готов опровергнуть Теорему Бёма — Якопини?

Да ну? Ты готов опровергнуть Теорему Бёма — Якопини?

Ты как-то по своему понимаешь смысл выражения «более выразительно». Так-то что угодно и на брейнфаке написать можно. Irreducible CFG транслируется в reducible путем копирования мешающих блоков. В паталогических случаях код может вырасти на порядок, но зато «структурненько» получится.

Irreducible CFG транслируется в reducible путем копирования мешающих блоков. В паталогических случаях код может вырасти на порядок, но зато «структурненько» получится.

Для этого придумали подпрограммы.

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

(define (get-params list)
  (define a #f)
  (define b #f)
  (define c #f)
  (define d #f)
  (define e #f)
  (dolist (l list)
     (cond
        ((check-a l) (set! a l))
        ((check-b l) (set! b l))
        ((check-c l) (set! c l))
        ((check-d l) (set! d l))
        ((check-e l) (set! e l))))
  (values a b c d e))

(define (get-params list)
  (define (loop list a b c d e)
     (cond
        ((null? list) (values a b c d e))
        ((check-a (car list)) (loop (cdr list) (car list) b c d e))
        ((check-b (car list)) (loop (cdr list) a (car list) c d e))
        ((check-c (car list)) (loop (cdr list) a b (car list) d e))
        ((check-d (car list)) (loop (cdr list) a b c (car list) e))
        ((check-e (car list)) (loop (cdr list) a b c d (car list)))))
  (loop list #f #f #f #f #f))

Так я и говорю, что рекурсия и goto эквивалентны и более выразительны (в смысле компактности кода), чем структурные конструкции. И, да, почти всю мутабельную хрень можно убить SSA-преобразованием и Array SSA, что потом тривиально транслируется в CPS.

Так я и говорю, что рекурсия и goto эквивалентны и более выразительны (в смысле компактности кода), чем структурные конструкции.

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

У тебя не эквивалентное преобразование.

Ghc в общем случае не разворачивает рекурсию в цикл вообще. Если говорить совсем примитивно, то сама программа скомпилированная ghc находится в бесконечном цикле. Функция возвращает продолжение — адрес функции которая будет вызвана следующей в этом бесконечном цикле. Так вот ghc возвращает продолжение для ЛЮБОГО хвостового и не хвостового вызова. Так что в ghc нет особой разницы между хвостовой рекурсией, просто рекурсией или миллионом разнародных хвостовых вызовов.

рекурсия и goto эквивалентны

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

У тебя не эквивалентное преобразование.

Приведи эквивалентное. Можешь считать, что у тебя есть вспомогательные макросы. Запрещён только set! (и любой макрос в него разворачивающийся).

CPS это очень частный случай, а я говорю про банальное преобразование: каждый basic block в отдельную функцию, весь контекст в аргументы функций (заодно все фи уйдут).

Эквивалентно по отсутствию сахара было бы goto, а его в твоем говноязычке нет.

В этом смысле они не эквивалентны. Из рекурсии невозможно выскочить в произвольном месте (если не считать специальных операторов call/cc, reurn и прочее). Рекурсия эквивалнтна goto только с продолжениями.

Из рекурсии невозможно выскочить в произвольном месте (если не считать специальных операторов call/cc, return и прочее).

Эквивалентный алгоритм сделать можно.

(lambda cmd1 ... (if (...) (return 0)) cmd2 ...)

(lambda cmd1 ... (if (...) 0 (begin cmd2 ...)))

Аналогично с любым goto. Вот call/cc или вычисляемый goto нельзя преобразовать.

i = <data set>
while (!computation_complete(i)){
  i = perform_computation(i);
}

def cycle(i) = 
  if (!computation_complete(i))  cycle(perform_computation(i)) 
  else i
cycle(<data set>)

Не вижу фундаментальной разницы и даже темы разговора. Вот показал как формально любой цикл переводится в хвостовую рекурсию и обратно. 4 строчки в 4 строчки. Вместо <data_set> подставьте любой набор переменных.

В качестве бесплатного бонуса получаете возможность написать юнит-тест для одной итерации цикла.

понты

Понты - это когда сложно и поцаны неосилили, а ты осилил. А хвостовая рекурсия - элементарно

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

ФВП не покрывает все, например хвостовая рекурсия или цикл обычно проще когда выполяется математический алгоритм с проверкой точности, например вычисляем корень численным методом (самый тривиальный пример). Количество итераций неизвестно, потому все foldLeft/reduce идут лесом. Максимум, например в Scala, создать Stream и потом takeWhile, но нафиг надо

Н*я писать циклы через жопу, если их можно написать напрямую

потому что не всегда цикл это банальное for(j=0; j<10; j++). Цикл может быть достаточно сложным и не явным, что часто встречается например в DSL. К примеру возьми тот же парсинг HTML, когда теги нужно обрабатывать рекурсивно, однако для процессора удобнее цикл.

Или это просто дешвые понты фп-дрочеров?

не только их. В gcc тоже есть TCO. И оно даже работает.

темы разговора

Ну да, ты выбрал удобный случай. Переведи факториал, хотя бы. Там тривиальщина так и прет.

То есть, фича в иммутабельности, ограничение на циклы — следствие этой фичи, так?

именно так.

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

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

Сталобыть строгая типизация, это отсутствие возможности сложить овец с носорогами (без конверсии), а значит, по вашей логике — отсутствие фичи?

нет. Заборчик на крыше — фича. Хотя он мешает прыгать с крыши. Фича в том, что складывать овец с носорогами не нужно.

Само сабой, возможность сложить овец с носорогами без конверсии является фичей.

проблема в том, что непонятно, что получается в итоге этого действия?

Так я и говорю, что рекурсия и goto эквивалентны и более выразительны

нет. Потому что IRL у тебя не только хвостовая рекурсия. Потому тебе требуется _две_ функции:

1. рекурсивная

2. хвостовая, которую ты развернул

Выразительнее, когда ты одно и то же действие делаешь одной и той же функцией. Если функция ненужна(TCO), то это уже проблема компилятора, её развернуть.

Другое дело что ФВП - намного лучший вариант по сравнению с циклами и хвостовой рекурсие

Трудно себе представить что в общем случае вообще можно писать хвосторекурсивные функции в языке без поддержки ФВП

Не тривиальный, а полностью общий. ПсевдокоТ факториала

f = 1
m = n
while (m != 1){
  f = f*m
  m = m-1
}

def cycle(f, m) = 
  if (m != 1)  cycle(f*m, m-1) 
  else f
cycle(1, n)

Абсолютно формально. Видишь куда переменные переплыли?

<dataset>: f=1, m=n
computation_complete: m==1
perform_computation:  f = f*m, m = m-1

например вычисляем корень численным методом

(define (sqrt-step cur x)
  (/ (+ cur (/ x cur)) 2))

(define (asymptote func test x (a0 1))
  (define r (func a0 x))
  (if (test r) r (asymptote func test x r)))

(define (approx a b eps)
  (define delta (- a b))
  (< (if (positive? delta) delta (- delta)) eps))

(define (sqrt x (eps 0.001))
   (asymptote sqrt-step
              (lambda (y) (approx (* y y) x eps))
              x))

Если считаем, что asymptote — стандартная функция для любых сходящихся рядов, то это решение (через ФВП) красивее, чем явный цикл/рекурсия

Ну естественно я имел ввиду привычные foldLeft/reduce, map, filter. А так конечно, можно написать алгоритм самому (через рекурсию), а потом пользоваться ФВП