О чистоте и лени

[iamjaph]

После N-ной провальной попытки изучить Haskell и понять суть религии под названием "монадический фетишизм", решил изобрести свой "велосипед", то есть чистый и ленивый язык программирования.

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

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

Одним из способов упорядочивания вычислений является ввод дополнительных переменных-маркеров, при помощи которых указываются дополнительные зависимости между подпрограммами. Например, подпрограмма "C" зависит от переменной "b", которая определяется в подпрограмме "B", в свою очередь подпрограмма "B" зависит от переменной "a", значение которой определяется в подпрограмме "A", что приводит к выполнению сначала подпрограммы "A", затем "B" и лишь затем "C". Эти переменные маркеры в Mozart-OZ получили название свободные (unbound) переменные, а в Clean - уникальные типы.

Другим способом упорядочивание вычислений является использование стиля передачи продолжений. Однако этот стиль труден для использования им требует модификации подпрограмм. К счастью последнего можно избежать при помощи подпрограммы-обертки. В Haskell этой оберткой является оператор bind, а монады по сути не что иное, как своеобразный "концептуальный сахар" над стилем передачи продолжений. В свою очередь Haskell оператор do является "синтаксическим сахаром" вокруг монад, создающих иллюзию того, что переменные меняют свое значение.

Так что на самом деле Haskell, как и Clean, - абсолютно чистый язык, а религия "монадический фетишизм" - удел тех, кто на видеть разницы между иллюзией и реальностью.

P.S.
Во загнул! С другой стороны, что взять с простого физ-химика, волей случая написавшего несколько маленьких программ на Perl.

Comments

[thesz.livejournal.com]

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

Эту штука пошире будет.

Есть Monad Maybe, Monad [], Monad (Either l), Monad (State s) и тп.

[migmit.livejournal.com]

Но при этом давно известно, что можно выкинуть все монады, кроме Cont, и сильно хуже не будет.

[thesz.livejournal.com]

Я это пропустил. Где можно ознакомиться?

[migmit.livejournal.com]

Если коротко - достаточно оставить instance Monad (Cont r). Всё остальное делается через неё:

data Cont r a = Cont {runCont :: (a -> r) -> r}
instance Monad (Cont r) where ... -- ну, понятно.

data IO a = ... -- встроенный тип, для которого НЕТ instance Monad, но есть
retIO :: a -> IO a
bindIO :: IO a -> (a -> IO b) -> IO b

toCont :: IO a -> Cont (IO r) a
toCont ioA = Cont {runCont = bindIO ioA}
fromCont :: Cont (IO r) r -> IO r
fromCont cnt = runCont cnt retIO

main = fromCont $
  do toCont $ putStrLn "What's your name?"
     name <- toCont $ getLine
     toCont $ putStrLn $ "Hi, " ++ name

[migmit.livejournal.com]

Во, нашёл: http://blog.sigfpe.com/2008/12/mother-of-all-monads.html

[iamjaph.livejournal.com]

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

[migmit.livejournal.com]

Не знаю, сейчас прочту...

Ну, например, что Haskell - абсолютно чистый язык. Это чистая правда, да.

[thesz.livejournal.com]

Отлично. Спасибо. ;)

[nponeccop.livejournal.com]

> У энергичных языков порядок определяется непосредственно
> самой последовательностью инструкций в программе. Напротив,
> для ленивых языков последовательность выполнения инструкций
> неопределена, а значения вычисляются по мере необходимости.

Термины в математике - абстрактные последовательности слов, в общем случае не поддающиеся лингвистической декомпозиции. Термин "call by need" нельзя интерпретировать так, как будто это словосочетание английского языка. Попытаясь понять этот абстрактный смысл нематематически, как будто смыслы составляющих термин слов "вызов" и "необходимость" являются частью составного смысла, как будто есть какие-то вызовы и какая-то необходимость, вы зашли в тупик.

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

