🔣 👩🏻‍🔧 👃🏾 تنفيذ امتداد الأنماط النشطة للغة OCaml 🙆🏼 🌭 💪🏻

حول المشروع

في ربيع عام 2020 ، كجزء من الممارسة الربيعية في مركز علوم الكمبيوتر ، كنت أطور تصميمًا جديدًا للغة البرمجة OCaml تحت إشراف صارم من ديمتري كوساريف .

لماذا OCaml

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

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

للتعمق في الموضوع ، أقترح إلقاء نظرة على مقالات OCaml للجماهير و Why OCaml .

حاليًا ، يجري العمل على تنفيذ نظام متعدد النواة لـ OCaml ، مقترنًا بالتأثيرات الجبرية ، والتي ستؤدي في نفس الوقت إلى زيادة الأداء العام للغة والقضاء على القيود الحالية لنظام الكتابة المرتبطة بحقيقة أن اللغة تسمح بالحسابات غير النقية.

مطابقة الأنماط والأنماط النشطة

ركز عملي بشكل أساسي على بناء مطابقة النمط ، والذي يستخدم على نطاق واسع في لغات البرمجة الوظيفية.

للتوضيح ، ضع في اعتبارك مثالًا بسيطًا لتدوير عقدة في شجرة ثنائية. في أسلوب الأمر الأكثر شيوعًا ، من المحتمل أن تبدو الشفرة كما يلي:

type 'a tree =
  | Node of 'a tree * 'a * 'a tree
  | Nil
let rotate_left' t =
  if is_node t
  then
    let a = get_left  t in
    let p = get_value t in
    let r = get_right t in
    if is_node r
    then
      let b = get_left  t in
      let q = get_value t in
      let c = get_right t in
      Node(Node(a,p,b),q,c)
    else t
  else t

وهنا نفس الكود المكتوب باستخدام بناء مطابقة النمط:

let rotate_left = function
  | Node(a, p, Node(b, q, c)) -> Node(Node(a, p, b), q, c)
  | Node _ | Nil as x -> x

عند استخدام هذا التصميم ، لدينا المزايا التالية:

تعبيرية عالية
التحقق من الاكتمال ، وهو خاصية مهمة للتحقق من الصحة وإعادة بناء البرامج ؛
مخططات تجميع فعالة.

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

على سبيل المثال ، إذا أضفت بنيات جديدة إلى شجرة بناء الجملة ، فسيعرض المحول البرمجي لي كود الكتابة AST إلى جسم الوظيفة ، حيث أحتاج إلى كتابة كود الكتابة للإنشاءات الجديدة:

هذه الخاصية تجعل OCaml مقاومًا جدًا لإعادة البناء والتغييرات البرمجية الأخرى.

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

module type List = sig
  type 'a t (* = ? *)
  val cons:  'a -> 'a t -> 'a t
  val empty: 'a t
  val head:  'a t -> ('a * 'a t) option
end

ومع ذلك ، فإن هذه المشكلة ليست أساسية ، وكما لوحظ في عام 1987 ، من الممكن تحقيق مطابقة الأنماط على الأنواع المجردة.

صياغة المشكلة

منذ عام 1987 ، تم تقديم العديد من التصميمات المختلفة في الأدبيات لحل المشكلة ، وهنا عدد قليل منها:

مع بداية المشروع ، كان العمل قد تم بالفعل على اختيار معقول وموضوعي لحل معين للتنفيذ ، وكان الأكثر فائدة هو امتداد الأنماط النشطة المطبق في لغة F #.

كان الهدف من المشروع هو البدء في تنفيذ Active Patterns لمترجم OCaml والتواصل قدر الإمكان.

الأنماط النشطة

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

module type List = sig
  type 'a t
  val (|Cons|Nil|): 'a t -> ('a * 'a t, unit) choice2
  val cons:  'a -> 'a t -> 'a t
  val empty: 'a t
  val head:  'a t -> ('a * 'a t) option
end

