FP (abreviatura de programación funcional ) [2] es un lenguaje de programación creado por John Backus para apoyar el paradigma de programación a nivel de función [2] . Permite construir programas a partir de un conjunto de primitivas generalmente útiles y evitar variables nombradas (un estilo también llamado programación tácita o "sin puntos"). Fue fuertemente influenciado por APL desarrollado por Kenneth E. Iverson a principios de la década de 1960. [3]
El lenguaje FP fue presentado en el artículo de Backus del Premio Turing de 1977 , "¿Puede la programación liberarse del estilo von Neumann?", subtitulado "un estilo funcional y su álgebra de programas". El artículo despertó el interés en la investigación de la programación funcional, [4] lo que finalmente condujo a los lenguajes funcionales modernos, que se basan en gran medida en el paradigma del cálculo lambda , y no en el paradigma de nivel de función que Backus había esperado. En su artículo del Premio Turing, Backus describió en qué se diferencia el estilo FP:
Un sistema de programación funcional se basa en el uso de un conjunto fijo de formas de combinación llamadas formas funcionales. Estas, más definiciones simples, son el único medio de construir nuevas funciones a partir de las existentes; no utilizan variables ni reglas de sustitución y se convierten en las operaciones de un álgebra asociada de programas. Todas las funciones de un sistema de programación funcional son de un mismo tipo: asignan objetos a objetos y siempre toman un único argumento. [2]
El lenguaje FP en sí nunca encontró mucho uso fuera del ámbito académico. [5] En la década de 1980, Backus creó un lenguaje sucesor, FL, como un proyecto interno en IBM Research.
Los valores que los programas FP asignan entre sí forman un conjunto que está cerrado bajo formación de secuencia :
Si x 1 ,..., x n son valores , entonces la secuencia〈x 1 ,..., x n〉 también es un valor
Estos valores se pueden construir a partir de cualquier conjunto de átomos: booleanos, enteros, reales, caracteres, etc.:
booleano : { T , F } entero : {0,1,2,...,∞} carácter : {'a','b','c',...} símbolo : { x , y ,...}⊥ es el valor indefinido o bottom . Las secuencias conservan el bottom :
〈x 1 ,..., ⊥ ,..., x n〉 = ⊥
Los programas FP son funciones f que asignan cada una un único valor x a otro:
f : x representa el valor que resulta de aplicar la función f al valor x
Las funciones son primitivas (es decir, proporcionadas con el entorno FP) o se construyen a partir de las primitivas mediante operaciones de formación de programas (también llamadas funcionales ).
Un ejemplo de función primitiva es constante , que transforma un valor x en la función de valor constante x̄ . Las funciones son estrictas :
f : ⊥ = ⊥
Otro ejemplo de una función primitiva es la familia de funciones selectoras , denotada por 1 , 2 ,... donde:
i :〈 x 1 ,..., x n〉 = x i si 1 ≤ i ≤ n = ⊥ en caso contrario
A diferencia de las funciones primitivas, las funciones funcionales operan sobre otras funciones. Por ejemplo, algunas funciones tienen un valor unitario , como 0 para la suma y 1 para la multiplicación . La unidad funcional produce dicho valor cuando se aplica a una función f que tiene uno:
unidad + = 0 unidad × = 1 unidad foo = ⊥
Estas son las funciones principales de FP:
composición f ∘ g donde f ∘ g : x = f :( g : x )
construcción [ f 1 ,..., f n ] donde [ f 1 ,..., f n ]: x = 〈f 1 : x ,..., f n : x〉
condición ( h ⇒ f ; g ) donde ( h ⇒ f ; g ): x = f : x si h : x = T = g : x si h : x = F = ⊥ en caso contrario
aplicar-a-todos α f donde α f :〈x 1 ,..., x n〉 = 〈f : x 1 ,..., f : x n〉
insert-right / f donde / f :〈x〉 = x y / f :〈x 1 , x 2 ,..., x n〉 = f :〈x 1 ,/ f :〈x 2 ,..., x n〉〉 y / f :〈 〉 = unidad f
insert-left \ f donde \ f :〈x〉 = x y \ f :〈x 1 , x 2 ,..., x n〉 = f :〈\ f :〈x 1 ,..., x n-1〉, x n〉 y \ f :〈 〉 = unidad f
Además de construirse a partir de primitivos mediante funcionales, una función puede definirse recursivamente mediante una ecuación, siendo el tipo más simple:
f ≡ E f
donde E f es una expresión construida a partir de primitivas, otras funciones definidas y el propio símbolo de función f , utilizando funcionales.
FP84 es una extensión de FP para incluir secuencias infinitas , formas de combinación definidas por el programador (análogas a las que el propio Backus añadió a FL , su sucesor de FP) y evaluación perezosa . A diferencia de FFP, otra de las variaciones de FP de Backus, FP84 hace una clara distinción entre objetos y funciones: es decir, las últimas ya no están representadas por secuencias de las primeras. Las extensiones de FP84 se logran eliminando la restricción de FP de que la construcción de secuencias se aplique solo a objetos que no sean -⊥: en FP84, todo el universo de expresiones (incluidas aquellas cuyo significado es ⊥) está cerrado bajo la construcción de secuencias.
La semántica de FP84 está incorporada en un álgebra subyacente de programas, un conjunto de igualdades a nivel de función que pueden usarse para manipular y razonar sobre programas.