search

Mazdaywik / mrefal

Компилятор Модульного Рефала
BSD 2-Clause "Simplified" License
6 stars 0 forks source link

Добавить неполное ООП в Модульный Рефал #1

Open Mazdaywik opened 8 years ago

Mazdaywik commented 8 years ago

Мотивация

Модульный Рефал имеет встроенный механизм инкапсуляции данных — так называемые «абстрактные типы данных», АТД. Модуль может определить несколько «тегов типа» — имён АТД, которыми может помечать некоторые скобочные термы (собственно, АТД-термы). Непосредственный доступ к содержимому АДТ-термов возможен только в функциях модуля, в котором определены метки. Другие модули могут манипулировать с АТД-термами, либо импортируя модуль, где они определены и вызывая его entry-функции, либо вызывая функции-callback’и того модуля.

Механизм АТД решает свою задачу: предотвращает доступ извне к содержимому, но при этом налагает жёсткое ограничение: либо нужно импортировать модуль, либо передавать callback, либо доступа вообще нет. Таким образом, возникают затруднения при написании некоторых универсальных служб (служб, которые могут работать с любыми объектными выражениями): сортировка, преобразование к строке, сериализация.

Другое ограничение АТД (в широком смысле) в модульных языках (Модульный Рефал, Модула-2) — необходимость прямого или косвенного импорта модуля, реализующего тип данных в модулях, использующих экземпляры этого типа. В результате возникает слишком жёсткая связь между отдельными компонентами (например, в синтаксическом анализаторе захардкожена ссылка на лексический анализатор).

Решение обеих проблем хорошо известно: разделение типа и интерфейса. Первая проблема решается тем, что универсальные службы предлагают интерфейс (например, ToString), который должны реализовать все типы, совместимые со службой. Вторая проблема решается тем, что клиенты зависят только от описания интерфейса, экземпляр типа, реализующий требуемый интерфейс, передаётся в клиенты методами верхнего уровня.

Предлагаемое решение

Концепция

В Модульном Рефале единица инкапсуляции — модуль. Это свойство разумно сохранить. Модульный Рефал — функциональный язык, поэтому интерфейс опишем как набор переопределяемых функций. Как-то так.

Некоторые модули предоставляют виртуальные функции, набор этих функций формирует некоторый интерфейс. Другие модули импортируют модули с виртуальными функциями и расширяют последние дополнительными предложениями, обрабатывающими АТД, реализованные в данном модуле. После чего можно вызывать виртуальные функции, передавая в них экземпляры АТД, для которых эти функции расширены. Виртуальные функции (они всегда экспортируются, пишем $VIRTUAL, подразумеваем $ENTRY) могут вызываться как из модулей, где они определены, так и из модулей, которые импортируют модули с виртуальными функциями. При этом последние ничего не знают о модулях, которые расширяют виртуальные функции.

Синтаксис

Виртуальная функция помечается ключевым словом $VIRTUAL и имеет одно и только одно виртуальное предложение. Виртуальное предложение состоит из одного образца (для краткости далее виртуального образца), который (а) может быть только жёстким образцом (без повторных переменных и открытых e-переменных), (б) должен содержать хотя бы один терм вида $DATA — признак виртуального предложения. Перед и после виртуального предложения могут располагаться обычные предложения с обычной семантикой.

Расширение виртуальной функции может располагаться только в модуле, который импортирует модуль, определяющий виртуальную функцию. Расширение виртуальной функции записывается как функция, помеченная ключевым словом $EXTENDS и имеющая имя ИмяМодуля.ИмяВиртуальнойФункции, где ИмяМодуля — имя модуля, где виртуальная функция определена. При этом в модуле не может дважды переопределяться одна и та же виртуальная функция. Каждое предложения расширения должно уточнять виртуальный образец, при этом на месте терма $DATA должен располагаться АТД-терм. Соответствие образцовых частей расширения виртуальному образцу должно контролироваться на стадии компиляции.

Расширение виртуальной функции самостоятельной функцией не является, предложения, перечисленные в теле функции, можно вызвать только вызывав виртуальную функцию. Соответственно, ключевое слово $ENTRY к расширению не применимо ибо бессмысленно.

