О чистоте и нечистотах

[thedeemon]

Уважаемый thesz написал у себя:
Для чистоты требуется 1) нормальный порядок упрощения (call-by-need или call-by-name, чтобы убрать зависимость от порядка вычисления) и 2) типы, чтобы ++i не пролезло в чистый код.
но, кажется, перепутал чистоту с хаскелем.

Ибо: 1) есть замечательный чистый функциональный язык Idris (даже проверяемо тотальный большей частью), в котором порядок вычислений строгий. Т.е. я бы заметил, что call-by-need требует чистоты, но чистота в общем случае не требует call-by-need.
То, что "есть классы программ, которые в нормальном порядке выразимы, в энергичном нет" - это правда, конечно, но к чистоте отношения не имеет.
Касательно 2) - бестиповое лямбда-исчисление тоже совершенно чистое, и для чистоты своей типов не требует. Чтобы ++i не пролезло в чистый код таки достаточно убрать из языка ++i и другие нечистоты.

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

Comments

[lomeo.livejournal.com]

Ну, конечно же, это неправда :) Я так делал много раз. Именно с целью решения описанной вами задачи.

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

[valentin budaev (from livejournal.com)]

> Делать же так ленивые из энергичных у вас не получится.

И энергичные из ленивых в общем случае не получится.
f x = 1

(f x)

Сделайте, пожалуйста, так, чтобы х было вычислено. Форсируйте снаружи.

[lomeo.livejournal.com]

Снаружи по отношению к f?
x `seq/deepSeq` f x
Внутри f? То же самое:
f !x = 1

Your turn:

библиотечные энергичные rep :: Int -> a -> a и map :: (a -> b) -> [a] -> b
Хочу получить ленивый список единичек из map (+1) (rep 1000 0)

[valentin budaev (from livejournal.com)]

> Снаружи по отношению к f?

Ага

> x `seq/deepSeq` f x

Это шутка такая? Ну ладно.

> библиотечные энергичные rep :: Int -> a -> a и map :: (a -> b) -> [a] -> b
Хочу получить ленивый список единичек из map (+1) (rep 1000 0)

(map (+1) (rep 1000 0)) `seq` f, где f - ленивый список единичек. Так же, как ваш вариант с x `seq/deepSeq` f x, только нужно требуемую форму подставить с другой стороны :)

[lomeo.livejournal.com]

Хм. Замечание про шутку заставляет меня предположить, что вы не писали на языках с ленивостью по умолчанию (я ошибаюсь?). Нет, это не шутка. Это стандартная идиома. Может выглядеть и так:
g !x = ... f x ...
или так
g x@(X !a !b) = ... f x ...

По поводу вашего кода, нет, он не как мой вариант, т.к. в энергичном языке у вас (req 1000 0) создаст список энергично. Вы не превратили аппликативный порядок в нормальный, я же обратную операцию сделал. x в f передастся уже вычисленным.

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

[valentin budaev (from livejournal.com)]

> С чем вы спорите, не пойму?

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

Можете мне написать ф-ю g, которая принимает ленивый фолдл, и возвращает энергичный, так, чтобы потом этот энергичный фолдл не выжрал память на чем-нибудь вроде foldl + 0 [1..1000000000]?

> Это стандартная идиома.

Это идиома для переписывания ф-й изнутри, в потрохах. Никто и не спорил, что такие есть - я же вас снаружи просил форсить, не изнутри.

[lomeo.livejournal.com]

Не существует способа делать такое для _всех_ ленивых функций. Тем не менее, для многих функций он есть. И не "в редких случаях", а достаточно, чтобы приносить пользу (я встречался с такими, которые приходилось переписывать, буквально пару раз). А вот в обратную сторону - нет, что вами и было продемонстрировано.

> Можете мне написать ф-ю g, которая принимает ленивый фолдл, и возвращает энергичный, так, чтобы потом этот энергичный фолдл не выжрал память на чем-нибудь вроде foldl + 0 [1..1000000000]?

А что это покажет? Наличие таких примеров? Так в инете их полно, thesz в своём посте рассматривает несколько. Или если не напишу, то покажет, что есть функции, которые нельзя зафорсить снаружи? Так с этим я не спорю. Кстати, в этом случае как раз можно, даже делать почти ничего не надо.

Важно: я могу передать функции, ожидающей ленивый аргумент, уже вычисленное значение, а вы передать функции, ожидающей значение, thunk не можете. Однажды вычисленное сделать невычисленным нельзя — время не вернёшь.

[valentin budaev (from livejournal.com)]

> Не существует способа делать такое для _всех_ ленивых функций.

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

> Кстати, в этом случае как раз можно

Ну я бы посмотрел.

> Важно: я могу передать функции, ожидающей ленивый аргумент, уже вычисленное значение, а вы передать функции, ожидающей значение, thunk не можете.

Как это не могу? Могу. Не забывайте что мы рассматриваем язык, который прозрачно работает с thunk'ами. Иначе тогда давайте его сравнивать с ленивым вариантом, который не может принимать значение там, где ожидается санка. Надо сравнивать сравнимые вещи, очевидно же.

[lomeo.livejournal.com]

> Совершенно аналогично и в обратную сторону - для одних ф-й это делать можно, для других - нельзя.

Вы этого не показали. Ещё не было ни одного примера.

> Ну я бы посмотрел.

Цель?

> Не забывайте что мы рассматриваем язык, который прозрачно работает с thunk'ами.

Пример такого языка? Пример использования в этом языке описанной вами техники? Чтобы сравнивать сравнимое.

[valentin budaev (from livejournal.com)]

> Цель?

Ну мне интересно посмотреть, а вы заявили, что это просто, видимо, однострочник какой-то? Почему бы не показать?

> Пример такого языка?

Любой энергичный язык, который умеет принимать санки на месте значений.

> Чтобы сравнивать сравнимое.

Именно, сравнивать надо сравнимое. Есть два совершенно ортогональных концепта:
(1) поддержка языком нативных санок/значений
(2) модель вычислений.

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

То, что язык с (1) лучше, чем язык без (1) - совершенно очевидный факт и с этим спорить никто не будет. Я же утверждаю, что:
а. энергичный язык с (1) лучше, чем ленивый с (1)
б. энергичный без (1) лучше, чем ленивый без (1)

Если же вы сравниваете энергичный без (1) и ленивый с (1) - вы сравниваете несравнимое.

[lomeo.livejournal.com]

Как же энергичный лучше, если примеров для ленивого полно, а для энергичного сколько не прошу вы мне даже одного не даёте? Как и сам язык, впрочем.

Что-то у нас не складывается. Я, пожалуй, всё. Спасибо за дискуссию!

[valentin budaev (from livejournal.com)]

> Как же энергичный лучше, если примеров для ленивого полно, а для энергичного сколько не прошу вы мне даже одного не даёте?

Я описал вам целый класс примеров, но вы заявили, что это не примеры.

> Как и сам язык, впрочем.

По-моему, я вполне конкретно указал язык - энергичный, с нативной поддержкой санок. Например, гипотетический энергичный хаскель. Вы ведь и до этого де-факто сравнивали хаскель с гипотетическим энергичным хаскелем (только другим), а не с реальным языком. В чем вдруг теперь возникла проблема - мне неясно.

> Спасибо за дискуссию!

Аналогично.