?

Log in

No account? Create an account
 

Трамплины и продолжения - swizard

About Трамплины и продолжения

Previous Entry Трамплины и продолжения 27 авг, 2016 @ 06:17 Next Entry
Любопытно, конечно, что наибольшую популярность завоёвывают именно плохие с инженерной точки зрения технологии. Я не могу объяснить этот феномен: казалось бы, согласно эволюционной теории "более лучшие" вещи должны постепенно заменять эквивалентные по функционалу "более худшие", но этого не происходит. И даже не всегда проблема в том, что что-то сложнее, а что-то легче: обычно, в плохо продуманных технологиях сложность как раз выше, просто она "отложенная".

Давайте, например, посмотрим на такие платформы: Common Lisp/Scheme, Haskell или OCaml. А потом на такие: Java или Javascript. В чём разница? Правильно, в одних есть хвостовая рекурсия, в других нет :)

Ладно, на самом деле, большинству программистов наджави эта рекурсия нафиг не сдалась. Полагаю, что многие и не подозревают даже что это такое, и подобное неведение никак не мешает им вполне комфортно существовать на свете. Но оная проблема встаёт достаточно остро для пользователей более вменяемых языков, которые используют джаву или js в качестве бэкенд-платформы. Например, Clojure для jvm или Elm для javascript. Эти языки предполагают функциональную парадигму программирования, и отсутствие TCO при этом причиняет серьёзные неудобства.

Честно говоря, натолкнувшись на переполнение стека в Elm, я был несколько ошарашен. Ничто не предвещает беды, вокруг тепло и уютно: с одной стороны, у тебя почти хаскель, с другой тебе было обещано отсутствие рантайм-исключений (если ты не выходишь за рамки чистого elm). И тут херак, привет из js:

RangeError: Maximum call stack size exceeded

Я поначалу даже растерялся — к такому меня жизнь явно не готовила. Пришлось потратить некоторое количество времени, чтобы разобраться, как в таких случаях следует поступать: ведь никаких специальных технических средств для написания явных циклов руками в ельме нет. Он умеет оптимизировать только самые простые хвостовые вызовы, но любая чуть более сложная рекурсия сразу становится "честной". Поэтому пишу этот материал постфактум в качестве инструкции — мало ли кому ещё поможет.

Итак, давайте рассмотрим следующий синтетический пример:


isEven : Int -> Bool
isEven x =
    case abs x of
        0 -> True
        v -> isOdd <| v - 1


isOdd : Int -> Bool
isOdd x =
    case abs x of
        0 -> False
        v -> isEven <| v - 1


isSumEven : Int -> Int -> Bool
isSumEven a b =
    isEven a == isEven b


Я тут попытался смоделировать проблему: у нас есть две взаимно-рекурсивные функции (определяющие, чётное или нечётное число на входе) и одна утилитарная, которая их как-то использует (предсказывает, будет ли сумма двух чисел чётная).

Можно сразу посмотреть в репле, как они (не) работают:


> isEven 2
True : Bool
> isOdd 13
True : Bool
> isSumEven 100 1
False : Bool
> isEven 100000
RangeError: Maximum call stack size exceeded


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

Общепринятая практика использовать в таких случаях технику, которая называется trampolining. Она широко используется, например, в Clojure. Идея там достаточно простая. Мы рефакторим функции, использующие рекурсию таким образом, чтобы:

  1. во всех местах, где производится рекурсивный вызов, вместо этого возвращалось наружу продолжение (достаточно просто обычного замыкания: thunk)
  2. на самом "верхнем" уровне выполняется обычный тупой цикл (trampoline), который последовательно вызывает отрефакторенную функцию до тех пор, пока она возвращает продолжения

Тем самым все функции перестают быть рекурсивными, и использование стека становится чётко детерминировано: из всех условных веток возвращаются либо результаты, либо замыкания (которые потом будут вызваны из трамплина).

В Elm, оказывается, есть даже микро-пакетик с трамплинами: elm-lang/trampoline. С его помощью можно переписать вышеприведённые взаимно-рекурсивные функции следующим образом:


import Trampoline exposing (Trampoline, done, jump, evaluate)


isEvenTr : Int -> Trampoline Bool
isEvenTr x =
    case abs x of
        0 -> done True
        v -> jump <| \() -> isOddTr <| v - 1


isOddTr : Int -> Trampoline Bool
isOddTr x =
    case abs x of
        0 -> done False
        v -> jump <| \() -> isEvenTr <| v - 1



