Hispanopedia Wiki
Articulo de referencia

Flecha (informática)

En informática , las flechas o pernos son una clase de tipo utilizada en la programación para describir cálculos de forma pura y declarativa . Propuestas inicialmente por el inf...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática , las flechas o pernos son una clase de tipo utilizada en la programación para describir cálculos de forma pura y declarativa . Propuestas inicialmente por el informático John Hughes como una generalización de las mónadas , las flechas proporcionan una forma referencialmente transparente de expresar relaciones entre pasos lógicos en un cálculo. [ 1 ] A diferencia de las mónadas, las flechas no limitan los pasos a tener una única entrada. Por ello, se han utilizado en programación reactiva funcional , programación tácita (estilo sin puntos), analizadores sintácticos y en otros usos. [ 1 ] [ 2 ]

Motivación e historia

Aunque las flechas se utilizaban antes de ser reconocidas como una clase distinta, no fue hasta el año 2000 que John Hughes publicó la primera investigación centrada en ellas. Hasta entonces, las mónadas habían demostrado ser suficientes para la mayoría de los problemas que requerían la combinación de lógica de programa en código puro. Sin embargo, algunas bibliotecas útiles , como la biblioteca Fudgets para interfaces gráficas de usuario y ciertos analizadores sintácticos eficientes, resistían la reescritura en forma monádica. [ 1 ]

El concepto formal de flechas se desarrolló para explicar estas excepciones al código monádico, y en el proceso se descubrió que las mónadas eran un subconjunto de flechas . [ 1 ] Desde entonces, las flechas han sido un área activa de investigación. Sus leyes y operaciones subyacentes se han refinado varias veces, y formulaciones recientes como el cálculo de flechas requieren solo cinco leyes. [ 3 ]

Relación con la teoría de categorías

En teoría de categorías , las categorías de Kleisli de todas las mónadas forman un subconjunto propio de las flechas de Hughes. [ 1 ] Si bien durante un tiempo se creyó que las categorías de Freyd eran equivalentes a las flechas, [ 4 ] desde entonces se ha demostrado que las flechas son aún más generales: las flechas no son simplemente equivalentes, sino directamente iguales a las categorías de Freyd enriquecidas . [ 5 ]

Definición

Al igual que todas las clases de tipos, las flechas pueden considerarse como un conjunto de cualidades que se pueden aplicar a cualquier tipo de dato . En el lenguaje de programación Haskell , las flechas permiten que las funciones (representadas en Haskell por ->un símbolo) se combinen de forma reificada . Sin embargo, el término "flecha" también puede derivar del hecho de que algunas (pero no todas) flechas corresponden a los morfismos (también conocidos como "flechas" en la teoría de categorías) de diferentes categorías de Kleisli. Como concepto relativamente nuevo, no existe una definición estándar, pero todas las formulaciones son lógicamente equivalentes, presentan algunos métodos necesarios y obedecen estrictamente ciertas leyes matemáticas. [ 6 ]

Funciones

La descripción que utilizan actualmente las bibliotecas estándar de Haskell requiere solo tres operaciones básicas:

  • Un constructor de tiposarr que toma funciones ->de cualquier tipo sa otro ty eleva esas funciones en una flecha Aentre los dos tipos. [ 7 ]
arr : ( s -> t ) -> A s t
  • Un método de canalización firstque toma una flecha entre dos tipos y la convierte en una flecha entre tuplas . Los primeros elementos de las tuplas representan la porción de la entrada y la salida que se modifica, mientras que los segundos elementos son un tercer tipo uque describe una porción inalterada que omite el cálculo. [ 7 ]
primero : A s t -> A ( s , u ) ( t , u )
  • Como todas las flechas deben ser categorías , heredan una tercera operación de la clase de categorías: un operador de composición>>> que puede adjuntar una segunda flecha a una primera siempre que la salida de la primera función y la entrada de la segunda tengan tipos coincidentes. [ 7 ]
( >>> ) : A s t -> A t u -> A s u

Si bien estos tres procedimientos son estrictamente necesarios para definir una flecha, se pueden derivar otros métodos para facilitar el trabajo con flechas tanto en la práctica como en la teoría.

