Defunkcionalizace - Defunctionalization

V programovacích jazycích , defunctionalization je kompilaci transformace, která eliminuje vyššího řádu funkce , nahradí je jediným prvního řádu platí funkci. Tuto techniku ​​poprvé popsal John C. Reynolds ve své práci z roku 1972 „Definiční tlumočníci pro programovací jazyky vyšších řádů“. Reynoldsovo pozorování spočívalo v tom, že daný program obsahuje pouze konečně mnoho abstrakcí funkcí, takže každému lze přiřadit a nahradit jedinečným identifikátorem. Každá aplikace funkcí v programu je poté nahrazena voláním funkce apply s identifikátorem funkce jako prvním argumentem. Aplikovat funkci jediným úkolem je odeslání na této první argument a proveďte instrukce označené identifikátorem funkce na zbývající argumenty.

Jednou z komplikací této základní myšlenky je, že abstrakce funkcí mohou odkazovat na volné proměnné . V takových situacích musí defunkcionalizaci předcházet uzavírací převod (zvedání lambda) , aby se všechny volné proměnné abstrakce funkce předávaly jako další argumenty, které se mají použít . Kromě toho, pokud jsou uzávěry podporovány jako hodnoty první třídy , je nutné reprezentovat tyto zachycené vazby vytvořením datových struktur.

Místo toho, aby jeden aplikovat funkce odesílání na všech funkčních odběrů v programu, různé druhy analýzy toku řízení (včetně jednoduchých rozlišování podle arity nebo typu podpisu ), mohou být použity pro určení, které slouží (y), může být nazýván při každé aplikaci funkčního site, a specializuje se vztahují funkce může být odkazoval se na místo. Cílový jazyk může alternativně podporovat nepřímá volání prostřednictvím ukazatelů funkcí , což může být efektivnější a rozšiřitelnější než přístup založený na odeslání.

Kromě jeho použití jako techniky kompilace funkčních jazyků vyššího řádu byla studována defunkcionalizace (zejména Olivierem Danvym a spolupracovníky) jako způsob mechanické transformace tlumočníků na abstraktní stroje . Defunkcionalizace souvisí také s technikou objektově orientovaného programování reprezentace funkcí funkčními objekty (jako alternativa k uzávěrkám).

Příklad

Toto je příklad od Oliviera Danvyho , přeložený do Haskella:

Vzhledem k datovému typu stromu: 

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

Budeme nefunkční následující 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)

Defunkcionalizujeme nahrazením všech funkcí vyššího řádu (v tomto případě oje to pouze funkce vyššího řádu) hodnotou Lamdatového typu a místo přímého volání zavedeme applyfunkci, která datový typ interpretuje: 

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)

Viz také

Reference

  • Reynolds, John (srpen 1972). "Definiční tlumočníci pro programovací jazyky vyšších řádů". Sborník z výroční konference ACM . Boston, Massachusetts. 717–740. doi : 10,1145 / 800194,805852 .
  • Danvy, Olivier ; Nielsen, Lasse R. (2001). „Defunkcionalizace v práci“ (PDF) . Sborník konference ACM SIGPLAN o zásadách a praxi deklarativního programování . 162–174. doi : 10,1145 / 773184,773202 .(Komplexnější verze: Technická zpráva BRICS-RS-01-23 )
  • Danvy, Olivier ; Millikin, Kevin R. (červen 2009). "Refunkcionalizace v práci" . Věda o počítačovém programování . 74 (8): 534–549. doi : 10.1016 / j.scico.2007.10.007 .(K dispozici také jako technická zpráva BRICS-RS-07-7 )

externí odkazy