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

Дефункционализация в программировании — техника преобразования программы на этапе компиляции, заменяющая функции высшего порядка на вызов одной-единственной функции применения функции к аргументу.

Впервые была описана Джоном Рейнольдсом (англ. John C. Reynolds) в 1972 году^[1]. Поскольку всякая программа содержит конечное количество функциональных абстракций, то каждая из них может быть заменена уникальным идентификатором, а каждое применение абстрактной функции в такой программе может быть заменено вызовом функции функции применения с идентификатором абстрактной функции в качестве первого параметра. При этом функция применения выбирает по идентификатору абстрактной функции операции и выполняет их над оставшимися аргументами (исходными аргументами абстрактной функции).

Одним из затруднений для этой техники является то, что функциональная абстракция может ссылаться на свободные переменные. В такой ситуации до выполнения дефункционализации должен быть выполнен λ-подъём^[англ.] — преобразование свободных переменных в замыкания, — чтобы любая свободная переменная, использующаяся функциональной абстракцией, передавалась бы в качестве аргумента в функцию применения. Кроме того, если замывание поддерживается в качестве значения первого класса, то необходимо обеспечить создание новых структур данных для представления захваченных значений.

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

Помимо применения в компиляторах для функциональных языков программирования, использующих функции высшего порядка, дефункционализация также исследовалась как метод механистического преобразования интерпретатора в абстрактную машину. Дефункционализация также связана с техникой представления функций с помощью функциональных объектов в объектно-ориентированного программирования (как альтернатива использованию замыканий).

Пример

Для типа данных «дерево»^[2]:

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, и 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)

Примечания

Литература

• John Reynolds. Definitional Interpreters for Higher-Order Programming Languages (англ.) // Proceedings of the ACM Annual Conference. — Boston, Massachusetts, 1972. — P. 717—740. — doi:10.1145/800194.805852.
• Olivier Danvy, Lasse R. Nielsen. Defunctionalization at Work (англ.) // Proceedings of the ACM SIGPLAN Conference on Principles and Practice of Declarative Programming. — 2001. — P. 162–174. — doi:10.1145/773184.773202. (Более подробная версия: Technical Report BRICS-RS-01-23)
• Olivier Danvy^[англ.], Kevin R. Millikin. Refunctionalization at Work (англ.) // Science of Computer Programming. — 2009. — June (vol. 74). — P. 534—549. — doi:10.1016/j.scico.2007.10.007. (Также доступен как Technical Report BRICS-RS-07-7)

Ссылки

• Defunctionalization (Programming Languages) // Oxford University

Эта страница в последний раз была отредактирована 26 июня 2021 в 20:51.