Otro método útil puede derivarse de arry first(y del cual firstpuede derivarse):

  • Un operador de fusión ***que toma dos flechas, posiblemente con diferentes tipos de entrada y salida, y las fusiona en una sola flecha entre dos tipos compuestos. El operador de fusión no es necesariamente conmutativo . [ 7 ]
( *** ) : A s t -> A u v -> A ( s , u ) ( t , v )

Leyes de flechas

Además de contar con procedimientos bien definidos, las flechas deben obedecer ciertas reglas para cualquier tipo al que se apliquen:

  • Las flechas siempre deben preservar las identidades de todos los tipos ( esencialmente las definiciones de todos los valores para todos los tipos dentro de una categoría). [ 7 ]
arr id == id
  • Al conectar dos funciones f y g , las operaciones de flecha requeridas deben distribuirse sobre composiciones desde la izquierda. [ 7 ]
arr ( f >>> g ) == arr f >>> arr g first ( f >>> g ) == first f >>> first g
  • En las leyes anteriores, las tuberías se pueden aplicar directamente a las funciones porque el orden debe ser irrelevante cuando las tuberías y el levantamiento ocurren simultáneamente. [ 7 ]
arr ( primer f ) == primer ( arr f )

Las leyes restantes restringen cómo se comporta el método de tuberías cuando se invierte el orden de una composición, permitiendo también expresiones simplificadas :

  • Si una identidad se fusiona con una segunda función para formar una flecha, adjuntarla a una función encadenada debe ser conmutativa. [ 7 ]
arr ( id *** g ) >>> first f == first f >>> arr ( id *** g )
  • El enrutamiento de una función antes de la simplificación de tipos debe ser equivalente a simplificar el tipo antes de conectarse a la función sin enrutamiento. [ 7 ]
primero f >>> arr (( s , t ) -> s ) == arr (( s , t ) -> s ) >>> f
  • Finalmente, aplicar una función dos veces antes de volver a asociar la tupla resultante, que está anidada, debería ser lo mismo que volver a asociar la tupla anidada antes de adjuntar una única derivación de la función. En otras palabras, las derivaciones apiladas se pueden aplanar agrupando primero aquellos elementos que no se ven afectados por la función. [ 7 ]
primero ( primer f ) >>> arr ( (( s , t ), u ) -> ( s ,( t , u )) ) == arr ( (( s , t ), u ) -> ( s ,( t , u )) ) >>> primer f

Aplicaciones

Las flechas pueden extenderse para adaptarse a situaciones específicas definiendo operaciones y restricciones adicionales. Las versiones más comunes incluyen flechas con opción, que permiten que un cálculo tome decisiones condicionales , y flechas con retroalimentación , que permiten que un paso tome sus propias salidas como entradas. Otro conjunto de flechas, conocidas como flechas con aplicación , rara vez se utilizan en la práctica porque son equivalentes a mónadas . [ 6 ]

Utilidad

Las flechas ofrecen varias ventajas, principalmente derivadas de su capacidad para hacer que la lógica del programa sea explícita y concisa. Además de evitar efectos secundarios , la programación puramente funcional crea más oportunidades para el análisis estático del código . Esto, a su vez, puede conducir teóricamente a mejores optimizaciones del compilador , una depuración más sencilla y características como el azúcar sintáctico . [ 6 ]

Aunque ningún programa requiere estrictamente flechas, estas generalizan gran parte del denso paso de funciones que requeriría el código declarativo puro. También pueden fomentar la reutilización de código al asignar definiciones de clase propias a los vínculos comunes entre los pasos del programa. La capacidad de aplicarlas a tipos de forma genérica también contribuye a la reutilización y mantiene las interfaces simples. [ 6 ]

Las flechas tienen algunas desventajas, incluido el esfuerzo inicial de definir una flecha que satisfaga las leyes de las flechas. Dado que las mónadas suelen ser más fáciles de implementar, y las características adicionales de las flechas pueden ser innecesarias, a menudo es preferible usar una mónada. [ 6 ] Otro problema, que se aplica a muchas construcciones de programación funcional , es compilar eficientemente el código con flechas al estilo de programación imperativa utilizado por las arquitecturas de conjuntos de instrucciones de las computadoras .