> Поэтому для осуществления взаимодействия с внешним миром в ленивые
> языки порядок вводиться искусственно.

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

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

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

Далее вы снова ушли в переменные меняющие значения. Перепишите без этого, так я не могу понять вашу мысль

Теперь по сути

[nponeccop.livejournal.com]

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

1) Что такое монады?

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

2) Что такое монады в Хаскеле?

Это особая абстрактная управляющая структура.

3) В чем польза хаскелевцам от наличия такого странного модуля, как Control.Monad?

Повторное использование кода. Функции из этого модуля вроде mapM и liftM2 удается повторно использовать в чрезвычайно большом количестве предметных областей. Монадический фетишизм заключается в том, что людей возбуждает, если функцию mapM удаётся применить в каком-то неожиданном месте. Т.е. пишешь-себе пишешь, а потом бах - обнаруживаешь: "Ба, да это я половину контрол-монад заимплементил, надо срочно выбросить 100 зря написанных строк и написать import Control.Monad". Собственно возбуждение наступает лишь в клинических случаях - люди учили монады чтобы делать ио, а потом прозрели, что оказывается в Хаскеле есть абстракции управления. В менее запущенных случаях человека возбуждают не только монады, а вообще все абстракции управления (стрелки, обобщенные свертки, функторы и аппликативные функторы, вся typeclassopedia). Но такие люди выглядят не фанатами, а занудами, т.к. они не могут похвастаться знанием фраз типа "категория эндофункторов", а "абстракции управления" - это недостаточно заумно, т.к. и "абстракция", и "управление" есть даже в книгах по джаве. С другой стороны, люди, бросающиеся на каждом углу словами "катаморфизм", не производят впечатления фетишистов, так как рядовому кодеру непонятно, зачем это нужно, когда можно писать рекурсивную лапшу. В случае монад же вопрос "зачем нужен ввод-вывод" покажется нелепым даже императивному программисту, так что их как-то приходится постигать всем.

4) Зачем ввод-вывод в Хаскеле организован таким странным образом?

Это уже не монадический фетишизм, а пуристический. Об этом в следующем комментарии

Re: Теперь по сути

[migmit.livejournal.com]

Дико извиняюсь, но зануда тут один - вы.

Монадический фетишизм

[nponeccop.livejournal.com]

Совершенно случайно, я как раз не далее чем вчера на ночь читал monads for functional programming Вадлера. Там очень хорошо и без привлечения математики написано, для чего монады нужны. В-общем, do-нотация это не эмуляция императивщины, а просто полезная фича для красивой записи целого класса выражений.

В PDF всё можно найти на CiteSeerX (просто поискав "monads for functional programming CiteSeerX" на Гугле). Вот список чего Вадлер написал по монадам и связанным темам:

http://homepages.inf.ed.ac.uk/wadler/topics/monads.html

Re: Монадический фетишизм

[iamjaph.livejournal.com]

> Совершенно случайно, я как раз не далее чем вчера на ночь читал monads for functional programming Вадлера. Там очень хорошо и без привлечения математики написано, для чего монады нужны. В-общем, do-нотация это не эмуляция императивщины, а просто полезная фича для красивой записи целого класса выражений.

Так я и пытался в этой заметке именно это и сказать, что что do-нотация - лишь красивая запись, и которая для тех, кто хочет, может создать иллюзии. Более того, что монады - это тоже сахарок над продолжениями, в чем усилилась моя уверенность после прочтения http://blog.sigfpe.com/2008/12/mother-of-all-monads.html.

Кстати, когда писал про неопределенность порядка подразумевал не на уровне всей программы, о чем вы говорили, а не уровне отдельно взятого куска кода, функции.
Ведь внутри функции не известно как там снаружи средуцируется граф, и какая переменная, то есть значение, получаемое из вне этой функцией понадобиться первым.
А продолжения позволяют связать функции так, что не выполнив одну, нельзя выполнить другую. Другим способом это сделать - unbound переменные в OZ.

