En informática , se dice que un lenguaje de programación tiene funciones de primera clase si trata a las 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 de lenguajes 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 map , 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 problemas se denominaban problemas funarg , el nombre proviene de "argumento de función". [5] En los primeros lenguajes imperativos, estos problemas se evitaban ya sea no admitiendo 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 primer lenguaje funcional Lisp adoptó el enfoque del 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 alcance léxico se introdujo en Scheme y requiere el manejo de 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.
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 ciudadanos de segunda clase ( C ).
En los lenguajes donde las funciones son ciudadanos de primera clase, las funciones pueden pasarse como argumentos a otras funciones de la misma manera que otros valores (una función que toma otra función como argumento se denomina función de orden superior). En el lenguaje Haskell :
mapa :: ( a -> b ) -> [ a ] -> [ b ] mapa f [] = [] mapa f ( x : xs ) = f x : mapa f xs Los lenguajes en los que las funciones no son de primera clase suelen permitir escribir funciones de orden superior mediante el uso de características como punteros de función o delegados . En el lenguaje C :
void map ( int ( * f )( int ), int x [], tamaño_t n ) { para ( int i = 0 ; i < n ; i ++ ) x [ i ] = f ( x [ i ]); } Hay varias 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 el ejemplo de C opere en listas enlazadas lo habría hecho innecesariamente complejo. Esto también explica el hecho de que la función de C necesita un parámetro adicional (que proporciona el tamaño de la matriz). La función de 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 la anterior se deja intacta). El ejemplo de Haskell usa recursión 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 el ejemplo de Haskell podría haberse expresado fácilmente en términos de un pliegue y el ejemplo de C en términos de recursión. Finalmente, la función de Haskell tiene un tipo polimórfico , ya que C no lo admite, hemos fijado todas las variables de tipo en el tipo constante int.
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 lenguaje que no admite funciones anónimas, debemos vincularlo a un nombre:
int f ( int x ) { devolver 3 * x + 1 ; } int main () { int lista [] = { 1 , 2 , 3 , 4 , 5 }; mapa ( f , lista , 5 ); } Una vez que tenemos funciones anónimas o anidadas, se vuelve 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 simples punteros de función, ya no podemos saber cómo se le debe pasar el valor que está fuera del cuerpo de la función y, por eso, es necesario crear un cierre manualmente. Por lo tanto, no podemos hablar aquí de funciones de "primera clase".
typedef struct { int ( * f )( int , int , int ); int a ; int b ; } cierre_t ; void map ( 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 ; } 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 ); } Tenga en cuenta también que mapahora está especializado en funciones que hacen referencia a dos ints fuera de su entorno. Esto se puede configurar de forma más general, pero requiere más código repetitivo . Si fhubiera sido una función anidada , igualmente nos habríamos encontrado con el mismo problema y esta es la razón por la que no se admiten en C. [6]
Cuando devolvemos una función, en realidad estamos devolviendo su cierre. En el ejemplo de C, cualquier variable local capturada por el cierre quedará fuera del alcance una vez que regresemos de la función que crea el cierre. Forzar el cierre en un punto posterior dará como resultado un comportamiento indefinido, posiblemente corrompiendo la pila. Esto se conoce como el problema de funarg ascendente .
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 [ map ( \ x -> a * x + b ), map ( \ x -> b * x + a )] Como se puede comprobar la igualdad de la mayoría de los literales y valores, es natural preguntarse si un lenguaje de programación puede soportar la comprobación de la igualdad de funciones. Si se analiza más a fondo, esta cuestión parece más difícil y hay que distinguir entre varios tipos de igualdad de funciones: [7]
En la teoría de tipos , el tipo de funciones que aceptan valores de tipo A y devuelven valores de tipo B se puede escribir como A → B o B A . En la correspondencia de Curry-Howard , los tipos de funciones están relacionados con la implicación lógica ; la abstracción lambda corresponde a la descarga de suposiciones hipotéticas y la aplicación de la función corresponde a la regla de inferencia del 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 teorías de categorías de programación, la disponibilidad de funciones de primera clase corresponde al supuesto de categoría cerrada . Por ejemplo, el cálculo lambda de tipos simples corresponde al lenguaje interno de las categorías cartesianas cerradas .
Los lenguajes de programación funcional, 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 comprendían adecuadamente todos los aspectos de las funciones de primera clase, lo que dio lugar a que las funciones tuvieran un alcance dinámico. Los dialectos posteriores de Scheme y Common Lisp sí tienen funciones de primera clase con alcance léxico.
Muchos lenguajes de script, incluidos Perl , Python , PHP , Lua , Tcl /Tk, JavaScript e Io , tienen funciones de primera clase.
En el caso de los lenguajes imperativos, es necesario distinguir entre Algol y sus descendientes, como Pascal, la familia C tradicional y las variantes modernas que utilizan la recolección de basura. La familia Algol ha permitido funciones anidadas y funciones de orden superior que toman funciones 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 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 permitía pasar funciones como argumentos y devolverlas como resultados, pero evitaba los problemas al no admitir funciones anidadas (el compilador gcc las 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 funciones de primera clase.
Los lenguajes imperativos modernos suelen admitir la recolección de basura, lo que hace posible la implementación de funciones de primera clase. Las funciones de primera clase a menudo solo se han admitido en revisiones posteriores del lenguaje, incluidas C# 2.0 y la extensión Blocks de Apple para C, C++ y Objective-C. C++11 ha agregado compatibilidad con 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 devuelven como resultados (ver a continuación).
functionSe debe utilizar el operador especial para recuperar la función como valor: (function foo)evalúa a 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).functools.partialdesde la versión 2.5, y operator.methodcallerdesde la versión 2.6.Methodor Procpara usarlo como dato de primera clase. La sintaxis para llamar a un objeto de función de este tipo difiere de la de llamar a métodos regulares.[1].{{cite journal}}: CS1 maint: bot: estado de URL original desconocido ( enlace )(también el 16 de febrero de 2010)