نظرية التصنيف للمبرمجين. على الأصابع

مرحبا زملائي.







تطوير اهتمامنا الثابت بالأدب الأكاديمي الجاد ، كما يمكن للمرء أن يقول ، وصلنا إلى نظرية المقولات . ظهر هذا الموضوع في العرض التقديمي الشهير لبارتوش ميليفسكي بالفعل على حبري والآن يمكنه التباهي بمثل هذه المؤشرات: إنه لمن دواعي سروري أننا تمكنا من العثور على مادة جديدة نسبيًا (يناير 2020) ، والتي تعد بمثابة مقدمة ممتازة وفي نفس الوقت موجزة قدر الإمكان لنظرية الفئات. نأمل أن نتمكن من إثارة اهتمامك بهذا الموضوع.











إذا واجهتك أنا وأنت ، عزيزي القارئ ، مشاكل مماثلة ، فعندئذ تعذبت مرة من السؤال "ما هو بحق الجحيم أحادي؟!" ثم بحثت في Google عن هذا السؤال ، وانزلقت خلسة في حفرة الأرانب في الرياضيات المجردة ، وتشابكت في الفكاهة ، والأحادية ، والفئاتحتى لاحظوا أنهم قد نسوا بالفعل السؤال الذي أتى بك إلى هنا. يمكن أن تكون هذه التجربة مربكة للغاية إذا لم تكن قد رأيت لغات برمجة وظيفية من قبل ، ولكن لا تقلق! لقد درست عدة صفحات من الرياضيات المكثفة من أجلك وشاهدت ساعات من المحاضرات حول هذا الموضوع. لذا ، لتوفير هذه الحاجة ، سألخص الموضوع هنا وأظهر لك أيضًا كيف يمكنك تطبيق نظرية الفئات بحيث يمكنك التفكير (وكتابة التعليمات البرمجية) بأسلوب وظيفي الآن.



هذه المقالة مخصصة لأي شخص يعتبر نفسه "مبتدئًا" في مجال البرمجة الوظيفية وقد بدأ للتو مع Scala أو Haskell أو أي لغة أخرى مماثلة. بعد قراءة هذا المقال ، ستشعر بمزيد من الثقة في تفسير أسس نظرية الفئة وتحديد مبادئها "على أرض الواقع". أيضًا ، إذا كنت قد جربت يدك في الرياضيات النظرية ، امتنع عن ذكر المفاهيم التي تمت مناقشتها هنا مباشرةً. كقاعدة عامة ، يمكن قول الكثير عن كل منها أكثر مما هو مكتوب هنا ، ولكن هذه المقالة ستكون كافية لمبرمج فضولي.

أساسيات

إذن ما هي الفئة بالضبط وكيف ترتبط بالبرمجة؟ مثل العديد من المفاهيم المستخدمة في البرمجة ، تعتبر الفئة شيئًا بسيطًا جدًا يحمل اسمًا رائعًا. هذا مجرد رسم بياني موجه معنون مع بعض القيود الإضافية. كل عقدة في فئة تسمى "كائن" ويطلق على كل من حوافها "شكل".







كما قد تكون خمنت ، ليس كل رسم بياني موجه فئة ؛ لكي يتم اعتبار الرسم البياني فئة ، يجب استيفاء بعض المعايير الإضافية. في الصورة التالية ، نلاحظ أن كل كائن لديه شكل يشير إلى نفسه. هذا هو التشكل المتطابق ، ويجب أن يكون لكل كائن مثل الرسم البياني يعتبر فئة. بعد ذلك ، لاحظ أن الكائن Aله شكل fيشير إلىB، وبالمثل ، فإن الكائن Bله شكل gيشير إلى C. لأنه ليس هناك مسار من Aل Bومن Bل C، ومن الواضح أن هناك مسار من Aل C، أليس كذلك؟ هذه هي فئات المتطلبات التالية للتشكيلات يجب بالضرورة تنفيذ التكوين الترابطي ، بحيث يكون للتشكيل f: A = > B ، g: B = > Cوهناك التشكل h = g(f): A = > C.



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

trait Rock
trait Sand
trait Glass
def crush(rock: Rock): Sand
def heat(sand: Sand): Glass

أعتقد أن هذا المثال سيجعل العلاقة أسهل قليلاً. إن محو الأحجار إلى رمل هو عملية تشكيل تحول الشيء rockإلى كائن sand، في حين أن صهر الزجاج من الرمل هو تشكيل يحول الشيء sandإلى كائن glass. في هذه الحالة ، سيبدو تكوين هذه العلاقات بالتأكيد