والنتيجة هي نوع مجموع مجهول choice2له التعريف التالي (هناك أنواع متشابهة تم إنشاؤها حتى choice32):

type ('a, 'b) choice2 =
  | Choice2_1 of 'a
  | Choice2_2 of 'b

وبالتالي ، (|Cons|Nil|)ستقوم الوظيفة بتحويل القائمة إلى أحد بديلين: إما إلى زوج من الرأس والذيل من القائمة ، أو إلى بديل فارغ يعني أن القائمة كانت فارغة.

تحديد مثل هذه الوظيفة لقائمة قياسية أمر تافه وسيبدو كما يلي:

let (|Cons|Nil|) = function
  | []      -> Nil
  | x :: xs -> Cons(x, xs)

كمثال على الاستخدام ، ضع في اعتبارك وظيفة تزيل التكرارات المتتالية في القائمة:

(* destutter [1;1;4;3;3;2] = [1;4;3;2] *)
let rec destutter = function
  | Nil -> nil
  | Cons(x, Nil) -> cons x empty
  | Cons(x, Cons(y, rest)) ->
      if x = y 
      then destutter (cons y rest)
      else cons x (destutter (cons y rest))

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

التقدم

كجزء من هذا العمل ، كان من الممكن تنفيذ تحليل وكتابة الامتداد لمحول OCaml الإصدار 4.09 ، يتم عرض النتائج هنا .

يتم تنفيذ المحلل اللغوي للمترجم باستخدام مولد محلل Menhir المتقدم . لدى Menhir دليل كامل ومفصل إلى حد ما ، ولكن حتى معه لم يكن واضحًا دائمًا كيف يمكنك تعيين قاعدة الاستدلال ، وكيف لا ولماذا. يعد تصحيح المحلل الناتج صغيرًا وبسيطًا للغاية ، ولكن المسار إليه يكمن من خلال 10-15 إزاحة وتقليل وتقليل التعارضات ، والتي استغرق تحليلها وإصلاحها بعض الوقت:

أود أن أشيد بمطوري Menhir وأشكرهم على عملهم في تفصيل وتوضيح الأخطاء. بمجرد فشل المولد اللغوي في توضيح الصراع واضطر إلى تفكيكه باستخدام الآلة المصممة لـ 1500 دولة. وهذا يتطلب بالطبع مزيدًا من الوقت.

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

استنتاج آخر توصلت إليه لنفسي هو ألا أنسى استخدام الإصدارات القديمة من المشروع. على سبيل المثال ، إليك مقارنة كمية لنفس القطعة المكتوبة في إصداري 2019 و 2005:

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

أخيرًا ، الاستنتاج الرئيسي الذي توصلت إليه أثناء عملي هو التأكيد على أن توثيق المشاريع مفتوحة المصدر أمر بالغ الأهمية. على الرغم من أن اللغة معبرة ، فإن الكود المصدري يمكنه فقط أن يخبرنا كيف تتصرف الوظيفة ، وليس ما تفعله أو لماذا تفعل ذلك بالطريقة التي تعمل بها. من الصعب جدًا قراءة سلاسل المكالمات type_self_pattern-> type_cases-> t ype_pat-> type_pat'-> type_pat_auxومعرفة الوظيفة التي تحتاجها ؛ أو اسم معلمة واحدة فقطconstrاحزر المنشئات ولماذا يجب كتابتها هنا.

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

خاتمة

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

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

آمل أن يكتمل هذا التنفيذ ، معي أو بدوني. على الرغم من كل الصعوبات ، كان من الرائع أن تجرب نفسك في تطوير مترجم صناعي للغتك المفضلة.

مؤلف:

ألكسندر باشكيروف طالب في مركز علوم الكمبيوتر وحاصل على بكالوريوس في هندسة البرمجيات في السنة الرابعة في جامعة ولاية سانت بطرسبرغ ، وهو موظف في JetBrains.

تنفيذ امتداد الأنماط النشطة للغة OCaml