Programação Funcional

O qué isto?

Trata-se de um modo (paradigma) de programar que aborda o projeto de forma matemática e as funções passam a ser os agentes de transformação dos dados. De forma análoga às funções matemáticas que levam um determinado valor a outro domínio.

A coisa parece bem estranha, e até onde vi, não só parece mas é estranha de fato. Imagine uma função que não possa transformar os elementos externos à ela e que não deve “retornar” um valor , mas operar transformações sobre ele, de modo que ao voltar ao domínio original, o valor esteja intacto. Daí a pergunta: como fazer algo útil com isto ?

Alegam os defensores deste paradigma que quando uma função deve alterar os valores, são colocadas em outra categoria, inferior, que possuem a vil tarefa de se comunicar conosco, os imperfeitos humanos. Estas funções “baixas” são na realidade as que operam e modificam os valores, mas as tarefas de dizer o que será apontado pertencem às funções de primeira classe e de alta ordem.

Vamos combinar que isto parece regra de maçonaria… Por que, pra que, ninguém sabe, mas sabe-se que os trabalhos são feitos nesta esfera e o trabalho sujo fica relegado aos não iniciados.

Iniciando o meu estudo sobre o assunto

O meu encontro com o LISP, anteontem, foi meio confuso. Estava procurando uma solução para um problema recorrente com strings e acabei resolvendo com o recurso da recorrência. (sic)
Apesar de algumas críticas, na verdade ‘uma’ crítica recebida, não pretendo desanimar do meu objetivo em entender está confusão. Não vou ficar fazendo um monte de programinha teste (pois já fiz vários ontem) para saber que não dá para avançar com este assunto sem muito estudo.
Ok, tenho documentação farta aqui comigo. Inteligência e tempo, nem tanto. O que me interessa não é (ainda) a maestria, mas sair da minha completa ignorância sobre o assunto.

PF – Programação funcional

Pelo pouco contato que tive, percebi que a programação funcional, baseada no Cálculo Lambda, é a alma deste negócio de LISP e seus asseclas (Scheme, Haskell, Emacs-Lisp, floresta et.al.)

Mas estou apenas no início da minha pesquisa sobre este assunto, já que eu achei o conceito muito parecido com o paradigma M-V-C. Quando tentei criar algo usando paradigma M-V-C, eu me deparei com o seguinte problema: muitas camadas de funções eram necessárias para se levar o dado modificado ao usuário. Achei difícil fazer deste modo, mas vi que, com um pouco de trabalho realizado pelas funções, que se tornam coesas por excelência durante o processo, o conjunto obtido é bastente sólido e robusto, ou seja menos bugs.

Mas também notei que há dificuldade em se manter o paradigma ao pé da letra e acabamos pecando em algum ponto (ou mesmo desistindo) e voltando ao que os puristas chamam de programação imperativa, esta que nós mortais usamos.

Modo de programar: Funcional x Imperativo

Existem estes dois modos, antagônicos, de se programar. Vi isto no livro, confesso quem nem sabia, e ambos são agrupados em duas linhas de linguagens e obviamente tem distintos modos de se pensar no problema.
Ambos são da mesma época. No modo imperativo, destacam-se o Fortan, Pascal, C, sendo que o Fortran, surgiu pouco antes do LISP, em meados dos anos 50.

As linguagens imperativas ou orientadas a estados foram desenvolvida com a meta de se resolver problemas computacionais númericos, enquanto a pretensão de linguagens como LISP, funcionais, era (e ainda é) a de desenvolver algorítmos para manipulação de símbolos ou dados simbólicos a exemplo de listas, árvores, grafos etc.

A construção básica das linguagens imperativas é composta por comandos, os quais modificam o estado, por exemplo, via uma atribuição a=2 e pelas iterações tipo loop – for, while, do while etc. Desta maneira, as linguagens imperativas são poderosas no suporte de acesso aleatório ou randômico as estruturas de dados como os arrays, os quais são essenciais na computação numérica.

