Anonymous recursion

Anonymous recursion
Bayanai
Ƙaramin ɓangare na	recursion (en)
Uses (en)	anonymous function (en)

A kimiyyar kwamfuta, maimaitawar da ba a sani ba ita ce maimaitawa wanda baya kiran aiki da suna. Ana iya yin wannan ko dai a bayyane, ta hanyar yin amfani da aiki mafi girma - wucewa a cikin aiki azaman hujja da kiransa - ko a fakaice, ta hanyar fasalin tunani wanda ke ba mutum damar samun dama ga wasu ayyuka dangane da mahallin yanzu, musamman "aikin yanzu. "ko wani lokacin" aikin kira na aikin yanzu".

A cikin aikace-aikacen shirye-shirye, ana amfani da maimaita maimaitawa musamman a JavaScript, wanda ke ba da wuraren tunani don tallafawa shi. A cikin ayyukan shirye-shirye gabaɗaya, duk da haka, ana ɗaukar wannan salon mara kyau, kuma ana ba da shawarar sake komawa tare da ayyuka masu suna maimakon. Maimaituwa mara ma'ana ta hanyar wucewa a sarari azaman mahawara yana yiwuwa a cikin kowane harshe mai goyan bayan ayyuka azaman mahawara, kodayake wannan ba kasafai ake amfani da shi a aikace ba, saboda ya fi tsayi da ƙasa bayyananne fiye da maimaita suna.

A cikin ilimin kimiyyar kwamfuta na ka'idar, maimaitawar da ba a san su ba yana da mahimmanci, saboda yana nuna cewa mutum zai iya aiwatar da maimaitawa ba tare da buƙatar ayyuka masu suna ba. Wannan yana da mahimmanci musamman ga lissafin lambda, wanda ke da ayyukan da ba a san su ba, to amma yana iya ƙididdige duk wani aiki mai maimaitawa. Ana iya samar da wannan maimaitawar da ba a bayyana ba gabaɗaya ta hanyar haɗawa da kafaffen wuri .

Amfani

Maimaituwar da ba a sani ba ita ce farkon amfani wajen ba da damar sake dawowa don ayyukan da ba a san su ba, musamman lokacin da suka samar da rufewa ko kuma ana amfani da su azaman kiran baya, don guje wa ɗaure sunan aikin.

Maimaituwar da ba a san sunansa ba ta ƙunshi kira "aikin yanzu", wanda ke haifar da maimaitawa kai tsaye . Maimaituwa kai tsaye ba a san shi ba yana yiwuwa, kamar ta kiran “mai kira (aikin da ya gabata)”, ko kuma, da wuya, ta hanyar haɓaka tarin kira, kuma ana iya ɗaure wannan sarƙa don samar da maimaitawar juna . Bayanin kai na "aikin na yanzu" yana aiki daidai da " wannan " keyword a cikin shirye-shiryen da ya dace da abu, yana bawa mutum damar komawa ga mahallin yanzu.

Hakanan za'a iya amfani da maimaita maimaitawa don ayyukan suna, maimakon kiran su da suna, a ce mutum yana maimaituwa akan aikin na yanzu, ko don ba da damar canza sunan aikin ba tare da buƙatar canza sunan inda yake kiran kansa ba. Koyaya, dangane da salon shirye-shiryen wannan gabaɗaya ba a yin haka.

Madadin

Ayyuka masu suna

Madadin da aka saba shine a yi amfani da ayyuka masu suna da mai-maita mai suna. Idan aka ba da aikin da ba a san shi ba, ana iya yin wannan ta hanyar ɗaure suna zuwa aikin, kamar yadda yake a cikin kalmomin aiki mai suna a JavaScript, ko kuma ta sanya aikin ga maɓalli sannan kuma kiran mai canji, kamar yadda yake cikin bayanan aiki a JavaScript. Tunda harsunan da ke ba da izinin ayyukan da ba a san su ba gabaɗaya suna ba da izinin sanya waɗannan ayyuka zuwa masu canji (idan ba ayyuka na aji na farko ba), yawancin harsuna ba su samar da hanyar da za a koma ga aikin da kanta ba, kuma a sarari suna ƙin sake dawowa ba tare da suna ba; misalan sun hada da Go . ^[1]

