хвостато-рекурсивные функции в монадах

[lomeo]

Когда мы пишем монадическую функцию с хвостовой рекурсией, то явно эта функция не хвостато-рекурсивная:

loop = do
    cmd <- getLine
    if (cmd == ":q")
        then return ()
        else loop

Например, эта функция выглядит как

loop = getLine >>= \cmd ->
    if (cmd == ":q")
        then return ()
        else loop

Я здесь хвостатости не вижу. Я предполагаю, что реализация (>>=) такова, что bind переводит запись c foo = m >>= foo в хвостовую рекурсию.

Чтобы было ясно, что я имею в виду:

instance Monad Identity where
    return a = Identity a
    m >>= k  = k (runIdentity m)

Откуда следует, что f = m >>= f преобразуется в f = f (runIndentity m). Но, с другой стороны, это только в случае инлайна будет возможна такая оптимизация. И фиг знает, что там с другими монадами. Полагаю, что их тоже можно развернуть в хвостатую запись. Может быть кто нибудь поможет с объяснением или ссылкой - почему так? Может быть на это влияет семантика монад, в частности то, что в m >>= f f не будет выполнено до тех пор, пока не будет выполнен m.

Кто подскажет?

Comments

[rvp74.livejournal.com]

Может стоит вопрос поставить иначе: возможен ли тут memory leak?

[lomeo.livejournal.com]

Без проблем, давай так вопрос поставим :-)
Возможен тут меморилик? Нет? Почему нет?

[rvp74.livejournal.com]

считай что оператор (>>=) конструирует замыкание, которое когда будет запущенно сначала вызывает левую часть. Потом вызывает правую часть, которая просто возвратит новое замыкание. И дальше управление будет передано ему. Это и будет хвостовая рекурсия, поскольку возвращается тот же объект-замыкание

[rvp74.livejournal.com]

Мой тебе совет. Возьми ocaml или lisp и реализуй свой монаду. Эти вопросы исчезнуть.
У меня монада была реализована как замыкание. Насколько я помню IO реализованна так же.

[lomeo.livejournal.com]

Спасибо, хороший совет, так и сделаю.

[lomeo.livejournal.com]

Переписал монады на схему, без подмешивание ленивости не получается сделать вечный цикл.
Хорошо, не поленился добавил лени :-) Работает, хвала всевышнему.

теперь получается что то вроде (словами Хаскеля)

loop = delay (\world -> 
    let (value, next_world) = (force (write 5)) world)
     in (force loop) next_world

Ну, это больше похоже на хвостовую рекурсию. Особенно в Haskell это выльется loop world = let .. in loop next_world.
С IO разобрался, хорошо. Но неужели мне так со всеми монадами надо разбираться, чтобы понять? Должно же быть где то теоретическое обоснование! Какое то простое объяснение, следующее из закона монад или ещё что...

[rvp74.livejournal.com]

Для для каждого вида монады надо отдельный подход. В случае List Monad будет все по другому:

leak = do {a <- [1,2,3] ; leak }


Не проверял. Но думаю, 100% будет утечка.

[rvp74.livejournal.com]

хм, этот код странно себя ведет:
leak !! 1000 замерает. На Сtrl-C не реагирует.

А вот код leak arg = do { a <- [1,2,3]; leak a }
как раз ведет себя как и ожидалось:
stack overflow на leak 1 !! 1000

[lomeo.livejournal.com]

Понял, значит моё предположение о принадлежности этого свойства всем монадам неверно.

Надо будет поглядеть насчёт списков внимательнее, а то я не пойму ни фига - с чего это leak без аргументов не течёт

[rvp74.livejournal.com]

Не течет потому что ghci на leak !! 1000 ничего не делает (загрузка ЦП 0%).
Может deadlock какой случился с ghci? :)

[rvp74.livejournal.com]

leak = leak ++ (leak ++ leak)

это после инлайнинга. Это выражение тоже ничего не делает, когда запускаю leak !! 1000

[thesz.livejournal.com]

Обычно советуют инлайнить >>= и return.

Поэтому проблем не возникает. Обычно. ;)

[lomeo.livejournal.com]

Где советуют? Я найти не могу просто, потому и спрашивал.

[thesz.livejournal.com]

Советуют в главе GHC User's Guide про оптимизацию программ - Quicker, faster, smaller. В районе прагмы inline.

[rvp74.livejournal.com]

инлайнить не обязательно. Так как утечки и так не будет

[thesz.livejournal.com]

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

[lomeo.livejournal.com]

А разве в данном случае это не одно и тоже? Утечка же не только по хипу бывает, но и по стеку.
(Кстати переписал на схему)

[thesz.livejournal.com]

Утечка памяти может изменить показатель степени в O(N^m) времени работы программы.

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

[lomeo.livejournal.com]

Прикольно! Это с чем связано, не пойму? Или это аппроксимация опытной оценки?

[thesz.livejournal.com]

Хип растет, время на его сканирование тоже. Вот и получается сумма арифметической прогрессии.

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

У меня получилась сложность вроде такой: время симуляции в секундах T=2e-7*N²+0.00015*N+5. N - количество эмулируемых тиков. T(1000) = 5.35, а вот T(100000) = 2020, 34 минуты.

Неприятно, но жить можно и времени заниматься уже нет. :(

[rvp74.livejournal.com]

http://rvp74.livejournal.com/31500.html
Я добавил там кое-что по мотивам этого треда. ;)

[lomeo.livejournal.com]

Ага, вижу :-)