البيانات والأنواع

3. البيانات والأنواع

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

• القوائم (lists) والأزواج المرتبة (tuples) قد تبدو مشابهة لما في Python؛ و
• السجلات (records) والأنواع المتغايرة (variants) قد تبدو مشابهة لنوعي struct وenum في C أو Java.

وبسبب هذه الألفة، نسمي هذه أنواع بيانات قياسية (standard). وسنتعلم التطابق النمطي (pattern matching)، وهي ميزة أقل احتمالًا أن تكون مألوفة.

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

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

• الخيارات (options)، وهي مرتبطة ارتباطًا غير وثيق بـ null في Java؛
• قوائم الترابط (association lists)، وهي تنفيذ بسيط بشكل مدهش للخرائط (أي القواميس) بالاعتماد على القوائم والأزواج المرتبة؛
• أنواع البيانات الجبرية (algebraic data types)، وهي بحق أهم نوع من الأنواع في OCaml، بل هي القوة الكامنة وراء كثير من الأنواع المدمجة الأخرى؛ و
• الاستثناءات (exceptions)، وهي نوع خاص من أنواع البيانات الجبرية.

3.1. القوائم

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

3.1.1. بناء القوائم

الصياغة. هناك ثلاث صيغ لبناء القوائم:

[]
e1 :: e2
[e1; e2; ...; en]

تُكتب القائمة الفارغة [] وتُلفظ «nil»، وهو اسم قادم من Lisp. وبالنظر إلى قائمة lst وعنصر elt، يمكننا إضافة elt إلى مقدمة lst بكتابة elt :: lst. ويُلفظ مؤثر النقطتين المزدوجتين «cons»، وهو اسم قادم من مؤثر في Lisp ينشئ كائنات في الذاكرة. ويمكن أيضًا استخدام «cons» فعلًا، كما في «سأضيف عنصرًا بـ cons إلى القائمة». ويُسمّى العنصر الأول في القائمة عادةً الرأس (head)، وتسمى بقية العناصر (إن وُجدت) الذيل (tail).

مؤثر cons الذي هو :: يميني الترابط، أي أن e1 :: e2 :: e3 تُفهم على أنها e1 :: (e2 :: e3)، لا على أنها (e1 :: e2) :: e3.

صياغة القوسين المعقوفين ملائمة لكنها غير ضرورية. فأي قائمة [e1; e2; ...; en] يمكن كتابتها بدلًا من ذلك بصياغة nil وcons الأكثر بدائية: e1 :: e2 :: ... :: en :: []. وعندما يمكن تعريف صياغة ملائمة بدلالة صياغة أكثر بدائية داخل اللغة، نسمي الصياغة الملائمة سكرًا صياغيًا (syntactic sugar): فهو يجعل اللغة «أحلى». ويسمى تحويل الصياغة الحلوة إلى الصياغة الأكثر بدائية إزالة السكر الصياغي (desugaring).

ولأن عناصر القائمة يمكن أن تكون تعبيرات اعتباطية، يمكن تداخل القوائم بعمق كما نشاء، مثل [[[]]; [[1; 2; 3]]].

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

• [] قيمة بالفعل.
• إذا قيّم e1 إلى v1، وإذا قيّم e2 إلى v2، فإن e1 :: e2 يقيّم إلى v1 :: v2.

ونتيجةً لتلك القواعد ولطريقة إزالة السكر الصياغي عن ترميز القوسين المعقوفين للقوائم، لدينا القاعدة المشتقة التالية:

• إذا قيّم ei إلى vi لكل i في 1..n، فإن [e1; ...; en] يقيّم إلى [v1; ...; vn].

بدأ كتابة «يقيّم إلى» في كل قواعد التقييم لدينا تصبح مملة. فلنستحدث ترميزًا أقصر لها. سنكتب e ==> v لنعني أن e يقيّم إلى v. لاحظ أن ==> ليس قطعة من صياغة OCaml، بل هو ترميز نستخدمه في وصفنا للغة، أشبه بالمتغيرات الفوقية. وباستخدام ذلك الترميز، يمكننا إعادة كتابة القاعدتين الأخيرتين أعلاه:

• إذا كان e1 ==> v1، وإذا كان e2 ==> v2، فإن e1 :: e2 ==> v1 :: v2.
• إذا كان ei ==> vi لكل i في 1..n، فإن [e1; ...; en] ==> [v1; ...; vn].

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

يجب أن تكون جميع عناصر القائمة من النوع نفسه. وإذا كان نوع العنصر ذلك هو t، فإن نوع القائمة هو t list. وينبغي أن تقرأ أنواعًا كهذه من اليمين إلى اليسار: فـ t list قائمة من قيم t، وt list list قائمة من قوائم من قيم t، وهكذا. وكلمة list نفسها هنا ليست نوعًا: فلا سبيل إلى بناء قيمة OCaml نوعها list فحسب. بل إن list مُنشئ أنواع (type constructor): فبالنظر إلى نوع، ينتج نوعًا جديدًا. على سبيل المثال، بالنظر إلى int، ينتج النوع int list. ويمكنك التفكير في منشئات الأنواع كأنها دوال تعمل على الأنواع، بدلًا من دوال تعمل على القيم.

وقواعد فحص الأنواع:

• [] : 'a list
• إذا كان e1 : t وكان e2 : t list، فإن e1 :: e2 : t list. وفي حال كانت النقطتان وأسبقيتهما مربكة، فالأخيرة تعني (e1 :: e2) : t list.

في قاعدة []، تذكّر أن 'a متغير نوعي: فهو يشير إلى نوع غير معروف. لذا فالقائمة الفارغة قائمة عناصرها من نوع غير معروف. وإذا أضفنا بـ cons عددًا صحيحًا إليها، مثل 2 :: []، فإن المصرّف يستنتج أن 'a يجب أن تكون int لتلك القائمة بعينها. لكن إذا أضفنا في موضع آخر قيمة منطقية إليها، مثل true :: []، فإن المصرّف يستنتج أن 'a يجب أن تكون bool لتلك القائمة بعينها.

3.1.2. الوصول إلى القوائم

ملاحظة

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

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

وإليك مثالًا على استخدام التطابق النمطي لحساب مجموع قائمة:

let rec sum lst =
  match lst with
  | [] -> 0
  | h :: t -> h + sum t

val sum : int list -> int = <fun>

تقول هذه الدالة خذ المدخل lst وانظر إن كان له الشكل نفسه الذي للقائمة الفارغة. فإن كان كذلك، أعد 0. وإلا، إن كان له الشكل نفسه الذي للقائمة h :: t، فلتكن h العنصر الأول من lst، ولتكن t بقية عناصر lst، ثم أعد h + sum t. والغرض من اختيار أسماء المتغيرات هنا هو الإيحاء بكلمتي «head» و«tail»، وهو أسلوب اصطلاحي شائع، لكننا نستطيع استخدام أسماء أخرى إن أردنا. ومن الأساليب الاصطلاحية الشائعة الأخرى:

let rec sum xs =
  match xs with
  | [] -> 0
  | x :: xs' -> x + sum xs'

val sum : int list -> int = <fun>

أي أن قائمة المدخل قائمة من قيم xs (وتُلفظ EX-uhs)، وعنصر الرأس هو x، والذيل هو xs’ (وتُلفظ EX-uhs prime).

ومن الناحية الصياغية لا يلزم استخدام هذا العدد من الأسطر لتعريف sum. يمكننا فعل ذلك كله في سطر واحد:

let rec sum xs = match xs with | [] -> 0 | x :: xs' -> x + sum xs'

val sum : int list -> int = <fun>

أو، مع ملاحظة أن أول | بعد with اختيارية بغض النظر عن عدد الأسطر التي نستخدمها، يمكننا أيضًا كتابة:

let rec sum xs = match xs with [] -> 0 | x :: xs' -> x + sum xs'

val sum : int list -> int = <fun>

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

وإليك مثالًا آخر على استخدام التطابق النمطي لحساب طول قائمة:

let rec length lst =
  match lst with
  | [] -> 0
  | h :: t -> 1 + length t

val length : 'a list -> int = <fun>

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

let rec length lst =
  match lst with
  | [] -> 0
  | _ :: t -> 1 + length t

val length : 'a list -> int = <fun>

وهذه الدالة مدمجة فعليًا في وحدة List بالمكتبة القياسية لـ OCaml. واسمها هناك List.length. ويشير ترميز «النقطة» ذلك إلى الدالة المسماة length داخل الوحدة المسماة List، على غرار ترميز النقطة المستخدم في لغات أخرى كثيرة.

وإليك مثالًا ثالثًا يلحق قائمة بمقدمة قائمة أخرى:

let rec append lst1 lst2 =
  match lst1 with
  | [] -> lst2
  | h :: t -> h :: append t lst2

val append : 'a list -> 'a list -> 'a list = <fun>

على سبيل المثال، append [1; 2] [3; 4] هي [1; 2; 3; 4]. وتتوفر هذه الدالة فعليًا كمؤثر مدمج @، لذا يمكننا بدلًا من ذلك كتابة [1; 2] @ [3; 4].

وكمثال أخير، يمكننا كتابة دالة لتحديد ما إذا كانت قائمة فارغة:

let empty lst =
  match lst with
  | [] -> true
  | h :: t -> false

val empty : 'a list -> bool = <fun>

لكن هناك طريقة أفضل بكثير لكتابة الدالة نفسها دون التطابق النمطي:

let empty lst =
  lst = []

val empty : 'a list -> bool = <fun>

لاحظ كيف تشبه جميع الدوال التعاودية أعلاه البرهان بالاستقراء على الأعداد الطبيعية: فكل عدد طبيعي إما أن يكون 0 أو يزيد بمقدار 1 على عدد طبيعي آخر $n$، لذا فبرهان الاستقراء له حالة أساسية عند 0 وحالة استقرائية عند $n + 1$. وبالمثل، لجميع دوالنا حالة أساسية للقائمة الفارغة وحالة تعاودية للقائمة التي تحتوي على عنصر واحد أكثر من قائمة أخرى. وهذا التشابه ليس مصادفة. فهناك علاقة عميقة بين الاستقراء والتعاود؛ وسنستكشف تلك العلاقة بمزيد من التفصيل لاحقًا في الكتاب.

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

3.1.3. (عدم) تغيير القوائم

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

let inc_first lst =
  match lst with
  | [] -> []
  | h :: t -> h + 1 :: t

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

1. نسخ قائمة الذيل t بالكامل عند إنشاء القائمة الجديدة في التطابق النمطي مع cons، بحيث تزيد كمية الذاكرة المستخدمة بمقدار يتناسب مع طول t.
2. مشاركة قائمة الذيل t بين القائمة القديمة والقائمة الجديدة، بحيث لا تزيد كمية الذاكرة المستخدمة — بما يتجاوز قطعة الذاكرة الإضافية الواحدة اللازمة لتخزين h + 1.

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

3.1.4. التطابق النمطي مع القوائم

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

الصياغة.

match e with
| p1 -> e1
| p2 -> e2
| ...
| pn -> en

تُسمى كل جملة من الجمل pi -> ei فرعًا (branch) أو حالة (case) من التطابق النمطي. وأول شريط عمودي في التطابق النمطي كله اختياري.

الحروف p هنا صيغة صياغية جديدة تسمى نمطًا (pattern). وفي الوقت الحالي، يمكن أن يكون النمط:

• اسم متغير، مثل x
• محرف الشرطة السفلية _، ويسمى محرف البدل (wildcard)
• القائمة الفارغة []
• p1 :: p2
• [p1; ...; pn]

ولا يجوز أن يظهر أي اسم متغير أكثر من مرة في النمط. على سبيل المثال، النمط x :: x غير قانوني. أما محرف البدل فيمكن أن يظهر أي عدد من المرات.

وكلما تعلمنا المزيد من بنى البيانات المتاحة في OCaml، وسّعنا الاحتمالات لما يمكن أن يكون عليه النمط.

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

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

match 1 :: [] with
| [] -> false
| h :: t -> h >= 1 && List.length t = 0

- : bool = true

عند تقييم الجانب الأيمن من الفرع الثاني، تُربط h بـ 1 وتُربط t بـ []. لنكتب h->1 لنعني ارتباط المتغير الذي يقول إن h له القيمة 1؛ وهذا ليس قطعة من صياغة OCaml، بل ترميز نستخدمه للاستدلال على اللغة. لذا ستكون ارتباطات المتغيرات التي ينتجها الفرع الثاني h->1, t->[].

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

• النمط x يطابق أي قيمة v وينتج ارتباط المتغير x->v.
• النمط _ يطابق أي قيمة ولا ينتج أي ارتباطات.
• النمط [] يطابق القيمة [] ولا ينتج أي ارتباطات.
• إذا طابق p1 القيمة v1 وأنتج مجموعة الارتباطات $b_1$، وإذا طابق p2 القيمة v2 وأنتج مجموعة الارتباطات $b_2$، فإن p1 :: p2 يطابق v1 :: v2 وينتج مجموعة الارتباطات $b_1 \cup b_2$. لاحظ أن v2 يجب أن تكون قائمة (لأنها على الجانب الأيمن من ::) ويمكن أن يكون لها أي طول: 0 عنصر أو عنصر واحد أو عناصر كثيرة. ولاحظ أن اتحاد الارتباطات $b_1 \cup b_2$ لن يواجه أبدًا مشكلة ربط المتغير نفسه منفصلًا في كل من $b_1$ و$b_2$ بسبب القيد الصياغي القائل بأنه لا يجوز أن يظهر أي اسم متغير أكثر من مرة في النمط.
• إذا صحّ، لكل i في 1..n، أن pi يطابق vi وينتج مجموعة الارتباطات $b_i$، فإن [p1; ...; pn] يطابق [v1; ...; vn] وينتج مجموعة الارتباطات $\bigcup_i b_i$. لاحظ أن هذا النمط يحدد الطول الدقيق الذي يجب أن تكون عليه القائمة.