В данном случае, всё получается достаточно прямолинейно: когда готов результат, возвращаем его через done, а когда нужно выполнить рекурсивный вызов, оборачиваем его в thunk и возвращаем через jump. Соответственно, в пакете trampoline лежит ещё функция evaluate, которая как раз крутит цикл, вызывая по-очереди все возвращаемые продолжения. Проверяем:


> evaluate <| isEvenTr 2
True : Bool
> evaluate <| isOddTr 13
True : Bool
> evaluate <| isOddTr 100000
False : Bool


Да, в этом варианте всё работает!

Кстати, небольшое отступление. Очевидно, что многим (включая меня) может не понравиться, как выглядит вот этот кусок кода:


jump <| \() -> isOddTr <| v - 1


Лично я его автоматически написал сначала так:


jump <| always <| isOddTr <| v - 1


За что был наказан потерянным часом на отладку. Кто может предположить, в чём кроется засада? :) Для справки: always.

Ладно, возвращаемся к примерам. Как написать трамплин-версию isSumEven? В принципе, можно как-то так:


isSumEvenTr : Int -> Int -> Trampoline Bool
isSumEvenTr a b =
    done <| (evaluate <| isEvenTr a) == (evaluate <| isEvenTr b)


Конкретно для этого синтетического примера, наверно, такой вариант особо ничем не плох. Но всё же: можно ли обойтись только одним evaluate? Очевидно, что можно, если получится каким-то образом "попасть внутрь" типа Trampoline a, чтобы достать значение a или, хотя бы, как-то его преобразовать. Но вот незадача: этот тип не является функтором или монадой, никаких соответствующих комбинаторов для него нет, да и вообще это всё страшные слова, и такой мерзости у нас в эльме не водится! Следовательно, единственный вариант — это честно интерпретировать Trampoline a через evaluate. Или нет?

На самом деле, есть способ "состыковать" несколько Trampoline-ов, чтобы выполнить их в одном цикле-эвалюаторе: опять же, CPS. Но для этого нам опять нужно отрефакторить функции, на этот раз в continuation passing style:


isEvenTrK : Int -> (Bool -> Trampoline Bool) -> Trampoline Bool
isEvenTrK x k =
    case abs x of
        0 -> k True
        v -> jump <| \() -> isOddTrK (v - 1) k


isOddTrK : Int -> (Bool -> Trampoline Bool) -> Trampoline Bool
isOddTrK x k =
    case abs x of
        0 -> k False
        v -> jump <| \() -> isEvenTrK (v - 1) k


isSumEvenTrK : Int -> Int -> (Bool -> Trampoline Bool) -> Trampoline Bool
isSumEvenTrK a b k =
    isEvenTrK a <|
        \resultA ->
            jump <| \() -> isEvenTrK b <|
                \resultB ->
                    k <| resultA == resultB



Главное изменение: функции теперь не возвращают результаты напрямую (логически, они уже ничего не должны возвращать), вместо этого они принимают дополнительные параметр: "продолжение", которому этот результат передаётся. Теперь в isEvenTrK появилась возможность состыковать две "затрамплиненные" функции внутри продолжения, при этом сохранив тип возвращаемого значения Trampoline Bool, который уже скармливается единственному evaluate:


> evaluate <| isSumEvenTrK 100000 1 done
False : Bool
> evaluate <| isSumEvenTrK 100000 100000 done
True : Bool


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

Ну, в целом, как-то так. Далее полагается, чтобы я написал какие-то выводы или подытоги, но какие тут могут быть выводы? Сложно, запутанно. Но это и есть та самая "отложенная сложность", про которую я говорил в начале поста. Был бы в вашем джаваскрипте изначально родной TCO, я бы не писал этот текст, а вместо этого сделал бы что-нибудь полезное.
(Оставить комментарий) Страница 1 из 3 - [1] [2] [3]
[User Picture Icon]
From:swizard
Date:Август, 27, 2016 11:08 (UTC)
(Link)
Ну так-то да, по-факту, в пакете elm-lang/trampoline, действительно, не хватает функции "andThen : Trampoline a -> (a -> Trampoline b) -> Trampoline b"

А визуально мимикрировать под монадический интерфейс, кмк, бессмысленно: мы же тем самым не получаем настоящую монаду (которую можно использовать в "do" и комбинаторах), просто вносится дополнительная путаница.
[User Picture Icon]
From:thedeemon
Date:Август, 27, 2016 05:54 (UTC)
(Link)
Интересно, как с этим у PureScript.
[User Picture Icon]
From:kika
Date:Август, 27, 2016 06:54 (UTC)
(Link)
Ну вот, пока я разрабатывал программное обеспечение, уже успели спросить.
Я ниже запостил, а вот программное обеспечение в виде текста:
https://gist.github.com/kika/b3dbba968f52614f71ac89d066723b21

