![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
О чистоте и лени
После N-ной провальной попытки изучить Haskell и понять суть религии под названием "монадический фетишизм", решил изобрести свой "велосипед", то есть чистый и ленивый язык программирования.
Для любой открытой системы важным моментов является взаимодействие с внешним миром. В данном случаем - порядок обмена информацией.
У энергичных языков порядок определяется непосредственно самой последовательностью инструкций в программе. Напротив, для ленивых языков последовательность выполнения инструкций неопределена, а значения вычисляются по мере необходимости. Поэтому для осуществления взаимодействия с внешним миром в ленивые языки порядок вводиться искусственно.
Одним из способов упорядочивания вычислений является ввод дополнительных переменных-маркеров, при помощи которых указываются дополнительные зависимости между подпрограммами. Например, подпрограмма "C" зависит от переменной "b", которая определяется в подпрограмме "B", в свою очередь подпрограмма "B" зависит от переменной "a", значение которой определяется в подпрограмме "A", что приводит к выполнению сначала подпрограммы "A", затем "B" и лишь затем "C". Эти переменные маркеры в Mozart-OZ получили название свободные (unbound) переменные, а в Clean - уникальные типы.
Другим способом упорядочивание вычислений является использование стиля передачи продолжений. Однако этот стиль труден для использования им требует модификации подпрограмм. К счастью последнего можно избежать при помощи подпрограммы-обертки. В Haskell этой оберткой является оператор bind, а монады по сути не что иное, как своеобразный "концептуальный сахар" над стилем передачи продолжений. В свою очередь Haskell оператор do является "синтаксическим сахаром" вокруг монад, создающих иллюзию того, что переменные меняют свое значение.
Так что на самом деле Haskell, как и Clean, - абсолютно чистый язык, а религия "монадический фетишизм" - удел тех, кто на видеть разницы между иллюзией и реальностью.
P.S.
Во загнул! С другой стороны, что взять с простого физ-химика, волей случая написавшего несколько маленьких программ на Perl.
Для любой открытой системы важным моментов является взаимодействие с внешним миром. В данном случаем - порядок обмена информацией.
У энергичных языков порядок определяется непосредственно самой последовательностью инструкций в программе. Напротив, для ленивых языков последовательность выполнения инструкций неопределена, а значения вычисляются по мере необходимости. Поэтому для осуществления взаимодействия с внешним миром в ленивые языки порядок вводиться искусственно.
Одним из способов упорядочивания вычислений является ввод дополнительных переменных-маркеров, при помощи которых указываются дополнительные зависимости между подпрограммами. Например, подпрограмма "C" зависит от переменной "b", которая определяется в подпрограмме "B", в свою очередь подпрограмма "B" зависит от переменной "a", значение которой определяется в подпрограмме "A", что приводит к выполнению сначала подпрограммы "A", затем "B" и лишь затем "C". Эти переменные маркеры в Mozart-OZ получили название свободные (unbound) переменные, а в Clean - уникальные типы.
Другим способом упорядочивание вычислений является использование стиля передачи продолжений. Однако этот стиль труден для использования им требует модификации подпрограмм. К счастью последнего можно избежать при помощи подпрограммы-обертки. В Haskell этой оберткой является оператор bind, а монады по сути не что иное, как своеобразный "концептуальный сахар" над стилем передачи продолжений. В свою очередь Haskell оператор do является "синтаксическим сахаром" вокруг монад, создающих иллюзию того, что переменные меняют свое значение.
Так что на самом деле Haskell, как и Clean, - абсолютно чистый язык, а религия "монадический фетишизм" - удел тех, кто на видеть разницы между иллюзией и реальностью.
P.S.
Во загнул! С другой стороны, что взять с простого физ-химика, волей случая написавшего несколько маленьких программ на Perl.
Бета-неэквивалентность нечистого ЛИ
let x = print 2 in (x ; x)
Рассахаривая let, получаем:
(\x -> x ; x) (print 2)
Понятно, что бета-редукция приведет к тому, что 2 напечатается 2 раза вместо одного
Re: Бета-неэквивалентность нечистого ЛИ
Н-да...
Остается только спросить минимальный список литературы, чтобы разобраться в ленивых языках.
Особенно про отсутствие ввода-вывода.
P.S.
"ЛИ" - это как расшифровывается?
Re: Бета-неэквивалентность нечистого ЛИ
Понять дизайн Алгола не менее трудно, чем дизайн Хаскеля. Собственно, научно-популярной литературы на эту тему нет - только посты мальчиков-дебилов, которые только заменят ваши текущие иллюзии на новые, не преподнеся знаний. Ну и научные публикации авторов и разработчиков Хаскеля, для чтения которых нужно обладать докторской степенью по компьютерным наукам западного вуза.
ЛИ - это "лямбда-исчисление".
Re: Бета-неэквивалентность нечистого ЛИ
Так не образованный я в этом вопросе, самоучка. А в программирование меня закинула необходимость обрабатывать экспериментальные данные различных исследований, моделирование физико-химических процессов.
Кстати, давно, когда пытался понять, что такое функциональное программирование - не мог понять, чем этот стиль отличается от моего. Понял лишь, когда увидел код программистов по образованию. Оказалась, что я привыкнув оперировать формулами, в основном писал без мутабельных переменных, даже объекты у меня "клонировалисть", а не изменялись, да и функции у меня были почти сущностями первого первого порядка насколько позволял язык (или как это называется)...
> Понять дизайн Алгола не менее трудно, чем дизайн Хаскеля. Собственно, научно-популярной литературы на эту тему нет - только посты мальчиков-дебилов, которые только заменят ваши текущие иллюзии на новые, не преподнеся знаний. Ну и научные публикации авторов и разработчиков Хаскеля, для чтения которых нужно обладать докторской степенью по компьютерным наукам западного вуза.
Вот и у меня сложилось такое мнение, что есть два вида литературы: остепененный гуру для гуру и тот, в которых говориться, например, что монады - это "дар богов", при помощи которого нам ничтожным можно из бренного императивного мира прикоснуться к абсолютной чистоте.
Поэтому "забил болт" на эти объяснения и решил представить реализацию чистого ленивого языка. Поговариват, что автор jhc так и сделал. :-)
Кстати, характер у меня такой: не могу использовать то, что не понимаю.
Re: Бета-неэквивалентность нечистого ЛИ
Ну, тогда вам долго прийдётся потеть. Список учебников:
Обзорные учебники по функциональному программированию:
1) Functional Programming, Field, Harrison ("филд-харрисон", есть на русском)
2) Structure and Interpretation of Computer Programs, Abelson, Sussman ("сикп", есть на русском)
Учебники по внутреннему устройству функциональных языков:
1) Functional programming and Parallel Graph Rewriting, Plasmeijer, Eckelen ("плазмеер")
2) Tackling the awkward squad: monadic input/output, concurrency, exceptions, and foreign-language calls in Haskell. Peyton Jones
Жесткая математика:
1) Lambda Calculus. Its syntax and semantics. Barendregt (есть на русском)
2) Lambda Calculi with Types. Barendregt
3) Programming in Martin-Löf's Type Theory: An Introduction, Nordstrom
4) Notions of Computation and Monads, Moggi
Ещё можно почитать чего-нибудь про denotational semantics. Ну и само собой, прийдется учить хотя бы "по верхам" математику как таковую (логики, теории множеств, теорию категорий, теорию моделей, теорию доказательств, теорию решеток, теорию порядка...)
Собственно по монадам - Могги и Пейтон-Джонс. Ещё есть хорошая статья "History of Haskell"
Re: Бета-неэквивалентность нечистого ЛИ
Сегодня ночью понял, что санки (http://www.haskell.org/haskellwiki/Thunk) для ленивого языка не нужны!
Они нужны для создания островков ленивости в энергичных языках программирования.
В ленивых языках в них нет необходимости - там правит бал редукция графов.
Теперь задумался: поставил на веса энергичность и ленивость - что выгодней?
Ведь на огромных ленивых списках - такой граф получается, что памяти не хватает.
Приходиться в наглую искусственно его сворачивать.
Кажется туман начинает проясняться.
Спасибо за литературу.
Кстати, есть еще хорошая книжка - Concepts, Techniques, and Models of Computer Programming.
Re: Бета-неэквивалентность нечистого ЛИ
1) Если санки используются "для островков" - получаем не ленивость (call by need, нормальный порядок редукции с разделением), а call by name - нормальный порядок редукции без разделения. Собственно, по вашей ссылке это и имели ввиду, когда говорили что Expressions are translated into a graph (not a tree, as you might have expected). Вот ещё литература: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.158.7919
2) Узлы графов при редукции графов - как раз санки и есть. Вот например в случае G-машины (GHC использует её вариацию):
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.43.7282
Finally, the functions are "compiled" in the sense that a function is converted into an expression which, when executed, builds a graph of function body and then reduces it.
Re: Бета-неэквивалентность нечистого ЛИ
Это же кажется то, про что я пытался сказать в этой заметке с высоты, то есть глубины своей необразованности в этой области!!!
Еще не понимал зачем в haskell есть отдельная монада для CPS, если во самой основе ленивости лежит CPS!
Огромное спасибо за эту ссылку!
Пошел читать эту статью подробно.
Кажется, в неудачной попытке понять монады, я, пойдя по пути создания своей реализации ленивого языка, выбрал вариант с CPS, а не тот, который использует haskell. Отсюда и утверждение, что санки не нужны.
Еще раз спасибо за эту ссылку!
Отдельная монада
1) важно понимать разницу между call by name и call by need. (большинство наивно представляющих ленивость представляют именно call by name, забывая о существенных отличиях)
2) CPS-трансформация в статье всё равно использует санки, если вы не заметили. Без defer и force никуда.
3) Бойтесь дурацкого термина "мемоизация" - его можно неправильно понять, и потом писать о ленивости чухню
4) чтобы понять монады, читайте Могги. Более адекватного описания я не встречал. Продолжения, исключения, эффекты имеют много общего. Поэтому в Хаскеле это общее выделено в отдельную библиотеку, требующую реализации некоего абстрактного интерфейса. C таким же успехом вы бы ещё спросили, зачем в Хаскеле Data.Foldable - затем же. Во-первых, фолд можно определить для разных структур. Во-вторых, через фолды определяются много других операций, и определив для своей структуры фолд, можно остальные операции получить автоматически. Нет "отдельной монады для CPS" - просто с продолжениями можно работать как через конкретный интерфейс, так и через обобщённый. Точно также как со списками можно работать как через map, так и через fmap.
Ленивость на огромных списках
> - что выгодней? Ведь на огромных ленивых списках - такой граф
> получается, что памяти не хватает. Приходится в наглую искусственно
> его сворачивать.
Поясните:
1) где вы увидели "на ленивых списках такой граф, что памяти не хватает"?
2) в каком смысле "выгодней"? по деньгам?
Re: Ленивость на огромных списках
2) Имел ввиду, борьбу с ленивостью. Стоит ли использовать ленивость, а где надо бороться с ней.
Или энергичность,а где надо делать ленивость. Выгода по простоте использования.
Борьба с ленивостью
Тотальные языки всем хороши, но, несмотря на абсолютную чистоту, не дают покоя пуристам тем, что необходимо Тьюринг-неполны.
В случае тотальности разные пути редукции ничем, кроме потребления ресурсов, не отличаются. Т.е. ленивый, энергичный и смешанный тотальные языки идеологически одинаково хороши.
В случае нетотальности у большинства термов есть бесконечные пути редукции. Важно, что если у терма есть нормальная форма (т.е. конечный путь редукции вообще существует) - то редукция в нормальном порядке также конечна (эта нормальная форма будет найдена при нормальном порядке редукции). Т.е. нормальный порядок редукции в неленивых языках идеологически предпочтительнее.
Преимущество тотальных ленивых языков перед нетотальными ленивыми в том, что в тотальном языке программа с произвольно расставленными seq эквивалентна программе без seq, а в нетотальных можно так расставить seq, что программа зациклится или упадёт. Т.е. в тотальных ленивых языках проще оптимизировать использование памяти.
Насчёт нетотальных ленивых и нетотальных энергичных - зависит от приложения. Компилятор (где зависимости по данным сложны) и веб-сайт васи пупкина (где производительность не важна) лучше писать на ленивом, а приложения, в которых разбухание памяти критично - на энергичном.
Детально - надо читать монографии об оценке пространственной и временной сложности ленивых программ. В целом, при ленивости чаще приходится пользоваться профайлером, а при энергичности - чаще писать код через жопу.
Re: Борьба с ленивостью
Изучения его для меня сводиться к болезненным расставанием с заблуждениями, полученными от чтение попадающихся на глаза различных статей и заметок о нем. Столько времени потратил на разные "слухи и сплетни". Надо себе где-то написать большими буквами: "ЧИТАЙ ПЕРВОИСТОЧНИКИ!!!"
Спасибо, вам, за хорошие ссылки.
А что такое тотальные языки - никак не могу нагуглить.
Re: Бета-неэквивалентность нечистого ЛИ
ААААААААААА!!! 800 страниц!!!!!