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 de lenguajes de programación también exigen 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 esenciales para la programación funcional , donde el uso de funciones de orden superior es una práctica habitual. Un ejemplo sencillo de función de orden superior es la función `map` , que recibe como argumentos una función y una lista, y devuelve la lista resultante de aplicar la función a cada elemento de la lista. Para que un lenguaje admita `map` , debe permitir 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 anónimas . Históricamente, estos problemas se denominaron problemas de funarg , nombre que proviene de argumento de función . ^{[ 5 ]} En los primeros lenguajes imperativos, estos problemas se evitaron al no admitir funciones como tipos de resultado (por ejemplo, ALGOL 60 , Pascal ) u omitir funciones anidadas y, por lo tanto, variables no locales (por ejemplo, C ). El lenguaje funcional Lisp adoptó el enfoque de ámbito 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 manejar referencias a funciones como cierres en lugar de punteros a funciones 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 ciertos 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 elementos de segunda clase ( C ).

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

void map ( int ( * f )( int ), int x [], size_t n ) { for ( int i = 0 ; i < n ; ++ i ) { x [ i ] = f ( x [ i ]); } }

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

int f ( int x ) { return 3 * x + 1 ; }int main () { int list [] = { 1 , 2 , 3 , 4 , 5 }; map ( f , list , 5 ); }

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

typedef struct { int ( * f )( int , int , int ); int a ; int b ; } Closure ;void map ( Closure * closure , int x [], size_t n ) { for ( int i = 0 ; i < n ; ++ i ) { x [ i ] = ( closure -> f )( closure -> a , closure -> 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 ; Closure closure = { f , a , b }; map ( & closure , l , 5 ); }

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

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 supuestos hipotéticos y la aplicación de funciones corresponde a la regla de inferencia 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 arreglos asociativos y estructuras de datos similares .

En las explicaciones de la programación basadas en la teoría de categorías , 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 cartesianas cerradas .

Los lenguajes de programación funcional, como Erlang , Scheme , ML , Haskell , F# y Scala , poseen funciones de primera clase. Cuando se diseñó Lisp , uno de los primeros lenguajes funcionales, no se comprendían del todo todos los aspectos de las funciones de primera clase, lo que dio como resultado funciones con ámbito dinámico. Los dialectos posteriores de Scheme y Common Lisp sí cuentan con funciones de primera clase con ámbito léxico.

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

En los lenguajes imperativos, es necesario distinguir entre Algol y sus descendientes, como Pascal, la familia C tradicional y las variantes modernas con recolección de basura. La familia Algol permitía funciones anidadas y funciones de orden superior que aceptaban funciones como argumentos, pero no funciones de orden superior que devolvieran funciones como resultado (excepto Algol 68, que sí lo permitía). Esto se debía a que se desconocía cómo manejar variables no locales si se devolvía una función anidada como resultado (y Algol 68 producía errores en tiempo de ejecución en tales casos).

La familia C permitía tanto pasar funciones como argumentos como devolverlas como resultados, pero evitaba problemas al no admitir funciones anidadas. (El compilador gcc las admite como extensión). Dado que la utilidad de devolver funciones reside 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 lenguajes con 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. Estas funciones a menudo solo han sido compatibles con revisiones posteriores del lenguaje, como C# 2.0 y la extensión Blocks de Apple para C, C++ y Objective-C. C++11 ha añadido compatibilidad con funciones anónimas y cierres, pero debido a la falta de recolección de basura en el lenguaje, se debe tener especial cuidado con las variables no locales en las funciones que se devuelven como resultados (véase más abajo).

C++

Las clausuras de C++11 pueden capturar variables no locales mediante construcción por copia, por referencia (sin extender su tiempo de vida) o mediante construcción por movimiento (la variable existe mientras exista la clausura). La primera opción es segura si se devuelve la clausura, pero requiere una copia y no se puede usar para modificar la variable original (que podría no existir en el momento en que se llama a la clausura). La segunda opción potencialmente evita una copia costosa y permite modificar la variable original, pero no es segura si se devuelve la clausura (véase referencias colgantes ). La tercera opción es segura si se devuelve la clausura y no requiere una copia, pero tampoco se puede usar para modificar la variable original.

Java

Las clausuras 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 adoptan el tipo inferido del contexto. Las referencias a métodos son limitadas. Para más detalles, consulte Función anónima §  Limitaciones de Java .

Ceceo

Las variantes de Lisp con ámbito léxico admiten cierres. Las variantes con ámbito dinámico no admiten cierres o necesitan una construcción especial para crearlos. ^{[ 22 ]}

En Common Lisp , el identificador de una función en el espacio de nombres de funciones no se puede usar como referencia a un valor de primera clase. functionSe debe usar el operador especial para recuperar la función como un valor: (function foo)se evalúa como un objeto de función. #'fooexiste como notación abreviada. Para aplicar dicho objeto de función, se debe usar 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" regular en Ruby (que en realidad es un método) no se puede usar como valor ni pasar como argumento. Primero debe recuperarse en un Methodobjeto Procpara poder usarse como dato de primera clase. La sintaxis para llamar a dicho objeto función difiere de la de llamar a métodos regulares.

Las definiciones de métodos anidados en realidad no anidan el ámbito.

Curry explícito con .

• Desfuncionalización
• evaluación
• Mensaje de primera clase
• Cálculo kappa : un formalismo que excluye las funciones de primera clase.
• Prueba de hombre o niño
• Aplicación parcial

• Leonidas Fegaras . "Lenguajes funcionales y funciones de orden superior" . CSE5317/CSE4305: Diseño y construcción de compiladores. Universidad de Texas en Arlington.

• Funciones de primera clase en Rosetta Code .
• Funciones de orden superior. Archivado el 12 de noviembre de 2019 en Wayback Machine de IBM developerWorks.