В языках программирования дефункционализация — это преобразование времени компиляции , которое устраняет функции высшего порядка , заменяя их одной функцией применения первого порядка . Впервые этот метод был описан Джоном К. Рейнольдсом в его статье 1972 года «Определительные интерпретаторы для языков программирования высшего порядка». Наблюдение Рейнольдса состояло в том, что данная программа содержит только конечное число абстракций функций, так что каждая может быть назначена и заменена уникальным идентификатором. Затем каждое применение функции в программе заменяется вызовом функции применения с идентификатором функции в качестве первого аргумента. Единственная задача функции применения — диспетчеризация по этому первому аргументу, а затем выполнение инструкций, обозначенных идентификатором функции, по оставшимся аргументам.
Одно из осложнений этой базовой идеи заключается в том, что абстракции функций могут ссылаться на свободные переменные . В таких ситуациях дефункционализации должно предшествовать преобразование замыкания (лямбда-подъем) , так что любые свободные переменные абстракции функции передаются как дополнительные аргументы для применения . Кроме того, если замыкания поддерживаются как значения первого класса , становится необходимым представлять эти захваченные привязки путем создания структур данных.
Вместо того, чтобы иметь одну функцию применения диспетчеризации для всех абстракций функций в программе, различные виды анализа потока управления (включая простые различия на основе арности или сигнатуры типа ) могут быть использованы для определения того, какие функции могут быть вызваны в каждом месте применения функции, и вместо этого может быть сделана ссылка на специализированную функцию применения . В качестве альтернативы целевой язык может поддерживать косвенные вызовы через указатели функций , что может быть более эффективным и расширяемым, чем подход на основе диспетчеризации.
Помимо использования в качестве метода компиляции для функциональных языков более высокого порядка , дефункционализация изучалась (в частности, Оливье Дэнви и соавторами) как способ механического преобразования интерпретаторов в абстрактные машины . Дефункционализация также связана с методом из объектно-ориентированного программирования представления функций с помощью функциональных объектов (как альтернатива замыканиям).
Вот пример, приведенный Оливье Дэнви , переведенный на Haskell:
Учитывая тип данных Tree:
данные Дерево a = Лист a | Узел ( Дерево a ) ( Дерево a ) Мы отключим следующую программу:
минусы :: а -> [ а ] -> [ а ] минусы x xs = x : xs о :: ( б -> в ) -> ( а -> б ) -> а -> в о ф г х = ф ( г х ) выравнивание :: Дерево t -> [ t ] выравнивание t = прогулка t [] прогулка :: Дерево t -> [ t ] -> [ t ] прогулка ( Лист x ) = cons x прогулка ( Узел t1 t2 ) = o ( прогулка t1 ) ( прогулка t2 ) Мы дефункционализируем, заменяя все функции высшего порядка (в данном случае — oэто единственная функция высшего порядка) значением типа Lamданных, и вместо их непосредственного вызова вводим applyфункцию, которая интерпретирует тип данных:
данные Lam a = LamCons a | LamO ( Lam a ) ( Lam a ) применить :: Lam a -> [ a ] -> [ a ] применить ( LamCons x ) xs = x : xs применить ( LamO f1 f2 ) xs = применить f1 ( применить f2 xs ) cons_def :: a -> Лам а cons_def x = ЛамКонс x o_def :: Lam a -> Lam a -> Lam a o_def f1 f2 = LamO f1 f2 flatten_def :: Дерево t -> [ t ] flatten_def t = применить ( walk_def t ) [] walk_def :: Дерево t -> Лэм t walk_def ( Лист x ) = cons_def x walk_def ( Узел t1 t2 ) = o_def ( walk_def t1 ) ( walk_def t2 )