Функциональный апартеид

[metaclass]

http://udpn.livejournal.com/78084.html?style=mine
Обычно говорят, что нормальный порядок редукции нужен для того, чтобы bottom в аргументе не превращался в bottom в результате всегда, когда это возможно. Само по себе это никому не нужно. Дело именно в отложенном вычислении аргументов. Чтобы определить управляющие конструкции в языке с аппл. порядком редукции, нужно это делать явно, и их можно ввести только конечное число на этапе разработки языка. С нормальным порядком мы имеем возможность определять новые конструкции в любом количестве.

Всех, кто ничего не понял - отправить в индию и бангладеш, купаться в ганге и поклонятся коровам.

Comments

[nivanych.livejournal.com]

С ленивостью одна большая проблема — это полный пофигизм по отношению к ресурсной семантике.
И даже в современных языках, все эти проблемы решаются ad hoc.
Вроде как, имеешь опыт работы с ленивостью — должен сообразить.
А не сообразил, и ВНЕЗАПНО, где-то-там у тебя прорвало — сам виноват.
Рассуждения о ресурсной семантике (не без помощи линейной логики!) нормализации в ламбда-исчислении приводят к оптимальной редукции, о которой немало писал codedot. Хоть он всё делает для бестиповой лямбды, но и такое изучить небесполезно.

[metaclass.livejournal.com]

Хм, оптимальный порядок редукции это интересно. Это ж будет "странная" комбинация аппликативного и нормального, которую мы сейчас обычно закатываем солнцем вручную.

[nivanych.livejournal.com]

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

[nponeccop.livejournal.com]

А там не оптимальный порядок редукции, а оптимальный sharing, по сути. Разделяется больше, чем при call by need.

[nivanych.livejournal.com]

Правда, должен заметить, что хоть сколько-то управляемая ресурсная семантика будет ещё и сиильно покруче более непривычная, чем итераты-енумераты, к примеру.
Я так думаю. И хотел бы, чтобы мне кто-то показал, что я неправ! ;-)

[udpn.livejournal.com]

Кстати да, всегда интересно было, о чём пишет codedot, но пишет он очень сложно.

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

[nivanych.livejournal.com]

Да, оптимальность по количеству "мелких редукций".
Уходить от графо-редукции необязательно, хотя и codedot, в общем-то, это сделал для своей машинки — там он может и про память говорить.
А вот задаться вопросом, можно ли осуществить такую-то нормализацию более оптимально, чем в `ленивой` модели, очень даже можно. Мемоизация, это только одна из техник оптимизации, но есть и общий подход.

[nponeccop.livejournal.com]

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

[nivanych.livejournal.com]

Так, точнее так будет сказать, я плохо выразился.

[udpn.livejournal.com]

А можно пример, на котором эта разница будет видна? Или лучше спросить самого codedot?

[nponeccop.livejournal.com]

Лучше спросите самого лэмпинга

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.90.2386

Levy[4, 5] has shown that there are lambda expressions for which any order of reduction duplicates work. One
example is ...