تكامل لامدا

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

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

حساب لامدا له تطبيقات في مجالات مختلفة في الرياضيات، الفلسفة، [2] اللسانيات، [3][4] وعلم الحاسوب.[5] وقد لعب حساب لامدا دورا هاما في تطوير نظرية لغات البرمجة. تطبق لغات البرمجة الوظيفية حساب لامدا. حساب لامدا أيضا هو موضوع البحث الحالي في نظرية الأصناف.[6]

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

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

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

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

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

تعريف: نعرف مجموعة المتغيرات الحرة تكراريا على الشكل الآتي:

FV(x)={x}

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

FV(MN)=FV(M) ∪ FV(N)

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

مثال: لتعتبر الحد الآتي:    xv(λy.(λz.yv)w  ، بوضع الأقواس سنحصل على العبارة المقوسة الآتية:

P=(((xv)(λy.(λz.(yv)))w)  

المتغيرات الحرة في P هي  x و v و w أما y فهو متغير مقيد، العامل λx له نفس دور السور x∀ في منطق المحمولات.

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

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

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

(λx.x(xy))N= (λx.x(xy))[x :=N]= N(Ny)

·      الدالة λ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 ، بينما الصيغة الثانية تسمى بالصيغة المختزلة أو المقلصة. سنرمز لهذا التحويل بالرمز ⊳_β الصيغة المختصرة تكون على الشكل (λx.A)M إذا طبقنا اختزال-بيطا  على هذه الصيغة القابلة للاختزال ستتحول إلى الصيغة:

(λx.A)M  ⊳β  A[x :=M]

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

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

مثال: لنأخذ  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  ، وذلك غير مسموح به.

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

مثال:

λx.xy ⊳α  λz.zy

سنطبق تحويل ألفا على المثال السابق:

λxy.yx ⊳α  λwy.yw ⊳α  λwz.zw

الآن، بعد إجراء تحويل ألفا نكون في وضعية إجراء تحويل بيطا على الشكل الآتي:

Fyx=((λw.(λz.zw))y)x ⊳β (λz.zy)x   ⊳β  xy

عموما يجب الالتزام بالقواعد الآتية في عملية الاستبدال:

• بوابة رياضيات
• بوابة علم الحاسوب
• بوابة منطق