Defunkcjonalizacja - Defunctionalization

W językach programowania , defunctionalization jest kompilacji transformacja, która eliminuje funkcje wyższego rzędu , zastępując je jednym pierwszej kolejności zastosować funkcję. Technika została po raz pierwszy opisana przez Johna C. Reynoldsa w jego artykule z 1972 roku „Definitional Interpreters for Higher-Order Programming Languages”. Obserwacja Reynoldsa była taka, że ​​dany program zawiera tylko skończenie wiele abstrakcji funkcji, tak że każda może być przypisana i zastąpiona unikalnym identyfikatorem. Każda aplikacja funkcji w programie jest następnie zastępowana wywołaniem funkcji Apply z identyfikatorem funkcji jako pierwszym argumentem. Zastosowanie funkcyjnego jedynym zadaniem jest gotowa na ten pierwszy argument, a następnie wykonaj instrukcje oznaczona identyfikatorem funkcji na pozostałych argumentów.

Jedną z komplikacji tej podstawowej idei jest to, że abstrakcje funkcji mogą odwoływać się do wolnych zmiennych . W takich sytuacjach defunkcjonalizacja musi być poprzedzona konwersją domknięcia (podnoszenie lambda) , aby wszelkie wolne zmienne abstrakcji funkcji były przekazywane jako dodatkowe argumenty do zastosowania . Ponadto, jeśli domknięcia są obsługiwane jako wartości pierwszej klasy , konieczne staje się reprezentowanie tych przechwyconych powiązań przez tworzenie struktur danych.

Zamiast pojedynczego zastosowania funkcji wysyłkę na wszystkich abstrakcji funkcji w programie, różne rodzaje analizy przepływu sterowania (w tym prostych wyróżnień w oparciu o liczbę operandów lub typu podpisu ) mogą być stosowane w celu określenia spełniających funkcję (S) może być zwołane w każdej aplikacji funkcji miejsce, a specjalizuje się zastosować funkcja może się odwoływać zamiast. Alternatywnie język docelowy może obsługiwać wywołania pośrednie za pomocą wskaźników funkcji , które mogą być bardziej wydajne i rozszerzalne niż podejście oparte na wysyłce.

Oprócz wykorzystania jako techniki kompilacji dla języków funkcyjnych wyższego rzędu , defunkcjonalizacja była badana (szczególnie przez Oliviera Danvy i współpracowników) jako sposób mechanicznego przekształcania interpreterów w abstrakcyjne maszyny . Defunkcjonalizacja jest również związana z techniką programowania obiektowego reprezentowania funkcji przez obiekty funkcyjne (jako alternatywa dla domknięć).

Przykład

Oto przykład podany przez Oliviera Danvy , przetłumaczony na Haskella:

Biorąc pod uwagę typ danych Drzewo: 

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

Zdefunkcjonalizujemy następujący program: 

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)

Defunkcjonalizujemy zastępując wszystkie funkcje wyższego rzędu (w tym przypadku ojest to jedyna funkcja wyższego rzędu) wartością Lamtypu danych, a zamiast wywoływać je bezpośrednio, wprowadzamy applyfunkcję, która interpretuje typ danych: 

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)

Zobacz też

Bibliografia

  • Reynolds, John (sierpień 1972). „Definicjalne interpretatory dla języków programowania wyższego rzędu”. Materiały z dorocznej konferencji ACM . Boston, Massachusetts. s. 717-740. doi : 10.1145/800194.805852 .
  • Danvy, Olivier ; Nielsen, Lasse R. (2001). „Defunkcjonalizacja w pracy” (PDF) . Materiały z konferencji ACM SIGPLAN nt. zasad i praktyki programowania deklaratywnego . s. 162-174. doi : 10.1145/773184.773202 .(Bardziej obszerna wersja: Raport techniczny BRICS-RS-01-23 )
  • Danvy, Olivier ; Millikin, Kevin R. (czerwiec 2009). „Refunkcjonalizacja w pracy” . Nauka o programowaniu komputerowym . 74 (8): 534–549. doi : 10.1016/j.scico.2007.10.007 .(Dostępny również jako Raport Techniczny BRICS-RS-07-7 )

Linki zewnętrzne