Функциональная композиция (информатика)

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

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

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

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

Составление вызовов функций [ править ]

Например, предположим, что у нас есть две функции $f$ и $g$ , как в $z = f (y)$ и $y = g (x)$ . Их составление означает, что мы сначала вычисляем $y = g (x)$ , а затем используем $y$ для вычисления $z = f (y)$ . Вот пример на языке C :

плавать   x  ,   y  ,   z  ; 
  // ... 
 y   =   g  (  x  ); 
  z   знак равно   ж  (  у  );

Шаги можно объединить, если не давать имя промежуточному результату:

z   знак равно   ж  (  г  (  Икс  ));

Несмотря на различия в длине, эти две реализации вычисляют один и тот же результат. Вторая реализация требует только одной строки кода и в просторечии называется «сложно составленной» формой. Читабельность и, следовательно, удобство сопровождения является одним из преимуществ сложных форм, поскольку они требуют меньше строк кода, что минимизирует «поверхность» программы. ^[1] ДеМарко и Листер эмпирически подтверждают обратную зависимость между площадью поверхности и ремонтопригодностью. ^[2]С другой стороны, возможно злоупотребление сложными формами. Вложенность слишком большого количества функций может иметь противоположный эффект, делая код менее удобным в сопровождении.

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

подруга

Который возьмет все, что было в стеке раньше, примените g, затем f и оставьте результат в стеке. см. в постфиксной композиции Соответствующие математические обозначения .

Именование состава функций [ править ]

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

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

float   foo  (  float   x  )   { 
     return   f  (  g  (  x  )); 
  }

(длинная форма с промежуточными элементами также подойдет.) Пример на Форте :

  :фу подруга ;

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

