Что такое суперпозиция в программировании
Перейти к содержимому

Что такое суперпозиция в программировании

  • автор:

Суперпозиции

Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует замыкание данного множества функций.

Способы получения суперпозиций

Рассмотрим две булевы функции: функцию [math]f[/math] от [math]n[/math] аргументов [math]f(x_, x_, \ldots, x_)[/math] и функцию [math]g[/math] от [math]m[/math] аргументов [math]g(y_, y_, \ldots, y_)[/math] .

Тогда мы можем получить новую функцию из имеющихся двумя способами:

  1. Подстановкой одной функции в качестве некоторого аргумента для другой;
  2. Отождествлением аргументов функций.

Подстановка одной функции в другую

Определение:
Подстановкой (англ. substitution) функции [math]g[/math] в функцию [math]f[/math] называется замена [math]i[/math] -того аргумента функции [math]f[/math] значением функции [math]g[/math] : [math]h(x_, \ldots, x_) = f(x_, \ldots, x_, g(x_, \ldots, x_), x_, \ldots, x_)[/math]

Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.

При подстановке функции [math]g[/math] вместо [math]i[/math] -того аргумента функции [math]f[/math] , результирующая функция [math]h[/math] будет принимать аргументы, которые можно разделить на следующие блоки:

1. [math] x_, \ldots, x_[/math] — аргументы функции [math]f[/math] до подставленного значения функции [math]g[/math]
2. [math] x_, \ldots, x_ [/math] — используются как аргументы для вычисления значения функции [math]g(y_, \ldots, y_)[/math]
3. [math] x_, \ldots, x_ [/math] — аргументы функции [math]f[/math] после подставленного значения функции [math]g[/math]
  1. [math] f(a,b) = a \vee b [/math]
  2. [math] g(a) = \neg a [/math]

[math] h(a,b) = f(a,g(b)) = a \vee \neg b [/math] — подстановка функции [math]g[/math] вместо второго аргумента функции [math]f[/math] . В данном примере при помощи подстановки мы получили функцию [math]h(a,b)=a \leftarrow b[/math] .

Отождествление переменных

Определение:
Отождествлением переменных (англ. identification of variables) называется подстановка [math]i[/math] -того аргумента функции [math]f[/math] вместо [math]j[/math] -того аргумента: [math]h(x_, \ldots, x_, x_, \ldots, x_) = f(x_, \ldots, x_, \ldots, x_, x_, x_, \ldots, x_)[/math]

Таким образом, при отождествлении [math]c[/math] переменных мы получаем функцию [math]h[/math] с количеством аргументов [math]n-c+1[/math] .

[math] f(a,b) = a \vee b [/math] — исходная функция

[math] h(a) = a \vee a [/math] — функция с отождествленными первым и вторым аргументами

Очевидно, в данном примере мы получили функцию [math]P_[/math] — проектор единственного аргумента.

Ранги суперпозиций

Определение:
Ранг суперпозиции (англ. rank of function composition) — это минимальное число подстановок и отождествлений, за которое суперпозиция может быть получена из исходного множества функций. Суперпозиция [math]K[/math] ранга [math]n[/math] обозначается как [math]K^[/math]

См. также

  • Булевы функции
  • Представление функции формулой, полные системы функций

Источники информации

  • Осипова В.А., Основы дискретной математики: Учебное пособие, М.: ФОРУМ: ИНФРА-М, 2006, стр 62-63
  • Композиция функций в математике
  • Е.Л. Рабкин, Ю.Б. Фарфоровская, Дискретная математика, Глава 7: Суперпозиция функций. Замыкание набора функций. Замкнутые классы функций. Полные наборы. Базисы

Суперпозиция функций

Суперпозицией функций f1, …, fm называется функция f, полученная с помощью подстановок этих функций друг в друга и переименования переменных.

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

Областью определения суперпозиции является множество .