والآن يمكننا أن نقول كيف يقيّم match e with p1 -> e1 | ... | pn -> en:

• قيّم e إلى قيمة v.
• حاول مطابقة v مع p1، ثم مع p2، وهكذا، بالترتيب الذي تظهر به في تعبير match.
• إذا لم تطابق v أيًا من الأنماط، فإن تقييم تعبير match يطلق استثناء Match_failure. ولم نتحدث بعد عن الاستثناءات في OCaml، لكنك بالتأكيد تعرفها من لغات أخرى. وسنعود إلى الاستثناءات قرب نهاية هذا الفصل، بعد أن نغطي بعض بنى البيانات المدمجة الأخرى في OCaml.
• وإلا، فلتكن pi أول نمط يطابق، ولتكن $b$ ارتباطات المتغيرات الناتجة عن مطابقة v مع pi.
• عوّض بتلك الارتباطات $b$ داخل ei، فينتج تعبير جديد e'.
• قيّم e' إلى قيمة v'.
• نتيجة تعبير match كله هي v'.

على سبيل المثال، هكذا سيقيّم تعبير match هذا:

match 1 :: [] with
| [] -> false
| h :: t -> h = 1 && t = []

- : bool = true

• 1 :: [] قيمة بالفعل.
• [] لا يطابق 1 :: [].
• h :: t يطابق 1 :: [] وينتج ارتباطات المتغيرات {h->1,t->[]}، لأن: h يطابق 1 وينتج ارتباط المتغير h->1.
• t يطابق [] وينتج ارتباط المتغير t->[].

وبتعويض {h->1,t->[]} داخل h = 1 && t = [] ينتج تعبير جديد هو 1 = 1 && [] = [].

ويُنتج تقييم 1 = 1 && [] = [] القيمة true. ونحذف هنا تبرير تلك الحقيقة، لكنها تتبع من قواعد تقييم أخرى للمؤثرات المدمجة وتطبيق الدوال.

لذا فنتيجة تعبير match كله هي true.

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

• إذا كان e : ta، ولكل i صحّ أن pi : ta وei : tb، فإن (match e with p1 -> e1 | ... | pn -> en) : tb.

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

فحوص ساكنة إضافية.

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

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

let head lst = match lst with h :: _ -> h

File "[12]", line 1, characters 15-41:

1 | let head lst = match lst with h :: _ -> h

                   ^^^^^^^^^^^^^^^^^^^^^^^^^^

Warning 8 [partial-match]: this pattern-matching is not exhaustive.

Here is an example of a case that is not matched:

[]

val head : 'a list -> 'a = <fun>

وبعرض ذلك التحذير على المبرمج، يساعد المصرّف المبرمج على الدفاع ضد احتمال استثناءات Match_failure في وقت التشغيل.

ملاحظة

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

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

let rec sum lst =
  match lst with
  | h :: t -> h + sum t
  | [ h ] -> h
  | [] -> 0

File "[13]", line 4, characters 4-9:

4 |   | [ h ] -> h

        ^^^^^

Warning 11 [redundant-case]: this match case is unused.

val sum : int list -> int = <fun>

الفرع الثاني غير مستخدم لأن الفرع الأول سيطابق أي شيء يطابقه الفرع الثاني.

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

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

let length_is lst n =
  match List.length lst with
  | n -> true
  | _ -> false

File "[14]", line 4, characters 4-5:

4 |   | _ -> false

        ^

Warning 11 [redundant-case]: this match case is unused.

val length_is : 'a list -> 'b -> bool = <fun>

كان المبرمج يظن أنه إذا كان طول lst مساويًا لـ n، فستعيد هذه الدالة true، وإلا فستعيد false. لكن هذه الدالة في الواقع تعيد دائمًا true. لماذا؟ لأن متغير النمط n مختلف عن وسيط الدالة n. افترض أن طول lst هو 5. عندئذ يصبح التطابق النمطي: match 5 with n -> true | _ -> false. فهل يطابق n القيمة 5؟ نعم، وفقًا للقواعد أعلاه: نمط المتغير يطابق أي قيمة وينتج هنا الارتباط n->5. ثم يطبّق التقييم ذلك الارتباط على true، فيعوّض كل مواضع ظهور n داخل true بالقيمة 5. حسنًا، لا توجد مواضع ظهور كهذه. لذا انتهينا، ونتيجة التقييم هي true فحسب.

وما كان المبرمج يعني كتابته حقًا هو:

let length_is lst n =
  match List.length lst with
  | m -> m = n

val length_is : 'a list -> int -> bool = <fun>

أو الأفضل من ذلك:

let length_is lst n =
  List.length lst = n

val length_is : 'a list -> int -> bool = <fun>

3.1.5. التطابق النمطي العميق

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

• _ :: [] يطابق جميع القوائم ذات العنصر الواحد بالضبط
• _ :: _ يطابق جميع القوائم ذات العنصر الواحد على الأقل
• _ :: _ :: [] يطابق جميع القوائم ذات العنصرين بالضبط
• _ :: _ :: _ :: _ يطابق جميع القوائم ذات الثلاثة عناصر على الأقل

3.1.6. المطابقات المباشرة

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

let rec sum lst =
  match lst with
  | [] -> 0
  | h :: t -> h + sum t

val sum : int list -> int = <fun>

يمكنك كتابة

let rec sum = function
  | [] -> 0
  | h :: t -> h + sum t

val sum : int list -> int = <fun>

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

3.1.7. OCamldoc وصياغة القوائم

OCamldoc مولّد توثيق شبيه بـ Javadoc. فهو يستخرج التعليقات من شيفرة المصادر وينتج HTML (وصيغ إخراج أخرى أيضًا). وتوثيق المكتبة القياسية على الويب لوحدة List مولّد بواسطة OCamldoc من شيفرة مصادر المكتبة القياسية لتلك الوحدة، على سبيل المثال.

تحذير

هناك عرف صياغي مع الأقواس المعقوفة في OCamldoc يمكن أن يكون مربكًا فيما يتعلق بالقوائم.

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

على سبيل المثال، إليك التعليق الخاص بـ List.hd في شيفرة مصادر المكتبة القياسية:

(** Return the first element of the given list. Raise
   [Failure "hd"] if the list is empty. *)

لا تعني [Failure "hd"] قائمة تحتوي على الاستثناء Failure "hd". بل تعني تنضيد التعبير Failure "hd" كشيفرة مصدرية، كما يمكنك أن ترى هنا.

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

(** [hd lst] returns the first element of [lst].
    Raises [Failure "hd"] if [lst = []]. *)

في [lst = []]، تشير الأقواس المعقوفة الخارجية إلى شيفرة مصدرية كجزء من تعليق، بينما تشير الأقواس المعقوفة الداخلية إلى القائمة الفارغة.

3.1.8. استيعابات القوائم

في بعض اللغات، ومنها Python وHaskell، صياغة تسمى الاستيعاب (comprehension) تتيح كتابة القوائم على نحو يشبه استيعابات المجموعات في الرياضيات. ويبدو أن أقدم مثال على الاستيعابات هو اللغة الوظيفية NPL، التي صُممت في عام 1977.

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

3.1.9. التعاود الذيلي

تذكّر أن الدالة تعاودية ذيلية إذا استدعت نفسها تعاوديًا لكنها لا تجري أي حساب بعد عودة النداء التعاودي، وتعيد فورًا إلى مستدعيها قيمة ندائها التعاودي. انظر إلى هذين التنفيذين، sum وsum_tr، لحساب مجموع قائمة:

let rec sum (l : int list) : int =
  match l with
  | [] -> 0
  | x :: xs -> x + (sum xs)
let rec sum_plus_acc (acc : int) (l : int list) : int =
  match l with
  | [] -> acc
  | x :: xs -> sum_plus_acc (acc + x) xs
let sum_tr : int list -> int =
  sum_plus_acc 0

val sum : int list -> int = <fun>

val sum_plus_acc : int -> int list -> int = <fun>

val sum_tr : int list -> int = <fun>

لاحظ الفرق التالي بين الدالتين sum وsum_tr أعلاه: في الدالة sum، وهي غير تعاودية ذيلية، نضيف x إلى قيمة النداء التعاودي بعد أن يعيدها. أما في sum_tr التعاودية الذيلية، أو بالأحرى في sum_plus_acc، فبعد عودة النداء التعاودي نعيد القيمة فورًا دون حساب إضافي.

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

لكن هذا لا يعني أن التنفيذ التعاودي الذيلية أفضل تمامًا. على سبيل المثال، قد تكون الدالة التعاودية الذيلية أصعب في القراءة. (انظر إلى sum_plus_acc.) كما أن هناك حالات يستلزم فيها تنفيذ دالة تعاودية ذيلية إجراء مرور معالجة مسبقة أو لاحقة لعكس القائمة. وعلى القوائم الصغيرة والمتوسطة الحجم، يمكن أن تجعل كلفة عكس القائمة (سواء من حيث الوقت أو من حيث تخصيص ذاكرة للقائمة المعكوسة) النسخة التعاودية الذيلية أقل كفاءة زمنيًا. وما الذي يعدّ «صغيرًا» مقابل «كبيرًا» هنا؟ يصعب تحديد ذلك، لكن ربما يكون 10,000 تقديرًا جيدًا، وفقًا لـ توثيق المكتبة القياسية لوحدة List.

وإليك دالة تعاودية ذيلية مفيدة لإنتاج قائمة طويلة:

(** [from i j l] is the list containing the integers from [i] to [j],
    inclusive, followed by the list [l].
    Example:  [from 1 3 [0] = [1; 2; 3; 0]] *)
let rec from i j l = if i > j then l else from i (j - 1) (j :: l)
(** [i -- j] is the list containing the integers from [i] to [j], inclusive. *)
let ( -- ) i j = from i j []
let long_list = 0 -- 1_000_000

val from : int -> int -> int list -> int list = <fun>

val ( -- ) : int -> int -> int list = <fun>

val long_list : int list =
  [0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20;
   21; 22; 23; 24; 25; 26; 27; 28; 29; 30; 31; 32; 33; 34; 35; 36; 37; 38;
   39; 40; 41; 42; 43; 44; 45; 46; 47; 48; 49; 50; 51; 52; 53; 54; 55; 56;
   57; 58; 59; 60; 61; 62; 63; 64; 65; 66; 67; 68; 69; 70; 71; 72; 73; 74;
   75; 76; 77; 78; 79; 80; 81; 82; 83; 84; 85; 86; 87; 88; 89; 90; 91; 92;
   93; 94; 95; 96; 97; 98; 99; 100; 101; 102; 103; 104; 105; 106; 107; 108;
   109; 110; 111; 112; 113; 114; 115; 116; 117; 118; 119; 120; 121; 122; 123;
   124; 125; 126; 127; 128; 129; 130; 131; 132; 133; 134; 135; 136; 137; 138;
   139; 140; 141; 142; 143; 144; 145; 146; 147; 148; 149; 150; 151; 152; 153;
   154; 155; 156; 157; 158; 159; 160; 161; 162; 163; 164; 165; 166; 167; 168;
   169; 170; 171; 172; 173; 174; 175; 176; 177; 178; 179; 180; 181; 182; 183;
   184; 185; 186; 187; 188; 189; 190; 191; 192; 193; 194; 195; 196; 197; 198;
   199; 200; 201; 202; 203; 204; 205; 206; 207; 208; 209; 210; 211; 212; 213;
   214; 215; 216; 217; 218; 219; 220; 221; 222; 223; 224; 225; 226; 227; 228;
   229; 230; 231; 232; 233; 234; 235; 236; 237; 238; 239; 240; 241; 242; 243;
   244; 245; 246; 247; 248; 249; 250; 251; 252; 253; 254; 255; 256; 257; 258;
   259; 260; 261; 262; 263; 264; 265; 266; 267; 268; 269; 270; 271; 272; 273;
   274; 275; 276; 277; 278; 279; 280; 281; 282; 283; 284; 285; 286; 287; 288;
   289; 290; 291; 292; 293; 294; 295; 296; 297; 298; ...]

وسيجدر بك دراسة تعريف -- لتقنع نفسك بأنك تفهم (i) كيف يعمل و(ii) لماذا هو تعاودي ذيلي.

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

List.init 1_000_000 Fun.id

