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

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

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

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

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

Пример

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

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

 данных  Дерево   a   =   Лист   a              |   Узел   (  Дерево   a  )   (  Дерево   a  )

Мы дефункционализируем следующую программу:

cons   ::   a   ->   [  a  ]   ->   [  a  ]  cons   x   xs   =   x   :   xs  o   ::   (  b   ->   c  )   ->   (  a   ->   b  )   ->   a   ->   c  o   f   g   x   =   f   (  g   x  )  сгладить   ::   Дерево   t   ->   [  t  ]  сгладить   t   =   ходить   t   []  ходить   ::   Дерево   t   ->   [  t  ]   ->   [  t  ]  ходить   (  Лист   x  )       =   cons   x  ходить   (  Узел   t1   t2  )   =   о   (  прогулка   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   ->   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 )

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

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