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

В программирования языках дефункционализация — это преобразование во время компиляции , которое исключает функции высшего порядка , заменяя их одной функцией применения первого порядка . Этот метод был впервые описан Джоном Рейнольдсом в его статье 1972 года «Определительные интерпретаторы языков программирования высшего порядка». Наблюдение Рейнольдса заключалось в том, что данная программа содержит только конечное число абстракций функций, так что каждой из них можно присвоить и заменить уникальным идентификатором. Каждое применение функции в программе затем заменяется вызовом функции apply с идентификатором функции в качестве первого аргумента. Единственная задача функции apply — выполнить отправку этого первого аргумента, а затем выполнить инструкции, обозначенные идентификатором функции, для остальных аргументов.

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

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

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

Пример

Это пример, приведенный Оливье Дэнви , переведенный на Haskell:

Учитывая тип данных «Дерево»:

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)

Мы дефункционализируем, заменяя все функции высшего порядка (в данном случае o единственная функция высшего порядка) со значением 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)

См. также

Ссылки

Рейнольдс, Джон (август 1972 г.). «Определенные интерпретаторы языков программирования высшего порядка». Материалы ежегодной конференции ACM . Бостон, Массачусетс. стр. 717–740. дои : 10.1145/800194.805852 .
Дэнви, Оливье ; Нильсен, Лассе Р. (2001). «Дефункционализация на работе» (PDF) . Материалы конференции ACM SIGPLAN по принципам и практике декларативного программирования . стр. 162–174. дои : 10.1145/773184.773202 . (Более полная версия: Технический отчет BRICS-RS-01-23 )
Дэнви, Оливье ; Милликин, Кевин Р. (июнь 2009 г.). «Рефункционализация в действии». Наука компьютерного программирования . 74 (8): 534–549. дои : 10.1016/j.scico.2007.10.007 . (Также доступен как Технический отчет BRICS-RS-07-7 )

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

Дефункционализация (языки программирования) . Оксфордский университет.