Анонимная рекурсия
В информатике , анонимная рекурсия — это рекурсия которая не вызывает явную функцию по имени. Это можно сделать либо явно, используя функцию более высокого порядка (передав функцию в качестве аргумента и вызвав ее), либо неявно, с помощью функций отражения , которые позволяют получить доступ к определенным функциям в зависимости от текущего контекста, особенно «текущей функции». " или иногда "вызывающая функция текущей функции".
В практике программирования анонимная рекурсия особенно используется в JavaScript , который предоставляет средства отражения для ее поддержки. Однако в общей практике программирования это считается плохим стилем, и вместо этого предлагается рекурсия с именованными функциями. Анонимная рекурсия посредством явной передачи функций в качестве аргументов возможна на любом языке, поддерживающем функции в качестве аргументов, хотя на практике это используется редко, поскольку это длиннее и менее понятно, чем явная рекурсия по имени.
В теоретической информатике анонимная рекурсия важна, поскольку она показывает, что можно реализовать рекурсию, не требуя именованных функций. Это особенно важно для лямбда-исчисления , которое имеет анонимные унарные функции, но способно вычислить любую рекурсивную функцию. Эту анонимную рекурсию можно создать в общих чертах с помощью комбинаторов с фиксированной точкой .
Используйте [ править ]
Анонимная рекурсия в первую очередь используется для обеспечения рекурсии для анонимных функций , особенно когда они образуют замыкания или используются в качестве обратных вызовов , чтобы избежать необходимости привязывать имя функции.
Анонимная рекурсия в основном состоит из вызова «текущей функции», что приводит к прямой рекурсии . Возможна анонимная косвенная рекурсия , например, путем вызова «вызывающего объекта (предыдущей функции)» или, реже, путем перехода дальше вверх по стеку вызовов , и это можно объединить в цепочку для создания взаимной рекурсии . Самоссылка , «текущей функции» является функциональным эквивалентом ключевого слова « this » в объектно-ориентированном программировании позволяя ссылаться на текущий контекст.
Анонимную рекурсию также можно использовать для именованных функций, а не вызывать их по имени, например, чтобы указать, что выполняется рекурсия для текущей функции, или чтобы можно было переименовать функцию без необходимости изменять имя, в котором она вызывает себя. Однако в соответствии со стилем программирования этого обычно не делают.
Альтернативы [ править ]
Именованные функции [ править ]
Обычная альтернатива — использование именованных функций и именованной рекурсии. Учитывая анонимную функцию, это можно сделать либо путем привязки имени к функции, как в выражениях именованных функций в JavaScript, либо путем присвоения функции переменной и последующего вызова этой переменной, как в операторах функций в JavaScript. Поскольку языки, допускающие анонимные функции, обычно позволяют присваивать эти функции переменным (если не функциям первого класса), многие языки не предоставляют возможности ссылаться на саму функцию и явно отвергают анонимную рекурсию; примеры включают Go . [1]
Например, в JavaScript функция факториала может быть определена посредством анонимной рекурсии следующим образом: [2]
[ 1 , 2 , 3 , 4 5, карта ( функция ( n ) { return ( ! ( n > 1 )) ? 1 : аргументы . calle ( n - 1 ) * n ; }); Переписано для использования выражения именованной функции, что дает:
[ 1 , 2 , 3 , 4 , 5 ]. карта ( функция факториал ( n ) { return ( ! ( n > 1 )) ? 1 : факториал ( n - 1 ) * n ; }); Передача функций в качестве аргументов [ править ]
Даже без механизмов обращения к текущей функции или вызывающей функции анонимная рекурсия возможна в языке, который допускает функции в качестве аргументов. Это делается путем добавления еще одного параметра к базовой рекурсивной функции и использования этого параметра в качестве функции для рекурсивного вызова. Это создает функцию более высокого порядка, и передача этой функции более высокого порядка сама позволяет анонимную рекурсию внутри фактической рекурсивной функции. Это можно сделать чисто анонимно, применив к этой функции более высокого порядка комбинатор с фиксированной точкой . Это в основном представляет академический интерес, в частности, чтобы показать, что лямбда-исчисление имеет рекурсию, поскольку полученное выражение значительно сложнее, чем исходная названная рекурсивная функция. И наоборот, использование комбинаторов с фиксированной точкой можно в целом назвать «анонимной рекурсией», поскольку это их заметное использование, хотя у них есть и другие приложения. [3] [4]
Это показано ниже с использованием Python. Во-первых, стандартная именованная рекурсия:
def факт ( n ): если n == 0 : вернуть 1 вернуть n * факт ( n - 1 ) Использование функции более высокого порядка, чтобы функция верхнего уровня анонимно рекурсировала по аргументу, но при этом в качестве аргумента все равно требовалась стандартная рекурсивная функция:
def fact0 ( n0 ): если n0 == 0 : вернуть 1 вернуть n0 * fact0 ( n0 - 1 ) fact1 = лямбда f , n1 : 1 если n1 == 0 else n1 * f ( n1 - 1 ) fact = лямбда n : факт1 ( факт0 , n ) Мы можем исключить стандартную рекурсивную функцию, передав аргумент функции в вызов:
факт1 = лямбда f , n1 : 1 , если n1 == 0, иначе n1 * f ( f , n1 - 1 ) факт = лямбда n : факт1 ( факт1 , n ) Вторую строку можно заменить общей функцией высшего порядка, называемой комбинатором :
F = лямбда f : ( лямбда x : f ( f , x )) fact1 = лямбда f , n1 : 1 , если n1 == 0, иначе n1 * f ( f , n1 - 1 ) факт = F ( факт1 ) Написано анонимно: [5]
( лямбда f : ( лямбда x : f ( f , x ))) \ ( лямбда g , n1 : 1 , если n1 == 0 , иначе n1 * g ( g , n1 - 1 )) В лямбда-исчислении , которое использует только функции одной переменной, это можно сделать с помощью Y-комбинатора . Сначала сделайте функцию высшего порядка двух переменных функцией одной переменной, которая напрямую возвращает функцию, с помощью каррирования :
факт1 = лямбда f : ( лямбда n1 : 1 если n1 == 0 иначе n1 * f ( f )( n1 - 1 )) факт = факт1 ( факт1 ) Здесь есть две операции «применения функции более высокого порядка к самой себе»: f(f) в первой строке и fact1(fact1) во втором. Вынесение второго двойного приложения в комбинатор дает:
C = лямбда x : x ( x ) факт1 = лямбда f : ( лямбда n1 : 1 если n1 == 0 иначе n1 * f ( f )( n1 - 1 )) факт = C ( факт1 ) Если исключить другое двойное приложение, получим:
C = лямбда x : x ( x ) D = лямбда f : ( лямбда x : f ( лямбда v : x ( x )( v ))) fact1 = лямбда g : ( лямбда n1 : 1 if n1 == 0 else n1 * г ( n1 - 1 )) факт = C ( D ( факт1 )) Объединение двух комбинаторов в один дает комбинатор Y :
C = лямбда x : x ( x ) D = лямбда f : ( лямбда x : f ( лямбда v : x ( x )( v ))) Y = лямбда y : C ( D ( y )) fact1 = лямбда g : ( лямбда n1 : 1 , если n1 == 0 , иначе n1 * g ( n1 - 1 )) факт = Y ( факт1 ) Раскрытие Y-комбинатора дает:
Y = лямбда f : ( лямбда x : f ( лямбда v : x ( x )( v ))) \ ( лямбда x : f ( лямбда v : x ( x )( v ))) fact1 = лямбда g : ( лямбда n1 : 1 если n1 == 0 иначе n1 * g ( n1 - 1 )) fact = Y ( факт1 ) Их объединение дает рекурсивное определение факториала в лямбда-исчислении (анонимные функции одной переменной): [6]
( лямбда f : ( лямбда x : f ( лямбда v : x ( x )( v ))) ( лямбда x : f ( лямбда v : x ( x )( v )))) \ ( лямбда g : ( лямбда n1 : 1 если n1 == 0 иначе n1 * g ( n1 - 1 ))) Примеры [ править ]
АПЛ [ править ]
В APL текущий dfn доступен через ∇. Это позволяет анонимную рекурсию, например, в этой реализации факториала:
{ 0 = ⍵: 1 ⋄ ⍵ × ∇ ⍵ - 1 } 5 120 { 0 = ⍵ : 1 ⋄ ⍵ × ∇ ⍵ - 1 } ¨ ⍳ 10 ⍝ применяется к каждому элементу от 0 до 9 1 1 2 6 24 120 720 5040 40320 362880 JavaScript [ править ]
В JavaScript текущая функция доступна через arguments.callee, а вызывающая функция доступна через arguments.caller. Они допускают анонимную рекурсию, например, в этой реализации факториала: [2]
[ 1 , 2 , 3 , 4 5, карта ( функция ( n ) { return ( ! ( n > 1 )) ? 1 : аргументы . calle ( n - 1 ) * n ; }); Перл [ править ]
Начиная с Perl 5.16, текущая подпрограмма доступна через __SUB__ токен, который возвращает ссылку на текущую подпрограмму, или undef вне подпрограммы. [7] Это позволяет анонимную рекурсию, например, в следующей реализации факториала:
#!/usr/bin/perl использовать функцию ":5.16" ; печать суб { мой $х = сдвиг ; $х > 0 ? $x * __SUB__ -> ( $x - 1 ) : 1 ; } -> ( 5 ), "\n" ; Р [ править ]
В R текущую функцию можно вызвать с помощью Recall. Например,
sapply ( 0 : 5 , функция ( n ) { if ( n == 0 ) return ( 1 ) n * Recall ( n - 1 ) }) Однако он не будет работать, если будет передан в качестве аргумента другой функции, например lapply, внутри определения анонимной функции. В этом случае, sys.function(0) можно использовать. [8] Например, приведенный ниже код рекурсивно возводит список в квадрат:
( функция ( x ) { if ( is.list ( x )) { lapply ( x , sys.function ( 0 )) } else { x ^ 2 } })( список ( список ( 1 , 2 , 3 ), список ( 4 , 5 ))) Ссылки [ править ]
- ^ Проблема 226: невозможно рекурсивно выполнить анонимную функцию в Go без обходных путей.
- ↑ Перейти обратно: Перейти обратно: а б ответ olliej, 25 октября 2008 г. на вопрос « Почему свойство аргументов.callee.caller устарело в JavaScript? », StackOverflow
- ^ Эта терминология, по-видимому, во многом фольклорная , но она встречается в следующем:
- Трей Нэш, Accelerated C# 2008 , Apress, 2007, ISBN 1-59059-873-3 , с. 462—463. В основном взято из Уэса Дайера (см. следующий пункт). блога
- Анонимная рекурсия Уэса Дайера в C# , 2 февраля 2007 г., содержит по существу аналогичный пример, найденный в книге выше, но сопровождаемый дополнительным обсуждением.
- ^ The If Works , вывод Y-комбинатора , 10 января 2008 г.
- ^ Ответ Хьюго Уолтера на вопрос « Может ли лямбда-функция рекурсивно вызывать себя в Python? »
- ^ Ответ Nux на вопрос « Может ли лямбда-функция рекурсивно вызывать себя в Python? »
- ^ Perldoc, « Функция current_sub» , функция perldoc
- ^ ответ agstudy на получение вызываемой в данный момент функции для написания анонимной рекурсивной функции в StackOverflow