Привет!
Конференция FPConf уже завтра, сегодня последний шанс купить билет и присоединиться! Регистрация — тут.
Накануне мы решили задать нашим спикерам один довольно неоднозначный вопрос. Большая часть ответов была опубликована вчера — тут
А сегодня мы получили ответ от нашего гостя Эдварда Кметта. Пока публикуем без перевода, обновим пост после конференции.
Вопрос был такой:
В объектно-ориентированных языках есть широко известный список паттернов проектирования (design patterns) от «Банды четырех» (Gang of Four). В функциональных языках такого известного списка не существует. С вашей точки зрения, почему так?
Подобные паттерны не нужны при программировании на функциональных языках или просто их канонический список еще не сложился?
Эдвард Кметт, Глава Haskell core libraries committee, Haskell программист, математик.
Design patterns give you a vocabulary for how to talk about things that your language isn't able to let you craft into a library. We use the term «design pattern» to talk about iterators, visitors, singletons, command patterns, etc. Each of which conveys the «general idea» of what is going on but doesn't actually give you the details of how to use the particular instantiation. You still have to care a great deal about the instances of the abstraction, and can do nothing based on symbol pushing with laws alone. Functional programmers are much much happier with symbol pushing than imperative programmers. That is a lot easier in a functional setting, where you don't have to go off and reason with Hoare logic or separation logic to figure out the state of the universe after each instruction like you do in an imperative setting.
We do have «design patterns» after a fashion in the functional programming world. The notion of monad «transformers», of effect systems, of encoding things in a 'finally tagless' manner, or initial encodings of syntax trees, of using 'data types a la carte', building interpreters for embedded DSLs, or «classy lenses» all have that same sort of design pattern feel to them. Data.Vector replicates the same list-like API a half dozen times. These all rise at least to the level functional programming idioms. The major difference in culture I think is that for the most part we like even these patterns or abstractions to carry with them some laws, while design patterns merely carry cultural guidelines.
In practice I personally like to pursue constructions that are somehow universal or free or something that is initial or terminal in a category theoretic sense. Why? Because if I can produce such a solution any other solution in the space should factor through mine.
But I think ultimately a design pattern in most settings is an attempt to go a bit beyond the notion of the idioms of a language, but not quite into the realm of laws, and that middle ground isn't something we tend to like too much as functional programmers. After all, an abstraction you can't reason about isn't an abstraction at all.
А что вы думаете по этому поводу?
Обсудим на FPConf.ru. Присоединяйтесь!
Конференция FPConf уже завтра, сегодня последний шанс купить билет и присоединиться! Регистрация — тут.
Накануне мы решили задать нашим спикерам один довольно неоднозначный вопрос. Большая часть ответов была опубликована вчера — тут
А сегодня мы получили ответ от нашего гостя Эдварда Кметта. Пока публикуем без перевода, обновим пост после конференции.
Вопрос был такой:
В объектно-ориентированных языках есть широко известный список паттернов проектирования (design patterns) от «Банды четырех» (Gang of Four). В функциональных языках такого известного списка не существует. С вашей точки зрения, почему так?
Подобные паттерны не нужны при программировании на функциональных языках или просто их канонический список еще не сложился?
Эдвард Кметт, Глава Haskell core libraries committee, Haskell программист, математик.
Design patterns give you a vocabulary for how to talk about things that your language isn't able to let you craft into a library. We use the term «design pattern» to talk about iterators, visitors, singletons, command patterns, etc. Each of which conveys the «general idea» of what is going on but doesn't actually give you the details of how to use the particular instantiation. You still have to care a great deal about the instances of the abstraction, and can do nothing based on symbol pushing with laws alone. Functional programmers are much much happier with symbol pushing than imperative programmers. That is a lot easier in a functional setting, where you don't have to go off and reason with Hoare logic or separation logic to figure out the state of the universe after each instruction like you do in an imperative setting.
We do have «design patterns» after a fashion in the functional programming world. The notion of monad «transformers», of effect systems, of encoding things in a 'finally tagless' manner, or initial encodings of syntax trees, of using 'data types a la carte', building interpreters for embedded DSLs, or «classy lenses» all have that same sort of design pattern feel to them. Data.Vector replicates the same list-like API a half dozen times. These all rise at least to the level functional programming idioms. The major difference in culture I think is that for the most part we like even these patterns or abstractions to carry with them some laws, while design patterns merely carry cultural guidelines.
In practice I personally like to pursue constructions that are somehow universal or free or something that is initial or terminal in a category theoretic sense. Why? Because if I can produce such a solution any other solution in the space should factor through mine.
But I think ultimately a design pattern in most settings is an attempt to go a bit beyond the notion of the idioms of a language, but not quite into the realm of laws, and that middle ground isn't something we tend to like too much as functional programmers. After all, an abstraction you can't reason about isn't an abstraction at all.
А что вы думаете по этому поводу?
Обсудим на FPConf.ru. Присоединяйтесь!
Комментарии (16)
dginz
14.08.2015 12:34+1Не совсем понял, что автор имел ввиду. Я перевёл как «абстракция, которая не течёт — вообще не абстракция».
Казалось бы, «абстракция, которую нельзя обсудить (поспорить), не является абстракцией в принципе.»
alexeyrom
14.08.2015 22:45+1В данном контексте — абстракция, о которой нельзя рассуждать с математической строгостью. Чтобы в этом убедиться, достаточно погуглить haskell reasoning.
Yuuri
17.08.2015 00:38Именно. Чуть выше Эдвард прямо пишет «основное различие – по большей части мы хотим, чтобы наши абстракции подчинялись некоторым формальным законам, тогда как паттерны проектирования просто следуют культурным соглашениям».
FiresShadow
17.08.2015 08:27Назовите пожалуйста паттерн, который с вашей точки зрения не удовлетворяет формальным законам.
FiresShadow
17.08.2015 12:00Можно менять реализацию абстракции, не нарушая самой абстракции. А вот провозглашая доказательство абстракции частью абстракцию, имхо, мы отказываемся от абстрактного мышления. Например, есть абстракция «веселиться». Реализация: веселиться = бегать, прыгать, плясать. Есть доказательство, что при веселье происходят бег, прыжки и пляски. Но вот приходит аналитик, и заявляет, что теперь веселиться = смеяться, хлопать в ладоши. Абстракция не изменилась, но её доказательство и реализация изменились. Вывод: доказательство не часть абстракции. Смысл абстракции как раз в том и заключается, что некая общая идея отделяется от её конкретной реализации в частном случае.
Согласен, идея доказательства контракта функции на основе её исходного кода выглядит привлекательной и перспективной, но непонятно, причём тут паттерны проектирования. Паттерны борются со сложностью программы, проверки корректности программы борются с ошибками программиста.
roman_kashitsyn
17.08.2015 17:04+2Паттерны борются со сложностью программы, проверки корректности программы борются с ошибками программиста.
Пример — абстракцияMonoid(Appendable). Абстракция состоит из бинарной операции op и единичного элемента unit. Законы:
- Левая единица:
op(unit, x) = x - Правая единица:
op(x, unit) = x - Ассоциативность:
op(x, op(y, z)) = op(op(x, y), z)
Если кто-то утверждает, что его тип является моноидом, это можно формально проверить. Далее, можно написать кучу библиотечного кода, работающего с моноидами (последовательная и параллельная свёртка произвольного контейнера, например). После формальной проверки можно использовать этот код и спать спокойно — если его реализация корректна, то с высокой вероятностью проблем не возникнет.
Какие законы можно выделить для «шаблона» «Абстрактная фабрика»? Можно ли формально доказать, что ваш тип удовлетворяет этим законам? Можно ли написать полезную библиотеку, работающую с абстрактными фабриками?FiresShadow
18.08.2015 07:24Спасибо за пример.
Если кто-то утверждает, что его тип является моноидом, и это нельзя доказать, то этому можно поверить. Да, программист может ошибиться, но абстракция от этого не перестаёт быть абстракцией.
Какие законы можно выделить для «шаблона» «Абстрактная фабрика»?
Закон единственности ответственности: алгоритм выбора того, какой именно класс использовать, не относится ни к одному из создаваемых фабрикой классов.
Можно ли формально доказать, что ваш тип удовлетворяет этим законам?
Доказать, не нарушает ли закон единственности ответственности, без ИИ или человека, наверное, не получится. Но при помощи статического анализатора можно найти потенциальные проблемные участки. Можно ли доказать, что класс является фабрикой? Да, можно. Информация об абстракции содержится в интерфейсе. Если класс реализует интерфейс IFactory, но не реализует объявленную в нём функцию TSomeClass Create(), то возникнет ошибка компиляции. Может ли функция вернуть null, также можно формально проверить.
Можно ли написать полезную библиотеку, работающую с абстрактными фабриками?
Да, можно. Например, в Castle.WindsorContainer есть TypedFactory. Или можно написать библиотеку, которая будет вызывать TSomeClass Create() в нужный момент времени.
Проверять ошибки программиста это круто, но при чём тут абстракция?roman_kashitsyn
18.08.2015 09:50+1тип является моноидом, и это нельзя доказать
Тип либо является моноидом, либо не является, третьего не дано. Доказывается этот факт исключительно формальной проверкой чётко заданных математических законов. Если хотя бы один из законов не удовлетворяется для всех возможных значений типа — проверка не пройдена.
Например, в Castle.WindsorContainer есть TypedFactory.
Ну вот отличный пример «определённости» ООП-шаблонов. Вы дали ссылку на реализацию шаблона «Фабрика», а не «Абстракная фабрика». Отличие в том, что «Абстрактная фабрика» создаёт связанные группы объектов.
Проверять ошибки программиста это круто, но при чём тут абстракция?
Эдвард как раз указывает на разницу к подходе к абстракциям — ФП идёт в сторону строгих определений абстракций с возможностью формальных доказательств (пусть и проводимых людьми). В типичном ООП-подходе к абстракции формальных определений нет и не может быть, и это создаёт много путаницы.FiresShadow
18.08.2015 10:54Вы дали ссылку на реализацию шаблона «Фабрика», а не «Абстракная фабрика».
Описание того, какой тип инстанцировать, передаётся в WindsorContainer. Фабрика наследуется от интерфейса, её реализация динамически кодогенерится контейнером. Итого, есть интерфейс фабрики. Внутри фабрики есть логика, определяющая, какой конкретный тип будем инстанцировать. Реализация фабрики и её логика может различаться в разных частях программы (например, если использовать другой контейнер). Имхо, это абстрактная фабрика.
Эдвард как раз указывает на разницу к подходе к абстракциям — ФП идёт в сторону строгих определений абстракций с возможностью формальных доказательств (пусть и проводимых людьми). В типичном ООП-подходе к абстракции формальных определений нет и не может быть
Есть такая штука, как контракт. При помощи него можно описать пред-условия функции, инварианты и постусловия. Контракты не доказываются, но могут проверяться в момент исполнения. Описать факты, не относящиеся непосредственно к единичному вызову функции, через контракт не получится. Т.е. op(x, op(y, z)) = op(op(x, y), z) или another(x, op(y, z)) = op(another(x, y), z) описать через контракт не получится, но это можно сделать в summary функции, пометив тегом code. То есть средства для формального описания инвариантов в ООП есть, причём довольно давно.
То что ФП предоставляет средства для доказательства инвариантов — несомненно, здорово. Но не у всех абстракций есть эти самые инварианты. Я уже приводил пример с абстракцией «демонстрировать радость». На моём опыте у подавляющего большинства абстракций, реализуемых программистами, нет инвариантов, а те редкие инварианты, которые всё же встречаются, обычно легко вписываются в контракт. Инварианты в основном часто встречаются в структурах данных и базовых мат. операциях, которые давно реализованы на уровне языка и поведение которых всем давно известно.
Я бы не стал утверждать, что «абстракция которую нельзя доказать — не абстракция» теоретически, а уж практически — тем более.
Нельзя недооценивать возможности ФП. Чего только стоит масштабируемость ФП программ, доказательство инвариантов тоже вносит свой вклад в копилку прогресса. Но, имхо, как то уж ФП энтузиасты это слишком превозносят, вплоть до того дошли, что вне ФП абстракций нет.roman_kashitsyn
18.08.2015 11:23+1То что ФП предоставляет средства для доказательства инвариантов — несомненно, здорово.
Это не ФП предоставляет средства, а математика и логика. Эти же методы можно применять при разработке на том же C++. Просто в ФП языках сама парадигма склоняет к формальным методам.
Я уже приводил пример с абстракцией «демонстрировать радость»
Честно говоря, я не понял этого примера. Не понял, в чём заключается абстракция и каковы её свойства. Если меняются законы, должны меняться и абстракции. Изменят ли когда-нибудь определение Моноида? Не думаю. Ваш тип со временем может перестать быть моноидом относительно одной из операций, и вам просто нужно будет подыскивать другую абстракцию, а не менять определение моноида.FiresShadow
21.08.2015 11:04Если меняются законы, должны меняться и абстракции.
Внесения изменений в программу — дело обыденное, особенно на этапе сопровождения. Например, приходит пользователь и говорит: «добавьте мне в отчёте снизу такого-то столбца сумму всех ячеек этого столбца». Абстракция отчёта от этого ни капли не изменилась, но вот её реализация изменилась. Отчёт — это предоставление определенной информации пользователю в удобной и понятной форме. При этом мы не можем даже проверить, что пользователь получил эту информацию — а вдруг он в монитор не смотрит? При этом эту информацию ему можно передавать разными способами — хоть на бипере морзянкой напискивать. Соответственно, во всём, что касается пользователя — мы не можем доказать, что добиваемся поставленной цели. Мы можем доказать, что делаем действия, которые, по нашему мнению, уместны. Доказать реализацию, но не абстракцию.
И, неожиданно, в сухом остатке в большинстве программ не остаётся больше ничего существенного и сложного, что нуждалось бы в доказательстве. Большинство программ работает следующим образом: пользователь 1)регистрирует изменения состояния чего-нибудь в системе и 2)запрашивает сводную информацию по состояниям. Так работают всевозможные erp-системы, онлайн-магазины, социальные сети, поисковики (в случае поисковиков изменения в системе регистрирует не пользователь, а паук crawler), онлайн-кинотетры, энциклопедии, сайты поиска работ, всевозможные корпоративные приложения и пр. При этом чаще всего используются декларативные средства для отображения и получения информации. Декларативно указываем базе данных, какие данные хочется получить. Декларативно указываем гриду, из какого поля брать информацию и в столбце с каким именем её отображать. Декларативно указываем в HTML, как следует отрисовать страничку. Соответственно, логики непосредственной отрисовки и получения данных в приложении нет. Конечно, можно доказать, что такая-то функция формирует такие-то данные в таком-то формате, но ведь можно формировать данные в другом формате и отдавать его другой библиотеке отображения. Т.е. опять таки доказывается и тестируется реализация, но не абстракция. Теоретически можно конечно изловчиться и доказать, что в результате работы функции, операционки и драйвера будет отрисовано нечто, что удовлетворяет неким формальным требованиям (которые практически невозможно сформулировать — дизайн графического элемента может сильно варьироваться), из чего мы сделаем вывод, что это конкретный графический элемент. Но ради чего такие сложности, если требования по отображению задаются декларативно?!
За вычетом этого, остаются функции операционного уровня. Наподобие, если нажали на такую то кнопку — отрисовать такую то формочку. Но их логика, как правило, настолько тривиальна, что не нуждается в доказательстве.
Но это, конечно, лишь только описание ситуации на практике. Если бы программирование было сосредоточено не вокруг удовлетворения нужд рядовых пользователей, а вокруг невероятно зубодробительных математических расчётов, то ситуация, вероятно, была бы несколько иной.roman_kashitsyn
21.08.2015 11:57+1добавьте мне в отчёте снизу такого-то столбца сумму всех ячеек этого столбца
Сколько ОО-шаблонов проектирования нужно, чтобы реализовать эту возможность? Какие будем выбирать?
Подход ФП сообщает, что:
- Числа в столбцах наверняка являются некоторыми числами одного типа, которые являются Monoid с нулём в качестве единичного элемента и сложением в качестве операции.
- Столбец наверняка является структурой данных, удовлетворяющей законам Foldable.
Итого, для получения суммы можно вызвать на столбце библиотечную функцию свёртки вроде foldMap, которая была написана один раз для свёртки произвольных моноидов (целых чисел, рациональных чисел, строк, etc.) на произвольных Foldable-структурах (списках, деревьях, векторах, таблицах, etc.).
К слову, можно доказать, что Double не является моноидом, поэтому fold лучше не использовать, а написать для суммирования специальный алгоритм, например, алгоритм Кэхэна.
Доказать реализацию, но не абстракцию.
Что это вообще означает «доказать абстракцию»?
Ещё раз: речь идёт о шаблонах в коде, о различии в подходах между ОО- и Ф- программистами.
ОО- держат в голове несколько эвристических правил, применяя известные шаблоны для организации кода, руководствуясь собственным вкусом и опытом.
Ф- в основном сводят всё к типам и функциям, по мере необходимости выделяя повторяющиеся шаблоны в абстракции с математически заданными законами. Некоторые шаблоны настолько вездесущи (вроде пресловутых монад), что для них пишутся библиотеки, а иногда даже вводится специальный синтаксис. В этом случае законы позволяют компилятору производить дополнительные оптимизации и преобразования кода.
В более общем случае законы сообщают, можно ли скормить ваш тип библиотеке, получив желаемый функционал в замен.
в большинстве программ не остаётся больше ничего существенного и сложного, что нуждалось бы в доказательстве
Да вы оптимист. Читали ли вы Programming Pearls? Знаете, сколько людей не могут бинарный поиск корректно написать?FiresShadow
21.08.2015 15:15Что это вообще означает «доказать абстракцию»?
Ок, давайте ещё раз объясню. Вот смотрите, допустим ФПшная абстракция моноида: op(x, op(y, z)) = op(op(x, y), z), светофора: ТипДвиженияПешехода(СигнализироватьСветофором(МашинамНужноДвигаться)) = Стоять(), годового отчёта: СостояниеНалоговойПослеПросмотраОтчёта(ПостроитьОтчёт(Дата)) = Довольны(). Если мы доказываем, что в результате работы светофора пешеход останавливается, то мы доказываем абстракцию; если мы доказываем, что светофор периодически меняет цвет, то мы доказываем реализацию. Светофор может не менять цвет, а например пищать, но это всё равно светофор.
Приходит заказчик\аналитик, и предоставляет свои хотелки и бизнес-сценарии. Например, если у пользователя нету прав, то при попытке доступа на такую то страницу, переходить на страницу-заглушку. Вот как вы докажете, что производится переход на страницу-заглушку? Максимум, вы можете доказать, что производится попытка перевода браузера пользователя на какую то фиксированную страницу. И после того как страница-заглушка будет изменена на другую, ваше «математическое доказательство» будет неверно. Т.е. доказывается то реализация, а не абстракция.
Автор заявил, что «абстракция которую нельзя доказать — не абстракция», на что я возражаю, что вы можете доказать только низкоуровневые абстракции, которые в большинстве приложений даже не используются, потому как основные функции: доступ к данным, отображение данных, — делаются декларативно и при помощи сторонних библиотек.
- Левая единица:
FiresShadow
Паттерны проектирования подсказывают, как можно удачно сгруппировать данные и функции, чтобы код был более читаемым, модифицируемым и удобным в использовании. Например, паттерн NULL-object заключается в группировке вместе методов, реализующих поведение сущности, когда основополагающий признак сущности не определён. Flyweight рассказывает, как сохранить качество кода при оптимизации расхода памяти.
Имхо, паттерны согласуются с идеями ООП-языков и принципами проектирования.Необходимость в паттернах проектирования возникла, потому что люди, чётко понимающие принцип ООП, затруднялись эффективно применять его на практике. Часто в одном процессе участвуют несколько объектов, и непонятно, в какой класс следует поместить метод. И тут на помощь приходит медиатор, инкапсулирующий внутри себя взаимодействие группы объектов в рамках какого-то процесса.
В ФП основная единица — функция, и тут смысл проектирования сводится к грамотному распределению кода по функциям. И если поиск сходств и различий назначений методов в ООП (для грамотного их распределения по классам) вызывает сложности даже у опытных программистов, то дробление функции на несколько более простых вызывает сложности лишь у новичков. Вполне возможно, что большинство людей, кристально ясно понимающих принцип ФП, не будут периодически сталкиваться с проблемами реализации принципа ФП на практике по причине сложности самого принципа. Соответственно, не будет сложностей при реализации — не будет и паттернов. Однако будут сложности или нет — это как гадание на кофейной гуще. Сейчас ФП не получило широкого распространения среди решений сложных промышленных задач, поэтому рано делать какие-то выводы.
Не совсем понял, что автор имел ввиду. Я перевёл как «абстракция, которая не течёт — вообще не абстракция».
zw0rk
Абстракция, о которой нельзя рассуждать, вовсе и не абстракция.