stringtranslate.com

Función de primera clase

En informática , se dice que un lenguaje de programación tiene funciones de primera clase si las trata como ciudadanos de primera clase . Esto significa que el lenguaje admite pasar funciones como argumentos a otras funciones, devolverlas como valores de otras funciones y asignarlas a variables o almacenarlas en estructuras de datos. [1] Algunos teóricos del lenguaje de programación también requieren soporte para funciones anónimas (literales de función). [2] En lenguajes con funciones de primera clase, los nombres de las funciones no tienen ningún estatus especial; se tratan como variables ordinarias con un tipo de función . [3] El término fue acuñado por Christopher Strachey en el contexto de "funciones como ciudadanos de primera clase" a mediados de la década de 1960. [4]

Las funciones de primera clase son una necesidad para el estilo de programación funcional , en el que el uso de funciones de orden superior es una práctica estándar. Un ejemplo simple de una función de orden superior es la función de mapa , que toma, como argumentos, una función y una lista, y devuelve la lista formada al aplicar la función a cada miembro de la lista. Para que un lenguaje admita map , debe admitir el paso de una función como argumento.

Existen ciertas dificultades de implementación al pasar funciones como argumentos o devolverlas como resultados, especialmente en presencia de variables no locales introducidas en funciones anidadas y anónimas . Históricamente, estos se denominaron problemas funarg , nombre que proviene de "argumento de función". [5] En los primeros lenguajes imperativos, estos problemas se evitaban no admitiendo funciones como tipos de resultados (por ejemplo, ALGOL 60 , Pascal ) u omitiendo funciones anidadas y, por tanto, variables no locales (por ejemplo, C ). El primer lenguaje funcional Lisp adoptó el enfoque de alcance dinámico , donde las variables no locales se refieren a la definición más cercana de esa variable en el punto donde se ejecuta la función, en lugar de donde se definió. En Scheme se introdujo el soporte adecuado para funciones de primera clase con alcance léxico y requiere manejar referencias a funciones como cierres en lugar de punteros de función simples , [4] lo que a su vez hace que la recolección de basura sea una necesidad.

Conceptos

En esta sección, comparamos cómo se manejan determinados modismos de programación en un lenguaje funcional con funciones de primera clase ( Haskell ) en comparación con un lenguaje imperativo donde las funciones son ciudadanas de segunda clase ( C ).

Funciones de orden superior: pasar funciones como argumentos

En lenguajes donde las funciones son ciudadanas de primera clase, las funciones se pueden pasar como argumentos a otras funciones de la misma manera que otros valores (una función que toma otra función como argumento se llama función de orden superior). En el idioma Haskell :

mapa :: ( a -> b ) -> [ a ] ​​-> [ b ] mapa f [] = [] mapa f ( x : xs ) = f x : mapa f xs                     

Los lenguajes donde las funciones no son de primera clase a menudo aún permiten escribir funciones de orden superior mediante el uso de características como punteros de función o delegados . En el idioma C :

mapa vacío ( int ( * f )( int ), int x [], size_t n ) { for ( int i = 0 ; i < n ; i ++ ) x [ i ] = f ( x [ i ]); }                   

Existen una serie de diferencias entre los dos enfoques que no están directamente relacionadas con el soporte de funciones de primera clase. El ejemplo de Haskell opera en listas , mientras que el ejemplo de C opera en matrices . Ambas son las estructuras de datos compuestas más naturales en los respectivos lenguajes y hacer que la muestra C funcione en listas enlazadas la habría hecho innecesariamente compleja. Esto también explica el hecho de que la función C necesita un parámetro adicional (que proporciona el tamaño de la matriz). La función C actualiza la matriz in situ , sin devolver ningún valor, mientras que en Haskell las estructuras de datos son persistentes (se devuelve una nueva lista). mientras que el antiguo se deja intacto.) El ejemplo de Haskell usa recursividad para recorrer la lista, mientras que el ejemplo de C usa iteración . Nuevamente, esta es la forma más natural de expresar esta función en ambos lenguajes, pero la muestra de Haskell podría haberse expresado fácilmente en términos de pliegue y la muestra de C en términos de recursividad. Finalmente, la función Haskell tiene un tipo polimórfico , como C no lo admite, hemos fijado todas las variables de tipo al tipo constante int.

Funciones anónimas y anidadas

