Anonimowa rekurencja

W informatyce anonimowa rekurencja to rekurencja , która nie wywołuje jawnie funkcji po imieniu . Można to zrobić jawnie, używając funkcji wyższego rzędu - przekazując funkcję jako argument i wywołując ją - lub niejawnie, za pomocą funkcji odbicia , które umożliwiają dostęp do pewnych funkcji w zależności od bieżącego kontekstu, zwłaszcza „bieżącej funkcji ” lub czasami „funkcja wywołująca bieżącej funkcji”.

W praktyce programistycznej anonimowa rekurencja jest szczególnie używana w JavaScript , który zapewnia funkcje refleksji, aby ją wspierać. Jednak w ogólnej praktyce programowania jest to uważane za zły styl i zamiast tego sugeruje się rekurencję z nazwanymi funkcjami. Anonimowa rekurencja poprzez jawne przekazywanie funkcji jako argumentów jest możliwa w każdym języku, który obsługuje funkcje jako argumenty, chociaż jest to rzadko używane w praktyce, ponieważ jest dłuższe i mniej jasne niż jawne rekursje z nazwy.

W informatyce teoretycznej anonimowa rekurencja jest ważna, ponieważ pokazuje, że można zaimplementować rekurencję bez wymagania nazwanych funkcji. Jest to szczególnie ważne w przypadku rachunku lambda , który ma anonimowe funkcje jednoargumentowe, ale jest w stanie obliczyć dowolną funkcję rekurencyjną. Ta anonimowa rekurencja może być generowana ogólnie za pomocą kombinatorów stałoprzecinkowych .

Używać

Anonimowa rekurencja jest przede wszystkim przydatna do umożliwienia rekurencji anonimowym funkcjom , zwłaszcza gdy tworzą one domknięcia lub są używane jako wywołania zwrotne , aby uniknąć konieczności wiązania nazwy funkcji.

Anonimowa rekurencja polega przede wszystkim na wywołaniu „bieżącej funkcji”, co skutkuje bezpośrednią rekurencją . Możliwa jest anonimowa rekurencja pośrednia , na przykład przez wywołanie „osoby wywołującej (poprzednia funkcja)” lub, rzadziej, przejście dalej w górę stosu wywołań , co można połączyć w łańcuch, aby uzyskać wzajemną rekurencję . Samoodniesienie „bieżącej funkcji” jest funkcjonalnym odpowiednikiem słowa kluczowego „ to ” w programowaniu obiektowym , umożliwiając odniesienie się do bieżącego kontekstu.

Anonimowej rekurencji można również użyć do nazwanych funkcji, zamiast wywoływać je po imieniu, powiedzmy, aby określić, że dana funkcja jest rekursywna dla bieżącej funkcji, lub aby umożliwić zmianę nazwy funkcji bez konieczności zmiany nazwy, w której się ona wywołuje. Jednak ze względu na styl programowania generalnie się tego nie robi.

Alternatywy

Nazwane funkcje

Zwykłą alternatywą jest użycie nazwanych funkcji i nazwanej rekurencji. Biorąc pod uwagę funkcję anonimową, można to zrobić albo przez powiązanie nazwy z funkcją, jak w nazwanych wyrażeniach funkcji w JavaScript, albo przez przypisanie funkcji do zmiennej, a następnie wywołanie zmiennej, jak w instrukcjach funkcji w JavaScript. Ponieważ języki, które zezwalają na funkcje anonimowe, generalnie pozwalają na przypisywanie tych funkcji do zmiennych (jeśli nie do funkcji pierwszej klasy), wiele języków nie zapewnia sposobu odniesienia się do samej funkcji i wyraźnie odrzuca anonimową rekurencję; przykłady obejmują Go .

Na przykład w JavaScript funkcję silni można zdefiniować za pomocą anonimowej rekurencji jako takiej:

     
              
 [  1  ,  2  ,  3  ,  4  ,  5  ].  map  (  funkcja  (  n  )  {  return  (  !  (  n  >  1  ))  ?  1  :  argumenty  .  wywoływany  (  n  -  1  )  *  n  ;  });

Przepisane w celu użycia nazwanego wyrażenia funkcyjnego daje:

      
              
 [  1  ,  2  ,  3  ,  4  ,  5  ].  map  (  funkcja  silnia  (  n  )  {  return  (  !  (  n  >  1  ))  ?  1  :  silnia  (  n  -  1  )  *  n  ;  });

