Sistema de programação funcional

O termo Sistema de Programação Funcional (abreviado sistema FP ) descreve um conceito de linguagens de programação funcional desenvolvidas por John W. Backus . Backus partiu da observação de que as linguagens de programação comuns representam os programas de computador como uma manipulação de dados serializados em pequena escala, pois são baseados no modelo de máquina de von Neumann. De acordo com Backus, isso resulta em dois problemas. Por outro lado, os programas de von Neumann são difíceis de paralelizar. Por outro lado, que é difícil argumentar formalmente sobre as propriedades dos programas de Von Neumann ou transformá-los. O Sistema de Programação Funcional aborda esses problemas construindo um programa a partir de uma composição . Ao fazer isso, grandes quantidades de dados estruturados são passados ​​de uma função para a outra, o que permite tecnicamente o processamento paralelo. Backus também considerou fazer dessa forma de trabalho a base de uma nova arquitetura de computador que tira proveito dessa possibilidade. ${\ displaystyle P}$${\ displaystyle P = F_ {n} \ circ F_ {n-1} \ circ F_ {n-2} \ circ .. \ circ F_ {1}}$

Em um discurso por ocasião da apresentação dos Prêmios Turing para Backus em 1977, este último apresentou a ideia de sistemas de FP. O título da palestra foi: A programação pode ser libertada do estilo de von Neumann? Um estilo funcional e sua álgebra de programas . Em outro ensaio, Backus decidiu usar o termo programação em nível de função .

Programa funcional para calcular o produto escalar

Com o cálculo do produto escalar, Backus dá um exemplo instrutivo para a aplicação do Sistema de Programação Funcional .

A função ("Produto Interno"), que determina o produto escalar de dois vetores, é composta pelo cálculo concatenado das três funções e (nesta ordem), que é expressa como uma composição de função da seguinte forma : ${\ displaystyle IP}$${\ displaystyle Trans, (\ alpha \ times)}$${\ displaystyle (/ +)}$

${\ displaystyle {\ begin {alinhado} IP & = (/ +) \ circ (\ alpha \ times) \ circ Trans \ end {alinhado}}}$

Aqui está uma função que transpõe uma matriz . No FP, por exemplo, esta relação é observada da seguinte forma para uma matriz : ${\ displaystyle Trans}$${\ displaystyle {\ bigl (} {\ begin {smallmatrix} 3 & 4 \\ 7 & 1 \\ - 1 & 0 \ end {smallmatrix}} {\ bigr)}}$

${\ displaystyle {\ begin {alinhado} Trans (<< 3.4>, <7.1>, <- 1.0 >>) & = << 3.7, -1>, <4.1.0 >> \ end {alinhado}}}$

Os símbolos e denotam funcionais . Estes assumem outras funções para criar novas funções. In der Form assume a função de multiplicação de dois dígitos e fornece uma função que se aplica a todos os elementos de uma lista de pares passada. O resultado do cálculo é então a lista dos produtos individuais. Em linguagens de programação modernas, isso é geralmente chamado de funcional . Backus os nomeia também . ${\ displaystyle \ alpha}$${\ displaystyle /}$${\ displaystyle (\ alpha \ times)}$${\ displaystyle \ alpha}$${\ displaystyle \ times}$${\ displaystyle \ times}$${\ displaystyle \ alpha}$mapApplyToAll

A função finalmente corresponde aproximadamente à função ou na programação funcional usual. Backus a nomeia , o que significa que a expressão representa uma função que insere a operação entre dois elementos em uma determinada lista . Então isso se aplica . ${\ displaystyle /}$reducefoldInsert${\ displaystyle (/ +)}$${\ displaystyle +}$${\ displaystyle (/ +) (<2,3,4>) = 2 + 3 + 4 = 9}$

O cálculo da função de produto escalar é aplicado aos dois vetores e pode então ser entendido da seguinte forma: ${\ displaystyle IP}$${\ displaystyle <1,2,3>}$${\ displaystyle <6,5,4>}$

${\ displaystyle {\ begin {alinhados} & IP: << 1,2,3>, <6,5,4 >> \\ & = (/ +) \ circ (\ alpha \ times) \ circ trans: < <1,2,3>, <6,5,4 >> \\ & = (/ +) \ circ (\ alpha \ vezes) :( trans: << 1,2,3>, <6,5, 4 >>) \\ & = (/ +): ((\ alpha \ times): << 1,6>, <2,5>, <3,4 >>) \\ & = (/ +): <\ times: <1,6>, \ times: <2,5>, \ times: <3,4 >> \\ & = (/ +): <6,10,12> \\ & = +: <6, +: <10,12 >> \\ & = 28 \ end {alinhado}}}$

O processo aritmético, portanto, representa um pipeline de processamento sem um estado interno, que converte a entrada em saída em três etapas de trabalho separadas. As próprias etapas de trabalho podem ser paralelizadas em diferentes graus. Também seria possível criar um pipeline de hardware para o programa . ${\ displaystyle IP}$

