التكرار المجهول

البديل المعتاد هو استخدام الدوال المسماة والاستدعاء الذاتي المسمى. عند وجود دالة مجهولة، يمكن القيام بذلك إما بربط اسم بالدالة، كما هو الحال في تعابير الدوال المسماة في جافا سكريبت، أو بإسناد الدالة إلى متغير ثم استدعاء هذا المتغير، كما هو الحال في عبارات الدوال في جافا سكريبت. ولأن اللغات التي تسمح بالدوال المجهولة تسمح عمومًا بإسناد هذه الدوال إلى متغيرات (إن لم تكن دوالًا من الدرجة الأولى)، فإن العديد من اللغات لا توفر طريقة للإشارة إلى الدالة نفسها، وترفض صراحةً الاستدعاء الذاتي المجهول؛ ومن الأمثلة على ذلك لغة جو . ^{[ 1 ]}

على سبيل المثال، في جافا سكريبت، يمكن تعريف دالة المضروب من خلال الاستدعاء الذاتي المجهول على النحو التالي: ^{[ 2 ]}

[ 1 ، 2 ، 3 ، 4 ، 5 ]. Map ( function ( n ) { return ( ! ( n > 1 )) ? 1 : الوسيطات . callee ( n - 1 ) * n ; });

إعادة كتابة الكود باستخدام تعبير دالة مُسماة ينتج عنه:

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

حتى بدون آليات للإشارة إلى الدالة الحالية أو الدالة المستدعِية، يُمكن استخدام الاستدعاء الذاتي المجهول في لغة تسمح باستخدام الدوال كوسائط. يتم ذلك بإضافة مُعامل آخر إلى الدالة الاستدعائية الأساسية واستخدام هذا المُعامل كدالة للاستدعاء الذاتي. يُنشئ هذا دالة من رتبة أعلى، ويُتيح تمرير هذه الدالة نفسها الاستدعاء الذاتي المجهول داخل الدالة الاستدعائية الأصلية. يُمكن القيام بذلك بشكل مجهول تمامًا بتطبيق مُركِّب ذي نقطة ثابتة على هذه الدالة من الرتبة الأعلى. يُعد هذا الأمر ذا أهمية أكاديمية في المقام الأول، لا سيما لإظهار أن حساب لامدا يدعم الاستدعاء الذاتي، حيث أن التعبير الناتج أكثر تعقيدًا بشكل ملحوظ من الدالة الاستدعائية الأصلية المُسماة. في المقابل، يُمكن الإشارة إلى استخدام مُركِّبات النقطة الثابتة بشكل عام باسم "الاستدعاء الذاتي المجهول"، حيث يُعد هذا استخدامًا بارزًا لها، على الرغم من وجود تطبيقات أخرى لها. ^{[ 3 ] [ 4 ]}

يوضح الشكل أدناه ذلك باستخدام لغة بايثون . أولاً، الاستدعاء الذاتي المسمى القياسي:

دالة fact ( n ): إذا كان n يساوي 0 : أرجع 1 أرجع n * fact ( n - 1 )

استخدام دالة من الرتبة العليا بحيث تستدعي الدالة ذات المستوى الأعلى بشكل مجهول على وسيط، ولكن لا تزال هناك حاجة إلى الدالة الاستدعائية القياسية كوسيط:

دالة fact0 ( n0 ): إذا كان n0 يساوي 0 : أرجع 1، أرجع n0 * fact0 ( n0 - 1 ). fact1 = lambda f , n1 : 1 إذا كان n1 يساوي 0، وإلا n1 * f ( n1 - 1 ). fact = lambda n : fact1 ( fact0 , n ).

يمكننا الاستغناء عن الدالة التكرارية القياسية عن طريق تمرير وسيط الدالة إلى الاستدعاء:

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

يمكن استبدال السطر الثاني بدالة عامة من الرتبة العليا تسمى المُركِّب :

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 )

كُتب بشكل مجهول: ^{[ 5 ]}

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

في حساب لامدا ، الذي يستخدم فقط دوال متغير واحد، يمكن تحقيق ذلك عبر مُركِّب Y. أولًا، اجعل الدالة ذات الرتبة الأعلى لمتغيرين دالة لمتغير واحد، والتي تُعيد دالة مباشرة، وذلك عن طريق تطبيق تقنية التخصيص الجزئي (currying ).

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

يوجد هنا عمليتان لتطبيق دالة من رتبة أعلى على نفسها: f(f)في السطر الأول fact1(fact1)وفي السطر الثاني. وبتحليل عملية التطبيق الثانية المزدوجة إلى مُركِّب ، نحصل على:

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

وبإخراج عامل التطبيق المزدوج الآخر نحصل على:

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 ))

يؤدي دمج المجموعتين في مجموعة واحدة إلى الحصول على المجموعة 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 )

يؤدي توسيع مُركِّب 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 )

يؤدي الجمع بين هذه إلى تعريف متكرر للمضروب في حساب التفاضل والتكامل لامدا (الدوال المجهولة لمتغير واحد): ^{[ 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 )))

في لغة APL ، يمكن الوصول إلى دالة التعريف الحالية عبر ∇. وهذا يسمح بالتكرار المجهول، كما هو الحال في هذا التطبيق لحساب المضروب:

{ 0 = ⍵: 1 ⋄ ⍵ × ∇ ⍵ - 1 } 5 120 { 0 = ⍵: 1 ⋄ ⍵ × ∇ ⍵ - 1 } ¨ ⍳ 10 ⍝ مطبقة على كل عنصر من 0 إلى 9 1 1 2 6 24 120 720 5040 40320 362880

في جافا سكريبت ، يمكن الوصول ^إلى الدالة الحالية arguments.calleeعبر ^{` _}arguments.caller ...

[ 1 ، 2 ، 3 ، 4 ، 5 ]. Map ( function ( n ) { return ( ! ( n > 1 )) ? 1 : الوسيطات . callee ( n - 1 ) * n ; });

ابتداءً من بيرل 5.16، يمكن الوصول إلى الروتين الفرعي الحالي عبر __SUB__الرمز المميز، الذي يُعيد مرجعًا إلى الروتين الفرعي الحالي، أو undefمن خارج الروتين الفرعي. ^{[ 7 ]} وهذا يسمح بالاستدعاء الذاتي المجهول، كما في تطبيق حساب المضروب التالي:

#!/usr/bin/env perl use feature ":5.16" ;print sub { my $x = shift ; $x > 0 ? $x * __SUB__ -> ( $x - 1 ) : 1 ; } -> ( 5 ), "\n" ;

في لغة R ، يمكن استدعاء الدالة الحالية باستخدام Recall. على سبيل المثال،

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

لن ينجح ذلك، مع ذلك، إذا تم تمريره كوسيط إلى دالة أخرى، مثلاً lapply، داخل تعريف دالة مجهولة. في هذه الحالة، sys.function(0)يمكن استخدام ^{[ 8 ]} . على سبيل المثال، يقوم الكود أدناه بتربيع قائمة بشكل متكرر:

( دالة ( س ) { إذا ( كانت قائمة ( س )) { تطبيق ( س ، دالة النظام ( 0 )) } وإلا { س ^ 2 } })( قائمة ( قائمة ( 1 ، 2 ، 3 )، قائمة ( 4 ، 5 )))