val glass: Glass = heat(crush(rock))

هناك أيضًا وظائف هوية (محددة في PredefScala) ، لأنه ليس من الصعب كتابة دالة تُرجع نفس الكائن لأي كائن. ومن ثم ، فإن هذا النظام هو فئة ، وإن كانت فئة بسيطة إلى حد ما.

معرفة أعمق بالفئات

سوف نتعمق الآن قليلاً في مصطلحات نظرية الفئة ونبدأ بفئة تسمى الصهارة. إذا لم تكن على دراية بهذا المفهوم الأساسي بعد ، دعني أوضح أن الصهارة هي مجرد عملية ثنائية ، أي عملية على قيمتين ، ونتيجة لذلك يتم الحصول على قيمة جديدة. من أجل عدم الخوض في التفاصيل ، لن أقدم هنا دليلًا على أن مجموعة جميع العمليات الثنائية هي في الواقع فئة ، ولكن بالنسبة لأولئك الذين يهتمون بالتفاصيل ، أوصي بقراءة المقالة التالية بقلم بارتوش ميليفسكي. تنتمي جميع العمليات الحسابية من الجمع إلى الضرب إلى الفئات الفرعية ، التي توحدها فئة الصهارة (انظر الرسم البياني).



ينطبق ترتيب الميراث التالي هنا:

• 1. الصهارة: جميع العمليات الثنائية
• 2. شبه المجموعات: جميع العمليات الثنائية التي تكون ترابطية
• o : .
• 3. : ,
• o : , (aka )

لذا ، بالعودة إلى مثالنا السابق ، فإن كلا من الجمع والضرب أحاديان لأنهما مترابطان (a + (b + c) = (a + b) + c)ولهما عنصر واحد (ax 1 = 1 xa = a). تحتوي الدائرة الأخيرة في هذا الرسم البياني على مجموعات شبه يمكن أن تنطبق عليها مبادئ دمج مختلفة عن تلك التي تنطبق على مجموعات شبه أو أحاديات. Quasigroups هي عمليات ثنائية يمكن عكسها. إن شرح هذه الخاصية ليس بهذه السهولة ، لذا أحيلك إلى سلسلة المقالات التي كتبها مارك سيمان والمخصصة لهذا الموضوع. A العملية الثنائية هي عكسها أنه لأجل أي قيم aو bهناك مثل هذه القيم xو yالتي تتيح تحويل aلb... أعلم أنه يبدو صعبًا. لتوضيح ذلك ، دعنا نلقي نظرة على مثال الطرح التالي:

val x = a - b
val y = a + b
assert(a - x == b)
assert(y - a == b)

يرجى ملاحظة: yلا تشارك في الطرح على هذا النحو ، ولكن المثال لا يزال مهمًا. الكائنات في فئة ما مستخرجة ويمكن أن تكون أي شيء تقريبًا ؛ في هذه الحالة، فمن المهم أن لأي aو bالتي يمكن توليدها، لا تزال هذه البيانات الحقيقية.

أنواع في السياق

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



تكمن المشكلة في أنه في نظرية الفئات نميل إلى الابتعاد عن المجموعات والتفكير من حيث الأشياء والتشكيلات. لكن حقيقة أن الأنواع هي مجرد مجموعات أمر لا مفر منه. لحسن الحظ ، هناك مكان في نظرية الفئات لهذه المجموعات ، لأن كائناتنا هي تجريدية ويمكن أن تمثل أي شيء. لذلك ، لدينا كل الحق في أن نقول إن كائناتنا هي مجموعات ، وننظر كذلك في برامج Scala الخاصة بنا على أنها فئات ، حيث تكون الأنواع كائنات والوظائف هي أشكال. بالنسبة للكثيرين ، قد يبدو هذا واضحًا بشكل مؤلم ؛ بعد كل شيء ، في Scala تعودنا على التعامل مع الأشياء ، لكن من الجدير الإشارة إلى ذلك صراحة.



إذا كنت قد عملت باستخدام لغة كائنية التوجه مثل Java ، فأنت على الأرجح على دراية بمفهوم الأنواع العامة. هذه أشياء مثلLinkedListأو ، في حالة Scala ، Option[T]حيث Tيمثل نوع البيانات الأساسي المخزن في بعض الهياكل. ماذا لو أردنا إنشاء مخطط من نوع إلى آخر بحيث يتم الحفاظ على بنية النوع الأول؟ مرحبًا بكم في عالم الممثلين ، المُعرَّف بأنه تعيينات بين الفئات للحفاظ على الهيكل. في البرمجة ، عادة ما يتعين عليك العمل مع فئة فرعية من المفاعلات ، تسمى endofunators ، والتي تساعد في تعيين الفئة لنفسها. لذلك سأقول فقط عندما أتحدث عن الممرضات ، أعني الأطباء الداخليين.



