Дефункционализация

Дефункционализация - в программировании означает преобразование программы на этапе компиляции заменяющее функции высшего порядка на вызов одной-единственной функции применения (apply). Эта техника впервые была описана Джоном С. Рейнольдом (John C. Reynolds) в его работе 1972 года, "Определяющие интерпретаторы для языков высшего порядка" (Definitional Interpreters for Higher-Order Programming Languages). Рейнольд отметил, что так как любая конкретная программа содержит конечное количество функциональных абстракций, то любая из этих абстракций может быть заменена уникальным идентификатором. Каждое применение функции в такой программе заменяется вызовом функции apply с идентификатором функции в качестве первого параметра, которая и выполняет связанные с заданным идентфикатором операции над оставшимися аргументами.

Одним из затруднений для этой идеи состоит в том, что фунциональная абстракция может ссылаться на свободные переменные. В такой ситуации до выполнения дефункционализации должен быть выполнен лямда-лифтинг (конвертация свободных перменных в замыкание), Таким образом, чтобы любая свободная перменная функциональной абстракции передавалась в качестве аргумента в функцию apply. Кроме того, если замывание поддерживается в качестве значения первого класса, то необходимо обеспечить создание новых структур данных для представления захваченных значений.

Пример

Этот пример предоставлен Оливером Данви (Olivier Danvy), переведённым на Хаскель.

Для типа данных Tree:

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

Производим дефункционализацию следующей программы:

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)

Мы производим дефункционализацию посредством замены всех функций высшего порядка (cons, o, and walk)значением типа Lam, и вместо прямого вызова функций, мы используем функцию apply, обрабатывающую этот значения этого типа:

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)

Примечания

• Лямда-лифтинг
• Частичное применение

Ссылки

• Reynolds, John (August 1972). "Definitional Interpreters for Higher-Order Programming Languages" (PDF). Proceedings of the ACM Annual Conference. Boston, Massachusetts. pp. 717—740. doi:10.1145/800194.805852. {{cite conference}}: Неизвестный параметр |booktitle= игнорируется (|book-title= предлагается) (справка)
• Danvy, Olivier; Nielsen, Lasse R. (2001). "Defunctionalization at Work" (PDF). Proceedings of the ACM SIGPLAN Conference on Principles and Practice of Declarative Programming. pp. 162—174. doi:10.1145/773184.773202. {{cite conference}}: Неизвестный параметр |booktitle= игнорируется (|book-title= предлагается) (справка) (More comprehensive version: Technical Report BRICS-RS-01-23)
• Danvy, Olivier; Millikin, Kevin R. (June 2009). "Refunctionalization at Work". Science of Computer Programming. 74 (8): 534—549. doi:10.1016/j.scico.2007.10.007. (Also available as Technical Report BRICS-RS-07-7)

Внешние ссылки

• Defunctionalization (Programming Languages). Oxford University.