En informática , un lenguaje de programación se dice que tiene funciones de primera clase si se trata funciones 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 ordinariascon 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 aplicando la función a cada miembro de la lista. Para que un lenguaje admita map , debe admitir pasar 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 anidadas . Históricamente, estos se denominaron problemas de funarg , cuyo nombre proviene de "argumento de función". [5] En los primeros lenguajes imperativos, estos problemas se evitaban al no admitir funciones como tipos de resultado (por ejemplo, ALGOL 60 , Pascal ) u omitiendo funciones anidadas y, por lo tanto, variables no locales (por ejemplo, C ). El lenguaje funcional temprano 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ó. El soporte adecuado para funciones de primera clase con ámbito léxico se introdujo en Scheme y requiere el manejo de referencias a funciones como cierres en lugar de punteros de función desnudos , [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 modismos de programación particulares en un lenguaje funcional con funciones de primera clase ( Haskell ) en comparación con un lenguaje imperativo donde las funciones son ciudadanos de segunda clase ( C ).
Funciones de orden superior: pasar funciones como argumentos
En lenguajes donde las funciones son ciudadanos 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 ) { para ( int i = 0 ; i < n ; i ++ ) x [ i ] = f ( x [ i ]); }
Hay una serie de diferencias entre los dos enfoques que no están directamente relacionadas con el soporte de funciones de primera clase. La muestra de Haskell opera en listas , mientras que la muestra 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 opere en listas enlazadas lo habría hecho innecesariamente complejo. 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 en el lugar , 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). La muestra de Haskell usa la recursividad para recorrer la lista, mientras que la muestra C usa la iteración . Una vez más, esta es la forma más natural de expresar esta función en ambos idiomas, pero la muestra de Haskell podría haberse expresado fácilmente en términos de pliegue y la muestra C en términos de recursividad. Finalmente, la función de Haskell tiene un tipo polimórfico , ya que C no lo admite, hemos fijado todas las variables de tipo a la constante de tipo int
.
Funciones anónimas y anidadas
En los lenguajes que admiten 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 idioma que no admite funciones anónimas, tenemos que vincularlo a un nombre en su lugar:
int f ( int x ) { return 3 * x + 1 ; }int main () { 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, es natural que se refieran 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 desnudos, ya no podemos saber cómo se le debe pasar el valor que está fuera del cuerpo de la función y, por lo tanto, es necesario crear un cierre manualmente. Por tanto, no podemos hablar aquí de funciones de "primera clase".
typedef struct { int ( * f ) ( int , int , int ); int * a ; int * b ; } cierre_t ; mapa vacío ( cierre_t * cierre , int x [], tamaño_t n ) { for ( int i = 0 ; i < n ; ++ i ) x [ i ] = ( * cierre -> f ) ( * cierre -> a , * cierre -> b , x [ i ]); }int f ( int a , int b , int x ) { return a * x + b ; }void main () { 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 map
ahora está especializado en funciones que se refieren a dos int
s fuera de su entorno. Esto se puede configurar de manera más general, pero requiere más código estándar . Si f
hubiera 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: funciones de retorno como resultados
Al devolver una función, de hecho estamos devolviendo su cierre. En el ejemplo de C, cualquier variable local capturada por el cierre saldrá del alcance una vez que regresemos de la función que construye el cierre. Forzar el cierre en un punto posterior resultará en un comportamiento indefinido, posiblemente corrompiendo la pila. Esto se conoce como el problema del funarg ascendente .
Asignar funciones a variables
Asignar funciones a variables y almacenarlas dentro de estructuras de datos (globales) presenta potencialmente 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 admitir funciones de prueba de igualdad. En una inspección más profunda, esta pregunta 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 extensionalmente igual si están de acuerdo en sus salidas para todas las entradas (∀ x . F ( x ) = g ( x )). Bajo 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 intratables. 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 intencional implica la igualdad extensional (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 intensional, la mayoría de los lenguajes que admiten funciones de prueba para la igualdad utilizan la igualdad de referencia. A todas las funciones o cierres se les asigna un identificador único (normalmente la dirección del cuerpo de la función o el cierre) y la igualdad se decide sobre la base de la igualdad del identificador. Dos definiciones de función 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 tanto, no se admite en lenguajes puros , como Haskell.
Teoría de tipos
En teoría tipo , el tipo de funciones que aceptan valores de tipo A y los valores de tipo regresan B se puede escribir como A → B 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 a la descarga de supuestos hipotéticos y la aplicación de la función corresponde a la regla de inferencia del modus ponens . Además del caso habitual de las 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 teóricas de categorías de la programación, la disponibilidad de funciones de primera clase corresponde al supuesto de categoría cerrada . Por ejemplo, el cálculo lambda simplemente tipado corresponde al lenguaje interno de las categorías cerradas cartesianas .
Ayuda de idioma
Los lenguajes de programación funcional, como Scheme , ML , Haskell , F # y Scala , tienen funciones de primera clase. Cuando se diseñó Lisp , uno de los primeros lenguajes funcionales, no se entendieron correctamente 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 de Scheme y Common Lisp tienen funciones de primera clase de ámbito léxico.
Muchos lenguajes de secuencias de comandos, 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 de recolección de basura. La familia Algol ha permitido funciones anidadas y funciones de toma de orden superior como argumentos, pero no funciones de orden superior que devuelven funciones como resultados (excepto Algol 68, que permite esto). La razón de esto fue que no se sabía cómo tratar con variables no locales si se devolvía una función anidada como resultado (y Algol 68 produce errores de tiempo de ejecución en tales casos).
La familia C permitió tanto pasar funciones como argumentos como devolverlas como resultados, pero evitó 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, estos lenguajes generalmente no se consideran que 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 se han admitido en revisiones posteriores del lenguaje, incluida C # 2.0 y la extensión Blocks de Apple a 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 no recolectada como basura, se debe tener especial cuidado para que las variables no locales en las funciones se devuelvan como resultados (ver más abajo ).
Idioma | Funciones de orden superior | Funciones anidadas | Variables no locales | Notas | ||||
---|---|---|---|---|---|---|---|---|
Argumentos | Resultados | Llamado | Anónimo | Cierres | Aplicación parcial | |||
Familia Algol | ALGOL 60 | sí | No | sí | No | Hacia abajo | No | Tener tipos de funciones . |
ALGOL 68 | sí | Sí [8] | sí | sí | Hacia abajo [9] | No | ||
Pascal | sí | No | sí | No | Hacia abajo | No | ||
Ada | sí | No | sí | No | Hacia abajo | No | ||
Oberon | sí | Solo no anidado | sí | No | Hacia abajo | No | ||
Delphi | sí | sí | sí | 2009 | 2009 | No | ||
Familia C | C | sí | sí | No | No | No | No | Tiene punteros de función . |
C ++ | sí | sí | C ++ 11 [10] | C ++ 11 [11] | C ++ 11 [11] | C ++ 11 | Tiene punteros de función , objetos de función . (También, vea más abajo). Posibilidad de aplicación parcial explícita con | |
C# | sí | sí | 7 | 2.0 / 3.0 | 2.0 | 3,0 | Tiene delegados (2.0) y expresiones lambda (3.0). | |
C objetivo | sí | sí | Usando anónimo | 2.0 + Bloques [12] | 2.0 + bloques | No | Tiene punteros de función. | |
Java | sí | sí | Usando anónimo | Java 8 | Java 8 | No | Tiene clases internas anónimas . | |
Ir | sí | sí | Usando anónimo | sí | sí | Sí [13] | ||
Limbo | sí | sí | sí | sí | sí | No | ||
Newsqueak | sí | sí | sí | sí | sí | No | ||
Oxido | sí | sí | sí | sí | sí | Sí [14] | ||
Lenguajes funcionales | Ceceo | Sintaxis | Sintaxis | sí | sí | Lisp común | No | (vea abajo) |
Esquema | sí | sí | sí | sí | sí | SRFI 26 [15] | ||
Julia | sí | sí | sí | sí | sí | sí | ||
Clojure | sí | sí | sí | sí | sí | sí | ||
ML | sí | sí | sí | sí | sí | sí | ||
Haskell | sí | sí | sí | sí | sí | sí | ||
Scala | sí | sí | sí | sí | sí | sí | ||
F# | sí | sí | sí | sí | sí | sí | ||
OCaml | sí | sí | sí | sí | sí | sí | ||
Lenguajes de secuencias de comandos | Io | sí | sí | sí | sí | sí | No | |
JavaScript | sí | sí | sí | sí | sí | ECMAScript 5 | Aplicación parcial posible con código de usuario-tierra en ES3 [16] | |
Lua | sí | sí | sí | sí | sí | Sí [17] | ||
PHP | sí | sí | Usando anónimo | 5.3 | 5.3 | No | Aplicación parcial posible con código de usuario-tierra. | |
Perl | sí | sí | 6 | sí | sí | 6 [18] | ||
Pitón | sí | sí | sí | Expresiones solamente | sí | 2,5 [19] | (vea abajo) | |
Rubí | Sintaxis | Sintaxis | Sin ámbito | sí | sí | 1,9 | (vea abajo) | |
Otros idiomas | Fortran | sí | sí | sí | No | No | No | |
Arce | sí | sí | sí | sí | sí | No | ||
Mathematica | sí | sí | sí | sí | sí | No | ||
MATLAB | sí | sí | sí | Sí [20] | sí | sí | Aplicación parcial posible mediante generación automática de nuevas funciones. [21] | |
Charla | sí | sí | sí | sí | sí | Parcial | Posibilidad de aplicación parcial a través de la biblioteca. | |
Rápido | sí | sí | sí | sí | sí | sí |
- C ++
- Los cierres de C ++ 11 pueden capturar variables no locales mediante la construcción de copias, por referencia (sin extender su vida útil) o por construcción de movimientos (la variable vive tanto tiempo 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 no existir más 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 (ver referencias colgantes ). 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 Lisp de ámbito léxico admiten cierres. Las variantes de ámbito dinámico no admiten cierres o 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
function
debe usarse para recuperar la función como un valor:(function foo)
evalúa a un objeto de función.#'foo
existe como una notación abreviada. Para aplicar dicho objeto una función, se debe utilizar lafuncall
función:(funcall #'foo bar baz)
. - Pitón
- Aplicación parcial explícita
functools.partial
desde la versión 2.5 yoperator.methodcaller
desde la versión 2.6. - Rubí
- El identificador de una "función" regular en Ruby (que en realidad es un método) no se puede usar como valor ni pasar. Primero debe recuperarse en un objeto
Method
oProc
para usarlo como datos de primera clase. La sintaxis para llamar a un objeto de función de este tipo difiere de llamar a métodos regulares. - Las definiciones de métodos anidados no anidan realmente el alcance.
- Curry explícito con
[1]
.
Ver también
- Desfuncionalización
- eval
- Mensaje de primera clase
- Cálculo Kappa : un formalismo que excluye funciones de primera clase
- Prueba de hombre o niño
- Aplicación parcial
Notas
- ^ Abelson, Harold ; Sussman, Gerald Jay (1984). Estructura e interpretación de programas informáticos . MIT Press. Formular abstracciones con procedimientos de orden superior . ISBN 0-262-01077-1.
- ^ Pragmática del lenguaje de programación , por Michael Lee Scott, sección 11.2 "Programación funcional".
- ^ Roberto Ierusalimschy ; Luiz Henrique de Figueiredo; Waldemar Celes (2005). "La implementación de Lua 5.0" . Revista de Ciencias de la Computación Universal . 11 (7): 1159-1176. doi : 10.3217 / jucs-011-07-1159 .
- ^ a b 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 . Archivado desde el original el 16 de febrero de 2010.CS1 maint: bot: estado de URL original desconocido ( enlace ) (también en 2010-02-16
- ^ Joel Moisés . "La función de FUNCTION en LISP, o por qué el problema de FUNARG debería llamarse el problema del medio ambiente" . MIT AI Memo 199, 1970.
- ^ "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 del compilador GNU: funciones anidadas )
- ^ Andrew W. Appel (1995). "Intensional Igualdad; =) para Continuaciones" .
- ^ Tanenbaum, AS (1977). "Una comparación de PASCAL y Algol 68" . The Computer Journal . 21 (4): 319. doi : 10.1093 / comjnl / 21.4.316 .
- ^ http://python-history.blogspot.nl/2009/04/origins-of-pythons-functional-features.html?showComment=1243166621952#c702829329923892023
- ^ Funciones anidadas usando lambdas / cierres
- ↑ a b 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 ++
- ^ https://developer.apple.com/mac/library/documentation/Cocoa/Conceptual/Blocks/Articles/00_Introduction.html
- ^ "2 ejemplos en Go que puedes tener aplicación parcial" .
- ^ "aplicación_parcial" . Docs.rs . Consultado el 3 de noviembre de 2020 .
- ^ http://srfi.schemers.org/srfi-26/srfi-26.html
- ^ http://ejohn.org/blog/partial-functions-in-javascript/
- ^ 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.
- ^ http://perlgeek.de/blog-en/perl-5-to-6/28-currying.html
- ^ https://docs.python.org/whatsnew/2.5.html#pep-309-partial-function-application
- ^ http://www.mathworks.co.uk/help/matlab/matlab_prog/anonymous-functions.html
- ^ Evaluación de funciones parciales en MATLAB
- ^ Cierres en ZetaLisp Archivado el 19 de marzo de 2012 en la Wayback Machine.
Referencias
- Leonidas Fegaras . "Lenguajes funcionales y funciones de orden superior" . CSE5317 / CSE4305: Diseño y construcción de compiladores. Universidad de Texas en Arlington.
enlaces externos
- Funciones de primera clase en Rosetta Code .
- Funciones de orden superior en IBM developerWorks