Misali, a cikin JavaScript ana iya siffanta aikin ma'auni ta hanyar maimaitawa ba a san su ba kamar haka: ^[2]

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

An sake rubutawa don amfani da aikin magana mai suna:

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

Wucewa ayyuka azaman muhawara

Ko da ba tare da hanyoyin da za a koma zuwa aikin na yanzu ko aikin kira ba, sake dawowa ba a san shi ba zai yiwu a cikin yaren da ke ba da damar ayyuka azaman muhawara. Ana yin haka ta ƙara wani siga zuwa ainihin aikin maimaitawa da amfani da wannan siga azaman aikin maimaita kiran. Wannan yana haifar da aiki mai girma, kuma wucewa wannan babban aikin da kansa yana ba da damar sake dawowa ba tare da sunansa ba a cikin ainihin aikin maimaitawa. Ana iya yin wannan kawai ba tare da sunansa ba ta amfani da madaidaicin mai haɗawa zuwa wannan babban aikin oda. Wannan shine galibi na sha'awar ilimi, musamman don nuna cewa lissafin lambda yana da maimaitawa, saboda furucin da ya haifar ya fi rikitarwa fiye da ainihin aikin maimaitawa mai suna. Sabanin haka, ana iya kiran amfani da kafaffen mahaɗai masu nuni a gabaɗaya a matsayin "sake maimaitawa", saboda wannan sanannen amfani ne da su, kodayake suna da wasu aikace-aikace. ^[3] ^[4]

An Kuma kwatanta wannan a ƙasa ta amfani da Python. Na farko, ma'auni mai suna recursion:

def fact(n):
  if n == 0:
    return 1
  return n * fact(n - 1)

Yin amfani da aiki mafi girma don haka aikin babban matakin yana komawa ba tare da saninsa ba akan hujja, amma har yanzu yana buƙatar daidaitaccen aikin maimaitawa azaman hujja:

def fact0(n0):
  if n0 == 0:
    return 1
  return n0 * fact0(n0 - 1)
fact1 = lambda f, n1: 1 if n1 == 0 else n1 * f(n1 - 1)
fact = lambda n: fact1(fact0, n)

Za mu iya kawar da daidaitaccen aikin maimaitawa ta hanyar shigar da hujjar aikin cikin kira:

fact1 = lambda f, n1: 1 if n1 == 0 else n1 * f(f, n1 - 1)
fact = lambda n: fact1(fact1, n)

Za a iya maye gurbin layi na biyu da babban aiki mai girma wanda ake kira combinator :

F = lambda f: (lambda x: f(f, x))
fact1 = lambda f, n1: 1 if n1 == 0 else n1 * f(f, n1 - 1)
fact = F(fact1)

An rubuta ba tare da suna ba: ^[5]

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

A cikin lissafin lambda, wanda kawai ke amfani da ayyuka na maɓalli ɗaya kawai, ana iya yin wannan ta hanyar haɗin Y . Da farko sanya aikin mafi girma na masu canji biyu ya zama aiki na maɓalli ɗaya, wanda ke dawo da aiki kai tsaye, ta currying :

fact1 = lambda f: (lambda n1: 1 if n1 == 0 else n1 * f(f)(n1 - 1))
fact = fact1(fact1)

Akwai ayyuka guda biyu "neman aiki mafi girma ga kansa" a nan: f(f) a layin farko da fact1(fact1) a cikin na biyu. Fitar da aikace-aikacen sau biyu na biyu zuwa mai haɗawa yana haifar da fa'ida:

C = lambda x: x(x)
fact1 = lambda f: (lambda n1: 1 if n1 == 0 else n1 * f(f)(n1 - 1))
fact = C(fact1)

Fitar da sauran aikace-aikacen sau biyu yana haifar da fa'ida:

C = lambda x: x(x)
D = lambda f: (lambda x: f(lambda v: x(x)(v)))
fact1 = lambda g: (lambda n1: 1 if n1 == 0 else n1 * g(n1 - 1))
fact = C(D(fact1))

Haɗa mahaɗa biyu zuwa ɗaya yana haifar da mai haɗa Y :

