Paradigma Funcional

Apresentação de LF1

Paradigma Funcional: modelo computacional

Entrada Programa Saída

Mapeamento (função) de valores de entrada em valores de saída

Ausência de estado e comandos (atribuição + controle)

Relação clara e explícita entre entrada e saída

Características gerais

Um programa consiste essencialmente de funções• Composição e decomposição suportados

— Modularidade

• Manipulado como uma expressão matemática

— Transformação de programas facilitada por transparência referencial

Estilo declarativo Conceitos sofisticados como

polimorfismo, funções de alta ordem e avaliação sob demanda

A Linguagem Funcional 1

Linguagem Funcional 1 - LF1

Estende LE2 com funções parametrizadas e recursivas (mas de primeira ordem)

O corpo de uma função é uma expressão e a aplicação da função a um argumento retorna um valor (aplicação também é uma expressão)

O contexto inclui dois componentes: • mapeamento de identificadores em valores • mapeamento de identificadores (nomes de

função) em definições de função Um programa é uma expressão

Apresentação da Linguagem Funcional 1 - LF1 http://www.cin.ufpe.br/~in1007

Explorando conceitos na LF1

LF1 é uma linguagem de programação! Sintaxe

• Valores, expressões e funções Semântica (operacional) e

implementação• Reescrita de termos (avaliação de

expressões) Universalidade

• Funções recursivas

Estratégias de Avaliação

Considere as seguintes funções let fun prod x y = if x == 0 then 0 else y + prod(x-1,y)

in let fun square x = prod(x,x) Como ocorre a avaliação de square(3+4) ?

Estratégias de Avaliação

square (3 + 4) => square (7) (+)innermost => prod(7, 7) (square)

=> 49 (prod)

square (3 + 4) => prod((3 + 4),(3 + 4)) (square)outermost => prod(7,(3 + 4)) (+)

=> prod(7,7) (+) => 49 (prod)

Qual estratégia adotar? Produzem o mesmo resultado? Considere a

expressão:

let fun f x = f(x) in let fun first y z = y in first(2,f(3)) Qual o resultado produzido neste caso?

Innermost versus Outermost ReductionPropriedade de Church-Rosser: Se um termo possuir uma forma

normal, esta será sempre obtida através de uma outermost reduction.

Se a redução usando a estratégia eager (ou qualquer outra combinação de avaliação entre eager e outermost) produzir um resultado, este será o mesmo produzido usando uma redução outermost.

Innermost versus Outermost Reduction Outermost Reduction --- Também

denominada:• Normal Order Reduction

Lazy Evaluation (Avaliação Preguiçosa)• Especialização de Outermost• O argumento é avaliado uma única vez• Referências subseqüentes ao argumento

são substituídas pelo valor (evitando reavaliação)

Innermost versus Outermost Reduction Innermost Reduction --- Também

denominada:• Applicative Order Reduction• Eager Evaluation

Em geral, avaliação Innermost é mais eficiente, mas a Outermost evita avaliar argumentos não utilizados

O mecanismo de avaliação de LF1 é innermost!

Exemplos de Projetos Realizados

Estender/modificar LF1 Escopo estático sem renomear variáveis

(usando Display em vez de Stack nos contextos)

Introdução de tipos explícitos e verificação Tipos recursivos (datatypes) Listas e verificação de tipos de listas (LF3) Casamento de padrão com equações

condicionais (LF3) Overloading Avaliação preguiçosa (Lazy) Aplicação parcial (LF2)

Escopo Estático O resultado da expressão:

Let var z = 2, fun f(x) = x + 1 in Let fun g(y) = f(y) + z in Let var z = 0, fun f(x) = x in g(1)

depende do bind de f e z usados na definição de g. Se o bind for com f e z (estático ou léxico) o resultado é 4, mas se for com f e z (dinâmico) o resultado é 1

Os interpretadores atuais das linguagens implementam escopo dinâmico

Referência: Acess links e displays em livros de compiladores

Introdução de Tipos Explícitos As BNFs das linguagens não

incluem declaração de variáveis com tipos

Os tipos são inferidos a partir do uso das variáveis

O objetivo deste projeto é adicionar declaração explícita de tipos e modificar o checaTipo() para LF1

Introdução de Tipos Explícitos A sintaxe para introdução de tipos