- : int list =
[0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20;
 21; 22; 23; 24; 25; 26; 27; 28; 29; 30; 31; 32; 33; 34; 35; 36; 37; 38; 39;
 40; 41; 42; 43; 44; 45; 46; 47; 48; 49; 50; 51; 52; 53; 54; 55; 56; 57; 58;
 59; 60; 61; 62; 63; 64; 65; 66; 67; 68; 69; 70; 71; 72; 73; 74; 75; 76; 77;
 78; 79; 80; 81; 82; 83; 84; 85; 86; 87; 88; 89; 90; 91; 92; 93; 94; 95; 96;
 97; 98; 99; 100; 101; 102; 103; 104; 105; 106; 107; 108; 109; 110; 111; 112;
 113; 114; 115; 116; 117; 118; 119; 120; 121; 122; 123; 124; 125; 126; 127;
 128; 129; 130; 131; 132; 133; 134; 135; 136; 137; 138; 139; 140; 141; 142;
 143; 144; 145; 146; 147; 148; 149; 150; 151; 152; 153; 154; 155; 156; 157;
 158; 159; 160; 161; 162; 163; 164; 165; 166; 167; 168; 169; 170; 171; 172;
 173; 174; 175; 176; 177; 178; 179; 180; 181; 182; 183; 184; 185; 186; 187;
 188; 189; 190; 191; 192; 193; 194; 195; 196; 197; 198; 199; 200; 201; 202;
 203; 204; 205; 206; 207; 208; 209; 210; 211; 212; 213; 214; 215; 216; 217;
 218; 219; 220; 221; 222; 223; 224; 225; 226; 227; 228; 229; 230; 231; 232;
 233; 234; 235; 236; 237; 238; 239; 240; 241; 242; 243; 244; 245; 246; 247;
 248; 249; 250; 251; 252; 253; 254; 255; 256; 257; 258; 259; 260; 261; 262;
 263; 264; 265; 266; 267; 268; 269; 270; 271; 272; 273; 274; 275; 276; 277;
 278; 279; 280; 281; 282; 283; 284; 285; 286; 287; 288; 289; 290; 291; 292;
 293; 294; 295; 296; 297; 298; ...]

ينشئ التعبير List.init len f القائمة [f 0; f 1; ...; f (len - 1)]، ويفعل ذلك تعاوديًا ذيليًا إذا كانت len أكبر من 10,000. والدالة Fun.id هي ببساطة دالة الهوية fun x -> x.

3.2. الأنواع المتغايرة

النوع المتغاير (variant) هو نوع بيانات يمثل قيمة تكون إحدى عدة احتمالات. وفي أبسط صوره، تشبه الأنواع المتغايرة تعدادات enum في C أو Java:

type day = Sun | Mon | Tue | Wed | Thu | Fri | Sat
let d = Tue

type day = Sun | Mon | Tue | Wed | Thu | Fri | Sat

val d : day = Tue

وتسمى الأسماء الفردية لقيم النوع المتغاير منشئات (constructors) في OCaml. وفي المثال أعلاه، المنشئات هي Sun وMon وغيرها. وهذا استخدام مختلف بعض الشيء لكلمة منشئ عمّا هو في C++ أو Java.

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

let int_of_day d =
  match d with
  | Sun -> 1
  | Mon -> 2
  | Tue -> 3
  | Wed -> 4
  | Thu -> 5
  | Fri -> 6
  | Sat -> 7

val int_of_day : day -> int = <fun>

ولا توجد أي طريقة تلقائية لربط اسم منشئ بعدد int، كما قد تتوقع من لغات ذات تعدادات.

الصياغة.

تعريف نوع متغاير:

type t = C1 | ... | Cn

يجب أن تبدأ أسماء المنشئات بحرف كبير. وتستخدم OCaml ذلك للتمييز بين المنشئات ومعرّفات المتغيرات.

وصياغة كتابة قيمة منشئ هي ببساطة اسمه، مثل C.

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

• المنشئ قيمة بالفعل. فلا يوجد حساب يجب إجراؤه.

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

• إذا كان t نوعًا معرّفًا بـ type t = ... | C | ...، فإن C : t.

3.2.1. النطاق

افترض أن هناك نوعين معرّفين بأسماء منشئات متداخلة، على سبيل المثال،

type t1 = C | D
type t2 = D | E
let x = D

type t1 = C | D

type t2 = D | E

val x : t2 = D

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

type ptype =
  TNormal | TFire | TWater
type peff =
  ENormal | ENotVery | ESuper

type ptype = TNormal | TFire | TWater

type peff = ENormal | ENotVery | ESuper

ولأن «Normal» سيكون طبيعيًا اسم منشئ لكل من نوع البوكيمون وفعالية هجوم البوكيمون، نضيف محرفًا إضافيًا أمام كل اسم منشئ للإشارة إلى ما إذا كان نوعًا أم فعالية.

3.2.2. التطابق النمطي

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

• اسم منشئ C

ونوسّع تعريف متى يطابق نمط قيمةً وينتج ارتباطًا كما يلي:

• النمط C يطابق القيمة C ولا ينتج أي ارتباطات.

ملاحظة

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

3.3. اختبار الوحدات باستخدام OUnit

ملاحظة

هذا القسم انحراف قليل عن دراستنا لأنواع البيانات، لكنه موضع جيد لهذا الانحراف: فنحن نعرف الآن ما يكفي لفهم كيفية إجراء اختبار الوحدات في OCaml، ولا سبب جيد للتأجيل أكثر من ذلك لتعلّمه.

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

تعلمنا الآن ما يكفي من ميزات OCaml لنرى كيفية إجراء اختبار الوحدات باستخدام مكتبة تسمى OUnit. وهي إطار لاختبار الوحدات شبيه بـ JUnit في Java وHUnit في Haskell وغيرهما. وسير العمل الأساسي لاستخدام OUnit هو كما يلي:

• اكتب دالة في ملف f.ml. وقد تكون هناك دوال كثيرة أخرى في ذلك الملف أيضًا.
• اكتب اختبارات وحدة لتلك الدالة في ملف منفصل test.ml. وهذا الاسم تحديدًا ليس جوهريًا في الواقع.
• ابنِ test وشغّله لتنفيذ اختبارات الوحدة.

وتوثيق OUnit متاح على GitHub.

3.3.1. مثال على OUnit

يوضح المثال التالي كيفية إنشاء مجموعة اختبارات OUnit. وهناك بعض الأمور في المثال قد تبدو غامضة في البداية؛ وستُناقش في القسم التالي.

أنشئ دليلًا جديدًا. وفي ذلك الدليل، أنشئ ملفًا باسم sum.ml وضع فيه الشيفرة التالية:

let rec sum = function
  | [] -> 0
  | x :: xs -> x + sum xs

أنشئ الآن ملفًا ثانيًا باسم test.ml وضع فيه هذه الشيفرة:

open OUnit2
open Sum
let tests = "test suite for sum" >::: [
  "empty" >:: (fun _ -> assert_equal 0 (sum []));
  "singleton" >:: (fun _ -> assert_equal 1 (sum [1]));
  "two_elements" >:: (fun _ -> assert_equal 3 (sum [1; 2]));
]
let _ = run_test_tt_main tests

حسب محررك وإعداداته، من المرجح أنك ترى الآن بعض أخطاء «Unbound module» بشأن OUnit2 وSum. لا تقلق؛ فالشيفرة صحيحة فعليًا. كل ما نحتاج إليه هو إعداد dune وإخباره بربط OUnit. أنشئ ملفًا باسم dune وضع فيه ما يلي:

(executable
 (name test)
 (libraries ounit2))

وأنشئ ملف dune-project كما هي العادة:

(lang dune 3.24)

ابنِ الآن مجموعة الاختبارات:

$ dune build test.exe

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

وأخيرًا، يمكنك تشغيل مجموعة الاختبارات:

$ dune exec ./test.exe

وستحصل على رد مثل هذا:

...
Ran: 3 tests in: 0.12 seconds.
OK

افترض الآن أننا عدّلنا sum.ml لإدخال علة بتغيير الشيفرة فيه إلى التالي:

let rec sum = function
  | [] -> 1 (* bug *)
  | x :: xs -> x + sum xs

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

FFF
==============================================================================
Error: test suite for sum:2:two_elements.
File ".../_build/oUnit-test suite for sum-...#01.log", line 9, characters 1-1:
Error: test suite for sum:2:two_elements (in the log).
Raised at OUnitAssert.assert_failure in file "src/lib/ounit2/advanced/oUnitAssert.ml", line 45, characters 2-27
Called from OUnitRunner.run_one_test.(fun) in file "src/lib/ounit2/advanced/oUnitRunner.ml", line 83, characters 13-26
not equal
------------------------------------------------------------------------------

السطر الأول من تلك المخرجات

FFF

يخبرنا أن OUnit شغّل ثلاث حالات اختبار وفشلت الثلاث جميعًا.

والسطر المثير للاهتمام التالي

Error: test suite for sum:2:two_elements.

يخبرنا أن حالة الاختبار ذات الفهرس 2 المسماة two_elements فشلت في مجموعة الاختبارات المسماة test suite for sum. وبقية مخرجات حالة الاختبار تلك ليست مثيرة للاهتمام بشكل خاص؛ فلنتجاهلها الآن.

3.3.2. شرح مثال OUnit

لندرس بعناية أكبر ما فعلناه في القسم السابق. في ملف الاختبار، يجلب open OUnit2 إلى النطاق التعريفات الكثيرة في OUnit2، وهي الإصدار 2 من إطار OUnit. ويجلب open Sum إلى النطاق التعريفات الموجودة في sum.ml. وسنتعلم المزيد عن النطاق والكلمة المفتاحية open لاحقًا في فصل قادم.

ثم أنشأنا قائمة بحالات الاختبار:

[
  "empty"  >:: (fun _ -> assert_equal 0 (sum []));
  "one"    >:: (fun _ -> assert_equal 1 (sum [1]));
  "onetwo" >:: (fun _ -> assert_equal 3 (sum [1; 2]));
]

كل سطر من الشيفرة حالة اختبار منفصلة. ولحالة الاختبار سلسلة نصية تمنحها اسمًا وصفيًا، ودالة تُشغَّل كحالة الاختبار. وبين الاسم والدالة نكتب >::، وهو مؤثر مخصص يعرّفه إطار OUnit. لننظر إلى الدالة الأولى أعلاه:

fun _ -> assert_equal 0 (sum [])

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

ثم أنشأنا مجموعة اختبارات:

let tests = "test suite for sum" >::: [
  "empty" >:: (fun _ -> assert_equal 0 (sum []));
  "singleton" >:: (fun _ -> assert_equal 1 (sum [1]));
  "two_elements" >:: (fun _ -> assert_equal 3 (sum [1; 2]));
]

مؤثر >::: هو مؤثر OUnit مخصص آخر. وهو يقع بين اسم مجموعة الاختبارات وقائمة حالات الاختبار في تلك المجموعة.

ثم شغّلنا مجموعة الاختبارات:

let _ = run_test_tt_main tests

الدالة run_test_tt_main يوفرها OUnit. وهي تشغّل مجموعة اختبارات وتطبع نتائج أي حالات الاختبار نجحت وأيها فشلت إلى المخرجات القياسية. ويشير استخدام let _ = هنا إلى أننا لا نهتم بالقيمة التي تعيدها الدالة؛ فهي تُهمل فحسب.

3.3.3. تحسين مخرجات OUnit

في مثالنا مع التنفيذ المعطوب لـ sum، حصلنا على المخرجات التالية:

==============================================================================
Error: test suite for sum:2:two_elements.
...
not equal
------------------------------------------------------------------------------

تعني عبارة not equal في مخرجات OUnit أن assert_equal اكتشفت أن القيمتين الممرَّرتين إليها في حالة الاختبار تلك غير متساويتين. وهذه ليست معلومات مفيدة كثيرًا: فنحن نريد معرفة سبب عدم تساويهما. وعلى وجه الخصوص، نريد معرفة المخرجة الفعلية التي أنتجتها sum في حالة الاختبار تلك. ولمعرفة ذلك، علينا تمرير وسيط إضافي إلى assert_equal. وينبغي أن تكون تلك الوسيطة، التي تسميتها printer، دالة قادرة على تحويل المخرجات إلى سلاسل نصية. وفي هذه الحالة، المخرجات أعداد صحيحة، لذا تكفي string_of_int من وحدة Stdlib. ونعدّل مجموعة الاختبارات كما يلي:

let tests = "test suite for sum" >::: [
  "empty" >:: (fun _ -> assert_equal 0 (sum []) ~printer:string_of_int);
  "singleton" >:: (fun _ -> assert_equal 1 (sum [1]) ~printer:string_of_int);
  "two_elements" >:: (fun _ -> assert_equal 3 (sum [1; 2]) ~printer:string_of_int);
]

والآن نحصل على مخرجات أكثر إفادة:

==============================================================================
Error: test suite for sum:2:two_elements.
...
expected: 3 but got: 4
------------------------------------------------------------------------------

تعني تلك المخرجات أن الاختبار المسمى two_elements أكد تساوي 3 و4. وكان الناتج المتوقع 3 لأنها كانت المدخل الأول إلى assert_equal، وتقول مواصفة تلك الدالة إنه في assert_equal x y ينبغي أن يكون الناتج الذي تتوقع أنت (كمختبر) الحصول عليه هو x، وأن يكون الناتج الذي تنتجه الدالة المختبرة فعليًا هو y.

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

let make_sum_test name expected_output input =
  name >:: (fun _ -> assert_equal expected_output (sum input) ~printer:string_of_int)
