Defunctionalization (original) (raw)
In programming languages, defunctionalization is a compile-time transformation which eliminates higher-order functions, replacing them by a single first-order apply function. The technique was first described by John C. Reynolds in his 1972 paper, "Definitional Interpreters for Higher-Order Programming Languages". Reynolds' observation was that a given program contains only finitely many function abstractions, so that each can be assigned and replaced by a unique identifier. Every function application within the program is then replaced by a call to the apply function with the function identifier as the first argument. The apply function's only job is to dispatch on this first argument, and then perform the instructions denoted by the function identifier on the remaining arguments.
| Property | Value |
|---|---|
| dbo:abstract | In programming languages, defunctionalization is a compile-time transformation which eliminates higher-order functions, replacing them by a single first-order apply function. The technique was first described by John C. Reynolds in his 1972 paper, "Definitional Interpreters for Higher-Order Programming Languages". Reynolds' observation was that a given program contains only finitely many function abstractions, so that each can be assigned and replaced by a unique identifier. Every function application within the program is then replaced by a call to the apply function with the function identifier as the first argument. The apply function's only job is to dispatch on this first argument, and then perform the instructions denoted by the function identifier on the remaining arguments. One complication to this basic idea is that function abstractions may reference free variables. In such situations, defunctionalization must be preceded by closure conversion (lambda lifting), so that any free variables of a function abstraction are passed as extra arguments to apply. In addition, if closures are supported as first-class values, it becomes necessary to represent these captured bindings by creating data structures. Instead of having a single apply function dispatch on all function abstractions in a program, various kinds of control flow analysis (including simple distinctions based on arity or type signature) can be employed to determine which function(s) may be called at each function application site, and a specialized apply function may be referenced instead. Alternatively, the target language may support indirect calls through function pointers, which may be more efficient and extensible than a dispatch-based approach. Besides its use as a compilation technique for higher-order functional languages, defunctionalization has been studied (particularly by Olivier Danvy and collaborators) as a way of mechanically transforming interpreters into abstract machines. Defunctionalization is also related to the technique from object-oriented programming of representing functions by function objects (as an alternative to closures). (en) Дефункционализация в программировании — техника преобразования программы на этапе компиляции, заменяющая функции высшего порядка на вызов одной-единственной функции применения функции к аргументу. Впервые была описана (англ. John C. Reynolds) в 1972 году. Поскольку всякая программа содержит конечное количество функциональных абстракций, то каждая из них может быть заменена уникальным идентификатором, а каждое применение абстрактной функции в такой программе может быть заменено вызовом функции функции применения с идентификатором абстрактной функции в качестве первого параметра. При этом функция применения выбирает по идентификатору абстрактной функции операции и выполняет их над оставшимися аргументами (исходными аргументами абстрактной функции). Одним из затруднений для этой техники является то, что функциональная абстракция может ссылаться на . В такой ситуации до выполнения дефункционализации должен быть выполнен — преобразование свободных переменных в замыкания, — чтобы любая свободная переменная, использующаяся функциональной абстракцией, передавалась бы в качестве аргумента в функцию применения. Кроме того, если замывание поддерживается в качестве значения первого класса, то необходимо обеспечить создание новых структур данных для представления захваченных значений. Вместо использования единственной функции применения для обработки всех случаев, могут использоваться различные методы анализа потока управления (включая простейшее различение разных видов арности (числа аргументов) или ) для разделения применения на несколько специализированных функций. Также язык программирования может поддерживать , использование которых может быть более эффективным, чем подход с диспетчеризацией. Помимо применения в компиляторах для функциональных языков программирования, использующих функции высшего порядка, дефункционализация также исследовалась как метод механистического преобразования интерпретатора в абстрактную машину. Дефункционализация также связана с техникой представления функций с помощью функциональных объектов в объектно-ориентированного программирования (как альтернатива использованию замыканий). (ru) |
| dbo:wikiPageExternalLink | https://spivey.oriel.ox.ac.uk/proglan/Defunctionalization http://www.daimi.au.dk/~danvy/DSc/22_danvy-nielsen_ppdp-2001.pdf http://www.brics.dk/RS/01/23/BRICS-RS-01-23.pdf http://www.brics.dk/RS/07/7/BRICS-RS-07-7.pdf |
| dbo:wikiPageID | 24504713 (xsd:integer) |
| dbo:wikiPageLength | 5417 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1069178466 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Programming_languages dbr:Interpreter_(computing) dbr:Object-oriented_programming dbr:Closure_(computer_science) dbr:Control_flow_analysis dbr:Arity dbr:Compile_time dbr:Function_object dbr:Closure_conversion dbr:Function_pointer dbc:Implementation_of_functional_programming_languages dbr:Type_signature dbr:Partial_evaluation dbr:Higher-order_function dbr:Abstract_machine dbr:Abstraction_(computer_science) dbr:John_C._Reynolds dbr:Olivier_Danvy dbr:Free_variables dbr:First-class_value dbr:Functional_languages |
| dbp:wikiPageUsesTemplate | dbt:Cite_conference dbt:Cite_journal dbt:Short_description |
| dct:subject | dbc:Implementation_of_functional_programming_languages |
| rdfs:comment | In programming languages, defunctionalization is a compile-time transformation which eliminates higher-order functions, replacing them by a single first-order apply function. The technique was first described by John C. Reynolds in his 1972 paper, "Definitional Interpreters for Higher-Order Programming Languages". Reynolds' observation was that a given program contains only finitely many function abstractions, so that each can be assigned and replaced by a unique identifier. Every function application within the program is then replaced by a call to the apply function with the function identifier as the first argument. The apply function's only job is to dispatch on this first argument, and then perform the instructions denoted by the function identifier on the remaining arguments. (en) Дефункционализация в программировании — техника преобразования программы на этапе компиляции, заменяющая функции высшего порядка на вызов одной-единственной функции применения функции к аргументу. Впервые была описана (англ. John C. Reynolds) в 1972 году. Поскольку всякая программа содержит конечное количество функциональных абстракций, то каждая из них может быть заменена уникальным идентификатором, а каждое применение абстрактной функции в такой программе может быть заменено вызовом функции функции применения с идентификатором абстрактной функции в качестве первого параметра. При этом функция применения выбирает по идентификатору абстрактной функции операции и выполняет их над оставшимися аргументами (исходными аргументами абстрактной функции). (ru) |
| rdfs:label | Defunctionalization (en) Дефункционализация (ru) |
| owl:sameAs | freebase:Defunctionalization wikidata:Defunctionalization dbpedia-ru:Defunctionalization https://global.dbpedia.org/id/4jBwg |
| prov:wasDerivedFrom | wikipedia-en:Defunctionalization?oldid=1069178466&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Defunctionalization |
| is dbo:knownFor of | dbr:John_C._Reynolds |
| is dbo:wikiPageWikiLink of | dbr:List_of_computer_scientists dbr:Currying dbr:List_of_programmers dbr:List_of_programming_language_researchers dbr:Closure_(computer_programming) dbr:Mutual_recursion dbr:List_of_Bates_College_people dbr:Higher-order_function dbr:John_C._Reynolds dbr:First-class_function dbr:Multitier_programming |
| is foaf:primaryTopic of | wikipedia-en:Defunctionalization |