Límites

La necesidad de definir una arrfunción para elevar funciones puras limita la aplicabilidad de las flechas. Por ejemplo, las transformaciones bidireccionales no pueden ser flechas, porque un programa debe proporcionar una función pura y su inversa al usarlas arr. [ 8 ] Esto también limita el uso de flechas para describir marcos reactivos basados ​​en empuje que detienen la propagación innecesaria. De manera similar, el uso de pares para tuplar valores resulta en un estilo de codificación difícil que requiere combinadores adicionales para reagrupar valores y plantea preguntas fundamentales sobre la equivalencia de flechas agrupadas de diferentes maneras. Estas limitaciones siguen siendo un problema abierto, y extensiones como Flechas Generalizadas [ 8 ] y FRP N-ario [ 9 ] exploran estos problemas.

Gran parte de la utilidad de las flechas está subsumida por clases más generales como profunctor(que solo requiere pre- y postcomposición con funciones), que tienen aplicación en optics. Una flecha es esencialmente un profunctor fuerte que también es una categoría, aunque las leyes difieren ligeramente.

Referencias

  1. 1 2 3 4 5 Hughes, John (mayo de 2000). "Generalizando mónadas a flechas". Science of Computer Programming . 37 ( 1–3 ): 67–111 . doi : 10.1016/S0167-6423(99)00023-4 . ISSN 0167-6423 . 
  2. ↑ Paterson, Ross (27 de marzo de 2003). «Capítulo 10: Flechas y computación» (PS.GZ) . En Gibbons, Jeremy; de Moor, Oege (eds.). The Fun of Programming . Palgrave Macmillan. pp. 201–222 . ISBN  978-1403907721Consultado el 10 de junio de 2012 .
  3. ↑ Lindley, Sam; Wadler, Philip ; Yallop, Jeremy (enero de 2010). "El cálculo de flechas" (PDF) . Journal of Functional Programming . 20 (1): 51– 69. doi : 10.1017/S095679680999027X . hdl : 1842/3716 . ISSN 0956-7968 . S2CID 7387691. Recuperado el 10 de junio de 2012 .  
  4. ↑ Jacobs, Bart; Heunen, Chris; Hasuo, Ichiro (2009). "Semántica categórica para flechas". Journal of Functional Programming . 19 ( 3– 4): 403– 438. doi : 10.1017/S0956796809007308 . hdl : 2066/75278 .
  5. ↑ Atkey, Robert (8 de marzo de 2011). "¿Qué es un modelo categórico de flechas?" . Electronic Notes in Theoretical Computer Science . 229 (5): 19– 37. doi : 10.1016/j.entcs.2011.02.014 . ISSN 1571-0661 . 
  6. 1 2 3 4 5 Hughes, John (2005) [14–21 de agosto de 2004]. "Programación con flechas" (PDF) . Programación funcional avanzada . 5.ª Escuela Internacional de Verano sobre Programación Funcional Avanzada. Tartu, Estonia: Springer. págs. 73–129 . doi : 10.1007/11546382_2 . ISBN  978-3-540-28540-3Consultado el 10 de junio de 2012 .
  7. 1 2 3 4 5 6 7 8 9 10 Paterson, Ross (2002). "Control.Arrow" . base-4.5.0.0: Bibliotecas básicas . Haskell.org. Archivado del original el 13 de febrero de 2006. Recuperado el 10 de junio de 2012 .
  8. 1 2 Joseph, Adam Megacz (2014). "Flechas generalizadas" (PDF) . Informe técnico n.º UCB/EECS-2014-130 . Departamento de EECS, Universidad de California, Berkeley . Recuperado el 20 de octubre de 2018 .
  9. ↑ Sculthorpe, Neil (2011). Hacia una programación reactiva funcional segura y eficiente (PDF) (tesis doctoral). Nottingham, Inglaterra: Universidad de Nottingham .
  • Flechas: Una interfaz general para la computación
  • Una nueva notación para flechas , Ross Paterson, en ICFP, septiembre de 2001.
  • Manual de notación de flechas de GHC