Desfuncionalização - Defunctionalization

Em linguagens de programação , a desfuncionalização é uma transformação em tempo de compilação que elimina funções de ordem superior , substituindo-as por uma única função de aplicação de primeira ordem . A técnica foi descrita pela primeira vez por John C. Reynolds em seu artigo de 1972, "Definitional Interpreters for Higher-Order Programming Languages". A observação de Reynolds foi que um determinado programa contém apenas um número finito de abstrações de funções, de modo que cada uma pode ser atribuída e substituída por um identificador único. Cada aplicativo de função dentro do programa é então substituído por uma chamada para a função apply com o identificador de função como o primeiro argumento. A única tarefa da função apply é despachar neste primeiro argumento e, em seguida, executar as instruções denotadas pelo identificador de função nos argumentos restantes.

Uma complicação para essa ideia básica é que as abstrações de função podem fazer referência a variáveis ​​livres . Em tais situações, a desfuncionalização deve ser precedida pela conversão de fechamento (levantamento de lambda) , de forma que quaisquer variáveis ​​livres de uma abstração de função sejam passadas como argumentos extras a serem aplicados . Além disso, se os encerramentos forem suportados como valores de primeira classe , será necessário representar essas ligações capturadas criando estruturas de dados.

Em vez de ter um único despacho de função de aplicação em todas as abstrações de função em um programa, vários tipos de análise de fluxo de controle (incluindo distinções simples com base em aridade ou assinatura de tipo ) podem ser empregados para determinar quais funções podem ser chamadas em cada aplicação de função site, e uma função de aplicação especializada pode ser referenciada em seu lugar. Como alternativa, a linguagem de destino pode suportar chamadas indiretas por meio de ponteiros de função , que podem ser mais eficientes e extensíveis do que uma abordagem baseada em despacho.

Além de seu uso como uma técnica de compilação para linguagens funcionais de ordem superior , a desfuncionalização tem sido estudada (principalmente por Olivier Danvy e colaboradores) como uma forma de transformar intérpretes mecanicamente em máquinas abstratas . A desfuncionalização também está relacionada à técnica de programação orientada a objetos de representação de funções por objetos de função (como uma alternativa para fechamentos).

Exemplo

Este é um exemplo dado por Olivier Danvy , traduzido para Haskell:

Dado o tipo de dados Tree: 

data Tree a = Leaf a
            | Node (Tree a) (Tree a)

Vamos desfuncionalizar o seguinte programa: 

cons :: a -> [a] -> [a]
cons x xs = x : xs

o :: (b -> c) -> (a -> b) -> a -> c
o f g x = f (g x)

flatten :: Tree t -> [t]
flatten t = walk t []

walk :: Tree t -> [t] -> [t]
walk (Leaf x)     = cons x
walk (Node t1 t2) = o (walk t1) (walk t2)

Nós desfuncionalizamos substituindo todas as funções de ordem superior (neste caso, oé a única função de ordem superior) por um valor do Lamtipo de dados e, em vez de chamá-los diretamente, introduzimos uma applyfunção que interpreta o tipo de dados: 

data Lam a = LamCons a
           | LamO (Lam a) (Lam a)

apply :: Lam a -> [a] -> [a]
apply (LamCons x)  xs = x : xs
apply (LamO f1 f2) xs = apply f1 (apply f2 xs)

cons_def :: a -> Lam a
cons_def x  = LamCons x

o_def :: Lam a -> Lam a -> Lam a
o_def f1 f2 = LamO f1 f2

flatten_def :: Tree t -> [t]
flatten_def t = apply (walk_def t) []

walk_def :: Tree t -> Lam t
walk_def (Leaf x)     = cons_def x
walk_def (Node t1 t2) = o_def (walk_def t1) (walk_def t2)

Veja também

Referências

  • Reynolds, John (agosto de 1972). "Intérpretes de definição para linguagens de programação de ordem superior". Proceedings of the ACM Annual Conference . Boston, Massachusetts. pp. 717–740. doi : 10.1145 / 800194.805852 .
  • Danvy, Olivier ; Nielsen, Lasse R. (2001). "Desfuncionalização no Trabalho" (PDF) . Proceedings of the ACM SIGPLAN Conference on Principles and Practice of Declarative Programming . pp. 162–174. doi : 10.1145 / 773184.773202 .(Versão mais abrangente: Relatório Técnico BRICS-RS-01-23 )
  • Danvy, Olivier ; Millikin, Kevin R. (junho de 2009). “Refuncionalização no Trabalho” . Ciência da Programação de Computadores . 74 (8): 534–549. doi : 10.1016 / j.scico.2007.10.007 .(Também disponível como Relatório Técnico BRICS-RS-07-7 )

links externos