C = lambda x: x(x)
D = lambda f: (lambda x: f(lambda v: x(x)(v)))
Y = lambda y: C(D(y))
fact1 = lambda g: (lambda n1: 1 if n1 == 0 else n1 * g(n1 - 1))
fact = Y(fact1)

Fadada haɓakar mai haɗa Y:

Y = lambda f: (lambda x: f(lambda v: x(x)(v))) \
       (lambda x: f(lambda v: x(x)(v)))
fact1 = lambda g: (lambda n1: 1 if n1 == 0 else n1 * g(n1 - 1))
fact = Y(fact1)

Haɗa waɗannan yana haifar da ma'anar ma'anar ma'ana a cikin lissafin lambda (ayyukan da ba a san su ba na maɓalli ɗaya): ^[6]

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

Misalai

APL

A cikin APL, dfn na yanzu yana samuwa ta hanyar ∇ . Wannan yana ba da damar sake dawowa da ba a san sunansa ba, kamar a cikin wannan aiwatar da abubuwa:

  {0=⍵:1 ⋄ ⍵×∇ ⍵-1} 5
120
  {0=⍵:1 ⋄ ⍵×∇ ⍵-1}¨ ⍳10  ⍝ applied to each element of 0 to 9
1 1 2 6 24 120 720 5040 40320 362880

JavaScript

A cikin JavaScript, ana iya samun damar aikin na yanzu ta hanyar arguments.callee, yayin da aikin kira ke samun dama ta arguments.caller . Waɗannan suna ba da damar sake dawowa da ba a san su ba, kamar a cikin wannan aiwatar da abubuwa: ^[2]

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

Perl

Farawa tare da Perl 5.16, ana samun dama ga subroutine na yanzu ta hanyar alamar __SUB__, wanda ke dawo da tunani zuwa ga abin da ke cikin halin yanzu, ko undef a waje da subroutine. ^[7] Wannan yana ba da damar sake dawowa da ba a san suna ba, kamar a cikin aiwatar da abubuwa masu zuwa:

#!/usr/bin/perl
use feature ":5.16";

print sub {
  my $x = shift;
  $x > 0
  ? $x * __SUB__->( $x - 1 )
  : 1;
}->(5), "\n";

R

A cikin R, ana iya kiran aikin na yanzu ta amfani da Recall . Misali,

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

Ba zai yi aiki ba, duk da haka, idan an wuce azaman hujja zuwa wani aiki, misali lapply, cikin ma'anar aikin da ba a san shi ba. A wannan yanayin, ana iya amfani da sys.function(0) . ^[8] Misali, lambar da ke ƙasa tana mirgine jeri akai-akai:

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

Magana

↑ Issue 226: It's impossible to recurse a anonymous function in Go without workarounds.
↑ ^2.0 ^2.1 answer by olliej, Oct 25 '08 to "Why was the arguments.callee.caller property deprecated in JavaScript?", StackOverflow
↑ This terminology appear to be largely folklore, but it does appear in the following:
↑ The If Works Deriving the Y combinator, January 10th, 2008
↑ Hugo Walter's answer to "Can a lambda function call itself recursively in Python?"
↑ Nux's answer to "Can a lambda function call itself recursively in Python?"
↑ Perldoc, "The 'current_sub' feature", perldoc feature
↑ agstudy's answer to Get currently called function to write anonymous recursive function at StackOverflow

[1] Issue 226: It's impossible to recurse a anonymous function in Go without workarounds.

[olliej-2] 2.0 ^2.1 answer by olliej, Oct 25 '08 to "Why was the arguments.callee.caller property deprecated in JavaScript?", StackOverflow

[3] This terminology appear to be largely folklore, but it does appear in the following:

[ifworks-4] The If Works Deriving the Y combinator, January 10th, 2008

[5] Hugo Walter's answer to "Can a lambda function call itself recursively in Python?"

[6] Nux's answer to "Can a lambda function call itself recursively in Python?"

[7] Perldoc, "The 'current_sub' feature", perldoc feature

[8] study's answer to Get currently called function to write anonymous recursive function at StackOverflow

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Anonymous recursion
Bayanai
Ƙaramin ɓangare na	recursion ^(en)
Uses ^(en)	anonymous function ^(en)