let tests = "test suite for sum" >::: [
  make_sum_test "empty" 0 [];
  make_sum_test "singleton" 1 [1];
  make_sum_test "two_elements" 3 [1; 2];
]

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

3.3.4. اختبار الاستثناءات

بقي علينا تعلّم القليل من OCaml قبل أن نرى كيفية اختبار الاستثناءات. ويمكنك أن تُطلّع مسبقًا على قسم الاستثناءات إن أردت معرفة ذلك الآن.

3.3.5. التطوير القائم على الاختبار

لا يلزم أن يحدث الاختبار بعد كتابة الشيفرة حصرًا. ففي التطوير القائم على الاختبار (test-driven development, TDD)، يأتي الاختبار أولًا! وهو يؤكد على التطوير التدريجي للشيفرة: فهناك دائمًا شيء يمكن اختباره. فالاختبار ليس شيئًا يحدث بعد التنفيذ؛ بل يُستخدم الاختبار المستمر لاكتشاف الأخطاء مبكرًا. ومن ثم، من المهم تطوير اختبارات الوحدة فور كتابة الشيفرة. وأتمتة مجموعات الاختبارات أمر جوهري بحيث لا يتطلب الاختبار المستمر أي جهد تقريبًا.

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

type day = Sunday | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday

ونريد كتابة دالة next_weekday : day -> day تعيد يوم العمل التالي بعد يوم معيّن. نبدأ بكتابة أبسط نسخة معطوبة من تلك الدالة يمكننا كتابتها:

let next_weekday d = failwith "Unimplemented"

ملاحظة

تطلق الدالة المدمجة failwith استثناءً مع رسالة الخطأ الممرَّرة إلى الدالة.

ثم نكتب أبسط اختبار وحدة يمكننا تخيله. على سبيل المثال، نعلم أن يوم العمل التالي بعد Monday هو Tuesday. لذا نضيف اختبارًا:

let tests = "test suite for next_weekday" >::: [
  "tue_after_mon"  >:: (fun _ -> assert_equal Tuesday (next_weekday Monday));
]

ثم نشغّل مجموعة اختبارات OUnit. فتفشل، كما هو متوقع. وهذا جيد! فأصبح لدينا الآن هدف ملموس هو جعل اختبار الوحدة ذلك ينجح. ونعدّل next_weekday لتحقيق ذلك:

let next_weekday d =
  match d with
  | Monday -> Tuesday
  | _ -> failwith "Unimplemented"

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

let tests = "test suite for next_weekday" >::: [
  "tue_after_mon"  >:: (fun _ -> assert_equal Tuesday (next_weekday Monday));
  "wed_after_tue"  >:: (fun _ -> assert_equal Wednesday (next_weekday Tuesday));
  "thu_after_wed"  >:: (fun _ -> assert_equal Thursday(next_weekday Wednesday));
  "fri_after_thu"  >:: (fun _ -> assert_equal Friday (next_weekday Thursday));
]

نصرّف الشيفرة ونشغّل الاختبارات، فيفشل كثير منها. وهذا جيد! فنضيف وظائف جديدة:

  let next_weekday d =
    match d with
    | Monday -> Tuesday
    | Tuesday -> Wednesday
    | Wednesday -> Thursday
    | Thursday -> Friday
    | _ -> failwith "Unimplemented"

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

لنستخلص دالة تنشئ حالات اختبار لـ next_weekday:

let make_next_weekday_test name expected_output input =
  name >:: (fun _ -> assert_equal expected_output (next_weekday input))
let tests = "test suite for next_weekday" >::: [
  make_next_weekday_test "tue_after_mon" Tuesday Monday;
  make_next_weekday_test "wed_after_tue" Wednesday Tuesday;
  make_next_weekday_test "thu_after_wed" Thursday Wednesday;
  make_next_weekday_test "fri_after_thu" Friday Thursday;
]

نُنهي الآن الاختبار والتنفيذ بمعالجة عطلات نهاية الأسبوع. أولًا نضيف بعض حالات الاختبار:

  ...
  make_next_weekday_test "mon_after_fri" Monday Friday;
  make_next_weekday_test "mon_after_sat" Monday Saturday;
  make_next_weekday_test "mon_after_sun" Monday Sunday;
  ...

ثم نُنهي الدالة:

let next_weekday d =
  match d with
  | Monday -> Tuesday
  | Tuesday -> Wednesday
  | Wednesday -> Thursday
  | Thursday -> Friday
  | Friday -> Monday
  | Saturday -> Monday
  | Sunday -> Monday

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

العملية. لنراجع عملية التطوير القائم على الاختبار:

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

3.4. السجلات والأزواج المرتبة

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

3.4.1. السجلات

السجل (record) تركيب من أنواع أخرى من البيانات، كل منها مسمّى. وسجلات OCaml تشبه كثيرًا بنى struct في C. وإليك مثالًا على تعريف نوع سجل mon لبوكيمون، بإعادة استخدام تعريف ptype من قسم الأنواع المتغايرة:

type ptype = TNormal | TFire | TWater
type mon = {name : string; hp : int; ptype : ptype}

type ptype = TNormal | TFire | TWater

type mon = { name : string; hp : int; ptype : ptype; }

يعرّف هذا النوع سجلًا بثلاثة حقول (fields) هي name وhp (نقاط الصحة) وptype. كما يُعطى نوع كل من تلك الحقول. لاحظ أن ptype يمكن استخدامها كاسم نوع وكاسم حقل معًا؛ فـفضاء الأسماء (namespace) الخاص بهما متمايز في OCaml.

ولبناء قيمة من نوع سجل، نكتب تعبير سجل يبدو هكذا:

{name = "Charmander"; hp = 39; ptype = TFire}

- : mon = {name = "Charmander"; hp = 39; ptype = TFire}

لذا نكتب في تعريف النوع نقطتين بين اسم الحقل ونوعه، أما في التعبير فكتب علامة يساوي.

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

let c = {name = "Charmander"; hp = 39; ptype = TFire};;
c.hp

val c : mon = {name = "Charmander"; hp = 39; ptype = TFire}

- : int = 39

ومن الممكن أيضًا استخدام التطابق النمطي للوصول إلى حقول السجل:

match c with {name = n; hp = h; ptype = t} -> h

- : int = 39

الحروف n وh وt هنا متغيرات نمطية. وهناك سكر صياغي متاح إذا أردت استخدام الاسم نفسه للحقل والمتغير النمطي معًا:

match c with {name; hp; ptype} -> hp

- : int = 39

هنا النمط {name; hp; ptype} سكر صياغي لـ {name = name; hp = hp; ptype = ptype}. وفي كل من تلك التعبيرات الفرعية، المعرّف الظاهر على الجانب الأيسر من علامة يساوي اسم حقل، والمعرّف الظاهر على الجانب الأيمن متغير نمطي.

الصياغة.

يُكتب تعبير السجل:

{f1 = e1; ...; fn = en}

ترتيب fi=ei داخل تعبير السجل غير مهم. على سبيل المثال، {f = e1; g = e2} مكافئ تمامًا لـ {g = e2; f = e1}.

ويُكتب الوصول إلى حقل:

e.f

حيث يجب أن تكون f معرّفًا لاسم حقل، لا تعبيرًا. وهذا القيد هو نفسه الموجود في أي لغة أخرى ذات ميزات مشابهة — على سبيل المثال أسماء الحقول في Java. وإذا كنت حقًا تريد حساب المعرّف الذي تريد الوصول إليه، فأنت في الواقع تريد بنية بيانات مختلفة: خريطة (map) (وتعرف أيضًا بأسماء كثيرة أخرى: قاموس (dictionary) أو قائمة ترابط (association list) أو جدول تجزئة (hash table) وغيرها، وإن كانت هناك فروق دقيقة يوحي بها كل من تلك المصطلحات.)

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

• إذا صحّ، لكل i في 1..n، أن ei ==> vi، فإن {f1 = e1; ...; fn = en} ==> {f1 = v1; ...; fn = vn}.
• إذا كان e ==> {...; f = v; ...} فإن e.f ==> v.

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

يُكتب نوع السجل:

{f1 : t1; ...; fn : tn}

ترتيب fi:ti داخل نوع السجل غير مهم. على سبيل المثال، {f : t1; g : t2} مكافئ تمامًا لـ {g:t2;f:t1}.

لاحظ أنه يجب تعريف أنواع السجلات قبل استخدامها. وهذا يمكّن OCaml من إجراء استدلال أنواع أفضل مما سيكون ممكنًا لو أمكن استخدام أنواع السجلات دون تعريف.

وقواعد فحص الأنواع هي:

• إذا صحّ، لكل i في 1..n، أن ei : ti، وإذا كان t معرّفًا بأنه {f1 : t1; ...; fn : tn}، فإن {f1 = e1; ...; fn = en} : t. لاحظ أن مجموعة الحقول المقدَّمة في تعبير السجل يجب أن تكون المجموعة الكاملة للحقول المعرّفة كجزء من نوع السجل (لكن انظر أدناه بشأن نسخ السجل).
• إذا كان e : t1، وإذا كان t1 معرّفًا بأنه {...; f : t2; ...}، فإن e.f : t2.

نسخ السجل.

تتوفر أيضًا صياغة أخرى لإنشاء سجل جديد من سجل قديم:

{e with f1 = e1; ...; fn = en}

هذا لا يغيّر السجل القديم. بل ينشئ سجلًا جديدًا بقيم جديدة. ومجموعة الحقول المقدَّمة بعد with لا يلزم أن تكون المجموعة الكاملة للحقول المعرّفة كجزء من نوع السجل. وفي السجل المنسوخ حديثًا، يُنسخ أي حقل لم يُقدَّم كجزء من with من السجل القديم.

نسخ السجل سكر صياغي. وهو مكافئ لكتابة

{ f1 = e1;   ...; fn = en;
  g1 = e.g1; ...; gn = e.gn }

حيث تكون مجموعة gi هي مجموعة جميع حقول نوع السجل ناقص مجموعة fi.

التطابق النمطي.

نضيف صيغة النمط الجديدة التالية إلى قائمة الأنماط القانونية:

• {f1 = p1; ...; fn = pn}

ونوسّع تعريف متى يطابق نمط قيمةً وينتج ارتباطًا كما يلي:

• إذا صحّ، لكل i في 1..n، أن pi يطابق vi وينتج ارتباطات $b_i$، فإن نمط السجل {f1 = p1; ...; fn = pn} يطابق قيمة السجل {f1 = v1; ...; fn = vn; ...} وينتج مجموعة الارتباطات $\bigcup_i b_i$. لاحظ أن قيمة السجل قد تحتوي على حقول أكثر مما يحتوي عليه نمط السجل.

وكسكر صياغي، توفر صيغة أخرى من نمط السجل: {f1; ...; fn}. وهي تُزال سكرها إلى {f1 = f1; ...; fn = fn}.

3.4.2. الأزواج المرتبة

مثل السجلات، الأزواج المرتبة تركيب من أنواع أخرى من البيانات. لكن بدلًا من تسمية المكونات، تُعرّف بموضعها. وإليك بعض الأمثلة على الأزواج المرتبة:

(1, 2, 10)
(true, "Hello")
([1; 2; 3], (0.5, 'X'))

ويسمى الزوج المرتب ذو المكونين زوجًا (pair). ويسمى ذو المكونات الثلاثة ثلاثيًا (triple). وما بعد ذلك، نستخدم عادةً كلمة زوج مرتّب بدلًا من مواصلة مخطط تسمية قائم على الأعداد.

ملاحظة

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

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

match (1, 2, 3) with (x, y, z) -> x + y + z

- : int = 6

الصياغة.

يُكتب الزوج المرتب

(e1, e2, ..., en)

الأقواس ليست إلزامية تمامًا — فغالبًا ما يمكن لشيفرتك أن تُحلَّل بنجاح دونها — لكن اعتبارها من الأسلوب الجيد عمومًا أمر معتاد.

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

• إذا صحّ، لكل i في 1..n، أن ei ==> vi، فإن (e1, ..., en) ==> (v1, ..., vn).

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

تُكتب أنواع الأزواج المرتبة باستخدام مُنشئ أنواع جديد هو *، وهو مختلف عن مؤثر الضرب. والنوع t1 * ... * tn هو نوع الأزواج المرتبة التي مكونها الأول من النوع t1، و…، ومكونها رقم n من النوع tn.

• إذا صحّ، لكل i في 1..n، أن ei : ti، فإن (e1, ..., en) : t1 * ... * tn.

التطابق النمطي.

نضيف صيغة النمط الجديدة التالية إلى قائمة الأنماط القانونية:

• (p1, ..., pn)

والأقواس هنا أيضًا ليست إلزامية تمامًا، لكن تضمينها اصطلاحي عادةً.

ونوسّع تعريف متى يطابق نمط قيمةً وينتج ارتباطًا كما يلي:

• إذا صحّ، لكل i في 1..n، أن pi يطابق vi وينتج ارتباطات $b_i$، فإن نمط الزوج المرتب (p1, ..., pn) يطابق قيمة الزوج المرتب (v1, ..., vn) وينتج مجموعة الارتباطات $\bigcup_i b_i$. لاحظ أن قيمة الزوج المرتب يجب أن يكون لها العدد نفسه بالضبط من المكونات التي لنمط الزوج المرتب.