كمثال على الممتلئ ، دعنا ننظر إلى نوع Scala Option[T]بالتزامن مع مثالنا السابق ، والذي ذكر الحجر والرمل والزجاج:

val rockOpt: Option[Rock] = Some(rock)

أعلاه لدينا النوع Rockكما حددناه سابقًا ، لكن ملفوفًا فيه Option. هذا نوع عام (وليس فقط ، المزيد حول هذا أدناه) ، يخبرنا أن الكائن هو إما كيان معين نبحث عنه ، أو Noneيمكن مقارنته nullبلغات أخرى.



إذا لم نستخدم [فونكتورس]، ثم يمكن أن نتصور كيف نحن نطبق وظيفة crush()ل Rock، الأمر الذي يتطلب اللجوء إلى مشغل if للتعامل مع الموقف الذي Optionهو None.

var sandOpt: Option[Sand] = None
if(rockOpt != None) {
  sandOpt = Some(crush(rockOpt.get))
}

قد نقول أن هذا جانبا ، لكن من فضلك لا تستخدم var - مثل هذا الرمز سيء في Scala لعدة أسباب. مرة أخرى ، العودة إلى الموضوع: في Java أو C # لن يكون هذا مشكلة. يمكنك التحقق لمعرفة ما إذا كانت القيمة الخاصة بك من النوع الذي تتوقع رؤيته وفعل ما تريد به. ولكن مع قوة الممرضين ، يمكن عمل كل شيء بشكل أكثر أناقة مع الوظيفة map():

val sandOpt: Option[Sand] = rockOpt.map(crush)

بوم ، سطر واحد وأنت انتهيت. سيكون من الممكن وضع المثال الأول في سطر واحد ، باستخدام عامل التشغيل الثلاثي أو شيء مشابه ، لكنك لن تنجح بإيجاز. هذا المثال رائع حقًا في بساطته. إليك ما يحدث هنا: إنها map()تأخذ وظيفة وتعيين تلك الوظيفة (بالمعنى الرياضي) لنفسها. يتم Optionالاحتفاظ بالهيكل ، ولكنه يحتوي الآن على إما Sand، أو Noneبدلاً من Rockأو None. يمكن توضيح ذلك بشيء من هذا القبيل:







لاحظ كيف يتم محاذاة كل شيء بشكل جميل ، ويتم الحفاظ على كل كائن وتشكيل في كلا النظامين. وبالتالي ، فإن التشكل في المركز هو عامل تشغيل يمثل تعيينًا من Tإلى Option[T].

سويا

الآن يمكننا العودة أخيرًا إلى السؤال الأصلي "ما هو الجحيم أحادي"؟ هناك إجابة يمكنك أن تتعثر عليها بشكل أعمى إذا حاولت فقط البحث عنها في Google ، ويبدو الأمر على هذا النحو: monad هو مجرد أحادي في فئة endofunators ، والذي غالبًا ما يتبعه ملاحظة ساخرة للغاية ، "ما هي المشكلة؟" كقاعدة عامة ، بهذه الطريقة يحاولون أن يوضحوا مازحا مدى صعوبة كل شيء في هذا الموضوع ، ولكن في الواقع ، ليس كل شيء مخيفًا للغاية - بعد كل شيء ، لقد اكتشفنا بالفعل معنى هذه العبارة. لنأخذ الأمر خطوة بخطوة مرة أخرى.



أولاً ، نعلم أن الأحاديات هي عمليات ثنائية ترابطية ، كل منها يحتوي على عنصر محايد (فردي). ثانيًا ، نعلم أن المفاعلات الداخلية تسمح لنا بتعيين فئة لنفسها ، مع الحفاظ على الهيكل. لذا فإن monad هو مجرد نوع من أنواع الغلاف (كما في مثال النوع العام أعلاه) الذي يحافظ على طريقة ما لقبول دالة وتعيينها لنفسها. List- هذا أحادي ، Option(مثل الذي ذكرناه أعلاه) أحادي ، وقد يخبرك شخص ما بذلك Futureوهو أيضًا أحادي. مثال:

val l: List[Int] = List(1, 2, 3)
def f(i: Int) = List(i, i*2, i*3)
println(l.flatMap(f)) // : List(1, 2, 3, 2, 4, 6, 3, 6, 9)

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