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

1.10.4. Композиция и суперпозиция функций. Способы задания функций

h: AC называется композицией функций  и g (обозначается og), если имеет место равенство , где хА.

Часто говорят, что функция h получена подстановкой

Для многоместных функций , возможны различные варианты подстановки  в g, дающие функции различных типов. Например, при m=3 и n=4 функция имеет шесть аргументов и тип .

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

Существует несколько способов задания функции.

1. Самый прямой способ – задать функцию с помощью списка значений, которые она принимает на элементах области А.

Пример1. Например, одна из функций : АВ с областью , областью значений и образом задаётся предписанием:

Другая функция g: АВ с образом задаётся предписанием

Заметим, что к образам этих функций можно применить булевы операции

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

2. Графиком;

3. Таблицей;

4. Формулой, описывающей функцию как суперпозицию других (исходных) функций;

5. Рекурсивной вычислительной процедурой.

Пример2. Функция f(x)=1∙2∙3∙ (x-1)x=x! описывается рекурсивной вычислительной процедурой, задаваемой следующими правилами:

1) (0)=1; 2) (х+1)=f(x)·(x+1).

Характеристические функции.

Всякому отношению R из А в В (RAB) можно сопоставить функцию R:AB0…1, полагая 1.10.5.

1.10.5. Представление функций в эвм

Пусть : АВ, множество А конечно и не очень велико, |A|=n. Наиболее общим представлением такой функции является массив array[A] of B, где А – тип данных, значения которых представляют элементы множества А, а В – тип данных, значения которых представляют элементы множества В. Если среда программирования допускает массивы только с натуральными индексами, то элементы множества А нумеруются (то есть и функция представляется с помощью массива array[1,2,…,n] of B

Функция нескольких аргументов представляется многомерным массивом.

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

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

Многомерные функции представляются с помощью нескольких формальных параметров в определении функции.

Пример 1. Таблица выигрышей лотереи устанавливает соответствие G между парами чисел (серия и номер выигравшего билета) и множеством выигрышей М: Является ли данное соответствие функцией, и если да, то какой?

Соответствие , задаваемое таблицей выигрышей является функциональным, так как для каждой указанной пары из (серия, № билета) определён конкретный (единственный) выигрыш из М.

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

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

Пример 2. является ли функция (х)=2х, имеющая тип NN отображением, и если – да, то каким? Имеет ли функция  обратную функцию  -1 , и если – да, то является ли  -1 отображением?

Функция (х)=2х, : NN всюду определена на N, однако не сюръективна, так как область значения функции  равна (область значений содержит только чётные числа из N). Поэтому  является отображением N в N или преобразованием множества N.

Между областью определения и областью значений имеет место взаимно однозначное соответствие: любому элементу nN соответствует один и только один элемент 2n из и наоборот. Поэтому функция (х)=2х, : NN, имеет обратную функцию -1 . Однако обратная функция не всюду определена: её областью определения является множество чётных чисел . Поэтому обратная функция  -1 , в отличие от исходной функции , не является отображением.

Пример 3. Задать несколько возможных типов для функции (х) =.2 n Для каждого типа определить:

а). свойства функции ;

б). является ли  отображением и, если – да, то каким?

1. Пусть тип функции : NN. Тогда (х) =2 n всюду определена, так как , но не сюръективна, так как ( – множество натуральных чисел, являющихся степенями двойки). Следовательно, функция  является отображением N в N.

2. : N . Тогда функция  всюду определена и сюръективна, следовательно, является отображением N на .

3. : NR. Функция всюду определена, но не сюръективна,

т. е.  есть отображение N в R.

4. : R₊N . Функция  частично определена и сюръективна, поскольку область значений (х) =2 n при заданном типе функции  представляет множество натуральных чисел, т. е. , значит, не для всех хR₊ функция  определена,

т. е. . Следовательно, : R₊N не является отображением.

5. : RR. Функция  всюду определена, но не сюръективна ( не имеет отрицательных значений). Следовательно,  – отображение R в R.

6. : R R₊. Функция всюду определена и сюръективна, т. е. является отображением R на R₊.

Кроме названных свойств во всех случаях  есть функциональное соответствие, а для случаев 2) и 6) – взаимно однозначное (биекция).

Пример 4. Чему равна композиция функций (х)=2х и g(x)=1+x?

Пусть функции f(х) и g(x) имеют тип RR. Тогда их композиции возможны в произвольном порядке. Композиция og =h₁ представляет собой подстановку  в g, т. е. h₁ =og =g(f(x))=1+f(x)=1+2x.

Композиция gо = h₂есть функция, полученная подстановкой g в , т. е. h₂= gо=f(g(x))=2g(x)=2(1+x)=2+2x.

Пример 5. Чему равна композиция функций и ? Каковы области определения композиций и функций?

Пусть функции и имеют тип RR, т. е. отображают одно и тоже множество на себя. Тогда композиция возможна в произвольном порядке и дает функции: h₁ =og =g(f(x))= и

Области определения исходных функций и их композиций: , , .

Пример 6. Функции  и g имеет тип , . Какой тип имеют функции h₁ и h₂ , являющиеся композициями  и g:

Функция h₁ содержит шесть аргументов и её тип .

Функция h₂ содержит восемь аргументов и её тип или .

Пример 7. Пусть функция . Определить функции образованные переименованием:

1. Переименование в приводит функцию к функции, , которая равна функции двух аргументов:

2. Переименование и в приводит к одноместной функции .

Пример 8. Дано множество A=<a, b, c, d> и два преобразования этого множества (т. е. функции типа АА, являющиеся отображением А в А):

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

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

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

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

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

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

