FP (lenguaje de programación)

Las principales estructuras de datos del lenguaje son los valores de base y las secuencias:

• Si x₁,...,x_n son valores, también lo es la secuencia ⟨x₁,...,x_n⟩.

Estos valores se construyen a partir de cualquier conjunto de valores atómicos: booleanos, enteros, reales, caracteres, etc.

• booleanos  : {T, F}
• enteros  : {0,1,2,...,∞}
• caracteres  : {'a', 'b', 'c',...}
• símbolos  : {x, y,...}

El símbolo ⊥ representa el valor indefinido. Las secuencias preservan el valor indefinido:

•         ⟨x₁,...,⊥,...,x_n⟩ = ⊥

Los programas en FP son funciones f tales que cada una hace corresponder un valor x en otro :

• f:x representa el valor resultante de aplicar la función f a x.

Las funciones pueden estar predefinidas o ser definidas según las operaciones de construcción de programas o funcionales.

Algunas funciones tienen elemento neutro, tal es el caso del valor 0 para la suma, o 1 para la multiplicación. El funcional unit produce ese valor al ser aplicado a una función f que posea elemento neutro:

•         unit + = 0
•         unit × = 1
•         unit foo = ⊥ si foo no posee elemento neutro.

Los principales funcionales de FP son:

• constante x̄:
          x̄:y = x

para todo valor y (exceptuando el valor indefinido, ⊥, cuyo resultado es él mismo cualquiera sea la función aplicada).

• composición f°g:
          f°g:x = f:(g:x)

• construcción [f₁,...f_n]:
          [f₁,...f_n]:x = ⟨ f₁:x,...,f_n:x ⟩

• condición (h⇒f; g):
          (h⇒f; g):x = f:x si h:x = T,
          (h⇒f; g):x = g:x si h:x = F, y
          (h⇒f; g):x = ⊥ en caso contrario.

• aplicar a todos o map αf:         αf:⟨x₁,...,x_n⟩ = ⟨f:x₁,...,f:x_n⟩

• inserción a la izquierda /f:
          /f:⟨x⟩ = x,
          /f:⟨x₁,x₂,...,x_n⟩ = f:⟨x₁,/f:⟨x₂,...,x_n⟩⟩,
          /f:⟨ ⟩ = unit f

• inserción a la derecha \f:
          \f:⟨x⟩ = x,
          \f:⟨x₁,x₂,...,x_n⟩ = f:⟨\f:⟨x₁,...,x_n-1⟩,x_n⟩, y
          \f:⟨ ⟩ = unit f

Para introducir la recursión en el lenguaje se utilizan ecuaciones en donde la función que se define aparece tanto a izquierda como a derecha. La forma más sencilla es:

•         f ≡ Ef

en donde E'f es una expresión construida a partir de otras funciones y el símbolo f combinadas con los funcionales del lenguaje.

Por ejemplo, las funciones de selección, que se denotan en FP con los símbolos 1,2,... corresponden a la siguiente especificación:

•         1:⟨x₁,...,x_n⟩ = x₁
•         i:⟨x₁,...,x_n⟩
                  = x_i si 0 < i ≤ n
                  = ⊥ en caso contrario