Notações no sistema FP

Backus usa uma notação que é vagamente baseada em convenções matemáticas e a complementa com as expressões condicionais de McCarthy e uma representação recursiva para loops WHILE. É fundamental que cada entidade represente uma função e, portanto, seja compatível com o operador de composição . ${\ displaystyle \ circ}$

Números como seletores

A linguagem de programação vetorial APL teve uma influência decisiva no sistema de programação funcional baseado em Combinator de John Backus, que funciona sem uma lista de variáveis ​​lambda ; em vez disso, os seletores (números) são usados ​​para escolher valores de uma sequência.

1:<x1,...,xn> → x1i:<x1,...,xi,...,xn> → xi

Número fixo de combinadores / formas funcionais

Combinando ...	... Forma
aplicativo	f : x	= f (x)
composição	(f o g): x	= f (g (x))
construção	[ f 1 , f 2 , ... , f n ]  : x	= < f 1 : x , f 2 : x , ... , f n : x >
doença	(p → f ; g): x	= se p: x = T então f: x caso contrário se p: x = F então g: x caso contrário ⊥
constante	~ x: y	= se y = ⊥ então ⊥ caso contrário x
Inserir	( / f): < x 1 , x 2 , ..., x n >	= f: < x 1 , f: < x 2 , ... f: < x n-1 , x n >>>
Aplicar a todos	( α f): < x 1 , x 2 , ..., x n >	= < f: x 1 , f: x 2 , ..., f: x n >
Binário para Unário	bu fx
Loop while	( enquanto pf): x	= se p: x = T então ( enquanto pf) : (f : x) caso contrário, se p: x = F então x caso contrário ⊥

e a definição de funções monádicas:

Def Name ≡ Term

Com ⊥ Backus significava o valor “inferior”, um valor como “indefinido” ou “exceção”. T e F são os valores para "verdadeiro" e "falso".

Desenvolvimento adicional de sistemas de FP

Uma equipe formada por John Backus, John Williams e Edward Wimmers desenvolveu o sucessor FL (Function-Level Programming) no IBM Almaden Research Center em 1989 . Com este conceito, deve-se ser capaz de reorganizar programas tão confortavelmente quanto se pode reorganizar equações em matemática, para isso a transparência referencial deve ser garantida. Isso deve servir a uma nova dimensão de otimização do programa (EFL). Com a FL, Backus queria transformar a "então ciência da computação" em uma disciplina de engenharia. Novamente, alguns desenvolvimentos adicionais de FL são J (aplicativo como APL) e PLaSM, uma linguagem de programação para geometria.

Implementações de FP

• PF INTERATIVO, página de ajuda para este
• Compilador FP que se compila em C, repo em
• Intérprete Fp em Lisp
• Trivialidades FP, repo FP para
• Plasm ( P rogramming La nguage for S olid M odeling), uma linguagem de programação funcional para uso em CAD , que é desenvolvida na Universidade Roma Tre .

Veja também

• Linguagem de programação algébrica

literatura

• Wolfram-Manfred Lippe : Programação Funcional e Aplicativa: Fundamentos, Linguagens, Técnicas de Implementação . 1ª edição. Springer , Berlin 2009, ISBN 978-3-540-89091-1 ( visualização limitada na pesquisa de livros do Google). 
• Alberto Paoluzzi e a: Programação Geométrica para Projeto Auxiliado por Computador . 1ª edição. Wiley , Chichester 2003, ISBN 978-0-471-89942-6 ( visualização limitada na Pesquisa de Livros do Google). 

Evidência individual

1. ↑ Lippe 2009, p. 73
2. ↑ A programação pode ser liberada do estilo von Neumann? Um estilo funcional e sua álgebra de programas Stanford University, 1978 (PDF; 2,87 MB)
3. ↑ Programas de nível de função como objetos matemáticos (PDF)
4. ↑ PF INTERATIVO
5. ↑ INTERACTVE FP - Ajuda
6. ↑ Furry Paws , um compilador FP
7. ↑ fp-interpreter-in-lisp
8. ↑ Intérprete FP, criado em Delphi
9. ↑ Linguagem funcional PLaSM para computação com geometria. Alberto Paoluzzi ( Universidade de Roma III ), acessado em 27 de novembro de 2010 . 

Links da web

• Críticas ao ensaio de Backus, de Edsger W. Dijkstra (PDF; 143 kB)
• John Backus: Programação em nível de função e linguagem FL , 1987 (vídeo)
• O Projeto FL: Desenho de uma linguagem funcional (PDF; 315 kB)
• Manual de linguagem FL, partes 1 e 2 (PDF; 20 MB)
• Introdução a FL e PLaSM (PDF)
• FP (Inglês)
• Scripts para sistemas FP