О чистоте и нечистотах
Aug. 24th, 2014 03:57 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
thedeemonУважаемый ![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif)
thesz написал у себя:
Для чистоты требуется 1) нормальный порядок упрощения (call-by-need или call-by-name, чтобы убрать зависимость от порядка вычисления) и 2) типы, чтобы ++i не пролезло в чистый код.
но, кажется, перепутал чистоту с хаскелем.
Ибо: 1) есть замечательный чистый функциональный язык Idris (даже проверяемо тотальный большей частью), в котором порядок вычислений строгий. Т.е. я бы заметил, что call-by-need требует чистоты, но чистота в общем случае не требует call-by-need.
То, что "есть классы программ, которые в нормальном порядке выразимы, в энергичном нет" - это правда, конечно, но к чистоте отношения не имеет.
Касательно 2) - бестиповое лямбда-исчисление тоже совершенно чистое, и для чистоты своей типов не требует. Чтобы ++i не пролезло в чистый код таки достаточно убрать из языка ++i и другие нечистоты.
Впрочем, без четкого определения чистоты все это довольно бессмысленное жонглирование. В частности, считать ли чистой функцию со свободными переменными.
thesz написал у себя:Для чистоты требуется 1) нормальный порядок упрощения (call-by-need или call-by-name, чтобы убрать зависимость от порядка вычисления) и 2) типы, чтобы ++i не пролезло в чистый код.
но, кажется, перепутал чистоту с хаскелем.
Ибо: 1) есть замечательный чистый функциональный язык Idris (даже проверяемо тотальный большей частью), в котором порядок вычислений строгий. Т.е. я бы заметил, что call-by-need требует чистоты, но чистота в общем случае не требует call-by-need.
То, что "есть классы программ, которые в нормальном порядке выразимы, в энергичном нет" - это правда, конечно, но к чистоте отношения не имеет.
Касательно 2) - бестиповое лямбда-исчисление тоже совершенно чистое, и для чистоты своей типов не требует. Чтобы ++i не пролезло в чистый код таки достаточно убрать из языка ++i и другие нечистоты.
Впрочем, без четкого определения чистоты все это довольно бессмысленное жонглирование. В частности, считать ли чистой функцию со свободными переменными.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2014-09-29 08:08 am (UTC)Надо сделать энергичным f2/f1 и переписать f3/f4 - точно так же как в случае с энергичность->лень.
Форс со стороны клиента бессмысленнен. Нам для чего нужно вообще делать ленивые ф-и энергичными? Чтобы они не тормозили и не жрали память. От того что мы зафорсим _снаружи_ они, в общем случае, не перестанут тормозить и жрать память - в конце концов, когда наша программа что-то делает (например вывод), то мы как раз автоматически форсим. И оно жрет. По-этому надо переписывать потроха.
Вот если бы нам надо было делать ленивые ф-и энергичными потому что просто так - то вариант с внешним форсом, конечно, прокатывал бы.
Ну и еще один ньюанс - энергичные вычисления следует сравнивать с call-by-value, а если мы берем call-by-need ("энергезированная" версия лени), то надо сравнивать с некоторым другим механизмом (с какой-то "ленивизированной" версией энергичности). Как минимум у нас call-by-need прозрачно работает со значениями/санками и не делеит пришедшее значение. Исходя из дуальности, наша энергичная модель должна прозрачно работать со значениями/санками и не форсить санки. Что это значит на практике? Что все должно вычислять до санок. Есть у нас энергичный список и его отдали в map - получили сразу же новый энергичный список. Есть у нас ленивый список и его отдали в _тот же самый_ map - получили санку с ленивым списком. Сделали список в котором санкой врапнут хвост после каждого десятого элемента - будет map форситься chunk'ами по десять элементов.
no subject
Date: 2014-09-29 03:20 pm (UTC)no subject
Date: 2014-09-29 04:35 pm (UTC)С-но, для меня существуют лишь те способы делать из энергичных ф-й ленивые, которые эту задачу решают. А те, которые не решают - не существуют. По-этому способ в котором "не нужно менять f3/f4" для меня не существует - ведь никто и никогда таким способом пользоваться все равно не будет. Это воображаемый способ. Его нет.
Я вот могу, например, придумать такой же воображаемый способ делать ленивые ф-и из энергичных - просто берем энергичную ф-ю и объявляем ее ленивой. И все. И вообще ничего изменять не надо.
no subject
Date: 2014-09-30 05:00 am (UTC)Делать же так ленивые из энергичных у вас не получится. При первом же обращении к, скажем, голове списка, он вычислится весь.
no subject
Date: 2014-09-30 09:03 am (UTC)И энергичные из ленивых в общем случае не получится.
f x = 1
(f x)
Сделайте, пожалуйста, так, чтобы х было вычислено. Форсируйте снаружи.
no subject
Date: 2014-09-30 02:37 pm (UTC)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)
no subject
Date: 2014-09-30 04:35 pm (UTC)Ага
> 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, только нужно требуемую форму подставить с другой стороны :)
no subject
Date: 2014-09-30 06:51 pm (UTC)g !x = ... f x ...
или так
g x@(X !a !b) = ... f x ...
По поводу вашего кода, нет, он не как мой вариант, т.к. в энергичном языке у вас (req 1000 0) создаст список энергично. Вы не превратили аппликативный порядок в нормальный, я же обратную операцию сделал. x в f передастся уже вычисленным.
Нет, ну действительно, неужели вы не писали ленивые структуры на энергичных и энергичные на ленивых? В первом случае, если нам нужны и ленивые и энергичные мы пишем _две_ структуры. Во втором, пишем только ленивую, а потом расставляем аннотации в местах использования. С чем вы спорите, не пойму?
no subject
Date: 2014-09-30 08:12 pm (UTC)Я спорю с тем, что существует способ, который позволяет делать энергичные функции из ленивых, позволяющий при этом полученной ф-и потреблять ресурсы так же, как энергичная. Во-первых "форсить снаружи" не всегда можно в принципе - я привел выше пример, который никак не зафорсишь, во-вторых, даже в тех редких случаях когда форсить модно - это не приводит к нужному улучшению производительности (если бы приводило то не нужно было бы ничего форсить, т.к. любая программа и так форсится снаружи, по умолчанию).
Можете мне написать ф-ю g, которая принимает ленивый фолдл, и возвращает энергичный, так, чтобы потом этот энергичный фолдл не выжрал память на чем-нибудь вроде foldl + 0 [1..1000000000]?
> Это стандартная идиома.
Это идиома для переписывания ф-й изнутри, в потрохах. Никто и не спорил, что такие есть - я же вас снаружи просил форсить, не изнутри.
no subject
Date: 2014-10-01 07:57 am (UTC)> Можете мне написать ф-ю g, которая принимает ленивый фолдл, и возвращает энергичный, так, чтобы потом этот энергичный фолдл не выжрал память на чем-нибудь вроде foldl + 0 [1..1000000000]?
А что это покажет? Наличие таких примеров? Так в инете их полно,
Важно: я могу передать функции, ожидающей ленивый аргумент, уже вычисленное значение, а вы передать функции, ожидающей значение, thunk не можете. Однажды вычисленное сделать невычисленным нельзя — время не вернёшь.
no subject
Date: 2014-10-01 03:39 pm (UTC)Совершенно аналогично и в обратную сторону - для одних ф-й это делать можно, для других - нельзя.
> Кстати, в этом случае как раз можно
Ну я бы посмотрел.
> Важно: я могу передать функции, ожидающей ленивый аргумент, уже вычисленное значение, а вы передать функции, ожидающей значение, thunk не можете.
Как это не могу? Могу. Не забывайте что мы рассматриваем язык, который прозрачно работает с thunk'ами. Иначе тогда давайте его сравнивать с ленивым вариантом, который не может принимать значение там, где ожидается санка. Надо сравнивать сравнимые вещи, очевидно же.
no subject
Date: 2014-10-02 04:07 am (UTC)Вы этого не показали. Ещё не было ни одного примера.
> Ну я бы посмотрел.
Цель?
> Не забывайте что мы рассматриваем язык, который прозрачно работает с thunk'ами.
Пример такого языка? Пример использования в этом языке описанной вами техники? Чтобы сравнивать сравнимое.
no subject
Date: 2014-10-02 12:11 pm (UTC)Ну мне интересно посмотреть, а вы заявили, что это просто, видимо, однострочник какой-то? Почему бы не показать?
> Пример такого языка?
Любой энергичный язык, который умеет принимать санки на месте значений.
> Чтобы сравнивать сравнимое.
Именно, сравнивать надо сравнимое. Есть два совершенно ортогональных концепта:
(1) поддержка языком нативных санок/значений
(2) модель вычислений.
(2) никак абсолютно не связано с (1) - действительно, ленивый язык без (1) не перестает быть ленивым, энергичный язык с (1) - остается энергичным. Потому что (1) относится не к самой модели а к способу ее реализации.
То, что язык с (1) лучше, чем язык без (1) - совершенно очевидный факт и с этим спорить никто не будет. Я же утверждаю, что:
а. энергичный язык с (1) лучше, чем ленивый с (1)
б. энергичный без (1) лучше, чем ленивый без (1)
Если же вы сравниваете энергичный без (1) и ленивый с (1) - вы сравниваете несравнимое.
no subject
Date: 2014-10-02 12:37 pm (UTC)Что-то у нас не складывается. Я, пожалуй, всё. Спасибо за дискуссию!
no subject
Date: 2014-10-02 04:15 pm (UTC)Я описал вам целый класс примеров, но вы заявили, что это не примеры.
> Как и сам язык, впрочем.
По-моему, я вполне конкретно указал язык - энергичный, с нативной поддержкой санок. Например, гипотетический энергичный хаскель. Вы ведь и до этого де-факто сравнивали хаскель с гипотетическим энергичным хаскелем (только другим), а не с реальным языком. В чем вдруг теперь возникла проблема - мне неясно.
> Спасибо за дискуссию!
Аналогично.