Я что-то подозреваю что это можно гораздо более кратко выразить, но не настоящий сварщик.
[User Picture Icon]
From:kika
Date:Август, 27, 2016 06:52 (UTC)
(Link)
Отличный пост с метавыводом.

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

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



Edited at 2016-08-27 06:56 (UTC)
[User Picture Icon]
From:thedeemon
Date:Август, 27, 2016 07:15 (UTC)
(Link)
Так это дело политическое: введешь монады, отпугнешь пользователей, мейнстримом не станешь. У него отличный доклад был на эту тему - как стать мейнстримом, как не распугать народ. Вот когда в C# они появятся в явном виде (а не только где-то глубоко в семантике LINQ), тогда можно будет.
From:dmzlj
Date:Август, 28, 2016 08:08 (UTC)
(Link)
Концепция TCO для тех людей, которые подобные языки делают - слишком сложна. Но включить в язык бесплатный jump goto по вычисляемому адресу они (censored) могли бы? Тем более, что в любом наборе инструкций оно есть. Кстати, отвественность за отсутствие этого пресловутого вычисляемого goto лежит на самых корифеях. Они бы сделали - остальные бы повторили в своих поделиях. Одна нищасная инструкция... Её отсутствие - такой же фейл, как нулевой указатель Хоара, или даже худший.

Edited at 2016-08-28 08:09 (UTC)
From:all_round_man
Date:Сентябрь, 5, 2016 13:16 (UTC)
(Link)
Согласно эволюционной теории не "более лучшие", а более приспособленные к данной ситуации вытесняют других. Разве у Lisp'а на практике не были в своё время проблемы (пришлось даже пилить лисп-машину), хаскель делали без оглядки на практику, для академических нужд - чего же теперь жаловаться.
From:(Anonymous)
Date:Сентябрь, 27, 2016 17:55 (UTC)

My unfamiliar website

(Link)
My new blog sites
http://hotpic.erolove.in/?post.mariela
guides masturbations preetens pussy arroyo valley high school staff directory sheemale futanaria xxx video free full length sex movies of anjali kara
From:(Anonymous)
Date:Октябрь, 9, 2016 03:20 (UTC)

Public pictures

(Link)
Blog with daily sexy pics updates
http://hotpic.erolove.in/?post-rebeca
tinys black adventures flower dressing room sex assparade compleatly freemp4 porn sex free clips how to know if you have cold feet free big tits porno
From:(Anonymous)
Date:Октябрь, 15, 2016 11:20 (UTC)

New Protrude

(Link)
Sexy looking-glass shots
http://asian.pornstars.sexblog.pw/?tweet-piper
erotic kids dildo sex free pom erotic underwear
From:(Anonymous)
Date:Октябрь, 16, 2016 20:47 (UTC)

Похудеть стало так легко

(Link)
Конфеты для похудения EcoPills Raspberry Похудеть стало так легко
http://offer.moscow/
From:(Anonymous)
Date:Октябрь, 27, 2016 01:14 (UTC)

Grown up galleries

(Link)
Novel devise
http://assjob.tobuy.in/?page.kenya
ponno xxx erotic literature adult erotic fiction define erotic erotic chatting
From:(Anonymous)
Date:Октябрь, 29, 2016 15:03 (UTC)

My brand-new website

(Link)
Started new web project
http://arab.aunties.porndairy.in/?entry.breana
qaddafi tools underwear pronounce pembela
From:(Anonymous)
Date:Декабрь, 20, 2016 09:49 (UTC)

New Protrude

(Link)
Blog about sissy life
are feminine washes good to use see through blouses fashion clothes for boys
http://sissytales.porndairy.in/?post.pamela
sissy chloe bra knickers today a bride free strap on islamic world full names for girls hwo to apply makeup youtube shoes in the sale
From:(Anonymous)
Date:Февраль, 18, 2017 06:42 (UTC)

Latest plat

(Link)
My novel folio
http://arab.girls.tv.yopoint.in/?entry-katelynn
sexiy perfume lifeguard ships robe
From:(Anonymous)
Date:Февраль, 22, 2017 08:01 (UTC)

Бесплатные порно и секс фото галереи

(Link)
Анальный секс, фото галереи анала, секс фото
http://sosushhaja.blondinka.yopoint.in/?post-keila
[User Picture Icon]
From:Azamat Kalimoulline
Date:Март, 28, 2017 13:47 (UTC)
(Link)
В Clojure TCO делается через специальную конструкцию recur.
(Оставить комментарий) Страница 1 из 3 - [1] [2] [3]
Top of Page Разработано LiveJournal.com