Семантика

Примечание. Здесь описывается идеализированная модель, реализация может (и будет) отличаться, но её поведение должно совпадать с идеализированной моделью.

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

Следовательно, исполнение виртуальной функции идёт в следующем порядке:

  1. Сопоставления с образцами предложений, расположенных до виртуального предложения. Если одно из них оказалось успешным, выполняется соответствующее предложение, виртуальная функция на этом завершается.
  2. Сопоставление аргумента с каждым из образцов расширений функции. Все эти образцы, уточняя виртуальный образец, различаются тегами АТД в позициях термов $DATA. В модуле, расширяющем виртуальную функцию, могут использоваться только теги данных, которые в нём определены, поэтому образцы предложений различных модулей не конфликтуют между собой. Если одно из сопоставлений завершилось успешно, выполняется соответствующее предложение расширения и виртуальная функция завершается.
  3. Сопоставление с образцами предложений, расположенных после виртуального предложения. Тут всё аналогично п. 1.
  4. Если не было успешного сопоставления, функция падает с ошибкой.

    Пара слов о синтаксисе

  5. Ключевые слова $VIRTUAL и $EXTENDS избыточны: виртуальную функцию можно узнать по наличию виртуального предложения, расширение — по квалифицированному имени. Однако, добавление этих ключевых слов повышает ясность и читабельность программы.
  6. Возможное расширение синтаксиса: [$ENTRY] ИмяФункции $EXTENDS Модуль.ВиртуальнаяФункция — создаёт как обычную функцию (с именем ИмяФункции), так и расширение Модуль.ВиртуальнаяФункция с идентичным набором предложений.

    Реализация

    Back-end C++/SR

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

Допустим, выполнение виртуальной функции дошло до виртуального предложения. Сопоставим аргумент с виртуальным образцом — допустим, оно прошло успешно, каждый из символов $DATA наложился на АТД-терм. Возьмём, к примеру, первое вхождение символа $DATA — зная тип АТД, мы можем узнать модуль, в котором он переопределён, и попытаться в этом модуле найти расширение виртуальной функции. Расширение нашли — можем попробовать сопоставить аргумент с каждой из левых частей предложений расширения. Если одно из предложений расширения выполнилось, то виртуальная функция на этом завершается, иначе происходит переход на предложения, следующие за виртуальным. Заметим, что другие расширения виртуальной функции проверять не нужно — они не могут содержать на месте $DATA чужой АТД.

Очевидно, что путь поиска расширения избыточен: из цепочки тег АТД → модуль → расширение можно выкинуть модуль, храня в теге непосредственно расширения для разных АТД, причём только те предложения из расширений, которые относятся к данному типу.

На данный момент тег типа для АТД представляет собой пустую функцию, поскольку его роль — только отличать друг от друга разные АТД. Поэтому его можно пополнить новой информацией, новым поведением без конфликтов с имеющимся кодом.

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

$MODULE Модуль;

$VIRTUAL Гладить {
  Обычное = Предложение;
  Виртуальное $DATA;
  Предложение = Суффикса;
}

$END Модуль.

будет компилироваться во что-то вроде:

$MODULE Модуль;

$ENTRY Гладить {
  Обычное = Предложение;
  Виртуальное [s.Tag e.Info] = <s.Tag &Гладить%суф Виртуальное [s.Tag e.Info]>;
}

$ENTRY Гладить%суф {
  Предложение = Суффикса;
}

$END Модуль.

Здесь используется синтаксически невозможная [s.Tag e.Info], которая позволяет извлечь тег типа из АТД для осуществления косвенного вызова. Тег АТД является функцией, которая принимает указатель на суффикс и исходный аргумент, причём указатель на суффикс играет две роли: во-первых, служит тегом виртуальной функции, во-вторых, на него передаётся управление в случае невозможности сопоставления. На примере модуля-клиента всё будет понятно.

$MODULE Клиент;

$IMPORT Модуль;
$IMPORT Format;

$DATA Кот, Утюг, НеКласс;

