Composición de funciones (informática)

En informática , la composición de funciones es un proceso o mecanismo para combinar funciones simples y construir otras más complejas. Al igual que en la composición de funciones en matemáticas , el resultado de cada función se pasa como argumento de la siguiente, y el resultado de la última es el resultado de la función completa.

Los programadores suelen aplicar funciones a los resultados de otras funciones, y casi todos los lenguajes de programación lo permiten. En algunos casos, la composición de funciones resulta interesante como función independiente, para su posterior uso. Si bien siempre es posible definir una función de este tipo, los lenguajes con funciones de primera clase lo facilitan.

La facilidad para componer funciones fomenta la factorización (descomposición) de las mismas para mejorar el mantenimiento y la reutilización del código . En términos más generales, los sistemas complejos pueden construirse componiendo programas completos.

En sentido estricto, la composición de funciones se aplica a funciones que operan sobre una cantidad finita de datos, procesándolos secuencialmente en cada paso antes de pasarlos al siguiente. Las funciones que operan sobre datos potencialmente infinitos (un flujo u otros datos de entrada ) se conocen como filtros y, en cambio, se conectan en una tubería , que es análoga a la composición de funciones y puede ejecutarse simultáneamente .

Por ejemplo, supongamos que tenemos dos funciones f y g , como en z = f ( y ) e y = g ( x ) . Para componerlas, primero calculamos y = g ( x ) y luego usamos y para calcular z = f ( y ) . Aquí está el ejemplo en lenguaje C :

float x , y , z ; // ... y = g ( x ); z = f ( y );

Los pasos se pueden combinar si no le damos un nombre al resultado intermedio:

z = f ( g ( x ));

A pesar de las diferencias de longitud, estas dos implementaciones calculan el mismo resultado. La segunda implementación requiere solo una línea de código y se la conoce coloquialmente como una forma "altamente compuesta". La legibilidad y, por lo tanto, la mantenibilidad es una ventaja de las formas altamente compuestas, ya que requieren menos líneas de código, minimizando el "área de superficie" de un programa. ^{[ 1 ]} DeMarco y Lister verifican empíricamente una relación inversa entre el área de superficie y la mantenibilidad. ^{[ 2 ]} Por otro lado, es posible abusar de las formas altamente compuestas. Un anidamiento excesivo de funciones puede tener el efecto contrario, haciendo que el código sea menos mantenible.

En un lenguaje basado en pila , la composición funcional es aún más natural: se realiza mediante concatenación y suele ser el método principal de diseño de programas. El ejemplo anterior en Forth :

novia

Esto tomará lo que estuviera en la pila antes, aplicará g, luego f, y dejará el resultado en la pila. Consulte la notación de composición posfija para la notación matemática correspondiente.

Ahora supongamos que la combinación de llamar a f() sobre el resultado de g() es frecuentemente útil, y que queremos llamar foo() para que se utilice como una función por derecho propio.

En la mayoría de los lenguajes, podemos definir una nueva función implementada por composición. Ejemplo en C :

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

(La forma larga con intermedios también funcionaría). Ejemplo en Forth :

 : foo gf ;

En lenguajes como C , la única forma de crear una nueva función es definirla en el código fuente del programa, lo que significa que las funciones no se pueden componer en tiempo de ejecución . Sin embargo, es posible evaluar una composición arbitraria de funciones predefinidas :

#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 );devolver 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 )); }

En los lenguajes de programación funcional , la composición de funciones se puede expresar de forma natural como una función u operador de orden superior . En otros lenguajes de programación, se pueden escribir mecanismos propios para realizar la composición de funciones.

foo = f . g

( . ) :: ( b -> c ) -> ( a -> b ) -> a -> c f . g = \ x -> f ( g x )

f g x y

( . ) . ( . )

