Programação em nível de função

Na ciência da computação, a programação em nível de função refere-se a um dos dois paradigmas de programação contrastantes identificados por John Backus em seu trabalho sobre programas como objetos matemáticos, sendo o outro a programação em nível de valor .

Em sua palestra no Prêmio Turing de 1977 , Backus expôs o que ele considerava ser a necessidade de mudar para uma filosofia diferente no design de linguagens de programação: [1]

As linguagens de programação parecem estar com problemas. Cada idioma sucessivo incorpora, com um pouco de limpeza, todos os recursos de seus predecessores e mais alguns. [...] Cada nova linguagem reivindica recursos novos e modernos... mas o fato é que poucas linguagens tornam a programação suficientemente barata ou mais confiável para justificar o custo de produzi-las e aprender a usá-las.

Ele projetou FP para ser a primeira linguagem de programação para suportar especificamente o estilo de programação em nível de função.

Um programa em nível de função é livre de variáveis ​​(cf. programação sem pontos ), uma vez que variáveis ​​de programa , que são essenciais em definições de nível de valor, não são necessárias em programas de nível de função.

Introdução

No estilo de programação em nível de função, um programa é construído diretamente a partir de programas fornecidos no início, combinando-os com operações ou funcionais de formação de programa . Assim, em contraste com a abordagem de nível de valor que aplica os programas dados a valores para formar uma sucessão de valores culminando no valor de resultado desejado, a abordagem de nível de função aplica operações de formação de programa aos programas dados para formar uma sucessão de programas culminando no programa de resultados desejado.

Como resultado, a abordagem de programação em nível de função convida ao estudo do espaço de programas sob operações de formação de programas , procurando derivar propriedades algébricas úteis dessas operações de formação de programas. A abordagem em nível de função oferece a possibilidade de tornar o conjunto de programas um espaço matemático, enfatizando as propriedades algébricas das operações de formação de programas sobre o espaço de programas .

Outra vantagem potencial da visualização em nível de função é a capacidade de usar apenas funções estritas e, portanto, ter semântica de baixo para cima, que é o tipo mais simples de todos. Ainda outra é a existência de definições de nível de função que não são a imagem levantada (isto é, elevada de um nível de valor inferior para um nível de função superior) de qualquer nível de valor existente: essas definições (geralmente concisas) de nível de função as definições representam um estilo mais poderoso de programação não disponível no nível de valor.

Contraste com a programação funcional

Quando Backus estudou e divulgou seu estilo de programação em nível de função, sua mensagem foi mal compreendida [2] como suporte às linguagens de estilo de programação funcional tradicional em vez de seu próprio FP e seu sucessor FL .

Backus chama programação funcional de programação aplicativa ; [ esclarecimento necessário ] sua programação em nível de função é um tipo específico e restrito.

Uma distinção fundamental das linguagens funcionais é que a linguagem de Backus tem a seguinte hierarquia de tipos:

  • átomos
  • funções, que levam átomos a átomos
  • Funções de ordem superior (que ele chama de "formas funcionais"), que levam uma ou duas funções para funções

...e a ​​única maneira de gerar novas funções é usar uma das formas funcionais, que são fixas: você não pode construir sua própria forma funcional (pelo menos não dentro do FP; você pode dentro do FFP (Formal FP) ) .

Essa restrição significa que as funções em FP são um módulo (gerado pelas funções internas) sobre a álgebra de formas funcionais e, portanto, tratáveis ​​algebricamente. Por exemplo, a questão geral da igualdade de duas funções é equivalente ao problema da parada e é indecidível, mas a igualdade de duas funções em FP é apenas igualdade na álgebra e, portanto (imagina Backus) mais fácil.

Ainda hoje, muitos usuários de linguagens de estilo lambda muitas vezes interpretam erroneamente a abordagem de nível de função de Backus como uma variante restritiva do estilo lambda, que é um estilo de nível de valor de fato . De fato, Backus não teria discordado da acusação 'restritiva': ele argumentou que era justamente devido a tais restrições que um espaço matemático bem formado poderia surgir, de maneira análoga à forma como a programação estruturada limita a programação a uma versão restrita de todas as possibilidades de fluxo de controle disponíveis em programas não estruturados simples e irrestritos .

O estilo livre de valores de FP está intimamente relacionado com a lógica equacional de uma categoria cartesiana fechada .

Idiomas de exemplo

A linguagem de programação em nível de função canônica é FP . Outros incluem FL e J .

Veja também

Referências

  1. ^ Backus, John (1978). "A programação pode ser liberada do estilo von Neumann?: Um estilo funcional e sua álgebra de programas" (PDF) . Comunicações da ACM . 21 (8): 613–641. doi : 10.1145/359576.359579 .
  2. ^ Hudak, Paul (1989). "Concepção, evolução e aplicação de linguagens de programação funcionais". ACM Computing Surveys . 21 (3): 359–411. doi : 10.1145/72551.72554. S2CID  207637854.

links externos

  • Programas de nível de função como objetos matemáticos de John Backus
  • Da semântica do nível de função à transformação e otimização do programa SpringerLink, consulte os pontos 1.2 e 1.3
  • Linguagens aplicativas fechadas, FP e FL, em John W. Backus (Publications) ou o original Programming Language Semantics and Closed Applicative Languages
  • Variáveis ​​de instância, uma saída para a abstinência variável