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

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

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

Вместо использования единственной функции 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. Refunctionalization at Work (неопр.) // Science of Computer Programming. — 2009. — June (т. 74). — С. 534—549. — doi:10.1016/j.scico.2007.10.007. (Also available as Technical Report BRICS-RS-07-7)

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

• Defunctionalization (Programming Languages). Oxford University.