3.4.3. الأنواع المتغايرة مقابل الأزواج المرتبة والسجلات

ملاحظة

يستخدم الفيديو الثاني أعلاه أمثلة أكثر تقدمًا على الأنواع المتغايرة ستُدرس في قسم لاحق.

الفرق الكبير بين الأنواع المتغايرة والأنواع التي تعلمناها للتو (السجلات والأزواج المرتبة) هو أن قيمة النوع المتغاير واحدة من مجموعة احتمالات، بينما توفر قيمة الزوج المرتب أو السجل كلًا من مجموعة احتمالات. وبالعودة إلى أمثلتنا، فقيمة من النوع day هي واحدة من Sun أو Mon أو غيرها. لكن قيمة من النوع mon توفر كلًا من string وint وptype. ولاحظ كيف ترتبط كلمة «or» (أو) في الجملتين السابقتين بالأنواع المتغايرة، بينما ترتبط كلمة «and» (و) بأنواع الأزواج المرتبة والسجلات. وذلك دليل جيد إن حاولت يومًا أن تقرر ما إذا كنت تريد استخدام نوع متغاير أم زوجًا مرتبًا أو سجلًا: فإن احتجت إلى قطعة بيانات أو أخرى، فأنت تريد نوعًا متغايرًا؛ وإن احتجت إلى قطعة بيانات و أخرى، فأنت تريد زوجًا مرتبًا أو سجلًا.

وتُعرف الأنواع واحد-من باسم أنواع المجموع (sum types)، والأنواع كل-من باسم أنواع الجداء (product types). وهذان الاسمان قادمان من نظرية المجموعات. فالأنواع المتغايرة تشبه الاتحاد المنفصل، لأن كل قيمة من قيم النوع المتغاير تأتي من واحدة من مجموعات أساسية كثيرة (وبعد، كل من تلك المجموعات هو مجرد منشئ واحد، ولهذا فإن عدد عناصره واحد). والاتحاد المنفصل يُكتب فعلًا أحيانًا بمؤثر جمع هو $\Sigma$. أما الأزواج المرتبة والسجلات فتشبه الجداء الديكارتي، لأن كل قيمة من قيم الزوج المرتب أو السجل تحتوي على قيمة من كل من مجموعات أساسية كثيرة. ويُكتب الجداء الديكارتي عادةً بمؤثر جداء، هو $\times$ أو $\Pi$.

3.5. التطابق النمطي المتقدم

وإليك بعض صيغ الأنماط الإضافية المفيدة:

• p1 | ... | pn: نمط «أو»؛ وينجح التطابق معه إذا نجح التطابق مع أي من الأنماط الفردية pi، التي تُجرَّب بالترتيب من اليسار إلى اليمين. ويجب أن تربط جميع الأنماط المتغيرات نفسها.
• (p : t): نمط مع تعليق نوعي صريح.
• c: هنا تعني c أي ثابت، مثل القيم الحرفية للأعداد الصحيحة والسلاسل النصية والقيم المنطقية.
• 'ch1'..'ch2': هنا يعني ch قيمة حرفية لمحرف. على سبيل المثال، يطابق 'A'..'Z' أي حرف كبير.
• p when e: يطابق p لكن فقط إذا قيّم e إلى true.

ويمكنك القراءة عن جميع صيغ الأنماط في الدليل.

3.5.1. التطابق النمطي مع let

الصياغة التي كنا نستخدمها حتى الآن لتعبيرات let هي في الواقع حالة خاصة من الصياغة الكاملة التي تسمح بها OCaml. وتلك الصياغة هي:

let p = e1 in e2

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

وبالنظر إلى هذه الصياغة، نعيد النظر في دلالات تعبيرات let.

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

لتقييم let p = e1 in e2:

1. قيّم e1 إلى قيمة v1.
2. طابق v1 مع النمط p. فإن لم يطابقه، أطلق الاستثناء Match_failure. وإلا، إن طابقه، فسوف ينتج مجموعة $b$ من الارتباطات.
3. عوّض بتلك الارتباطات $b$ في e2، فينتج تعبير جديد e2'.
4. قيّم e2' إلى قيمة v2.
5. نتيجة تقييم تعبير let هي v2.

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

• إذا صحّ كل ما يلي فإن (let p = e1 in e2) : t2: e1 : t1
• المتغيرات النمطية في p هي x1..xn
• e2 : t2 بافتراض أنه لكل i في 1..n يصحّ أن xi : ti،

تعريفات let.

كما سبق، يمكن فهم تعريف let على أنه تعبير let لم يُعطَ جسمه بعد. لذا يمكن تعميم صياغتها إلى

let p = e

وتتبع دلالاتها دلالات تعبيرات let، كما سبق.

3.5.2. التطابق النمطي مع الدوال

الصياغة التي كنا نستخدمها حتى الآن للدوال هي أيضًا حالة خاصة من الصياغة الكاملة التي تسمح بها OCaml. وتلك الصياغة هي:

let f p1 ... pn = e1 in e2   (* function as part of let expression *)
let f p1 ... pn = e          (* function definition at toplevel *)
fun p1 ... pn -> e           (* anonymous function *)

الصيغة الصياغية البدائية حقًا التي نحتاج إلى الاهتمام بها هي fun p -> e. ولنعد النظر في دلالات الدوال المجهولة وتطبيقها مع هذه الصيغة؛ والتغييرات في الصيغ الأخرى تتبع ما يلي:

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

• لتكن x1..xn المتغيرات النمطية الظاهرة في p. فإذا أمكننا، بافتراض أن x1 : t1 وx2 : t2 و… وxn : tn، أن نستنتج أن p : t وأن e : u، فإن fun p -> e : t -> u.
• قاعدة فحص الأنواع الخاصة بالتطبيق دون تغيير.

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

• قاعدة تقييم الدوال المجهولة دون تغيير.
• لتقييم e0 e1: قيّم e0 إلى دالة مجهولة fun p -> e، وقيّم e1 إلى قيمة v1.
• طابق v1 مع النمط p. فإن لم يطابقه، أطلق الاستثناء Match_failure. وإلا، إن طابقه، فسوف ينتج مجموعة $b$ من الارتباطات.
• عوّض بتلك الارتباطات $b$ في e، فينتج تعبير جديد e'.
• قيّم e' إلى قيمة v، وهي نتيجة تقييم e0 e1.

3.5.3. أمثلة على التطابق النمطي

وإليك عدة طرق للحصول على نقاط صحة بوكيمون:

(* Pokemon types *)
type ptype = TNormal | TFire | TWater
(* A record to represent Pokemon *)
type mon = { name : string; hp : int; ptype : ptype }
(* OK *)
let get_hp m = match m with { name = n; hp = h; ptype = t } -> h
(* better *)
let get_hp m = match m with { name = _; hp = h; ptype = _ } -> h
(* better *)
let get_hp m = match m with { name; hp; ptype } -> hp
(* better *)
let get_hp m = match m with { hp; _ } -> hp
(* best *)
let get_hp m = m.hp

type ptype = TNormal | TFire | TWater

type mon = { name : string; hp : int; ptype : ptype; }

val get_hp : mon -> int = <fun>

val get_hp : mon -> int = <fun>

val get_hp : mon -> int = <fun>

val get_hp : mon -> int = <fun>

val get_hp : mon -> int = <fun>

وإليك كيفية الحصول على المكونين الأول والثاني من زوج:

let fst (x, _) = x
let snd (_, y) = y

val fst : 'a * 'b -> 'a = <fun>

val snd : 'a * 'b -> 'b = <fun>

والدالتان fst وsnd معرّفتان فعلًا لك مسبقًا في المكتبة القياسية.

وأخيرًا، إليك عدة طرق للحصول على المكون الثالث من ثلاثي:

(* OK *)
let thrd t = match t with x, y, z -> z
(* good *)
let thrd t =
  let x, y, z = t in
  z
(* better *)
let thrd t =
  let _, _, z = t in
  z
(* best *)
let thrd (_, _, z) = z

val thrd : 'a * 'b * 'c -> 'c = <fun>

val thrd : 'a * 'b * 'c -> 'c = <fun>

val thrd : 'a * 'b * 'c -> 'c = <fun>

val thrd : 'a * 'b * 'c -> 'c = <fun>

ولا تعرّف المكتبة القياسية أي دوال للثلاثيات والرباعيات وغيرها.

3.6. المرادفات النوعية

المرادف النوعي (type synonym) اسم جديد لنوع موجود بالفعل. على سبيل المثال، إليك بعض المرادفات النوعية التي قد تكون مفيدة في تمثيل بعض الأنواع من الجبر الخطي:

type point = float * float
type vector = float list
type matrix = float list list

type point = float * float

type vector = float list

type matrix = float list list

في أي موضع يُتوقع فيه float * float، يمكنك استخدام point، والعكس صحيح. فالنوعان قابلان للتبادل تمامًا بينهما. وفي الشيفرة التالية، لا تهتم get_x بما إذا مررت إليها قيمة معلّقة بأحد النوعين أم بالآخر:

let get_x = fun (x, _) -> x
let p1 : point = (1., 2.)
let p2 : float * float = (1., 3.)
let a = get_x p1
let b = get_x p2

val get_x : 'a * 'b -> 'a = <fun>

val p1 : point = (1., 2.)

val p2 : float * float = (1., 3.)

val a : float = 1.

val b : float = 1.

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

3.7. الخيارات

افترض أنك تريد كتابة دالة تعيد عادةً قيمة من النوع t، لكنها تعيد أحيانًا لا شيء. على سبيل المثال، قد تريد تعريف دالة list_max تعيد القيمة العظمى في قائمة، لكن لا يوجد شيء معقول تعيده على قائمة فارغة:

let rec list_max = function
  | [] -> ???
  | h :: t -> max h (list_max t)

وهناك احتمالان يمكن التفكير فيهما:

• أن تعيد min_int؟ لكن list_max عندئذ لن تعمل إلا مع الأعداد الصحيحة — لا مع أعداد الفاصلة العائمة أو أنواع أخرى.
• أن تطلق استثناءً؟ لكن مستخدم الدالة عندئذ سيتعين عليه تذكّر التقاط الاستثناء.
• أن تعيد null؟ وهذا ينجح في Java، لكن OCaml لا تملك قيمة null بحكم التصميم. وهذا في الواقع أمر جيد: علل المؤشرات الفارغة ليست ممتعة في التنقيح.

ملاحظة

يسمّي السير توني هور اختراعه لقيمة null «خطأ بمليار دولار».

إضافةً إلى تلك الاحتمالات، توفر OCaml شيئًا أفضل حتى، يسمى الخيار (option). (وسيتعرف مستخدمو Haskell على الخيارات بأنها موناد Maybe.)

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

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

وإليك كيف ننشئ خيارًا كأنه صندوق بداخله 42:

Some 42

- : int option = Some 42

وإليك كيف ننشئ خيارًا كأنه صندوق فارغ:

None

- : 'a option = None

تعني Some أن هناك شيئًا داخل الصندوق، وهو 42. وتعني None أنه لا شيء داخل الصندوق.

ومثل list، نسمي option مُنشئ أنواع: فبالنظر إلى نوع، ينتج نوعًا جديدًا؛ لكنه ليس نوعًا في نفسه. لذا لأي نوع t، يمكننا كتابة t option كنوع. لكن option وحدها لا يمكن استخدامها كنوع. وقد تحتوي قيم النوع t option على قيمة من النوع t، أو قد لا تحتوي على شيء. وNone من النوع 'a option لأنه لا قيد على نوع الشيء الموجود بالداخل — إذ لا يوجد شيء بالداخل.

ويمكنك الوصول إلى محتوى قيمة خيار e باستخدام التطابق النمطي. وإليك دالة تستخرج int من خيار، إن كان هناك واحد بالداخل، وتحوّله إلى سلسلة نصية:

let extract o =
  match o with
  | Some i -> string_of_int i
  | None -> "";;

val extract : int option -> string = <fun>

وإليك مثالين على استخدامات تلك الدالة:

extract (Some 42);;
extract None;;

- : string = "42"

- : string = ""

وإليك كيف يمكننا كتابة list_max باستخدام الخيارات:

let rec list_max = function
  | [] -> None
  | h :: t -> begin
      match list_max t with
        | None -> Some h
        | Some m -> Some (max h m)
      end

val list_max : 'a list -> 'a option = <fun>

ملاحظة

لفّ التطابق النمطي المتداخل أعلاه بـ begin..end ليس مطلوبًا تمامًا هنا لكنه ليس عادة سيئة، لأنه سيمنع أخطاء صياغة محتملة في شيفرة أكثر تعقيدًا. والكلمتان المفتاحيتان begin وend مكافئتان لـ ( و).

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

صياغة الخيارات ودلالاتها.

• t option نوع لكل نوع t.
• None قيمة من النوع 'a option.
• Some e تعبير من النوع t option إذا كان e : t. وإذا كان e ==> v فإن Some e ==> Some v

3.8. قوائم الترابط

الخريطة (map) بنية بيانات تربط مفاتيح (keys) بـقيم (values). وتُعرف الخرائط أيضًا باسم القواميس (dictionaries). ومن التنفيذات السهلة للخريطة قائمة الترابط (association list)، وهي قائمة من الأزواج. وهنا، على سبيل المثال، قائمة ترابط تربط بعض أسماء الأشكال بعدد أضلاعها:

