Функционально-ориентированное программирование

В компьютерном программировании функционально-ориентированное программирование (FOP) или функционально-ориентированная разработка программного обеспечения (FOSD) - это парадигма программирования для генерации программ в линейках программных продуктов (SPL) и для инкрементной разработки программ.

Связь между стеками слоев и композициями преобразований

вертикальная укладка слоев

История[править]

FOSD возник в конце 1980-х годов на основе многоуровневых конструкций и уровней абстракции в сетевых протоколах и расширяемых системах баз данных. Программа представляла собой стек слоев. Каждый слой добавлял функциональность к ранее составленным слоям, а различные композиции слоев создавали разные программы. Неудивительно, что для выражения таких конструкций требовался компактный язык. Элементарная алгебра подходила всем: каждый слой представлял собой функцию (преобразование программы), которая добавляла новый код к существующей программе для создания новой программы, а дизайн программы моделировался выражением, то есть композицией преобразований (слоев). На рисунке слева показана укладка слоев i, j и h (где h находится внизу, а i - сверху). Алгебраические обозначения i (j (h)), i • j • h и i + j + h использовались для выражения этих конструкций.

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

Второе поколение исследований FOSD было посвящено взаимодействиям функций, которые возникли в телекоммуникациях. Позже был введен термин feature-oriented programming; эта работа выявила взаимодействия между слоями. Взаимодействия требуют, чтобы функции были адаптированы при составлении с другими функциями.

Третье поколение исследований сосредоточено на том факте, что каждая программа имеет несколько представлений (например, исходный код, make-файлы, документация и т. Д.), И добавление функции в программу должно разработать каждое из ее представлений так, чтобы все они были согласованы. Кроме того, некоторые представления могут быть сгенерированы (или получены) из других. В разделах ниже описана математика трех последних поколений FOSD, а именно GenVoca, AHEAD, и FOMDD, а также приведены ссылки на линейки продуктов, которые были разработаны с использованием инструментов FOSD. Кроме того, четыре дополнительных результата, которые применимы ко всем поколениям FOSD: метамодели FOSD, программные кубы FOSD и взаимодействия функций FOSD. GenVoca

GenVoca (сочетание названий Genesis и Avoca)[1] - композиционная парадигма для определения программ продуктовых линеек. Базовые программы - это 0-арные функции или преобразования, называемые значениями:

f -- базовая программа с функцией f
h -- базовая программа с функцией h

а функции - это унарные функции / преобразования, которые разрабатывают (модифицируют, расширяют, уточняют) программу:

i + x -- добавляет функцию i в программу x
j + x -- добавляет функцию j в программу x

где + обозначает состав функции. Дизайн программы - это именованное выражение, например:

p 1 = j + f -- программа p 1 имеет функции j и f
p 2 = j + h -- программа p 2 имеет функции j и h
p 3 = i + j + h -- программа p 3 имеет функции i, j и h

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

GenVoca основана на поэтапной разработке программ: процесс, который подчеркивает простоту и понятность дизайна, которые являются ключом к пониманию программ и автоматизированному построению программ. Рассмотрим программу p 3 выше: она начинается с базовой программы h, затем добавляется функция j (читай: функциональность функции j добавляется в кодовую базу h), и, наконец, добавляется функция i (читай: функциональность функции i добавляется в кодовую базу j • h).

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

Примечание: Более поздняя формулировка GenVoca симметрична: существует только одна базовая программа 0 (пустая программа), и все функции являются унарными функциями. Это предполагает интерпретацию того, что GenVoca составляет программные структуры путем суперпозиции, идею о том, что сложные структуры составляются путем наложения более простых структур. Еще одна переформуляция GenVoca выглядит как моноид: модель GenVoca представляет собой набор функций с операцией композиции (•); композиция ассоциативна исуществует элемент идентичности (а именно 1, функция идентичности). Хотя все композиции возможны, не все они имеют смысл. Это причина для feature models.

