FP (lenguaje de programación)

FP (por programación funcional ) ^{[ 2 ]} es un lenguaje de programación creado por John Backus para dar soporte al paradigma de programación a nivel de función ^{[ 2 ]} . Permite construir programas a partir de un conjunto de primitivas de lenguaje de utilidad general y evitar variables con nombre (un estilo también llamado programación tácita o "sin puntos"). Estuvo fuertemente influenciado por APL , desarrollado por Kenneth E. Iverson a principios de la década de 1960. ^{[ 3 ]}

El lenguaje FP se introdujo en el artículo de Backus de 1977 , por el que recibió el Premio Turing , titulado "¿Puede liberarse la programación del estilo de von Neumann?: un estilo funcional y su álgebra de programas". El artículo despertó 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 a 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 FP se basa en el uso de un conjunto fijo de formas combinatorias llamadas formas funcionales. Estas, junto con definiciones simples, son el único medio para 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 de programas asociada. Todas las funciones de un sistema FP son de un solo tipo: mapean objetos sobre objetos y siempre toman un único argumento. ^{[ 2 ]}

FP se usó poco 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í conforman un conjunto que es cerrado bajo la formación de secuencias :

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 fondo . Las secuencias conservan el fondo :

〈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, se proporcionan con el entorno de programación funcional) 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 la constante , que transforma un valor x en la función de valor constante x̄ . Las funciones son estrictas :

f : ⊥ = ⊥

Otro ejemplo de 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, los 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 funcionalidades 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〉

insertar-derecha / 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

insertar-izquierda \ 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 primitivas 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 símbolo de función f por sí solo, utilizando funcionales.

FP84 es una extensión de FP que incluye secuencias infinitas , formas combinatorias definidas por el programador (análogas a las que Backus añadió a FL , su sucesor de FP) y evaluación perezosa . A diferencia de FFP, otra variación de FP creada por Backus, FP84 distingue claramente entre objetos y funciones: es decir, estas últimas ya no se representan mediante secuencias de los primeros. Las extensiones de FP84 se posibilitan 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 se materializa en un álgebra subyacente de programas, un conjunto de igualdades a nivel de función que pueden utilizarse para manipular programas y razonar sobre ellos.

• Sacrificar la simplicidad por la conveniencia: ¿Dónde está el límite? , John H. Williams y Edward L. Wimmers, Centro de Investigación IBM Almaden, Actas del Decimoquinto Simposio Anual ACM SIGACT-SIGPLAN sobre Principios de Lenguajes de Programación, San Diego, CA, enero de 1988.

• Intérprete de función plana escrito en Delphi – Lazarus
• Dirk Gerrits: Conferencia del Premio Turing (1977-1978) ff , en John W. Backus (Publicaciones)
• FP84 frente a FL: Sacrificar la simplicidad por la comodidad: ¿Dónde está el límite? JH William y EL Wimmers, 1988 (páginas 169-179)