#include   <stdio.h> 

 typedef   int   FXN  (  int  ); 

  int   f  (  int   x  )   {   return   x  +  1  ;    } 
 Int   g  (  int   x  )   {   return   x  *  2  ;    } 
 Int   h  (  int   x  )   {   return   x  -3  ;    } 

 int   eval  (  FXN   *  fs  [],   int   size  ,   int   x  ) 
 { 
    for   (  int   i  =  0  ;   i  <  size  ;   i  ++  )   x   =   (  *  fs  [  i  ])(  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  ;     обр  [  0  ]   знак равно   час  ; 
     printf  (  "%d  \n  "  ,   eval  (  arr  ,   3  ,   6  )); 
  }

Первоклассный состав [ править ]

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

Хаскелл [ править ]

В Haskell пример $foo = f \circ g$ приведенный выше выглядит следующим образом:

фу = е.  г

используя встроенный оператор композиции (.), который можно прочитать как f после g или g, составленный с помощью f .

Сам оператор композиции $\circ$ можно определить в Haskell с помощью лямбда-выражения :

(  .  )   ::   (  b   ->   c  )   ->   (  a   ->   b  )   ->   a   ->   c 
 f   .    г   знак равно   \  Икс   ->   ж   (  г   Икс  )

Первая строка описывает тип (.) — он принимает пару функций $f, g$ и возвращает функцию (лямбда-выражение во второй строке). Обратите внимание, что Haskell не требует указания точных типов ввода и вывода f и g; a, b, c и x — заполнители; имеет значение только отношение между $f и g$ (f должно принять то, что возвращает g). Это делает (.) полиморфным оператором.

Лисп [ править ]

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

(  define   (  compose   .   fs  ) 
   (  if   (  null?   fs  )   (  лямбда   (  x  )   x  )   ; если аргумент не указан, вычисляется тождественная функция 
       (  лямбда   (  x  )   ((  car   fs  )   ((  apply   compose   (  cdr   fs  ))   Икс  ))))) 

 ;   примеры 
 (  define   (  add-a-bang   str  ) 
   (  string-append   str   "!"  )) 

 (  define   Givebang 
   (  составить   строку->символ   add-a-bang   символ->строка  )) 

 (  Givebang   'set  )   ;   ===> установил! 

  ;   анонимная композиция 
 ((  compose   sqrt   negate   Square  )   5  )   ;   ===> 0+5i

АПЛ [ править ]

Многие диалекты APL имеют встроенную композицию функций с использованием символа ∘. Эта функция высшего порядка расширяет композицию функций до диадического применения левой функции, так что A f∘g B является A f g B.

foo ← f ∘ g

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

o ← { ⍺⍺  ⍵⍵  ⍵ }

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

∇   р  ←  (  ж   о   г  )  Икс 
   р  ←  ж   г   Икс 
 ∇

Раку [ править ]

Raku, как и Haskell, имеет встроенный оператор композиции функций, основное отличие состоит в том, что он пишется как ∘ или o.

мой   &  foo   =   &  f   ∘   &  g  ;

Также, как и в Haskell, вы можете определить оператор самостоятельно. Фактически, ниже приведен код Raku, используемый для его определения в реализации Rakudo .

# реализация здесь имеет немного другую строку, потому что она обманывает 
 прото   -   инфикс  :<∘> (&?, &?) is equiv(&[~]) is assoc<left> {  *  } 

 multi   sub-   инфикс  :<∘> ( ) {   *.   self   }   # позволяет `[∘] @array` работать, когда `@array` пуст, 
 multi   sub   infix  :<∘> (&f) {   &  f   }     # позволяет `[∘] @array` работать, когда `@array` имеет один элементный 
 мультиподинфикс   > (&f, &   :< ∘  g --> Block) { 
     (  &  f  )  .   кол   >   1 
     ??    ->   |   аргументы   {   ж   |   г   |   аргументы   } 
     !!    ->   |   аргументы   {   ж   г   |   args   } 
 } 

 # присвоить ему псевдоним написания "Техас" (все больше, и ASCII в Техасе) 
 my   &  infix:  <o>   :  =   &  infix:  <∘>  ;

Nim [ edit ]

Nim поддерживает единый синтаксис вызова функций , что позволяет создавать произвольную композицию функций через синтаксис метода. . оператор. ^[3]

func   foo  (  a  :   int  ):   string   =   $  a 
 func   bar  (  a  :   string  ,   count  :   int  ):   seq  [  string  ]   = 
   for   i   in   0   ..  <   count  : 
     result  .   add  (  a  ) 
 func   baz  (  a  :   seq  [  строка  ]  )   = 
   for   i   in   a  : 
     echo   i 

 # эквивалент! 
  эхо   фу  (  5  ).   бар  (  6  ).   baz  () 
 echo   baz  (  bar  (  6  ,   foo  (  5  )))

Питон [ править ]

В Python способ определения композиции для любой группы функций — использование функции сокращения (используйте functools.reduce в Python 3):

# Доступно начиная с Python v2.6 
 из   functools   import   сокращение 
 от   ввода   import   Callable 

 def   compose  (  *  funcs  )   ->   Callable  [[  int  ],   int  ]: 
     """ Составьте группу функций (f(g(h(...) )))) в одну составную функцию.""" 
     return   уменьшить  (  лямбда   f  ,   g  :   лямбда   x  :   f  (  g  (  x  )),   funcs  ) 

 # Пример 
 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 и создает функцию:

function   o  (  f  ,   g  )   { 
     return   function  (  x  )   { 
         return   f  (  g  (  x  )); 
      } 
 } 

 // В качестве альтернативы можно использовать оператор rest и лямбда-выражения в ES2015 
 const   compose   =   (...  fs  )   =>   (  x  )   =>   fs  .   уменьшитьRight  ((  Acc  ,   f  )   =>   f  (  Acc  ),   x  )

С# [ править ]

В C# мы можем определить его как метод расширения, который принимает Funcs f и g и создает новый Func:

// Пример вызова: 
 // var c = f.ComposeWith(g); 
  // 
 // Func<int, bool> g = _ => ... 
 // Func<bool, string> f = _ => ... 

 public   static   Func  <  T1  ,   T3  >   ComposeWith  <  T1  ,   T2  ,   T3  >  (  это   Func  <  T2  ,   T3  >   f  ,   Func  <  T1  ,   T2  >   g  )   =>   x   =>   f  (  g  (  x  ));

Руби [ править ]

Такие языки, как Ruby, позволяют вам самостоятельно создавать бинарный оператор:

class   Proc 
   def   compose  (  other_fn  ) 
     ->  (  *  as  )   {   other_fn  .   вызов  (  вызов  (  *  as  ))   } 
   end 
   alias_method   :+  ,   :compose 
 end 

 f   =   ->  (  x  )   {   x   *   2   } 
 g   =   ->  (  x  )   {   x   **   3   } 
 (  f   +   g  )  .   позвони  (  12  )   # => 13824

Однако в Ruby 2.6 появился собственный оператор композиции функций: ^[4]

е   =   процесс  {  |   х  |    х   +   2  } 
 г   =   процесс  {  |   х  |    Икс   *   3  } 
 (  ж   <<   г  )  .   вызов  (  3  )   # -> 11;   идентично f(g(3)) 
 (  f   >>   g  )  .   вызов  (  3  )   # -> 15;   идентично g(f(3))

Исследование [ править ]

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

Стил (1994) непосредственно применил функциональную композицию к сборке строительных блоков, известных как « монады » в языке программирования Haskell .
Мейер (1988) рассмотрел проблему повторного использования программного обеспечения с точки зрения компонуемости.
Абади и Лампорт (1993) формально определили правило доказательства функциональной композиции, которое гарантирует безопасность и жизнеспособность программы.
Крахт (2001) определил усиленную форму композиционности, поместив ее в семиотическую систему и применив ее к проблеме структурной двусмысленности, часто встречающейся в компьютерной лингвистике .
ван Гелдер и Порт (1993) исследовали роль композиционности в аналоговых аспектах обработки естественного языка.
Согласно обзору Гиббонса (2002) , формальная обработка композиции лежит в основе проверки сборки компонентов в языках визуального программирования, таких как IBM Visual Age для языка Java .

Масштабная композиция [ править ]

Целые программы или системы можно рассматривать как функции, которые можно легко составить, если их входные и выходные данные четко определены. ^[5] Конвейеры , позволяющие легко создавать фильтры, оказались настолько успешными, что стали образцом проектирования операционных систем.

Императивные процедуры с побочными эффектами нарушают ссылочную прозрачность и поэтому не могут быть полностью компонуемы. Однако если рассматривать «состояние мира» до и после запуска кода как его входные и выходные данные, можно получить чистую функцию. Состав таких функций соответствует последовательному запуску процедур. использует Формализм монады эту идею для включения побочных эффектов и ввода/вывода (I/O) в функциональные языки.

См. также [ править ]

Примечания [ править ]

^ Кокс (1986) , стр. 15–17.
^ ДеМарко и Листер (1995) , стр. 133–135.
^ «Руководство Nim: Синтаксис вызова методов» . nim-lang.org . Проверено 17 августа 2023 г.
^ «Выпущен 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 .
Дауме, Hal III, еще одно руководство по Haskell .
ДеМарко, Том ; Листер, Тим (1995), «Разработка программного обеспечения: современное состояние и состояние практики», в книге ДеМарко, Том (редактор), « Почему программное обеспечение стоит так дорого» и другие загадки информационного века , Нью-Йорк, Нью-Йорк: Дорсет Хаус, ISBN 0-932633-34-Х .
ван Гелдер, Тимоти ; Порт, Роберт (1993), «За пределами символического: пролегомены к Камасутре композиционности», в Хонаваре, Васант ; Ур, Леонард (ред.), Обработка символов и коннекционистские модели в искусственном интеллекте и познании: шаги к интеграции , Academic Press .
Гиббонс, Джереми (2002), Арбаб, Фархад; Талкотт, Кэролайн (ред.), Proc. 5-я Международная конференция по координационным моделям и языкам (PDF) , Конспекты лекций по информатике, том. 2315, Springer-Verlag, стр. 339–350, doi : 10.1007/3-540-46000-4\_18 .
Корн, Генри; Либери, Альберт (1974), Элементарный подход к функциям , Нью-Йорк, Нью-Йорк: McGraw-Hill, ISBN 0-07-035339-5 .
Крахт, Маркус (2001), «Строгая композиционность и грамматики буквальных движений», Proc. 3-я Международная конференция по логическим аспектам компьютерной лингвистики , Конспекты лекций по информатике, том. 2014, Springer-Verlag, стр. 126–143, номер документа : 10.1007/3-540-45738-0_8 .
Мейер, Бертран (1988), Объектно-ориентированное создание программного обеспечения , Нью-Йорк, Нью-Йорк: Prentice Hall, стр. 13–15, ISBN. 0-13-629049-3 .
Миллер, Джордж А. (1956), «Магическое число семь плюс-минус два: некоторые ограничения нашей способности обрабатывать информацию» , Psychoological Review , 63 (2): 81–97, doi : 10.1037/h0043158 , hdl : 11858/00-001M-0000-002C-4646-B , PMID 13310704 , заархивировано из оригинала 19 июня 2010 г. , получено 2 мая 2010 г.
Пирс, Бенджамин К.; Тернер, Дэвид Н. (2000), «Pict: язык программирования, основанный на пи-исчислении», Доказательство, язык и взаимодействие: эссе в честь Робина Милнера , серия «Основы вычислений», Кембридж, Массачусетс: MIT Press, стр. . 455–494, ISBN. 0-262-16188-5 .
Рэймонд, Эрик С. (2003), «1.6.3 Правило композиции: создавайте программы, которые будут связаны с другими программами» , Искусство программирования для Unix , Аддисон-Уэсли, стр. 15–16, ISBN 978-0-13-142901-7 .
Стил, Гай Л. младший (1994), «Создание интерпретаторов путем составления монад» , Proc. 21-й симпозиум ACM по принципам языков программирования , стр. 472–492, doi : 10.1145/174675.178068 .

[1] Кокс (1986) , стр. 15–17.

[2] ДеМарко и Листер (1995) , стр. 133–135.

[3] «Руководство Nim: Синтаксис вызова методов» . nim-lang.org . Проверено 17 августа 2023 г.

[4] «Выпущен Ruby 2.6.0» . www.ruby-lang.org . Проверено 4 января 2019 г.

[5] Раймонд (2003)

[1]

[2]

[3]

[4]

[5]