Функция называется внешней, а -внутренней функцией для суперпозиции .

Функции, представленные в виде композиции «более простых», называются сложными функциями.

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

Рекурсивные функции

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

Примитивно рекурсивная функция

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

К числу базовых примитивно рекурсивных функций относятся функции следующих трёх видов:

Нулевая функция— функция без аргументов, всегда возвращающая0.

Функция следованияодного переменного, сопоставляющая любому натуральному числунепосредственно следующее за ним натуральное число .

Функции , где , от n переменных, сопоставляющие любому упорядоченному набору натуральных чисел число из этого набора.

Операторы подстановки и примитивной рекурсии определяются следующим образом:

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

Оператор примитивной рекурсии. Пусть — функция от n переменных, а — функция от переменных. Тогда результатом применения оператора примитивной рекурсии к паре функций и называется функция от переменной вида ;

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

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

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

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

Функция сложения двух натуральных чисел () может быть рассмотрена в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения оператора примитивной рекурсии к функциям и , вторая из которых получается подстановкой основной функции в основную функцию :

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

Симметрическая разность(абсолютная величина разности) двух натуральных чисел () может быть рассмотрена в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения следующих подстановок и примитивных рекурсий:

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

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

Начнем с понятия программы. С математической точки зрения программа — это функция. Иногда это может показаться не очевидным. Если программа — функция, тогда следует решить что есть ее аргументами и что она возвращает. В случае с простыми утилитами вроде 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 за то, что он помог поправить статью.

  • композиция
  • функции
  • теория программирования
  • проектирование по

3 Композиция и суперпозиция функций в функциональном программировани кратко

Привет, Вы узнаете о том , что такое 3 Композиция и суперпозиция функций в функциональном программировани, Разберем основные из виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое 3 Композиция и суперпозиция функций в функциональном программировани , настоятельно рекомендую прочитать все из категории Функциональное программирование.

Композиция и суперпозиция функций

3 Композиция и суперпозиция функций в функциональном программировани

Как все нормальные программисты, мы — ленивые. Мы не хотим постоянно собирать, тестировать и деплоить один и тот же код, который переписываем снова, и снова, и снова. Мы всегда пытаемся найти пути, чтобы, решив какую-нибудь задачу однажды, использовать это решение в других случаях. Повторное использование кода — хорошая затея, но в реальности этого тяжело добиться. Попробуйте сделать код слишком специализированным и у вас не получится использовать его снова. Попробуйте сделать его слишком общим и вам будет сложно использовать его даже в вашей первоочередной задаче. То, что нам нужно — баланс между этими двумя положениями, споcоб создавать элементы поменьше с возможностью их многократного использования, которые мы будем применять как строительные блоки для конструирования более сложного функционала. В функциональном программировании функции — наши строительные блоки. Мы пишем их для решения определенных задач, а потом складываем вместе, как блоки в Lego™. Результат такого сложения называется композицией функций. Так как же это работает? Давайте начнем с двух JavaScript-функций:

var add10 = function(value) < return value + 10; >; var mult5 = function(value) < return value * 5; >;

Код получился слишком пространный, так что давайте перепишем его, используя стрелочные функции:

var add10 = value => value + 10; var mult5 = value => value * 5;

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

var mult5AfterAdd10 = value => 5 * (value + 10)

Даже несмотря на такой простой пример, нам бы не хотелось писать целую функцию с нуля. Во-первых, мы могли бы допустить ошибку и, например, забыть поставить круглые скобки. Во-вторых, у нас есть одна функция, прибавляющая к значению 10, и другая, умножающая его на 5. Получается, мы пишем код, который уже написали. Так что вместо этого давайте используем add10 и mult5 и соберем новую функцию:

var mult5AfterAdd10 = value => mult5(add10(value));

