О чистоте и лени
Dec. 3rd, 2010 08:06 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
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.
Для любой открытой системы важным моментов является взаимодействие с внешним миром. В данном случаем - порядок обмена информацией.
У энергичных языков порядок определяется непосредственно самой последовательностью инструкций в программе. Напротив, для ленивых языков последовательность выполнения инструкций неопределена, а значения вычисляются по мере необходимости. Поэтому для осуществления взаимодействия с внешним миром в ленивые языки порядок вводиться искусственно.
Одним из способов упорядочивания вычислений является ввод дополнительных переменных-маркеров, при помощи которых указываются дополнительные зависимости между подпрограммами. Например, подпрограмма "C" зависит от переменной "b", которая определяется в подпрограмме "B", в свою очередь подпрограмма "B" зависит от переменной "a", значение которой определяется в подпрограмме "A", что приводит к выполнению сначала подпрограммы "A", затем "B" и лишь затем "C". Эти переменные маркеры в Mozart-OZ получили название свободные (unbound) переменные, а в Clean - уникальные типы.
Другим способом упорядочивание вычислений является использование стиля передачи продолжений. Однако этот стиль труден для использования им требует модификации подпрограмм. К счастью последнего можно избежать при помощи подпрограммы-обертки. В Haskell этой оберткой является оператор bind, а монады по сути не что иное, как своеобразный "концептуальный сахар" над стилем передачи продолжений. В свою очередь Haskell оператор do является "синтаксическим сахаром" вокруг монад, создающих иллюзию того, что переменные меняют свое значение.
Так что на самом деле Haskell, как и Clean, - абсолютно чистый язык, а религия "монадический фетишизм" - удел тех, кто на видеть разницы между иллюзией и реальностью.
P.S.
Во загнул! С другой стороны, что взять с простого физ-химика, волей случая написавшего несколько маленьких программ на Perl.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
Re: Бета-неэквивалентность нечистого ЛИ
Date: 2010-12-14 05:16 pm (UTC)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: Бета-неэквивалентность нечистого ЛИ
Date: 2010-12-15 07:56 am (UTC)Это же кажется то, про что я пытался сказать в этой заметке с высоты, то есть глубины своей необразованности в этой области!!!
Еще не понимал зачем в haskell есть отдельная монада для CPS, если во самой основе ленивости лежит CPS!
Огромное спасибо за эту ссылку!
Пошел читать эту статью подробно.
Кажется, в неудачной попытке понять монады, я, пойдя по пути создания своей реализации ленивого языка, выбрал вариант с CPS, а не тот, который использует haskell. Отсюда и утверждение, что санки не нужны.
Еще раз спасибо за эту ссылку!
Отдельная монада
Date: 2010-12-15 10:05 am (UTC)1) важно понимать разницу между call by name и call by need. (большинство наивно представляющих ленивость представляют именно call by name, забывая о существенных отличиях)
2) CPS-трансформация в статье всё равно использует санки, если вы не заметили. Без defer и force никуда.
3) Бойтесь дурацкого термина "мемоизация" - его можно неправильно понять, и потом писать о ленивости чухню
4) чтобы понять монады, читайте Могги. Более адекватного описания я не встречал. Продолжения, исключения, эффекты имеют много общего. Поэтому в Хаскеле это общее выделено в отдельную библиотеку, требующую реализации некоего абстрактного интерфейса. C таким же успехом вы бы ещё спросили, зачем в Хаскеле Data.Foldable - затем же. Во-первых, фолд можно определить для разных структур. Во-вторых, через фолды определяются много других операций, и определив для своей структуры фолд, можно остальные операции получить автоматически. Нет "отдельной монады для CPS" - просто с продолжениями можно работать как через конкретный интерфейс, так и через обобщённый. Точно также как со списками можно работать как через map, так и через fmap.