$EXTENDS Модуль.Гладить {
  Виртуальное [Кот e.Кот] = Гладим кота;
  Виртуальное [Утюг e.Утюг] = Гладим бельё;
}

$EXTENDS Format.ToString {
  [Кот e.Кот] = 'Кота зовут ' e.Кот;
  [Утюг e.Утюг] = 'Утюг марки ' e.Утюг;
}

$END Клиент.

компилируется в

$MODULE Клиент;

$IMPORT Модуль;
$IMPORT Format;

Кот {
  & Модуль.Гладить%суф Виртуальное [Кот e.Кот] = Гладим кота;
  & Format.ToString%суф [Кот e.Кот] = 'Кота зовут ' e.Кот;
  s.Suf e.Arg = <s.Suf e.Arg>;
}

Утюг {
  & Модуль.Гладить%суф Виртуальное [Утюг e.Утюг] = Гладим бельё;
  & Format.ToString%суф [Утюг e.Утюг] = 'Утюг марки ' e.Утюг;
  s.Suf e.Arg = <s.Suf e.Arg>;
}

НеКласс {
  s.Suf e.Arg = <s.Suf e.Arg>;
}

$END Клиент.

Теги типов становятся уже таблицами виртуальных функций. Последнее предложение каждой виртуальной функции служит для передачи управления на суффикс, АТД, для которых расширения не определены, состоят только из одного такого предложения.

Back-end Простого Рефала

Реализуется аналогично back-end’у C++/SR с той лишь разницей, что конструкция [s.Tag e.Info] синтаксически недопустима, а значит, нужно идти в обход.

АТД, не участвующие в каком-либо расширении виртуальных функций, описываются как и раньше — пустая функция для тега и [Tag e.Info] для АТД-термов. Для типов, участвующих в расширении виртуальных функций тег описывается также, как и для предыдущего back-end’а, а терм — [Class Tag [Tag e.Info]] — таким образом, (а) по-прежнему обеспечивается инкапсуляция, но при этом есть доступ к тегу типа. Тег Class глобален на всю программу, объявляется в файле .main.sref как $EENUM.

Виртуальные предложения ожидают, что типы данных имеют вид [Class Tag [Tag e.Info]], поэтому при передаче в них АТД, не участвующих в расширениях виртуальных функций, выполнение сразу передаётся на суффикс. Пример выше может быть откомпилирован так:

$EXTERN Class;

$ENTRY МодульP_Гладить {
  #Обычное = #Предложение;
  #Виртуальное [Class s.Tag [s.Tag e.Info]] =
    <s.Tag МодульP_ГладитьX_суф #Виртуальное [Class s.Tag [s.Tag e.Info]]>;
  #Предложение = #Суффикса;
}

$ENTRY МодульP_ГладитьX_суф {
  #Предложение = #Суффикса;
}
$EXTERN Class;
$EXTERN МодульP_ГладитьX_суф;
$EXTERN FormatP_ToStringX_суф;

КлиентP_Кот {
  МодульP_ГладитьX_суф #Виртуальное [Class Кот [Кот e.Кот]] = Гладим кота;
  FormatP_ToStringX_суф [Class Кот [Кот e.Кот]] = 'Кота зовут ' e.Кот;
  s.Suf e.Arg = <s.Suf e.Arg>;
}

КлиентP_Утюг {
  МодульP_ГладитьX_суф #Виртуальное [Class Утюг [Утюг e.Утюг]] = Гладим бельё;
  FormatP_ToStringX_суф [Class Утюг [Утюг e.Утюг]] = 'Утюг марки ' e.Утюг;
  s.Suf e.Arg = <s.Suf e.Arg>;
}

$EMPTY КлиентP_НеКласс;

Back-end Рефала-5

Поскольку стадия компоновки является частью Модульного Рефала, здесь можно непосредственно реализовать семантику.

Заключение

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

Как внедрить наследование реализации, а главное, стоит ли его внедрять — вопрос открытый.

Mazdaywik commented 3 years ago

Для back-end’а SimRef АДТ можно представлять проще:

[DATA s.Tag e.Info]

Нет никакой необходимости мудрить с двойным вложением.