( define ( compose . fs ) ( if ( null? fs ) ( lambda ( x ) x ) ; si no se proporciona ningún argumento, se evalúa a la función identidad ( lambda ( x ) (( car fs ) (( apply compose ( cdr fs )) x ))))); ejemplos ( define ( add-a-bang str ) ( string-append str "!" ))( define givebang ( componer cadena->símbolo agregar-un-bang símbolo->cadena ))( givebang 'set ) ; ===> ¡set!; composición anónima (( componer raíz cuadrada - raíz cuadrada ) 5 ) ; ===> 0+5i

foo ← f ∘ g

o ← { ⍺⍺ ⍵⍵ ⍵ }

∇ r ← ( f o g ) x r ← f g x ∇

mi & foo = & f ∘ & g ;

# la implementación tiene una línea ligeramente diferente aquí porque hace trampa proto sub infix :<∘> (&?, &?) es equiv(&[~]) es assoc<left> { * }multi sub infix :<∘> () { *. self } # permite que `[∘] @array` funcione cuando `@array` está vacío multi sub infix :<∘> (&f) { & f } # permite que `[∘] @array` funcione cuando `@array` tiene un elemento multi sub infix :<∘> (&f, &g --> Block) { ( & f ) . count > 1 ?? -> | args { f | g | args } !! -> | args { f g | args } }# alias para la ortografía "Texas" (todo es más grande y ASCII en Texas) mi & infijo: <o> : = & infijo: <∘> ;

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 [ string ] ) = for i in a : echo i# ¡equivalente! echo foo ( 5 ). bar ( 6 ). baz () echo baz ( bar ( 6 , foo ( 5 )))

from functools import reduce from typing import Callabledef compose ( * funcs ) -> Callable [[ int ], int ]: """Compone un grupo de funciones (f(g(h(...)))) en una única función compuesta.""" return reduce ( lambda f , g : lambda x : f ( g ( x )), funcs )# Ejemplo f = lambda x : x + 1 g = lambda x : x * 2 h = lambda x : x - 3# Llamar a la función x=10 : ((x - 3) * 2) + 1 = 15 print ( compose ( f , g , h )( 10 ))

función o ( f , g ) { return función ( x ) { return f ( g ( x )); } }// Alternativamente, usando el operador rest y expresiones lambda en ES2015 const compose = (... fs ) => ( x ) => fs . reduceRight (( acc , f ) => f ( acc ), x )

// Ejemplo de llamada: // var c = f.ComposeWith(g); // // Func<int, bool> g = _ => ... // Func<bool, string> f = _ => ...public static Func < T1 , T3 > ComposeWith < T1 , T2 , T3 > ( this Func < T2 , T3 > f , Func < T1 , T2 > g ) => x => f ( g ( x ));

clase Proc def componer ( otra_función ) -> ( * como ) { otra_función . llamar ( llamar ( * como )) } fin alias_method :+ , :componer finf = -> ( x ) { x * 2 } g = -> ( x ) { x ** 3 } ( f + g ) . call ( 12 ) # => 13824

f = proc { | x | x + 2 } g = proc { | x | x * 3 } ( f << g ) . call ( 3 ) # -> 11; idéntico a f(g(3)) ( f >> g ) . call ( 3 ) # -> 15; idéntico a g(f(3))

Las nociones de composición, incluyendo el principio de composicionalidad y componibilidad , son tan omnipresentes que numerosas líneas de investigación han evolucionado por separado. A continuación, se presenta una muestra del tipo de investigación en la que la noción de composición es fundamental.

• Steele (1994) aplicó directamente la composición de funciones al conjunto de bloques de construcción conocidos como ' mónadas ' en el lenguaje de programación Haskell .
• Meyer (1988) abordó el problema de la reutilización de software en términos de componibilidad.
• Abadi y Lamport (1993) definieron formalmente una regla de prueba para la composición funcional que garantiza la seguridad y la vivacidad de un programa.
• Kracht (2001) identificó una forma reforzada de composicionalidad al colocarla en un sistema semiótico y aplicarla al problema de la ambigüedad estructural que se encuentra con frecuencia en la lingüística computacional .
• Van Gelder y Port (1993) examinaron el papel de la composicionalidad en aspectos analógicos del procesamiento del lenguaje natural.
• Según una revisión de Gibbons (2002) , el tratamiento formal de la composición subyace a la validación del ensamblaje de componentes en lenguajes de programación visual como Visual Age de IBM para el lenguaje Java .

Los programas o sistemas completos pueden tratarse como funciones, que pueden componerse fácilmente si sus entradas y salidas están bien definidas. ^{[ 7 ]} Las tuberías que permiten una fácil composición de filtros tuvieron tanto éxito que se convirtieron en un patrón de diseño de sistemas operativos.

