Implementação de
Linguagens Funcionais
Eudes Raphael
Thiago Arrais
Roteiro
Arquitetura
 Lambda-calculus
 Lambda Lifting
 Redução de Grafos
 Máquina de Templates
 Referências

Arquitetura
Lambda-calculus
Modelo teórico sob o qual se
baseiam a semântica e a
implementação de linguagens
funcionais.
 lx. E : É uma função que assume um
argumento x e retorna uma
expressão E (que pode depender de
x)

Lambda-calculus
Bound X free variables
 Seja lx.x (lz.x y z) (y z)

x é bound da abstração mais externa
 y não é bound para ambas abstrações
 Z é bound apenas na abstração mais
interna


Uma abstração l sem variáveis livres
é um combinator
Lambda-calculus
b – conversion: Operação de substituição
bidirecional
 (lx.E) E’ bE[E’/x]
 Reduz a aplicação de uma abstração
l

Lambda-calculus

Redex: Reducible Expression
ou um uma aplicação de uma abstração
 ou uma aplicação de uma função predefinida


Uma expressão l está na forma
normal se ela não possui nenhum
redex
Lambda-calculus
Avaliação: Seqüência de reduções
 Applicative-order reduction



Eager Evaluation
Normal-order reduction
Lazy Evaluation
 Uma expressão está na WHNF Quando
não mais é possível realizar reduções
na Normal-order reduction

Lambda-calculus

Strict functions: precisam de fato
do valor de seus argumentos


g é restrita ao segundo argumento se e
somente se g x ^ z = ^
Lazy
functions:
Podem
ser
avaliadas
na
falta
de
algum
argumento
Lambda-lifting
Consiste em técnica de transformar
programas funcionais com definições
locais, em um programa contendo
apenas definições globais
 Cada ocorrência de uma variável
livre no corpo da função é
substituída pela adição de um novo
parâmetro formal

Lambda-lifting
Permite full laziness, pela
maximização do compartilhamento
de definições
 Evita a criação de closures em
tempo de execução

Super-combinadores



Free expression é uma expressão que
não contém nenhuma instância de uma
bound variable
Maximal free variables (mfv) são
expressões livres que não contém
nenhuma outra expressão livre.
Super-combinadores são funções que
abstraem suas mfvs como parâmetros
Super-combinadores

Exemplo:
Redução de Grafos
Núcleo da execução de um
programa funcional
 Consiste em substituir uma
expressão redutível (redex) por sua
forma reduzida
 Lambda-Calculus


abe h-conversão
Redução de Grafos
Expressões representadas em forma
de grafo
 Cada nó é fisicamente representado
em células, que podem ter tamanho
fixo ou variável
 Valores Boxed e Unboxed

Redução de Grafos - Algoritmo
Até que não haja mais nenhum redex
(forma normal)
1. Selecione o redex mais externo (Normalorder reduction)
2. Reduza-o (abe h-reduction)
3. Substitua o redex pelo resultado da
redução
Obs: Se uma função for restrita a algum
argumento, ele pode ser avaliado antes
Redução de aplicações


b- Reduction
1.Função definida pelo usuário
(supercombinador)


Substituir o nó de aplicação pelo corpo da
função, e os parâmetros formais por
ponteiros para os argumentos
2.Função pré-definida (primitivas)


Se os argumentos não estiverem reduzidos,
reduzir
Avaliar a função
Redução de Grafos 
Compartilhamento de cópias
 Se dois grafos são semelhantes, apenas
uma cópia é preciso.
 Aumenta o compartilhamento no grafo
 Uma implementação que maximiza o
compartilhamento é dita Fully Lazy
 Garbage Collection se faz necessária
Redução de Grafos – Um exemplo
square x = x * x ;
main = square (square 3)
main
1
@
/ \
square @
/ \
square 3
Redução de Grafos – Um exemplo
@!
/ \
square @
/ \
square 3
1
@!
/ \
@
\
/ \__ @
*
/ \
square
3
Redução de Grafos – Um exemplo
@
/ \
@
\
/ \__ @
*
/ \
square
3
2.1
@
/ \
@
\
/ \__ @!
*
/ \
square
3
@
/ \
@
\
/ \__ @!
*
/ \
@
\
/ \__ 3
*
1
Redução de Grafos – Um exemplo
@
/ \
@
\
/ \__ @!
*
/ \
@
\
/ \__ 3
*
@!
/ \
@
\
/ \__ 9
2.2
*
2.2
81
Redução de Grafos 
Função projetora: é uma função cujo
corpo é apenas uma variável
 Causam perda de compartilhamento
 Seja head [f E]
 Substituir o nó faz com que a aplicação
(f E) seja duplicada
 Solução: Nó de indireção (ponteiro para
outro nó)
Redução de Grafos 
Nós de indereção são ineficientes
 Deve ser testada indireção toda vez
que uma operação for realizada
 Pode formar correntes de indireção
 Solução: Boa parte dos argumentos
pode ser avaliada antes da aplicação da
função projetora
Máquina de Templates

Máquina de estados
Stack: Pilha de endereços, relativos ao
heap
 Dump: Pilha de pilhas
 Heap: Lista de nós identificadas por
endereços
 Globals: Lista os endereços dos
supercombinadores

Máquina de Templates

Transições de Estado

Aplicação
T1

Instanciação
T2
Máquina de Templates

Estrutura principal


> runProg = showResults . eval . compile . Parse
Compile

Transforma um programa em um
estado inicial
Máquina de Templates

T1
T2
Estágio de Avaliação
> apStep :: TiState -> Addr -> Addr -> TiState
> apStep (stack, dump, heap, globals, stats) a1 a2
> = (a1 : stack, dump, heap, globals, stats)
> scStep :: TiState -> Name -> [Name] -> CoreExpr -> TiState
> scStep (stack, dump, heap, globals, stats) sc_name arg_names body
> = (new_stack, dump, new_heap, globals, stats)
>
where
>
new_stack = result_addr : (drop (length arg_names+1) stack)
>
>
(new_heap, result_addr) = instantiate body heap env
>
env = arg_bindings ++ globals
>
arg_bindings = zip2 arg_names (getargs heap stack)
Máquina de Templates

Instanciação de supercombinador
Função instantiate
 Consiste em percorrer o nó do corpo do
supercombinador, substituindo os
parâmetros formais pelos argumentos

Máquina de Templates
Atualização
 Para evitar avaliar uma expressão
mais de uma vez, adiciona-se um
novo tipo de nó: um nó de indireção

• > NInd a1

É preciso adicionar uma nova transição
T3
Máquina de Templates

Atualização

Ao avaliar-se um supercombinador,
substitui-se o nó no heap por um nó de
indireção
T2

Avaliações subseqüentes só precisam
seguir o nó de indireção
Garbage Collection

Mark-scan collection
Marcar os nós acessíveis
 Escanear todo o heap, eliminando nós
não marcados

Referências

Jones, S. e Lester, D. Implementing Functional
Languages: a tutorial


http://research.microsoft.com/Users/simonpj/Papers/pjlester-book/
Functional Programming - UWA

http://undergraduate.csse.uwa.edu.au/courses/230.301/lect
ureNotes/