Mazdaywik commented 3 years ago

Как реализовать наследование

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

ООП

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

Требования к наследованию

Для начала нужно определить понятие «наследование». Наследование — механизм языка, позволяющий создавать новые классы на основе существующих, при этом класс-наследник получает некоторую функциональность своего предка. Наследование позволяет повторно использовать код класса-предка, а также определяет отношение подтипизации (классы-наследники являются подмножеством классов-предков).

Некоторые свойства:

И всё это нужно положить на язык программирования Модульный Рефал. Свойства Модульного Рефала, которым должно удовлетворять наследование:

В ОО-языках с ссылочными типами данных внутри методов доступна ссылка this или self (или с произвольным именем, например, в Обероне или Python’е). Ссылка указывает на объект, для которого был вызван метод. И динамический тип объекта может отличаться от статического типа, в котором был определён метод. Благодаря такому механизму можно в методах базового класса вызывать методы производного — вот он, шаблонный метод.

В Модульном Рефале ссылок нет, поэтому в «методах» класса нужно целиком иметь весь объект, но при этом доступ должен быть открыт только к части объекта на соответствующем уровне иерархии.

Требуется реализовать перечисленные выше свойства наследования при перечисленных ограничениях Модульного Рефала.

Синтаксис и семантика

Классы с наследованием расширяют предложенный ранее полиморфизм, т.е. синтаксис, описанный выше, остаётся актуальным. Также остаются актуальным некоторые решения проектирования:

Синтаксически обращение к классу будет выглядеть так:

o.〈ИНДЕКС〉 @ [〈ТЕГ〉 〈образец〉]

Описанная выше конструкция — это образец терма. o-переменная — терм самого объекта, по смыслу — t-переменная. @ [〈ТЕГ〉 〈образец〉] — вырезка из объекта соответствующего слоя. Далее эту конструкцию мы будем называть o-@-конструкцией.

Применение o-@-конструкции:

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

Почему нельзя обойтись одними только t-переменными? Зачем потребовались o-переменные? Рассмотрим функцию

F {
  o.Self @ [Foo e.Info] = o.Self @ [Bar e.Info];
}

Функция у объекта меняет тег слоя Foo на Bar. Если бы o-переменных не было, а использовались бы вместо них t-переменные, то был бы допустим такой синтаксис:

G {
  t.MaybeObject = t.MaybeObject @ [Zoo 'hello'];
}

Функция G предполагает, что t.MaybeObject является объектом и или добавляет, или обновляет слой с именем Zoo. Во-первых, нет гарантии, что t.MaybeObject — объект. Во-вторых, не ясна в этом случае семантика. Сколько слоёв можно добавить к объекту? Как можно заменить один слой на другой? Если слои можно добавлять, то можно ли их удалять?

В случае синтаксиса с o-переменными, как например, в функции F, таких вопросов не возникает. Можно либо оставить объект нетронутым (поместив в правую часть o-переменную без вырезки), либо заменить на новый конкретный слой, выбранный в левой части.

Но как же создать такой объект? Ведь синтаксис выше слои не создаёт, число слоёв и порядок сохраняется прежним. А вот здесь приходится вводить понятие конструктора. Конструктор — функция, создающая некоторый объект с нуля. Синтаксически оформляется так:

$NEW NewWidget {
  … = [Widget …];
  … = <Base::NewSmth …> @ [Gadget …];
}

Метка $NEW, как и метка $VIRTUAL, неявно подразумевает $ENTRY. В функциях, помеченных как $NEW в правой части обязательно должен располагаться или АТД-терм, или <>-@-конструкция. Таким образом гарантируется, что функции-конструкторы всегда возвращают объект соответствующей глубины иерархии.

<>-@-конструкция — это синтаксис вида

<Base::NewSmth …> @ [Gadget …]

где в угловых скобках может находиться только вызов конструктора. Конструктор может быть только функцией из другого модуля, вызывать конструктор из текущего модуля запрещено на уровне синтаксиса. При выполнении <>-@-конструкции новый слой добавляется к объекту.

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

Другие вопросы