let d = [("rectangle", 4); ("nonagon", 9); ("icosagon", 20)]

val d : (string * int) list =
  [("rectangle", 4); ("nonagon", 9); ("icosagon", 20)]

لاحظ أن قائمة الترابط ليست نوع بيانات مدمجًا في OCaml بقدر ما هي تركيب من نوعين آخرين: القوائم والأزواج.

وإليك دالتين تنفّذان الإدراج والبحث في قائمة ترابط:

(** [insert k v lst] is an association list that binds key [k] to value [v]
    and otherwise is the same as [lst] *)
let insert k v lst = (k, v) :: lst
(** [lookup k lst] is [Some v] if association list [lst] binds key [k] to
    value [v]; and is [None] if [lst] does not bind [k]. *)
let rec lookup k = function
| [] -> None
| (k', v) :: t -> if k = k' then Some v else lookup k t

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

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

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

لذا فالإدراج في قائمة ترابط يستغرق زمنًا ثابتًا، والبحث يستغرق زمنًا خطيًا. ورغم أن هناك بالتأكيد تنفيذات أكثر كفاءة للقواميس — وسندرس بعضها لاحقًا في هذا المقرر — فإن قوائم الترابط تنفيذ سهل ومفيد جدًا للقواميس الصغيرة التي لا يشكّل الأداء فيها أمرًا حرجًا. وللمكتبة القياسية في OCaml دوال لقوائم الترابط في وحدة List؛ ابحث عن List.assoc والدوال التي تليها في التوثيق. وما كتبناه للتو باسم lookup معرّف فعلًا باسم List.assoc_opt. ولا توجد دالة insert معرّفة مسبقًا في المكتبة لأن إضافة زوج في المقدمة بـ cons أمر تافه للغاية.

3.9. أنواع البيانات الجبرية

رأينا حتى الآن الأنواع المتغايرة مجرد تعداد لمجموعة من القيم الثابتة، مثل:

type day = Sun | Mon | Tue | Wed | Thu | Fri | Sat
type ptype = TNormal | TFire | TWater
type peff = ENormal | ENotVery | Esuper

لكن الأنواع المتغايرة أقوى بكثير من ذلك.

3.9.1. أنواع متغايرة تحمل بيانات

وكمثال متكرر، إليك نوع متغاير shape يفعل أكثر من مجرد تعداد القيم:

type point = float * float
type shape =
  | Point of point
  | Circle of point * float (* center and radius *)
  | Rect of point * point (* lower-left and upper-right corners *)

type point = float * float

type shape = Point of point | Circle of point * float | Rect of point * point

هذا النوع، أي shape، يمثل شكلًا يكون إما نقطة أو دائرة أو مستطيلًا. فالنقطة يمثلها منشئ Point يحمل بعض البيانات الإضافية، وهي قيمة من النوع point. والدائرة يمثلها منشئ Circle يحمل قطعتين من البيانات: إحداهما من النوع point والأخرى من النوع float. وتمثل تلك البيانات مركز الدائرة ونصف قطرها. والمستطيل يمثله منشئ Rect يحمل نقطتين إضافيتين.

وإليك دالتين تستخدمان النوع shape:

let area = function
  | Point _ -> 0.0
  | Circle (_, r) -> Float.pi *. (r ** 2.0)
  | Rect ((x1, y1), (x2, y2)) ->
      let w = x2 -. x1 in
      let h = y2 -. y1 in
      w *. h
let center = function
  | Point p -> p
  | Circle (p, _) -> p
  | Rect ((x1, y1), (x2, y2)) -> ((x2 +. x1) /. 2.0, (y2 +. y1) /. 2.0)

val area : shape -> float = <fun>

val center : shape -> point = <fun>

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

وتسمى الأنواع المتغايرة أحيانًا اتحادات موسومة (tagged unions). فكل قيمة من النوع من مجموعة القيم التي هي اتحاد كل القيم من الأنواع الأساسية التي يحملها المنشئ. على سبيل المثال، في النوع shape، كل قيمة موسومة إما بـ Point أو Circle أو Rect وتحمل قيمة من:

• مجموعة جميع قيم point، متحدة مع
• مجموعة جميع قيم point * float، متحدة مع
• مجموعة جميع قيم point * point.

وثمة اسم آخر لهذه الأنواع المتغايرة هو نوع بيانات جبري (algebraic data type). ويشير «الجبر» هنا إلى حقيقة أن الأنواع المتغايرة تحتوي على أنواع مجموع وأنواع جداء معًا، على النحو المعرّف في المحاضرة السابقة. فأنواع المجموع تأتي من أن قيمة النوع المتغاير تتكوّن من واحد من المنشئات. وأنواع الجداء تأتي من أن المنشئ يمكن أن يحمل أزواجًا مرتبة أو سجلات، تحتوي قيمها على قيمة فرعية من كل من أنواع مكوناتها.

وباستخدام الأنواع المتغايرة، يمكننا التعبير عن نوع يمثل اتحاد عدة أنواع أخرى، لكن بطريقة آمنة الأنواع. هنا، على سبيل المثال، نوع يمثل إما string أو int:

type string_or_int =
  | String of string
  | Int of int

type string_or_int = String of string | Int of int

ولو أردنا، لاستطعنا استخدام هذا النوع لبرمجة قوائم (مثلًا) تحتوي إما على سلاسل نصية أو أعداد صحيحة:

type string_or_int_list = string_or_int list
let rec sum : string_or_int list -> int = function
  | [] -> 0
  | String s :: t -> int_of_string s + sum t
  | Int i :: t -> i + sum t
let lst_sum = sum [String "1"; Int 2]

type string_or_int_list = string_or_int list

val sum : string_or_int list -> int = <fun>

val lst_sum : int = 3

وهكذا توفر الأنواع المتغايرة طريقة آمنة الأنواع لفعل شيء ربما بدا مستحيلًا من قبل.

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

type t = Left of int | Right of int
let x = Left 1
let double_right = function
  | Left i -> i
  | Right i -> 2 * i

type t = Left of int | Right of int

val x : t = Left 1

val double_right : t -> int = <fun>

3.9.2. الصياغة والدلالات

الصياغة.

لتعريف نوع متغاير:

type t = C1 [of t1] | ... | Cn [of tn]

تشير الأقواس المعقوفة أعلاه إلى أن of ti اختيارية. ويمكن لكل منشئ على حدة أن يحمل بيانات أو لا يحمل. ونسمي المنشئات التي لا تحمل بيانات ثابتة (constant)؛ وتلك التي تحمل بيانات غير ثابتة (non-constant).

ولكتابة تعبير يكون نوعًا متغايرًا:

C e

أو:

C

حسب ما إذا كان اسم المنشئ C غير ثابت أم ثابتًا.

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

• إذا كان e ==> v فإن C e ==> C v، بافتراض أن C غير ثابت.
• C قيمة بالفعل، بافتراض أن C ثابت.

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

• إذا كان t = ... | C | ... فإن C : t.
• إذا كان t = ... | C of t' | ... وإذا كان e : t' فإن C e : t.

التطابق النمطي.

نضيف صيغة النمط الجديدة التالية إلى قائمة الأنماط القانونية:

• C p

ونوسّع تعريف متى يطابق نمط قيمةً وينتج ارتباطًا كما يلي:

• إذا طابق p القيمة v وأنتج ارتباطات $b$، فإن C p يطابق C v وينتج الارتباطات $b$.

3.9.3. الحالات الشاملة

من الأمور التي ينبغي الحذر منها عند التطابق النمطي مع الأنواع المتغايرة ما يسميه Real World OCaml «الحالات الشاملة» (catch-all cases). وإليك مثالًا بسيطًا على ما قد يخطئ. لنفترض أنك كتبت هذا النوع المتغاير والدالة:

type color = Blue | Red
(* a thousand lines of code in between *)
let string_of_color = function
  | Blue -> "blue"
  | _ -> "red"

type color = Blue | Red

val string_of_color : color -> string = <fun>

يبدو جيدًا، أليس كذلك؟ لكنك تدرك يومًا ما أن في العالم ألوانًا أكثر. تحتاج إلى تمثيل اللون الأخضر. فتعود وتضيف الأخضر إلى نوعك المتغاير:

type color = Blue | Red | Green
(* a thousand lines of code in between *)
let string_of_color = function
  | Blue -> "blue"
  | _ -> "red"

type color = Blue | Red | Green

val string_of_color : color -> string = <fun>

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

string_of_color Green

- : string = "red"

والمشكلة هي الحالة الشاملة في التطابق النمطي داخل string_of_color: الحالة الأخيرة التي تستخدم نمط محرف البدل لتطابق أي شيء. وهذه الشيفرة ليست متينة في وجه التغييرات المستقبلية في النوع المتغاير.

أما إذا كنت قد كتبت الدالة في الأصل كما يلي، لكانت الحياة أفضل:

let string_of_color = function
  | Blue -> "blue"
  | Red  -> "red"

File "[9]", lines 1-3, characters 22-17:

1 | ......................function

2 |   | Blue -> "blue"

3 |   | Red  -> "red"

Warning 8 [partial-match]: this pattern-matching is not exhaustive.

Here is an example of a case that is not matched:

Green

val string_of_color : color -> string = <fun>

فمدقّق أنواع OCaml ينبّهك الآن إلى أنك لم تحدّث string_of_color بعد لتراعي المنشئ الجديد.

وخلاصة القصة: الحالات الشاملة تؤدي إلى شيفرة معطوبة. فتجنّب استخدامها.

3.9.4. الأنواع المتغايرة التعاودية

يمكن أن تذكر الأنواع المتغايرة اسمها الخاص داخل جسمها. على سبيل المثال، إليك نوعًا متغايرًا يمكن استخدامه لتمثيل شيء شبيه بـ int list:

type intlist = Nil | Cons of int * intlist
let lst3 = Cons (3, Nil)  (* similar to 3 :: [] or [3] *)
let lst123 = Cons(1, Cons(2, lst3)) (* similar to [1; 2; 3] *)
let rec sum (l : intlist) : int =
  match l with
  | Nil -> 0
  | Cons (h, t) -> h + sum t
let rec length : intlist -> int = function
  | Nil -> 0
  | Cons (_, t) -> 1 + length t
let empty : intlist -> bool = function
  | Nil -> true
  | Cons _ -> false

type intlist = Nil | Cons of int * intlist

val lst3 : intlist = Cons (3, Nil)

val lst123 : intlist = Cons (1, Cons (2, Cons (3, Nil)))

val sum : intlist -> int = <fun>

val length : intlist -> int = <fun>

val empty : intlist -> bool = <fun>

لاحظ أننا في تعريف intlist نعرّف المنشئ Cons ليحمل قيمة تحتوي على intlist. وهذا يجعل النوع intlist تعاوديًا (recursive): فهو معرّف بدلالة نفسه.

ويمكن أن تكون الأنواع متعاودة تبادليًا إذا استخدمت الكلمة المفتاحية and:

type node = {value : int; next : mylist}
and mylist = Nil | Node of node

type node = { value : int; next : mylist; }
and mylist = Nil | Node of node

ويجب أن يتضمن أي تعاود متبادل كهذا نوعًا متغايرًا أو نوع سجل واحدًا على الأقل «يمر عبره» التعاود. على سبيل المثال، التالي غير مسموح به:

type t = u and u = t

File "[12]", line 1, characters 0-10:
1 | type t = u and u = t
    ^^^^^^^^^^
Error: The type abbreviation t is cyclic:
         t = u,
         u = t

لكن هذا مسموح به:

type t = U of u and u = T of t

type t = U of u
and u = T of t

ويمكن أن تكون أنواع السجلات تعاودية أيضًا:

type node = {value : int; next : node}

type node = { value : int; next : node; }

لكن المرادفات النوعية العادية لا يمكن أن تكون كذلك:

type t = t * t

File "[15]", line 1, characters 0-14:
1 | type t = t * t
    ^^^^^^^^^^^^^^
Error: The type abbreviation t is cyclic:
         t = t * t,
         t * t contains t

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

3.9.5. الأنواع المتغايرة ذات المعاملات

يمكن أن تكون الأنواع المتغايرة ذات معاملات (parameterized) على أنواع أخرى. على سبيل المثال، يمكن تعميم النوع intlist أعلاه لتوفير قوائم (مبرمجة بأيدينا) على أي نوع:

type 'a mylist = Nil | Cons of 'a * 'a mylist
let lst3 = Cons (3, Nil)  (* similar to [3] *)
let lst_hi = Cons ("hi", Nil)  (* similar to ["hi"] *)

type 'a mylist = Nil | Cons of 'a * 'a mylist

val lst3 : int mylist = Cons (3, Nil)

val lst_hi : string mylist = Cons ("hi", Nil)

هنا، mylist مُنشئ أنواع وليس نوعًا: فلا سبيل إلى كتابة قيمة من النوع mylist. لكن يمكننا كتابة قيمة من النوع int mylist (مثل lst3) ومن النوع string mylist (مثل lst_hi). فكّر في مُنشئ الأنواع كأنه دالة، لكن دالة تربط أنواعًا بأنواع، بدلًا من ربط قيم بقيم.

وإليك بعض الدوال على 'a mylist:

let rec length : 'a mylist -> int = function
  | Nil -> 0
  | Cons (_, t) -> 1 + length t
let empty : 'a mylist -> bool = function
  | Nil -> true
  | Cons _ -> false

val length : 'a mylist -> int = <fun>

val empty : 'a mylist -> bool = <fun>

لاحظ أن جسم كل دالة لم يتغير عن تعريفها السابق لـ intlist. كل ما غيّرناه هو التعليق النوعي. بل كان يمكن حتى حذفه بأمان:

let rec length = function
  | Nil -> 0
  | Cons (_, t) -> 1 + length t
let empty = function
  | Nil -> true
  | Cons _ -> false

val length : 'a mylist -> int = <fun>

val empty : 'a mylist -> bool = <fun>

الدوال التي كتبناها للتو مثال على ميزة لغوية تسمى تعدد الأشكال الوسيطي (parametric polymorphism). فلا تهتم الدوال بما تكونه 'a في 'a mylist، ومن ثم فهي سعيدة تمامًا بالعمل على int mylist أو string mylist أو أي (something) mylist أخرى. وكلمة «polymorphism» مبنية على الجذرين اليونانيين «poly» (كثير) و«morph» (شكل). فقيمة من النوع 'a mylist يمكن أن يكون لها أشكال كثيرة، حسب النوع الفعلي 'a.

لكن بمجرد أن تضع قيدًا على ما يمكن أن يكون عليه النوع 'a، تتخلى عن قدر من تعدد الأشكال. على سبيل المثال،

let rec sum = function
  | Nil -> 0
  | Cons (h, t) -> h + sum t

val sum : int mylist -> int = <fun>

كوننا نستخدم المؤثر ( + ) مع رأس القائمة يقيّد عنصر الرأس ذلك بأن يكون int، ومن ثم يجب أن تكون جميع العناصر int. وهذا يعني أن sum يجب أن تأخذ int mylist، لا أي نوع آخر من أنواع 'a mylist.

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

type ('a, 'b) pair = {first : 'a; second : 'b}
let x = {first = 2; second = "hello"}

type ('a, 'b) pair = { first : 'a; second : 'b; }

val x : (int, string) pair = {first = 2; second = "hello"}

3.9.6. الأنواع المتغايرة المتعددة الأشكال

حتى الآن، كلما أردت تعريف نوع متغاير، كان عليك إعطاؤه اسمًا، مثل day أو shape أو 'a mylist:

type day = Sun | Mon | Tue | Wed | Thu | Fri | Sat
type shape =
  | Point of point
  | Circle of point * float
  | Rect of point * point
type 'a mylist = Nil | Cons of 'a * 'a mylist

type day = Sun | Mon | Tue | Wed | Thu | Fri | Sat

type shape = Point of point | Circle of point * float | Rect of point * point

type 'a mylist = Nil | Cons of 'a * 'a mylist

وقد تحتاج أحيانًا إلى نوع متغاير لقيمة إرجاع دالة واحدة فقط. على سبيل المثال، إليك دالة f يمكنها إما أن تعيد int أو $\infty$؛ وتُضطر إلى تعريف نوع متغاير لتمثيل تلك النتيجة:

type fin_or_inf = Finite of int | Infinity
let f = function
  | 0 -> Infinity
  | 1 -> Finite 1
  | n -> Finite (-n)

type fin_or_inf = Finite of int | Infinity

val f : int -> fin_or_inf = <fun>

والجانب السلبي في هذا التعريف أنك أُجبرت على تعريف fin_or_inf رغم أنه لن يُستخدم في كثير من برنامجك.

وهناك نوع آخر من الأنواع المتغايرة في OCaml يدعم هذا النمط من البرمجة: الأنواع المتغايرة المتعددة الأشكال (polymorphic variants). وهي تمامًا كالأنواع المتغايرة، إلا أن:

1. لا يلزمك تعريف نوعها أو منشئاتها قبل استخدامها.
2. لا يوجد اسم لنوع متغاير متعدد الأشكال. (لذا كان يمكن تسمية هذه الميزة «الأنواع المتغايرة المجهولة».)
3. تبدأ منشئات النوع المتغاير المتعدد الأشكال بمحرف علامة الاقتباس الخلفية.

وباستخدام الأنواع المتغايرة المتعددة الأشكال، يمكننا إعادة كتابة f:

let f = function
  | 0 -> `Infinity
  | 1 -> `Finite 1
  | n -> `Finite (-n)

val f : int -> [> `Finite of int | `Infinity ] = <fun>

يقول هذا النوع إن f إما تعيد Finite nلبعضn : intأو Infinity. والأقواس المعقوفة هنا لا تشير إلى قائمة، بل إلى مجموعة من المنشئات الممكنة. وعلامة > تعني أن أي شيفرة تطابق نمطيًا قيمة من ذلك النوع يجب أن تتعامل على الأقل مع المنشئين Finite و Infinity، وربما أكثر. على سبيل المثال، يمكننا كتابة:

match f 3 with
  | `NegInfinity -> "negative infinity"
  | `Finite n -> "finite"
  | `Infinity -> "infinite"

- : string = "finite"

لا بأس مطلقًا في أن يتضمن التطابق النمطي منشئات غير Finiteأو Infinity، لأن f مضمونة ألا تعيد أي منشئات غير تلك.

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

3.9.7. الأنواع المتغايرة المدمجة

نوع بيانات القوائم المدمج في OCaml هو في الحقيقة نوع متغاير تعاودي ذو معاملات. وهو معرّف كما يلي:

type 'a list = [] | ( :: ) of 'a * 'a list

لذا فـ list مجرد مُنشئ أنواع، له منشئا (قيم) هما [] (نلفظه «nil») و:: (نلفظه «cons»).

ونوع بيانات الخيارات المدمج في OCaml هو أيضًا في الحقيقة نوع متغاير ذو معاملات. وهو معرّف كما يلي:

type 'a option = None | Some of 'a

لذا فـ option مجرد مُنشئ أنواع، له منشئا (قيم) هما None وSome.

ويمكنك رؤية كل من list وoption معرّفين في مكتبة OCaml الأساسية.

3.10. الاستثناءات

لدى OCaml آلية استثناءات شبيهة بكثير من لغات البرمجة الأخرى. ويُعرّف نوع جديد من استثناءات OCaml بهذه الصياغة:

exception E of t

حيث E اسم منشئ وt نوع. وof t اختياري. لاحظ كيف يشبه ذلك تعريف منشئ لنوع متغاير. على سبيل المثال:

exception A
exception B
exception Code of int
exception Details of string

exception A

exception B

exception Code of int

exception Details of string

ولإنشاء قيمة استثناء، استخدم الصياغة نفسها التي تستخدمها لإنشاء قيمة نوع متغاير. وهنا، على سبيل المثال، قيمة استثناء منشئها Failure، وهي تحمل string:

Failure "something went wrong"

- : exn = Failure "something went wrong"

هذا المنشئ معرّف مسبقًا في المكتبة القياسية وهو من أكثر الاستثناءات شيوعًا التي يستخدمها مبرمجو OCaml.

ولإطلاق قيمة استثناء e، اكتب ببساطة

raise e

وهناك دالة ملائمة failwith : string -> 'a في المكتبة القياسية تطلق Failure. أي أن failwith s مكافئة لـ raise (Failure s).

ولالتقاط استثناء، استخدم هذه الصياغة:

try e with
| p1 -> e1
| ...
| pn -> en

التعبير e هو ما قد يطلق استثناءً. فإن لم يفعل، يقيّم تعبير try كله إلى ما يقيّم إليه e. وإن أطلق e قيمة استثناء v فعلًا، فتُطابق تلك القيمة v مع الأنماط المقدَّمة، تمامًا كما في تعبير match.

3.10.1. الاستثناءات أنواع متغايرة قابلة للتوسيع

جميع قيم الاستثناءات من النوع exn، وهو نوع متغاير معرّف في النواة. لكنه نوع متغاير غير معتاد، يسمى نوعًا متغايرًا قابلًا للتوسيع (extensible)، وهو يتيح تعريف منشئات جديدة للنوع المتغاير بعد تعريف نوع النوع المتغاير نفسه. راجع دليل OCaml لمزيد من المعلومات عن الأنواع المتغايرة القابلة للتوسيع إن كنت مهتمًا.

3.10.2. دلالات الاستثناءات

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

الدلالات الديناميكية. كما قلنا في الأصل، كل تعبير OCaml إما

• يقيّم إلى قيمة
• أو يطلق استثناءً
• أو يفشل في التوقف (أي «حلقة لا نهائية»).

حتى الآن لم نعرض إلا الجزء من الدلالات الديناميكية الذي يعالج الحالة الأولى من تلك الحالات الثلاث. فما الذي يحدث عندما نضيف الاستثناءات؟ الآن، ينتج تقييم التعبير إما قيمة أو حزمة استثناء (exception packet). والحزم ليست قيم OCaml عادية؛ والقطعتان الوحيدتان من اللغة اللتان تتعرفان عليها هما raise وtry. وقيمة الاستثناء التي تنتجها (مثلًا) Failure "oops" جزء من حزمة الاستثناء التي ينتجها raise (Failure "oops")، لكن الحزمة تحتوي على أكثر من قيمة الاستثناء فقط؛ فقد يكون فيها تتبّع مكدّس (stack trace) على سبيل المثال.

ولأي تعبير e غير try، إذا أنتج تقييم تعبير فرعي من e حزمة استثناء P، فإن تقييم e ينتج الحزمة P.

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

let _ = raise A in raise B;;

Exception: A.
Raised at <unknown> in file "[3]", line 1, characters 8-15
Called from Topeval.load_lambda in file "toplevel/byte/topeval.ml", line 93, characters 4-14

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

(raise B) (raise A)

File "[4]", line 1, characters 10-19:

1 | (raise B) (raise A)

              ^^^^^^^^^

Warning 20 [ignored-extra-argument]: this argument will not be used by the function.

File "[4]", line 1, characters 10-19:

1 | (raise B) (raise A)

              ^^^^^^^^^

Warning 20 [ignored-extra-argument]: this argument will not be used by the function.

Exception: A.

Raised at <unknown> in file "[4]", line 1, characters 10-19
Called from Topeval.load_lambda in file "toplevel/byte/topeval.ml", line 93, characters 4-14

من المنطقي أن تطلق كلتا القطعتين من الشيفرة الاستثناء نفسه، بما أننا نعلم أن let x = e1 in e2 سكر صياغي لـ (fun x -> e2) e1.

لكن ما الاستثناء الذي تطلقه الشيفرة التالية؟

(raise A, raise B)

Exception: B.

Raised at <unknown> in file "[5]", line 1, characters 10-17
Called from Topeval.load_lambda in file "toplevel/byte/topeval.ml", line 93, characters 4-14

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

let a = raise A in
let b = raise B in
(a, b)

Exception: A.

Raised at <unknown> in file "[6]", line 1, characters 8-15
Called from Topeval.load_lambda in file "toplevel/byte/topeval.ml", line 93, characters 4-14

تلك الشيفرة مضمونة بأن تطلق A لا B.

ومن الحالات الطرفية المثيرة للاهتمام ما يحدث عندما يكون لتعبير raise نفسه تعبير فرعي يطلق استثناءً:

exception C of string;;
exception D of string;;
raise (C (raise (D "oops")))

exception C of string

exception D of string

Exception: D "oops".

Raised at <unknown> in file "[7]", line 3, characters 9-27
Called from Topeval.load_lambda in file "toplevel/byte/topeval.ml", line 93, characters 4-14

تنتهي تلك الشيفرة بإطلاق D، لأن أول ما يجب أن يحدث هو تقييم C (raise (D "oops")) إلى قيمة. ويتطلب ذلك تقييم raise (D "oops") إلى قيمة. ويؤدي ذلك إلى إنتاج حزمة تحتوي على D "oops"، ثم تنتشر تلك الحزمة لتصبح نتيجة تقييم C (raise (D "oops"))، ومن ثم نتيجة تقييم raise (C (raise (D "oops"))).

وبمجرد أن ينتج تقييم تعبير حزمة استثناء P، تنتشر تلك الحزمة حتى تصل إلى تعبير try:

try e with
| p1 -> e1
| ...
| pn -> en

تُطابق قيمة الاستثناء داخل P مع الأنماط المقدَّمة باستخدام قواعد التقييم المعتادة للتطابق النمطي — باستثناء واحد (والتورية مقصودة مرة أخرى). فإن لم يطابق أي من الأنماط، فبدلًا من إنتاج Match_failure داخل حزمة استثناء جديدة، تستمر حزمة الاستثناء الأصلية P في الانتشار حتى الوصول إلى تعبير try التالي.

3.10.3. التطابق النمطي

هناك صيغة نمط للاستثناءات. وإليك مثالًا على استخدامها:

match List.hd [] with
  | [] -> "empty"
  | _ :: _ -> "non-empty"
  | exception (Failure s) -> s

- : string = "hd"

لاحظ أن الشيفرة أعلاه مجرد تعبير match عادي، لا تعبير try. وهي تطابق قيمة List.hd [] مع الأنماط الثلاثة المقدَّمة. وكما نعلم، ستطلق List.hd [] استثناءً يحتوي على القيمة Failure "hd". ونمط الاستثناء exception (Failure s) يطابق تلك القيمة. لذا ستقيّم الشيفرة أعلاه إلى "hd".

أنماط الاستثناءات نوع من السكر الصياغي. انظر إلى هذه الشيفرة على سبيل المثال:

match e with
  | p1 -> e1
  | exception p2 -> e2
  | p3 -> e3
  | exception p4 -> e4

يمكننا إعادة كتابة الشيفرة لإزالة نمط الاستثناء:

try
  match e with
    | p1 -> e1
    | p3 -> e3
with
  | p2 -> e2
  | p4 -> e4

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

3.10.4. الاستثناءات وOUnit

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

open OUnit2
let tests = "suite" >::: [
    "empty" >:: (fun _ -> assert_raises (Failure "hd") (fun () -> List.hd []));
  ]
let _ = run_test_tt_main tests

يتحقق التعبير assert_raises exn (fun () -> e) مما إذا كان التعبير e يطلق الاستثناء exn. فإن فعل، نجحت حالة اختبار OUnit، وإلا فشلت.

لاحظ أن الوسيط الثاني لـ assert_raises دالة من النوع unit -> 'a، تسمى أحيانًا «ثانك» (thunk). وقد يبدو غريبًا كتابة دالة بهذا النوع — فالمدخل الوحيد الممكن هو () — لكن هذا نمط شائع في اللغات الوظيفية لتعليق تقييم برنامج أو تأجيله. وفي هذه الحالة، نريد أن تقيّم assert_raises التعبير List.hd [] عندما تكون مستعدة. فلو قيّمنا List.hd [] فورًا، لما تمكنت assert_raises من التحقق مما إذا كان الاستثناء الصحيح قد أُطلق. وسنتعلم المزيد عن الثانكات في فصل لاحق.

تحذير

من الأخطاء الشائعة نسيان (fun () -> ...) حول e. فإن ارتكبت هذا الخطأ، فقد يظل البرنامج سليم الأنواع لكن حالة اختبار OUnit ستفشل: فبدون الدالة المجهولة الإضافية، يُطلق الاستثناء قبل أن تسنح لـ assert_raises أي فرصة لمعالجته.

3.11. مثال: الأشجار

الأشجار بنية بيانات مفيدة جدًا. والشجرة الثنائية (binary tree)، كما ستتذكر من CS 2110، عقدة تحتوي على قيمة وطفلين كل منهما شجرة. ويمكن أن تكون الشجرة الثنائية شجرة فارغة أيضًا، ونستخدمها كذلك لتمثيل غياب عقدة طفل.

3.11.1. التمثيل بالأزواج المرتبة

إليك تعريفًا لنوع بيانات شجرة ثنائية:

type 'a tree =
| Leaf
| Node of 'a * 'a tree * 'a tree

type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree

تحمل العقدة عنصر بيانات من النوع 'a ولها شجرة فرعية يسرى وأخرى يمنى. والورقة فارغة. قارن هذا التعريف بتعريف القائمة ولاحظ مدى تشابه بنيتهما:

type 'a tree =                        type 'a mylist =
  | Leaf                                | Nil
  | Node of 'a * 'a tree * 'a tree      | Cons of 'a * 'a mylist

والفرق الجوهري الوحيد أن Cons تحمل قائمة فرعية واحدة، بينما تحمل Node شجرتين فرعيتين.

وإليك شيفرة تنشئ شجرة صغيرة:

(* the code below constructs this tree:
         4
       /   \
      2     5
     / \   / \
    1   3 6   7
*)
let t =
  Node(4,
    Node(2,
      Node(1, Leaf, Leaf),
      Node(3, Leaf, Leaf)
    ),
    Node(5,
      Node(6, Leaf, Leaf),
      Node(7, Leaf, Leaf)
    )
  )

val t : int tree =
  Node (4, Node (2, Node (1, Leaf, Leaf), Node (3, Leaf, Leaf)),
   Node (5, Node (6, Leaf, Leaf), Node (7, Leaf, Leaf)))

حجم (size) الشجرة هو عدد العقد فيها (أي عقد Node، لا Leaf). على سبيل المثال، حجم الشجرة t أعلاه هو 7. وإليك دالة size : 'a tree -> int تعيد عدد العقد في شجرة:

let rec size = function
  | Leaf -> 0
  | Node (_, l, r) -> 1 + size l + size r

3.11.2. التمثيل بالسجلات

لنُنقّح الآن نوع شجرتنا ليستخدم نوع سجل لتمثيل عقدة شجرة. وفي OCaml علينا تعريف نوعين متعاودين تبادليًا، أحدهما لتمثيل عقدة شجرة، والآخر لتمثيل شجرة (قد تكون فارغة):

type 'a tree =
  | Leaf
  | Node of 'a node
and 'a node = {
  value: 'a;
  left: 'a tree;
  right: 'a tree
}

type 'a tree = Leaf | Node of 'a node
and 'a node = { value : 'a; left : 'a tree; right : 'a tree; }

وإليك شجرة مثال:

(* represents
      2
     / \
    1   3  *)
let t =
  Node {
    value = 2;
    left = Node {value = 1; left = Leaf; right = Leaf};
    right = Node {value = 3; left = Leaf; right = Leaf}
  }

val t : int tree =
  Node
   {value = 2; left = Node {value = 1; left = Leaf; right = Leaf};
    right = Node {value = 3; left = Leaf; right = Leaf}}

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

(** [mem x t] is whether [x] is a value at some node in tree [t]. *)
let rec mem x = function
  | Leaf -> false
  | Node {value; left; right} -> value = x || mem x left || mem x right

val mem : 'a -> 'a tree -> bool = <fun>

واسم الدالة mem اختصار لـ «member» (عضو)؛ وكثيرًا ما تستخدم المكتبة القياسية دالة بهذا الاسم لتنفيذ بحث في بنية بيانات تجميعية لتحديد ما إذا كان عنصر ما عضوًا في ذلك التجميع.

وإليك دالة تحسب اجتياز البادئة (preorder) لشجرة، حيث تُزار كل عقدة قبل أي من أطفالها، بإنشاء قائمة تظهر فيها القيم بالترتيب الذي ستُزار به:

