التكرير (تقنية في البرمجة الوظيفية)
المحتويات
على سبيل التعريف، في الرياضيات وعلم الحاسوب، يُعدّ التكرير أو الكرّية أو التقييس ، تقنية لتحويل دالة تأخذ عدة وسائط إلى تسلسل من عائلات الدوال، تأخذ كل واحدة منها وسيطًا واحدًا فقط. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
من جانب آخر، التحوير الكاري مرتبط بالتطبيق الجزئي، لكنه ليس الشيء نفسه. يمكن استخدام المثال أعلاه لتوضيح التطبيق الجزئي؛ وهو مشابه جدًا. التطبيق الجزئي هو الدالة التي تأخذ الزوج و كوسيطين معًا، وتُعيد وباستخدام الترميز ذاته، تكون صيغة التطبيق الجزئي هي ومكتوبة بهذه الطريقة، يمكن اعتبار دالة التطبيق مقابلة (adjoined) لدالة التحوير الكاري.
من جهة ثانية، يمكن تعريف التحوير الكاري لدالة تحتوي على أكثر من وسيطين باستخدام الاستقراء.
ومن جهة أخرى، في المثال النموذجي، نبدأ بدالة تأخذ وسيطين، أحدهما من والآخر من ، وتنتج عناصر في الشكل المحوَّر من هذه الدالة يعامل الوسيط الأول كمعامل، لتكوين عائلة من الدوال وتُنظَّم هذه العائلة بحيث يوجد لكل عنصر في دالة واحدة فقط
وفي هذا الصدد، في هذا المثال، تصبح نفسها دالة، تأخذ كوسيط، وتُعيد دالة تربط كل بـ التمثيل الرمزي المناسب لذلك طويل نوعًا ما. فالدالة تنتمي إلى مجموعة الدوال أما فتنتمي إلى مجموعة الدوال وعليه، فإن الشيء الذي يربط بـ سيكون من النوع وبهذا الترميز، فإن هي دالة تأخذ عناصر من المجموعة الأولى، وتُعيد عناصر من المجموعة الثانية، وتُكتب بالشكل هذا مثال غير رسمي بعض الشيء؛ إذ تُعرض تعريفات أدق لما يُقصد بـ "عنصر" و"دالة" لاحقًا. وتختلف هذه التعريفات حسب السياق، وتأخذ أشكالًا متعددة تبعًا للنظرية المعتمدة.
وعلى صعيد آخر، إلغاء التكرير هو تحويل الثنوية المقابل للتكرير، ويمكن اعتباره شكلاً من نزع التأدية. إذ يأخذ دالة تُعيد كقيمة دالة أخرى ، ويُنتج دالة جديدة تأخذ كوسائط الوسيطات الخاصة بكل من و، وتُعيد كنتيجة تطبيق ثم على تلك الوسائط. ويمكن تكرار هذه العملية.
وفي هذا السياق، قُدّمت فكرة التحوير الكاري لأول مرة بواسطة جوتلوب فريجه, وطُوّرت لاحقًا بواسطة موسى شونفينكل، وطُوّر لاحقًا بواسطة هاسكل كاري.
كذلك، التحوير الكاري مفيد في السياقات العملية والنظرية على حد سواء. ففي البرمجة الوظيفية ولغات البرمجة الأخرى، يوفّر طريقة لإدارة تمرير الوسيطات إلى الدوال والتعامل مع الاستثناءات بشكل تلقائي. أما في علم الحاسوب النظري، فهو يوفّر وسيلة لدراسة الدوال متعددة الوسائط ضمن نماذج نظرية أبسط لا تقبل سوى وسيط واحد. وتُعد الفئات الأحادية المغلقة الإطار الأكثر تعميمًا للمفهوم الصارم للتحوير الكاري وعكسه، وهي تشكّل أساسًا لتعميم واسع لمقابلة تطابق كاري-هوارد بين الإثباتات والبرامج لتشمل بنيات أخرى كثيرة، مثل ميكانيكا الكم، والكوبوردية، ونظرية الأوتار.
التاريخ
من جهة ثانية، الاسم "تكرير" أو "تقييس" يعود إلى عالم المنطق هاسكل كاري، الذي استعمل هذا المفهوم على نطاق واسع، لكن كان قد طرح الفكرة قبل كاري بست سنوات.
وفي هذا الصدد، أما أصل مصطلح "currying" (التكرير) فليس واضحًا تمامًا. ديفيد تورنر يقول إن هو من صاغ الكلمة في ملاحظاته الدراسية لعام 1967 بعنوان مفاهيم أساسية في لغات البرمجة،
ومن جهة أخرى، لكن المصدر يقدّم المفهوم باعتباره "أداة من ابتكار شونفينكل"، ولا يستعمل مصطلح "currying" صراحة، رغم أن كاري يُذكر لاحقًا في سياق الدوال من الدرجة الأعلى.
إضافةً إلى ذلك، أما جون س. رينولدز فقد عرّف مصطلح "currying" في ورقة بحثية عام 1972، لكنه لم يدّعِ أنه من ابتكره.
علاوةً على ذلك، في السياق الرياضي، يمكن تتبع هذا المبدأ إلى أعمال جوتلوب فريجه في سنة 1893.
علاوةً على ذلك، وقد تم اقتراح اسم بديل لهذا المفهوم وهو "شونفينكلية" (Schönfinkelisation).
نظرية المجموعات
وفي هذا السياق، في نظرية المجموعات، يُستعمل الترميز للدلالة على مجموعة الدوال من المجموعة إلى المجموعة . والتقييس هو تناظر تقابلي طبيعي بين المجموعة للدوال من إلى ، والمجموعة للدوال من إلى مجموعة الدوال من إلى . بالرموز:
إضافةً إلى ذلك، في الواقع، فإن هذا التناظر الطبيعي هو ما يُبرّر الترميز الرياضي لمجموعة الدوال. وكما هو الحال في جميع أمثلة التقييس، تصف الصيغة أعلاه زوجًا مقترنًا من الدوال المرافقة: لكل مجموعة ثابتة ، يكون التابع هو المرافق الأيسر للتابع .
في تصنيف المجموعات، يُطلق على كائن رياضي اسم كائن أسي.
الطوبولوجيا الجبرية
علاوةً على ذلك، حيث هي مجموعة تحاول بين الدوال ، و هو تعليق لـ"A"، و هو فضاء العقد لـ"A". من حيث الجوهر، يمكن اعتبار التعليق كحاصل الضرب الكارتيزي لـ مع الفترة الواحدة، مع معاملته بعلاقة تكافؤ لتحويل الفترة إلى حلقة. الصورة بواسطة curry تربط الفضاء إلى فضاء الدوال من الحلقات إلى ، أي من إلى . وبالتالي، فإن هو دالة مرافق تربط التعليقات بفضاءات العقد، وuncurrying هو النظير لها.
كذلك، في طوبولوجيا جبرية، تُعد currying مثالًا على تطابق إيكمان–هيلتون، ولذلك تلعب دورًا مهمًا في سياقات متنوعة. مثلًا، فضاء العقد هو المرافق لتعليق مختزل، ويُكتب عادة:
وفي السياق ذاته، في الجبر التماثلي، تُعرف العلاقة بين curry وuncurry باسم مرافقة الجداء التنسوري والدالة هوم، حيث تظهر ظاهرة مثيرة للاهتمام: قد لا تُرفع دالة هوم ودالة جداء موتر إلى متتالية منضبطة؛ ما يؤدي إلى تعريف دالة إكست ودالة تور.
في هذا الإطار، يمكن فهم الازدواجية بين مخروط التضمين وألياف التضمين (أي إدراج وإسقاط) كشكل من أشكال curry، مما يؤدي بدوره إلى الازدواجية بين متتالية منضبطة ومتتاليات بوبي العكسية.
حساب لامبدا
من جهة ثانية، يمكن استخدام الدوال المُكرّاة في أي لغة برمجة تدعم الإغلاق. ومع ذلك، غالبًا ما تُفضّل الدوال غير المُكرّاة لأسباب تتعلق بالكفاءة، إذ يمكن تجنب تكلفة التطبيق الجزئي وإنشاء الإغلاقات في أغلب استدعاءات الدوال.
في هذا الإطار، في علم الحاسوب النظري، يوفر الكرّيان وسيلة لدراسة الدوال متعددة الوسائط ضمن نماذج نظرية بسيطة جدًا، مثل حساب لامبدا، حيث تأخذ الدوال وسيطًا واحدًا فقط. لنفترض وجود دالة تأخذ وسيطين وتملك النوع ، مما يعني أن x يجب أن يكون من النوع ، وy من النوع ، بينما تُرجع الدالة نفسها قيمة من النوع . الشكل المُكرّى للدالة f يُعرّف على النحو التالي:
وفي هذا السياق، حيث هو معامل التجريد في حساب لامبدا. وبما أن الكرّيان يأخذ كمدخل دوال من النوع ، فإن نوع الكرّيان ذاته يُستنتج كالتالي:
.
كذلك، عادةً ما يُعتبر معامل تجميعيًا إلى اليمين، لذلك يُكتب النوع غالبًا بصيغة مختصرة . وبالمقابل، فإن تطبيق الدالة يُعتبر تجميعيًا إلى اليسار، لذا فإن التعبير يعادل:
أي أن الأقواس ليست ضرورية لتوضيح ترتيب التطبيق.
الدافع
وعلى صعيد آخر، بعض لغات البرمجة تستعمل دوال مقيّسة بشكل شبه دائم لتحقيق تعدد المعاملات؛ من الأمثلة البارزة أم أل وهاسكل، حيث أن جميع الدوال في كلتا اللغتين تستقبل معاملًا واحدًا فقط. وهذه الخاصية موروثة من تكامل لامدا، حيث تمثل الدوال متعددة المعاملات عادةً بصيغة مقيّسة.
ومن ناحية أخرى، جميع الدوال "العادية" التي تُصادف عادة في تحليل رياضي أو في برمجة يمكن تقييسها. إلا أن هناك فئات رياضية لا يكون التقييس ممكنًا فيها؛ وأكثر الفئات تعميمًا التي تسمح بالتقييس هي فئة مونودية مغلقة.
علاوةً على ذلك، عمليًا، يمكن استخدام تقنية الإغلاقات البرمجية لتنفيذ التطبيق الجزئي ونوع من التقييس، من خلال إخفاء بعض المعاملات داخل بيئة ترافق الدالة المقيّسة.
يرتبط التقييس بتطبيق جزئي، لكنه لا يُعدّ الشيء نفسه.
كذلك، يوفّر التكرير وسيلة للتعامل مع الدوال التي تستقبل عدة معاملات، واستخدامها في أطر عمل لا تسمح إلا بدوال تأخذ معاملًا واحدًا فقط. فمثلًا، بعض التقنيات التحليلية لا يمكن تطبيقها إلا على دالة ذات معامل واحد. ومع ذلك، فإن الدوال العملية غالبًا ما تتطلب أكثر من ذلك. وقد بيّن جوتلوب فريجه أن من الكافي توفير حلول لحالة المعامل الواحد، إذ يمكن تحويل دالة متعددة المعاملات إلى سلسلة من الدوال أحادية المعامل. وتُعرف هذه العملية في الوقت الحالي باسم التقييس.
فضاءات الدوال
وفي السياق ذاته، بينما تكون دالة uncurrying هي المعكوس لهذه الدالة. إذا أُعطيت المجموعة من الدوال المستمرة من إلى طوبولوجيا منفتحة مضغوطة، وكان الفضاء هاوسدورف موضعيًا مضغوط، فإن:
إضافةً إلى ذلك، هي دالة مستمرة عندما يكون بمنفتحة مضغوطة و هاوسدورف موضعيًا مضغوطًا. هاتان النتيجتان أساسيتان في إثبات استمرارية تحاول، أي عندما يكون هو الفترة الواحدة ، بحيث يمكن اعتبار إما تحاول بين دالتين من إلى ، أو مسارًا مستمرًا في .
وفي هذا الصدد، إحدى النتائج المفيدة هي أن الدالة تكون مستمرة إذا وفقط إذا كانت صورتها بطريقة curry مستمرة. نتيجة مهمة أخرى هي أن دالة "التطبيق"، والتي تُعرف عادةً باسم "التقييم" في هذا السياق، تكون مستمرة (لاحظ أن إيفال مفهوم مختلف تمامًا في علوم الحاسوب). أي أن:
علاوةً على ذلك، في نظرية فضاء دالي مثل تحليل دالي أو نظرية التجانس، غالبًا ما يهتم المرء بـدالة مستمرة بين فضاء طوبولوجي. يُكتب (أي دالة هوم) للدلالة على مجموعة "جميع" الدوال من إلى ، ويُستعمل الترميز للإشارة إلى الجزء الفرعي من الدوال المستمرة. هنا، تُعطى دالة وفق تقابل (دالة):
ومن ناحية أخرى، تكون تصاكل. ينطبق هذا كذلك عندما تكون و و فضاءات مولدة بطريقة مضغوطة، على الرغم من وجود حالات أكثر.
المنطق
وفي السياق ذاته، في فئة جبر هايتنغ، يُكتب الكائن الأسي عادةً على شكل اقتضاء منطقي . وتُعد الجبرات التوزيعية من نوع هايتنغ جبور بولية، ويأخذ الكائن الأسي فيها الشكل الصريح ، مما يُبرز أن الكائن الأسي يُمثّل في الحقيقة الاقتضاء المادي.
إضافةً إلى ذلك، بموجب تطابق كاري-هوارد، فإن وجود الكرّيان واللاكرّيان يعادل النظريّة المنطقية (والمعروفة كذلك باسم التصدير)، إذ إن النوع الضربي يُقابل اقترانًا منطقيًا، ونوع الدالة يُقابل الاقتضاء.
نظرية النمط
كذلك، يُعبَّر عن هذا النهج النمطي في لغات برمجة مثل إم إل واللغات المتفرعة منها أو المتأثرة بها مثل كامل وهاسكل، وإف.
ومن ناحية أخرى، في نظرية النمط، يتم تنظيم الفكرة العامة لنظام الأنواع في علم الحاسوب ضمن جبر محدد للأنواع. فمثلًا، عند كتابة ، فإن المقصود أن و هما أنواع، بينما السهم هو منشئ نوع، وبشكل خاص، يمثل نوع الدالة أو نوع السهم. وبالمثل، فإن حاصل الضرب الديكارتي للأنواع يُنشأ بواسطة منشئ نوع الضرب .
ومن جهة أخرى، يوفّر النهج النمطي تكاملًا طبيعيًا مع لغة نظرية الفئات، كما سيُناقش لاحقًا. يعود ذلك إلى أن الفئات، وبشكل خاص الفئات الوحيدية، تمتلك لغة داخلية، ويُعد حساب لامبدا النمطي البسيط المثال الأبرز على مثل هذه اللغة. وتكمن أهميته في هذا السياق بقدرته على البناء انطلاقًا من منشئ نوع وحيد، هو نوع السهم. ويُضفي الكرّيان على اللغة نوع الضرب بشكل طبيعي. وتسمح المطابقة بين الكائنات في الفئات والأنواع بإعادة تفسير لغات البرمجة كأنظمة منطقية (عبر تطابق كاري-هوارد)، وكأنظمة رياضية أخرى، كما سيُستعرض لاحقًا.
نظرية الفئات
وعلى صعيد آخر، حيث يُشير "هوم" إلى الدالة المراعية (الخارجية) التي تجمع جميع التشاكلات في الفئة، في حين يُمثل الهوم الداخلي في الفئة المغلقة الأحادية. في فئة المجموعات، يتطابق الاثنان. وعندما يكون الجداء هو الجداء الديكارتي، يصبح الهوم الداخلي هو الكائن الأسي .
ومن جهة أخرى، تجد مفاهيم الكرّيان واللاكرّيان أوضح تعبيراتها العامة والمجردة في نظرية الفئات. يُعدّ الكرّيان خاصية شاملة للكائن الأسي (كائن أسي)، وينتج عنه اقتران في الفئات المغلقة الديكارتية. أي أن هناك تماكل طبيعي (تحويل طبيعي) بين التشاكلات من الجداء الثنائي والتشاكلات إلى كائن أسي .
وفي هذا السياق، قد يفشل الكرّيان في حالتين. الأولى، إذا لم تكن الفئة مغلقة، وبالتالي تفتقر إلى دالة هوم داخلية (ربما لوجود أكثر من خيار ممكن لهذه الدالة). والثانية، إذا لم تكن أحادية، أي أنها تفتقر إلى جداء (أي لا يوجد بها طريقة لتكوين أزواج من الكائنات). الفئات التي تمتلك كلاً من الجداءات والهومات الداخلية هي بالضبط الفئات المغلقة الأحادية.
كذلك، وعلى النقيض، فإن الجداء في الفئات الأحادية (مثل فضاء هيلبرت أو الفضاءات المتجهية في التحليل الدالي) هو جداء موتر. وتُعد المنطق الخطي هو اللغة الداخلية لهذه الفئات، وهي أحد أشكال المنطق الكمومي؛ ويُقابلها نظام الأنواع الخطي. تُستعمل هذه الفئات في توصيف التشابك الكمومي، كما تسمح — على نحو أوسع — بتعميم واسع لـ تطابق كاري-هوارد إلى ميكانيكا الكم، والمتعددات الحدية في الطوبولوجيا الجبرية، ونظرية الأوتار.
إضافةً إلى ذلك، يكمن الفرق بين هذين الإطارين في أن الجداء في الفئات الديكارتية (مثل فئة المجموعات، أو رتب جزئية تامة، أو جبور هايتنغ) هو ببساطة جداء ديكارتي؛ ويُفسَّر على أنه زوج مرتب من العناصر (أو قائمة). ويُعد حساب لامبدا النمطي البسيط هو اللغة الداخلية للفئات المغلقة الديكارتية؛ ولهذا السبب تُعد الأزواج والقوائم هي نظام الأنواع الأساسي في نظرية النمط لكل من ليسب وسكيم (لغة برمجة) والكثير من لغات البرمجة الوظيفية.
من جانب آخر، يُعد إطار الفئات المغلقة الديكارتية كافيًا لمناقشة المنطق الكلاسيكي؛ أما الإطار العام للفئات المغلقة الأحادية فهو مناسب لـ الحوسبة الكمومية.
من جهة ثانية، ويُعمّم هذا على نتيجة أوسع في فئة مغلقة أحادية: يُمثّل الكرّيان القول إن الجداء التوتري (جداء الفئة الأحادية) والهوم الداخلي هما دوال مراعية مقترنة؛ أي أن لكل كائن يوجد تماثل طبيعي على النحو الآتي:
نظرية المجالات
ومن ناحية أخرى، في نظرية الترتيب، أي نظرية شبكة لمجموعة مرتبة جزئيًا، تكون دالة مستمرة عندما تُزود الشبكة بطوبولوجيا سكوت. لقد دُرست الدوال المستمرة وفق سكوت في البداية كجزء من محاولة لإيجاد دلالات لـتكامل لامدا (نظرًا لعدم كفاية نظرية المجموعات العادية لذلك). بشكل أعم، تُدرس هذه الدوال في نظرية المجالات، التي تشمل دراسة الدلالات التصويرية لخوارزميات الحاسوب. لاحظ أن طوبولوجيا سكوت تختلف كثيرًا عن الكثير من الطوبولوجيات الشائعة في فئة الفضاءات الطوبولوجية؛ فهي عادةً ما تكون أدق، وليست فضاء رصين.
التعريف
وفي هذا السياق، يُفهم التقييس (Currying) بسهولة من خلال البدء بتعريف غير رسمي، يمكن فيما بعد تكييفه ليناسب الكثير من المجالات المختلفة. أولًا، يجب توضيح بعض الرموز. تشير الصيغة إلى جميع الدوال من إلى . وإذا كانت دالة من هذا النوع، فإننا نكتب . وليكن هو مجموعة الأزواج المرتبة من عناصر و على التوالي، أي جداء ديكارتي لـ و. قد تكون و مجموعات، أو أنواعًا (types)، أو أنواعًا أخرى من الكائنات، كما سيتم توضيحه لاحقًا.
من جهة ثانية، أما إلغاء التقييس (Uncurrying) فهو التحويل العكسي، ويمكن فهمه بسهولة من خلال مرافقه الأيمن، وهو الدالة .
- فإن عملية التقييس (currying) تُنشئ دالة جديدة:
- .
- أي أن تأخذ معاملًا من النوع وتُرجع دالة من النوع . وتُعرّف كما يلي:
- حيث من النوع و من النوع . ويمكننا كذلك كتابة:
إذا كانت لدينا دالة:
،
التمايز عن التطبيق الجزئي للدوال
ومن ناحية أخرى، الدافع العملي للتطبيق الجزئي هو أن الدوال الناتجة عن تزويد بعض، وليس كل، الوسائط تكون غالبًا مفيدة؛ مثلًا، الكثير من اللغات توفر دوال مثل plus\_one، والتي يمكن إنشاؤها بسهولة عن طريق تثبيت الوسيط الأول لدالة الجمع عند 1.
ومن جهة أخرى، في المقابل، يشير "التطبيق الجزئي للدوال" إلى عملية تثبيت عدد من الوسيطات في دالة، وإنتاج دالة جديدة بعدد وسائط أقل. إذا أخذنا نفس الدالة السابقة، و"ثبّتنا" الوسيط الأول، نحصل على دالة من الشكل . يمكن استدعاؤها بالشكل . أي أن النتيجة في هذه الحالة هي دالة تقبل وسيطين، وليس سلسلة من الدوال الأحادية.
ومن جهة أخرى، من حيث الفهم الحدسي، يمكن القول إن التطبيق الجزئي يعني: "إذا ثبّتت أول وسيط في دالة، ستحصل على دالة تقبل باقي الوسائط". مثلًا، إذا كانت الدالة div تمثل عملية القسمة x ÷ y، فإن تثبيت x عند 1 (أي div 1) ينتج دالة مساوية للدالة inv التي تُرجع مقلوب الوسيط، أي: inv(y) = 1 ÷ y.
أو ببساطة:
- انظر كذلك
- تثمين كسول
- المراجع
من جهة ثانية، مثلًا، إذا كانت لدينا دالة من النمط ، فإن كرّية هذه الدالة تُنتج دالة بالشكل . أي أن استدعاء الدالة الأصلية قد يكون بالشكل ، بينما يُستدعى الشكل الكرّي منها بـ ، حيث يُمرر كل وسيط بشكل تسلسلي إلى دالة أحادية تُرجع دالة أخرى حتى الوصول للنتيجة النهائية. لاحظ أنه بعد استدعاء نحصل على دالة تقبل وسيطًا واحدًا وتُرجع دالة أخرى، وليس دالة تقبل وسيطين.
إضافةً إلى ذلك، ولمزيد من الإثبات، يمكن القول إنه إذا كانت لدينا دالة ، فيمكننا تعريف دالة بحيث ؛ مما يدل على أن أي تطبيق جزئي يمكن اختزاله إلى عملية كرّية واحدة.
في هذا الإطار، يمكن اعتبار التطبيق الجزئي بمثابة تقييم لدالة كرّية عند نقطة معينة. مثلًا، إذا كانت و ، فإن:
وعلى صعيد آخر، غالبًا ما يُخلط بين الكرّية (Currying) والتطبيق الجزئي للدوال (Partial Function Application).
وفي هذا السياق، من هنا، يمكن تعريف التطبيق الجزئي على أنه الناتج الفعلي لتطبيق واحد لعملية الكرّية على ترتيب معين لوسائط دالة معينة.
من جانب آخر، وبالتالي، فإن التطبيق الجزئي ما هو إلا دالة كرّية تم تقييمها عند نقطة معينة. وبالمثل، فإن أي دالة كرّية عند نقطة معينة تُعد تطبيقًا جزئيًا.
في هذا الإطار، من الفروقات الجوهرية بينهما أن استدعاء دالة مطبَّقة جزئيًا يُرجع النتيجة مباشرة، وليس دالة أخرى في سلسلة الكرّية؛ ويمكن توضيح هذا الفرق بسهولة أكبر عند التعامل مع دوال ذات عدد كبير من الوسيطات (أي الأريتي > 2).
حيث تمثل كرّية الوسيط الأول للدالة f.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