تكامل لامدا

FV(λx.M)=FV(M)-{x}

ومن ناحية أخرى، ما هي المتغيرات الحرة في  M=x(λy.xy) ؟ المتغير x يرد حرا مرتين، بينما المتغير y فهو مقيد، لذلك نكتب: FV(M)={x} ، قد يرد أحيانا المتغير حرا ومقيدا مثل العبارة: y(λy.y).

في هذا الإطار، FV(MN)=FV(M) ∪ FV(N)تكون M مغلوقة أو دالة توافقية  إذا كان FV(M)= ∅ ، نرمز لمجموعة الحدود المغلوقة بالرمز 0Λ

إضافةً إلى ذلك، مثال: لتعتبر الحد الآتي:    xv(λy.(λz.yv)w  ، بوضع الأقواس سنحصل على العبارة المقوسة الآتية:P=(((xv)(λy.(λz.(yv)))w)  المتغيرات الحرة في P هي  x و v و w أما y فهو متغير مقيد، العامل λx له نفس دور السور x∀ في منطق المحمولات.

المتغيرات الحرة والمقيدة

في هذا الإطار، يتعين في البداية معرفة نطاق العامل λx  في عبارة لامبدا، سنستعين على ذلك بالمثال الآتي، لنعتبر الحد P

b) (λx.y)N ⊳β y

• c) (λx.(λy.yx)z)v ⊳β (λy.yx)z)[x :=v] ≡ (λy.yv)z ⊳β yv[y :=z] ≡ zv
• d) (λx.xx) (λx.xx) ⊳β (λx.xx)[x := λx.xx] ≡ (λx.xx) (λx.xx)
• ⊳β (λx.xx)[x := λx.xx] ≡ (λx.xx) (λx.xx)
• …..
• e) (λx.xxy)(λx.xxy) ⊳β (λx.xxy)(λx.xxy) y

تحويل بيطا

ومن ناحية أخرى، موضوع هذا المحور هو طريقة حساب حدود لامبدا، رأينا سابقا أن الصيغة القابلة للاختزال تكون على الصورة (λx.A)M ، إذا طبقنا اختزال-بيطا  على هذه الصيغة ستتحول إلى الصيغة المقلصة:(λx.A)M ⊳β A[x :=M]حيث حل M محل المتغير الحر  x في الحد A ، عموما إذا تضمن الحد P الصيغة القابلة للاختزال  (λx.A)M ثم استبدلنا  هذه الصيغة الأخيرة بــ A[x :=M] فحصلنا على  حد جديد P' ، نقول حينئد أننا اختزلنا P إلى P’ ، ونكتب:P ⊳β P'إذا قمنا بتغيير P إلى Q بعد سلسلة من التقليصات وإعادة تسمية المتغيرات المقيدة، نقول أننا قمنا باختزال-بيطا P إلى Q فنكتب:P ⊳β Q

مثالa) (λx.x(xy))N ⊳β N(Ny)

⊳β (λx.xxy)(λx.xxy) yy

…..

وفي السياق ذاته، تعريف 20 : (الاختزال بخطوة وحيدة ⊳β1 )  نقول أن A تختزل بخطوة وحيدة إلى B (نرمز لها بالرمز A  ⊳β1  B)  في حالة ما تضمن الحد A جزءَ C=(λx.M)N  ، ولا تختلف A عن B  إلا بكون الجزء C مستبدل في B بالجزء المقلص  M[x :=N]

وفي السياق ذاته، سنحاول التمييز بين نوعين من الاختزالات اختزال بخطوة وحيدة واختزال بعد سلسلة من الاختزالات:

ومن ناحية أخرى، في المثال السابق  b  الحد (λx.y)N   مختزل بخطوة وحيدة إلى y نكتب:   (λx.y)N ⊳β1 yكذلك a مختزلة بخطوة وحيدة:(λx.x(xy))N ⊳β1 N(Ny)تعريف 21  : سلسلة الاختزالات من حد A إلى الحد B هي سلسلة متناهية من الحدود s1….sn تبدأ من A وتنتهي بــ B حيث إن حدين متجاورين (s1,s2)  يحققان الخاصية الآتية: sk ⊳β1 sk+1 في المثال السابق نمثل لسلسلة الاختزالات بــ  c :(λx.(λy.yx)z)v , (λy.yv)z , zv

P=(λy.yx(λx.y(λy.z)x))vw

من جانب آخر، تعريف: يكون المتغير x في P مقيدا إذا كان يوجد في نطاق λx وإلا سُمي حرا.