Поведение виртуальных функций никак не меняется. В расширениях виртуальных функций на месте метки $DATA в формате может располагаться не только АТД-терм, но и o-@-конструкция, что довольно очевидно.

Выше сказано, что o-переменные не могут быть повторными. Можно разрешить повторные o-переменные со следующим ограничением: только одна из них в образце может иметь вырезку, остальные не могут. Соответственно, допускаются и переменные без вырезок в образце, но они могут быть только повторными (другое её вхождение обязано иметь вырезку).

О реализации

Реализация таких объектов станет сложнее, нежели просто добавления полиморфизма АТД-термам. Скорее всего, объекты будут представлены как списки слоёв:

[Class [X1 …] [X2 …] … [Xn …]]

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

При этом реализация обычных АДТ-термов не изменится. Различать теги (классы/данные) можно будет по конструкторам: если тег данных в конструкторе не используется, то базовым классом он быть не может — добавлять новые слои можно только в <>-@-конструкциях.

Детально описывать реализацию я пока не планирую. Это более технический вопрос, нежели идеологический, опишу, если (когда) буду всё это реализовывать.

Заключение

Расширить язык объектами с наследованием можно. При этом и объекты останутся типами-значениями, и паттерн шаблонный метод сможет работать, и расширение будет не сильно уходить от духа Модульного Рефала. Однако, расширение наследованием более громоздко, нежели расширение полиморфизмом.

В схеме с полиморфизмом нет явных классов — для разных тегов АТД можно реализовать разные виртуальные функции, причём совершенно несогласованно:

…
$DATA A, B, C;

$EXTENDS M.F {
  [A e.1] = 1;
  [B e.2] = 2;
}

$EXTENDS N.G {
  [B e.2] = 2;
  [C e.3] = 3;
}

$EXTENDS O.H {
  [C e.3] = 3;
  [A e.1] = 1;
}
…

В схеме с наследованием точно также нет явной иерархии, расширяться слоем может любой объект любого класса:

…
$NEW NewABC {
  1 e.1 = <M::NewX e.1> @ [A e.1];
  2 e.2 = <N::NewY e.2> @ [B e.2];
  3 e.3 = [C e.3];
}

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

На вопрос, заданный ранее

Как внедрить наследование реализации, а главное, стоит ли его внедрять — вопрос открытый.

половина ответа нашлась. Но осталась вторая половина: а нужно ли наследование в Модульном Рефале?

Mazdaywik commented 3 years ago

Уточнение предыдущего комментария

Можно различать классы и абстрактные типы данных. Первые участвуют в иерархии, вторые — нет. Классы объявляются ключевым словом $CLASS, анализируются только o-@-конструкцией, должны создаваться функциями-конструкторами и никак иначе. Абстрактные типы данных наоборот, не могут разбираться o-@-конструкцией (а только образцами вида [D …]), не могут создаваться в конструкторах, а значит, и иметь наследников.

Можно вообще ввести для классов универсальный базовый класс RUNTIME.OBJECT, запись … = [C …]; в конструкторе считать синтаксическим сахаром для … = <RUNTIME::NewOBJECT> @ [C …];.

А в свете последнего, RUNTIME.OBJECT будет просто абстрактным типом данных. Запись o.X @ [C …] будет тогда синтаксическим сахаром для [RUNTIME.OBJECT e.X-B [C …] e.X-E].

Если экземпляры классов представляются как [RUNTIME.OBJECT [C1 …] … [Cn …]], то семантику виртуальных функций можно определить так.

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

Так что данную семантику можно определить и иначе. Для объекта со слоями C1, …, Cn, где C1 — крайний предок, а Cn — крайний потомок, расширение виртуальной функции строится из предложений расширений в порядке от потомков к предкам.

Очень странное ООП получается. Но в духе Модульного Рефала. Самому интересно, что откроется мне дальше. Когда я начинал писать комментарий, я думал написать только о ключевом слове $CLASS и разнице между $CLASS и $DATA. Остальное возникло в процессе написания комментария. Пишешь комментарий, а ощущение, как будто читаешь чужую книгу. Интересно, а что дальше?