En los lenguajes que soportan funciones anónimas, podemos pasar dicha función como argumento a una función de orden superior:

principal = mapa ( \ x -> 3 * x + 1 ) [ 1 , 2 , 3 , 4 , 5 ]              

En un lenguaje que no admite funciones anónimas, debemos vincularlo a un nombre:

int f ( int x ) { retorno 3 * x + 1 ; }         int principal () { int lista [] = { 1 , 2 , 3 , 4 , 5 }; mapa ( f , lista , 5 ); }             

Variables no locales y cierres.

Una vez que tenemos funciones anónimas o anidadas, resulta natural que hagan referencia a variables fuera de su cuerpo (llamadas variables no locales ):

principal = sea a = 3 b = 1 en el mapa ( \ x -> a * x + b ) [ 1 , 2 , 3 , 4 , 5 ]                      

Si las funciones se representan con punteros de función simples, ya no podemos saber cómo se le debe pasar el valor que está fuera del cuerpo de la función y, debido a eso, es necesario crear un cierre manualmente. Por lo tanto, aquí no podemos hablar de funciones "de primera clase".

estructura typedef { int ( * f )( int , int , int ); en un ; intb ;} cierre_t ;           mapa vacío ( cierre_t * cierre , int x [], tamaño_t n ) { para ( int i = 0 ; i < n ; ++ i ) x [ i ] = ( cierre -> f ) ( cierre -> a , cierre - > b , x [ i ]); }                     int f ( int a , int b , int x ) { devolver a * x + b ; }             vacío principal () { int l [] = { 1 , 2 , 3 , 4 , 5 }; int a = 3 ; int b = 1 ; cierre_t cierre = { f , a , b }; mapa ( & cierre , l , 5 ); }                           

También tenga en cuenta que mapahora está especializado en funciones que se refieren a dos ints fuera de su entorno. Esto se puede configurar de manera más general, pero requiere más código repetitivo . Si fhubiera sido una función anidada, todavía nos habríamos encontrado con el mismo problema y esta es la razón por la que no son compatibles con C. [6]

Funciones de orden superior: devolver funciones como resultados

Cuando devolvemos una función, de hecho estamos devolviendo su cierre. En el ejemplo de C, cualquier variable local capturada por el cierre quedará fuera de alcance una vez que regresemos de la función que crea el cierre. Forzar el cierre en un momento posterior dará como resultado un comportamiento indefinido, posiblemente corrompiendo la pila. Esto se conoce como el problema de la funarg hacia arriba .

Asignar funciones a variables

Asignar funciones a variables y almacenarlas dentro de estructuras de datos (globales) potencialmente sufre las mismas dificultades que devolver funciones.

f :: [[ Entero ] -> [ Entero ]] f = sea a = 3 b = 1 en [ mapa ( \ x -> a * x + b ), mapa ( \ x -> b * x + a )]                             

Igualdad de funciones

Como se puede probar la igualdad de la mayoría de los literales y valores, es natural preguntarse si un lenguaje de programación puede soportar la prueba de igualdad de funciones. Si se analiza más detalladamente, esta cuestión parece más difícil y hay que distinguir entre varios tipos de igualdad de funciones: [7]

Igualdad extensional
Dos funciones f y g se consideran extensivamente iguales si coinciden en sus salidas para todas las entradas (∀ x . f ( x ) = g ( x )). Según esta definición de igualdad, por ejemplo, dos implementaciones cualesquiera de un algoritmo de clasificación estable , como la clasificación por inserción y la clasificación por fusión , se considerarían iguales. Decidir sobre la igualdad extensional es indecidible en general e incluso para funciones con dominios finitos a menudo es intratable. Por esta razón, ningún lenguaje de programación implementa la igualdad de funciones como igualdad extensional.
Igualdad intencional
Bajo igualdad intensional, dos funciones f y g se consideran iguales si tienen la misma "estructura interna". Este tipo de igualdad podría implementarse en lenguajes interpretados comparando el código fuente de los cuerpos de las funciones (como en Interpreted Lisp 1.5) o el código objeto en lenguajes compilados . La igualdad intensional implica igualdad extensil (asumiendo que las funciones son deterministas y no tienen entradas ocultas, como el contador del programa o una variable global mutable ).
Igualdad de referencia
Dada la impracticabilidad de implementar la igualdad extensional e intencional, la mayoría de los lenguajes que soportan funciones de prueba para la igualdad utilizan igualdad de referencia. A todas las funciones o cierres se les asigna un identificador único (generalmente la dirección del cuerpo de la función o el cierre) y la igualdad se decide en función de la igualdad del identificador. Dos definiciones de funciones definidas por separado, pero por lo demás idénticas, se considerarán desiguales. La igualdad referencial implica igualdad intensional y extensional. La igualdad referencial rompe la transparencia referencial y, por lo tanto, no es compatible con lenguajes puros, como Haskell.