Рассмотрим же прообразы этих операций в языках программирования. Где-то они более явные, где-то менее. В Языке Си операция ветвления, очевидно, сокрыта в управляющей структуре : либо тернарном операторе: В первом случае был рассмотрен statement, а не expression, но это ведь не мешает представить как, например, все множество переменных в области видимости. В LISP прообраз данной композиции выглядел бы так: А в Haskell это выглядит как либо
Если говорить об операции суперпозиции, то она еще менее заметна во многих языках программирования, но тем не менее, вездесуща. Операция суперпозиции в языке Си позволяет сделать следующую подстановку На LISP это выглядело бы как На Haskell же как
Сразу следует отметить, что арность всех предложенных функций должна быть единой, иначе примение к ним механизма композиций может быть значительно затруднено, т.е. X в самом деле это что-то вроде .
Очевидно, что композиции глубоко «похоронены» в синтаксисе языков программирования, неявно присутствуя в них. Впрочем, ничего нового, как может верно заметить искушенный в этом деле читатель. Еще Эдсгар Дейкстра это заметил в своей книге «Дисциплина программирования».

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

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

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

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

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

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

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

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

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

Содержание

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

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

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

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

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

Определение:

Подстановкой (англ. substitution) функции [math]g[/math] в функцию [math]f[/math] называется замена [math]i[/math] -того аргумента функции [math]f[/math] значением функции [math]g[/math] : [math]h(x_<1>, \ldots, x_) = f(x_<1>, \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_<1>, \ldots, x_[/math]	— аргументы функции [math]f[/math] до подставленного значения функции [math]g[/math]
2. [math] x_, \ldots, x_ [/math]	— используются как аргументы для вычисления значения функции [math]g(y_<1>, \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_<1>, \ldots, x_, x_, \ldots, x_) = f(x_<1>, \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_<1>[/math] — проектор единственного аргумента.

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

Язык Python поддерживает различные стили программирования, начиная с простейших вариантов до наиболее популярного объектно-ориентированного стиля программирования.

Работа в интерактивном режиме

На первых советских компьютерах была возможность выполнять программу в командном режиме и видеть результаты выполнения каждой команды. Более того, можно было отдельную команду выполнять по тактам. Интерпретатор Python позволяет проводить подобные эксперименты, работая в интерактивной среде IDLE, где можно выполнять фрагменты кода оператор за оператором, просматривая результаты работы каждого оператора.

Вот пример подобного стиля работы:

Программа Python как неделимый модуль

Язык Python позволяет написать простую программу от начала и до конца как последовательность операторов, не привлекая функций и других средств модульности. Программа выполняется оператор за оператором, в соответствии с ее текстом. Текст управляет выполнением. Чтобы написать такую программу, достаточно создать файл, представляющий модуль языка Python . Файл сохраняется с уточнением .py. Двойной щелчок на этом файле позволяет запустить модуль интерпретатором Python и выполнить программу. Для простых программ весьма удобная технология работы.

Запишем наш предыдущий пример как программу Python :

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

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

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

Все стили программирования в первую очередь направлены на борьбу со сложностью программ и позволяют декомпозировать сложную программу, представляя ее в виде совокупности более простых элементов — функций в функциональном программировании, модулей — в модульном программировании, классов — в объектно-ориентированном программировании. Исторически первым появился стиль функционального программирования. Уже в первом языке программирования Fortran58 программа ( routine ) могла содержать подпрограммы ( subroutine ). В следующем языке Algol60 программа могла включать процедуры и функции. Стиль функционального программирования в этих популярных языках того времени стал общепринятым.

В чисто функциональных языках программирования, следуя математике, каждая программа P(X, Y) рассматривается как функция F: X => Y , задающая отображение данных из области определения X , содержащей входные данные, в область значений функции Y , — содержащей результаты вычислений. Декомпозиция программы F означает, что функция F представляет композицию более простых функций , вызывая эти функции в процессе вычисления результата функции. Каждая функция f может быть, в свою очередь, декомпозирована и представлять композицию функций. Суперпозиция — один из основных инструментов функционального программирования — предполагает, что функции могут выступать в качестве аргументов других функций.

Язык Python поддерживает стиль функционального программирования.

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

В этом примере определены три функции. Функции f и g определены над числами и возвращают число в качестве результата. Функция F — это функция высших порядков, она представляет суперпозицию функций f и g: F(x) = f(g(x)) . У функции три аргумента, первый это число, второй и третий аргументы — это функции.

Функции F передать функции f и g также просто, как и число 5. Вот результат выполнения:

Рассмотрим теперь классическую содержательную задачу, требующую введения функции высшего порядка. Это задача вычисления определенного интеграла. Функция Integral, вычисляющая интеграл, имеет три параметра, — пределы интегрирования a, b и подынтегральную функцию f . Поскольку в языке Python функции являются объектами, такими же, как и, например, числа, то передавать функции Integral конкретную подынтегральную функцию в качестве фактического параметра также просто, как передать число.

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

Для вычисления площади фигуры применяется метод трапеций. Интервал интегрирования разбивается на n частей. Площадь каждой части вычисляется как площадь трапеции. В цикле выполняется удвоение n. Вычисления заканчиваются, когда площадь фигуры при n -разбиении и 2n -разбиении отличается менее чем на малую величину eps , которая задается как еще один параметр функции Integral .

Приведу реализацию этой функции:

Функция Integral является функцией высших порядков, поскольку один из ее параметров является функцией. Давайте вычислим интеграл для нескольких подынтегральных функций. Две из этих функций — f и g были определены выше, третья функция является встроенной в класс math функцией sin(x):

Точные значения площади для всех трех случаев легко вычисляются. Результаты вычислений функции Integral с заданной точностью eps совпадают с точными значениями. Вот результаты вычислений: