البرمجة المعيارية

5. البرمجة المعيارية

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

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

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

وتُجرَّد الوحدات بإعطاء مواصفات لما يُفترض أن تفعله. والمواصفة الجيدة للوحدة واضحة ومفهومة وتعطي القدر الكافي فقط من المعلومات عمّا تفعله الوحدة حتى يستطيع العملاء استخدامها بنجاح. وهذا التجريد يسهّل مهمة المبرمج كثيرًا؛ وهو مفيد حتى عندما لا يوجد إلا مبرمج واحد يعمل على برنامج كبير إلى حد معتدل، وهو حاسم عندما يكون هناك أكثر من مبرمج واحد.

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

يتخذ المطورون العاملون مع وحدة ما أدوارًا متمايزة. فمعظم المطورين عادةً عملاء للوحدة يفهمون الواجهة لكنهم لا يحتاجون إلى فهم تنفيذ الوحدة. أما المطور الذي يعمل على تنفيذ الوحدة فيسمى طبيعيًا منفِّذًا (implementer). وواجهة الوحدة عقد (contract) بين العميل والمنفِّذ يحدد مسؤوليات كل منهما. والعقود مهمة جدًا لأنها تساعدنا على عزل مصدر المشكلة عند حدوث خطأ — وعلى معرفة من نلوم!

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

وينبغي استخدام الوحدات عبر واجهاتها المعلنة فقط، وينبغي أن تساعد اللغة على فرض ذلك. وهذا صحيح حتى عندما يكون العميل والمنفِّذ الشخص نفسه. فالوحدات تفصل مسألة تصميم النظام وتنفيذه إلى مهام منفصلة يمكن إنجازها إلى حد كبير بشكل مستقل. وعندما تُستخدم وحدة عبر واجهتها فقط، يحتفظ المنفِّذ بمرونة تغيير الوحدة ما دامت تحقق واجهتها.

5.1. أنظمة الوحدات

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

فضاءات الأسماء. يوفر فضاء الأسماء (namespace) مجموعة من الأسماء المجمّعة معًا، والتي عادةً ما تكون مترابطة منطقيًا، والتي تتمايز عن فضاءات الأسماء الأخرى. وهذا يتيح لاسم foo في فضاء أسماء أن يكون له معنى مختلف عن foo في فضاء أسماء آخر. وفضاء الأسماء بذلك آلية للنطاق. وفضاءات الأسماء جوهرية للمعيارية. فبدونها، قد تتصادم الأسماء التي يختارها أحد المبرمجين مع الأسماء التي يختارها مبرمج آخر. في Java، تجمّع الأصناف (والحزم) الأسماء. وفي OCaml، البنى (structures) (وسندرسها قريبًا) شبيهة بالأصناف من حيث إنها تجمّع الأسماء — لكن دون أي من التعقيدات المضافة للبرمجة كائنية التوجه التي ترافق الأصناف عادةً (المنشئات، والأعضاء الساكنة مقابل أعضاء النسخ، والوراثة، والتجاوز، وthis وغيرها). والبنى هي جوهر نظام وحدات OCaml؛ بل إننا كنا نستخدمها طوال الوقت دون التفكير كثيرًا فيها.

التجريد. التجريد (abstraction) يخفي بعض المعلومات بينما يكشف معلومات أخرى. وبذلك يتيح التجريد التغليف (encapsulation)، أي إخفاء المعلومات (information hiding). وعادةً ما تتيح آليات تجريد الوحدات كشف بعض الأسماء الموجودة داخل الوحدة وإخفاء بعضها الآخر. ولذا تصف عمليات التجريد علاقات بين الوحدات: فقد توجد وحدات كثيرة يمكن اعتبارها محققة لتجريد معيّن. والتجريد جوهري للمعيارية، لأنه يتيح لمنفِّذي الوحدة إخفاء تفاصيل التنفيذ عن العملاء، فيمنع العملاء بذلك من إساءة استخدام تلك التفاصيل. وفي فريق كبير، تُحمى بذلك الوحدات التي يصممها أحد المبرمجين من إساءة استخدام مبرمج آخر. كما يتيح للعملاء أن يبقوا بجهل سعيد بتلك التفاصيل. ففي فريق كبير، لا يحتاج أي مبرمج إلى معرفة كل تفاصيل كل الوحدات. وفي Java، توفر الواجهات والأصناف المجردة التجريد. وفي OCaml، تُستخدم التواقيع (signatures) لتجريد البنى بإخفاء بعض أسماء البنية وتعريفاتها. والتواقيع في جوهرها أنواع البنى.

إعادة استخدام الشيفرة. يتيح نظام الوحدات إعادة استخدام الشيفرة (code reuse) بتوفير ميزات تتيح استخدام شيفرة من وحدة داخل وحدة أخرى دون الحاجة إلى نسخ تلك الشيفرة. وبذلك يتيح إعادة الاستخدام للمبرمجين أن يبنوا على عمل الآخرين بطريقة قابلة للصيانة: فعندما يجري منفِّذ إحدى الوحدات تحسينًا في تلك الوحدة، يحصل جميع المبرمجين الذين يعيدون استخدام تلك الشيفرة تلقائيًا على مزايا ذلك التحسين. وإعادة استخدام الشيفرة جوهرية للمعيارية، لأنها تتيح «لبنات بناء» يمكن تجميعها وإعادة تجميعها لتكوين قطع معقدة من البرمجيات. وفي Java، يوفر التنميط الفرعي والوراثة إعادة استخدام الشيفرة. وفي OCaml، يتيح المُوظِّفات (functors) والتضمينات (includes) إعادة استخدام الشيفرة. فالمُوظِّفات كالدوال، من حيث إنها تنتج وحدات جديدة من وحدات قديمة. أما التضمينات فكأنها شكل ذكي من النسخ واللصق: فهي تضمّن شيفرة من جزء من برنامج في جزء آخر.

تحذير

هذه المقارنات بين Java وOCaml ناقصة بالضرورة. وقد تخرج طبيعيًا من المناقشة أعلاه وأنت تعتقد أحد الأمرين التاليين:

• «البنى كأصناف Java، والتواقيع كواجهاتها.»
• «البنى ككائنات Java، والتواقيع كأصنافها.»

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

5.2. الوحدات

نبدأ بمثالين على نظام وحدات OCaml قبل الغوص في التفاصيل.

البنية (structure) ببساطة مجموعة من التعريفات، مثل:

struct
  let inc x = x + 1
  type primary_color = Red | Green | Blue
  exception Oops
end

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

في حد ذاتها، لن تُصرَّف الشيفرة أعلاه، لأن البنى لا تتمتع بمكانة من الرتبة الأولى كمكانة قيم مثل الأعداد الصحيحة أو الدوال. فلا يمكنك مجرد إدخال تلك الشيفرة في utop، ولا تمرير تلك البنية إلى دالة، وهكذا. وما يمكنك فعله هو ربط البنية باسم:

module MyModule = struct
  let inc x = x + 1
  type primary_color = Red | Green | Blue
  exception Oops
end

module MyModule :
  sig
    val inc : int -> int
    type primary_color = Red | Green | Blue
    exception Oops
  end

وناتج OCaml له الصيغة:

module MyModule : sig ... end

وهذا يشير إلى أن MyModule قد عُرّفت، وأنه استُنتج لها نوع الوحدة (module type) الظاهر على يمين النقطتين. ويُكتب ذلك النوع المسمّى توقيعًا (signature):

sig
  val inc : int -> int
  type primary_color = Red | Green | Blue
  exception Oops
end

التوقيع نفسه مجموعة من المواصفات (specifications). ومواصفات الأنواع المتغايرة والاستثناءات هي ببساطة تعريفاتها الأصلية، لذا لا تختلف primary_color وOops عمّا كانتا عليه في البنية الأصلية. أما مواصفة inc فمكتوبة بالكلمة المفتاحية val، تمامًا كما ستستجيب الواجهة التفاعلية لو عرّفنا inc فيها.

ملاحظة

قد يكون استخدام كلمة «مواصفة» هنا مربكًا، لأن كثيرًا من المبرمجين يستخدمون تلك الكلمة بمعنى «التعليقات التي تحدد سلوك دالة». لكن إن وسّعنا نظرتنا قليلًا، أمكننا اعتبار نوع الدالة جزءًا من مواصفتها. فهو على الأقل معنى ذو صلة بالكلمة.

وعادةً ما تكون التعريفات في الوحدة أكثر ترابطًا من تلك الموجودة في MyModule. فكثيرًا ما تنفّذ الوحدة بنية بيانات ما. على سبيل المثال، إليك وحدة للمكدّسات منفّذة كقوائم مترابطة:

module ListStack = struct
  (** [empty] is the empty stack. *)
  let empty = []
  (** [is_empty s] is whether [s] is empty. *)
  let is_empty = function [] -> true | _ -> false
  (** [push x s] pushes [x] onto the top of [s]. *)
  let push x s = x :: s
  (** [Empty] is raised when an operation cannot be applied
      to an empty stack. *)
  exception Empty
  (** [peek s] is the top element of [s].
      Raises [Empty] if [s] is empty. *)
  let peek = function
    | [] -> raise Empty
    | x :: _ -> x
  (** [pop s] is all but the top element of [s].
      Raises [Empty] if [s] is empty. *)
  let pop = function
    | [] -> raise Empty
    | _ :: s -> s
end

module ListStack :
  sig
    val empty : 'a list
    val is_empty : 'a list -> bool
    val push : 'a -> 'a list -> 'a list
    exception Empty
    val peek : 'a list -> 'a
    val pop : 'a list -> 'a list
  end

مهم

قد تفاجئك مواصفة pop. لاحظ أنها لا تعيد العنصر الأعلى. فتلك مهمة peek. بل تعيد pop جميع العناصر عدا العنصر الأعلى.

ويمكننا بعدها استخدام تلك الوحدة للتعامل مع مكدّس:

ListStack.push 2 (ListStack.push 1 ListStack.empty)

- : int list = [2; 1]

تحذير

هناك التباس شائع يكمن هنا للمبرمجين القادمين من لغات كائنية التوجه. فمن المغري التفكير في ListStack كأنه كائن تستدعي عليه طرقًا. بل إن ListStack.push تبدو غامضًا كأننا نستدعي طريقة push على كائن ListStack. لكن ليس ذلك ما يحدث. ففي لغة كائنية التوجه يمكنك إنشاء نسخ كثيرة من كائنات المكدّسات. لكن هنا، لا يوجد إلا ListStack واحد. علاوة على أنه ليس كائنًا، وذلك في جزء كبير منه لأنه لا يملك أي فكرة عن كلمة مفتاحية مثل this أو self للدلالة على الكائن المستقبِل لاستدعاء الطريقة.

من المسلم به أن تلك الشيفرة مطوّلة نوعًا ما. وسنرى قريبًا عدة حلول لتلك المشكلة، لكن إليك حلًا واحدًا الآن:

ListStack.(push 2 (push 1 empty))

- : int list = [2; 1]

فبكتابة ListStack.(e)، تصبح جميع الأسماء من ListStack قابلة للاستخدام في e دون الحاجة إلى كتابة البادئة ListStack. في كل مرة. ومن التحسينات الأخرى استخدام مؤثر خط الأنابيب:

ListStack.(empty |> push 1 |> push 2)

- : int list = [2; 1]

والآن يمكننا قراءة الشيفرة من اليسار إلى اليمين دون عناء تحليل الأقواس. جميل.

تحذير

هناك التباس آخر شائع من عالم كائنية التوجه يكمن هنا. فمن المغري التفكير في ListStack كأنه صنف تُنشأ منه كائنات. لكن ليس ذلك هو الحال. لاحظ أنه لا يوجد مؤثر new مستخدم لإنشاء مكدّس أعلاه، ولا أي منشئات (بالمعنى الكائني للكلمة).

الوحدات أكثر أساسية بكثير من الأصناف. فالوحدة مجرد مجموعة من التعريفات في فضاء أسماء خاص بها. وفي ListStack، لدينا بعض تعريفات الدوال — push وpop وغيرها — وقيمة واحدة هي empty.

لذا فبينما في Java قد ننشئ مكدّسين باستخدام شيفرة كهذه:

Stack s1 = new Stack();
s1.push(1);
s1.push(2);
Stack s2 = new Stack();
s2.push(3);

يمكن في OCaml إنشاء المكدّسين نفسيهما كما يلي:

let s1 = ListStack.(empty |> push 1 |> push 2)
let s2 = ListStack.(empty |> push 3)

val s1 : int list = [2; 1]

val s2 : int list = [3]

5.2.1. تعريفات الوحدات

تشبه الكلمة المفتاحية module في التعريف كثيرًا الكلمة المفتاحية let في التعريف التي تعلمناها سابقًا. (كان بإمكان مصممي OCaml افتراضيًا اختيار استخدام let_module بدلًا من module للتأكيد على التشابه.) والفرق هو فقط أن:

• let تربط قيمة باسم، بينما
• module تربط قيمة وحدة (module value) باسم.

الصياغة.

أكثر صياغة شيوعًا لتعريف وحدة هي ببساطة:

module ModuleName = struct
  module_items
end

حيث يمكن أن تشمل module_items داخل البنية تعريفات let وتعريفات type وتعريفات exception، إضافةً إلى تعريفات module متداخلة. ويجب أن تبدأ أسماء الوحدات بحرف كبير، وتُكتب اصطلاحيًا بنمط CamelCase لا Snake_case.

لكن النسخة الأدق من الصياغة ستكون:

module ModuleName = module_expression

حيث يكون struct مجرد نوع واحد من أنواع module_expression. وإليك نوعًا آخر: اسم وحدة معرّفة مسبقًا. على سبيل المثال، يمكنك كتابة module L = List إن أردت اسمًا مختصرًا لوحدة List. وسنرى أنواعًا أخرى من تعبيرات الوحدات لاحقًا في هذا القسم وهذا الفصل.

ويمكن اختياريًا إنهاء التعريفات داخل البنية بـ ;; كما في الواجهة التفاعلية:

module M = struct
  let x = 0;;
  type t = int;;
end

module M : sig val x : int type t = int end

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

ومن حالات استخدام ;; أن تريد تقييم تعبير كجزء من وحدة:

module M = struct
  let x = 0;;
  assert (x = 0);;
end

module M : sig val x : int end

لكن يمكن إعادة كتابة ذلك دون ;; هكذا:

module M = struct
  let x = 0
  let _ = assert (x = 0)
end

module M : sig val x : int end

ويمكن كتابة البنى أيضًا في سطر واحد، مع ;; اختيارية بين العناصر لأجل قابلية القراءة:

module N = struct let x = 0 let y = 1 end
module O = struct let x = 0;; let y = 1 end

module N : sig val x : int val y : int end

module O : sig val x : int val y : int end

والبنية الفارغة مسموح بها:

module E = struct end

module E : sig end

الدلالات الديناميكية.

نعلم بالفعل أن التعبيرات تُقيَّم إلى قيم. وبالمثل، يُقيَّم تعبير الوحدة إلى قيمة وحدة (module value) أو «وحدة» اختصارًا. والنوع الوحيد المثير للاهتمام من تعبيرات الوحدات الذي لدينا حتى الآن، من منظور التقييم على أي حال، هو البنية. وتقييم البنى سهل: قيّم كل تعريف فيها فحسب، بالترتيب الذي تظهر به. وبسبب ذلك، تكون التعريفات السابقة في النطاق في التعريفات اللاحقة، لا العكس. لذا هذه الوحدة سليمة:

module M = struct
  let x = 0
  let y = x
end

module M : sig val x : int val y : int end

لكن هذه الوحدة ليست سليمة، لأنه وقت تقييم تعريف let الخاص بـ x، لم تكن y قد رُبطت بعد:

module M = struct
  let x = y
  let y = 0
end

File "[13]", line 2, characters 10-11:
2 |   let x = y
              ^
Error: Unbound value y

وبالطبع يمكن استخدام التعاود المتبادل إن أُريد:

module M = struct
  (* Requires: input is non-negative. *)
  let rec even = function
    | 0 -> true
    | n -> odd (n - 1)
  and odd = function
    | 0 -> false
    | n -> even (n - 1)
end

module M : sig val even : int -> bool val odd : int -> bool end

الدلالات الساكنة.

تكون البنية سليمة الأنواع إذا كانت جميع التعريفات فيها سليمة الأنواع هي نفسها، وفقًا لجميع قواعد الكتابة التي تعلمناها بالفعل.

وكما رأينا في مخرجات الواجهة التفاعلية، فإن نوع وحدة البنية توقيع. لكن لأنواع الوحدات أكثر من ذلك. ولنؤجّل ذلك لحظة لنتحدث أولًا عن النطاق.

5.2.2. النطاق وopen

بعد تعريف وحدة M، يمكنك الوصول إلى الأسماء داخلها باستخدام مؤثر النقطة. على سبيل المثال:

module M = struct let x = 42 end

module M : sig val x : int end

M.x

- : int = 42

بالطبع، من خارج الوحدة لا يكون للاسم x وحده معنى:

x

File "[17]", line 1, characters 0-1:
1 | x
    ^
Error: Unbound value x

لكن يمكنك جلب جميع تعريفات وحدة إلى النطاق الحالي باستخدام open:

open M

x

- : int = 42

فتح وحدة يشبه كتابة تعريف محلي لكل اسم معرّف في الوحدة. على سبيل المثال، يجلب open String جميع التعريفات من وحدة String إلى النطاق، وله أثر على فضاء الأسماء المحلي مشابه لما يلي:

let length = String.length
let get = String.get
let lowercase_ascii = String.lowercase_ascii
...

وإذا كانت هناك أنواع أو استثناءات أو وحدات معرّفة في وحدة ما، فتُجلب هي أيضًا إلى النطاق بـ open.

الوحدة المفتوحة دائمًا. هناك وحدة خاصة تسمى Stdlib تُفتح تلقائيًا في كل برنامج OCaml. وهي تحتوي على الدوال والمؤثرات «المدمجة». لذا لا تحتاج أبدًا إلى سابقة Stdlib. على أي من الأسماء التي تعرّفها، وإن كان يمكنك فعل ذلك إن احتجت يومًا إلى تحديد اسم منها تحديدًا لا لبس فيه. وفي أيام سابقة، كانت هذه الوحدة تسمى Pervasives، وقد ترى ذلك الاسم بعد في بعض قواعد الشيفرة.

open كعنصر وحدة. يُعد open نوعًا آخر من module_item. لذا يمكننا فتح وحدة داخل أخرى:

module M = struct
  open List
  (** [uppercase_all lst] upper-cases all the elements of [lst]. *)
  let uppercase_all = map String.uppercase_ascii
end

module M : sig val uppercase_all : string list -> string list end

بما أن List مفتوحة، فالاسم map منها في النطاق. لكن ماذا لو أردنا التخلص من String. أيضًا؟

module M = struct
  open List
  open String
  (** [uppercase_all lst] upper-cases all the elements of [lst]. *)
  let uppercase_all = map uppercase_ascii
end

File "[21]", line 6, characters 26-41:
6 |   let uppercase_all = map uppercase_ascii
                              ^^^^^^^^^^^^^^^
Error: The value uppercase_ascii has type string -> string
       but an expression was expected of type char -> char
       Type string is not compatible with type char

أصبحت لدينا الآن مشكلة، لأن String تعرّف أيضًا الاسم map، لكن بنوع مختلف عن List. وكما هي العادة، يظلّل التعريف اللاحق تعريفًا سابقًا، فيُختار String.map بدلًا من List.map كما قصدنا.

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

ملاحظة

لذا من الممارسات الجيدة عمومًا ألا تفتح جميع الوحدات التي ستستخدمها في أعلى ملف ‎.ml أو بنية. وهذا ربما يختلف عن طريقة عملك المعتادة مع لغات مثل Java، حيث قد تستورد حزمًا كثيرة بـ *. بل من الجيد تحديد النطاق الذي تفتح فيه الوحدات.

تقييد نطاق open. رأينا بالفعل طريقة لتقييد نطاق open: M.(e). فداخل e تكون جميع الأسماء من الوحدة M في النطاق. وهذا مفيد لاستخدام M لفترة وجيزة في تعبير قصير:

(* remove surrounding whitespace from [s] and convert it to lower case *)
let s = "BigRed "
let s' = s |> String.trim |> String.lowercase_ascii (* long way *)
let s'' = String.(s |> trim |> lowercase_ascii) (* short way *)

val s : string = "BigRed "

val s' : string = "bigred"

val s'' : string = "bigred"

لكن ماذا لو أردت جلب وحدة إلى النطاق لدالة كاملة، أو لكتلة شيفرة أكبر أخرى؟ الصياغة لذلك (الغريبة كما نعترف) هي let open M in e. وهي تجعل جميع الأسماء من M في النطاق داخل e. على سبيل المثال:

(** [lower_trim s] is [s] in lower case with whitespace removed. *)
let lower_trim s =
  let open String in
  s |> trim |> lowercase_ascii

val lower_trim : string -> string = <fun>

وبالعودة إلى مثالنا uppercase_all، قد يكون الأفضل تجنّب أي نوع من الفتح وأن نكون صريحين ببساطة في أي وحدة نستخدم وأين:

module M = struct
  (** [uppercase_all lst] upper-cases all the elements of [lst]. *)
  let uppercase_all = List.map String.uppercase_ascii
end

module M : sig val uppercase_all : string list -> string list end

5.2.3. تعريفات أنواع الوحدات

رأينا بالفعل أن OCaml يستنتج توقيعًا كنوع للوحدة. ولنرَ الآن كيفية كتابة أنواع الوحدات تلك بأنفسنا. وكمثال، إليك نوع وحدة لمكدّساتنا القائمة على القوائم:

module type LIST_STACK = sig
  exception Empty
  val empty : 'a list
  val is_empty : 'a list -> bool
  val push : 'a -> 'a list -> 'a list
  val peek : 'a list -> 'a
  val pop : 'a list -> 'a list
end

module type LIST_STACK =
  sig
    exception Empty
    val empty : 'a list
    val is_empty : 'a list -> bool
    val push : 'a -> 'a list -> 'a list
    val peek : 'a list -> 'a
    val pop : 'a list -> 'a list
  end

والآن، بعد أن أصبح لدينا وحدة ونوع وحدة معًا للمكدّسات القائمة على القوائم، ينبغي أن ننقل تعليقات المواصفة من البنية إلى التوقيع. فتلك التعليقات جزء صحيح من مواصفة الأسماء في التوقيع. فهي تحدد السلوك، فتوسّع بذلك مواصفة الأنواع التي توفرها إعلانات val.

module type LIST_STACK = sig
  (** [Empty] is raised when an operation cannot be applied
      to an empty stack. *)
  exception Empty
  (** [empty] is the empty stack. *)
  val empty : 'a list
  (** [is_empty s] is whether [s] is empty. *)
  val is_empty : 'a list -> bool
  (** [push x s] pushes [x] onto the top of [s]. *)
  val push : 'a -> 'a list -> 'a list
  (** [peek s] is the top element of [s].
      Raises [Empty] if [s] is empty. *)
  val peek : 'a list -> 'a
  (** [pop s] is all but the top element of [s].
      Raises [Empty] if [s] is empty. *)
  val pop : 'a list -> 'a list
end
module ListStack = struct
  let empty = []
  let is_empty = function [] -> true | _ -> false
  let push x s = x :: s
  exception Empty
  let peek = function
    | [] -> raise Empty
    | x :: _ -> x
  let pop = function
    | [] -> raise Empty
    | _ :: s -> s
end

module type LIST_STACK =
  sig
    exception Empty
    val empty : 'a list
    val is_empty : 'a list -> bool
    val push : 'a -> 'a list -> 'a list
    val peek : 'a list -> 'a
    val pop : 'a list -> 'a list
  end

module ListStack :
  sig
    val empty : 'a list
    val is_empty : 'a list -> bool
    val push : 'a -> 'a list -> 'a list
    exception Empty
    val peek : 'a list -> 'a
    val pop : 'a list -> 'a list
  end

لكن لا شيء حتى الآن يخبر OCaml بوجود علاقة بين LIST_STACK وListStack. وإذا أردنا أن يضمن OCaml أن ListStack تملك فعلًا نوع الوحدة الذي يحدده LIST_STACK، يمكننا إضافة تعليق نوعي في السطر الأول من تعريف module:

module ListStack : LIST_STACK = struct
  let empty = []
  let is_empty = function [] -> true | _ -> false
  let push x s = x :: s
  exception Empty
  let peek = function
    | [] -> raise Empty
    | x :: _ -> x
  let pop = function
    | [] -> raise Empty
    | _ :: s -> s
end

module ListStack : LIST_STACK

يوافق المصرّف على أن الوحدة ListStack تعرّف فعلًا جميع العناصر التي يحددها LIST_STACK بأنواع مناسبة. ولو كنا قد أغفلنا عنصرًا ما بالخطأ، لرُفض التعليق النوعي:

module ListStack : LIST_STACK = struct
  let empty = []
  let is_empty = function [] -> true | _ -> false
  let push x s = x :: s
  exception Empty
  let peek = function
    | [] -> raise Empty
    | x :: _ -> x
  (* [pop] is missing *)
end

File "[28]", lines 1-15, characters 32-3:
 1 | ................................struct
 2 |   let empty = []
 3 |
 4 |   let is_empty = function [] -> true | _ -> false
 5 |
...
12 |     | x :: _ -> x
13 |
14 |   (* [pop] is missing *)
15 | end
Error: Signature mismatch:
       ...
       The value pop is required but not provided
       File "[26]", line 21, characters 2-30: Expected declaration

الصياغة.

أكثر صياغة شيوعًا لنوع وحدة هي ببساطة:

module type ModuleTypeName = sig
  specifications
end

حيث يمكن أن تشمل specifications داخل توقيع إعلانات val وتعريفات الأنواع وتعريفات الاستثناءات وتعريفات module type المتداخلة. ومثل البنى، يمكن كتابة التوقيع على أسطر كثيرة أو على سطر واحد فقط، والتوقيع الفارغ sig end مسموح به.

لكن، كما رأينا في تعريفات الوحدات، ستكون النسخة الأدق من الصياغة:

module type ModuleTypeName = module_type

حيث يكون التوقيع مجرد نوع واحد من أنواع module_type. ومن الأنواع الأخرى اسم نوع وحدة معرّف مسبقًا — مثل module type LS = LIST_STACK. وسنرى أنواع وحدات أخرى لاحقًا في هذا القسم وهذا الفصل.

وبحكم العرف، تُكتب أسماء أنواع الوحدات عادةً بنمط CamelCase، مثل أسماء الوحدات. فلماذا استخدمنا ALL_CAPS أعلاه لـ LIST_STACK؟ كان ذلك لتجنّب نقطة التباس محتملة في ذلك المثال، التي نوضحها الآن. كان يمكننا بدلًا من ذلك استخدام ListStack اسمًا للوحدة ونوع الوحدة معًا:

module type ListStack = sig ... end
module ListStack : ListStack = struct ... end

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

ملاحظة

كان استخدام ALL_CAPS لأنواع الوحدات شائعًا في وقت ما، وقد تراه بعد. وهو عرف أقدم من Standard ML. لكن الأعراف الاجتماعية لاستخدام الأحرف الكبيرة كلها تغيرت منذ تلك الأيام. فقد يبدو اسم مثل LIST_STACK للقارئ الحديث كأن شيفرتك تصرخ في وجهه بوقاحة. وهذا معنى ضمني تطوّر في الثمانينيات. وكانت لغات البرمجة الأقدم (مثل Pascal وCOBOL وFORTRAN) تستخدم عادةً الأحرف الكبيرة كلها للكلمات المفتاحية وحتى لأسمائها نفسها. ولا تزال اللغات الحديثة تستخدم اصطلاحيًا الأحرف الكبيرة كلها للثوابت — انظر، على سبيل المثال، Math.PI في Java أو دليل الأسلوب في Python.

المزيد من الصياغة.

ينبغي أن نضيف الآن صياغة التعليقات النوعية لأنواع الوحدات أيضًا. فقد تشمل تعريفات الوحدات تعليقًا نوعيًا اختياريًا:

module ModuleName : module_type = module_expression

وقد تشمل تعبيرات الوحدات تعليقات نوعية يدوية:

(module_expression : module_type)

وتلك الصياغة مماثلة لكيفية كتابتنا (e : t) لتحديد النوع t لتعبير e يدويًا.

وإليك بضعة أمثلة لبيان كيف يمكن استخدام تلك الصياغة:

module ListStackAlias : LIST_STACK = ListStack
(* equivalently *)
module ListStackAlias = (ListStack : LIST_STACK)
module M : sig val x : int end = struct let x = 42 end
(* equivalently *)
module M = (struct let x = 42 end : sig val x : int end)

module ListStackAlias : LIST_STACK

module ListStackAlias : LIST_STACK

module M : sig val x : int end

module M : sig val x : int end

كما يمكن أن تشمل أنواع الوحدات مواصفات وحدات متداخلة:

module type X = sig
  val x : int
end
module type T = sig
  module Inner : X
end
module M : T = struct
  module Inner : X = struct
    let x = 42
  end
end

module type X = sig val x : int end

module type T = sig module Inner : X end

module M : T

في المثال أعلاه، يحدد T أنه يجب أن توجد وحدة داخلية باسم Inner نوع وحدتها X. وهنا التعليق النوعي إلزامي، لأننا لو لم نضعه لما عُرف شيء عن Inner. ولذا فعند تنفيذ T، على الوحدة M أن توفر وحدة (i) بهذا الاسم، و(ii) تحقق مواصفات نوع الوحدة X.

الدلالات الديناميكية.

بما أن أنواع الوحدات هي في الواقع أنواع، فهي لا تُقيَّم. ولا دلالات ديناميكية لها.

الدلالات الساكنة.

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

5.2.4. دلالات أنواع الوحدات

إذا كانت M مجرد كتلة struct، فإن نوع وحدتها هو أي توقيع يستنتجه المصرّف لها. لكن يمكن تغيير ذلك بالتعليقات النوعية لأنواع الوحدات. والسؤال الرئيسي الذي علينا الإجابة عنه هو: ماذا يعني التعليق النوعي بالنسبة إلى الوحدات؟ أي ماذا يعني عندما نكتب : T في module M : T = ...؟

وهناك خاصيتان يضمنهما المصرّف:

1. مطابقة التوقيع (signature matching): كل اسم معلَن في T معرّف في M بالنوع نفسه أو بنوع أعم.
2. التغليف (encapsulation) أي العتامة (opacity): أي اسم معرّف في M لا يظهر في T لا يكون مرئيًا لشيفرة خارج M.

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

في Java، تنشئ الكلمة المفتاحية extends علاقات تنميط فرعي بين الأصناف:

class C { }
class D extends C { }
D d = new D();
C c = d;

والتنميط الفرعي هو ما يسمح بإسناد d إلى c في السطر الأخير من ذلك المثال. فبما أن D يمتد C، يعتبر Java أن D نمط فرعي لـ C، ومن ثم يسمح باستخدام كائن منسوخ من D في أي موضع يُتوقع فيه كائن منسوخ من C. وبالطبع، يعود الأمر إلى مبرمج D في ضمان ألا يؤدي ذلك إلى أخطاء في وقت التشغيل؛ فعلى طرق D أن تضمن، على سبيل المثال، تحقق ثوابت الصنف C. لذا فبكتابة D extends C، يتحمّل المبرمج بعض المسؤولية، ويكسب في المقابل بعض المرونة بتمكنه من كتابة عبارات إسناد كهذه.

فما هو «النمط الفرعي»؟ يتوقف هذا المفهوم على اللغة من نواحٍ كثيرة. وللحصول على مفهوم مستقل عن اللغة، نلجأ إلى باربرا ليسكوف. فقد حصلت على جائزة تورينغ في عام 2008، ويعود ذلك جزئيًا إلى عملها في تصميم اللغات كائنية التوجه. وقبل ذلك بعشرين عامًا، اخترعت ما يسمى الآن مبدأ استبدال ليسكوف (Liskov Substitution Principle) لشرح التنميط الفرعي. وهو يقول إنه إذا كان S نمطًا فرعيًا لـ T، فإن استبدال كائن من النوع S بكائن من النوع T ينبغي ألا يغيّر أي سلوك مرغوب فيه في البرنامج. ويمكنك رؤية ذلك يعمل في مثال Java أعلاه، سواء من حيث ما تسمح به اللغة أو ما يجب على المبرمج ضمانه.

وتسمى النكهة الخاصة للتنميط الفرعي في Java التنميط الفرعي الاسمي (nominal subtyping)، أي أنه قائم على الأسماء. وفي مثالنا، D نمط فرعي لـ C بسبب طريقة إعلان الأسماء فحسب. فقد أصدر المبرمج مرسومًا بعلاقة التنميط الفرعي تلك، وقبلت اللغة المرسوم دون سؤال. بل إن علاقات التنميط الفرعي الوحيدة الموجودة هي تلك التي صدر بها مرسوم بالاسم عبر استخدامات كهذه لـ extends وimplements.

وحان الآن وقت العودة إلى OCaml. فنظام وحداتها يستخدم التنميط الفرعي أيضًا، بالحدس نفسه الكامن وراء مبدأ استبدال ليسكوف. لكن OCaml يستخدم نكهة مختلفة تسمى التنميط الفرعي البنيوي (structural subtyping). أي أنه قائم على بنية الوحدات لا على أسمائها. و«البنية» هنا تعني ببساطة التعريفات المحتواة في الوحدة. وتُستخدم تلك التعريفات لتحديد ما إذا كان (M : T) مقبولًا كتعليق نوعي، حيث M وحدة وT نوع وحدة.

ولنتلاعب بفكرة البنية هذه عبر عدة أمثلة، بدءًا بهذه الوحدة:

module M = struct
  let x = 0
  let z = 2
end

module M : sig val x : int val z : int end

تحتوي الوحدة M على تعريفين. ويمكنك رؤية ذلك في توقيع الوحدة الذي تطبعه OCaml: فهو يحتوي على x : int وz : int. وبسبب الأول، يُقبل التعليق النوعي التالي:

module type X = sig
  val x : int
end
module MX = (M : X)

module type X = sig val x : int end

module MX : X

يتطلب نوع الوحدة X عنصر وحدة باسم x من النوع int. والوحدة M تحتوي فعلًا على عنصر كهذا. لذا فـ (M : X) صالح. والأمر نفسه سينجح مع z:

module type Z = sig
  val z : int
end
module MZ = (M : Z)

module type Z = sig val z : int end

module MZ : Z

أو مع x وz معًا:

module type XZ = sig
  val x : int
  val z : int
end
module MXZ = (M : XZ)

module type XZ = sig val x : int val z : int end

module MXZ : XZ

لكن ليس مع y، لأن M لا تحتوي على عنصر كهذا:

module type Y = sig
  val y : int
end
module MY = (M : Y)

module type Y = sig val y : int end

File "[35]", line 5, characters 13-14:
5 | module MY = (M : Y)
                 ^
Error: Signature mismatch:
       Modules do not match:
         sig val x : int val z : int end
       is not included in
         Y
       The value y is required but not provided
       File "[35]", line 2, characters 2-13: Expected declaration

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

sig val x : int val z : int end

هو التوقيع الذي يستخدمه OCaml لـ M. وبما أن M وحدة، فذلك التوقيع مجرد الأسماء والأنواع كما عُرّفت في M. ويقارن OCaml ذلك التوقيع بـ Y، فيكتشف عدم تطابق:

The value `y' is required but not provided

وذلك لأن Y تتطلب y لكن M لا توفر تعريفًا كهذا.

وإليك رسالة خطأ أخرى للتدرب على قراءتها:

module type Xstring = sig
  val x : string
end
module MXstring = (M : Xstring)

module type Xstring = sig val x : string end

File "[36]", line 5, characters 19-20:
5 | module MXstring = (M : Xstring)
                       ^
Error: Signature mismatch:
       Modules do not match:
         sig val x : int val z : int end
       is not included in
         Xstring
       Values do not match: val x : int is not included in val x : string
       The type int is not compatible with the type string
       File "[36]", line 2, characters 2-16: Expected declaration
       File "[31]", line 2, characters 6-7: Actual declaration

الخطأ هذه المرة هو

Values do not match: val x : int is not included in val x : string

لقد تغيّر الخطأ، لأن M توفر فعلًا تعريفًا لـ x، لكن بنوع مختلف عن الذي تتطلبه Xstring. وهذا معنى «is not included in» هنا. فلماذا لا يقول OCaml شيئًا أبسط قليلًا مثل «is not the same as»؟ لأنه لا يلزم أن يكون النوعان متماثلين تمامًا. فإذا كان نوع القيمة الموفَّرة متعدد الأشكال، فقد يكفي أن يكون نوع القيمة المطلوبة تجسيدًا لذلك النوع المتعدد الأشكال.

على سبيل المثال، إذا تطلب توقيع نوعًا int -> int، فقد يكفي أن توفر بنية قيمة من النوع 'a -> 'a:

module type IntFun = sig
  val f : int -> int
end
module IdFun = struct
  let f x = x
end
module Iid = (IdFun : IntFun)

module type IntFun = sig val f : int -> int end

module IdFun : sig val f : 'a -> 'a end

module Iid : IntFun

حتى الآن كانت كل هذه الأمثلة مجرد مقارنة التعريفات التي يتطلبها توقيع بالتعريفات التي توفرها بنية. لكن إليك مثالًا قد يكون مفاجئًا:

module MXZ' = ((M : X) : Z)

File "[38]", line 1, characters 15-22:
1 | module MXZ' = ((M : X) : Z)
                   ^^^^^^^
Error: Signature mismatch:
       Modules do not match: X is not included in Z
       The value z is required but not provided
       File "[33]", line 2, characters 2-13: Expected declaration

فلماذا يشتكي OCaml من أن z مطلوبة لكنها غير موفَّرة؟ نعلم من تعريف M أنها تمتلك فعلًا قيمة z : int. ومع ذلك تدّعي رسالة الخطأ، على نحو غريب ربما:

The value `z' is required but not provided.

وسبب هذا الخطأ أننا قد أوردنا بالفعل التعليق النوعي X في تعبير الوحدة (M : X). وهذا يجعل تعبير الوحدة معروفًا عند نوع الوحدة X فحسب. بعبارة أخرى، نسينا بعد ذلك التعليق النوعي نسيانًا لا رجعة فيه وجود z. فكل ما يُعرف هو أن للوحدة عناصر يتطلبها X.

وبعد كل تلك الأمثلة، إليك الدلالات الساكنة للتعليقات النوعية لأنواع الوحدات:

• التعليق النوعي (M : T) صالح إذا كان نوع وحدة M نمطًا فرعيًا لـ T. ويصبح نوع وحدة (M : T) هو T بعد ذلك في أي فحص أنواع لاحق.
• نوع الوحدة S نمط فرعي لـ T إذا كانت مجموعة التعريفات في S مجموعة شاملة لتعريفات T. ويُسمح لتعريفات T بتجسيد متغيرات نوعية من S.

ولا تمثل كلمتا «sub» مقابل «super» في القاعدة الثانية خطأً طباعيًا. انظر إلى أنواع الوحدات والوحدات التالية:

module type T = sig
  val a : int
end
module type S = sig
  val a : int
  val b : bool
end
module A = struct
  let a = 0
end
module AB = struct
  let a = 0
  let b = true
end
module AC = struct
  let a = 0
  let c = 'c'
end

module type T = sig val a : int end

module type S = sig val a : int val b : bool end

module A : sig val a : int end

module AB : sig val a : int val b : bool end

module AC : sig val a : int val c : char end

يوفر نوع الوحدة S مجموعة شاملة للتعريفات في T، لأنه يضيف تعريفًا لـ b. فلماذا إذن يسمى S نمطًا فرعيًا لـ T؟ فكّر في مجموعة $\mathit{Type}(T)$ المكوّنة من كل قيم الوحدات M التي تحقق M : T. وتحتوي تلك المجموعة على A وAB وAC وغيرها كثير. وفكّر أيضًا في مجموعة $\mathit{Type}(S)$ المكوّنة من كل قيم الوحدات M التي تحقق M : S. وتحتوي تلك المجموعة على AB لكن ليس على A ولا AC. لذا فـ $\mathit{Type}(S) \subset \mathit{Type}(T)$، لأن هناك بعض قيم الوحدات في $\mathit{Type}(T)$ لكنها ليست في $\mathit{Type}(S)$.

وكمثال آخر، قد يخصص نوع وحدة StackHistory للمكدّسات توقيع Stack المعتاد لدينا بإضافة عملية history : 'a t -> int تعيد عدد العناصر التي دُفعت إلى المكدّس في تاريخه. وتلك العملية history تجعل مجموعة التعريفات في StackHistory أكبر من مجموعتها في Stack، ومن هنا استخدام «superset» في القاعدة أعلاه. لكن مجموعة قيم الوحدات التي تنفّذ StackHistory أصغر من مجموعة قيم الوحدات التي تنفّذ Stack، ومن هنا استخدام «subset».

5.2.5. أنواع الوحدات ساكنة

تُتخذ القرارات المتعلقة بصحة التعليقات النوعية لأنواع الوحدات في وقت التصريف لا في وقت التشغيل.

مهم

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

فمبرمجو Python، على سبيل المثال، معتادون على ما يسمى «الكتابة البطية» (duck typing). وقد يتوقعون أن يكون ((M : X) : Z) صالحًا، لأن z موجودة فعلًا في وقت التشغيل داخل M. لكن في OCaml، أخفى النوع في وقت التصريف لـ (M : X) وجود z عن الأنظار إخفاءً لا رجعة فيه.

أما مبرمجو Java، فقد يتوقعون أن تعمل التعليقات النوعية للوحدات مثل التحويلات النوعية القسرية. لذا قد يبدو صالحًا «تحويل» M أولًا إلى X ثم إلى Z. وفي Java تُفحص تلك التحويلات النوعية القسرية، حسب الحاجة، في وقت التشغيل. لكن التعليقات النوعية للوحدات في OCaml ساكنة. فبمجرد إجراء تعليق نوعي بـ X، لا سبيل إلى فحص ما قد يوجد من عناصر أخرى في الوحدة في وقت التصريف — فذلك سيتطلب فحصًا في وقت التشغيل لا تسمح به OCaml.

وفي كلتا الحالتين قد يبدو الأمر وكأن OCaml مقيّدة أكثر مما ينبغي. ربما. لكن في مقابل ذلك التقييد، تضمن OCaml غياب الأخطاء في وقت التشغيل من النوع الذي قد يحدث في Java أو Python، سواء بسبب خطأ في وقت التشغيل من تحويل نوعي قسري، أو خطأ في وقت التشغيل من طريقة مفقودة.

5.2.6. الوحدات من الرتبة الأولى

ليست الوحدات من الرتبة الأولى في OCaml بمثل ما للدوال. لكن من الممكن حزم الوحدات كقيم من الرتبة الأولى. وبإيجاز:

• (module M : T) تحزم الوحدة M بنوع الوحدة T في قيمة.
• (val e : T) تلغي حزم e إلى وحدة من النوع T.

ولن نتوسع في ذلك أكثر، لكن إن كنت فضوليًا يمكنك الاطلاع على الدليل.

5.3. الوحدات والواجهة التفاعلية

ملاحظة

يستخدم الفيديو أدناه نظام البناء القديم، أي ocamlbuild، بدلًا من نظام البناء الجديد، أي dune. وتتغير بعض التفاصيل مع dune، كما هو موصوف في النص أدناه.

هناك عدة أمور عملية تتعلق بالوحدات والواجهة التفاعلية من المهم إتقانها لاستخدام الاثنتين معًا بفعالية.

5.3.1. تحميل الوحدات المصرّفة

يُنتج تصريف ملف OCaml وحدة تحمل اسم الملف نفسه، لكن بحرف أول كبير. ويمكن تحميل تلك الوحدات المصرّفة في الواجهة التفاعلية باستخدام #load.

على سبيل المثال، افترض أنك أنشأت ملفًا باسم mods.ml وضعت فيه الشيفرة التالية:

let b = "bigred"
let inc x = x + 1
module M = struct
  let y = 42
end

لاحظ أنه لا يوجد module Mods = struct ... end حول ذلك. فالشيفرة في أعلى مستوى في الملف، إن جاز التعبير.

ثم افترض أنك كتبت ocamlc mods.ml لتصريفه. ومن الملفات المنشأة حديثًا ملف mods.cmo: وهو ملف كائن وحدة مصرّف، أي شيفرة بايتية.

ويمكنك جعل تلك الشيفرة البايتية متاحة للاستخدام في الواجهة التفاعلية بالتوجيهات التالية. تذكّر أن محرف # مطلوب أمام التوجيه. وهو ليس جزءًا من الموجه.

# #load "mods.cmo";;

يحمل ذلك التوجيه الشيفرة البايتية الموجودة في mods.cmo، فيجعل وحدة باسم Mods متاحة للاستخدام. والأمر تمامًا كما لو كنت قد أدخلت هذه الشيفرة:

module Mods = struct
  let b = "bigred"
  let inc x = x + 1
  module M = struct
    let y = 42
  end
end

module Mods :
  sig val b : string val inc : int -> int module M : sig val y : int end end

لذا سيتقيّم كلا التعبيرين التاليين بنجاح:

Mods.b;;
Mods.M.y;;

- : string = "bigred"

- : int = 42

لكن هذا سيفشل:

inc

File "[3]", line 1, characters 0-3:
1 | inc
    ^^^
Error: Unbound value inc
Hint: Did you mean incr?

يفشل لأن inc في فضاء أسماء Mods.

Mods.inc

- : int -> int = <fun>

وبالطبع، إذا فتحت الوحدة، أمكنك تسمية inc مباشرةً:

open Mods;;
inc;;

- : int -> int = <fun>

5.3.2. Dune

يوفر Dune أمرًا يسهّل بدء utop والمكتبات محمّلة مسبقًا. افترض أننا أضفنا ملف dune هذا إلى الدليل نفسه الذي فيه mods.ml:

(library
 (name mods))

يخبر ذلك dune ببناء مكتبة باسم Mods من mods.ml (ومن أي ملفات أخرى في الدليل نفسه، لو وُجدت). ثم يمكننا تشغيل هذا الأمر لبدء utop وتلك المكتبة محمّلة مسبقًا:

$ dune utop

والآن يمكننا فورًا الوصول إلى مكونات Mods دون الحاجة إلى إصدار توجيه #load:

Mods.inc

- : int -> int = <fun>

ويقبل الأمر dune utop اسم دليل كوسيط إن أردت تحميل مكتبات في دليل فرعي معيّن من شيفرة مصادرك.

5.3.3. تهيئة الواجهة التفاعلية

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

والحل هو إنشاء ملف في دليل العمل وتسميته .ocamlinit. لاحظ أن النقطة في مقدمة اسم الملف مطلوبة وتجعله ملفًا مخفيًا لا يظهر في قوائم الأدلة إلا إذا طُلب صراحةً (مثلًا بـ ls -a). وسيعالج utop كل ما في .ocamlinit عند تحميله.

على سبيل المثال، افترض أنك أنشأت ملفًا باسم .ocamlinit في الدليل نفسه الذي فيه mods.ml، ووضعت في ذلك الملف الشيفرة التالية:

open Mods;;

أعد الآن تشغيل utop بالأمر dune utop. ستكون جميع الأسماء المعرّفة في Mods في النطاق بالفعل. على سبيل المثال، سينجح هذان:

inc;;
M.y;;

- : int -> int = <fun>

- : int = 42

5.3.4. طلب المكتبات

افترض أنك أردت تجربة بعض شيفرة OUnit في utop. لا يمكنك فعلًا فتحها:

open OUnit2;;

File "[8]", line 1, characters 5-11:
1 | open OUnit2;;
         ^^^^^^
Error: Unbound module OUnit2
Hint: Did you mean Unit?

المشكلة أن مكتبة OUnit لم تُحمَّل بعد في utop. ويمكن تحميلها بالتوجيه التالي:

#require "ounit2";;

والآن يمكنك فتح الوحدة بنجاح دون الحصول على خطأ:

open OUnit2;;

5.3.5. #load مقابل #use

هناك فرق كبير بين #load لملف وحدة مصرّف و#use لملف مصادر غير مصرّف. فالأول يحمّل شيفرة بايتية ويجعلها متاحة للاستخدام. على سبيل المثال، أدى تحميل mods.cmo إلى إتاحة وحدة Mod، وأمكننا الوصول إلى أعضائها بتعبيرات مثل Mod.b. أما الثاني (#use) فهو تضمين نصي: فهو ككتابة محتويات الملف مباشرةً في الواجهة التفاعلية. لذا فإن استخدام mods.ml لا يؤدي إلى إتاحة وحدة Mod، ويمكن الوصول إلى التعريفات في الملف مباشرةً، مثل b.

على سبيل المثال، في التفاعل التالي، يمكننا الرجوع إلى b مباشرةً لكن لا يمكننا استخدام الاسم المؤهَّل Mods.b:

# #use "mods.ml"

# b;;
val b : string = "bigred"

# Mods.b;;
Error: Unbound module Mods

أما في هذا التفاعل، فالوضع معكوس:

# #directory "_build";;
# #load "mods.cmo";;

# Mods.b;;
- : string = "bigred"

# b;;
Error: Unbound value b

لذا عندما تستخدم الواجهة التفاعلية لتجربة شيفرتك، غالبًا ما يكون الأفضل العمل بـ #load بدلًا من #use. فالتوجيه #load يعكس بدقة كيفية تفاعل وحداتك بعضها مع بعض ومع العالم الخارجي.

5.4. التغليف

أحد الشواغل الرئيسية لنظام الوحدات هو توفير التغليف (encapsulation): أي إخفاء المعلومات المتعلقة بالتنفيذ خلف واجهة. ويجعل نظام وحدات OCaml ذلك ممكنًا بميزة رأيناها سابقًا: العتامة (opacity) التي تُنشئها التعليقات النوعية للوحدات. ومن الاستخدامات الخاصة للعتامة إعلان الأنواع المجرّدة (abstract types). وسندرس الفكرتين معًا في هذا القسم.

5.4.1. العتامة

عند تنفيذ وحدة ما، قد تكون لديك أحيانًا دوال مساعدة لا تريد كشفها لعملاء الوحدة. فمثلًا، ربما تنفّذ وحدة رياضيات توفر دالة عاملي تعاودية ذيلية:

module Math = struct
  (** [fact_aux n acc] is [n! * acc]. *)
  let rec fact_aux n acc =
    if n = 0 then acc else fact_aux (n - 1) (n * acc)
  (** [fact n] is [n!]. *)
  let fact n = fact_aux n 1
end

module Math : sig val fact_aux : int -> int -> int val fact : int -> int end

قد ترغب في جعل fact قابلة للاستخدام من عملاء Math، لكنك ترغب أيضًا في إبقاء fact_aux مخفية. غير أنك ترى في الشيفرة أعلاه أن fact_aux مرئية في التوقيع المستنتج لـ Math. ومن طرق إخفائها ببساطة تضمين fact_aux داخل fact:

module Math = struct
  (** [fact n] is [n!]. *)
  let fact n =
    (** [fact_aux n acc] is [n! * acc]. *)
    let rec fact_aux n acc =
      if n = 0 then acc else fact_aux (n - 1) (n * acc)
    in
    fact_aux n 1
end

module Math : sig val fact : int -> int end

انظر إلى التوقيع، ولاحظ اختفاء fact_aux. لكن ذلك التضمين يجعل fact أصعب قليلًا في القراءة. كما يعني أن fact_aux لم تعد متاحة لأي دوال أخرى داخل Math. وفي هذه الحالة لا مشكلة في ذلك غالبًا—إذ لا توجد على الأرجح دوال أخرى في Math تحتاج fact_aux. لكن لو وُجدت، لما أمكننا تضمين fact_aux.

لذا فثمة طريقة أخرى لإخفاء fact_aux عن عملاء Math مع إبقائها متاحة لمنفّذي Math، وهي استخدام نوع وحدة لا يكشف إلا الأسماء التي ينبغي للعملاء رؤيتها:

module type MATH = sig
  (** [fact n] is [n!]. *)
  val fact : int -> int
end
module Math : MATH = struct
  (** [fact_aux n acc] is [n! * acc]. *)
  let rec fact_aux n acc =
    if n = 0 then acc else fact_aux (n - 1) (n * acc)
  let fact n = fact_aux n 1
end

module type MATH = sig val fact : int -> int end

module Math : MATH

وبما أن MATH لا تذكر fact_aux، فإن التعليق النوعي Math : MATH يجعل fact_aux مخفية:

Math.fact_aux

File "[4]", line 1, characters 0-13:
1 | Math.fact_aux
    ^^^^^^^^^^^^^
Error: Unbound value Math.fact_aux

وبهذا المعنى تكون التعليقات النوعية للوحدات معتمة (opaque): فهي تستطيع منع رؤية عناصر الوحدة. ونقول إن نوع الوحدة يغلق (seals) الوحدة، فيصير أي مكوّن غير مسمى في نوع الوحدة غير قابل للوصول.

مهم

تذكّر إذن أن التعليقات النوعية للوحدات ليست فقط وسيلة للتحقق مما إذا كانت الوحدة تعرّف عناصر معينة. فهي تخفي العناصر أيضًا.

وماذا لو أردت التحقق من التعريفات فحسب دون إخفاء أي شيء؟ إذن لا تُقدّم التعليق النوعي عند تعريف الوحدة:

module type MATH = sig
  (** [fact n] is [n!]. *)
  val fact : int -> int
end
module Math = struct
  (** [fact_aux n acc] is [n! * acc]. *)
  let rec fact_aux n acc =
    if n = 0 then acc else fact_aux (n - 1) (n * acc)
  let fact n = fact_aux n 1
end
module MathCheck : MATH = Math

module type MATH = sig val fact : int -> int end

module Math : sig val fact_aux : int -> int -> int val fact : int -> int end

module MathCheck : MATH

والآن أصبح Math.fact_aux مرئية، لكن MathCheck.fact_aux ليست كذلك:

Math.fact_aux

- : int -> int -> int = <fun>

MathCheck.fact_aux

File "[7]", line 1, characters 0-18:
1 | MathCheck.fact_aux
    ^^^^^^^^^^^^^^^^^^
Error: Unbound value MathCheck.fact_aux

بل لم يكن يلزمك حتى تسمية وحدة «التحقق» لأنك لا تنوي الوصول إليها على الأرجح؛ كان يمكنك بدلًا من ذلك تركها بلا اسم:

module _ : MATH = Math

مقارنة بمحددات الرؤية. يشبه استخدام الإغلاق في OCaml إذن استخدام محددات الرؤية (visibility modifiers) مثل private وpublic في Java. بل إن من طرق التفكير في تعريفات أصناف Java أنها تعرّف عدة تواقيع في الوقت نفسه.

فمثلًا، تأمل صنف Java التالي:

class C {
  private int x;
  public int y;
}

والمقابل لذلك في OCaml سيكون الوحدات والأنواع التالية:

module type C_PUBLIC = sig
  val y : int
end
module CPrivate = struct
  let x = 0
  let y = 0
end
module C : C_PUBLIC = CPrivate

module type C_PUBLIC = sig val y : int end

module CPrivate : sig val x : int val y : int end

module C : C_PUBLIC

وبهذه التعريفات، لن تصل أي شيفرة تستخدم C إلا إلى الأسماء المكشوفة في نوع الوحدة C_PUBLIC.

ويمكن توسيع تلك المقابلة لتشمل محددات الرؤية الأخرى، protected والافتراضي أيضًا. وهذا يعني أن أصناف Java تعرّف فعليًا أربعة أنواع مترابطة، ويتأكد المصرّف من استخدام النوع الصحيح في كل موضع يُذكر فيه الاسم C في قاعدة الشيفرة. فلا عجب أن إتقان الرؤية في اللغات كائنية التوجه قد يكون صعبًا في البداية.

5.4.2. الأنواع المجرّدة

في قسم سابق نفّذنا المكدّسات كقوائم بالوحدة والنوع التاليين:

module type LIST_STACK = sig
  (** [Empty] is raised when an operation cannot be applied
      to an empty stack. *)
  exception Empty
  (** [empty] is the empty stack. *)
  val empty : 'a list
  (** [is_empty s] is whether [s] is empty. *)
  val is_empty : 'a list -> bool
  (** [push x s] pushes [x] onto the top of [s]. *)
  val push : 'a -> 'a list -> 'a list
  (** [peek s] is the top element of [s].
      Raises [Empty] if [s] is empty. *)
  val peek : 'a list -> 'a
  (** [pop s] is all but the top element of [s].
      Raises [Empty] if [s] is empty. *)
  val pop : 'a list -> 'a list
end
module ListStack : LIST_STACK = struct
  exception Empty
  let empty = []
  let is_empty = function [] -> true | _ -> false
  let push x s = x :: s
  let peek = function [] -> raise Empty | x :: _ -> x
  let pop = function [] -> raise Empty | _ :: s -> s
end

module type LIST_STACK =
  sig
    exception Empty
    val empty : 'a list
    val is_empty : 'a list -> bool
    val push : 'a -> 'a list -> 'a list
    val peek : 'a list -> 'a
    val pop : 'a list -> 'a list
  end

module ListStack : LIST_STACK

ماذا لو أردنا تعديل بنية المعطيات تلك لإضافة عملية لحجم المكدّس؟ الطريقة السهلة أن ننفّذها باستخدام List.length:

module type LIST_STACK = sig
  ...
  (** [size s] is the number of elements on the stack. *)
  val size : 'a list -> int
end
module ListStack : LIST_STACK = struct
  ...
  let size = List.length
end

ينتج عن ذلك تنفيذ خطي الزمن لـ size. وماذا لو أردنا تنفيذًا أسرع ثابت الزمن؟ مقابل قليل من المساحة، يمكننا تخزين حجم المكدّس مؤقتًا. ولنمثّل الآن المكدّس بزوج، يكون مكوّنه الأول القائمة نفسها كما كانت، ومكوّنه الثاني حجم المكدّس:

module ListStackCachedSize = struct
  exception Empty
  let empty = ([], 0)
  let is_empty = function ([], _) -> true | _ -> false
  let push x (stack, size) = (x :: stack, size + 1)
  let peek = function ([], _) -> raise Empty | (x :: _, _) -> x
  let pop = function
    | ([], _) -> raise Empty
    | (_ :: stack, size) -> (stack, size - 1)
end

module ListStackCachedSize :
  sig
    exception Empty
    val empty : 'a list * int
    val is_empty : 'a list * 'b -> bool
    val push : 'a -> 'a list * int -> 'a list * int
    val peek : 'a list * 'b -> 'a
    val pop : 'a list * int -> 'a list * int
  end

لدينا مشكلة كبيرة. فـ ListStackCachedSize لا تنفّذ نوع الوحدة LIST_STACK، لأن ذلك النوع يحدد 'a list في كل مواضعه لتمثيل المكدّس—لا 'a list * int.

module CheckListStackCachedSize : LIST_STACK = ListStackCachedSize

File "[12]", line 1, characters 47-66:
1 | module CheckListStackCachedSize : LIST_STACK = ListStackCachedSize
                                                   ^^^^^^^^^^^^^^^^^^^
Error: Signature mismatch:
       ...
       Values do not match:
         val empty : 'a list * int
       is not included in
         val empty : 'a list
       The type 'a list * int is not compatible with the type 'b list
       File "[10]", line 7, characters 2-21: Expected declaration
       File "[11]", line 3, characters 6-11: Actual declaration

علاوة على ذلك، يجب الآن تعديل أي شيفرة كتبناها سابقًا باستخدام ListStack للتعامل مع الزوج، وقد يعني ذلك مراجعة مطابقات الأنماط وأنواع الدوال وما إلى ذلك.

وكما تعلمت بلا شك في مقررات البرمجة السابقة، فالمشكلة التي نواجهها هنا نقص في التغليف. كان ينبغي أن نُبقي النوع الذي ينفّذ ListStack مخفيًا عن العملاء. ففي Java مثلًا ربما كتبنا:

class ListStack<T> {
  private List<T> stack;
  private int size;
  ...
}

وبهذه الطريقة لن يعرف عملاء ListStack شيئًا عن stack أو size. بل لن يتمكنوا من تسمية تلك الحقول أصلًا. بل سيستخدمون ListStack فحسب كنوع للمكدّس:

ListStack<Integer> s = new ListStack<>();
s.push(1);

فكيف إذن يمكننا في OCaml إبقاء نوع التمثيل (representation type) للمكدّس مخفيًا؟ ما تعلمناه عن العتامة والإغلاق حتى الآن لا يكفي. فالمشكلة أن النوع 'a list * int يظهر حرفيًا في توقيع ListStackCachedSize، مثلًا في push:

ListStackCachedSize.push

- : 'a -> 'a list * int -> 'a list * int = <fun>

كان يمكن لتعليق نوعي للوحدة أن يخفي إحدى القيم المعرّفة في ListStackCachedSize، مثل push نفسها، لكن ذلك لا يحل المشكلة: نحتاج إلى إخفاء النوع 'a list * int مع كشف العملية push. لذا يوفر OCaml ميزة تفعل ذلك بالضبط: الأنواع المجرّدة (abstract types). ولنرَ مثالًا على تلك الميزة.

نبدأ بتعديل LIST_STACK، باستبدال 'a list بنوع جديد 'a stack في كل موضع. ولن نعيد تعليقات المواصفة هنا لإبقاء المثال أقصر. وبينما نحن في ذلك، لنضف عملية size.

module type LIST_STACK = sig
  type 'a stack
  exception Empty
  val empty : 'a stack
  val is_empty : 'a stack -> bool
  val push : 'a -> 'a stack -> 'a stack
  val peek : 'a stack -> 'a
  val pop : 'a stack -> 'a stack
  val size : 'a stack -> int
end

module type LIST_STACK =
  sig
    type 'a stack
    exception Empty
    val empty : 'a stack
    val is_empty : 'a stack -> bool
    val push : 'a -> 'a stack -> 'a stack
    val peek : 'a stack -> 'a
    val pop : 'a stack -> 'a stack
    val size : 'a stack -> int
  end

لاحظ أن 'a stack غير معرّف فعليًا في ذلك التوقيع. فلم نقل شيئًا عن ماهيته. فقد يكون 'a list أو 'a list * int أو {stack : 'a list; size : int} أو أي شيء آخر. وهذا ما يجعله نوعًا مجرّدًا: أعلنّا اسمه لكننا لم نحدد تعريفه.

الآن يمكن لـ ListStackCachedSize أن تنفّذ ذلك النوع بإضافة سطر واحد فقط من الشيفرة: السطر الأول من البنية، الذي يعرّف 'a stack:

module ListStackCachedSize : LIST_STACK = struct
  type 'a stack = 'a list * int
  exception Empty
  let empty = ([], 0)
  let is_empty = function ([], _) -> true | _ -> false
  let push x (stack, size) = (x :: stack, size + 1)
  let peek = function ([], _) -> raise Empty | (x :: _, _) -> x
  let pop = function
    | ([], _) -> raise Empty
    | (_ :: stack, size) -> (stack, size - 1)
  let size = snd
end

module ListStackCachedSize : LIST_STACK

تأمل المخرجات بعناية: لا يظهر فيها 'a list في أي موضع. بل لا يظهر إلا LIST_STACK. وLIST_STACK لا تذكر إلا 'a stack. فلن يعرف أحد إذن أن قائمة تُستخدم داخليًا. (حسنًا، سيعرفون: فالاسم يوحي بذلك. لكن المقصود أنهم لا يستطيعون الاستفادة من ذلك، لأن النوع مجرّد.)

وبالمثل، يحقق تنفيذنا الأصلي ذو الزمن الخطي لـ size نوع الوحدة. علينا فقط أن نضيف سطرًا لتعريف 'a stack:

module ListStack : LIST_STACK = struct
  type 'a stack = 'a list
  exception Empty
  let empty = []
  let is_empty = function [] -> true | _ -> false
  let push x s = x :: s
  let peek = function [] -> raise Empty | x :: _ -> x
  let pop = function [] -> raise Empty | _ :: s -> s
  let size = List.length
end

module ListStack : LIST_STACK

لاحظ أن إغفال ذلك السطر المضاف سيؤدي إلى خطأ، تمامًا كما لو فشلنا في تعريف push أو أي من العمليات الأخرى من نوع الوحدة:

module ListStack : LIST_STACK = struct
  (* type 'a stack = 'a list *)
  exception Empty
  let empty = []
  let is_empty = function [] -> true | _ -> false
  let push x s = x :: s
  let peek = function [] -> raise Empty | x :: _ -> x
  let pop = function [] -> raise Empty | _ :: s -> s
  let size = List.length
end

File "[17]", lines 1-10, characters 32-3:
 1 | ................................struct
 2 |   (* type 'a stack = 'a list *)
 3 |   exception Empty
 4 |   let empty = []
 5 |   let is_empty = function [] -> true | _ -> false
 6 |   let push x s = x :: s
 7 |   let peek = function [] -> raise Empty | x :: _ -> x
 8 |   let pop = function [] -> raise Empty | _ :: s -> s
 9 |   let size = List.length
10 | end
Error: Signature mismatch:
       ...
       The type `stack' is required but not provided
       File "[14]", line 2, characters 2-15: Expected declaration

وهذا تنفيذ ثالث مخصص لـ LIST_STACK. وهو معقّد عن قصد، جزئيًا لبيان كيف يمكن للنوع المجرّد أن يخفي تفاصيل تنفيذ يُفضّل عدم كشفها للعملاء:

module CustomStack : LIST_STACK = struct
  type 'a entry = {top : 'a; rest : 'a stack; size : int}
  and 'a stack = S of 'a entry option
  exception Empty
  let empty = S None
  let is_empty = function S None -> true | _ -> false
  let size = function S None -> 0 | S (Some {size}) -> size
  let push x s = S (Some {top = x; rest = s; size = size s + 1})
  let peek = function S None -> raise Empty | S (Some {top}) -> top
  let pop = function S None -> raise Empty | S (Some {rest}) -> rest
end

module CustomStack : LIST_STACK

أهي فعلًا مكدّس «قوائم»؟ إنها تحقق نوع الوحدة LIST_STACK. لكن بالتأمل، لم يكن لذلك النوع فعلًا أي علاقة بالقوائم بعد أن جعلنا النوع 'a stack مجرّدًا. لا حاجة فعلًا لتسميته LIST_STACK. والأفضل أن نستخدم STACK فحسب، لأنه يمكن تنفيذه بقائمة أو بغير قائمة. وعندئذ يمكننا ببساطة اعتماد Stack اسمًا له، لأنه لا توجد وحدة باسم Stack كتبناها قد تلتبس به. وهذا يتجنب مظهر الأحرف الكبيرة الذي يجعل شيفرتنا تبدو صارخة في وجهنا.

module type Stack = sig
  type 'a stack
  exception Empty
  val empty : 'a stack
  val is_empty : 'a stack -> bool
  val push : 'a -> 'a stack -> 'a stack
  val peek : 'a stack -> 'a
  val pop : 'a stack -> 'a stack
  val size : 'a stack -> int
end
module ListStack : Stack = struct
  type 'a stack = 'a list
  exception Empty
  let empty = []
  let is_empty = function [] -> true | _ -> false
  let push x s = x :: s
  let peek = function [] -> raise Empty | x :: _ -> x
  let pop = function [] -> raise Empty | _ :: s -> s
  let size = List.length
end

module type Stack =
  sig
    type 'a stack
    exception Empty
    val empty : 'a stack
    val is_empty : 'a stack -> bool
    val push : 'a -> 'a stack -> 'a stack
    val peek : 'a stack -> 'a
    val pop : 'a stack -> 'a stack
    val size : 'a stack -> int
  end

module ListStack : Stack

ثمة تحسين تسمية آخر يمكننا إجراؤه. لاحظ نوع ListStack.empty (ولا تقلق بشأن جزء abstr الآن؛ سنعود إليه):

ListStack.empty

- : 'a ListStack.stack = <abstr>

ذلك النوع، 'a ListStack.stack، وعْر نوعًا ما، لأنه ينقل كلمة «stack» مرتين: مرة في اسم الوحدة، ومرة في اسم نوع التمثيل داخل تلك الوحدة. وفي مواضع كهذه، يستخدم مبرمجو OCaml اصطلاحيًا اسمًا قياسيًا هو t بدلًا من اسم نوع تمثيل أطول:

module type Stack = sig
  type 'a t
  exception Empty
  val empty : 'a t
  val is_empty : 'a t -> bool
  val push : 'a -> 'a t -> 'a t
  val peek : 'a t -> 'a
  val pop : 'a t -> 'a t
  val size : 'a t -> int
end
module ListStack : Stack = struct
  type 'a t = 'a list
  exception Empty
  let empty = []
  let is_empty = function [] -> true | _ -> false
  let push x s = x :: s
  let peek = function [] -> raise Empty | x :: _ -> x
  let pop = function [] -> raise Empty | _ :: s -> s
  let size = List.length
end
module CustomStack : Stack = struct
  type 'a entry = {top : 'a; rest : 'a t; size : int}
  and 'a t = S of 'a entry option
  exception Empty
  let empty = S None
  let is_empty = function S None -> true | _ -> false
  let size = function S None -> 0 | S (Some {size}) -> size
  let push x s = S (Some {top = x; rest = s; size = size s + 1})
  let peek = function S None -> raise Empty | S (Some {top}) -> top
  let pop = function S None -> raise Empty | S (Some {rest}) -> rest
end

module type Stack =
  sig
    type 'a t
    exception Empty
    val empty : 'a t
    val is_empty : 'a t -> bool
    val push : 'a -> 'a t -> 'a t
    val peek : 'a t -> 'a
    val pop : 'a t -> 'a t
    val size : 'a t -> int
  end

module ListStack : Stack

module CustomStack : Stack

الآن صار نوع المكدّسات أبسط:

ListStack.empty;;
CustomStack.empty;;

- : 'a ListStack.t = <abstr>

- : 'a CustomStack.t = <abstr>

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

في الحديث غير الرسمي، ننطق تلك الأنواع عادةً دون جزء «dot t». فقد نقول مثلًا «alpha ListStack»، متجاهلين t ببساطة—وإن كان وجودها مطلوبًا تقنيًا لتكون شيفرة OCaml قانونية.

وأخيرًا، الأنواع المجرّدة ليست في الحقيقة إلا حالة خاصة من العتامة. بل يمكنك فعلًا كشف تعريف نوع في توقيع إن أردت:

module type T = sig
  type t = int
  val x : t
end
module M : T = struct
  type t = int
  let x = 42
end
let a : int = M.x

module type T = sig type t = int val x : t end

module M : T

val a : int = 42

لاحظ كيف تمكّنّا من استخدام M.x بقيمة من النوع int. ويعمل ذلك لأن مساواة النوعين t وint كُشفت في نوع الوحدة. لكن لو أبقينا t مجرّدًا، لفشل الاستخدام نفسه:

module type T = sig
  type t (* = int *)
  val x : t
end
module M : T = struct
  type t = int
  let x = 42
end
let a : int = M.x

module type T = sig type t val x : t end

module M : T

File "[24]", line 11, characters 14-17:
11 | let a : int = M.x
                   ^^^
Error: This expression has type M.t but an expression was expected of type
         int

لا يُسمح لنا باستخدام M.x بالنوع int خارج M، لأن نوعه M.t مجرّد. هذا هو التغليف أثناء عمله، إذ يُبقي تفصيل التنفيذ ذلك مخفيًا.

5.4.3. الطباعة الجميلة

رأينا في بعض المخرجات أعلاه أمرًا مثيرًا للفضول: تطبع الواجهة التفاعلية `` بدلًا من المحتويات الفعلية لقيمة نوعها مجرّد:

ListStack.empty;;
ListStack.(empty |> push 1 |> push 2);;

- : 'a ListStack.t = <abstr>

- : int ListStack.t = <abstr>

تذكّر أن الواجهة التفاعلية تستخدم اصطلاح الأقواس الزاوية هذا للدلالة على قيمة غير قابلة للطباعة. وقد صادفنا ذلك سابقًا مع الدوال و``:

fun x -> x

- : 'a -> 'a = <fun>

من ناحية، من المعقول أن تسلك الواجهة التفاعلية هذا السلوك. فبمجرد أن يصير النوع مجرّدًا، لا يُقصد كشف تنفيذه للعملاء. لذا فطباعة القائمة [] أو [2; 1] فعلًا ردًّا على المدخلات أعلاه ستكشف أكثر مما هو مقصود.

ومن ناحية أخرى، من المعقول أيضًا أن يوفر المنفّذون للعملاء طريقة ودية لعرض قيمة من نوع مجرّد. فمبرمجو Java، على سبيل المثال، كثيرًا ما يكتبون دوال toString() كي تتمكن الكائنات من الطباعة كمخرجات في الطرفية أو في JShell. ولدعم ذلك، تحتوي الواجهة التفاعلية لـ OCaml على توجيه #install_printer، يسجّل دالة لطباعة القيم. وإليك كيف يعمل.

• تكتب دالة طباعة جميلة (pretty printing) نوعها Format.formatter -> t -> unit، لأي نوع t تريد. ولنفترض على سبيل المثال أنك تسمي تلك الدالة pp.
• تستدعي #install_printer pp في الواجهة التفاعلية.
• من الآن فصاعدًا، كلما أرادت الواجهة التفاعلية طباعة قيمة من النوع t، استخدمت دالتك pp لفعل ذلك.

يبدو منطقيًا أن تحتاج دالة الطباعة الجميلة إلى استقبال قيمة من النوع t (لأن ذلك ما يلزم طباعته) وأن تعيد unit (كما تفعل دوال الطباعة الأخرى). لكن لماذا تستقبل وسيطة Format.formatter؟ السبب ميزة عالية القدرة يحاول OCaml توفيرها هنا: كسر الأسطر التلقائي والإزاحة في منتصف مخرجات ضخمة جدًا.

تأمل المخرجات من هذا التعبير، الذي ينشئ قوائم متداخلة:

List.init 15 (fun n -> List.init n (Fun.const n))

- : int list list =
[[]; [1]; [2; 2]; [3; 3; 3]; [4; 4; 4; 4]; [5; 5; 5; 5; 5];
 [6; 6; 6; 6; 6; 6]; [7; 7; 7; 7; 7; 7; 7]; [8; 8; 8; 8; 8; 8; 8; 8];
 [9; 9; 9; 9; 9; 9; 9; 9; 9]; [10; 10; 10; 10; 10; 10; 10; 10; 10; 10];
 [11; 11; 11; 11; 11; 11; 11; 11; 11; 11; 11];
 [12; 12; 12; 12; 12; 12; 12; 12; 12; 12; 12; 12];
 [13; 13; 13; 13; 13; 13; 13; 13; 13; 13; 13; 13; 13];
 [14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14; 14]]

تحتوي كل قائمة داخلية على n نسخة من العدد n. لاحظ كيف أن الإزاحة وكسور الأسطر متطورة نوعًا ما. فكل القوائم الداخلية مُزاحة مسافة واحدة عن الهامش الأيسر. وأُدرجت كسور أسطر لتجنب تقسيم القوائم الداخلية على أسطر متعددة.

وحدة Format هي التي توفر هذه الوظيفة، وFormat.formatter نوع مجرّد فيها. ويمكنك التفكير في المنسّق (formatter) كمكان تُرسل إليه المخرجات، مثل ملف، فتُنسَّق تلقائيًا أثناء ذلك. والاستخدام المعتاد للمنسّق هو كوسيطة لدالة مثل Format.fprintf، التي تستخدم مواصفات تنسيق مثل Printf.

فمثلًا، افترض أنك أردت تغيير كيفية طباعة الواجهة التفاعلية للسلاسل النصية وإضافة ” kupo” إلى نهاية كل سلسلة. إليك الشيفرة التي تفعل ذلك:

let kupo_pp fmt s = Format.fprintf fmt "%s kupo" s;;
#install_printer kupo_pp;;

val kupo_pp : Format.formatter -> string -> unit = <fun>

الآن يمكنك أن ترى أن الواجهة التفاعلية تضيف ” kupo” إلى كل سلسلة أثناء طباعتها، مع أنها ليست فعلًا جزءًا من السلسلة الأصلية:

let h = "Hello"
let s = String.length h

val h : string = Hello kupo

val s : int = 5

ولئلا نربك أنفسنا بشأن السلاسل النصية في بقية هذا القسم، لنلغِ تثبيت دالة الطباعة الجميلة تلك قبل المتابعة:

#remove_printer kupo_pp;;

وكمثال أكبر، لنضف الطباعة الجميلة إلى ListStack:

module type Stack = sig
  type 'a t
  exception Empty
  val empty : 'a t
  val is_empty : 'a t -> bool
  val push : 'a -> 'a t -> 'a t
  val peek : 'a t -> 'a
  val pop : 'a t -> 'a t
  val size : 'a t -> int
  val pp :
    (Format.formatter -> 'a -> unit) -> Format.formatter -> 'a t -> unit
end

module type Stack =
  sig
    type 'a t
    exception Empty
    val empty : 'a t
    val is_empty : 'a t -> bool
    val push : 'a -> 'a t -> 'a t
    val peek : 'a t -> 'a
    val pop : 'a t -> 'a t
    val size : 'a t -> int
    val pp :
      (Format.formatter -> 'a -> unit) -> Format.formatter -> 'a t -> unit
  end

أولًا، لاحظ أنه يجب علينا كشف pp كجزء من نوع الوحدة. وإلا لكانت مغلّفة، ومن ثم لما أمكننا تثبيتها. وثانيًا، لاحظ أن نوع pp يأخذ الآن وسيطة أولى إضافية من النوع Format.formatter -> 'a -> unit. وهي بذاتها دالة طباعة جميلة للنوع 'a الذي يُوسَّم t به. ونحتاج إلى تلك الوسيطة حتى نتمكن من طباعة قيم النوع 'a طباعةً جميلة.

module ListStack : Stack = struct
  type 'a t = 'a list
  exception Empty
  let empty = []
  let is_empty = function [] -> true | _ -> false
  let push x s = x :: s
  let peek = function [] -> raise Empty | x :: _ -> x
  let pop = function [] -> raise Empty | _ :: s -> s
  let size = List.length
  let pp pp_val fmt s =
    let open Format in
    let pp_break fmt () = fprintf fmt "@," in
    fprintf fmt "@[<v 0>top of stack";
    if s <> [] then fprintf fmt "@,";
    pp_print_list ~pp_sep:pp_break pp_val fmt s;
    fprintf fmt "@,bottom of stack@]"
end

module ListStack : Stack

في ListStack.pp نستخدم بعض الميزات المتقدمة لوحدة Format. فالدالة Format.pp_print_list تقوم بالعمل الشاق لطباعة كل عناصر المكدّس. أما بقية الشيفرة فتتولى الإزاحة وكسور الأسطر. وإليك النتيجة:

#install_printer ListStack.pp

ListStack.empty

- : 'a ListStack.t = top of stack
                     bottom of stack

ListStack.(empty |> push 1 |> push 2)

- : int ListStack.t = top of stack
                      2
                      1
                      bottom of stack

لمزيد من المعلومات، انظر دليل الواجهة التفاعلية (ابحث عن #install_printer)، ووحدة Format، وقضية OCaml على GitHub هذه. ويبدو أن الأخيرة هي الموضع الوحيد الذي يوثق استخدام الوسائط الإضافية، كما في pp_val أعلاه، لطباعة قيم الأنواع المتعددة الأشكال.

5.5. وحدات الترجمة

وحدة الترجمة (compilation unit) زوج من ملفات مصادر OCaml في الدليل نفسه. يشتركان في الاسم الأساسي نفسه، ولنسمّه x، لكن امتداديهما يختلفان: أحد الملفين x.ml والآخر x.mli. ويسمى الملف x.ml التنفيذ (implementation)، ويسمى x.mli الواجهة (interface).

فمثلًا، افترض أن foo.mli يحتوي بالضبط على ما يلي:

val x : int
val f : int -> int

ويحتوي foo.ml، في الدليل نفسه، بالضبط على ما يلي:

let x = 0
let y = 12
let f x = x + y

عندئذ سيكون لتصريف foo.ml الأثر نفسه الذي لتعريف الوحدة Foo كما يلي:

module Foo : sig
  val x : int
  val f : int -> int
end = struct
  let x = 0
  let y = 12
  let f x = x + y
end

وبشكل عام، عندما يصادف المصرّف وحدة ترجمة، يعاملها كما لو كانت تعرّف وحدة وتوقيعًا هكذا:

module Foo
  : sig (* insert contents of foo.mli here *) end
= struct
  (* insert contents of foo.ml here *)
end

ويُشتق اسم الوحدة (unit name) Foo من الاسم الأساسي foo بمجرد كتابة حرفه الأول كبيرًا. ولاحظ أنه لا يوجد نوع وحدة مسمّى يُعرَّف؛ فتوقيع Foo مجهول فعليًا.

وتستخدم المكتبة القياسية وحدات الترجمة لتنفيذ معظم الوحدات التي استخدمناها حتى الآن، مثل List وString. ويمكنك رؤية ذلك في شيفرة المكتبة القياسية.

5.5.1. تعليقات التوثيق

بعض تعليقات التوثيق مكانها ملف الواجهة، بينما مكان تعليقات أخرى ملف التنفيذ:

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

وينبغي ألا يُكرر التوثيق بين الملفين. وبوجه خاص، لا ينبغي تكرار تعليقات المواصفة الموجَّهة للعملاء في ملف الواجهة داخل ملف التنفيذ. وأحد الأسباب أن التكرار يؤدي حتمًا إلى أخطاء. وسبب آخر أن OCamldoc قادر على إدراج التعليقات من ملف الواجهة تلقائيًا في HTML المولَّد من ملف التنفيذ.

ويمكن وضع تعليقات OCamldoc إما قبل عنصر من عناصر الواجهة وإما بعده. فمثلًا، كلا الموضعين التاليين ممكن:

(** The mathematical constant 3.14... *)
val pi : float

val pi : float
(** The mathematical constant 3.14... *)

نصيحة

يبدو أن مطوري المكتبة القياسية يفضّلون وضع التعليق بعده، ويبدو أن OCamlFormat يعمل على نحو أفضل مع ذلك أيضًا.

5.5.2. مثال بالمكدّسات

ضع هذه الشيفرة في mystack.mli، ولاحظ أنه لا يوجد sig..end حولها ولا أي module type:

type 'a t
exception Empty
val empty : 'a t
val is_empty : 'a t -> bool
val push : 'a -> 'a t -> 'a t
val peek : 'a t -> 'a
val pop : 'a t -> 'a t

نستخدم اسم «mystack» لأن المكتبة القياسية تحتوي بالفعل على وحدة Stack. وإعادة استخدام ذلك الاسم قد تؤدي إلى رسائل خطأ يصعب فهمها نوعًا ما.

وضع هذه الشيفرة أيضًا في mystack.ml، ولاحظ أنه لا يوجد struct..end حولها ولا أي module:

type 'a t = 'a list
exception Empty
let empty = []
let is_empty = function [] -> true | _ -> false
let push = List.cons
let peek = function [] -> raise Empty | x :: _ -> x
let pop = function [] -> raise Empty | _ :: s -> s

أنشئ ملف dune:

(library
 (name mystack))

صرّف الشيفرة وشغّل utop:

$ dune utop

وحدة ترجمتك جاهزة للاستخدام:

# Mystack.empty;;
- : 'a Mystack.t = <abstr>

5.5.3. وحدات الترجمة غير المكتملة

ماذا لو كان ملف الواجهة أو ملف التنفيذ مفقودًا لوحدة ترجمة؟

ملفات الواجهة المفقودة. هذا في الحقيقة هو بالضبط أسلوب عملنا المعتاد حتى هذه النقطة. فمثلًا، ربما أنجزت واجبًا في ملف باسم lab1.ml لكنك لم تحتج قط للقلق بشأن lab1.mli. ولا يوجد شرط بأن يكون لكل ملف .ml ملف .mli مقابل، أو بعبارة أخرى، بأن تكون كل وحدة ترجمة مكتملة.

وإذا كان ملف .mli مفقودًا، فستُنشأ مع ذلك وحدة، كما رأينا حين تعلمنا #load والوحدات. غير أنه لا يُفرض عليها توقيع تلقائيًا. فمثلًا، ستؤدي الحالة مع lab1 أعلاه إلى إنشاء الوحدة التالية أثناء التصريف:

module Lab1 = struct
  (* insert contents of lab1.ml here *)
end

ملفات التنفيذ المفقودة. هذه الحالة أندر بكثير، وليست مما يُرجح أن تصادفه في التطوير اليومي. لكن اعلم أن ثمة حالة إساءة استخدام يقع فيها مبرمجو Java أو C++ أحيانًا عن غير قصد. افترض أن لديك واجهة سيكون لها عدة تنفيذات. وبالعودة إلى المكدّسات في وقت سابق من هذا الفصل، ربما لديك نوع وحدة Stack ووحدتان تنفذانه، ListStack وCustomStack:

module type Stack = sig
  type 'a t
  val empty : 'a t
  val push : 'a -> 'a t -> 'a t
  (* etc. *)
end
module ListStack : Stack = struct
  type 'a t = 'a list
  let empty = []
  let push = List.cons
  (* etc. *)
end
module CustomStack : Stack = struct
  (* omitted *)
end

ومن المغري تقسيم تلك الشيفرة إلى ملفات كما يلي:

(********************************)
(* stack.mli *)
type 'a t
val empty : 'a t
val push : 'a -> 'a t -> 'a t
(* etc. *)
(********************************)
(* listStack.ml *)
type 'a t = 'a list
let empty = []
let push = List.cons
(* etc. *)
(********************************)
(* customStack.ml *)
(* omitted *)

وسبب ذلك الإغراء أنك في Java قد تضع واجهة Stack في ملف Stack.java، وصنف ListStack في ملف ListStack.java، وهكذا. وفي C++ قد يُفعل شيء مشابه بملفات .hpp و.cpp.

لكن تنظيم ملفات OCaml المعروض أعلاه لن يعمل ببساطة. فلكي تكون listStack.ml وحدة ترجمة، يجب أن تكون واجهتها في listStack.mli. ولا يمكن أن تكون في ملف بأي اسم آخر. لذا لا سبيل مع ذلك التقسيم للشيفرة إلى اشتراط أن ListStack : Stack.

وبدلًا من ذلك، يمكن تقسيم الشيفرة هكذا:

(********************************)
(* stack.ml *)
module type S = sig
  type 'a t
  val empty : 'a t
  val push : 'a -> 'a t -> 'a t
  (* etc. *)
end
(********************************)
(* listStack.ml *)
module M : Stack.S = struct
  type 'a t = 'a list
  let empty = []
  let push = List.cons
  (* etc. *)
end
(********************************)
(* customStack.ml *)
module M : Stack.S = struct
  (* omitted *)
end

ولاحظ ما يلي بشأن ذلك التقسيم:

• يوضع نوع الوحدة في ملف .ml لا في ملف .mli، لأننا لا نحاول إنشاء وحدة ترجمة.
• نعطي الوحدات وأنواع الوحدات في الملفات أسماء قصيرة، لأنها ستكون بالفعل داخل وحدة بحسب اسم الملف. فسيكون مسهبًا نوعًا ما، مثلًا، أن نسمي S باسم أطول مثل Stack. فلو فعلنا، لوجب علينا كتابة Stack.Stack في تعليقات أنواع الوحدات بدلًا من Stack.S.

وثمة احتمال آخر لتقسيم الشيفرة، وهو وضع كل الشيفرة في ملف واحد stack.ml. وهذا يعمل إن كانت كل الشيفرة جزءًا من المكتبة نفسها، لكنه لا يعمل إن كان ListStack وCustomStack مثلًا مطوَّرين من مؤسستين منفصلتين. وإذا كانت الشيفرة في ملف واحد، أمكننا حينئذ تحويله إلى وحدة ترجمة:

(********************************)
(* stack.mli *)
module type S = sig
  type 'a t
  val empty : 'a t
  val push : 'a -> 'a t -> 'a t
  (* etc. *)
end
module ListStack : S
module CustomStack : S
(********************************)
(* stack.ml *)
module type S = sig
  type 'a t
  val empty : 'a t
  val push : 'a -> 'a t -> 'a t
  (* etc. *)
end
module ListStack : S = struct
  type 'a t = 'a list
  let empty = []
  let push = List.cons
  (* etc. *)
end
module CustomStack : S = struct
  (* omitted *)
end

للأسف، يعني ذلك أننا كررنا Stack.S في ملفي الواجهة والتنفيذ معًا. ولا سبيل إلى «استيراد» نوع وحدة معلَن بالفعل من ملف .mli تلقائيًا إلى ملف .ml المقابل.

5.6. بنى المعطيات الوظيفية

بنية المعطيات الوظيفية (functional data structure) بنية لا تستخدم القابلية للتغيير. ويمكن بناء بنى معطيات وظيفية في اللغات الوظيفية كما في اللغات الأمرية. فمثلًا، يمكنك بناء مقابل في Java لنوع list في OCaml بإنشاء صنف Node حقوله غير قابلة للتغيير بحكم استخدام الكلمة المفتاحية final.

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

5.6.1. القوائم

بنية list المترابطة أحادية الاتجاه المدمجة في OCaml وظيفية. ونحن نعلم ذلك، لأننا رأينا كيف ننفّذها بالأنواع الجبرية. وهي أيضًا دائمة، ويمكننا بيان ذلك:

let lst = [1; 2];;
let lst' = List.tl lst;;
lst;;

val lst : int list = [1; 2]

val lst' : int list = [2]

- : int list = [1; 2]

أخذ ذيل lst لا يغيّر القائمة. فكل من lst وlst' موجودتان معًا دون أن تؤثر إحداهما في الأخرى.

5.6.2. المكدّسات

نفّذنا المكدّسات في وقت سابق من هذا الفصل. وإليك صيغة موجزة لأحد تلك التنفيذات، نضيف فيها عملية to_list لتسهيل عرض محتويات المكدّس في الأمثلة:

module type Stack = sig
  type 'a t
  exception Empty
  val empty : 'a t
  val is_empty : 'a t -> bool
  val push : 'a -> 'a t -> 'a t
  val peek : 'a t -> 'a
  val pop : 'a t -> 'a t
  val size : 'a t -> int
  val to_list : 'a t -> 'a list
end
module ListStack : Stack = struct
  type 'a t = 'a list
  exception Empty
  let empty = []
  let is_empty = function [] -> true | _ -> false
  let push = List.cons
  let peek = function [] -> raise Empty | x :: _ -> x
  let pop = function [] -> raise Empty | _ :: s -> s
  let size = List.length
  let to_list = Fun.id
end

module type Stack =
  sig
    type 'a t
    exception Empty
    val empty : 'a t
    val is_empty : 'a t -> bool
    val push : 'a -> 'a t -> 'a t
    val peek : 'a t -> 'a
    val pop : 'a t -> 'a t
    val size : 'a t -> int
    val to_list : 'a t -> 'a list
  end

module ListStack : Stack

ذلك التنفيذ وظيفي، كما يتبين أعلاه، ودائم أيضًا:

open ListStack;;
let s = empty |> push 1 |> push 2;;
let s' = pop s;;
to_list s;;
to_list s';;

val s : int ListStack.t = <abstr>

val s' : int ListStack.t = <abstr>

- : int list = [2; 1]

- : int list = [1]

لا تتغير القيمة s بعملية pop التي تنشئ s'. فنسختا المكدّس موجودتان معًا.

ويلمّح نوع الوحدة Stack تلميحًا قويًا إلى أن بنية المعطيات دائمة من خلال الأنواع التي يوفرها لكل من push وpop:

val push : 'a -> 'a t -> 'a t
val pop : 'a t -> 'a t

فكلتاهما تأخذ مكدّسًا كوسيطة وتعيد مكدّسًا جديدًا كنتيجة. وبنية المعطيات الزائلة لا تكلف نفسها عادةً إعادة مكدّس. ففي Java مثلًا، قد يكون لتلك الطرق نوع إرجاع void؛ ومقابله في OCaml إرجاع unit.

5.6.3. الخيارات مقابل الاستثناءات

كل تنفيذاتنا للمكدّسات حتى الآن رفعت استثناءً كلما طُبِّقت peek أو pop على المكدّس الفارغ. ومن الاحتمالات الأخرى استخدام option كنوع إرجاع. فإذا كان المكدّس المدخل فارغًا، أعادت peek وpop القيمة None؛ وإلا أعادتا Some.

module type Stack = sig
  type 'a t
  val empty : 'a t
  val is_empty : 'a t -> bool
  val push : 'a -> 'a t -> 'a t
  val peek : 'a t -> 'a option
  val pop : 'a t -> 'a t option
  val size : 'a t -> int
  val to_list : 'a t -> 'a list
end
module ListStack : Stack = struct
  type 'a t = 'a list
  exception Empty
  let empty = []
  let is_empty = function [] -> true | _ -> false
  let push = List.cons
  let peek = function [] -> None | x :: _ -> Some x
  let pop = function [] -> None | _ :: s -> Some s
  let size = List.length
  let to_list = Fun.id
end

module type Stack =
  sig
    type 'a t
    val empty : 'a t
    val is_empty : 'a t -> bool
    val push : 'a -> 'a t -> 'a t
    val peek : 'a t -> 'a option
    val pop : 'a t -> 'a t option
    val size : 'a t -> int
    val to_list : 'a t -> 'a list
  end

module ListStack : Stack

لكن ذلك يجعل تسلسل العمليات أصعب:

ListStack.(empty |> push 1 |> pop |> peek)

File "[5]", line 1, characters 11-33:
1 | ListStack.(empty |> push 1 |> pop |> peek)
               ^^^^^^^^^^^^^^^^^^^^^^
Error: This expression has type int ListStack.t option
       but an expression was expected of type 'a ListStack.t

تنهار الأنواع عند تسلسل العمليات مباشرة بعد pop، لأنها تعيد الآن 'a t option، بينما تتوقع peek مدخلًا هو مجرد 'a t.

من الممكن تعريف بعض المؤثرات الإضافية للمساعدة في استعادة القدرة على التسلسل. بل إن هذه الدوال معرَّفة بالفعل في وحدة Option في المكتبة القياسية، وإن لم تكن كمؤثرات بينية:

(* Option.map aka fmap *)
let ( >>| ) opt f =
  match opt with
  | None -> None
  | Some x -> Some (f x)
(* Option.bind *)
let ( >>= ) opt f =
  match opt with
  | None -> None
  | Some x -> f x

val ( >>| ) : 'a option -> ('a -> 'b) -> 'b option = <fun>

val ( >>= ) : 'a option -> ('a -> 'b option) -> 'b option = <fun>

ويمكننا استخدام تلك المؤثرات حسب الحاجة في التسلسل:

ListStack.(empty |> push 1 |> pop >>| push 2 >>= pop >>| push 3 >>| to_list)

- : int list option = Some [3]

لكن ليس من اللطيف تحديد أي المؤثرات الثلاثة تستخدم وأين.

لذا ثمة مقايضة في تصميم الواجهة:

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

ثمة إذن مقايضة بين كتابة شيفرة أكثر مبكرًا (بالخيارات) أو تنقيح أخطاء أكثر لاحقًا (بالاستثناءات). وقد بدأت المكتبة القياسية لـ OCaml حديثًا توفر نسختي الواجهة في بنية معطيات، بحيث يختار العميل كيف يريد استخدامها. فمثلًا، يمكننا توفير كل من peek وpeek_opt، وكذلك الأمر بالنسبة إلى pop، لعملاء وحدة المكدّس لدينا:

module type Stack = sig
  type 'a t
  exception Empty
  val empty : 'a t
  val is_empty : 'a t -> bool
  val push : 'a -> 'a t -> 'a t
  val peek : 'a t -> 'a
  val peek_opt : 'a t -> 'a option
  val pop : 'a t -> 'a t
  val pop_opt : 'a t -> 'a t option
  val size : 'a t -> int
  val to_list : 'a t -> 'a list
end
module ListStack : Stack = struct
  type 'a t = 'a list
  exception Empty
  let empty = []
  let is_empty = function [] -> true | _ -> false
  let push = List.cons
  let peek = function [] -> raise Empty | x :: _ -> x
  let peek_opt = function [] -> None | x :: _ -> Some x
  let pop = function [] -> raise Empty | _ :: s -> s
  let pop_opt = function [] -> None | _ :: s -> Some s
  let size = List.length
  let to_list = Fun.id
end

module type Stack =
  sig
    type 'a t
    exception Empty
    val empty : 'a t
    val is_empty : 'a t -> bool
    val push : 'a -> 'a t -> 'a t
    val peek : 'a t -> 'a
    val peek_opt : 'a t -> 'a option
    val pop : 'a t -> 'a t
    val pop_opt : 'a t -> 'a t option
    val size : 'a t -> int
    val to_list : 'a t -> 'a list
  end

module ListStack : Stack

من المحاسن في هذا التنفيذ أنه فعّال. فكل العمليات عدا size ثابتة الزمن. وقد رأينا سابقًا في الفصل أنه يمكن جعل size ثابتة الزمن أيضًا، مقابل بعض المساحة الإضافية — وإن كانت مضاعفًا ثابتًا فحسب — بتخزين حجم المكدّس عند كل عقدة في القائمة.

5.6.4. الطوابير

الطوابير والمكدّسات واجهتان متشابهتان إلى حد كبير. وسنبقى مع الاستثناءات بدلًا من الخيارات في الوقت الحالي.

module type Queue = sig
  (** An ['a t] is a queue whose elements have type ['a]. *)
  type 'a t
  (** Raised if [front] or [dequeue] is applied to the empty queue. *)
  exception Empty
  (** [empty] is the empty queue. *)
  val empty : 'a t
  (** [is_empty q] is whether [q] is empty. *)
  val is_empty : 'a t -> bool
  (** [enqueue x q] is the queue [q] with [x] added to the end. *)
  val enqueue : 'a -> 'a t -> 'a t
  (** [front q] is the element at the front of the queue. Raises [Empty]
      if [q] is empty. *)
  val front : 'a t -> 'a
  (** [dequeue q] is the queue containing all the elements of [q] except the
      front of [q]. Raises [Empty] if [q] is empty. *)
  val dequeue : 'a t -> 'a t
  (** [size q] is the number of elements in [q]. *)
  val size : 'a t -> int
  (** [to_list q] is a list containing the elements of [q] in order from
      front to back. *)
  val to_list : 'a t -> 'a list
end

module type Queue =
  sig
    type 'a t
    exception Empty
    val empty : 'a t
    val is_empty : 'a t -> bool
    val enqueue : 'a -> 'a t -> 'a t
    val front : 'a t -> 'a
    val dequeue : 'a t -> 'a t
    val size : 'a t -> int
    val to_list : 'a t -> 'a list
  end

مهم

كما في peek وpop، لاحظ كيف تقتسم front وdequeue مسؤولية الحصول على العنصر الأول مقابل الحصول على كل بقية العناصر.

من السهل تنفيذ الطوابير بالقوائم، كما كان الحال في تنفيذ المكدّسات:

module ListQueue : Queue = struct
  (** The list [x1; x2; ...; xn] represents the queue with [x1] at its front,
      followed by [x2], ..., followed by [xn]. *)
  type 'a t = 'a list
  exception Empty
  let empty = []
  let is_empty = function [] -> true | _ -> false
  let enqueue x q = q @ [x]
  let front = function [] -> raise Empty | x :: _ -> x
  let dequeue = function [] -> raise Empty | _ :: q -> q
  let size = List.length
  let to_list = Fun.id
end

module ListQueue : Queue

لكن رغم سهولة ذلك، هذا التنفيذ ليس بفعالية مكدّساتنا القائمة على القوائم. فإخراج العناصر عملية ثابتة الزمن بهذا التمثيل، أما إدخالها فعملية خطية الزمن. والسبب أن dequeue تُجري مطابقة نمط واحدة، بينما على enqueue أن تجتاز القائمة كلها لتضيف العنصر الجديد في النهاية.

ثمة طريقة بارعة جدًا لتحسين الفعالية. يمكننا استخدام قائمتين لتمثيل طابور واحد. وقد اخترع هذا التمثيل Robert Melville ضمن أطروحته للدكتوراه في جامعة كورنيل (Asymptotic Complexity of Iterative Computations، يناير 1981)، التي أشرف عليها الأستاذ David Gries. ويسميها Chris Okasaki (Purely Functional Data Structures، Cambridge University Press، 1988) الطوابير المجمّعة (batched queues). وسترى أحيانًا الإشارة إلى هذا التنفيذ نفسه بأنه «تنفيذ طابور بمكدّسين». والسبب أن المكدّسات والقوائم متشابهة إلى هذا الحد (كما رأينا) بحيث يمكن إعادة كتابة pop كـ List.tl، وما إلى ذلك.

للفكرة الجوهرية جزء A وجزء B. أما الجزء A فهو: نستخدم القائمتين لتقسيم الطابور إلى قطعتين، هما الوارد (inbox) والصادر (outbox). وعندما تُدخل عناصر جديدة، نضعها في الوارد. وفي النهاية (وسنرى قريبًا كيف) تُنقل العناصر من الوارد إلى الصادر. وعندما يُطلب إخراج عنصر، يُزال ذلك العنصر من الصادر؛ أو عندما يُطلب العنصر الأمامي، نبحث عنه في الصادر. فمثلًا، لو كان الوارد يحتوي حاليًا على [3; 4; 5] والصادر على [1; 2]، لكان العنصر الأمامي 1، وهو رأس الصادر. وسيؤدي إخراج عنصر إلى إزالة ذلك العنصر وترك الصادر ببساطة [2]. وبالمثل، سيؤدي إدخال 6 إلى أن يصير الوارد [3; 4; 5; 6].

فعالية front وdequeue جيدة جدًا حتى الآن. فعلينا فقط أخذ رأس الصادر أو ذيله، على الترتيب، بشرط ألا يكون فارغًا. وتلك عمليتان ثابتتا الزمن. لكن فعالية enqueue لا تزال سيئة. فهي خطية الزمن، لأن علينا إضافة العنصر الجديد إلى نهاية القائمة. ومن المؤسف أن نضطر إلى استخدام مؤثر الإضافة، فهو خطي الزمن بحكم طبيعته. وسيكون أفضل بكثير لو تمكّنّا من استخدام cons، وهو ثابت الزمن.

وإليك الجزء B من الفكرة الجوهرية: لنُبقِ الوارد بترتيب معكوس. فمثلًا، لو أدخلنا 3 ثم 4 ثم 5، لكان الوارد في الحقيقة [5; 4; 3] لا [3; 4; 5]. وعندئذ لو أُدخل 6 تاليًا، أمكننا وضعه في مقدمة الوارد بـ cons، فيصير [6; 5; 4; 3]. فالطابور الذي يمثله الوارد i والصادر o هو إذن o @ List.rev i. وبذلك يمكن أن تكون enqueue الآن عملية ثابتة الزمن دائمًا.

لكن ماذا عن dequeue (وfront)؟ إنهما ثابتتان الزمن أيضًا، ما دام الصادر غير فارغ. أما إذا كان فارغًا، فلدينا مشكلة. نحتاج عندئذ إلى نقل كل ما في الوارد إلى الصادر. فمثلًا، إذا كان الصادر فارغًا وكان الوارد [6; 5; 4; 3]، فعلينا تبديلهما، فيصير الصادر [3; 4; 5; 6] والوارد فارغًا. وذلك سهل فعلًا: علينا فقط عكس القائمة.

للأسف، أعدنا للتو إدخال عملية خطية الزمن. لكن مع فرق حاسم واحد: ليس علينا إجراء ذلك العكس الخطي في كل dequeue، بينما مع ListQueue أعلاه كان علينا إجراء الإضافة الخطية في كل enqueue. بل نحتاج إلى العكس فقط في تلك المناسبات النادرة التي يفرغ فيها الصادر.

لذا حتى لو كانت dequeue (وfront) خطيتي الزمن في أسوأ الحالات، فلن تكونا كذلك في معظم الوقت. بل سنبيّن لاحقًا في هذا الكتاب عند دراستنا التحليل المستهلك (amortized analysis) أنهما يمكن فهمهما على المدى الطويل كعمليتين ثابتتي الزمن. وفي الوقت الحالي، إليك حدسًا يدعم ذلك الادعاء: كل عنصر فردي يدخل الوارد مرة (بـ cons)، وينتقل إلى الصادر مرة (بمطابقة نمط ثم cons)، ويخرج من الصادر مرة (بمطابقة نمط). وكل ذلك ثابت الزمن. لذا لا يمر كل عنصر إلا بعمليات ثابتة الزمن من منظوره الخاص.

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

module BatchedQueue : Queue = struct
  (** [{o; i}] represents the queue [o @ List.rev i]. For example,
      [{o = [1; 2]; i = [5; 4; 3]}] represents the queue [1, 2, 3, 4, 5],
      where [1] is the front element. To avoid ambiguity about emptiness,
      whenever only one of the lists is empty, it must be [i]. For example,
      [{o = [1]; i = []}] is a legal representation, but [{o = []; i = [1]}]
      is not. This implies that if [o] is empty, [i] must also be empty. *)
  type 'a t = {o : 'a list; i : 'a list}
  exception Empty
  let empty = {o = []; i = []}
  let is_empty = function
    | {o = []} -> true
    | _ -> false
  let enqueue x = function
    | {o = []} -> {o = [x]; i = []}
    | {o; i} -> {o; i = x :: i}
  let front = function
    | {o = []} -> raise Empty
    | {o = h :: _} -> h
  let dequeue = function
    | {o = []} -> raise Empty
    | {o = [_]; i} -> {o = List.rev i; i = []}
    | {o = _ :: t; i} -> {o = t; i}
  let size {o; i} = List.(length o + length i)
  let to_list {o; i} = o @ List.rev i
end

module BatchedQueue : Queue

تأتي فعالية الطوابير المجمّعة بثمن في قابلية القراءة. فإذا قارنّا ListQueue وBatchedQueue، فمن المأمول أن يكون واضحًا أن ListQueue تنفيذ بسيط وصحيح لبنية معطيات الطابور. أما أنه من الواضح أن BatchedQueue تنفيذ صحيح، فذلك أقل بكثير. فانظر فقط إلى كم الفقرات التي لزمت لشرحه أعلاه!

5.6.5. الخرائط

تذكّر أن الخريطة (map)، وتُسمى أيضًا القاموس (dictionary)، تربط المفاتيح بقيم. وإليك نوع وحدة للخرائط. وثمة عمليات أخرى كثيرة قد تدعمها الخريطة، لكن هذه ستكفي في الوقت الحالي.

module type Map = sig
  (** [('k, 'v) t] is the type of maps that bind keys of type ['k] to
      values of type ['v]. *)
  type ('k, 'v) t
  (** [empty] does not bind any keys. *)
  val empty  : ('k, 'v) t
  (** [insert k v m] is the map that binds [k] to [v], and also contains
      all the bindings of [m].  If [k] was already bound in [m], that old
      binding is superseded by the binding to [v] in the returned map. *)
  val insert : 'k -> 'v -> ('k, 'v) t -> ('k, 'v) t
  (** [lookup k m] is the value bound to [k] in [m]. Raises: [Not_found] if [k]
      is not bound in [m]. *)
  val lookup : 'k -> ('k, 'v) t -> 'v
  (** [bindings m] is an association list containing the same bindings as [m].
      The keys in the list are guaranteed to be unique. *)
  val bindings : ('k, 'v) t -> ('k * 'v) list
end

module type Map =
  sig
    type ('k, 'v) t
    val empty : ('k, 'v) t
    val insert : 'k -> 'v -> ('k, 'v) t -> ('k, 'v) t
    val lookup : 'k -> ('k, 'v) t -> 'v
    val bindings : ('k, 'v) t -> ('k * 'v) list
  end

لاحظ كيف تُوسَّم Map.t بنوعين، 'k و'v، مكتوبين بين قوسين ومفصولين بفاصلة. ورغم أن ('k, 'v) قد يبدو كزوج من القيم، فهو ليس كذلك: إنه صياغة لكتابة متغيرات أنواع متعددة.

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

[("pi", 3.14); ("e", 2.718); ("phi", 1.618)]

وبطبيعة الحال يمكننا تنفيذ نوع الوحدة Map بقوائم الترابط:

module AssocListMap : Map = struct
  (** The list [(k1, v1); ...; (kn, vn)] binds key [ki] to value [vi].
      If a key appears more than once in the list, it is bound to the
      the left-most occurrence in the list. *)
  type ('k, 'v) t = ('k * 'v) list
  let empty = []
  let insert k v m = (k, v) :: m
  let lookup k m = List.assoc k m
  let keys m = List.(m |> map fst |> sort_uniq Stdlib.compare)
  let bindings m = m |> keys |> List.map (fun k -> (k, lookup k m))
end

module AssocListMap : Map

هذا التنفيذ للخرائط دائم. فمثلًا، إضافة ربط جديد إلى الخريطة m أدناه لا تغيّر m نفسها:

open AssocListMap
let m = empty |> insert "pi" 3.14 |> insert "e" 2.718
let m' = m |> insert "phi" 1.618
let b = bindings m
let b' = bindings m'

val m : (string, float) AssocListMap.t = <abstr>

val m' : (string, float) AssocListMap.t = <abstr>

val b : (string * float) list = [("e", 2.718); ("pi", 3.14)]

val b' : (string * float) list = [("e", 2.718); ("phi", 1.618); ("pi", 3.14)]

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

تتعقّد عملية bindings بسبب احتمال وجود مفاتيح مكررة في القائمة. وتستخدم دالة مساعدة keys لاستخراج قائمة المفاتيح الفريدة بمساعدة دالة المكتبة List.sort_uniq. وتلك الدالة ترتب قائمة مدخلة وتطرح التكرارات في أثناء ذلك. وهي تتطلب دالة مقارنة كمدخل.

ملاحظة

يجب أن تعيد دالة المقارنة القيمة 0 إذا تعادل معاملاها، وعددًا صحيحًا موجبًا إذا كان الأول أكبر، وعددًا صحيحًا سالبًا إذا كان الأول أصغر.

نستخدم هنا دالة المقارنة Stdlib.compare من المكتبة القياسية، وهي تسلك أساسًا السلوك نفسه الذي تسلكه مؤثرات المقارنة المدمجة = و<> وغيرها. وتفيد دوال المقارنة المخصصة إن أردت مفهومًا متسامحًا لما يُعد تكرارًا. فمثلًا، ربما تريد تجاهل حالة الأحرف في السلاسل النصية، أو إشارة عدد، وما إلى ذلك.

زمن تشغيل List.sort_uniq خطي شبه لوغاريتمي، وينتج عددًا خطيًا من المفاتيح كمخرج. ونُجري لكل مفتاح من تلك المفاتيح عملية بحث خطية الزمن. لذا فزمن التشغيل الكلي لـ bindings هو $O(n \log n) + O(n) \cdot O(n)$، أي $O(n^2)$. ويمكننا بالتأكيد أن نفعل أفضل من ذلك ببنى معطيات أكثر تقدمًا.

بل يمكننا الحصول على عملية bindings ثابتة الزمن حتى بقوائم الترابط، إن كنا مستعدين لدفع ثمن عملية insert خطية الزمن:

module UniqAssocListMap : Map = struct
  (** The list [(k1, v1); ...; (kn, vn)] binds key [ki] to value [vi].
      No duplicate keys may occur. *)
  type ('k, 'v) t = ('k * 'v) list
  let empty = []
  let insert k v m = (k, v) :: List.remove_assoc k m
  let lookup k m = List.assoc k m
  let bindings m = m
end

module UniqAssocListMap : Map

ذلك التنفيذ يزيل أي ربط مكرر لـ k قبل إدراج ربط جديد.

5.6.6. المجموعات

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

module type Set = sig
  (** ['a t] is the type of sets whose elements are of type ['a]. *)
  type 'a t
  (** [empty] is the empty set. *)
  val empty : 'a t
  (** [mem x s] is whether [x] is an element of [s]. *)
  val mem : 'a -> 'a t -> bool
  (** [add x s] is the set that contains [x] and all the elements of [s]. *)
  val add : 'a -> 'a t -> 'a t
  (** [elements s] is a list containing the elements of [s].  No guarantee
      is made about the ordering of that list, but each element is guaranteed
      to be unique. *)
  val elements : 'a t -> 'a list
end

module type Set =
  sig
    type 'a t
    val empty : 'a t
    val mem : 'a -> 'a t -> bool
    val add : 'a -> 'a t -> 'a t
    val elements : 'a t -> 'a list
  end

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

module UniqListSet : Set = struct
  type 'a t = 'a list
  let empty = []
  let mem = List.mem
  let add x s = if mem x s then s else x :: s
  let elements = Fun.id
end

module UniqListSet : Set

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

وإليك تنفيذًا ثانيًا يسمح بالتكرارات في القائمة:

module ListSet : Set = struct
  type 'a t = 'a list
  let empty = []
  let mem = List.mem
  let add = List.cons
  let elements s = List.sort_uniq Stdlib.compare s
end

module ListSet : Set

في ذلك التنفيذ، صارت عملية add ثابتة الزمن، وعملية elements خطية شبه لوغاريتمية الزمن.

5.7. قيود أنواع الوحدات

لقد أشَدْنا بمزايا التغليف. وسنفعل الآن شيئًا قد يبدو منافيًا للحدس: انتهاك التغليف انتقائيًا.

وكمثال حافز، إليك نوع وحدة يمثّل قيمًا تدعم عمليتي الجمع والضرب المعتادتين من الحساب، أو بصيغة أدق، حلقة (ring):

module type Ring = sig
  type t
  val zero : t
  val one : t
  val ( + ) : t -> t -> t
  val ( * ) : t -> t -> t
  val ( ~- ) : t -> t  (* additive inverse *)
  val to_string : t -> string
end

module type Ring =
  sig
    type t
    val zero : t
    val one : t
    val ( + ) : t -> t -> t
    val ( * ) : t -> t -> t
    val ( ~- ) : t -> t
    val to_string : t -> string
  end

تذكّر أنه يجب علينا كتابة ( * ) بدلًا من (*) لأن الأخيرة ستُحلَّل على أنها بداية تعليق. ونكتب ~ في ( ~- ) للدلالة على مؤثر أحادي.

هذا مثال غريب بعض الشيء. فلسنا نعتاد التفكير في الأعداد كبنية معطيات. لكن ما بنية المعطيات إلا مجموعة من القيم وعمليات عليها؟ ويوضح نوع الوحدة Ring أن هذا ما لدينا.

وإليك وحدة تنفّذ ذلك النوع:

module IntRing : Ring = struct
  type t = int
  let zero = 0
  let one = 1
  let ( + ) = Stdlib.( + )
  let ( * ) = Stdlib.( * )
  let ( ~- ) = Stdlib.( ~- )
  let to_string = string_of_int
end

module IntRing : Ring

ولأن t مجرّد، لا تستطيع الواجهة التفاعلية تقديم مخرجات جيدة عن ناتج جمع واحد وواحد:

IntRing.(one + one)

- : IntRing.t = <abstr>

لكن يمكننا تحويله إلى سلسلة نصية:

IntRing.(one + one |> to_string)

- : string = "2"

بل يمكننا تثبيت دالة طباعة جميلة لتفادي استدعاء to_string يدويًا:

let pp_intring fmt i =
  Format.fprintf fmt "%s" (IntRing.to_string i);;
#install_printer pp_intring;;
IntRing.(one + one)

val pp_intring : Format.formatter -> IntRing.t -> unit = <fun>

- : IntRing.t = 2

ويمكننا تنفيذ أنواع أخرى من الحلقات أيضًا:

module FloatRing : Ring = struct
  type t = float
  let zero = 0.
  let one = 1.
  let ( + ) = Stdlib.( +. )
  let ( * ) = Stdlib.( *. )
  let ( ~- ) = Stdlib.( ~-. )
  let to_string = string_of_float
end

module FloatRing : Ring

وعندئذ سيتعين علينا تثبيت دالة طباعة لها هي أيضًا:

let pp_floatring fmt f =
  Format.fprintf fmt "%s" (FloatRing.to_string f);;
#install_printer pp_floatring;;
FloatRing.(one + one)

val pp_floatring : Format.formatter -> FloatRing.t -> unit = <fun>

- : FloatRing.t = 2.

هل كانت هناك حاجة فعلًا إلى جعل النوع t مجرّدًا في أمثلة الحلقات أعلاه؟ يمكن القول إنه لا. ولو لم يكن مجرّدًا، لما اضطررنا إلى عناء تحويل القيم المجرّدة إلى سلاسل نصية، أو تثبيت دوال الطباعة. ولنواصل تلك الفكرة تاليًا.

5.7.1. تخصيص أنواع الوحدات

رأينا في الماضي أنه يمكننا إغفال التعليق النوعي للوحدة، ثم إجراء تحقق منفصل للتأكد من أن البنية تحقق التوقيع:

module IntRing = struct
  type t = int
  let zero = 0
  let one = 1
  let ( + ) = Stdlib.( + )
  let ( * ) = Stdlib.( * )
  let ( ~- ) = Stdlib.( ~- )
  let to_string = string_of_int
end
module _ : Ring = IntRing

module IntRing :
  sig
    type t = int
    val zero : int
    val one : int
    val ( + ) : int -> int -> int
    val ( * ) : int -> int -> int
    val ( ~- ) : int -> int
    val to_string : int -> string
  end

IntRing.(one + one)

- : int = 2

ثمة طريقة أكثر تطورًا لتحقيق الهدف نفسه. يمكننا تخصيص نوع الوحدة Ring لنحدد أن t يجب أن يكون int أو float. ونفعل ذلك بإضافة قيد (constraint) باستخدام الكلمة المفتاحية with:

module type INT_RING = Ring with type t = int

module type INT_RING =
  sig
    type t = int
    val zero : t
    val one : t
    val ( + ) : t -> t -> t
    val ( * ) : t -> t -> t
    val ( ~- ) : t -> t
    val to_string : t -> string
  end

لاحظ كيف يحدد نوع الوحدة INT_RING الآن أن t وint نوع واحد. فهو يكشف تلك الحقيقة، أو يشاركها (shares) مع العالم، لذا يمكن أن نسمي هذه «قيود المشاركة».

الآن يمكن إعطاء IntRing ذلك النوع:

module IntRing : INT_RING = struct
  type t = int
  let zero = 0
  let one = 1
  let ( + ) = Stdlib.( + )
  let ( * ) = Stdlib.( * )
  let ( ~- ) = Stdlib.( ~- )
  let to_string = string_of_int
end

module IntRing : INT_RING

وبما أن مساواة t وint مكشوفة، تستطيع الواجهة التفاعلية طباعة قيم النوع t دون أي مساعدة من دالة طباعة جميلة:

IntRing.(one + one)

- : IntRing.t = 2

بل يمكن للمبرمجين مزج قيم int المدمجة مع القيم التي توفرها IntRing:

IntRing.(1 + one)

- : IntRing.t = 2

ويمكن فعل الشيء نفسه مع الأعداد العشرية:

module type FLOAT_RING = Ring with type t = float
module FloatRing : FLOAT_RING = struct
  type t = float
  let zero = 0.
  let one = 1.
  let ( + ) = Stdlib.( +. )
  let ( * ) = Stdlib.( *. )
  let ( ~- ) = Stdlib.( ~-. )
  let to_string = string_of_float
end

module type FLOAT_RING =
  sig
    type t = float
    val zero : t
    val one : t
    val ( + ) : t -> t -> t
    val ( * ) : t -> t -> t
    val ( ~- ) : t -> t
    val to_string : t -> string
  end

module FloatRing : FLOAT_RING

يتبين أنه لا حاجة إلى تعريف INT_RING وFLOAT_RING منفصلين. فالكلمة المفتاحية with يمكن استخدامها كجزء من تعريف module، وإن كانت الصياغة تصير أصعب قليلًا في القراءة بسبب تقارب علامتي =:

module FloatRing : Ring with type t = float = struct
  type t = float
  let zero = 0.
  let one = 1.
  let ( + ) = Stdlib.( +. )
  let ( * ) = Stdlib.( *. )
  let ( ~- ) = Stdlib.( ~-. )
  let to_string = string_of_float
end

module FloatRing :
  sig
    type t = float
    val zero : t
    val one : t
    val ( + ) : t -> t -> t
    val ( * ) : t -> t -> t
    val ( ~- ) : t -> t
    val to_string : t -> string
  end

5.7.2. القيود

الصياغة.

هناك نوعان من القيود. أحدهما النوع الذي رأيناه أعلاه، بمعادلات type:

• T with type x = t، حيث T نوع وحدة، وx اسم نوع، وt نوع.

والنوع الآخر معادلة module، وهي سكر نحوي لتحديد مساواة جميع الأنواع في الوحدتين:

• T with module M = N، حيث M وN اسما وحدتين.

ويمكن إضافة قيود متعددة بالكلمة المفتاحية and:

• T with constraint1 and constraint2 and ... constraintN

الدلالات الساكنة.

نوع الوحدة المقيّد T with type x = t هو نفسه T، إلا أن إعلان type x داخل T يُستبدل بـ type x = t. فمثلًا، قارن التوقيعين المطبوعين أدناه:

module type T = sig type t end
module type U = T with type t = int

module type T = sig type t end

module type U = sig type t = int end

وبالمثل، T with module M = N هو نفسه T، إلا أن أي إعلان type x داخل نوع وحدة M يُستبدل بـ type x = N.x. (وكذلك الحال تعاوديًا مع أي وحدات متداخلة.) ويتطلب إعطاء هذا المثال وفهمه جهدًا أكبر:

module type XY = sig
  type x
  type y
end
module type T = sig
  module A : XY
end
module B = struct
  type x = int
  type y = float
end
module type U = T with module A = B
module C : U = struct
  module A = struct
    type x = int
    type y = float
    let x = 42
  end
end

module type XY = sig type x type y end

module type T = sig module A : XY end

module B : sig type x = int type y = float end

module type U = sig module A : sig type x = int type y = float end end

module C : U

ركّز على المخرجات الخاصة بنوع الوحدة U. لاحظ أن نوعي x وy فيه صارا int وfloat بسبب قيد module A = B. ولاحظ أيضًا أن الوحدتين B وC.A ليستا الوحدة نفسها؛ فللأخيرة عنصر إضافي x. لذا فالصياغة module A = B قد تكون مربكة. فالقيد لا يحدد أن الوحدتين متماثلتان، بل يحدد أن أنواعهما كلها مقيَّدة بأن تكون متساوية.

الدلالات الديناميكية.

لا توجد دلالات ديناميكية للقيود، لأنها للتحقق من الأنواع فحسب.

5.8. التضمينات

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

يوفر نظام وحدات OCaml ميزة أنيقة تسمى التضمينات (includes)، وهي أشبه بنسخ ولصق منظّم سريع وسهل الاستخدام، لكنه يتجنب التكرار الفعلي. ويمكن استخدامها لحل بعض المشكلات نفسها التي تحلها الوراثة (inheritance) في اللغات كائنية التوجه.

لنبدأ بمثال. تذكّر هذا التنفيذ للمجموعات كقوائم:

module type Set = sig
  type 'a t
  val empty : 'a t
  val mem : 'a -> 'a t -> bool
  val add : 'a -> 'a t -> 'a t
  val elements : 'a t -> 'a list
end
module ListSet : Set = struct
  type 'a t = 'a list
  let empty = []
  let mem = List.mem
  let add = List.cons
  let elements s = List.sort_uniq Stdlib.compare s
end

module type Set =
  sig
    type 'a t
    val empty : 'a t
    val mem : 'a -> 'a t -> bool
    val add : 'a -> 'a t -> 'a t
    val elements : 'a t -> 'a list
  end

module ListSet : Set

افترض أننا أردنا إضافة دالة of_list : 'a list -> 'a t تبني مجموعة من قائمة. لو كان لدينا وصول إلى الشيفرة المصدرية لكل من ListSet وSet، ولو كان مسموحًا لنا بتعديلها، لما كان ذلك صعبًا. لكن ماذا لو كانتا مكتبتين من طرف ثالث لا نملك شيفرتهما المصدرية؟

في Java، قد نستخدم الوراثة لحل هذه المشكلة:

interface Set<T> { ... }
class ListSet<T> implements Set<T> { ... }
class ListSetExtended<T> extends ListSet<T> {
  Set<T> ofList(List<T> lst) { ... }
}

يساعدنا ذلك على إعادة استخدام الشيفرة، لأن الصنف الفرعي يرث كل طرق صنفه الأعلى.

والتضمينات في OCaml مشابهة. فهي تتيح لوحدة أن تضم كل العناصر التي تعرّفها وحدة أخرى، أو لنوع وحدة أن يضم كل مواصفات نوع وحدة آخر.

وإليك كيف يمكننا استخدام التضمينات لحل مشكلة إضافة of_list إلى ListSet:

module ListSetExtended = struct
  include ListSet
  let of_list lst = List.fold_right add lst empty
end

module ListSetExtended :
  sig
    type 'a t = 'a ListSet.t
    val empty : 'a t
    val mem : 'a -> 'a t -> bool
    val add : 'a -> 'a t -> 'a t
    val elements : 'a t -> 'a list
    val of_list : 'a list -> 'a t
  end

تقول هذه الشيفرة إن ListSetExtended وحدة تضم كل تعريفات الوحدة ListSet، إضافة إلى تعريف of_list. ولا نحتاج إلى معرفة الشيفرة المصدرية التي تنفّذ ListSet لتحقيق ذلك.

ملاحظة

قد تتساءل لماذا لا يمكننا ببساطة تنفيذ of_list كدالة الهوية. انظر القسم أدناه عن التغليف لمعرفة الجواب.

5.8.1. دلالات التضمين

يمكن استخدام التضمينات داخل البنى والتواقيع. فعندما نضمّن داخل توقيع، يجب أن نضمّن توقيعًا آخر. وعندما نضمّن داخل بنية، يجب أن نضمّن بنية أخرى.

تضمين بنية هو في جوهره مجرد سكر نحوي لكتابة تعريف محلي لكل اسم معرّف في الوحدة. فكتابة include ListSet كما فعلنا أعلاه، مثلًا، لها أثر مشابه لكتابة ما يلي:

module ListSetExtended = struct
  (* BEGIN all the includes *)
  type 'a t = 'a ListSet.t
  let empty = ListSet.empty
  let mem = ListSet.mem
  let add = ListSet.add
  let elements = ListSet.elements
  (* END all the includes *)
  let of_list lst = List.fold_right add lst empty
end

module ListSetExtended :
  sig
    type 'a t = 'a ListSet.t
    val empty : 'a ListSet.t
    val mem : 'a -> 'a ListSet.t -> bool
    val add : 'a -> 'a ListSet.t -> 'a ListSet.t
    val elements : 'a ListSet.t -> 'a list
    val of_list : 'a list -> 'a ListSet.t
  end

لا شيء من ذلك ينسخ فعلًا الشيفرة المصدرية لـ ListSet. بل إن include تنشئ ببساطة تعريفًا جديدًا في ListSetExtended بالاسم نفسه الذي لكل تعريف في ListSet. لكن لو تغيّرت يومًا مجموعة الأسماء المعرّفة داخل ListSet، لعكست include ذلك التغيير، بينما لا تفعل عملية نسخ ولصق.

وتضمين توقيع يشبه ذلك كثيرًا. فمثلًا، يمكننا كتابة:

module type SetExtended = sig
  include Set
  val of_list : 'a list -> 'a t
end

module type SetExtended =
  sig
    type 'a t
    val empty : 'a t
    val mem : 'a -> 'a t -> bool
    val add : 'a -> 'a t -> 'a t
    val elements : 'a t -> 'a list
    val of_list : 'a list -> 'a t
  end

وسيكون لذلك أثر مشابه لكتابة ما يلي:

module type SetExtended = sig
  (* BEGIN all the includes *)
  type 'a t
  val empty : 'a t
  val mem : 'a -> 'a t -> bool
  val add : 'a -> 'a t -> 'a t
  val elements  : 'a t -> 'a list
  (* END all the includes *)
  val of_list : 'a list -> 'a t
end

module type SetExtended =
  sig
    type 'a t
    val empty : 'a t
    val mem : 'a -> 'a t -> bool
    val add : 'a -> 'a t -> 'a t
    val elements : 'a t -> 'a list
    val of_list : 'a list -> 'a t
  end

وسيكون ذلك النوع مناسبًا لـ ListSetExtended:

module ListSetExtended : SetExtended = struct
  include ListSet
  let of_list lst = List.fold_right add lst empty
end

module ListSetExtended : SetExtended

5.8.2. التغليف والتضمين

ذكرنا أعلاه أنك قد تتساءل لماذا لم نكتب هذا التعريف الأبسط لـ of_list:

module ListSetExtended : SetExtended = struct
  include ListSet
  let of_list lst = lst
end

File "[7]", lines 1-4, characters 39-3:
1 | .......................................struct
2 |   include ListSet
3 |   let of_list lst = lst
4 | end
Error: Signature mismatch:
       ...
       Values do not match:
         val of_list : 'a -> 'a
       is not included in
         val of_list : 'a list -> 'a t
       The type 'a list -> 'a list is not compatible with the type
         'a list -> 'a t
       Type 'a list is not compatible with type 'a t = 'a ListSet.t 
       File "[5]", line 9, characters 2-31: Expected declaration
       File "[7]", line 3, characters 6-13: Actual declaration

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

module ListSetExtended : SetExtended = struct
  include ListSet
  let of_list (lst : 'a list) : 'a t = lst
end

File "[8]", line 3, characters 39-42:
3 |   let of_list (lst : 'a list) : 'a t = lst
                                           ^^^
Error: This expression has type 'a list
       but an expression was expected of type 'a t = 'a ListSet.t

آه، صارت المشكلة الآن أوضح: في جسم of_list، مساواة 'a t و'a list غير معروفة. فنحن في ListSetExtended نعلم أن 'a t = 'a ListSet.t، لأن ذلك ما أعطتنا إياه include. لكن حقيقة أن 'a ListSet.t = 'a list كانت مخفية عندما أُغلقت ListSet عند نوع الوحدة Set. لذا يجب أن تلتزم التضمينات بالتغليف، كما يلتزم به بقية نظام الوحدات.

وثمة حل بديل هو إعادة كتابة التعريفات كما يلي:

module ListSetImpl = struct
  type 'a t = 'a list
  let empty = []
  let mem = List.mem
  let add = List.cons
  let elements s = List.sort_uniq Stdlib.compare s
end
module ListSet : Set = ListSetImpl
module type SetExtended = sig
  include Set
  val of_list : 'a list -> 'a t
end
module ListSetExtendedImpl = struct
  include ListSetImpl
  let of_list lst = lst
end
module ListSetExtended : SetExtended = ListSetExtendedImpl

module ListSetImpl :
  sig
    type 'a t = 'a list
    val empty : 'a list
    val mem : 'a -> 'a list -> bool
    val add : 'a -> 'a list -> 'a list
    val elements : 'a list -> 'a list
  end

module ListSet : Set

module type SetExtended =
  sig
    type 'a t
    val empty : 'a t
    val mem : 'a -> 'a t -> bool
    val add : 'a -> 'a t -> 'a t
    val elements : 'a t -> 'a list
    val of_list : 'a list -> 'a t
  end

module ListSetExtendedImpl :
  sig
    type 'a t = 'a list
    val empty : 'a list
    val mem : 'a -> 'a list -> bool
    val add : 'a -> 'a list -> 'a list
    val elements : 'a list -> 'a list
    val of_list : 'a -> 'a
  end

module ListSetExtended : SetExtended

التغيير المهم أن ListSetImpl غير مغلقة، فنوعها 'a t ليس مجرّدًا. وعندما نضمّنها في ListSetExtended، يمكننا إذن استغلال كونها مرادفًا لـ 'a list.

وما فعلناه للتو هو فعليًا الشيء نفسه الذي تفعله Java للتعامل مع محددات الرؤية public وprivate وغيرها. فـ«النسخة الخاصة» من الصنف تشبه نسخة Impl أعلاه: فكل من يستطيع رؤية تلك النسخة يستطيع رؤية كل العناصر المكشوفة (الحقول في Java، والأنواع في OCaml)، دون أي تغليف. أما «النسخة العامة» من الصنف فتشبه النسخة المغلقة أعلاه: فكل من يستطيع رؤية تلك النسخة يُلزَم بمعاملة العناصر كمجرّدة، ومن ثم مغلّفة.

وبهذه التقنية، إن أردنا تقديم تنفيذ جديد لإحدى الدوال المضمّنة، أمكننا فعل ذلك أيضًا:

module ListSetExtendedImpl = struct
  include ListSetImpl
  let of_list lst = List.fold_right add lst empty
  let rec elements = function
    | [] -> []
    | h :: t -> if mem h t then elements t else h :: elements t
end

module ListSetExtendedImpl :
  sig
    type 'a t = 'a list
    val empty : 'a list
    val mem : 'a -> 'a list -> bool
    val add : 'a -> 'a list -> 'a list
    val of_list : 'a list -> 'a list
    val elements : 'a list -> 'a list
  end

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

تحذير

وهذا يختلف عما قد تتوقعه من Java، التي تستخدم ميزة لغوية تسمى الإرسال الديناميكي لتحديد أي تنفيذ للطريقة يُستدعى. ويكاد الإرسال الديناميكي يكون السمة المميزة للغات كائنية التوجه. أما دوال OCaml فليست طرقًا، وهي لا تستخدم الإرسال الديناميكي.

5.8.3. include مقابل open

تتشابه عبارتا include وopen كثيرًا، لكن لكل منهما أثر مختلف قليلًا في البنية. تأمل هذه الشيفرة:

module M = struct
  let x = 0
end
module N = struct
  include M
  let y = x + 1
end
module O = struct
  open M
  let y = x + 1
end

module M : sig val x : int end

module N : sig val x : int val y : int end

module O : sig val y : int end

انظر بدقة إلى القيم المحتواة في كل بنية. فـ N تحتوي على كل من x وy، بينما تحتوي O على y فحسب. والسبب أن include M تجعل كل تعريفات M مضمّنة أيضًا في N، فيوجد تعريف x من M في N. لكن open M جعلت تلك التعريفات متاحة في نطاق O فحسب؛ فهي لا تجعلها فعلًا جزءًا من البنية. لذا لا تحتوي O على تعريف x، رغم أن x في النطاق أثناء تقييم تعريف y في O.

وقد يفيد هذا التشبيه في فهم الفرق: open M تستورد التعريفات من M وتجعلها متاحة للاستهلاك المحلي، لكنها لا تُصدَّر إلى العالم الخارجي. أما include M فتستورد التعريفات من M، وتجعلها متاحة للاستهلاك المحلي، وتصدّرها بالإضافة إلى ذلك إلى العالم الخارجي.

5.8.4. تضمين الشيفرة في وحدات متعددة

تذكّر أن لدينا أيضًا تنفيذًا للمجموعات يضمن أن كل عنصر في القائمة الأساسية فريد:

module UniqListSet : Set = struct
  (** All values in the list must be unique. *)
  type 'a t = 'a list
  let empty = []
  let mem = List.mem
  let add x s = if mem x s then s else x :: s
  let elements = Fun.id
end

module UniqListSet : Set

افترض أننا أردنا إضافة of_list إلى تلك الوحدة أيضًا. ومن الاحتمالات نسخ تلك الدالة ولصقها من ListSet إلى UniqListSet. لكن ذلك هندسة برمجيات رديئة. فلنستبعده فورًا كحل غير مقبول.

وبدلًا من ذلك، افترض أننا نحاول تعريف الدالة خارج أي من الوحدتين:

let of_list lst = List.fold_right add lst empty

File "[13]", line 1, characters 34-37:
1 | let of_list lst = List.fold_right add lst empty
                                      ^^^
Error: Unbound value add

المشكلة أننا نحتاج إلى اختيار add وempty الخاصتين بأي وحدة نريد. لكن بمجرد أن نفعل ذلك، تصير الدالة مفيدة مع تلك الوحدة الوحيدة فحسب:

let of_list lst = List.fold_right ListSet.add lst ListSet.empty

val of_list : 'a list -> 'a ListSet.t = <fun>

ويمكننا جعل add وempty معاملين بدلًا من ذلك:

let of_list' add empty lst = List.fold_right add lst empty
let of_list lst = of_list' ListSet.add ListSet.empty lst
let of_list_uniq lst = of_list' UniqListSet.add UniqListSet.empty lst

val of_list' : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b = <fun>

val of_list : 'a list -> 'a ListSet.t = <fun>

val of_list_uniq : 'a list -> 'a UniqListSet.t = <fun>

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

لنحاول استخدام التضمينات لحل هذه المشكلة. أولًا، نكتب وحدة تحتوي على التنفيذ الموسَّم بمعاملات:

module SetOfList = struct
  let of_list' add empty lst = List.fold_right add lst empty
end

module SetOfList :
  sig val of_list' : ('a -> 'b -> 'b) -> 'b -> 'a list -> 'b end

ثم نضمّن تلك الوحدة للحصول على الدالة المساعدة:

module UniqListSetExtended : SetExtended = struct
  include UniqListSet
  include SetOfList
  let of_list lst = of_list' add empty lst
end
module ListSetExtended : SetExtended = struct
  include ListSet
  include SetOfList
  let of_list lst = of_list' add empty lst
end

module UniqListSetExtended : SetExtended

module ListSetExtended : SetExtended

يعمل ذلك، لكننا لم ننجح إلا جزئيًا في تحقيق إعادة استخدام الشيفرة:

• من الجانب الإيجابي، جُمِّعت الشيفرة التي تنفّذ of_list' في موضع واحد وأُعيد استخدامها في البنيتين.
• لكن من الجانب السلبي، كان علينا مع ذلك كتابة تنفيذ لـ of_list في كلتا الوحدتين. والأسوأ أن هذين التنفيذين متماثلان. فلا يزال هناك تكرار للشيفرة.

فهل يمكننا أن نفعل أفضل؟ نعم. وهذا يقودنا إلى المُوظِّفات تاليًا.

5.9. المُوظِّفات

المشكلة التي واجهتنا في القسم السابق أننا أردنا إضافة شيفرة إلى وحدتين مختلفتين، لكن تلك الشيفرة احتاجت إلى أن تُوسَّم بمعاملات هي تفاصيل الوحدة التي تُضاف إليها. وهذا النوع من التوسيم بالمعاملات هو ما تتيحه ميزة لغوية في OCaml تسمى المُوظِّفات (functors).

ملاحظة

لماذا اسم «functor»؟ في نظرية الفئات، تحتوي الفئة (category) على تشاكلات (morphisms)، وهي تعميم للدوال كما نعرفها، والمُوظِّف (functor) تطبيق بين فئتين. وبالمثل، تحتوي وحدات OCaml على دوال، وتطبّق مُوظِّفات OCaml من وحدات إلى وحدات.

الاسم مخيف للأسف، لكن المُوظِّف ليس إلا «دالة» من وحدات إلى وحدات. ووُضعت كلمة «دالة» بين علامتي تنصيص في تلك الجملة فقط لأنه نوع من الدوال لا يمكن تبادله مع بقية الدوال التي رأيناها. فنظام أنواع OCaml مطبَّق (stratified): قيم الوحدات متمايزة عن القيم الأخرى، لذا لا يمكن كتابة دوال من وحدات إلى وحدات ولا استخدامها بالطريقة نفسها التي تُكتب بها دوال من قيم إلى قيم. لكن من حيث المفهوم، المُوظِّفات دوال فعلًا.

وإليك مثالًا صغيرًا على مُوظِّف:

module type X = sig
  val x : int
end
module IncX (M : X) = struct
  let x = M.x + 1
end

module type X = sig val x : int end

module IncX : (M : X) -> sig val x : int end

اسم المُوظِّف هو IncX. وهو أساسًا دالة من وحدات إلى وحدات. وبوصفها دالة، تأخذ مدخلًا وتنتج مخرجًا. ومدخلها اسمه M ونوع مدخله X. ومخرجها هو البنية التي تظهر على يمين علامة المساواة: struct let x = M.x + 1 end.

وثمة طريقة أخرى للتفكير في IncX، وهي أنه بنية موسَّمة بمعامل (parameterized structure). والمعامل الذي يأخذه اسمه M ونوعه X. والبنية نفسها تحتوي على قيمة واحدة اسمها x. وستعتمد قيمة x على المعامل M.

وبما أن المُوظِّفات دوال أساسًا، فإننا نطبّقها. وإليك مثالًا على تطبيق IncX:

module A = struct let x = 0 end

module A : sig val x : int end

A.x

- : int = 0

module B = IncX (A)

module B : sig val x : int end

B.x

- : int = 1

module C = IncX (B)

module C : sig val x : int end

C.x

- : int = 2

في كل مرة نمرّر إلى IncX وحدة. فعندما نمرّر إليه الوحدة المرتبطة بالاسم A، يكون مدخل IncX هو struct let x = 0 end. ويأخذ المُوظِّف IncX ذلك المدخل وينتج مخرجًا هو struct let x = A.x + 1 end. وبما أن A.x هي 0، فالنتيجة struct let x = 1 end. لذا يُربط B بـ struct let x = 1 end. وبالمثل، ينتهي C مرتبطًا بـ struct let x = 2 end.

ورغم أن المُوظِّف IncX يعيد وحدة تشبه وحدة مدخله كثيرًا، فليس ذلك لازمًا. بل يمكن للمُوظِّف أن يعيد أي وحدة يريدها، وربما شيئًا مختلفًا جدًا عن بنية مدخله:

module AddX (M : X) = struct
  let add y = M.x + y
end

module AddX : (M : X) -> sig val add : int -> int end

ولنطبّق ذلك المُوظِّف على وحدة. بل لا يلزم أن تكون الوحدة مرتبطة باسم؛ يمكننا ببساطة كتابة بنية مجهولة:

module Add42 = AddX (struct let x = 42 end)

module Add42 : sig val add : int -> int end

Add42.add 1

- : int = 43

لاحظ أن وحدة المدخل إلى AddX تحتوي على قيمة اسمها x، لكن وحدة المخرج من AddX لا تحتوي عليها:

Add42.x

File "[11]", line 1, characters 0-7:
1 | Add42.x
    ^^^^^^^
Error: Unbound value Add42.x

تحذير

من المغري أن نظن أن المُوظِّف هو نفسه extends في Java، وأن المُوظِّف بذلك يوسّع وحدة المدخل بتعريفات جديدة مع إبقاء التعريفات القديمة أيضًا. ويبيّن المثال أعلاه أن ذلك ليس هو الحال. فالمُوظِّف ليس في جوهره إلا دالة، وتلك الدالة يمكن أن تعيد ما يريد المبرمج. بل يمكن أن يكون مخرج المُوظِّف مختلفًا اعتباطيًا عن المدخل.

5.9.1. صياغة المُوظِّفات ودلالاتها

في صياغة المُوظِّفات التي كنا نستخدمها:

module F (M : S) = ...
end

فإن التعليق النوعي : S والقوسين حوله، (M : S)، مطلوبان. والسبب أن OCaml يحتاج إلى توفير المعلومات النوعية عن S لينجز عملًا جيدًا في استدلال الأنواع لـ F نفسها.

وكما في الدوال، يمكن كتابة المُوظِّفات بلا اسم. والصياغتان التاليتان للمُوظِّفات متكافئتان:

module F (M : S) = ...
module F = functor (M : S) -> ...

وتستخدم الصيغة الثانية الكلمة المفتاحية functor لإنشاء مُوظِّف مجهول، كما تنشئ الكلمة المفتاحية fun دالة مجهولة.

كما يمكن توسيم المُوظِّفات بمعاملات على عدة بنى:

module F (M1 : S1) ... (Mn : Sn) = ...

وبالطبع، ذلك مجرد سكر نحوي لـ مُوظِّف عالي الرتبة (higher-order functor) يأخذ بنية كمدخل ويعيد مُوظِّفًا مجهولًا:

module F = functor (M1 : S1) -> ... -> functor (Mn : Sn) -> ...

وإذا أردت تحديد نوع مخرج المُوظِّف، فالصياغة تشبه الدوال مرة أخرى:

module F (M : Si) : So = ...

وكما جرت العادة، يمكن أيضًا كتابة التعليق النوعي للمخرج على تعبير الوحدة:

module F (M : Si) = (... : So)

لتقييم تطبيق module_expression1 (module_expression2)، يُقيَّم تعبير الوحدة الأول ويجب أن ينتج مُوظِّفًا F. ثم يُقيَّم تعبير الوحدة الثاني إلى وحدة M. ثم يُطبَّق المُوظِّف على الوحدة. وسينتج المُوظِّف وحدة جديدة N في أثناء ذلك التطبيق. وتُقيَّم تلك الوحدة الجديدة كالعادة، بترتيب التعريف من أعلى إلى أسفل، مع إتاحة تعريفات M للاستخدام.

5.9.2. صياغة أنواع المُوظِّفات ودلالاتها

أبسط صياغة لأنواع المُوظِّفات هي في الواقع الصياغة نفسها الخاصة بالدوال:

module_type -> module_type

فمثلًا، X -> Add أدناه نوع مُوظِّف، وهو يعمل مع الوحدة AddX التي عرّفناها سابقًا في هذا القسم:

module type Add = sig val add : int -> int end
module CheckAddX : X -> Add = AddX

module type Add = sig val add : int -> int end

module CheckAddX : X -> Add

تزداد صياغة أنواع المُوظِّفات تعقيدًا إذا كان نوع وحدة المخرج معتمدًا على نوع وحدة المدخل. فمثلًا، افترض أننا أردنا إنشاء مُوظِّف يقرن قيمة من وحدة ما بقيمة أخرى:

module type T = sig
  type t
  val x : t
end
module Pair1 (M : T) = struct
  let p = (M.x, 1)
end

module type T = sig type t val x : t end

module Pair1 : (M : T) -> sig val p : M.t * int end

ويتبين أن نوع Pair1 هو:

functor (M : T) -> sig val p : M.t * int end

إذن يمكننا أيضًا كتابة:

module type P1 = functor (M : T) -> sig val p : M.t * int end
module Pair1 : P1 = functor (M : T) -> struct
  let p = (M.x, 1)
end

module type P1 = (M : T) -> sig val p : M.t * int end

module Pair1 : P1

نوع الوحدة P1 هو نوع مُوظِّف يأخذ وحدة مدخلة اسمها M ونوع وحدتها T، ويعيد وحدة مخرجة نوع وحدتها معطى بالتوقيع sig..end. وداخل التوقيع يكون الاسم M في النطاق. ولهذا يمكننا كتابة M.t فيه، فنضمن بذلك أن نوع المكوّن الأول من الزوج p هو النوع من الوحدة المحددة M التي تُمرَّر إلى Pair1، لا من أي وحدة أخرى. فمثلًا، إليك تجسيدين مختلفين:

module P0 = Pair1 (struct type t = int let x = 0 end)
module PA = Pair1 (struct type t = char let x = 'a' end)

module P0 : sig val p : int * int end

module PA : sig val p : char * int end

لاحظ الفرق بين int وchar في نوعي الوحدتين الناتجين. ومن المهم أن يستطيع نوع مخرج Pair1 التمييز بينهما. ولهذا يجب أن يكون بالإمكان تسمية M على يمين السهم في P1.

ملاحظة

أنواع المُوظِّفات مثال على ميزة متقدمة في لغات البرمجة تسمى الأنواع المعتمدة (dependent types)، التي يُحدَّد بها نوع المخرج بـقيمة المدخل. وهذا يختلف عن الحالة المعتادة للدالة، حيث تكون قيمة المخرج محددة بقيمة المدخل، ونوع المخرج مستقلًا عن قيمة المدخل.

وتمكّن الأنواع المعتمدة أنظمة الأنواع من التعبير عن الكثير عن صحة البرنامج، لكن فحص الأنواع والاستدلال فيها أصعب بكثير. وأنظمة الأنواع المعتمدة العملية مجال بحث نشط. وربما تصير يومًا شائعة في اللغات السائدة.

ولا يلزم أن يكون نوع وحدة الوسيطة الفعلية للمُوظِّف مطابقًا لنوع الوحدة المعلَن الصوري للوسيطة؛ فلا بأس بأن يكون نمطًا فرعيًا. فمثلًا، لا بأس في تطبيق F أدناه على X أو على Z. ولن يسبب العنصر الإضافي في Z أي صعوبة.

module F (M : sig val x : int end) = struct let y = M.x end
module X = struct let x = 0 end
module Z = struct let x = 0;; let z = 0 end
module FX = F (X)
module FZ = F (Z)

module F : (M : sig val x : int end) -> sig val y : int end

module X : sig val x : int end

module Z : sig val x : int val z : int end

module FX : sig val y : int end

module FZ : sig val y : int end

5.9.3. وحدة Map

تنفّذ وحدة Map في المكتبة القياسية خريطة (ربطًا من المفاتيح إلى القيم) باستخدام أشجار ثنائية متوازنة. وهي تستخدم المُوظِّفات استخدامًا مهمًا. وندرس في هذا القسم كيفية استخدامها. ويمكنك الاطلاع على تنفيذ تلك الوحدة على GitHub وكذلك واجهتها.

تعرّف وحدة Map مُوظِّفًا Make ينشئ بنية تنفّذ خريطة على نوع معين من المفاتيح. وذلك النوع هو بنية المدخل إلى Make. ونوع بنية المدخل تلك هو Map.OrderedType، وهي أنواع تدعم عملية compare:

module type OrderedType = sig
  type t
  val compare : t -> t -> int
end

module type OrderedType = sig type t val compare : t -> t -> int end

تحتاج وحدة Map إلى ترتيب، لأن الأشجار الثنائية المتوازنة تحتاج إلى القدرة على مقارنة المفاتيح لتحديد ما إذا كان أحدها أكبر من الآخر. ومواصفة دالة compare هي نفسها مواصفة وسيطة المقارنة في List.sort_uniq، التي ناقشناها سابقًا:

• ينبغي أن تعيد المقارنة 0 إذا تعادل مفتاحان.
• وينبغي أن تعيد المقارنة عددًا سالبًا قطعًا إذا كان المفتاح الأول أصغر من الثاني.
• وينبغي أن تعيد المقارنة عددًا موجبًا قطعًا إذا كان المفتاح الأول أكبر من الثاني.

ملاحظة

أتبدو تلك المواصفة غريبة قليلًا؟ أتبدو صعبة الحفظ فيما يتعلق بموعد إرجاع عدد سالب مقابل موجب؟ لماذا لا نعرّف نوعًا متغايرًا بدلًا من ذلك؟

type order = LT | EQ | GT
val compare : t -> t -> order

للأسف، استخدمت لغات كثيرة تاريخيًا دوال مقارنة بمواصفات مماثلة، مثل دالة strcmp في مكتبة C القياسية.

ويدعم مخرج Map.Make كل العمليات المعتادة التي نتوقعها من قاموس:

module type S = sig
  type key
  type 'a t
  val empty: 'a t
  val mem: key -> 'a t -> bool
  val add: key -> 'a -> 'a t -> 'a t
  val find: key -> 'a t -> 'a
  ...
end

ومتغير النوع 'a هو نوع القيم في الخريطة. لذا لا تستطيع أي وحدة خريطة معينة ينشئها Map.Make التعامل إلا مع نوع واحد من المفاتيح، لكنها لا تتقيد بأي نوع معين من القيم.

5.9.3.1. مثال على خريطة

وإليك مثال على استخدام المُوظِّف Map.Make:

module IntMap = Map.Make(Int)

module IntMap :
  sig
    type key = Int.t
    type 'a t = 'a Map.Make(Int).t
    val empty : 'a t
    val add : key -> 'a -> 'a t -> 'a t
    val add_to_list : key -> 'a -> 'a list t -> 'a list t
    val update : key -> ('a option -> 'a option) -> 'a t -> 'a t
    val singleton : key -> 'a -> 'a t
    val remove : key -> 'a t -> 'a t
    val merge :
      (key -> 'a option -> 'b option -> 'c option) -> 'a t -> 'b t -> 'c t
    val union : (key -> 'a -> 'a -> 'a option) -> 'a t -> 'a t -> 'a t
    val cardinal : 'a t -> int
    val bindings : 'a t -> (key * 'a) list
    val min_binding : 'a t -> key * 'a
    val min_binding_opt : 'a t -> (key * 'a) option
    val max_binding : 'a t -> key * 'a
    val max_binding_opt : 'a t -> (key * 'a) option
    val choose : 'a t -> key * 'a
    val choose_opt : 'a t -> (key * 'a) option
    val find : key -> 'a t -> 'a
    val find_opt : key -> 'a t -> 'a option
    val find_first : (key -> bool) -> 'a t -> key * 'a
    val find_first_opt : (key -> bool) -> 'a t -> (key * 'a) option
    val find_last : (key -> bool) -> 'a t -> key * 'a
    val find_last_opt : (key -> bool) -> 'a t -> (key * 'a) option
    val iter : (key -> 'a -> unit) -> 'a t -> unit
    val fold : (key -> 'a -> 'acc -> 'acc) -> 'a t -> 'acc -> 'acc
    val map : ('a -> 'b) -> 'a t -> 'b t
    val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
    val filter : (key -> 'a -> bool) -> 'a t -> 'a t
    val filter_map : (key -> 'a -> 'b option) -> 'a t -> 'b t
    val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
    val split : key -> 'a t -> 'a t * 'a option * 'a t
    val is_empty : 'a t -> bool
    val mem : key -> 'a t -> bool
    val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
    val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
    val for_all : (key -> 'a -> bool) -> 'a t -> bool
    val exists : (key -> 'a -> bool) -> 'a t -> bool
    val to_list : 'a t -> (key * 'a) list
    val of_list : (key * 'a) list -> 'a t
    val to_seq : 'a t -> (key * 'a) Seq.t
    val to_rev_seq : 'a t -> (key * 'a) Seq.t
    val to_seq_from : key -> 'a t -> (key * 'a) Seq.t
    val add_seq : (key * 'a) Seq.t -> 'a t -> 'a t
    val of_seq : (key * 'a) Seq.t -> 'a t
  end

إذا عرضت تلك المخرجات، فسترى نوع الوحدة الطويل لـ IntMap. ووحدة Int جزء من المكتبة القياسية. ومن الملائم أنها تعرّف بالفعل العنصرين اللذين يتطلبهما OrderedType، وهما t وcompare، بسلوكين مناسبين. وتعرّف المكتبة القياسية أيضًا وحدات للأنواع الأولية الأخرى (String وغيرها) تجعل استخدام أي نوع أولي كمفتاح ملائمًا.

والآن لنجرب تلك الخريطة بربط int بـ string:

open IntMap;;
let m1 = add 1 "one" empty

val m1 : string IntMap.t = <abstr>

find 1 m1

- : string = "one"

mem 42 m1

- : bool = false

find 42 m1

Exception: Not_found.

Raised at Stdlib__Map.Make.find in file "map.ml", line 141, characters 10-25
Called from <unknown> in file "[22]", line 1, characters 0-10
Called from Topeval.load_lambda in file "toplevel/byte/topeval.ml", line 93, characters 4-14

bindings m1

- : (IntMap.key * string) list = [(1, "one")]

وتتيح لنا الوحدة IntMap نفسها ربط int بـ float:

let m2 = add 1 1. empty

val m2 : float IntMap.t = <abstr>

bindings m2

- : (IntMap.key * float) list = [(1, 1.)]

لكن يجب أن تكون المفاتيح من النوع int، لا أي نوع آخر:

let m3 = add true "one" empty

File "[26]", line 1, characters 13-17:
1 | let m3 = add true "one" empty
                 ^^^^
Error: The constructor true has type bool
       but an expression was expected of type IntMap.key = int

والسبب أن وحدة IntMap أُنشئت خصيصًا لمفاتيح هي أعداد صحيحة ومرتبة وفقًا لذلك. ومرة أخرى، الترتيب حاسم، لأن بنية المعطيات الأساسية شجرة بحث ثنائية، تتطلب مقارنات للمفاتيح لتحديد موضع تخزين المفتاح في الشجرة. بل يمكنك رؤية ذلك في شيفرة المكتبة القياسية (الإصدار 4.12)، الذي يُعد ما يلي مقتطفًا منه معدَّلًا تعديلًا طفيفًا:

module Make (Ord : OrderedType) = struct
  type key = Ord.t
  type 'a t =
    | Empty
    | Node of {l : 'a t; v : key; d : 'a; r : 'a t; h : int}
      (** Left subtree, key, value/data, right subtree, height of node. *)
  let empty = Empty
  let rec mem x = function
    | Empty -> false
    | Node {l, v, r} ->
        let c = Ord.compare x v in
        c = 0 || mem x (if c < 0 then l else r)
  ...
end

نوع key معرّف كمرادف للنوع t داخل Ord، فقيم key قابلة للمقارنة باستخدام Ord.compare. وتستعين دالة mem بذلك لمقارنة المفاتيح وتقرير ما إذا كانت ستعاود على الشجرة الفرعية اليسرى أم اليمنى.

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

لذا استخدم منفّذ Map مُوظِّفًا لحل مشكلته. فقد وسّم بمعامل هو وحدة تجمع نوع المفاتيح مع دالة يمكن استخدامها لمقارنتها. ومن مسؤولية العميل أن ينفّذ تلك الوحدة.

ويحل إطار عمل مجموعات Java (Java Collections Framework) مشكلة مشابهة في صنف TreeMap، الذي له مُنشئ يأخذ Comparator. وهناك تقع على العميل مسؤولية تنفيذ صنف للمقارنات، لا بنية. ورغم اختلاف الميزات اللغوية، فالفكرة هي نفسها.

5.9.3.2. خرائط بأنواع مفاتيح مخصصة

عندما يصير نوع المفتاح معقدًا، قد نريد كتابة دالة مقارنة مخصصة خاصة بنا. فمثلاً، افترض أننا نريد خريطة تكون مفاتيحها سجلات تمثّل أسماء، وتُرتب فيها الأسماء أبجديًا حسب اسم العائلة ثم حسب الاسم الأول. وفي الشيفرة أدناه نقدم وحدة Name قادرة على مقارنة السجلات بتلك الطريقة:

type name = {first : string; last : string}
module Name = struct
  type t = name
  let compare { first = first1; last = last1 } { first = first2; last = last2 }
      =
    match String.compare last1 last2 with
    | 0 -> String.compare first1 first2
    | c -> c
end

type name = { first : string; last : string; }

module Name : sig type t = name val compare : name -> name -> int end

ويمكن استخدام وحدة Name كمدخل إلى Map.Make لأنها تحقق توقيع Map.OrderedType:

module NameMap = Map.Make (Name)

module NameMap :
  sig
    type key = Name.t
    type 'a t = 'a Map.Make(Name).t
    val empty : 'a t
    val add : key -> 'a -> 'a t -> 'a t
    val add_to_list : key -> 'a -> 'a list t -> 'a list t
    val update : key -> ('a option -> 'a option) -> 'a t -> 'a t
    val singleton : key -> 'a -> 'a t
    val remove : key -> 'a t -> 'a t
    val merge :
      (key -> 'a option -> 'b option -> 'c option) -> 'a t -> 'b t -> 'c t
    val union : (key -> 'a -> 'a -> 'a option) -> 'a t -> 'a t -> 'a t
    val cardinal : 'a t -> int
    val bindings : 'a t -> (key * 'a) list
    val min_binding : 'a t -> key * 'a
    val min_binding_opt : 'a t -> (key * 'a) option
    val max_binding : 'a t -> key * 'a
    val max_binding_opt : 'a t -> (key * 'a) option
    val choose : 'a t -> key * 'a
    val choose_opt : 'a t -> (key * 'a) option
    val find : key -> 'a t -> 'a
    val find_opt : key -> 'a t -> 'a option
    val find_first : (key -> bool) -> 'a t -> key * 'a
    val find_first_opt : (key -> bool) -> 'a t -> (key * 'a) option
    val find_last : (key -> bool) -> 'a t -> key * 'a
    val find_last_opt : (key -> bool) -> 'a t -> (key * 'a) option
    val iter : (key -> 'a -> unit) -> 'a t -> unit
    val fold : (key -> 'a -> 'acc -> 'acc) -> 'a t -> 'acc -> 'acc
    val map : ('a -> 'b) -> 'a t -> 'b t
    val mapi : (key -> 'a -> 'b) -> 'a t -> 'b t
    val filter : (key -> 'a -> bool) -> 'a t -> 'a t
    val filter_map : (key -> 'a -> 'b option) -> 'a t -> 'b t
    val partition : (key -> 'a -> bool) -> 'a t -> 'a t * 'a t
    val split : key -> 'a t -> 'a t * 'a option * 'a t
    val is_empty : 'a t -> bool
    val mem : key -> 'a t -> bool
    val equal : ('a -> 'a -> bool) -> 'a t -> 'a t -> bool
    val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int
    val for_all : (key -> 'a -> bool) -> 'a t -> bool
    val exists : (key -> 'a -> bool) -> 'a t -> bool
    val to_list : 'a t -> (key * 'a) list
    val of_list : (key * 'a) list -> 'a t
    val to_seq : 'a t -> (key * 'a) Seq.t
    val to_rev_seq : 'a t -> (key * 'a) Seq.t
    val to_seq_from : key -> 'a t -> (key * 'a) Seq.t
    val add_seq : (key * 'a) Seq.t -> 'a t -> 'a t
    val of_seq : (key * 'a) Seq.t -> 'a t
  end

والآن يمكننا استخدام تلك الخريطة لربط الأسماء بسنوات الميلاد:

let k1 = {last = "Kardashian"; first = "Kourtney"}
let k2 = {last = "Kardashian"; first = "Kimberly"}
let k3 = {last = "Kardashian"; first = "Khloe"}
let nm =
  NameMap.(empty |> add k1 1979 |> add k2 1980 |> add k3 1984)
let lst = NameMap.bindings nm

val k1 : name = {first = "Kourtney"; last = "Kardashian"}

val k2 : name = {first = "Kimberly"; last = "Kardashian"}

val k3 : name = {first = "Khloe"; last = "Kardashian"}

val nm : int NameMap.t = <abstr>

val lst : (NameMap.key * int) list =
  [({first = "Khloe"; last = "Kardashian"}, 1984);
   ({first = "Kimberly"; last = "Kardashian"}, 1980);
   ({first = "Kourtney"; last = "Kardashian"}, 1979)]

لاحظ أن ترتيب المفاتيح في تلك القائمة ليس ترتيب إضافتها. فالقائمة مرتبة وفقًا لدالة Name.compare التي كتبناها. وستعالج أيضًا عدة دوال أخرى في توقيع Map.S روابط الخريطة بذلك الترتيب المرتب—مثل map وfold وiter.

5.9.3.3. كيف تستخدم Map قيود أنواع الوحدات

في واجهة map.mli في المكتبة القياسية، تكون مواصفة Map.Make كالتالي:

module Make (Ord : OrderedType) : S with type key = Ord.t

والقيد with هناك حاسم. تذكّر أن قيود الأنواع تخصص نوع وحدة. وهنا يخصص S with type key = Ord.t النوع S لكشف مساواة S.key وOrd.t. بعبارة أخرى، نوع المفاتيح هو النوع المرتب.

ويمكنك رؤية أثر قيد المشاركة ذلك بالنظر إلى نوع الوحدة في مثال IntMap السابق. فقيد المشاركة هو ما جعل = Int.t حاضرًا:

module IntMap : sig
  type key = Int.t
  ...
end

وتحتوي وحدة Int على السطر التالي:

type t = int

إذن IntMap.key = Int.t = int، وهذا بالضبط سبب السماح لنا بتمرير int إلى دالتي add وmem في IntMap.

لولا قيد النوع، لبقي النوع key مجرّدًا. ويمكننا محاكاة ذلك بإضافة تعليق نوعي للوحدة من النوع Map.S، فنغلق الوحدة عند ذلك النوع من جديد دون كشف المساواة:

module UnusableMap = (IntMap : Map.S);;

module UnusableMap : Map.S

والآن صار من المستحيل إضافة ربط إلى الخريطة:

let m = UnusableMap.(empty |> add 0 "zero")

File "[31]", line 1, characters 34-35:
1 | let m = UnusableMap.(empty |> add 0 "zero")
                                      ^
Error: The constant 0 has type int but an expression was expected of type
         UnusableMap.key

هذا النوع من حالات الاستخدام هو سبب كون قيود أنواع الوحدات مهمة جدًا في البرمجة الفعالة بنظام وحدات OCaml. فكثيرًا ما يلزم تخصيص نوع مخرج مُوظِّف لإظهار علاقة بين نوع فيه ونوع في أحد مدخلات المُوظِّف. لكن التفكير مليًا في القيد اللازم بالضبط قد يكون صعبًا!

5.9.4. استخدام المُوظِّفات

رأينا مع Map حالة استخدام واحدة للمُوظِّفات: إنتاج بنية معطيات موسَّمة بمعامل هو ترتيب يقدمه العميل. وإليك حالتَي استخدام أخريين.

5.9.4.1. أجنحة الاختبار

وإليك تنفيذان لمكدّس:

exception Empty
module type Stack = sig
  type 'a t
  val empty : 'a t
  val push : 'a -> 'a t -> 'a t
  val peek : 'a t -> 'a
  val pop : 'a t -> 'a t
end
module ListStack = struct
  type 'a t = 'a list
  let empty = []
  let push = List.cons
  let peek = function [] -> raise Empty | x :: _ -> x
  let pop = function [] -> raise Empty | _ :: s -> s
end
module VariantStack = struct
  type 'a t = E | S of 'a * 'a t
  let empty = E
  let push x s = S (x, s)
  let peek = function E -> raise Empty | S (x, _) -> x
  let pop = function E -> raise Empty | S (_, s) -> s
end

exception Empty

module type Stack =
  sig
    type 'a t
    val empty : 'a t
    val push : 'a -> 'a t -> 'a t
    val peek : 'a t -> 'a
    val pop : 'a t -> 'a t
  end

module ListStack :
  sig
    type 'a t = 'a list
    val empty : 'a list
    val push : 'a -> 'a list -> 'a list
    val peek : 'a list -> 'a
    val pop : 'a list -> 'a list
  end

module VariantStack :
  sig
    type 'a t = E | S of 'a * 'a t
    val empty : 'a t
    val push : 'a -> 'a t -> 'a t
    val peek : 'a t -> 'a
    val pop : 'a t -> 'a t
  end

افترض أننا أردنا كتابة اختبار OUnit لـ ListStack:

let test = "peek (push x empty) = x" >:: fun _ ->
  assert_equal 1 ListStack.(empty |> push 1 |> peek)

للأسف، لاختبار VariantStack، سيتعين علينا تكرار تلك الشيفرة:

let test' = "peek (push x empty) = x" >:: fun _ ->
  assert_equal 1 VariantStack.(empty |> push 1 |> peek)

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

وتقدم المُوظِّفات حلًا أفضل. يمكننا كتابة مُوظِّف موسَّم بمعامل هو تنفيذ المكدّس، وينتج الاختبار لذلك التنفيذ:

module StackTester (S : Stack) = struct
  let tests = [
    "peek (push x empty) = x" >:: fun _ ->
      assert_equal 1 S.(empty |> push 1 |> peek)
  ]
end
module ListStackTester = StackTester (ListStack)
module VariantStackTester = StackTester (VariantStack)
let all_tests = List.flatten [
  ListStackTester.tests;
  VariantStackTester.tests
]

الآن كلما ابتكرنا اختبارًا جديدًا أضفناه إلى StackTester، فيُشغَّل تلقائيًا على تنفيذي المكدّس معًا. رائع!

لكن لا يزال هناك بعض تكرار الشيفرة غير المستحسن، إذ علينا كتابة سطرين من الشيفرة لكل تنفيذ. ويمكننا إزالة ذلك التكرار باستخدام الوحدات من الرتبة الأولى:

let stacks = [ (module ListStack : Stack); (module VariantStack) ]
let all_tests =
  let tests m =
    let module S = (val m : Stack) in
    let module T = StackTester (S) in
    T.tests
  in
  let open List in
  stacks |> map tests |> flatten

الآن يكفي أن نضيف أحدث تنفيذ للمكدّس إلى قائمة stacks فحسب. أجمل!

5.9.4.2. توسيع وحدات متعددة

حاولنا سابقًا إضافة دالة of_list إلى كل من ListSet وUniqListSet دون أي شيفرة مكررة، لكننا لم ننجح نجاحًا كاملًا. ولنفعلها الآن على نحو صحيح حقًا.

المشكلة التي واجهتنا سابقًا أننا احتجنا إلى توسيم تنفيذ of_list بمعاملات هي دالة add وقيمة empty في وحدة المجموعة. ويمكننا تحقيق ذلك التوسيم بمُوظِّف:

module type Set = sig
  type 'a t
  val empty : 'a t
  val mem : 'a -> 'a t -> bool
  val add : 'a -> 'a t -> 'a t
  val elements : 'a t -> 'a list
end
module SetOfList (S : Set) = struct
  let of_list lst = List.fold_right S.add lst S.empty
end

لاحظ كيف يستخدم المُوظِّف، في جسمه، S.add. فهو يأخذ تنفيذ add من S ويستخدمه لتنفيذ of_list (وكذلك الأمر بالنسبة إلى empty)، فيحل بذلك المشكلة نفسها التي واجهتنا سابقًا عند محاولة استخدام التضمينات.

وعندما نطبّق SetOfList على تنفيذَي مجموعتنا، نحصل على وحدتين تحتوي كل منهما على دالة of_list الخاصة بالتنفيذ المقابل:

module ListSet : Set = struct
  type 'a t = 'a list
  let empty = []
  let mem = List.mem
  let add = List.cons
  let elements s = List.sort_uniq Stdlib.compare s
end
module UniqListSet : Set = struct
  (** All values in the list must be unique. *)
  type 'a t = 'a list
  let empty = []
  let mem = List.mem
  let add x s = if mem x s then s else x :: s
  let elements = Fun.id
end

module OfList = SetOfList (ListSet)
module UniqOfList = SetOfList (UniqListSet)

module OfList : sig val of_list : 'a list -> 'a ListSet.t end

module UniqOfList : sig val of_list : 'a list -> 'a UniqListSet.t end

وقد مكّن المُوظِّف إعادة استخدام الشيفرة التي لم نتمكن من الحصول عليها سابقًا: فيمكننا الآن تنفيذ دالة of_list واحدة واشتقاق تنفيذين منها لمجموعتين مختلفتين.

لكن تلك هي الدالة الوحيدة التي تحتوي عليها الوحدتان. وما نريده فعلًا هو تنفيذ مجموعة كامل يحتوي أيضًا على دالة of_list. ويمكننا الحصول على ذلك بدمج التضمينات مع المُوظِّفات:

module SetWithOfList (S : Set) = struct
  include S
  let of_list lst = List.fold_right S.add lst S.empty
end

module SetWithOfList :
  (S : Set) ->
    sig
      type 'a t = 'a S.t
      val empty : 'a t
      val mem : 'a -> 'a t -> bool
      val add : 'a -> 'a t -> 'a t
      val elements : 'a t -> 'a list
      val of_list : 'a list -> 'a S.t
    end

يأخذ ذلك المُوظِّف مجموعة كمدخل، وينتج وحدة تحتوي على كل شيء من تلك المجموعة (بسبب include) إضافة إلى دالة جديدة of_list.

وعندما نطبّق المُوظِّف، نحصل على وحدة مجموعة جميلة جدًا:

module SetL = SetWithOfList (ListSet)
module UniqSetL = SetWithOfList (UniqListSet)

module SetL :
  sig
    type 'a t = 'a ListSet.t
    val empty : 'a t
    val mem : 'a -> 'a t -> bool
    val add : 'a -> 'a t -> 'a t
    val elements : 'a t -> 'a list
    val of_list : 'a list -> 'a ListSet.t
  end

module UniqSetL :
  sig
    type 'a t = 'a UniqListSet.t
    val empty : 'a t
    val mem : 'a -> 'a t -> bool
    val add : 'a -> 'a t -> 'a t
    val elements : 'a t -> 'a list
    val of_list : 'a list -> 'a UniqListSet.t
  end

لاحظ كيف تسجّل بنية المخرج أن نوعها t هو النوع نفسه الموجود في بنية مدخلها. فهما يشاركانه بسبب include.

وبالنظر إلى الأمر من بعيد، فما فعلناه للتو يشبه تشابهًا كبيرًا توسيع الأصناف في Java. فقد أنشأنا وحدة أساسية ووسّعنا وظائفها بشيفرة جديدة مع الحفاظ على وظائفها القديمة. لكن بينما يقتضي توسيع الأصناف أن يكون الصنف الموسَّع حديثًا نمطًا فرعيًا للقديم، وأن تبقى له كل الوظائف القديمة، فإن مُوظِّفات OCaml أدق تفصيلًا فيما تستطيع تحقيقه. فيمكننا اختيار ما إذا كانت تضم الوظائف القديمة. ولا تلزم بالضرورة أي علاقات تنميط فرعي. علاوة على ذلك، يمكن استخدام المُوظِّف الذي كتبناه لتوسيع أي تنفيذ للمجموعة بـ of_list، بينما لا ينطبق توسيع الأصناف إلا على صنف أساسي واحد. وثمة طرق لتحقيق شيء مشابه في اللغات كائنية التوجه بـالممزوجات (mixins)، التي تمكّن صنفًا من إعادة استخدام وظائف من أصناف أخرى دون أن يقتضي ذلك تعقيد الوراثة المتعددة.

5.10. الملخّص

يوفر نظام وحدات OCaml آليات للبرمجة المعيارية تقدّم قدرات مشابهة لآليات رأيتها في لغات أخرى. لكن ظهور تلك الآليات بأشكال مختلفة يساعدك، كما نأمل، على فهمها فهمًا أفضل. فالأنواع المجرّدة والتواقيع في OCaml، على سبيل المثال، توفر آلية للتجريد تشبه محدّدات الظهور (visibility modifiers) والواجهات في Java. ورؤية الفكرة نفسها مجسّدة في لغتين مختلفتين، لكن معبَّرًا عنها بطرق مختلفة تمامًا، ستساعدك، كما نأمل، على التعرّف على الفكرة عندما تصادفها في لغات أخرى مستقبلًا.

علاوة على ذلك، فإن فكرة إمكان أن يكون النوع مجرّدًا فكرة مؤسِّسة في تصميم لغات البرمجة. ويجعل نظام وحدات OCaml هذه الفكرة ظاهرة بجلاء. أما لغات أخرى كـ Java فتحجبها بعض الشيء بقرنها مع كثير من الميزات الأخرى دفعة واحدة. وهناك معنى يكون فيه كل صنف Java معرِّفًا ضمنًا لنوع مجرّد (بل أربعة أنواع مجرّدة مترابطة بالتنميط الفرعي، واحد لكل محدّد ظهور [public، protected، private، وdefault])، وتكون كل دوال الصنف دوالًا على ذلك النوع المجرّد.

المُوظِّفات (functors) ميزة لغوية متقدّمة في OCaml قد تبدو غامضة في البداية. وإن كان الأمر كذلك فتذكّر: إنها في الحقيقة مجرّد نوع من الدوال يأخذ بنية مدخلًا ويعيد بنية مخرجًا. وسبب عدم تصرّفها تمامًا كدوال OCaml العادية هو أن البنى ليست قيمًا من الرتبة الأولى في OCaml: فلا يمكنك كتابة دوال عادية تأخذ بنية مدخلًا أو تعيد بنية مخرجًا. لكن المُوظِّفات تستطيع فعل ذلك بالضبط.

تتيح المُوظِّفات والتضمينات إعادة استخدام الشيفرة. وأنواع إعادة استخدام الشيفرة التي تتيحها ميزات البرمجة كائنية التوجه يمكن تحقيقها أيضًا بالمُوظِّفات والتضمين. ولا يعني ذلك أن المُوظِّفات والتضمينات مكافئة تمامًا لتلك الميزات كائنية التوجه: فبعض أنواع إعادة استخدام الشيفرة قد يكون تحقيقها أسهل بمجموعة ميزات من الأخرى.

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

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

5.10.1. المصطلحات والمفاهيم

• نوع مجرّد (abstract type)
• التجريد (abstraction)
• العميل (client)
• إعادة استخدام الشيفرة (code reuse)
• وحدة الترجمة (compilation unit)
• الإعلان (declaration)
• التعريف (definition)
• التغليف (encapsulation)
• بنية معطيات عابرة (ephemeral data structure)
• بنية معطيات وظيفية (functional data structure)
• المُوظِّف (functor)
• التنفيذ (implementation)
• المنفِّذ (implementer)
• التضمين (include)
• إخفاء المعلومات (information hiding)
• الواجهة (interface)
• الاستدلال المحلي (local reasoning)
• قابلية الصيانة (maintainability)
• الخرائط (maps)
• البرمجة المعيارية (modular programming)
• المعيارية (modularity)
• الوحدة (module)
• نوع الوحدة (module type)
• فضاء الأسماء (namespace)
• open
• بنية مُعامَلة (parameterized structure)
• بنية معطيات دائمة (persistent data structure)
• نوع التمثيل (representation type)
• النطاق (scope)
• مُغلَق (sealed)
• تمثيلات المجموعات (set representations)
• قيود المشاركة (sharing constraints)
• التوقيع (signature)
• مطابقة التواقيع (signature matching)
• المواصفة (specification)
• البنية (structure)

5.10.2. قراءات إضافية

• Introduction to Objective Caml، الفصول 11 و12 و13
• OCaml from the Very Beginning، الفصل 16
• Real World OCaml، الفصول 4 و9 و10
• Purely Functional Data Structures، الفصلان 1 و2، بقلم Chris Okasaki.
• “Design Considerations for ML-Style Module Systems” بقلم Robert Harper وBenjamin C. Pierce، الفصل 8 من Advanced Topics in Types and Programming Languages، تحرير Benjamin C. Pierce، MIT Press، 2005. معالجة متقدّمة للدلالات الساكنة للوحدات.

module Stack = struct
  type 'a t = 'a list
  (* Add your definitions here. *)
end

module Queue = struct
  type 'a t = 'a list
  (* Add your definitions here. *)
end

module type ComplexSig = sig
  val zero : float * float
  val add : float * float -> float * float -> float * float
end

module Complex : ComplexSig = struct
  type t = float * float
  let zero = (0., 0.)
  let add (r1, i1) (r2, i2) = r1 +. r2, i1 +. i2
end

(** Creates a ListQueue filled with [n] elements. *)
let fill_listqueue n =
  let rec loop n q =
    if n = 0 then q
    else loop (n - 1) (ListQueue.enqueue n q) in
  loop n ListQueue.empty

let fill_batchedqueue n =
  let rec loop n q =
    if n = 0 then q
    else loop (n - 1) (BatchedQueue.enqueue n q) in
  loop n BatchedQueue.empty

module type Fraction = sig
  (* A fraction is a rational number p/q, where q != 0. *)
  type t
  (** [make n d] represents n/d, a fraction with 
      numerator [n] and denominator [d].
      Requires d <> 0. *)
  val make : int -> int -> t
  val numerator : t -> int
  val denominator : t -> int
  val to_string : t -> string
  val to_float : t -> float
  val add : t -> t -> t
  val mul : t -> t -> t
end

(** [gcd x y] is the greatest common divisor of [x] and [y].
    Requires: [x] and [y] are positive. *)
let rec gcd x y =
  if x = 0 then y
  else if (x < y) then gcd (y - x) x
  else gcd y (x - y)

# module CharMap = Map.Make(Char);;

type date = {month : int; day : int}

module Date = struct
  type t = date
  let compare ...
end

type calendar = string DateMap.t

type date = {month : int; day : int}
let make_date month day = {month; day}
let get_month d = d.month
let get_day d = d.day
let to_string d = (string_of_int d.month) ^ "/" ^ (string_of_int d.day)

(library
 (name date))

$ dune utop

type date = {month : int; day : int}
val make_date : int -> int -> date
val get_month : date -> int
val get_day : date -> int
val to_string : date -> string

type date

val format : Format.formatter -> date -> unit

#install_printer Date.format;;