Logo

Объектная алгебра

Объектная алгебра — внутренний термин Кантора, обозначающий совокупность обобщенных операций по корекурсивной обработке контейнеров, сделанных по аналогии с SQL. Сюда входят:
  • Итерирующие выражения, обход деревьев и графов (аналог map).
  • Внешние и внутренние соединения (декларативный аналог map для данных).
  • Пересечение, вычитание, объединение и прочие операции из теории множеств.
  • Группировка и агрегатные функции (reduceсвертка списка).
  • Сортировка значений.
Главное отличие объектной алгебры от SQL — работа с произвольными контейнерами, а не только с таблицами и представлениями, ведь СУБД-шных таблиц и представлений в Канторе нет.

Упорядоченность контейнеров

Множества SQL не упорядочены, поскольку основаны на реляционной парадигме. Для прямого доступа реляционным множествам нужны индексы, для уникальности элементов — первичные и уникальные ключи, а для упорядоченности — явно заданный оператор order by, эти самые индексы и ключи использующий. СУБД, по сути, сводит множества к единственной реализации — таблице с полями, доступ к которой легко может быть скрыт за магией среды.

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

Отличие объектно-ориентированной БД от реляционной

Вполне возможно, что внутренняя упорядоченность — это именно то, что отличает объектно-ориентированную БД от реляционной. Поскольку всё есть контейнер, объектно-ориентированная БД не делает различий между таблицей и полем, и если попытаться адаптировать SQL к ОО-среде, это непременно придется учесть. В Канторе это выливается во from из любого выражения, без явно заданного select.

В ранних версиях синтаксиса Кантора наоборот, был select откуда угодно, а смысл from еще был неясен. Но с первого дня было понятно, что в объектно-ориентированной СУБД select и from — одно и то же.

Отделение структур данных от вычислений

Концептуально объектная алгебра служит для отделения структур данных от вычислений на уровне реализации. В объявлениях данные отделяются от вычислений классами и функциями, а в реализации — объектной алгеброй. Таким образом программа — (фрактальный) набор узлов — пересечений данных с вычислениями. Это переосмысление формулы Вирта «алгоритмы + структуры данных = программы» на современном технологическом уровне, через ФП и ООП.

Если структуры данных и вычисления концептуально разнесены, имеет смысл говорить об аналоге гарвадской архитектуры в языке программирования. Цель ее в том, чтобы иметь возможность анализировать структуры данных отдельно от процедур их обработки, делая структуры данных самодостаточными и самоценными, как происходит в СУБД.

Отсутствие ссылок на код

Объектная алгебра — это альтернативная реализация концепции функций первого класса в языке без ссылок на код, что сделано для упрощения частичных вычислений. Логично, что раз данные и вычисления концептуально разделены и пересекаются в строго заданных точках, организовать их частичное вычисление будет намного проще, чем продираться через функции по ссылкам.

В Канторе нет ссылок на код, поэтому родную функцию нельзя передать как обратный вызов или делегат. Вместо этого Кантор предлагает концепцию итерирующих выражений. По большому счету, это части оператора select SQL, вытащенные из окружения РСУБД и погруженные в объектную среду языка общего назначения.

Именно из-за объектной алгебры в Канторе нет явного каррирования, поскольку оно имеет смысл только вместе с передачей функций в функции. Возможно, итераторы объектной алгебры являются неявным каррированием с некоторыми дополнительными атрибутами.

Итерирующие выражения

Концепцию объектной алгебры можно сравнивать и с LINQ, но в .NET LINQ — своего рода синтаксический сахар, существующий одновременно с традиционными циклами и итераторами, через которые этот LINQ эмулируется. В Канторе же нет циклов, а итерирующие выражения вписаны в язык как часть реализации объектной алгебры.

В компиляторе Кантора итерирующие выражения будут напрямую порождать машинный код, а не эмулироваться библиотекой, то есть играть ту же роль, что представления (view) в СУБД.

Итерирующие выражения как замена циклам

В императивных языках программирования циклы — одна из базовых управляющих структур. Циклы нужны для реализации итеративных функций (рядов) и обхода контейнеров. Можно говорить, что в императивных языках итеративные функции и итераторы выражены через циклы.

Во фрактальной модели, напротив, всё есть контейнер. Контейнер в Канторе — тоже функция. Будучи функцией, контейнер может быть не только хранилищем данных, но и любой итеративной функцией, значения которой нигде не хранятся, а вычисляются на лету. В этом смысле понятие контейнера в Канторе близко понятию списка в Лиспе, с той разницей, что Кантор не ограничивается списками.

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

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

Синтаксис итерирующих выражений

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

Общий синтаксис итерирующего выражения:
итератор = выражение [блок-from] [блок-where]

блок-from = "from" выражение "to"|"downto" выражение ["by" выражение]
блок-where = "where" условия
Планируется, что смысл where будет аналогичен SQL:
Упоминание членов охраняемого выражения обозначает итерации, а внешние по отношению к охране условия — немедленный выход, аналогичный оператору break.
На данный момент блок с from считается синтаксическим сахаром к общей форме с where, содержащим выражения с prior, но использование ключевого слова prior для обозначения линейных итераций пока вызывает сомнение. Слово prior взято из SQL, где оно обозначает уровни при построении дерева, и в этой роли (предположительно) его можно считать наиболее употребительным с точки зрения носителя английского языка.

В рамках этой темы выходит, что ключевое слово for исключается из языка.

Пример итерирующего выражения

Простой пример вывода в консоль:
with
  console = new Platform:Console;
do
  console.WriteLine(from 1 to 10);
end;
Легко догадаться, что этот код должен напечатать числа от 1 до 10.

Конструкция from 1 to 10анонимный итератор, последовательно возвращающий значения от 1 до 10, а сама конструкция является выражением объектной алгебры и аналогична оператору yield в некоторых языках программирования.

Итерирующее выражение как виртуальный список

Итерирующее выражение, записанное при помощи from..to, представляет собой виртуальный список: объекта типа «список» в коде нет, а значения его есть. Порождаемый им скрытый цикл — аналог nested loops в плане SQL.

Можно говорить, что итерирующее выражение — способ сгенерировать несколько вызовов использующего его кода, цикл наоборот. Итерирующее выражение — разновидность ленивой функции. Ленивые вычисления будут развертываться в точке вызова, при переходе от функциональной парадигмы к процедурной. В нашем примере это попадает на вызов Console.WriteLine. Итерирующий параметр развернется, и Console.WriteLine будет вызвана 10 раз.

Списковые включения

Близкое к объектной алгебре понятие называется списковым включением, в Википедии даже есть пример вложенных итераций по переменным на Питоне:
[(x, y) for x in range(1, 10) for y in range(1, 10) if x % y == 0]
Не знаю, допустима ли здесь в Питоне блочная запись, но таком виде смотрится не очень читабельно, для понимания нужно вглядываться и вникать. Проблема та же, что и с SQL, записанным в одну строчку.

В качестве реализации списковых включений в Википедии упоминается и LINQ.

См. также

Комментариев нет :

Отправить комментарий

Выбрав в выпадающем списке пункт «Имя/URL», можно оставить комментарий от своего имени без предварительной регистрации.