Upload
internet
View
116
Download
7
Embed Size (px)
Citation preview
Resenha do ArtigoResenha do Artigo
Implementing lazy functional Implementing lazy functional languages on stock languages on stock hardware: the Spineless hardware: the Spineless Tagless G-Machine Tagless G-Machine (Parte I)(Parte I)Monique L. B. Monteiro
{mlbm}@cin.ufpe.br
(Simon L. Peyton Jones}
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Essência do ArtigoEssência do Artigo• Propor um modelo otimizado e Propor um modelo otimizado e
simplificado de compilação de simplificado de compilação de linguagens funcionaislinguagens funcionais
• Expor em detalhes o funcionamento Expor em detalhes o funcionamento da da Spineless Tagless G-MachineSpineless Tagless G-Machine
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Relevância para o HS.NETRelevância para o HS.NET• Entender o modelo básico de Entender o modelo básico de
compilação utilizado pelo GHCcompilação utilizado pelo GHC
• Promover maior intimidade com a Promover maior intimidade com a compilação de linguagens funcionais compilação de linguagens funcionais em geralem geral
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
STG – Visão geralSTG – Visão geral• Máquina abstrata projetada para Máquina abstrata projetada para
linguagens linguagens funcionais não estritas de funcionais não estritas de alta ordemalta ordem
• Utiliza uma linguagem intermediária Utiliza uma linguagem intermediária funcionalfuncional – – STG LanguageSTG Language
• C como linguagem alvoC como linguagem alvo• EficienteEficiente• Linguagens Linguagens fortemente tipadasfortemente tipadas, ,
puramente funcionais puramente funcionais e e lazylazy
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Compilação de HaskellCompilação de Haskell
Várias transformações...Source.hs Source.hc Source.stg Source.c
Alternativas de Alternativas de ImplementaçãoImplementação
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
ImplementaçãoImplementação• Combinação de várias outras técnicasCombinação de várias outras técnicas• Origens em técnicas de redução de Origens em técnicas de redução de
grafosgrafos• Representação deRepresentação de
– Funções-valorFunções-valor– DadosDados– Expressões não avaliadasExpressões não avaliadas– Aplicação de funçõesAplicação de funções– Estruturas Estruturas casecase em dados de tipos em dados de tipos
algébricosalgébricos
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
ClosuresClosures• Objetos do heapObjetos do heap
– Head normal form Head normal form (ou (ou valoresvalores))– Objetos não avaliados (Objetos não avaliados (thunksthunks))
• Head Normal formHead Normal form– Função-valorFunção-valor– DadosDados
• Normal FormNormal Form– Não contém thunksNão contém thunks
Closures
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
FunçõesFunções
Variáveis LivresCódigo
- Computação “suspensa”- Computação “suspensa”
- Bloco de código compartilhado- Bloco de código compartilhado
- Denominado - Denominado closureclosure
- Para - Para entrar entrar na closure: ponteiro de ambiente na closure: ponteiro de ambiente aponta para a mesma aponta para a mesma
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
ThunksThunks• Computação “suspensa”Computação “suspensa”• Representados por closuresRepresentados por closures• Atualizados na primeira avaliaçãoAtualizados na primeira avaliação• Não são aplicações parciaisNão são aplicações parciais• Não são construtoresNão são construtores
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
AtualizaçõesAtualizações• Naïve reduction modelNaïve reduction model
– Atualiza após cada reduçãoAtualiza após cada redução– Um thunk pode ser atualizado com outro: Um thunk pode ser atualizado com outro:
atualização repetidaatualização repetida
• Cell model (Modelo de célula)Cell model (Modelo de célula)– FlagFlag de status de status – Já foi avaliado: retorna o valorJá foi avaliado: retorna o valor– Não foi avaliado: “entra”, calcula o valorNão foi avaliado: “entra”, calcula o valor– Código chamador atualiza o valor e a flagCódigo chamador atualiza o valor e a flag
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
AtualizaçõesAtualizações• Self-updating model (Auto-atualização)Self-updating model (Auto-atualização)
– Utilizado pela STGUtilizado pela STG– Atualização feita pelo código interno ao Atualização feita pelo código interno ao
thunkthunk– Valor é computado e atualizado OU Valor é computado e atualizado OU
simplesmente simplesmente retornadoretornado– Valor pode ser representado por indireçãoValor pode ser representado por indireção– Não Não há testeshá testes– Deve possuir ponteiro para códigoDeve possuir ponteiro para código
• Nem sempre a atualização precisa ser Nem sempre a atualização precisa ser feita!feita!
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Atualização: ExemploAtualização: Exemplo• Modelo de auto-atualizaçãoModelo de auto-atualização
Código
Variáveis Livres
Antes de atualizar
Depois de atualizar (valor pequeno)
TailHead
Código do Cons
Depois de atualizar (valor grande)
Código de indireção
Valor
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Atualização: ExemploAtualização: Exemplo• Modelo de célulaModelo de célula
0
Código
Variáveis Livres
Antes de atualizar Depois de atualizar
1 Valor
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Aplicação de FunçõesAplicação de Funções• CurrificaçãoCurrificação
– Tipo de Tipo de ff pode ser pode ser a -> (b -> a)a -> (b -> a)
(f 1 2)(f 1 2) = = ((f 1) 2)((f 1) 2)
(map (f 1) xs)(map (f 1) xs)
f x y = x
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Aplicação da FunçõesAplicação da Funções• Modelo Modelo eval-applyeval-apply
– Funcao é Funcao é avaliadaavaliada– Argumentos são avaliadosArgumentos são avaliados– Valor-função é aplicado ao argumentoValor-função é aplicado ao argumento– Avaliação trivial para funções conhecidasAvaliação trivial para funções conhecidas
• Modelo Modelo push-enter push-enter (STG, G-machine, (STG, G-machine, TIM)TIM)– Baseado em redução de grafoBaseado em redução de grafo– Coloca-se o argumento na pilha de avaliaçãoColoca-se o argumento na pilha de avaliação– Tail-call (ou entra) a funçãoTail-call (ou entra) a função– Não há “return”Não há “return”
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Modelo push-enterModelo push-enter• Adequado para uso de funções Adequado para uso de funções
currificadascurrificadas
• Os 3 argumentos são empilhadosOs 3 argumentos são empilhados
apply f x y z = f x y z
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Modelo push-enterModelo push-enter• Não há alocação explícita de quadros de Não há alocação explícita de quadros de
ativaçãoativação• Pilha de avaliação contígua ao invés de Pilha de avaliação contígua ao invés de
lista ligada de quadros alocados na heaplista ligada de quadros alocados na heap• Melhor performance (localidade Melhor performance (localidade
espacial)espacial)• Outra alternativa: Outra alternativa: v,Gv,G-machine-machine
– Espaço de trabalho alocado em cada closureEspaço de trabalho alocado em cada closure– Mal uso de espaçoMal uso de espaço– Aplicação parcial: cópia dos argumentos para Aplicação parcial: cópia dos argumentos para
a closure da aplicaçãoa closure da aplicação– Espaço alocado pode não ser suficienteEspaço alocado pode não ser suficiente
Resenha de Artigo - Projeto Haskell.NET @ CIn/UFPE – 2004.1
Tipos AlgébricosTipos Algébricos• Compiladores implementam tipos Compiladores implementam tipos
built-inbuilt-in de forma “mágica” de forma “mágica”– Pior performance para tipos algébricos Pior performance para tipos algébricos
definidos pelo usuáriodefinidos pelo usuário
• Mecanismo genérico para compilação Mecanismo genérico para compilação de tipos algébricos deveria ser de tipos algébricos deveria ser eficiente para tipos built-in!eficiente para tipos built-in!
• Compilação de expressões Compilação de expressões casecase
Resenha do ArtigoResenha do Artigo
Implementing lazy functional Implementing lazy functional languages on stock languages on stock hardware: the Spineless hardware: the Spineless Tagless G-Machine Tagless G-Machine (Parte I)(Parte I)Monique L. B. Monteiro
{mlbm}@cin.ufpe.br
(Simon L. Peyton Jones}