> В PDF всё можно найти на CiteSeerX (просто поискав "monads for functional programming CiteSeerX" на Гугле). Вот список чего Вадлер написал по монадам и связанным темам:
>
> http://homepages.inf.ed.ac.uk/wadler/topics/monads.html

Спасибо.

P.S.
Вы как-то грозились написать красиво об этом всем.
Стоить надеяться на это в ближайшие время?

Написать красиво

[nponeccop.livejournal.com]

надеяться не стоит - сейчас стоит задача написать красиво о HN0 (http://code.google.com/p/inv)

Пуристический фетишизм

[nponeccop.livejournal.com]

Если очень кратко - то ввод-вывод в Хаскеле так сделан для радикального упрощения как написания, так и компиляции программ.

В обычных языках и компилятор при оптимизациях, и программист при рефакторингах должны помнить, занимается ли функция вводом-выводом или нет. Скажем, в Си

int x = foo(3);
x = 5;

можно заменить на int x = 5 только в случае, если foo не занимается вводом-выводом. Соответственно, в компиляторе проверки на потенциальное(!) наличие ввода-вывода должны быть расставлены повсеместно. Даже присваивания не доставляют столько хлопот компилятору, как ввод-вывод. Соответственно, если удастся сделать язык без ввода-вывода - то это существенно упростит всё: компиляторы, инструменты рефакторинга и анализа, работу программистов и т п.

Поэтому авторы Хаскеля (конкретно, Вадлер) придумали, как сделать хаскель без ввода-вывода вообще (ввода-вывода в Хаскеле нет, если вы не знали). И случайно оказалось, что проклятый mapM и сюда пролез.

В-общем, осталось ответить на вопросы:

1) Почему ввод-вывод доставляет столько проблем оптимизатору, что от него стоит избавиться?
2) Если в Хаскеле ввода-вывода нет, то как на Хаскеле читают файлы? (на Хаскеле файлы, строго говоря, и не читают)

Упрощение семантики

[nponeccop.livejournal.com]

И ленивость, и чистота возникают из требований простоты семантики.

Семантика ленивого ЛИ проще, чем семантика энергичного ЛИ.
Семантика ЛИ проще, чем семантика ML.
Семантика языка без присваивания проще, чем семантика языка с присваиванием.
Семантика языка без побочных эффектов вообще проще, чем семантика языка без присваивания, но с вводом-выводом.

Семантика - это функция, сопоставляющая корректным программам их смыслы (результат их работы). Важно, что семантика позволяет также определить эквивалентность двух программ - две программы эквивалентны, если семантики их равны. Знание, какие программы эквивалентны, нужно как оптимизаторам, так и авторам программ. Более того, разработаны технологии т.н. абстрактной интерпретации, позволяющие почти механически конструировать анализаторы программ из математического описания семантики. Соответственно, простота семантики критична - программы с простой семантикой проще анализировать (в т.ч. человеку при написании, чтении чужой программы и рефакторингах) и проще оптимизировать, т.к. при эквивалентных преобразованиях надо проверять меньшее количество условий.

Иметь семантику ЛИ выгодно, потому что ЛИ простое и хорошо изучено. Хорошо изучено также "ЛИ с константами". Важно понимать, что мы не можем просто добавить в ЛИ константу print. Такое наивное добавление нарушит семантику, ранее эквивалентные преобразования станут неэквивалентными.

Скажем, семантика ЛИ говорит нам, что бета- и эта-преобразования (редукции и экспансии) эквивалентны. В случае констант print и ; ("последовательность экшенов") это нарушается. Также семантика говорит нам, что разные последовательности редукций одного терма отличаются в ЛИ лишь тем, что некоторые из них завершаются, а некоторые нет, а все завершающиеся последовательности редукций приводят к одинаковому результату.

Легко видеть, что терм print 2 ; print 3, в префиксной записи (;) (print 2) (print 3) не обладает таким свойством: редукции двух print местами переставлять нельзя.

