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

Ответ 1

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

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

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

• Для С++ кажется, что, по крайней мере, Степанову - это соответствует шаблонам (хотя идеи о том, как сделать это лучше всего все еще развиваются).
• Для языков OO (Generic Java, С#) ограничения на параметры типа обычно выражаются с помощью ограничений подтипа ( "ограниченные подстановочные знаки"...).
• Для Haskell или Scala у вас есть (соответственно, и аналогично) типы классов или имплициты.
• Семейство языков ML предпочитает делать это с помощью модулей.
• обратите внимание, что ряд помощников по доказательству (которые могут выражать свойства "честный к богу" как типы) развили типы классов: Isabelle, Coq, Matita - такие примеры.

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

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

• Полиморфный код

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

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

• любые сбои, вызванные типичностью, возникают во время компиляции. Например, шаблоны носят легально быстрый

Если вы видели какую-то общую 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;
 }

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

Ответ 2

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

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

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

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

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

ADT = (N, Σ, E)

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

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