FP (linguagem de programação)

FP (de Function Programming) é uma linguagem de programação criada por John Backus para suportar o paradigma da programação em nível funcional.[1] Isso permite a eliminação de variáveis nomeadas.

Os valores que os programas em FP mapeiam em outros compreendem um conjunto fechado em formação seqüencial:

Se x1,...,xn são valores, então a sequência 〈x1,...,xn〉 também é um valor 

Esses valores podem ser construídos a partir de qualquer conjunto de átomos: booleanos, inteiros, reais, caracteres, etc:

boolean   : {T, F} integer   : {0,1,2,...,∞} character : {'a','b','c',...} symbol    : {x,y,...} 

⊥ é o valor indefinido, ou base. Seqüências são preservadoras da base:

〈x1,...,⊥,...,xn〉  =  ⊥ 

Programas em FP são funções f, sendo que cada uma mapeia um valor único x em outro:

f:x representa o valor que resulta da aplicação da função f      ao valor x 

Funções podem ser primitivas (isto é, embutidas no ambiente de FP) ou construídas a partir de primitivas por operações de formação de programas (também chamadas Funcionais).

Um exemplo de função primitiva é constant, que transforma um valor x em uma função de valor constante x̄. Funções são estritas:[2]

f:⊥ = ⊥ 

Outro exemplo de uma função primitiva é o seletor de família de funções, denotado por 1,2,... onde:

1:〈x1,...,xn〉  =  x1 i:〈x1,...,xn〉  =  xi  se  0 < i ≤ n               =  ⊥   em caso contrário 

Em contraste com funções primitivas, funcionais operam em outras funções. Por exemplo, algumas funções têm um valor de unidade (elemento neutro), tal como 0 para adição e 1 para a multiplicação. A unidade funcional produz tal valor quando aplicada a uma função f que tem um:

unit +   =  0 unit ×   =  1 unit foo =  ⊥ 

Estes são os núcleos funcionais de FP:

composição  f°g        onde    f°g:x = f:(g:x) 

construção [f1,...fn] onde   [f1,...fn]:x =  〈f1:x,...,fn:x〉 

condição (h ⇒ f;g)    onde   (h ⇒ f;g):x   =  f:x   if   h:x  =  T                                              =  g:x   se   h:x  =  F                                              =  ⊥    caso contrário 

aplicação a todos  αf       onde   αf:〈x1,...,xn〉  = 〈f:x1,...,f:xn〉 

inserção à direita  /f       onde   /f:〈x〉             =  x                        e     /f:〈x1,x2,...,xn〉  =  f:〈x1,/f:〈x2,...,xn〉〉                        e     /f:〈 〉             =  unit f 

inserção à esquerda  \f       onde   \f:〈x〉             =  x                       e     \f:〈x1,x2,...,xn〉  =  f:〈\f:〈x1,...,xn-1〉,xn〉                       e     \f:〈 〉             =  unit f 

Além de ser construída a partir de funcionais primitivas, uma função pode ser definida recursivamente por uma equação, o tipo mais simples sendo:

f ≡ Ef 

onde E'f é uma expressão construída partir de primitivas, outras funções já definidas, e o próprio símbolo de função f, usando funcionais.

• FL (Linguagem sucessora de FP, também de Backus)
• John Backus

• Can Programming Be Liberated from the von Neumann Style? Aula de Backus ao receber o prêmio Turing award. (Disponível em The History of Computing Project)