Nas linguagens puramente funcionais, entretanto, não existe a noção de estados ou mudanças de estado. Os conceitos básicos são:

  • aplicar uma função a um argumento – como na matemática, aplicada uma função a um valor, este é levado a outro domínio (não confundir com transformação, que seria uma alteração para outro estado). Ex. f(x) = x², a função leva, num plano cartesiano, o valor de x, no eixo das abcissas, para a sua potência quadrada no eixo das ordenadas. Veja que x não deixa de ser x, mas assume em y, uma nova dimensão, outro valor. IMHO isto é “muido doido”!
  • definição da função propriamente dita. Exemplo: f(x) = x²+1 ou recursivamente, f(x) = if x = 0 then 1 else x * f(x-1).

Também se nota que além de aplicar e definia funções, é necessário se ter as operações fundamentais sobre os tipos básicos – números naturais, booleanos, etc. – e as operações condicionais para as decisões nos casos (if, case, etc.). Além disto as linguagens funcionais fornecem meios para definição de tipos recursivos de dados, listando explicitamente seus construtores (consing é o termo usado). Exemplo: a definição de árvores binárias:

tree = empty() | mk_tree(tree, tree)

Tem o empty como sendo um construtor “zerário” sem descendentes enquanto mk_tree é um construtor binário que parte de duas árvores, t1 e t2 para construir uma nova árvore cujos descendentes esquerdo e direito são respectivamente t1 e t2. (Continua “muido doido isto”).

Daí se pode concluir que as linguagens funcionais suportam não somente definições recursivas mas também definições recursivas de “tipos de dados”. Sendo a grande vantagem aludida, sobre as linguagens imperativas, como o C ou Pascal onde tipos de dados recursivos precisam ser implementados por intermédio de ponteiros (e outras gambiarritas más), notáveis pela sua sensibilidade a más interpretações (tornam-se facilmente selvagens, quando são mal elaborados) e fonte garantida de bugs difíceis de ser exterminar.

Uma abordagem típica usada ao desenvolvermos programas imperativos é a criação de um fluxograma descrevendo visualmente (Aha! É daqui que vem os maléficos ‘Visuals’ et al) o comportamento dinâmico do programa. Logo se pode deduzir que a tarefa principal de um programa imperativo é organizar o caos, aka comportamentos dinâmicos complexos, o famigerado controle de fluxo.

Na programação funcional, por sua vez, o comportamento dinâmico do programa não precisa (sim eles odeiam loops, eu já vi isto) ser especificado explicitamente. Ao invés disto basta se definir a função a ser implementada. (Que beleza… e o bicho fica lá grudado olhando para mim sem fazer nada, uma lista e pronto). É claro que na prática estas funções definidas são justamente hierárquicas, i.e. baseadas numa cascata de funções pré definidas (me lembrei das carreiras de pedras de dominó). Daí o programa, o oposto de uma definição de função, (o vilão desta história, eu ja ví isto, pois ele lida com o trabalho sujo de fazer pelo menos uma transformação: a que dá o peteleco na primeira pedra), usualmente toma a forma de uma aplicação f(e1,…, en) e é “evaluated”, ou seja avaliado, pelo interpretador (putz num tem jeito de compilar esta merda depois? Ahhh! Em algumas implementações tem.). A atividade de programar em uma linguagem funcional consiste em definir funções (explicitamente ou recursivamente) sem se preocupar com os aspectos dinâmicos da execução, já que isto é tarefa do interpretador (java, ou melhor, jávi este papo antes…). Por fim, então devemos nos concentar no que e esquecer o como (que papo mais RH, gerencial este). Assim sendo quando se define as funções em programação funcional devemos grudar nas formas de definição (que melda é esta?) fornecidas pela linguagem e não lançar mão dos recurso ordinários da matemática corriqueira (pelo que entendi, fazer do jeito mais difícil, até que se torne fácil. Parece até filme oriental …. Mestre, por que não posso tomar atalhos?)