Przekazywanie funkcji jako argumentów

Nawet bez mechanizmów odwołujących się do bieżącej funkcji lub funkcji wywołującej, anonimowa rekurencja jest możliwa w języku, który dopuszcza funkcje jako argumenty. Odbywa się to poprzez dodanie kolejnego parametru do podstawowej funkcji rekurencyjnej i użycie tego parametru jako funkcji dla wywołania rekurencyjnego. Tworzy to funkcję wyższego rzędu, a samo przekazanie tej funkcji wyższego rzędu umożliwia anonimową rekurencję w ramach rzeczywistej funkcji rekurencyjnej. Można to zrobić całkowicie anonimowo, stosując kombinator punktów stałych do tej funkcji wyższego rzędu. Jest to głównie przedmiotem zainteresowania akademickiego, szczególnie w celu wykazania, że rachunek lambda ma rekurencję, ponieważ wynikowe wyrażenie jest znacznie bardziej skomplikowane niż pierwotnie nazwana funkcja rekurencyjna. I odwrotnie, użycie kombinatorów o punktach stałych można ogólnie określić jako „anonimową rekurencję”, ponieważ jest to ich godne uwagi zastosowanie, chociaż mają one inne zastosowania.

Jest to zilustrowane poniżej przy użyciu Pythona. Po pierwsze, standardowa nazwana rekurencja:

 
       0
         
          def  fakt  (  n  ):  jeśli  n  ==  :  zwróć  1  zwróć  n  *  fakt  (  n  -  1  )

Używając funkcji wyższego rzędu, aby funkcja najwyższego poziomu powtarzała się anonimowo w argumencie, ale nadal potrzebuje standardowej funkcji rekurencyjnej jako argumentu:

 
       0
         
         
         0      
      def  fakt0  (  n0  ):  if  n0  ==  :  return  1  return  n0  *  fakt0  (  n0  -  1  )  fakt1  =  lambda  f  ,  n1  :  1  if  n1  ==  else  n1  *  f  (  n1  -  1  )  fakt  =  lambda  n  :  fakt1  (  fakt0  ,  n  )

Możemy wyeliminować standardową funkcję rekurencyjną, przekazując argument funkcji do wywołania:

         0       
      fakt1  =  lambda  f  ,  n1  :  1  if  n1  ==  inaczej  n1  *  f  (  fa  ,  n1  -  1  )  fakt  =  lambda  n  :  fakt1  (  fakt1  ,  n  )

Drugi wiersz można zastąpić ogólną funkcją wyższego rzędu, zwaną kombinatorem :

       
         0       
   F  =  lambda  fa  :  (  lambda  x  :  fa  (  fa  ,  x  ))  fakt1  =  lambda  fa  ,  n1  :  1  jeśli  n1  ==  inaczej  n1  *  fa  (  fa  ,  n1  -  1  )  fakt  =  fa  (  fakt1  )

Napisane anonimowo:

            0        (  lambda  f  :  (  lambda  x  :  fa  (  fa  ,  x  )))  \  (  lambda  g  ,  n1  :  1  if  n1  ==  else  n1  *  g  (  g  ,  n1  -  1  ))

W rachunku lambda , który wykorzystuje tylko kombinatora Y. funkcje jednej zmiennej, można to zrobić za pomocą Najpierw spraw, aby funkcja wyższego rzędu dwóch zmiennych była funkcją pojedynczej zmiennej, która bezpośrednio zwraca funkcję, przez curry :

          0      
   fakt1  =  lambda  f  :  (  lambda  n1  :  1  if  n1  ==  else  n1  *  f  (  f  )(  n1  -  1  ))  fakt  =  fakt1  (  fakt1  )

Istnieją tutaj dwie operacje „stosowania do siebie funkcji wyższego rzędu”: f(f) w pierwszym wierszu i fact1(fact1) w drugim. Uwzględnienie drugiej podwójnej aplikacji w kombinatorze daje:

    
          0      
   C  =  lambda  x  :  x  (  x  )  fakt1  =  lambda  fa  :  (  lambda  n1  :  1  if  n1  ==  else  n1  *  f  (  f  )(  n1  -  1  ))  fakt  =  C  (  fakt1  )