let rec preorder = function
  | Leaf -> []
  | Node {value; left; right} -> [value] @ preorder left @ preorder right

val preorder : 'a tree -> 'a list = <fun>

preorder t

- : int list = [2; 1; 3]

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

let preorder_lin t =
  let rec pre_acc acc = function
    | Leaf -> acc
    | Node {value; left; right} -> value :: (pre_acc (pre_acc acc right) left)
  in pre_acc [] t

val preorder_lin : 'a tree -> 'a list = <fun>

تستخدم النسخة أعلاه عملية :: واحدة بالضبط لكل عقدة Node في الشجرة، مما يجعلها خطية الزمن.

3.12. مثال: الأعداد الطبيعية

يمكننا تعريف نوع متغاير تعاودي يعمل عمل الأعداد، لنبرهن أننا لا نحتاج حقًا إلى أن تكون الأعداد مدمجة في OCaml! (لكن من الجيد، من أجل الكفاءة، أنها مدمجة.)

العدد الطبيعي (natural number) إما صفر (zero) أو لاحق (successor) عدد طبيعي آخر. وهكذا قد تعرّف الأعداد الطبيعية في مقرر منطق رياضي، ويؤدي ذلك طبيعيًا إلى نوع OCaml التالي nat:

type nat = Zero | Succ of nat

type nat = Zero | Succ of nat

عرّفنا نوعًا جديدًا nat، والمنشئان Zero وSucc منشئان لقيم من هذا النوع. وهذا يتيح لنا بناء تعبيرات فيها عدد اعتباطي من منشئات Succ المتداخلة. وتعمل تلك القيم عمل الأعداد الطبيعية:

let zero = Zero
let one = Succ zero
let two = Succ one
let three = Succ two
let four = Succ three

val zero : nat = Zero

val one : nat = Succ Zero

val two : nat = Succ (Succ Zero)

val three : nat = Succ (Succ (Succ Zero))

val four : nat = Succ (Succ (Succ (Succ Zero)))

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

let iszero = function
  | Zero -> true
  | Succ _ -> false
let pred = function
  | Zero -> failwith "pred Zero is undefined"
  | Succ m -> m

val iszero : nat -> bool = <fun>

val pred : nat -> nat = <fun>

وبالمثل، يمكننا تعريف دالة لجمع عددين:

let rec add n1 n2 =
  match n1 with
  | Zero -> n2
  | Succ pred_n -> add pred_n (Succ n2)

val add : nat -> nat -> nat = <fun>

ويمكننا تحويل قيم nat إلى النوع int والعكس:

let rec int_of_nat = function
  | Zero -> 0
  | Succ m -> 1 + int_of_nat m
let rec nat_of_int = function
  | i when i = 0 -> Zero
  | i when i > 0 -> Succ (nat_of_int (i - 1))
  | _ -> failwith "nat_of_int is undefined on negative ints"

val int_of_nat : nat -> int = <fun>

val nat_of_int : int -> nat = <fun>

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

let rec even = function Zero -> true | Succ m -> odd m
and odd = function Zero -> false | Succ m -> even m

val even : nat -> bool = <fun>
val odd : nat -> bool = <fun>

3.13. الملخّص

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

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

توفر OCaml أنواع بيانات للأنواع المتغايرة (أنواع واحد-من)، والأزواج المرتبة والجداة (أنواع كل-من)، والخيارات (أنواع ربما). ويمكن استخدام التطابق النمطي للوصول إلى قيم كل من تلك الأنواع. كما يمكن استخدام التطابق النمطي في تعبيرات let والدوال.

وتجمع قوائم الترابط بين القوائم والأزواج المرتبة لإنشاء تنفيذ خفيف للقواميس.

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

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

• نوع بيانات جبري (algebraic data type)
• الإلحاق (append)
• قائمة ترابط (association list)
• الأشجار الثنائية كأنواع متغايرة (binary trees as variants)
• الربط (binding)
• الفرع (branch)
• البيانات المحمولة (carried data)
• الحالات الشاملة (catch-all cases)
• cons
• منشئ ثابت (constant constructor)
• منشئ (constructor)
• النسخ (copying)
• إزالة السكر الصياغي (desugaring)
• نوع كل-من (each-of type)
• استثناء (exception)
• الاستثناءات كأنواع متغايرة (exception as variants)
• حزمة استثناء (exception packet)
• نمط استثناء (exception pattern)
• قيمة استثناء (exception value)
• الشمول (exhaustiveness)
• حقل (field)
• الرأس (head)
• الاستقراء (induction)
• ورقة (leaf)
• قائمة (list)
• القوائم كأنواع متغايرة (lists as variants)
• نوع «ربما» (maybe type)
• الدوال المتعاودة تبادليًا (mutually recursive functions)
• الأعداد الطبيعية كأنواع متغايرة (natural numbers as variants)
• nil
• عقدة (node)
• منشئ غير ثابت (non-constant constructor)
• نوع واحد-من (one-of type)
• الخيارات (options)
• الخيارات كأنواع متغايرة (options as variants)
• ترتيب التقييم (order of evaluation)
• زوج (pair)
• نوع متغاير ذو معاملات (parameterized variant)
• تعدد الأشكال الوسيطي (parametric polymorphism)
• التطابق النمطي (pattern matching)
• الإضافة إلى المقدمة (prepend)
• نوع جداء (product type)
• سجل (record)
• التعاود (recursion)
• نوع متغاير تعاودي (recursive variant)
• المشاركة (sharing)
• إطار مكدّس (stack frame)
• نوع مجموع (sum type)
• سكر صياغي (syntactic sugar)
• وسم (tag)
• الذيل (tail)
• نداء ذيلي (tail call)
• التعاود الذيلي (tail recursion)
• التطوير القائم على الاختبار (test-driven development, TDD)
• ثلاثي (triple)
• زوج مرتّب (tuple)
• مُنشئ أنواع (type constructor)
• مرادف نوعي (type synonym)
• نوع متغاير (variant)
• محرف البدل (wildcard)

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

• Introduction to Objective Caml، الفصول 4 و5.2 و5.3 و5.4 و6 و7 و8.1
• OCaml from the Very Beginning، الفصول 3 و4 و5 و7 و8 و10 و11
• Real World OCaml، الفصول 3 و5 و6 و7

1
2
3

let rec print_int_list = function
| [] -> ()
| h :: t -> (* fill in here *); print_int_list t

let print_int_list' lst =
  List.iter (fun x -> (* fill in here *)) lst

type student = {first_name : string; last_name : string; gpa : float}

type poketype = Normal | Fire | Water

type quad = I | II | III | IV
type sign = Neg | Zero | Pos
let sign (x:int) : sign =
  ...
let quadrant : int*int -> quad option = fun (x,y) ->
  match ... with
    | ... -> Some I
    | ... -> Some II
    | ... -> Some III
    | ... -> Some IV
    | ... -> None

let quadrant_when : int*int -> quad option = function
    | ... when ... -> Some I
    | ... when ... -> Some II
    | ... when ... -> Some III
    | ... when ... -> Some IV
    | ... -> None

val sign : int -> [> `Neg | `Pos | `Zero ]
val quadrant : int * int -> [> `I | `II | `III | `IV ] option