pode ser a usual:• Let var z : Int = 2, fun f : Int -> Int . f

x = x + 1 • ...

Inicialmente o escopo não inclui polimorfismo. Dependendo da complexidade poderá ser adicionado

Tipos Recursivos O objetivo é implementar os tipos

livres, ou datatypes, comuns em programação funcional.

O caso mais simples permite a definição de tipos enumerados• Exemplo: Type Cor ::= amarelo | azul |

preto ... Uma facilidade um pouco mais

elaborada é a união (disjunção de tipos)• Exemplo: Type IntBool ::= inteiro (Int) |

booleano (Bool)

Tipos Recursivos

Em geral, os tipos podem ser recursivos• Exemplo: Type Lista ::= vazia | cons

(Int x Lista) Há ainda a possibilidade de

parametrização, mas não faz parte do escopo do projeto

Listas e Typecheck de Listas Implementar a estrutura de dados listas

em LF1. A BNF deve ser estendida com ValorLista.

Com relação à sintaxe, usar [] para representar a lista vazia e [e1,e2,...,en] para uma lista de n elementos.

Incluir as seguintes operações sobre listas:• cons(e,L) recebe um elemento (e), uma lista

(L) e retorna uma lista com o elemento e acrescido no início de L

Listas e Typecheck de Listas

• head(L) recebe uma lista L e retorna o elemento que está na cabeça (elemento mais à esquerda) de L

• Tail(L) recebe uma lista L e retorna uma lista com todos os elementos de L exceto o head

• Concat(L1,L2) concatena (combina) os elementos de L1 e de L2 preservando a ordem (os de L1 aparecem primeiro)

Referência: Seções 2.4.1 e 13.1.2 do livro texto

Casamento de Padrão

Implementar casamento de padrão em LF1.

A BNF deve ser estendida de forma a permitir que declarações de funções possam ser escritas da seguinte forma:

• onde padrao_i é uma constante ou identificador, exp_i

• é uma expressão e cond_i é uma expressão booleana;

fun f padrao_1 = exp_1,[ if cond_1] | ... | f padrao_n = exp_n, [if cond_n]

Casamento de Padrão

Sugestão: converter as definições expressas em termos de padrões em expressões IfThenElse

Referência: Seção 13.1.1 do livro texto

Avaliação Preguiçosa Já explicado na transparência sobre

reduções innermost e outermost. O único operador lazy no interpretador

atual de LF1 é o if_then_else O objetivo do projeto é tornar toda

avaliação lazy Referência: Seção 13.1.4 do livro texto

Aplicação Parcial (LF2)

Aplicação parcial é permitir a aplicação de uma função a alguns (não necessariamente a todos os) argumentos.

Isto é permitido naturalmente em LF2 para funções definidas de forma currificada (curried) como será mostrado em sala.

O objetivo do projeto e´estender esta facilidade para funções não currificadas (uncurried)

Avaliação Parcial (LF2)

A idéia é permitir que uma função como • add(x,y) = x + y

possa ser aplicada a apenas um argumento. Ex. add 2

Referência:Funções Curry e Uncurry em livros de programação funcional

Outros projetos realizados Provador de teoremas para LF1 Concorrência (linguagem imperativa e

OO) via compartilhamento de variáveis

Concorrência via passagem de mensagens

Implementação de parte das linguagens usando outros padrões/plataforma (prog. funcional, prog. lógica, .net, ...)

Outros projetos realizados

Programação orientada a aspectos (extensão de projetos existentes)

Características de Java 1.5

Mais projetos sugeridos

Projetos Programação lógica Mobilidade para LI2 (Extensão de trabalho

anterior já realizado para concorrência) Linguagem para modelagem de agentes

(possivelmente com construtores de programação em lógica para modelar aprendizado) – continuação de trabalho anterior

Implementação de Técnicas de I/O para LF1/LF2

Projetos Integração de paradigmas (exemplo,

funcional e imperativo) com base em linguagens multi-paradigmas existentes

Comparação da abordagem do curso com outras propostas existentes

Leitura

Programming Language Concepts and Paradigms • Capítulo 5 (5.1.1)• Capítulo 13 (13.1.1, 13.1.2 e 13.1.4)

Introduction to Functional Programming• Seção 6.2