Функции GenVoca изначально были реализованы с использованием методов C preprocessor (#ifdef feature ... #endif). Более продвинутый метод, называемый mixin layers, показал связь функций с объектно-ориентированными проектами на основе совместной работы.

Впереди[править]

Алгебраические иерархические уравнения для проектирования приложений (AHEAD)[4] обобщают GenVoca двумя способами. Сначала он выявил внутреннюю структуру значений GenVoca в виде кортежей. Каждая программа имеет несколько представлений, таких как исходный код, документация, байт-код и make-файлы. Значение GenVoca - это кортеж программных представлений. Например, в линейке парсеров базовый парсер f определяется его грамматикой g f, исходным кодом Java s f и документацией d f. Парсер f моделируется кортежем f=[g f, s f, d f]. Каждое представление программы может иметь подрепрезентации, и они тоже могут иметь подрепрезентации, рекурсивно. В общем случае значение GenVoca представляет собой кортеж вложенных кортежей, которые определяют иерархию представлений для конкретной программы.

Иерархические отношения между артефактами программы

Пример. Предположим, что терминальные представления являются файлами. В AHEAD грамматика g f соответствует одному BNF-файлу, source s f соответствует кортежу Java-файлов [c 1...c n], а documentation d f - кортежу HTML-файлов [h 1...h k]. Значение GenVoca (вложенные кортежи) может быть изображено в виде ориентированного графа: график для парсера f показан на рисунке справа. Стрелки обозначают проекции, т.е. отображения из кортежа в один из его компонентов. AHEAD реализует кортежи как каталоги файлов, поэтому f - это каталог, содержащий файл g f и подкаталоги s f и d f . Аналогично, каталог s f содержит файлы c 1...c n, а каталог df содержит файлы h 1...h k.

Примечание: Файлы могут быть иерархически разложены дальше. Каждый класс Java может быть разложен на кортеж членов и другие объявления классов (например, блоки инициализации и т. Д.). Важная идея здесь заключается в том, что математика AHEAD рекурсивна.

Во-вторых, AHEAD выражает функции как вложенные кортежи унарных функций, называемых дельтами. Дельты могут быть уточнениями программы (преобразования, сохраняющие семантику), расширениями (преобразования, расширяющие семантику) или взаимодействиями (преобразования, изменяющие семантику). Мы используем нейтральный термин “дельта” для представления всех этих возможностей, поскольку каждая из них встречается в FOSD.

Для иллюстрации предположим, что функция j расширяет грамматику с помощью Δ \Delta g j (добавляются новые правила и токены), расширяет исходный код с помощью Δ \Delta s j (добавляются новые классы и члены и изменяются существующие методы) и расширяет документацию с помощью Δ \Delta d j . Кортеж дельт для функции j моделируется j =[ Δ \Delta g j, Δ \Delta s j, Δ \Delta d j], который мы называем дельта-кортежем. Элементы дельта-кортежей сами могут быть дельта-кортежами. Пример: Δ \Delta s j представляет изменения, которые вносятся в каждый класс в s f функцией j, т.Е. Δ {\displaystyle \Delta } \Delta s j =[ Δ \Delta c 1... Δ \Delta c n] . Представления программы вычисляются рекурсивно вложенным векторным сложением. Представления для парсера p 2 (чье выражение GenVoca равно j+f) являются:

p2 = j + f -- выражение
GenVoca = [     
       Δ
\Delta g j,   
       Δ
\Delta s j,      
       Δ
\Delta d j] + [g f, s f, d f] -- подстановка
= [  
       Δ
\Delta g j+g f,   
       Δ
\Delta s j+s f,     
       Δ   
\Delta d j+d f] -- составление кортежей поэлементно

То есть грамматика p2 - это базовая грамматика, составленная с ее расширением ( Δ , источник p2 - это базовый источник, составленный с его расширением ( Δ \Delta s j + s f), и так далее. Поскольку элементы дельта-кортежей сами могут быть дельта-кортежами, композиция рекурсирует, например, Δ \Delta c 1... Δ \Delta c n+c n] . Подводя итог, значения GenVoca являются вложенными кортежами артефактов программы, а функции - вложенными дельта-кортежами, где + рекурсивно составляет их путем векторного сложения. В этом суть AHEAD.

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

Оригинальной реализацией AHEAD является набор инструментов AHEAD и язык Jak, который демонстрирует как принципы единообразия, так и масштабируемости. Инструменты следующего поколения включают CIDE [10] и FeatureHouse.

FOMDD[править]

Деривационные и уточняющие отношения между артефактами программы

Feature-Oriented Model-Driven Design (FOMDD)[5][6] объединяет идеи AHEAD с Model-Driven Design (MDD) (он же Model-Driven Architecture (MDA)). Функции AHEAD фиксируют пошаговое обновление артефактов программы при добавлении функции в программу. Но существуют и другие функциональные отношения между артефактами программы, которые выражают деривации. Например, связь между грамматикой g f и источником ее синтаксического анализатора s f определяется компилятором-компилятором, например javacc. Аналогично, связь между исходным кодом Java s f и его байт-кодом b f определяется компилятором javac. Коммутирующая диаграмма выражает эти отношения. Объекты - это представления программ, стрелки вниз - деривации, а горизонтальные стрелки - дельты. На рисунке справа показана коммутирующая диаграмма для программы p3 = i+j+h = [g3, s3, b3].

Фундаментальным свойством коммутирующей диаграммы является то, что все пути между двумя объектами эквивалентны. Например, один из способов получить байт-код b3 парсера p3 (нижний правый объект на рисунке справа) из грамматики g h парсера h (верхний левый объект) - это получить байт-код b h и уточнить до b 3, в то время как другой способ уточнить g h до g 3, а затем выведите b 3 , где + представляет дельта-композицию, а () - функцию или инструментальное приложение:

Существуют ( 4 2 ) }возможные пути для получения байт-кода b3 парсера p3 из грамматики g h парсера h. Каждый путь представляет собой метапрограмму, выполнение которой генерирует целевой объект (b3) из начального объекта (g f). Существует потенциальная оптимизация: обход каждой стрелки коммутирующей диаграммы имеет стоимость. Самый дешевый (т.е. Самый короткий) путь между двумя объектами на коммутирующей диаграмме - это геодезическая, которая представляет собой наиболее эффективную метапрограмму, которая производит целевой объект из данного объекта.

Примечание: “метрика затрат” не обязательно должна быть денежной; стоимость может быть измерена во времени производства, пиковых или общих требованиях к памяти, энергопотреблении или какой-либо неформальной метрике, такой как “простота объяснения”, или их комбинации (например, многоцелевая оптимизация). Идея геодезической является общей и должна быть понята и оценена из этого более общего контекста.

Примечание: В геодезической может быть m начальных объектов и n конечных объектов; когда m = 1 и n> 1, это направленная проблема дерева Штейнера, которая является NP-жесткой.

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