В информатике , композиция функций является акт или механизм комбинировать простые функции для построения более сложных. Подобно обычному составу функций в математике , результат каждой функции передается как аргумент следующей, а результат последней является результатом целого.
Программисты часто применяют функции к результатам других функций, и почти все языки программирования позволяют это. В некоторых случаях композиция функций интересна как самостоятельная функция, которая будет использоваться позже. Такую функцию всегда можно определить, но языки с функциями первого класса упрощают ее.
Возможность легко составлять функции поощряет факторизацию (разделение) функций для удобства обслуживания и повторного использования кода . В более общем смысле большие системы можно строить путем составления целых программ.
Грубо говоря, композиция функций применяется к функциям, которые работают с конечным объемом данных, причем каждый шаг последовательно обрабатывает их, прежде чем передать их следующему. Функции, которые работают с потенциально бесконечными данными ( потоком или другими кодовыми данными ), называются фильтрами , и вместо этого они соединяются в конвейер , который аналогичен композиции функций и может выполняться одновременно .
Составление вызовов функций
Например, предположим, что у нас есть две функции f и g , например , z = f ( y ) и y = g ( x ) . Их составление означает, что мы сначала вычисляем y = g ( x ) , а затем используем y для вычисления z = f ( y ) . Вот пример на языке C :
float x , y , z ; // ... y = g ( x ); z = f ( y );
Шаги можно объединить, если мы не дадим название промежуточному результату:
z = f ( g ( x ));
Несмотря на различия в длине, эти две реализации вычисляют один и тот же результат. Вторая реализация требует только одной строки кода и в просторечии называется «хорошо составленной» формой. Удобочитаемость и, следовательно, ремонтопригодность - одно из преимуществ хорошо составленных форм, поскольку они требуют меньшего количества строк кода, что сводит к минимуму «площадь поверхности» программы. [1] Демарко и Листер эмпирически подтверждают обратную зависимость между площадью поверхности и ремонтопригодностью. [2] С другой стороны, возможно чрезмерное использование сложных форм. Вложение слишком большого количества функций может иметь противоположный эффект, делая код менее удобным в обслуживании.
В стековом языке функциональная композиция еще более естественна: она выполняется путем конкатенации и обычно является основным методом разработки программ. Приведенный выше пример в Forth :
gf
Это возьмет все, что было в стеке раньше, применит g, затем f и оставит результат в стеке. См. Соответствующие математические обозначения в нотации постфиксной композиции .
Назовите состав функций
Теперь предположим, что комбинация вызова f () для результата g () часто бывает полезной и которую мы хотим назвать foo (), чтобы использовать ее как самостоятельную функцию.
В большинстве языков мы можем определить новую функцию, реализованную путем композиции. Пример на C :
float foo ( float x ) { вернуть f ( g ( x )); }
(длинная форма с промежуточными значениями тоже подойдет.) Пример в Форте :
: foo gf;
В таких языках, как C , единственный способ создать новую функцию - это определить ее в исходном коде программы, что означает, что функции не могут быть составлены во время выполнения . Однако возможна оценка произвольного состава предопределенных функций:
#include ЬурейиЙ INT FXN ( INT );int f ( int x ) { вернуть x + 1 ; } int g ( int x ) { возврат x * 2 ; } int h ( int x ) { вернуть x -3 ; }int eval ( FXN * fs [], int size , int x ) { для ( int i = 0 ; i < size ; i ++ ) x = ( * fs [ i ]) ( x ); вернуть x ; }int main () { // ((6 + 1) * 2) -3 = 11 FXN * arr [] = { f , g , h }; printf ( "% d \ n " , eval ( arr , 3 , 6 )); // ((6-3) * 2) +1 = 7 arr [ 2 ] = f ; arr [ 0 ] = h ; printf ( "% d \ n " , eval ( arr , 3 , 6 )); }
Первоклассный состав
В языках функционального программирования композиция функций может быть естественным образом выражена как функция или оператор высшего порядка . На других языках программирования вы можете написать свои собственные механизмы для выполнения композиции функций.
Haskell
В Haskell приведенный выше пример выглядит следующим образом:
foo = f. грамм
с помощью встроенного оператора композиции (.), который можно читать как f после g или g, составленного с помощью f .
Сам оператор композиции может быть определен в Haskell с помощью лямбда-выражения :
( . ) :: ( b -> c ) -> ( a -> b ) -> a -> c f . г = \ х -> е ( г х )
Первые строки описывают тип (.) - он принимает пару функций и возвращает функцию. Обратите внимание, что Haskell не требует указания точных типов ввода и вывода f и g, только отношения между ними (f должен принимать то, что возвращает g). Это делает (.) Полиморфным оператором.
Лисп
Варианты Lisp , особенно Scheme , взаимозаменяемость кода и данных вместе с обработкой функций очень хорошо подходят для рекурсивного определения вариативного композиционного оператора.
( define ( compose . fs ) ( if ( null? fs ) ( lambda ( x ) x ) ; если аргумент не задан, вычисляется функция идентичности ( lambda ( x ) (( car fs ) (( apply compose ( cdr fs) )) х ))))); примеры ( define ( add-a-bang str ) ( string-append str "!" ))( определить givebang ( составить строку-> символ добавить-a-bang symbol-> строка ))( набор givebang ) ; ===> установить! ; анонимная композиция (( compose sqrt negate square ) 5 ) ; ===> 0 + 5i
APL
Многие диалекты APL имеют встроенную функциональную композицию с использованием символа ∘
. Эта функция более высокого порядка расширяет функции композиции диадического применения боковой функции левого таким образом, что A f∘g B
есть A f g B
.
foo ← f ∘ g
Дополнительно вы можете определить состав функций:
o ← { ⍺⍺ ⍵⍵ ⍵ }
На диалекте, который не поддерживает встроенное определение с использованием фигурных скобок, доступно традиционное определение:
∇ r ← ( f o g ) x r ← f g x ∇
Раку
В Raku, как и в Haskell, есть встроенный оператор композиции функций, главное отличие в том, что он пишется как ∘
или o
.
мой & foo = & f ∘ & g ;
Также, как и в Haskell, вы можете сами определить оператор. Фактически, следующий код Raku используется для его определения в реализации Rakudo .
# Реализация имеет немного другую линию здесь , потому что читы прото суб инфикс : <∘> (& ?, и?) Является эквив (& [~]) является ассоциативный <влево> { * } вспомогательный инфикс multi : <∘> () { *. self } # позволяет `[∘] @ array` работать, когда` @ array` пусто multi sub infix : <∘> (& f) { & f } # разрешает `[∘] @ array` работать, когда` @ array` имеет одноэлементный мульти- суб- инфикс : <∘> (& f, & g -> Block) { ( & f ) . count > 1 ?? -> | аргументы { f | г | args } !! -> | args { f g | args } }# присвоить ему псевдоним написания "Техас" (все больше, и ASCII в Техасе) my & infix: : = & infix: <∘> ;
Python
В Python способ определения композиции для любой группы функций заключается в использовании функции reduce (используйте functools.reduce в Python 3):
# Выпускается с Python v2.6 от functools импорта уменьшитьdef compose ( * funcs ) -> int : "" "Составьте группу функций (f (g (h (...)))) в одну составную функцию." "" return reduce ( lambda f , g : lambda x : f ( g ( x )), функции )# Пример f = лямбда x : x + 1 g = лямбда x : x * 2 h = лямбда x : x - 3# Вызов функции x = 10: ((x-3) * 2) +1 = 15 print ( compose ( f , g , h ) ( 10 ))
JavaScript
В JavaScript мы можем определить его как функцию, которая принимает две функции f и g и производит функцию:
функция о ( е , г ) { вернуть функцию ( х ) { вернуть е ( г ( х )); } }// В качестве альтернативы, используя оператор rest и лямбда-выражения в ES2015 const compose = (... fs ) => ( x ) => fs . reduceRight (( acc , f ) => f ( acc ), x )
C #
В C # мы можем определить его как Func, который принимает две Func f и g и производит Func:
// Пример вызова: // var c = Compose (f, g); // // Func g = _ => ... ,>// Func f = _ => ... ,>Func < TIn , TOut > Составить < TIn , TMid , TOut > ( Func < TMid , TOut > f , Func < TIn , TMid > g ) => _ => f ( g ( _ ));
Рубин
Такие языки, как Ruby, позволяют вам самостоятельно создавать бинарные операторы:
class Proc def compose ( other_fn ) -> ( * as ) { other_fn . вызов ( вызов ( * а )) } конец alias_method : + , : Compose конецf = -> ( x ) { x * 2 } g = -> ( x ) { x ** 3 } ( f + g ) . звоните ( 12 ) # => 13824
Однако в Ruby 2.6 был введен собственный оператор композиции функций: [3]
f = proc { | х | x + 2 } g = proc { | х | х * 3 } ( f << g ) . звонок ( 3 ) # -> 11; идентично f (g (3)) ( f >> g ) . звонок ( 3 ) # -> 15; идентично g (f (3))
Исследовательский опрос
Понятия композиции, в том числе принципа композиционности и компонуемости , настолько повсеместно , что многочисленные нити исследований были отдельно развивались. Ниже приведены примеры исследований, в которых понятие композиции занимает центральное место.
- Стил (Steele, 1994) напрямую применил композицию функций к набору строительных блоков, известных как « монады » в языке программирования Haskell .
- Мейер (1988) обратился к проблеме повторного использования программного обеспечения с точки зрения возможности компоновки.
- Абади и Лэмпорт (1993) формально определили правило доказательства для функциональной композиции, которое гарантирует безопасность и жизнеспособность программы.
- Крахт (2001) определил усиленную форму композиционности, поместив ее в семиотическую систему и применив к проблеме структурной неоднозначности, часто встречающейся в компьютерной лингвистике .
- van Gelder & Port (1993) исследовали роль композиционности в аналоговых аспектах обработки естественного языка.
- Согласно обзору Гиббонса (2002) , формальная трактовка композиции лежит в основе проверки сборки компонентов в языках визуального программирования, таких как IBM Visual Age для языка Java .
Масштабная композиция
Целые программы или системы можно рассматривать как функции, которые можно легко составить, если их входы и выходы представляют собой четко определенные [4] конвейеры, позволяющие легко компоновать фильтры, которые были настолько успешными, что стали образцом проектирования операционных систем.
Обязательные процедуры с побочными эффектами нарушают ссылочную прозрачность и, следовательно, не могут быть полностью составлены. Однако, если вы рассматриваете «состояние мира» до и после выполнения кода в качестве его ввода и вывода, вы получите чистую функцию. Состав таких функций соответствует последовательному запуску процедур. Монады формализм использует эту идею включить побочные эффекты и I / O в функциональных языках.
Смотрите также
- Каррирование
- Функциональная декомпозиция
- Наследование реализации
- Семантика наследования
- Итеративная
- Конвейер (Unix)
- Принцип композиционности
- Виртуальное наследование
Заметки
- Перейти ↑ Cox (1986) , pp. 15–17
- ↑ DeMarco & Lister (1995) , стр. 133–135.
- ^ «Выпущен Ruby 2.6.0» . www.ruby-lang.org . Проверено 4 января 2019 .
- ↑ Раймонд (2003)
Рекомендации
- Абади, Мартин ; Лампорт, Лесли (1993), "Составление спецификации" (PDF) , ACM Сделки по Языки программирования и системы , 15 (1): 73-132, DOI : 10,1145 / 151646,151649.
- Кокс, Брэд (1986), объектно-ориентированное программирование, эволюционный подход , чтение, Массачусетс: Аддисон-Уэсли, ISBN 978-0-201-54834-1.
- Daume, Hal, III, Еще одно руководство по Haskell.
- Демарко, Том ; Листер, Тим (1995), "Разработка программного обеспечения: современное состояние против состояния практики", в Демарко, Том (редактор), Почему программное обеспечение стоит так дорого, и других загадках информационной эпохи , Нью-Йорк, Нью-Йорк: Дорсет-Хаус, ISBN 0-932633-34-X.
- ван Гельдер, Тимоти ; Порт, Роберт (1993), «За пределами символического: пролегомены к Кама-сутре композиционности», в Хонаваре, Васант ; Ур, Леонард (ред.), Обработка символов и коннекционистские модели в искусственном интеллекте и познании: шаги к интеграции , Academic Press.
- Гиббонс, Джереми (2002), Арбаб, Фархад; Талкотт, Кэролайн (ред.), Proc. 5-я Международная конференция по моделям координации и языкам (PDF) , Lecture Notes in Computer Science, 2315 , Springer-Verlag, pp. 339–350, doi : 10.1007 / 3-540-46000-4 \ _18 CS1 maint: обескураженный параметр ( ссылка ).
- Корн, Генри; Либери, Альберт (1974), Элементарный подход к функциям , Нью-Йорк, Нью-Йорк: Макгроу-Хилл, ISBN 0-07-035339-5.
- Kracht, Marcus (2001), "Строгая композиционность и грамматики буквального движения", Proc. 3-я Международная конференция по логическим аспектам компьютерной лингвистики , Lecture Notes in Computer Science, 2014 , Springer-Verlag, pp. 126–143, doi : 10.1007 / 3-540-45738-0_8.
- Мейер, Бертран (1988), Построение объектно-ориентированного программного обеспечения , Нью-Йорк, Нью-Йорк: Prentice Hall, стр. 13–15, ISBN 0-13-629049-3.
- Миллер, Джордж А. (1956), «Магическое число семь, плюс-минус два: некоторые ограничения нашей способности обрабатывать информацию» , Psychological Review , 63 (2): 81–97, doi : 10.1037 / h0043158 , hdl : 11858 / 00-001M-0000-002C-4646-B , PMID 13310704 , заархивировано из оригинала 19.06.2010 , получено 02.05.2010.
- Пирс, Бенджамин С .; Тернер, Дэвид Н. (2000), «Pict: язык программирования, основанный на пи-исчислении», Proof, Language, and Interaction: Essays in Honor of Robin Milner , Foundations Of Computing Series, Cambridge, MA: MIT Press, стр. 455–494, ISBN 0-262-16188-5.
- Рэймонд, Эрик С. (2003), «1.6.3 Правило композиции: проектируйте программы так, чтобы они были связаны с другими программами» , The Art of Unix Programming , Addison-Wesley, pp. 15–16, ISBN 978-0-13-142901-7.
- Стил, Гай Л., младший (1994), "Создание интерпретаторов путем составления монад" , Proc. Двадцать первого ACM симпозиум по принципам языков программирования ., Стр 472-492, DOI : 10,1145 / 174675,178068.