Teoría de tipos

En teoría de tipos , el tipo de funciones que aceptan valores de tipo A y devuelven valores de tipo B se puede escribir como AB o B A. En la correspondencia Curry-Howard , los tipos de funciones están relacionados con la implicación lógica ; la abstracción lambda corresponde al cumplimiento de supuestos hipotéticos y la aplicación de funciones corresponde a la regla de inferencia modus ponens . Además del caso habitual de funciones de programación, la teoría de tipos también utiliza funciones de primera clase para modelar matrices asociativas y estructuras de datos similares .

En las explicaciones de programación teóricas de categorías , la disponibilidad de funciones de primera clase corresponde al supuesto de categoría cerrada . Por ejemplo, el cálculo lambda simplemente escrito corresponde al lenguaje interno de las categorías cerradas cartesianas .

Ayuda de idioma

Los lenguajes de programación funcionales, como Erlang , Scheme , ML , Haskell , F# y Scala , tienen funciones de primera clase. Cuando se diseñó Lisp , uno de los primeros lenguajes funcionales, no se entendieron adecuadamente todos los aspectos de las funciones de primera clase, lo que dio como resultado que las funciones tuvieran un alcance dinámico. Los dialectos posteriores Scheme y Common Lisp tienen funciones de primera clase con alcance léxico.

Muchos lenguajes de programación, incluidos Perl , Python , PHP , Lua , Tcl /Tk, JavaScript e Io , tienen funciones de primera clase.

Para los lenguajes imperativos, se debe hacer una distinción entre Algol y sus descendientes, como Pascal, la familia C tradicional y las variantes modernas recolectadas de basura. La familia Algol ha permitido funciones anidadas y funciones de orden superior que toman como argumentos, pero no funciones de orden superior que devuelven funciones como resultados (excepto Algol 68, que lo permite). La razón de esto era que no se sabía cómo tratar con variables no locales si como resultado se devolvía una función anidada (y Algol 68 produce errores de tiempo de ejecución en tales casos).

La familia C permitía pasar funciones como argumentos y devolverlas como resultados, pero evitaba cualquier problema al no admitir funciones anidadas. (El compilador gcc los permite como una extensión). Como la utilidad de devolver funciones radica principalmente en la capacidad de devolver funciones anidadas que han capturado variables no locales, en lugar de funciones de nivel superior, generalmente no se considera que estos lenguajes tengan primero -funciones de clase.

Los lenguajes imperativos modernos a menudo admiten la recolección de basura, lo que hace factible la implementación de funciones de primera clase. Las funciones de primera clase a menudo solo han sido admitidas en revisiones posteriores del lenguaje, incluido C# 2.0 y la extensión Blocks de Apple para C, C++ y Objective-C. C++ 11 ha agregado soporte para funciones anónimas y cierres al lenguaje, pero debido a la naturaleza del lenguaje que no recolecta basura, se debe tener especial cuidado con las variables no locales en las funciones que se devolverán como resultados (ver más abajo ).

