Re: Стабильная система?
Dmitrii Kashin -> debian-russian@lists.debian.org @ Sat, 17 Oct 2015 00:17:13 +0300:
>> >> DK> За время работы с ним меня приятно удивило после Haskell:
>> >>
>> >> DK> 1) Позволяет более просто комбинировать функциональное и императивное
>> >> DK> программирование: не надо изворачиваться монадами, чтобы добиться
>> >> DK> последовательного выполнения команд.
>> >>
>> >> ...
>> >>
>> >> а зачем, собственно, добиваться последовательного выполнения никак не
>> >> связанных между собой команд?
>>
>> DK> Я думаю, тут есть недоразумение. Требование последовательного выполнения
>> DK> определённых команд как раз и определяет связь между ними. Если конечно
>> DK> не считать, что связь -- это "результат А нужен для вычисления B". Тут
>> DK> важно понять, что императивное программирование -- это именно
>> DK> программирование с изменением состояния системы.
>>
>> Тогда это, натурально, связанные между собой команды. Для вычисления B
>> требуется состояние системы, полученное после вычисления A.
>>
>> Хаскельный компилятор просто более аккуратно подходит к вопросу
>> зависимости (он машина, ему внимания не жалко), и может обнаружить
>> независимость там, где программист ее не обнаружил, и по умолчанию
>> полагает, что зависимость есть.
DK> Теоретически это наверное плюс. Но мне бы реальных ситуаций. У меня
DK> такое чувство, что вполне себе может случится обратное: зависимость
DK> есть, а компилятор её не обнаружил, и решил что-нибудь
DK> соптимизировать. В этом случае мне кажется, чем тупее система -- тем
DK> лучше.
Если компилятор ее не обнаружил, то он не смог скомпилировать код. Ему
же надо превратить функциональную зависимость в императивный код.
Он же работает по схеме "для вычисления вот этого мне нужно вот это, вот
это и вот это. Где я их возьму?" А если ему в процессе этого выяснения
что-то _не_ понадобилось, то от него зависимости нет по построению.
>> DK> Зачем это нужно? Ну, бывают разные случаи.
>>
>> DK> Бывает, что это повышает производительность. В случае большого словаря
>> DK> создание его дубликата при изменении значения одного ключа создаёт очень
>> DK> большие накладные расходы.
>>
>> Это, как я уже писал, вопрос не императивности, а мутабельности. Нам,
>> вообще говоря, совершенно незачем выполнять строго последовательно
>> изменения значений у двух разных ключей.
DK> Извините, у меня в мозгу императивность и мутабельность неразрывно
DK> связаны. Объясните, почему Вы разделяете их? Мутабельность -- это
DK> возможность объекта менять состояние. Императивность -- стиль
DK> программирования, при котором программа проходит через
DK> последовательность состояний.
Императивность - это стиль программирования, при котором единица
программирования - это выполнение инструкции, самой по себе
бессмысленной, и только в комплекте со всеми остальными решающей
задачу — преобразовать вход в выход.
Модель типа такая: вот у нас на входе реальный мир. Мы подкрутили
чуть-чуть тут, потом чуть-чуть здесь... Опа, внезапно на выходе у нас
реальный мир с дополнительными нужными свойствами (и дополнительными
ненужными, которые мы не заметили :).
Каждое изменение производится локально, но имеет неопределенные
последствия при взгляде из точки изменения.
Функциональный стиль тоже преобразует реальный мир на входе в реальный
мир на выходе, т.е. мутирует его. Но в иной модели:
Мы хотим, чтобы вот тут было вот так. Для этого надо взять вот это и
вот это и вот так их скомбинировать. Вот это можно получить вот так...
Что именно при этом изменится в мире, можно тупо выяснить автоматически,
пройдя по дереву зависимостей. То, что не затронуто деревом
зависимостей, гарантированно не изменится в результате _наших_ действий.
А так мутировать-то мы его мутируем...
>> Хаскель, кстати, будет делать дубликат не всего словаря, а только той
>> ветки, в которой поменяли значение. Для, допустим, Map это O(log n).
DK> Ну и таки да, Хаскель не будет делать дубликат словаря, ибо эти "разницы
DK> между исходной версией и данной" для него суть thunk-и, и это одно из
DK> полезных следствий ленивости.
Нет, не поэтому. Когда он вычислит эти thunk'и, у него появится shared
structure. Потому что остальной словарь не затронут, и его можно
использовать as is, копия не требуется.
DK> Но тут мы вроде бы занимались выяснением вопроса "почему иногда
DK> императив всё-таки нужен".
А выяснили пока что, зачем _в некоторых очень отдельных местах_ нужна
мутабельность. Причем если рассмотреть задачу в целом, внезапно
выяснится, что целиком мутабельный словарь выгоднее только в сферическом
случае в вакууме, когда к нему обращаются (и на изменение, и на чтение)
строго последовательно. Иначе всю выгоду от более быстрого изменения
может сожрать обеспечение консистентности.
>> DK> Бывает, что это упрощает описание алгоритма. Например, если Вы
>> DK> реализуете программу, алгоритм которой описан в императивном стиле в
>> DK> некоторой статье, то логично пользоваться тем же представлением, что и
>> DK> автор.
>>
>> Ну, тут да. Тут, действительно, может выясниться, что один в один
>> перевести сложнонавороченный цикл на монадную схему... не то чтобы
>> сложно, но получается менее удобочитаемо. С другой стороны, ну, пишем
>> наскоро EDSL под псевдокод из статьи, и вперед. Зефиров рассказывал,
>> что для какой-то довольно серьезной задачи он делал императивный даже не
>> EDSL, а просто DSL, и транслировал его в хаскель.
DK> Ну, в принципе, создание EDSL -- это метод. Но это, как я понимаю, в
DK> основном прерогатива Lisp-ов. Там они органичны более-менее. (Хотя это
DK> смотря где ещё. Вот гигиенические макросы из Scheme на меня тоску
DK> наводят). А как в Haskell с расширением синтаксиса?
Весьма неплохо. Так, на глазок, не меньше половины стандартных
библиотек представляют собой EDSL.
Для особо желающих есть Template Haskell. Это примерно то же, что
лисповые макросы - ты хаскельным кодом генерируешь хаскельный код,
который затем обрабатывается компилятором. Но не в рантайме, как это
было бы в лиспе, а при компиляции, как и основной код.
Соответственно, минус возможность выполнить код, полученный извне в
рантайме. И связанные с этим ошибки и взломы :)
>> DK> Бывает, что без этого обойтись невозможно. Такое случается, когда Ваша
>> DK> программа должна некоторым образом взаимодействовать со внешней
>> DK> средой. Вот пишете Вы, допустим, сборочную систему, и Вам принципиально
>> DK> важно, чтобы были выполнены последовательно сначала git clone, а потом
>> DK> git checkout.
>>
>> Это система с изменением состояния - "не склонировано", "склонировано",
>> "извлечено". git checkout можно делать из состояния "склонировано", а
>> откуда и когда оно взялось, в этом месте неважно. А берется оно из
>> завершения git clone (это состояние RealWorld)...
>>
>> Система зависимостей тут как раз может гарантировать консистентность
>> вытащенного, потому что, если копать дальше, для выполнения git clone
>> надо, чтобы место было чистое - и вызывается команда приведения места в
>> чистое состояние...
DK> Ну, значит тут надо изменить подход к процедуре описания данных
DK> алгоритмов. Начать оперировать состояниями внешней среды. Я должен их
DK> разумеется детектировать, описывать, задать правила их вычисления,
DK> задать правила их изменения.
DK> Что ж, возможно, тут есть свои подходы. Вот об этом-то и надо бы писать
DK> в книжках.
Так об этом надо писать книжки не по языку, а по парадигме. Есть
подозрение, что они существуют - я же откуда-то все это знаю...
Статей по функциональному программированию точно много, и хорошие есть.
>> DK> Но вот сейчас я вспомнил, чего я действительно не видел в Haskell, и что
>> DK> очень облегчает мне жизнь сейчас. Это опциональные аргументы при
>> DK> сопутствующих полноценных возможностях каррирования.
>>
>> DK> ...
>>
>> Я иногда тоже хочу параметров по умолчанию, но сильно подозреваю, что
>> это пережиток языков с duck typing. На практике, учитывая, что язык
>> компилируемый, всегда можно либо добавить пару параметров и поменять все
>> (найденные компилятором) вхождения вызовов, добавив туда дефолтные
>> значения, либо, что чаще, одновременно со вводом дополнительных
>> параметров переименовать функцию, а старое имя определить как
>> каррирование нового.
DK> Поменять все? Вряд ли. Их может быть очень много.
Вот когда _очень_ много, я иду вторым путем. Когда просто много,
бывает, что и первым. Компилятор все найдет.
DK> Тут ещё интересный вопрос: куда добавлять новый аргумент? В конец,
DK> в середину, в начало? Судя по всему в начало, иначе каррирование
DK> может Вас свести с ума (это справедливо, например, если у вас
DK> где-то происходит выбор между функциями с похожими, но слегка
DK> различными аргументами методом каррирования до общей базы).
Как правило, да, но если старая функция переопределяется через новую, то
куда угодно. Мне _один_ раз придется переставить аргументы.
DK> Переименование функции может быть не самым лучшим решением, вообще
DK> говоря. После ряда таких вот "уточнений" исходной функции, у Вас будет
DK> несколько новых, каждая всё с более длинным именем. Рано или поздно
DK> имена перестанут быть лаконичными и говорящими. Хорошо ли это? Вряд ли.
Чтобы так произошло, надо _по очереди_ добавить штук пять параметров, не
меньше. Независимых, потому что связанные естественным образом
объединятся в одну запись. Есть мнение, что это признак очень, очень
плохого пути изменения...
>> DK> Как Вы знаете, некоторое время тому назад я с Вашей подачи пытался
>> DK> работать на Haskell, и предпринял даже попытку написать дипломную работу
>> DK> с использованием этого языка.
>>
>> DK> В то время язык оказался неподходящим. Я, конечно, разработал чисто
>> DK> функциональные алгоритмы, которые сильно упростили мне проектирование
>> DK> будущих версий программы, но я столкнулся вот с чем:
>>
>> DK> Программа была научная, и её целью было исследование метода. Так вот:
>> DK> очень, очень сложно производить дебаг алгоритма, когда вычисления
>> DK> производятся ленивым образом.
>>
>> А вот это место можно поподробнее? Непонятно, откуда берется проблема.
DK> Хм. Я, пожалуй, не совсем выразился. Дебаг программы самой по себе
DK> хорош. Ещё б ему не быть хорошим, при выводе типов-то. Проблема, которая
DK> выбила из колеи лично меня -- это дебаг реализуемого алгоритма.
Я сумел это прочесть, и спросил именно об этом.
DK> Я решал задачу расчёта поля течения на некоторой сетке (короче,
DK> эйлеровский подход к построению эволюции течения подразумевает, что мы
DK> разбиваем профиль на ячейки, образуя "сетку". В каждой ячейке содержатся
DK> значения параметров течения, и они по некоторым законам изменяются со
DK> временем. Каждую итерацию по заданному полю вычисляется, какое поле
DK> течения будет черед некоторое время tau. На tau, конечно, есть вполне
DK> определённые ограничения сверху).
DK> Так вот, была сделана попытка разработать новый метод расчёта течения,
DK> который смог бы учесть межфазный обмен. Короче, как это в физике часто
DK> бывает, сначала построили метод, а потом начали разбираться, почему
DK> результат не согласуется с ожидаемым.
DK> И тут всплыла неприятность: необходимо было получать не только
DK> промежуточный результат, но ещё и некоторую информацию о состоянии
DK> некоторых ячеек сетки на каждой итерации.
DK> Я сумел разобраться, как поставить точки останова и выйти в repl ghci,
DK> чтобы посмотреть состояние окружения в момент останова (посмотреть там
DK> значения параметров ячейки, которую мы сейчас обрабатываем, и т.п.).
DK> Но разумное желание после такого останова -- пройти выше по callstack и
DK> посмотреть, в какую функцию что было передано. Я не сумел этого добиться
DK> никак.
Неудивительно. Стека вызовов там в этот момент с шансами тупо нет.
Возможно, никогда и не было.
DK> Возможно, я не разобрался, конечно, но знаете, это было весьма
DK> проблемно: сидишь на закрытом объекте, ни гугла, ни ирки, ни рассылки, в
DK> которой Артём Чуприна может подсказать что-то дельное... :)
DK> И тут ладно, что нету у меня callstack-а. Я мог бы и сам поставить
DK> остановы в места, из которых данная функция вызывается,
DK> но... Вай-вай-вай, а когда у меня эта функция вызывается? У меня же
DK> добрых пять десятков законов, описывающих различные аспекты вычисления
DK> поля, и я понятья не имею, какой в какой момент вызвается для получения
DK> конечного результата. Победа, товарищи.
Идея понятна, да. Так вот без контекста не скажешь, как было бы более
правильно искать проблему в алгоритме. Я бы, новерное, и в императивном
случае подходил бы функционально, двигаясь сверху вниз и ставя фрагменты
кода в условия, в которых проблема проявляется.
Хуже, конечно, если метод сформулирован настолько императивно, что
промежуточные этапы хрен выделишь. Ну, тут модифицируется код, чтобы в
вызываемом коде можно было посмотреть на контекст (который иначе давно
бы уже был съеден garbage collector'ом). Потом размодифицируется
обратно. Тут как раз могут помочь неявные параметры. Которых,
вероятно, в ghc еще не было в обсуждаемое время.
DK> Концепцию монад я переварил уже сильно позже, после того, как решил
DK> махнуть рукой на Haskell и переписал программу на SBCL. Кстати, вот тут
DK> я бы отдельно подчеркнул, что лиспы для прототипирования --
DK> великолепны. Именно что: в момент останова (намеренного ли, или при
DK> ошибке), я вываливаюсь в отличный дебаггер, где могу проследовать вверх
DK> по вызовам, посмотреть на все параметры, переданные в функцию. Если там
DK> список, то пройтись по элементам, со всем разобраться.
Для прототипирования алгоритма — соглашусь. Но вот уже workflow лучше
прототипировать на богатой системе типов, на лиспе зароешься уже на
второй итерации правки workflow.
Все, собственно, зависит от того, куда при этой работе должно быть
направлено внимание, и какие возможности язык предлагает для снятия с
программиста работы по отслеживанию взаимосвязей. Haskell предлагает
хорошие для отслеживания взаимосвязей между абстракциями и плохие —
между числами. У лиспа с числами будет лучше (хотя все равно хуже, чес
у хаскеля с абстракциями), а с абстракциями хуже.
DK> Разумеется, отладка граничных случаев в этом случае весьма нетривиальна,
DK> но до неё, в общем-то, в моей работе дела так и не дошло.
>> DK> Сейчас я работаю в основном на Racket Scheme, Emacs/Common Lisps и
>> DK> Ocaml. Последний выглядит для меня примерно как Haskell, только без
>> DK> ленивости. Синтаксис выразительный, но логика вычислений проще поддаётся
>> DK> осмыслению, и дебаг также не вызывает трудностей.
>>
>> Мозги разные? Для меня логика вычислений на хаскеле на порядок (по
>> основанию явно больше 2, но не 10) проще для осмысления. Именно в силу
>> функциональности. Ведь императивный алгоритм - это инструкции для
>> тупого, но очень неленивого исполнителя.
DK> Эгегей, а кто говорит, что функциональные алгоритмы сложнее? )
DK> Я обеими руками за простоту осмысления функциональных алгоритмов. Сам
DK> пишу код в основном функциональный, ибо да, таки удобнее и
DK> проще. Выразительный синтаксис -- это я о макросах в лиспе.
DK> Для меня лично основную проблему представляет именно ленивость. Я
DK> понимаю, как писать программы с добавлением ленивости в определённых
DK> местах, но у меня, хоть убейте, не получается делать наоборот.
Рецепт довольно простой: надо перестать думать за машину.
Убрать ленивость, если она мешает, проще, чем добавить. Но главное —
если не пытаться думать за машину, оказывается, что это нужно весьма
редко.
Если пытаться думать за машину, то даже в формально функциональный
подход начинает влезать императивщина. А это зря.
>> Тупого настолько, что связь "данный алгоритм решает данную задачу" ему
>> недоступна. Можно выполнить дословно, но что за задачу мы решили? Да
>> фиг ее знает... Извлечь из императивного алгоритма задачу, которую он
>> решает (или проверить, что он решает известную задачу, в императивном
>> случае это тот же уровень сложности) требует от меня очень недетского
>> напряжения.
DK> Классический вариант "море императивщины без комментариев"?
DK> Соболезную. :(
Комментарии помогают только пока соответствуют коду. А это нечем
проверить, кроме себя, любимого.
>> Ленивость, правда, порой добавляет сложности в процесс понимания (если
>> она в алгоритме задействована нетривиальным образом - если тривиальным,
>> то разницы никакой).
DK> Нетривиальным -- это каким?
Представляешь себе список, определенный рекурсивно через два экземпляра
самого себя? Константный, т.е. безо всяких аргументов. Один из самых
вычислительно эффективных способов посчитать (лабораторный пример)
нужное число Фибоначчи (выбор из этого списка по индексу).
fib n = fibSeq ! n where
fibSeq = 1 : 1 : zipWith (+) fibSeq (drop 1 fibSeq)
Числа Фибоначчи как лабораторный пример интересны, как известно, тем,
что вычисление их в лоб по рекурсивной формуле имеет экспоненциальную
сложность вместо линейной. Все образованные программисты это знают, и
знают, что надо поддерживать как минимум бегущую пару — тогда линейно.
Но код под это выглядит уже далеко не столь ясно, как рекурсивное
определение.
Вариант с самоссылающимся списком при ленивом вычислении разворачивается
в тот же код, но на _опытный_ взгляд выглядит почти как исходное
математическое определение. А при необходимости вычислить много чисел
дает бесплатную мемоизацию (достаточно вытащить fibSeq в toplevel), со
сложностью вычисления O(количество запросов плюс максимальное число),
вместо O(их произведение). В неленивом варианте мемоизацию придется
делать отдельно. Но неопытным взглядом прочесть этот код...
>> Но порой и убавляет. Работа с рекурсивными конструкциями зачастую
>> заметно упрощается...
DK> Охотно верю!
DK> ********************
DK> Так, уже полночь, и я всё ещё не вычитал всё письмо. Это в некотором
DK> роде сырец, и я уже весьма подустал. У меня остался один тезис, который
DK> я не знаю, куда впихнуть и в каком контексте. Поэтому приведу его просто
DK> так.
DK> Самое важное в программировании -- это понятный процесс вычисления. При
DK> использовании Haskell в силу ленивости он несколько тяжелее поддаётся
DK> осмыслению.
DK> Это тезис спорный, и я охотно от него откажусь, если что. Я и сам в нём
DK> не уверен, время позднее, и вообще я агностик. :)
Я не согласен с тем, что важен понятный процесс. Важен понятный способ.
Ты же не копаешь, как процессор выполняет сложение (даже если речь идет
о сложении не машинных целых, а больших, и складывает их не процессор, а
вообще библиотека). Ты веришь, что если применить эту операцию к двум
числам, то получится их сумма.
Лучше всего, чтобы результат получался из исходных данных путем понятной
комбинации операций с понятными свойствами. А уж какой порядок
вычислений — естественный (ленивый в λ-исчислении считается естественным
:) или какой другой — вопрос, _как правило_, для понятности
несущественный.
Да, ленивость иногда влияет на понятность, но в какую сторону — заранее
не предскажешь. А думать над процессом вычисления раньше времени не
надо, ты ж не процессор.
Reply to: