Pull to refresh

Языки программирования. Композиционный взгляд

Reading time 5 min
Views 9.2K
Здравствуй, Хабр! Сегодня хотел бы поднять вопрос об использовании композиций и их роли в программировании. Те, кто сталкивался с функциональными языками, скорее всего слышали о них, а те, кто не сталкивался, возможно, узнают что-нибудь новое. Надеюсь на интересную дискуссию в конце статьи об их применении. Эшер для привлечения внимания.



Начнем с понятия программы. С математической точки зрения программа — это функция. Иногда это может показаться не очевидным. Если программа — функция, тогда следует решить что есть ее аргументами и что она возвращает. В случае с простыми утилитами вроде bc всё понятно: аргументом выражение из stdin, а результатом — результат в stdout. В более сложных случаях тоже можно прийти к тому, что программа — это функция. Рассмотрим, пример, СУБД, в этом случае программа тоже функция, аргументом она принимает память, выделенную ей в user-space, ее же и возвращает, при этом непрерывно выполняясь. Может, довольно неоптимальный пример, но он доступен для понимания.

Если программа — функция, то следует рассмотреть, какие средства получения этой функции могут быть. Тут уже всё зависит от языков программирования, именно они являются такими средствами. И независимо от того функциональный это язык, процедурный, императивный, декларативный и т.д., всем им свойственно использование композиций, явное или неявное. Пришло время определить понятие композиции. Пусть даны две функции и , из них можно построить функцию применив к ним функцию : . Такая функция F, которая принимает как аргумент другие функции и будет называться композицией. А способов построения может быть множество, каждый способ — композиция. Рассмотрим пару примеров композиций: композиция ветвления и композиция суперпозиции.

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

Композиция суперпозиции. Пусть задана функция , где -арная функция и существует такая функция , которая определяется как . В этом случае будет считаться полученной с помощью операции суперпозиции : .

Рассмотрим же прообразы этих операций в языках программирования. Где-то они более явные, где-то менее. В Языке Си операция ветвления, очевидно, сокрыта в управляющей структуре :
if(p(X)) f1(X); else f2(X);
либо тернарном операторе:
p(X) ? f1(X) : f2(X);
В первом случае был рассмотрен statement, а не expression, но это ведь не мешает представить как, например, все множество переменных в области видимости. В LISP прообраз данной композиции выглядел бы так:
(if (p X) (f1 X) (f2 X))
А в Haskell это выглядит как
if p X then f1 X else f2 X
либо
g x
	| p  x == True = f1  x
	| p  x == False = f2  x
Если говорить об операции суперпозиции, то она еще менее заметна во многих языках программирования, но тем не менее, вездесуща. Операция суперпозиции в языке Си позволяет сделать следующую подстановку
f(f1(X), f2(X), f3(X));
На LISP это выглядело бы как
(f (f1 X) (f2 X) (f3 X))
На Haskell же как
f (f1 x) (f2 x) (f3 x)

Сразу следует отметить, что арность всех предложенных функций должна быть единой, иначе примение к ним механизма композиций может быть значительно затруднено, т.е. X в самом деле это что-то вроде .
Очевидно, что композиции глубоко «похоронены» в синтаксисе языков программирования, неявно присутствуя в них. Впрочем, ничего нового, как может верно заметить искушенный в этом деле читатель. Еще Эдсгар Дейкстра это заметил в своей книге «Дисциплина программирования».

Использование композиций


В связи с вышесказанным, появляется множество вопросов. В частности то, а почему композиции не используются явным образом? Ведь использование композиций явным образом могло бы принести много преимуществ. Особенно то, что станет возможным рассмотрение самого процесса программирования, а следовательно — оптимизация разработки сложных проектов. Ведь как сейчас программирует программист? Он делает это как художник, пишущий картину. Иными словами, конструкторские решения принимаются на основании его опыта, предчувствия, советов коллег, каких-то личных эстетических убеждений. Но этот ход размышления нельзя выложить просто так в файл вместе с программой. Т.е. программа есть, а хода мыслей, приведшего к ней, нет. Это первый вопрос. Почему у языков такой синтаксис как есть, почему создатели языка заложили именно такой набор управляющих структур? Почему их набор догматизирован? Что делать если необходимо добавить другие управляющие структуры.

Эти вопросы помогли бы решить средства применения и порождения композиций. Так как решение любой сколь угодно сложной задачи человеком сводится к анализу/декомпозиции, а потом синтезу, этот процесс может быть органично поддержан механизмом композиций. Ведь композиции будут именно тем самым связующим элементом, который будет склеивать части, на которые разбита задача. Ну а задачу разбивать так или иначе придется человеку, именно это его прерогатива, а не синтаксическое оформление задачи. К сожалению пока ни одного языка, который был бы заточен под понятие композиции, не замечено.

Для лучшего понимания рассмотрим пример с нахождением наибольшего общего делителя (НОД) с применением композиций. Вычислитель может находить остаток от деления (), осуществлять целочисленное деление (), вычислять предикат неравенства (), генерировать ноль (). Все функции определены на множестве натуральных чисел без нуля. Таким образом имеем следующие функции в предложенной алгебре = { , , , , }. Читатель может заметить еще одну функцию — , так называемую селекторную функцию, которая из аргументов возвращает без изменений -й, она необходима, так как мы работаем с -арными функциями. Кроме этого доступна композиция циклирования, назовем ее . Приведем ее определение. Пусть даны -арных функций , а также -арный предикат . Итерационно каждая функция выполняет вычисление одного из аргументов для следующей итерации, так вычисляет , вычисляет и т.д. Итерационный процесс продолжается до тех пор, пока значение предиката «истина». Аргументы операции циклирования передаются в следующем порядке . Значение , полученное на последней итерации будет значением функции, полученной в результате композиции. Кроме того доступна, описанная ранее, композиция суперпозиции. Тогда алгоритм вычисления НОД можно записать как . Схематически это будет выглядеть следующим образом:


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

Сам композиционный подход к решению начали исследовать А.И. Мальцев (мальцевские алгебры), академик Глушков (алгоритмические алгебры). Но все они работают на уровне применения композиций, догматизируя набор композиций, с которым ведется работа. Важным улучшением композиционного подхода была бы возможность получать новые композиции из существующих, применив к ним некоторые мета-композиции. Тема интересная, не знаю чтобы кто-то ее затрагивал, но об этом в следующий раз. Надеюсь я вас не утомил.

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

P.S. Внезапно увидел недавний пост, затрагивающий тоже тему композиций. Надеюсь они дополнят друг друга.
P.P.S. Большое спасибо sekrasoft за то, что он помог поправить статью.
Tags:
Hubs:
+2
Comments 19
Comments Comments 19

Articles