Po odrzuceniu innych podwójnych zastosowań otrzymujemy:

    
        
          0      
   C  =  lambda  x  :  x  (  x  )  D  =  lambda  f  :  (  lambda  x  :  f  (  lambda  v  :  x  (  x  )(  v  )))  fact1  =  lambda  g  :  (  lambda  n1  :  1  jeśli  n1  ==  inaczej  n1  *  g  (  n1  -  1  ))  fakt  =  do  (  re  (  fakt1  ))

Połączenie dwóch kombinatorów w jeden daje kombinator Y :

    
        
    
          0      
   C  =  lambda  x  :  x  (  x  )  D  =  lambda  fa  :  (  lambda  x  :  fa  (  lambda  v  :  x  (  x  )(  v  )))  Y  =  lambda  y  :  C  (  D  (  y  ))  fakt1  =  lambda  g  :  (  lambda  n1  :  1  jeśli  n1  ==  inaczej  n1  *  g  (  n1  -  1  ))  fakt  =  Y  (  fakt1  )

Rozszerzenie kombinatora Y daje:

            
          0      
   Y  =  lambda  f  :  (  lambda  x  :  f  (  lambda  v  :  x  (  x  )(  v  )))  \  (  lambda  x  :  f  (  lambda  v  :  x  (  x  )(  v  )))  fakt1  =  lambda  g  :  (  lambda  n1  :  1  jeśli  n1  ==  inaczej  n1  *  g  (  n1  -  1  ))  fakt  =  Y  (  fakt1  )

Połączenie tych danych daje rekurencyjną definicję silni w rachunku lambda (anonimowe funkcje pojedynczej zmiennej):

      
                       0       (  lambda  f  :  (  lambda  x  :  f  (  lambda  v  :  x  (  x  )(  v  )))  (  lambda  x  :  f  (  lambda  v  :  x  (  x  )(  v  ))))  \  (  lambda  g  :  (  lambda  n1  :  1  jeśli  n1  ==  inaczej  n1  *  g  (  n1  -  1  )))

Przykłady

APL

W APL bieżący dfn jest dostępny przez ∇ . Pozwala to na anonimową rekurencję, na przykład w tej implementacji silni:

   0    

   0        
          {  =  ⍵:  1  ⋄  ⍵  ×  ∇  ⍵  -  1  }  5  120  {  =  ⍵:  1  ⋄  ⍵  ×  ∇  ⍵  -  1  }  ¨  ⍳  10  ⍝ zastosowane do każdego elementu od 0 do 9  1  1  2  6  24  120  720  5040  40320  362880

JavaScript

W JavaScript bieżąca funkcja jest dostępna poprzez arguments.callee , podczas gdy funkcja wywołująca jest dostępna poprzez arguments.caller . Umożliwiają one anonimową rekurencję, na przykład w tej implementacji silni:

     
               
 [  1  ,  2  ,  3  ,  4  ,  5  ].  map  (  funkcja  (  n  )  {  return  (  !  (  n  >  1  ))  ?  1  :  argumenty  .  wywoływany  (  n  -  1  )  *  n  ;  });

Perl

Począwszy od Perla 5.16, bieżący podprogram jest dostępny za pośrednictwem tokena __SUB__ , który zwraca odniesienie do bieżącego podprogramu lub undef poza podprogramem. Pozwala to na anonimową rekurencję, na przykład w następującej implementacji silni:


  

  
       
      0
           
     
  #!/usr/bin/perl  użyj  funkcji  ":5.16"  ;  print  sub  {  mój  $x  =  przesunięcie  ;  $x  >  ?  $x  *  __SUB__  ->  (  $x  -  1  )  :  1  ;  }  ->  (  5  ),  "\n"  ;

R

W R bieżąca funkcja może być wywołana za pomocą Recall . Na przykład,

0  
    0 
      
 sapply  (  :  5  ,  funkcja  (  n  )  {  if  (  n  ==  )  return  (  1  )  n  *  Recall  (  n  -  1  )  })

Nie zadziała jednak, jeśli zostanie przekazany jako argument do innej funkcji, np. lapply , wewnątrz definicji funkcji anonimowej. W takim przypadku można użyć sys.function(0) . Na przykład poniższy kod rekursywnie wyrównuje listę do kwadratu:

 
   
     0
    
    
  
     (  funkcja  (  x  )  {  if  (  is.list  (  x  ))  {  lapply  (  x  ,  sys.function  (  ))  }  else  {  x  ^  2  }  }) (  lista  (  lista  (  1  ,  2  ,  3  ),  lista  (  4  ,  5  )))