Мы просто использовали существующие функции, чтобы получить mult5AfterAdd10, но есть и способ получше. В математике f ∘ g — композиция функций (прим. Об этом говорит сайт https://intellect.icu . пер., или суперпозиция функций) и читается она как «применение функции f к результату функции g» или более просто «выполнение f после g». Получается, что (f ∘ g)(x) — эквивалент вызова функции f после функции g со значением x или еще проще: f(g(x)). В нашем примере у нас mult5 ∘ add10 или «mult5 после add10», отсюда и название нашей функции mult5AfterAdd10. И это объясняет то, что мы сделали. Мы вызвали mult5 после вызова add10 с value или просто: mult5(add10(value)). Поскольку JavaScript нативно не реализует возможность композиции функций, давайте взглянем на Elm:

add10 value = value + 10mult5 value = value * 5mult5AfterAdd10 value = (mult5 

В Elm функции компонуются с помощью инфиксального оператора

f x = (g 

В этом случае x передается в t, чей результат передается в r, чей результат, в свою очередь, — в s и так далее. Если вы захотите сделать что-то подобное в JavaScript, это будет выглядеть примерно так: g(h(s(r(t(x))))) — просто какой-то ад из круглых скобок.

Бесточечная нотация функций

Бесточечная нотация — стиль описания функций без предварительного указания входных параметров. По началу такой стиль будет казаться необычным, но по мере продолжения, когда вы достаточно разберетесь, вы оцените лаконичность такого подхода. Вы заметите, что в mult5AfterAdd10 значение value определяется дважды. Один раз в списке параметров и один раз в момент использования.

-- Эта функция ожидает 1 входной параметрmult5AfterAdd10 value = (mult5 

Но этот параметр несущественен, так как add10, самая правая функция в композиции, ожидает тот же параметр. Следующая бесточечная версия — эквивалент предыдущей:

-- Эта функция тоже ожидает 1 входной параметрmult5AfterAdd10 = (mult5 

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

Особенности безточесных функций

До сих пор мы разбирались, как работает композиция функций, и как следует определять функции при бесточечной нотации для лаконичности, чистоты и гибкости кода. Теперь давайте попробуем использовать эти идеи при слегка ином сценарии и посмотрим, насколько они ему соответствуют. Представьте, что мы заменяем add10 на add:

add x y = x + ymult5 value = value * 5

Как нам создать mult5AfterAdd10, используя эти две функции? Ладно, если вы действительно потратите время, раздумывая над этим вопросом, то вернетесь примерно с таким решением:

-- Это неверно . mult5AfterAdd10 = (mult5 

Но такой код не будет работать. Потому что add принимает два параметра. Если это не так очевидно в Elm, попробуйте написать то же самое в JavaScript:

var mult5AfterAdd10 = mult5(add(10)); // не работает

Этот код неверен, но почему? Потому что в нем функция add принимает лишь один из своих двух параметров, после чего передает ошибочные результаты в mult5. Это будет приводить к неверным решениям. По факту, в Elm компилятор не позволит вам даже написать такой нецелесообразный код (что является одним из больших плюсов языка Elm). Давайте попробуем еще раз:

var mult5AfterAdd10 = y => mult5(add(10, y)); // не бесточечный стиль

Да, это не бесточечный стиль, но я тем не менее могу жить с таким решением. В то же время, теперь я уже не просто комбинирую функции. Я пишу новую функцию. Также, если задача станет гораздо сложнее, к примеру, если я захочу скомпоновать mult5AfterAdd10 с какой-то другой функцией, я столкнусь с серьезной проблемой. Пока мы не можем «обвенчать» эти две функции, будет казаться, что идея композиции функций не обладает такой уж большой практической ценностью. И это очень плохо, потому что на самом деле это не так. Что ж, что было бы действительно хорошо, так это если бы у нас была идея, как предварительно передать нашей функции add один из ее входных параметров и уже позже — второй параметр, когда будет вызвана mult5AfterAdd10. Выходом из этого затруднительного положения является концепция каррирования.

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *