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

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

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

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

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

Пример

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

Учитывая тип данных 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)

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

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