Что такое «многосортная алгебра», и как я могу использовать ее для решения «реальных проблем»?

Question

Очевидно, что Александр Степанов в своем интервью 1002 * заявил следующее:

«Я считаю, что ООП [объектно-ориентированное программирование] технически несостоятельно.Он пытается разложить мир с точки зрения интерфейсов, которые различаются по одному типу. Чтобы справиться с реальными проблемами, вам нужны мультисортированные алгебры - семейства интерфейсов, охватывающих несколько типов. ” [Выделено добавлено.]

Игнорированиеего утверждение относительно ООП на мгновение, что такое «многосортные алгебры», помимо его краткого определения, и можете ли вы привести практический пример их использования (на языке по вашему выбору)?

Answer 1

Я полагаю, что он говорил о родовом программировании (он придумал термин ), независимо от того, подразумевается ли он в контексте этого разговора о STL или "в целом" в чувство:

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

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

• Для C ++ кажется, по крайней мере, для Степанова, это соответствует шаблонам (хотя идеи о том, как сделать это лучше всего , все еще развиваются ).
• Для ОО-языков (Generic Java, C #) ограничения на параметры типа обычно выражаются с использованием границ подтипа («ограниченные подстановочные знаки» ...).
• Для Haskell или Scala у вас есть (соответственно и аналогично) классов типов или имплицитов .
• Семейство языков ML предпочитает делать это с использованием модулей .
• обратите внимание, что ряд корректных помощников (которые могут выражать свойства * в качестве типов) в качестве "честных богов" разработали разновидность классов типов: Изабель, Кок, Матита такие примеры

Обратите внимание, что Степанов только что соавтором всей книги дал исчерпывающую разработку библиотеки, которая включает в себя точно что он (я думаю) имеет в виду. Так что, если вам нужны примеры в C ++ , это определенно то место, куда вам следует обратиться. Также обратите внимание, что это гораздо более развито, чем общепринятая сейчас рекомендация кодировать интерфейс, а не объект .

Под «практическим примером» я не знаю, имеете ли вы в виду «как» или «почему», кто-то его использует. Чтобы дать карикатурно быстрый ответ на вопрос «почему», универсальность хороша, потому что, как обычный полиморфизм, она позволяет повторно использовать код . Но, что более важно:

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

2. , указав, как этот интерфейс соответствует некоторым вашим данным, вы можете выбрать безопасный тип для выбора только тех элементов, которые соответствуют вашим потребностям. Например, вы, вероятно, знаете, что оператор сокращений (reduce в Python & Hadoop, fold для ряда функциональных языков) распараллелен, только если порядок, в котором вы применяете функцию сокращения, не не имеет значения (+, x, min, and работают, но разница в настройках не работает). Если у вас есть понятие «тип, снабженный ассоциативной операцией», вы знаете, что сможете вызвать параллельное сокращение для него.

3. любые издержки, связанные с универсальностью, происходят во время компиляции. Например, шаблоны работают очень быстро

Если вы видели какой-то универсальный Java, посмотрите, скажем, Comparable универсальный интерфейс. Он определяет только одну операцию, но контракт, который он заключает, хотя и является базовым, очень похож на алгебраический. Я цитирую:

Для математически наклоненного отношения, которое определяет естественное упорядочение для данного класса C, будет:

  {(x, y) such that x.compareTo((Object)y) <= 0}.

Коэффициент для этого общего заказа:

  {(x, y) such that x.compareTo((Object)y) == 0}.

Из контракта на сравнение немедленно следует, что частное является отношением эквивалентности на C> и что естественное упорядочение является полным порядком на C.

Теперь я могу написать метод, который выбирает минимум один раз, и использовать его для любого типа, который подходит этому интерфейсу :

 public static <T extends Comparable<T>> T min (T x, T y) {
   if (x.compare(y) < 0) x; else y;
 }

Естественно, поскольку способ, которым программные конструкции реализуют это понятие, сильно различается, то, что вы получите с точки зрения удобства использования и выразительности, также будет меняться. Возможно, вам не следует судить об универсальном программировании данных только по ОО-языкам, таким как C ++ или Java, - но я уже написал слишком много, чтобы начать с присваивания модуля или автоматического создания экземпляров классов типов.

Answer 2

Я опоздал, но, возможно, это будет полезно для вас. Пользователь huitseeker написал отличный ответ с точки зрения разработки программного обеспечения. Я хочу ответить на ваш вопрос с точки зрения математики. До погружения в мир программного обеспечения Алексей Степанов был математиком и изучал аннотация и универсальную алгебру. И он часто пытался внести строгие математические основы в мир разработки программного обеспечения и алгоритмов. В своих книгах От математики до общего программирования и Элементы программирования он отстаивает эту практику проектирования. Его идеи о смешении понятий алгебраических структур и проектировании программного обеспечения были реализованы в понятии generic programming. А теперь давайте поговорим о его цитате:

Для решения реальных задач вам нужны многосортные алгебры - семейства интерфейсов, охватывающих несколько типов

По моему мнению, здесь есть две основные концепции, которые он хотел бы упомянуть: идея абстрактный тип данных (ADT) и алгебраическая структура . Первая концепция: ADT. ADT - это математическая модель для типов данных, в которой тип данных определяется только его семантикой. Степанов противопоставил идею ADT идее object в смысле ООП. Объект содержит данные и состояние, в то время как ADT - , а не . ADT - это behavioural abstraction, operation cluster, который описывает взаимодействие с данными. Поведенческая абстракция полностью описывается с помощью алгебраической спецификации абстрактного типа данных. Вы можете прочитать об этом больше в оригинальной статье Liskov & Zilles , также я рекомендую вам бумагу Объектно-ориентированное программирование в сравнении с абстрактными типами данных от Уильям Р. Кук .

( Discalimer : Вы можете пропустить этот абзац, потому что он более "математический и не столь важный" ) Сначала я хочу уточнить некоторую терминологию. Когда я говорю о algebraic structure, это то же самое, что алгебра. Слово algebra часто также используется для алгебраической структуры. Чтобы быть более точным, когда мы говорим об алгебраических структурах (алгебрах), мы обычно имеем в виду алгебру над алгебраической теорией . Существует понятие многообразия алгебр , поскольку существует несколько понятий алгебраической структуры на объекте некоторой категории. По определению algebraic theory (алгебра над ним) состоит из спецификации операций и законов, которым должны удовлетворять эти операции: это рабочее определение алгебраической структуры, которую мы будем использовать, и это определение, я думаю, Степанов неявно упоминается в цитата.

Второе понятие , которое Степанов хотел упомянуть, является наиболее интересным свойством АТД: они могут быть формально смоделированы непосредственно как many-sorted algebraic structures. Давайте поговорим об этом более формально. Алгебраическая структура - это carrier set с одной или несколькими заданными конечными операциями. Эти операции обычно определяются не над одним набором, а над несколькими. Например. давайте определим и алгебру, которая моделирует конкатенацию строк. Эта алгебра будет определяться не для одного набора строк, а для двух наборов: набор строк S и набор натуральных чисел N, потому что мы можем определить операцию, которая может конкатенировать строку с собой некоторое конечное число раз. Таким образом, эта операция займет два операнда, принадлежащих различным базовым (несущим) наборам: S и N. Набор, определяющий эти различные операнды (их типы) в алгебре, называется набором sorts. Sort является алгебраическим аналогом типа. Алгебра с множественными сортами называется многосортной алгеброй. В универсальной алгебре в signature перечислены операции, которые характеризуют алгебраическую структуру. Многосортная алгебраическая структура может иметь произвольное количество областей. Сортировки являются частью подписи, и они играют роль имен для разных доменов. Многочисленные сигнатуры также предписывают, для каких сортов определяются функции и отношения многосортной алгебраической структуры. Для односортного множества алгебр сигнатура - это множество, элементы которого называются операциями, каждому из которых присваивается кардинальное число (0,1,2,…), называемое его арностью. Сигнатура многосортированной алгебры может быть определена как Σ = (S,OP,A), где S - набор имен (типов) сортировки, OP - набор имен операций и A - арности, как и раньше, за исключением того, что теперь это арность представляет собой список ( последовательность или, в более общем случае, свободный моноид ) входных сортировок, а не просто натуральное число (длина списка) вместе с одной выходной сортировкой. Теперь мы можем создать алгебраическую спецификацию абстрактного типа данных ADT в виде тройки:

ADT = (N, Σ, E)

, где N - имя абстрактного типа данных, Σ = (S,OP,A) - сигнатура многосортной алгебраической структуры, E = {e1, e2, …,en} - конечный набор равенств в сигнатуре. Как вы можете видеть, у нас есть строгое математическое описание ADT. В математике многие сортированные алгебраические структуры часто используются в качестве удобного инструмента, даже если их можно избежать с небольшими усилиями. Многочисленные алгебраические структуры редко определяются строгим образом, потому что это просто выполнить обобщение явно. Вот почему теория многогранных алгебр может быть успешно применена к разработке программного обеспечения.

Итак, Алексей Степанов хотел сказать, что он предпочитает ООП и общее программирование ООП, потому что, таким образом, мы можем создавать программы со строгой математической / алгебраической основой. Я высоко ценю его усилия. Мы все знаем, что алгебраический дизайн всегда правильный, строгий, красивый, простой и дает нам лучшие абстракции.

Answer 3

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

Комуиметь дело с реальными проблемами, которые вам нужны многосортные алгебры - семейства интерфейсов, которые охватывают несколько типов.

Из моих чтений, я думаю, семейства интерфейсов, которые охватывают несколько типов звучит очень похожеклассы типов из Haskell, что аналогично понятиям из C ++.Возьмем класс типа, например Foldable, это на самом деле интерфейс с параметризацией типа, т.е.семейство интерфейсов, которые охватывают несколько типов.Итак, что касается вашего вопроса о том, как решать проблемы с многосортными алгебрами, универсальное программирование - это все, что нужно, если вы понимаете классы типов или понятия.