Resenha do Artigo
Implementing lazy functional
languages on stock hardware: the
Spineless Tagless G-Machine (Parte I)
(Simon L. Peyton Jones}
Monique L. B. Monteiro
{mlbm}@cin.ufpe.br
Essência do Artigo
• Propor um modelo otimizado e simplificado
de compilação de linguagens funcionais
• Expor em detalhes o funcionamento da
Spineless Tagless G-Machine
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Relevância para o HS.NET
• Entender o modelo básico de compilação
utilizado pelo GHC
• Promover maior intimidade com a compilação
de linguagens funcionais em geral
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
STG – Visão geral
• Máquina abstrata projetada para linguagens
funcionais não estritas de alta ordem
• Utiliza uma linguagem intermediária
funcional – STG Language
• C como linguagem alvo
• Eficiente
• Linguagens fortemente tipadas, puramente
funcionais e lazy
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Compilação de Haskell
Várias
transformações...
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Alternativas de
Implementação
Implementação
• Combinação de várias outras técnicas
• Origens em técnicas de redução de grafos
• Representação de
–
–
–
–
–
Funções-valor
Dados
Expressões não avaliadas
Aplicação de funções
Estruturas case em dados de tipos algébricos
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Closures
• Objetos do heap
– Head normal form (ou valores)
– Objetos não avaliados (thunks)
• Head Normal form
– Função-valor
– Dados
• Normal Form
– Não contém thunks
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Closures
Funções
- Computação “suspensa”
- Bloco de código compartilhado
- Denominado closure
- Para entrar na closure: ponteiro de ambiente aponta
para a mesma
Variáveis Livres
Código
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Thunks
•
•
•
•
•
Computação “suspensa”
Representados por closures
Atualizados na primeira avaliação
Não são aplicações parciais
Não são construtores
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Atualizações
• Naïve reduction model
– Atualiza após cada redução
– Um thunk pode ser atualizado com outro:
atualização repetida
• Cell model (Modelo de célula)
–
–
–
–
Flag de status
Já foi avaliado: retorna o valor
Não foi avaliado: “entra”, calcula o valor
Código chamador atualiza o valor e a flag
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Atualizações
• Self-updating model (Auto-atualização)
– Utilizado pela STG
– Atualização feita pelo código interno ao thunk
– Valor é computado e atualizado OU simplesmente
retornado
– Valor pode ser representado por indireção
– Não há testes
– Deve possuir ponteiro para código
• Nem sempre a atualização precisa ser feita!
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Atualização: Exemplo
• Modelo de auto-atualização
Antes de atualizar
Variáveis
Livres
Código
Depois de atualizar (valor grande)
Depois de atualizar (valor pequeno)
Valor
Head
Código de indireção
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Código do Cons
Tail
Atualização: Exemplo
• Modelo de célula
Antes de atualizar
0
Depois de atualizar
1
Código
Variáveis
Livres
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Valor
Aplicação de Funções
• Currificação
f x y = x
– Tipo de f pode ser a -> (b -> a)
(f 1 2) = ((f 1) 2)
(map (f 1) xs)
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Aplicação da Funções
• Modelo eval-apply
–
–
–
–
Funcao é avaliada
Argumentos são avaliados
Valor-função é aplicado ao argumento
Avaliação trivial para funções conhecidas
• Modelo push-enter (STG, G-machine, TIM)
–
–
–
–
Baseado em redução de grafo
Coloca-se o argumento na pilha de avaliação
Tail-call (ou entra) a função
Não há “return”
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Modelo push-enter
• Adequado para uso de funções currificadas
apply f x y z = f x y z
• Os 3 argumentos são empilhados
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Modelo push-enter
• Não há alocação explícita de quadros de
ativação
• Pilha de avaliação contígua ao invés de lista
ligada de quadros alocados na heap
• Melhor performance (localidade espacial)
• Outra alternativa: v,G-machine
– Espaço de trabalho alocado em cada closure
– Mal uso de espaço
– Aplicação parcial: cópia dos argumentos para a
closure da aplicação
– Espaço alocado pode não ser suficiente
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Tipos Algébricos
• Compiladores implementam tipos built-in de
forma “mágica”
– Pior performance para tipos algébricos definidos
pelo usuário
• Mecanismo genérico para compilação de tipos
algébricos deveria ser eficiente para tipos
built-in!
• Compilação de expressões case
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Resenha do Artigo
Implementing lazy functional
languages on stock hardware: the
Spineless Tagless G-Machine (Parte I)
(Simon L. Peyton Jones}
Monique L. B. Monteiro
{mlbm}@cin.ufpe.br