من جهة ثانية، نطاق العامل λy الذي يوجد في أقصى اليسار هو العبارة yx(λx.y(λy.z)x ، ونطاق λx هوy(λy.z)x ، أما نطاق العامل λy الذي يوجد على اليمين هو z .

في هذا الإطار، مجموعة المتغيرات الحرة في P  يرمز لها بالرمز:  FV(P)، والحد المغلوق هو الحد الذي لا يتضمن أي متغير حر.

من جانب آخر، تعريف: نعرف مجموعة المتغيرات الحرة تكراريا على الشكل الآتي:FV(x)={x}

مثال: λx.xy ⊳α λz.zy

ومن جهة أخرى، سنطبق تحويل ألفا على المثال السابق:λxy.yx ⊳α λwy.yw ⊳α λwz.zw الآن، بعد إجراء تحويل ألفا نكون في وضعية إجراء تحويل بيطا على الشكل الآتي:Fyx=((λw.(λz.zw))y)x ⊳β (λz.zy)x ⊳β xyعموما يجب الالتزام بالقواعد الآتية في عملية الاستبدال:

(λxy.yx)uv ⊳β (λy.yu)v ⊳β vu

(λx.xxy)(λy.yz) ⊳β (λy.yz) (λy.yz)y ≡ ((λy.yz) (λy.yz))y

⊳β ((λy.yz)z)y ⊳β zzy

من جانب آخر، الإمكانية الأولى:(λx.(λy.yx)z)v ⊳β (λy.yv)z) ⊳β zvالإمكانية الثانية:

في هذا الإطار، (λx.(λy.yx)z)v ⊳β (λy.yv)z) ⊳β zvفي هذه الإمكانية اختزلنا الحد (z(λy.yx).الذي يوجد ضمن الحد الأكبر المتضمن له. يلاحظ أن كلا الامكانيتين أفضتا إلى صيغة طبيعية واحدة، وهذه خاصية لابد أن تتميز بها جميع الأنساق الحوسبية أي يتوجب أن توجد صيغة طبيعية واحد مهما اختلفت الطرق المؤدية إليها.

إضافةً إلى ذلك، ملاحظة مهمة تتعلق بكون بعض الحدود توجد أكثر من طريقة في اختزالها، إذا عدنا إلى الحد c الذي يوجد في  المثال 87، يمكن أن نختزل هذا الحد بطريقتين مختلفتين كما يتبين من الاختزالات الممكنة الآتية:

[1] - normal form

الاستبدال في حساب لامبدا

كذلك، مثال: لنأخذ  F≡λxy.yx ونطبقها على M وN:FMN ⊳β ((λx.(λy.yx) M)N ⊳β (λy.yM)N ⊳β NMهذه العملية كما رأينا تعكس ترتيب الحدود، إذا طبقنا F على yx من المنتظر أن نحصل على  Fyx=xy لكن الأمر ليس كذلك:Fyx=((λx.(λy.yx))y)x ⊳β (λy.yy)x=xxوبالتالي فإن xy=xx وهذا تناقض، من هذه العبارة يمكن أن نشتق أي شيء، لذلك لابد من قواعد تضبط عملية الاستبدال تجنبنا الوقوع في هذه المفارقات، السؤال أين الخلل في التحويل السابق؟ نشأ الخلل في المرحلة:( λx.(λy.yx) )y=λy.yyالمتغير الحر y أصبح مقيدا بعد أن قمنا بعملية استبداله بــ x في λy.yx  ، وذلك غير مسموح به.

كذلك، الصيغة المختصرة تكون على الشكل (λx.A)M إذا طبقنا اختزال-بيطا  على هذه الصيغة القابلة للاختزال ستتحول إلى الصيغة:(λx.A)M ⊳β A[x :=M]

ومن ناحية أخرى، إذن لابد من وضع قاعدة تحول دون أن يفضي تحويل الحدود إلى مفارقات، لأجل ذلك سنعرف تحويلا آخر، إلى جانب  تحويل بيطا، سنسميه  بتحويل ألفا α-conversion سنرمز لهذا التحويل بالرمز  ⊳α. يسعى تحويل-ألفا إلى إعادة تسمية المتغيرات المقيدة.

كذلك، أمثلة: سنقوم بتطبيق التجريد λx.x(xy)) على N ونرى كيف تتم عملية الاستبدال، بداية سنقوم بالبحث عن المتغيرات الحرة x في الحد x(xy)  لاحقًا سنقوم باحلال N مكان هذه المتغيرات الحرة:(λx.x(xy))N= (λx.x(xy))[x :=N]= N(Ny)

وفي هذا السياق، عملية الاستبدال في الحدود أحيانا لا تسير وفق الخطة التي شرحناها سابقا، أحيانا الاستبدالات قد تفضي إلى مفارقات، لنتأمل في المثال الآتي:

من جانب آخر، نعرف على حدود لامبدا عملية الاستبدال التي نرمز لها بالرمز: M[x :=N]   ، وتشير إلى تعويض المتغير الحر x في M بــ N .

حيث حل M محل x في الحد A .

كذلك، ·      الدالة λx.y تمثل الدالة الثابتة  تأخذ القيمة y مهما يكن الموضوع x ، لأنه عندما نطبقها على N تنتج y:(λx.y)N =(λx.y)[x :=N]= y·      الدالة λx.x تمثل دالة المطابقة تأخذ الموضوع x ثم تعطي نفس الموضوع x :(λx.x)N = (λx.x) [x :=N]= Nيسمى هذا التحويل الذي نقلنا من الصيغة (λx.x)N    إلى الصيغة  [x :=N](λx.x) حيث أحللنا N مكان x بتحويل بيطا أو اختزال بيطا، الصيغة الأولى  N(λx.x)   تسمى العبارة القابلة  للاختزال β-redex ، بينما الصيغة الثانية تسمى بالصيغة المختزلة أو المقلصة. سنرمز لهذا التحويل بالرمز ⊳β

الصيغة الطبيعية

إضافةً إلى ذلك، تعريف: الحد Q الذي لا يتضمن أية صيغة قابلة للاختزال β-redex يسمى بصيغة طبيعية (أو بعبارة أخرى يوجد في صيغة طبيعية ونختزلها في الرمز nf)، إذا اختزلنا P إلى الحد Q في صيغة طبيعية nf ، عندئذ يسمى Q بالصيغة الطبيعية لــ P .

وفي السياق ذاته، سنختزل العبارات الآتية إلى صيغها الطبيعية:(λx.xy)(λu.vuu) ⊳β (λu.vuu) y ⊳β vyy

وفي السياق ذاته، هذه الملاحظة ستجرنا إلى تعريف خاصية جد مهمة يتعلق الأمر بالصيغة الطبيعية[1]  .

ومن ناحية أخرى، ملاحظة هامة في الحوسبة تستحق أن نقف عندها مفادها أن عملية اختزال الحدود  ) مثل a و b  و (c قد تتوقف عند صيغة محددة، إذ توقف الاختزال عند الصيغة N(Ny) بالنسبة لـ a ، وتوقف الاختزال عند الصيغة zv بالنسبة لــ c  ولم يبق لنا من سبيل إلى اختزالها أكثر، لأنه لا توجد صيغة قابلة للاختزال تنتظر منا أن نقلصها هذا من جهة، أما من جهة ثانية  توجد حدود من قبيل d و e لا تتوقف عملية الاختزال بل تستمر إلى غير نهاية؛ فكلما اختزلنا صيغة قابلة للاختزال إلا وظهرت في النتيجة صيغ أخرى قابلة للاختزال تنتظر الاختزال، يُرمز للحد (λx.xx) (λx.xx)   الذي يوجد في d بالرمز Ω .

وفي السياق ذاته، في c من المثال السابق يعتبر الحد zv  صيغة طبيعية لــ (λx.(λy.yx)z)v   وفي a الحد N(Ny)  هو الصيغة الطبيعية لــ  (λx.x(xy))N الحد (λx.xx)(λx.xx)=Ω الموجود في d من المثال   لا توجد له صيغة طبيعية، دائما يختزل إلى نفسه.

الشرح والتطبيقات

كذلك، حساب لامدا هو تورنغ كاملة وهو نموذج عام من الحوسبة والتي يمكن استخدامها لمحاكاة أي آلة تورنغ ذات شريط واحد. تحمل الاسم الحرف اليوناني لامدا (λ)، ويستعمل في تعبيرات لامدا وشروط لامدا لاسناد متغير في الوظيفة أو التابع.

علاوةً على ذلك، حساب لامدا له تطبيقات في مجالات مختلفة في الرياضيات، الفلسفة، اللسانيات، وعلم الحاسوب. وقد لعب حساب لامدا دورا هاما في تطوير نظرية لغات البرمجة. تطبق لغات البرمجة الوظيفية حساب لامدا. حساب لامدا كذلك هو موضوع البحث الحالي في نظرية الأصناف.

وعلى صعيد آخر، يمكن أن يكون حساب لامدا منمطاً أو غير منمط. في حساب لامدا المنمط لا يمكن تطبيق الوظائف إلا إذا كانت قادرة على قبول أنماط البيانات المدخلة.

أمثلة

وفي السياق ذاته، (λy.x(λx. x))[x :=λy.xy] ⊳α (λy.x(λz. z))[x :=λy.xy] ≡λy. λy.xy(λz. z)

من جهة ثانية، سنجري مجموعة من الاستبدالات على الحدود الآتية:(λy.x(λw.vwx))[x :=uv] ⊳α (λy.(uv)(λw.vw(uv)))

ومن ناحية أخرى، (y(λv.xv))[x :=λy.vy] ⊳α (y(λz.xz))[x :=λy.vy] ≡ y(λz.( λy.vy)z)