как устроена память в хаскеле?
Да есть такие книги.
функциональное программирование филд харрисон
Окасаки - функциональные структуры данных.
функциональное программирование филд харрисон
Окасаки - функциональные структуры данных.
Список - это структура данных с доступом O(N так что странно ожидать от нее свойств массива.
Я бы на твоём месте не надеялся в хаскеле знать точно как всё это будет выглядеть в машинных кодах. Это может сильно зависеть от компилятора.
Про Хаскель вроде известно, какой там алгоритм - граф редакшн, если не ошибаюсь.
а это разве не зависит от компилятора?
в каком-то компиляторе есть всякие умные оптимизации, а в каком-то нет
в каком-то компиляторе есть всякие умные оптимизации, а в каком-то нет
Рекомендую статью SPJ "Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine".
функциональное программирование филд харрисонТам же не про хаскель, а в строгих языках рантайм иначе устроен.
Окасаки - функциональные структуры данных.
а это разве не зависит от компилятора?А сейчас фактически компилятор один - GHC, остальные либо отсталые, либо сырые.
Там же не про хаскель, а в строгих языках рантайм иначе устроен.Ты ее читал? Она по предшественнику Хаскеля написана и проблемы ленивости там подробно описаны.
проблемы ленивостиЧто за проблемы? Ленивость является одной из возможных стратегий бета-редукции, всё делается компилятором и рантайм тут сбоку.
О чем твой пост? Попробуй написать компилятор для ленивого языка и сразу увидишь в чем проблемы.
Спасибо за ссылку на книгу ФП, не читал её раньше. В ней описано в деталях то же самое, на что уже указал.
Вне зависимотри от стратегии редукции (грубо говоря фронт-энд для компилятора видом intermediate representation для бэк-энда компилятора является нетипизированное нередуцируемое лямбда-выражение, где порядок аппликаций у тебя строго определён. Соответственно говорить о сохранении понятия ленивости в рантайме мне кажется странным, так как свойство ленивости исчезает уже в intermediate representation. Если в чём-то ошибаюсь, поправь, буду рад.
Вне зависимотри от стратегии редукции (грубо говоря фронт-энд для компилятора видом intermediate representation для бэк-энда компилятора является нетипизированное нередуцируемое лямбда-выражение, где порядок аппликаций у тебя строго определён. Соответственно говорить о сохранении понятия ленивости в рантайме мне кажется странным, так как свойство ленивости исчезает уже в intermediate representation. Если в чём-то ошибаюсь, поправь, буду рад.
Как оно исчезает? Заранее нельзя выяснить насколько выражение должно быть вычислено, поэтому на этапе выполнения ленивость языка играет определяющую роль - например надо уметь избегать повторных вычислений одного выражения. Т.е. с научной точки зрения ты прав, но с практической нет, эффективный компилятор ленивого языка сделать нетривиально, собственно полкниги этому и посвящено.
Как оно исчезает?я, конечно, не знаю, как оно всё внутри устроено, иначе бы и не спрашивал. Но здравый смысл подсказывает, что любое ленивое вычисление можно превратить в неленивое добавлением условного оператора (а если нужно вычислить, то вычислить). Вполне логично, что в промежуточной форме всю ленивость уберут. А в завершающей форме и вовсе получится императивная программа.
По поводу книжек - я читал какую-то статью, где описывалось как сделать циклический список путём создания рекурсивной бесконечной структуры и прочие приёмы ленивости. Приёмы я усвоил, но всё не же оказался недостаточно чистым и мне захотелось понять, не только какой будет результат использования ленивых структур, что не зависит от реализации, но и как и с какими затратами он будет достигнут. Куда и в какой момент девается память. Что остаётся в кеше и пригодно для повторного использования, что вычислять приходится заново?
Предложенное тут я посмотрю и позже напишу насколько оно оказалось полезным
функциональное программирование филд харрисона кто может поделиться сабжем в электронной форме? Я, конечно, сам ищу сейчас, но как-то малопродуктивно
upd: нашёл, но на русском. На английском так и не нашёл
Окасаки - функциональные структуры данных.почитал. Понимания не добавилось ни на грамм. Во-первых, там не про хаскель, а про язык с явной ленивостью. Я же как раз не разобрался с процессом трансляции из неявных форм в явные, который в хаскеле проходит за кулисами. Во-вторых, собственно структур практически нет, зато есть десяток методов приближённой оценки производительности, которые были порождены для формализации решения достаточно очевидной на трезвый взгляд проблемы: ленивые структуры могут вычисляться частично, а могут и быть повторно использованы благодаря мемоизации (чем-то напоминает кеширование). Практически та же самая проблема, что и с вычислением потребляемой программой памяти, когда эта программ юзает динамическую линковку. И проблема очевидные, и подходы к решению путём добавления оценочных костылей тоже скучны, неизящно прямы и очевидны, и всё равно ясно, что нормального решения нет.
Та же самая мемоизация - непонятна мне стратегия хранения данных. Возвращаясь к теме, затронутой в первом посту
( ! 2) = head . tail . tail
( ! 4) = head . tail . tail . tail . tail
( ! 1) = head . tail
Если мы вычислили (! 2 взяв два раза tail, значит ли это, что в (! 4) эти данные будут запомнены и использованы?
Опять же tail для (! 1) был получен в результате промежуточных вычислений (! 2). Будут они закешированы или нет?
что кешировать то, два перехода по ссылке 
перевычисляться элементы списка конешно же не будут, но хранить в голове какой элемент 2-ой это как-то странно.
перевычисляться элементы списка конешно же не будут, но хранить в голове какой элемент 2-ой это как-то странно.Как я понимаю происходящее (могу серьёзно заблуждаться).
Результаты вычислений не "кэшируются", но сохраняются в thunk'e. Т.е. если ты одним и тем же thunk'ом воспользуешься два раза, то второй раз будет использован результат, вычисленный в первый раз. Если же ты создашь второй thunk, пусть даже синтаксически эквивалентный первому, он будем вычисляться по новой при необходимости.
Результаты вычислений не "кэшируются", но сохраняются в thunk'e. Т.е. если ты одним и тем же thunk'ом воспользуешься два раза, то второй раз будет использован результат, вычисленный в первый раз. Если же ты создашь второй thunk, пусть даже синтаксически эквивалентный первому, он будем вычисляться по новой при необходимости.
По-моему, ты понимаешь совершенно правильно. Хотя я тоже могу заблуждаться!
Однако прочтённая RWH, разные статьи про оптимизацию их GC и собственные эксперименты в общем говорят именно так: никакой "деленивизации" там не происходит, thunks второй раз не эвалюируются конечно, но и попыток найти и соптимизить структурно эквивалентные куски тоже не предпринимается, ну и вообще, передний край оптимизации сейчас состоит в loop fusion (или как там его) — это когда, в питоновских/шарповских терминах, у тебя есть несколько вложенных генераторов и результаты работы прокидываются по цепочке через стек, а не выделяются на хипе. То есть до sufficiently clever compiler, который мог бы делать с кодом что-то нетривиальное, ещё очень далеко, и задумываться об этом пока совершенно не нужно.
О чём, наверное, следует задумываться — это о том, почему foldr может работать за О(1) по памяти. В отличие от foldl (вместо которого следует использовать foldl', который тоже может работать за О(1) по памяти, но в других случаях).
Однако прочтённая RWH, разные статьи про оптимизацию их GC и собственные эксперименты в общем говорят именно так: никакой "деленивизации" там не происходит, thunks второй раз не эвалюируются конечно, но и попыток найти и соптимизить структурно эквивалентные куски тоже не предпринимается, ну и вообще, передний край оптимизации сейчас состоит в loop fusion (или как там его) — это когда, в питоновских/шарповских терминах, у тебя есть несколько вложенных генераторов и результаты работы прокидываются по цепочке через стек, а не выделяются на хипе. То есть до sufficiently clever compiler, который мог бы делать с кодом что-то нетривиальное, ещё очень далеко, и задумываться об этом пока совершенно не нужно.
О чём, наверное, следует задумываться — это о том, почему foldr может работать за О(1) по памяти. В отличие от foldl (вместо которого следует использовать foldl', который тоже может работать за О(1) по памяти, но в других случаях).
В упомятуной мной статье как раз про санки подробно понаписано. Самомодифицирующийся код по-сути. Помощь рантайма нужна как раз для кэширования вычисленных значений и понимания где вычисленные, а где нет. В тэглесс случае сделано довольно красиво - без if'ов. Если не кэшировать, то это call by name, который действительно можно скомпилить в ту же семантику, что и строгий язык. Вот пример такой компиляции, где один и тот же ФЯ компилируется строго или лениво в один и тот же IR (по ссылке ближе к концу поста):
http://thedeemon.livejournal.com/13078.html
B GHC в режиме с оптимизацией еще активно работает анализатор строгости, который по возможности ищет, что можно выполнить нелениво, и делает это. Например, при простой компиляции sum [1..10000000] создает в памяти десять мильонов невычисленных санков, а потом их сворачивает, но при -O2 этого уже не происходит.
http://thedeemon.livejournal.com/13078.html
B GHC в режиме с оптимизацией еще активно работает анализатор строгости, который по возможности ищет, что можно выполнить нелениво, и делает это. Например, при простой компиляции sum [1..10000000] создает в памяти десять мильонов невычисленных санков, а потом их сворачивает, но при -O2 этого уже не происходит.
Оставить комментарий
yroslavasako
В учебных целях написал несколько вычислительных программ на хаскеле. Что касается концепций ФП - тут всё ясно. Но ведь вычислительные проги обязаны быть быстрыми. А вот в рантайме хаскеля я нифига не понимаю. Есть какая книжка, чтобы полноценно с этим разобраться можно было? Вот например такой вопрос - я хочу получить i-ый элемент списка. (a ! i) Допустим я его получил. Как правило это значит, что где-то остался и хвост списка. Если мне нужно будет получить i+k элемент списка - список будет прокручиваться с начала или будет использован хвост, оставшийся от вычисления i го элемента? А i-1 элемент уже будет готов или его тоже нужно будет вычислять заново? Многие алгоритмы любят получать индексированный доступ к данным (особенно в sparse задачах мне пока приходилось переписывать его в некрасивую и плохочитабельную рекурсию, обеспечивающую вычисление данных в один проход потоком - без индексных обращений.Собственно вопрос в рантайм поведении хаскел прог, методов построяния функциональных структур данных, оптимизации вычислений. Как бы всё это узнать подробнее?