C++
Los cierres de C++ 11 pueden capturar variables no locales mediante construcción de copia, por referencia (sin extender su vida útil) o mediante construcción de movimiento (la variable vive tanto como el cierre). La primera opción es segura si se devuelve el cierre pero requiere una copia y no se puede usar para modificar la variable original (que podría ya no existir en el momento en que se llama al cierre). La segunda opción evita potencialmente una copia costosa y permite modificar la variable original, pero no es segura en caso de que se devuelva el cierre (consulte las referencias pendientes ). La tercera opción es segura si se devuelve el cierre y no requiere una copia, pero tampoco se puede utilizar para modificar la variable original.
Java
Los cierres de Java 8 solo pueden capturar variables no locales finales o "efectivamente finales". Los tipos de funciones de Java se representan como Clases. Las funciones anónimas toman el tipo inferido del contexto. Las referencias de métodos son limitadas. Para obtener más detalles, consulte Función anónima § Limitaciones de Java .
Ceceo
Las variantes de Lisp con alcance léxico admiten cierres. Las variantes de ámbito dinámico no admiten cierres ni necesitan una construcción especial para crear cierres. [22]
En Common Lisp , el identificador de una función en el espacio de nombres de la función no se puede utilizar como referencia a un valor de primera clase. El operador especial functiondebe usarse para recuperar la función como un valor: (function foo)se evalúa como un objeto de función. #'fooexiste como una notación abreviada. Para aplicar un objeto de función de este tipo, se debe utilizar la funcallfunción: (funcall #'foo bar baz).
Pitón
Aplicación parcial explícita functools.partialdesde la versión 2.5 y operator.methodcallerdesde la versión 2.6.
Rubí
El identificador de una "función" normal en Ruby (que en realidad es un método) no se puede utilizar como valor ni pasar. Primero se debe recuperar en un objeto Methodo Procpara utilizarlo como datos de primera clase. La sintaxis para llamar a un objeto de función de este tipo difiere de la de llamar a métodos normales.
Las definiciones de métodos anidados en realidad no anidan el alcance.
Curry explícito con [1].

Ver también

Notas

  1. ^ Abelson, Harold ; Sussman, Gerald Jay (1984). Estructura e Interpretación de Programas Informáticos. Prensa del MIT. Formulación de abstracciones con procedimientos de orden superior. ISBN 0-262-01077-1.
  2. ^ Pragmática del lenguaje de programación, por Michael Lee Scott, sección 11.2 "Programación funcional".
  3. ^ Roberto Ierusalimschy ; Luis Enrique de Figueiredo; Waldemar Celes (2005). "La implementación de Lua 5.0". Revista de Informática Universal . 11 (7): 1159-1176. doi : 10.3217/jucs-011-07-1159 .
  4. ^ ab Burstall, Rod; Strachey, Christopher (2000). "Comprensión de los lenguajes de programación" (PDF) . Computación simbólica y de orden superior . 13 (52): 11–49. doi :10.1023/A:1010052305354. S2CID  1989590. Archivado desde el original el 16 de febrero de 2010.{{cite journal}}: Mantenimiento CS1: bot: estado de la URL original desconocido ( enlace )(también el 2010-02-16
  5. ^ Joel Moisés . "La función de FUNCIÓN en LISP, o por qué el problema FUNARG debería llamarse problema ambiental". Memorándum 199 del MIT AI, 1970.
  6. ^ "Si intenta llamar a la función anidada a través de su dirección después de que la función contenedora haya salido, se desatará el infierno". (Colección de compiladores GNU: funciones anidadas)
  7. ^ Andrew W. Appel (1995). "Igualdad intencional ;=) para continuaciones".
  8. ^ Tanenbaum, AS (1977). "Una comparación de PASCAL y Algol 68". La revista informática . 21 (4): 319. doi : 10.1093/comjnl/21.4.316 .
  9. ^ "La historia de Python: orígenes de las características" funcionales "de Python". 21 de abril de 2009.
  10. ^ Funciones anidadas usando lambdas/cierres
  11. ^ ab Doc No. 1968: V Samko; J Willcock, J Järvi, D Gregor, A Lumsdaine (26 de febrero de 2006) Expresiones lambda y cierres para C++
  12. ^ "Mac Dev Center: Temas de programación de bloques: Introducción". Archivado desde el original el 31 de agosto de 2009.
  13. ^ "2 ejemplos en Go que puedes tener aplicación parcial".
  14. ^ "aplicación_parcial". Docs.rs.Consultado el 3 de noviembre de 2020 .
  15. ^ "SRFI 26: Notación para parámetros especializados sin curry".
  16. ^ "John Resig - Aplicación parcial en JavaScript".
  17. ^ Katz, Ian (23 de julio de 2010). "Código Lua para Curry (funciones de curry)". Archivado desde el original el 6 de noviembre de 2018.
  18. ^ "Blog | Perlgeek.de :: Curry".
  19. ^ "Novedades de Python 2.5: documentación de Python 3.10.0".
  20. ^ "Funciones anónimas - MATLAB y Simulink - MathWorks Reino Unido".
  21. ^ Evaluación de funciones parciales en MATLAB
  22. ^ Cierres en ZetaLisp Archivado el 19 de marzo de 2012 en la Wayback Machine.

Referencias

enlaces externos