No andamento deste estudo vou continar traduzindo e comentando esta loucura, porque parece loucura este caminho zen, e investigando o por quê deste treco estar a tanto tempo no mercado e, apesar de não ver a luz do mercado, continuar existindo, pelo jeito com força total e avante.

O modelo e seus aspectos

Os aspectos centrais das lingagens funcionais, que devem ser investigados, em particular como se dá a sua interação, são

Modelo ---------- Interpretador
\ /
\ /
Lógica

ou


Semantica notacional ------------------ Semantica Operacional
\ /
\ Calculo de Verificação/

PCF – Programming Computable Functional

Primeiramente introduzimos a mais simples linguagem funcional – PCF – com os tipos básicos porém sem os tipos recursivos.

A semântica operacional do PCF será dada por uma indução definida pela relação de avaliação (aqui eu viajei completamente para fora da órbita)

E ↓ V

Especificando que expressões E são avaliadas com valore V ( onde V são expressões particulares que não podem ser mais avaliadas ) (no popular seria V expressões terminais?). Por exemplo se E ↓ V e E é um termo fechado do tipo nat de números naturais, então V será uma expressão da forma n, i.e. uma expressão canônica para o numero natural n (usualmente chamado de numeral)

Este último parágrafo e mais um monte de notações descritas na tese original me afastaram do objetivo, acabei procurando letrinhas matemáticas para compor as fórmulas e isto inviabiliza o resto da leitura da tese, que apesar de interessante, é pouco prática.

Buscando outra referência para estudo… Ok, encontrei a Bíblia deste assunto.

A execução de código em LISP é chamada de “evaluation” (valoração ou avaliação) pois a parte sendo executada normalmente resulta em um objeto de daods chamado de “value” (valor) produzido pelo código. O símbolo => (agora a seta deitou…) é usada em exemplos para indicar que houve “valoração”. Por exemplo;

(+ 4 5) => 9

Já o símblo -> é usado em exemplos para indicar uma expansão de macro. Por exemplo:

(push x v) -> (setf v (cons x v))

O que no fim das contas quer dizer que as duas formas de código executam a mesma coisa; a segunda parte do código é a definição do que a primeira faz. (Parece com o #define do C)

O símbolo ≡ (aqui entra outro daqueles) é usado em exemplos para indicar equivalência de código, assim

(gcd x (gcd y z)) ≡ (gcd (gcd x y) z)

Que foca mais o “efeito” do que na substituição literal, portanto o “efeito” da valoração de (gcd x (gcd y z)) é equivalente ao efeito da valoração de (gcd (gcd x y) z) ( … santa ambiguidade, Batman).

Scheme
O common lisp está para o schema assim como o c++ está para o c.

Schema parece ser bem mais simples do que o common lisp. Mais um livro on-line que dsimistificou algumas dúvidas.

S-expessions: todos os tipos de dados podem ser reunidos em um único e abrangente tipo de dados chamado de s-expression (s vem de símbolo, e não de sigma como eu pensei). Daí:
42, #\c,
(1 . 2)
#(a b c)
“Hello”
(quote xyz)
(string->number “16”)
(begin (display “Hello, World!”) (newline))
são todos s-expressions.

Form: os programas em lisp são s-expressions, pois todos os programas são dados. Portanto um simples caracter do conjunto de dados #\c é um programa ou como se chamam (e eu não tinha sacado) um form (isto deve vir de fórmula, e não de formulário como eu tinha pensado) sendo portanto, o termo form geralmente mais utilizado no lugar de programa.

Nota: este é um post em andamento, que inicialmente pensei em criar como página, mas pensei melhor e entendi que esta é uma classe de assuntos.
Portanto vou agrupar em links numa página especial sobre paradigmas

Referências:
Can Your Programming Language Do This? by Joel Spolsky
Functional Programming – Wikipedia
Mathematical Foundations of Functional Programming. Streicher, Thoms.
Digital Press – Lisp – 1990 – Common Lisp the Language, 2nd Edition – Steele, Guy L.
Símbolos matemáticos em html

Anúncios

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s