miniaturadaimagem|117x117px|Lambda, símbolo comumente usado para denotar abstrações no cálculo lambda. Em ciência da computação, programação funcional é um padrão de programação que trata a computação como uma avaliação de funções matemáticas, evitando estados ou dados mutáveis. Ela enfatiza a aplicação de funções, em contraste da programação imperativa (que enfatiza mudanças no estado do programa). Enfatizando as expressões ao invés de comandos, as expressões são utilizados para cálculo de valores com dados imutáveis.
Uma função, neste sentido, pode ter ou não ter parâmetros (valores de entrada da função) e um simples valor de retorno (resultado da função). A definição de uma função descreve como a função será avaliada em termos de outras funções. Por exemplo, a função é definida em termos de funções de exponenciação e adição. Do mesmo modo, a linguagem deve oferecer funções básicas que não requerem definições adicionais.
A programação funcional trata as funções de forma em que estas possam ser passadas como parâmetro e valores para outras e funções e podendo ter o resultado armazenado em uma constante.
Linguagens de programação funcionais, especialmente as puramente funcionais, têm sido mais usadas academicamente que no desenvolvimento comercial de software. Entretanto, algumas linguagens notáveis usadas na indústria e no comércio incluem Erlang (aplicações concorrentes), R (estatística), OCaml (quantitative trading), Mathematica (matemática simbólica) J, K (análise financeira) e XSLT. Importantes influências na programação funcional foram o cálculo lambda, as linguagens de programação APL e Lisp, e mais recentemente ML, Haskell, OCaml, F# e Elixir.
História O cálculo lambda, desenvolvido na década de 1930 por Alonzo Church, é um sistema formal de computação construído a partir da aplicação de funções. Em 1937, Alan Turing provou que o cálculo lambda e as máquinas de Turing são modelos de computação equivalentes, mostrando que o cálculo lambda é Turing completo. O cálculo lambda forma a base de todas as linguagens de programação funcionais. Uma formulação teórica equivalente, a lógica combinatória, foi desenvolvida por Moses Schönfinkel e Haskell Curry nas décadas de 1920 e 1930.
Mais tarde, Church desenvolveu um sistema mais fraco, o cálculo lambda simplesmente tipado, que estendeu o cálculo lambda atribuindo um tipo de dados a todos os termos. Isto forma a base para a programação funcional tipada estaticamente.
A primeira linguagem de programação de alto nível funcional, Lisp, foi desenvolvida no final da década de 1950 para a série de computadores científicos IBM 700/7000 por John McCarthy enquanto estava no Instituto de Tecnologia de Massachusetts (MIT). As funções Lisp foram definidas usando a notação lambda de Church, estendida com uma construção de rótulo para permitir funções recursivas. O Lisp introduziu pela primeira vez muitas características paradigmáticas da programação funcional, embora os primeiros Lisps fossem linguagens multiparadigma e incorporassem suporte para vários estilos de programação à medida que novos paradigmas evoluíam. Dialetos posteriores, como Scheme e Clojure, e ramificações como Dylan e Julia, procuraram simplificar e racionalizar o Lisp em torno de um núcleo puramente funcional, enquanto o Common Lisp foi projetado para preservar e atualizar as características paradigmáticas dos numerosos dialetos mais antigos que substituiu.
A Linguagem de Processamento de Informação (IPL), de 1956, é por vezes citada como a primeira linguagem de programação funcional baseada em computador.O livro de memórias de Herbert A. Simon (1991), Models of My Life pp. 189-190 afirma que ele, Al Newell e Cliff Shaw são "...comumente considerados os pais do campo da inteligência artificial", por terem escrito o Logic Theorist, um programa que provava teoremas do Principia Mathematica automaticamente. Para o conseguir, tiveram de inventar uma linguagem e um paradigma que, vistos retrospetivamente, incorporam a programação funcional. É uma linguagem de estilo assembly para manipular listas de símbolos. Possui uma noção de gerador, que equivale a uma função que aceita uma função como argumento e, como é uma linguagem de baixo nível, o código pode ser visto como dados, pelo que a IPL pode ser considerada como tendo funções de ordem superior. No entanto, depende fortemente da estrutura de lista mutável e de características imperativas semelhantes.
Kenneth E. Iverson desenvolveu a linguagem APL no início da década de 1960, descrita no seu livro de 1962 A Programming Language (). A APL foi a principal influência na linguagem FP de John Backus. No início da década de 1990, Iverson e Roger Hui criaram a linguagem J. Em meados da década de 1990, Arthur Whitney, que já havia trabalhado com Iverson, criou a linguagem K, que é usada comercialmente nas indústrias financeiras juntamente com a sua descendente Q.
Em meados da década de 1960, Peter Landin inventou a máquina SECD, a primeira máquina abstrata para uma linguagem de programação funcional, descreveu uma correspondência entre o ALGOL 60 e o cálculo lambda, e propôs a linguagem de programação ISWIM.
John Backus apresentou a linguagem FP na sua palestra do Prêmio Turing de 1977 "Can Programming Be Liberated From the von Neumann Style? A Functional Style and its Algebra of Programs". Ele define os programas funcionais como sendo construídos de forma hierárquica por meio de "formas de combinação" que permitem uma "álgebra de programas"; na linguagem moderna, isto significa que os programas funcionais seguem o princípio da composicionalidade. O artigo de Backus popularizou a pesquisa em programação funcional, embora enfatizasse a programação ao nível da função em vez do estilo de cálculo lambda hoje associado à programação funcional.
A linguagem ML de 1973 foi criada por Robin Milner na Universidade de Edimburgo, e David Turner desenvolveu a linguagem SASL na Universidade de St Andrews. Também em Edimburgo, na década de 1970, Burstall e Darlington desenvolveram a linguagem funcional NPL.R.M. Burstall. Design considerations for a functional programming language. Invited paper, Proc. Infotech State of the Art Conf. "The Software Revolution", Copenhaga, 45–57 (1977) A NPL baseava-se nas Equações de Recursão de Kleene (ver Teorema da recursão de Kleene) e foi introduzida pela primeira vez no seu trabalho sobre transformação de programas.R.M. Burstall and J. Darlington. A transformation system for developing recursive programs. Journal of the Association for Computing Machinery 24(1):44–67 (1977) Burstall, MacQueen e Sannella incorporaram depois a verificação de tipos polimórfica do ML para produzir a linguagem Hope.R.M. Burstall, D.B. MacQueen and D.T. Sannella. HOPE: an experimental applicative language. Proceedings 1980 LISP Conference, Stanford, 136–143 (1980). O ML acabou por se desenvolver em vários dialetos, dos quais os mais comuns são agora o OCaml e o Standard ML.
Na década de 1970, Guy L. Steele e Gerald Jay Sussman desenvolveram a linguagem Scheme, conforme descrito nos Lambda Papers e no livro de 1985 Structure and Interpretation of Computer Programs. O Scheme foi o primeiro dialeto de Lisp a usar o escopo léxico e a exigir a otimização de chamadas de cauda, características que encorajam a programação funcional.
Na década de 1980, Per Martin-Löf desenvolveu a teoria dos tipos intuicionista (também chamada de teoria dos tipos construtiva), que associava programas funcionais a provas construtivas expressas como tipos dependentes. Isto levou a novas abordagens à demonstração interativa de teoremas e influenciou o desenvolvimento de linguagens de programação funcional subsequentes.
A linguagem funcional preguiçosa (lazy), Miranda, desenvolvida por David Turner, apareceu inicialmente em 1985 e teve uma forte influência sobre a linguagem Haskell. Sendo o Miranda proprietário, o Haskell começou com um consenso em 1987 para formar um padrão aberto para a investigação em programação funcional; os lançamentos de implementações têm ocorrido desde 1990.
Mais recentemente, tem encontrado uso em nichos como o CAD paramétrico na linguagem OpenSCAD, construída sobre o framework CGAL, embora a sua restrição à reatribuição de valores (todos os valores são tratados como constantes) tenha gerado confusão entre os utilizadores que não estão familiarizados com a programação funcional como conceito.
A programação funcional continua a ser utilizada em ambientes comerciais.
Conceitos Uma série de conceitosSean Tull - Monoidal Categories for Formal Concept Analysis. e paradigmas são específicos à programação funcional e, em geral, estranhos à programação imperativa (incluindo a programação orientada a objetos). No entanto, as linguagens de programação frequentemente atendem a vários paradigmas de programação, de modo que os programadores que usam linguagens "maioritariamente imperativas" podem ter utilizado alguns destes conceitos.
Funções de primeira classe e de ordem superior
As funções de ordem superior são funções que podem receber outras funções como argumentos ou retorná-las como resultados. No cálculo, um exemplo de uma função de ordem superior é o operador diferencial , que retorna a derivada de uma função .
As funções de ordem superior estão intimamente relacionadas com as funções de primeira classe, uma vez que tanto as funções de ordem superior como as funções de primeira classe permitem funções como argumentos e resultados de outras funções. A distinção entre as duas é sutil: "ordem superior" descreve um conceito matemático de funções que operam sobre outras funções, enquanto "primeira classe" é um termo da ciência da computação para entidades de linguagem de programação que não têm restrições quanto ao seu uso (assim, funções de primeira classe podem aparecer em qualquer lugar do programa onde outras entidades de primeira classe, como números, podem, incluindo como argumentos para outras funções e como os seus valores de retorno).
As funções de ordem superior permitem a aplicação parcial ou o currying, uma técnica que aplica uma função aos seus argumentos um de cada vez, com cada aplicação retornando uma nova função que aceita o argumento seguinte. Isto permite que um programador expresse de forma sucinta, por exemplo, a função sucessora como o operador de adição aplicado parcialmente ao número natural um.
Funções puras
As funções puras (ou expressões) não têm efeitos colaterais (na memória ou I/O). Isto significa que as funções puras têm várias propriedades úteis, muitas das quais podem ser usadas para otimizar o código: Se o resultado de uma expressão pura não for usado, ele pode ser removido sem afetar outras expressões. Se uma função pura for chamada com argumentos que não causam efeitos colaterais, o resultado é constante em relação a essa lista de argumentos (por vezes chamado de transparência referencial ou idempotência), ou seja, chamar a função pura novamente com os mesmos argumentos retorna o mesmo resultado. (Isto pode permitir otimizações de cache, como a memoização.) Se não houver dependência de dados entre duas expressões puras, a sua ordem pode ser revertida, ou podem ser realizadas em paralelo e não podem interferir uma com a outra (noutros termos, a avaliação de qualquer expressão pura é segura para threads/thread-safe). Se a linguagem no seu todo não permitir efeitos colaterais, então qualquer estratégia de avaliação pode ser usada; isto dá ao compilador a liberdade para reordenar ou combinar a avaliação de expressões num programa (por exemplo, usando a desflorestação/deforestation).