Los procedimientos imperativos con efectos secundarios violan la transparencia referencial y, por lo tanto, no son fácilmente componibles. Sin embargo, si se considera el "estado del mundo" antes y después de ejecutar el código como su entrada y salida, se obtiene una función limpia. La composición de dichas funciones corresponde a ejecutar los procedimientos uno tras otro. El formalismo de mónadas utiliza esta idea para incorporar efectos secundarios y entrada/salida (E/S) en lenguajes funcionales.

• Zurra
• Descomposición funcional
• Herencia de implementación
• Semántica de la herencia
• Iterar
• Tubería (Unix)
• Principio de composicionalidad
• Herencia virtual

• Abadi, Martín ; Lamport, Leslie (1993), "Composing Specifications" (PDF) , ACM Transactions on Programming Languages ​​and Systems , 15 (1): 73–132 , doi : 10.1145/151646.151649.
• Cox, Brad (1986), Programación orientada a objetos: un enfoque evolutivo , Reading, MA: Addison-Wesley, Bibcode : 1986oopa.book.....C , ISBN 978-0-201-54834-1.
• Daume, Hal III, Otro tutorial más de Haskell.
• DeMarco, Tom ; Lister, Tim (1995), "Desarrollo de software: estado del arte frente al estado de la práctica", en DeMarco, Tom (ed.), ¿Por qué el software cuesta tanto? y otros enigmas de la era de la información , Nueva York, NY: Dorset House, ISBN 0-932633-34-X.
• van Gelder, Timothy ; Port, Robert (1993), "Más allá de lo simbólico: prolegómenos a un Kama-Sutra de la composicionalidad", en Honavar, Vasant ; Uhr, Leonard (eds.), Procesamiento de símbolos y modelos conexionistas en inteligencia artificial y cognición: pasos hacia la integración , Academic Press.
• Gibbons, Jeremy (2002), "Hacia una semántica basada en colímites para la programación visual", en Arbab, Farhad; Talcott, Carolyn (eds.), Actas de la 5.ª Conferencia Internacional sobre Modelos y Lenguajes de Coordinación (PDF) , Lecture Notes in Computer Science, vol.  2315, Springer-Verlag, pp. 339–350 , doi : 10.1007/3-540-46000-4_18 , ISBN  978-3-540-43410-8.
• Korn, Henry; Liberi, Albert (1974), Un enfoque elemental de las funciones , Nueva York, NY: McGraw-Hill, ISBN 0-07-035339-5.
• Kracht, Marcus (2001), "Composicionalidad estricta y gramáticas de movimiento literal", Actas de la 3.ª Conferencia Internacional sobre Aspectos Lógicos de la Lingüística Computacional , Lecture Notes in Computer Science, vol.  2014, Springer-Verlag, pp. 126–143 , doi : 10.1007/3-540-45738-0_8 , ISBN  978-3-540-42251-8.
• Meyer, Bertrand (1988), Construcción de software orientado a objetos , Nueva York, NY: Prentice Hall, pp. 13–15 , ISBN  0-13-629049-3.
• Miller, George A. (1956), "El número mágico siete, más o menos dos: algunos límites a nuestra capacidad de procesar información" , Psychological Review , 63 (2): 81–97 , doi : 10.1037/h0043158 , hdl : 11858/00-001M-0000-002C-4646-B , PMID 13310704 , archivado del original el 19 de junio de 2010 , recuperado el 2 de mayo de 2010. .
• Pierce, Benjamin C.; Turner, David N. (2000), «Pict: Un lenguaje de programación basado en el cálculo pi», Prueba, lenguaje e interacción: Ensayos en honor a Robin Milner , Serie Fundamentos de la computación, Cambridge, MA: MIT Press, pp. 455–494 , ISBN  0-262-16188-5.
• Raymond, Eric S. (2003), "1.6.3 Regla de composición: Diseñar programas para que se conecten con otros programas" , The Art of Unix Programming , Addison-Wesley, pp. 15–16 , ISBN  978-0-13-142901-7.
• Steele, Guy L. Jr. (1994), "Construcción de intérpretes mediante la composición de mónadas" , Actas del 21.º Simposio ACM sobre Principios de Lenguajes de Programación , págs. 472–492 , doi : 10.1145/174675.178068 , ISBN  0-89791-636-0.