Бета-неэквивалентность нечистого ЛИ

[nponeccop.livejournal.com]

Вот пример с нарушением бета-эквивалентности:

let x = print 2 in (x ; x)

Рассахаривая let, получаем:

(\x -> x ; x) (print 2)

Понятно, что бета-редукция приведет к тому, что 2 напечатается 2 раза вместо одного

Re: Бета-неэквивалентность нечистого ЛИ

[iamjaph.livejournal.com]

:-(
Н-да...
Остается только спросить минимальный список литературы, чтобы разобраться в ленивых языках.
Особенно про отсутствие ввода-вывода.

P.S.
"ЛИ" - это как расшифровывается?

Re: Бета-неэквивалентность нечистого ЛИ

[nponeccop.livejournal.com]

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

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

ЛИ - это "лямбда-исчисление".

Re: Бета-неэквивалентность нечистого ЛИ

[iamjaph.livejournal.com]

> Трудные вопросы вы задаете, батенька. Вот вы учили десятки языков, как две капли воды похожие на Алгол-60, принимали их дизайн как данное и не спрашивали литературу, обосновывающую дизайн Алгола.

Так не образованный я в этом вопросе, самоучка. А в программирование меня закинула необходимость обрабатывать экспериментальные данные различных исследований, моделирование физико-химических процессов.

Кстати, давно, когда пытался понять, что такое функциональное программирование - не мог понять, чем этот стиль отличается от моего. Понял лишь, когда увидел код программистов по образованию. Оказалась, что я привыкнув оперировать формулами, в основном писал без мутабельных переменных, даже объекты у меня "клонировалисть", а не изменялись, да и функции у меня были почти сущностями первого первого порядка насколько позволял язык (или как это называется)...

> Понять дизайн Алгола не менее трудно, чем дизайн Хаскеля. Собственно, научно-популярной литературы на эту тему нет - только посты мальчиков-дебилов, которые только заменят ваши текущие иллюзии на новые, не преподнеся знаний. Ну и научные публикации авторов и разработчиков Хаскеля, для чтения которых нужно обладать докторской степенью по компьютерным наукам западного вуза.

Вот и у меня сложилось такое мнение, что есть два вида литературы: остепененный гуру для гуру и тот, в которых говориться, например, что монады - это "дар богов", при помощи которого нам ничтожным можно из бренного императивного мира прикоснуться к абсолютной чистоте.

Поэтому "забил болт" на эти объяснения и решил представить реализацию чистого ленивого языка. Поговариват, что автор jhc так и сделал. :-)

Кстати, характер у меня такой: не могу использовать то, что не понимаю.

[beroal.livejournal.com]

Плохо то, что слово «вычисление» уже начало означать «изменение памяти компьютера». Вычисляли же люди и до компьютеров, и перечёркивали написанное на бумаге только если оно было написано не правильно. :) Поэтому я бы говорил не о «порядке вычислений», а о порядке обмена информацией или о порядке запуска подпрограмм. Порядок вычислений, конечно же, тоже существует, и именно он не нужен. В каком порядке не вычисляй, результат будет одинаковый.

[iamjaph.livejournal.com]

Кажется я по втором абзаце уточнил, что разговор идет о порядке обмена информацией с внешней средой.
Насчет слова "вычисление" с вами полностью согласен. Да и сейчас бумагу уважаю. Все сложное сначала рисую на ней :-)

[beroal.livejournal.com]

Кстати, «монадический фетишизм» действительно существует, но называется «монадические технологии» (http://beroal.livejournal.com/16499.html). :)

[udpn.livejournal.com]

Опа, еще один химико-программист!
Присоединяйтесь к нам ;)

aamonster, sharpc, udpn

[iamjaph.livejournal.com]

Ой, тяжко у вас тут.
Я ведь все на динамической типизации: Perl, OZ.
R, J.