المكتبة العربية لعلوم الحاسوب
تعلّم البرمجة بلغة OCaml › الخطوات الأولى 4 / 16 السابق التالي

الخطوات الأولى

2. الخطوات الأولى

أفضل طريقة لتعلّم لغة برمجة هي البرمجة نفسها. لذلك نعرض أدناه أربعة عشر برنامجًا (صغيرًا) للبدء مع أوسمل (OCaml). والهدف هو تقديم البُنى والأفكار الأساسية للغة.

2.1 السنوات الكبيسة

برنامجنا الأول، leap_year.ml، يحدد ما إذا كانت سنة معيّنة كبيسة. ويمكننا ترجمته باستخدام ocamlc.

  > ocamlc -o leap_year leap_year.ml

عند تشغيل البرنامج، ينتظر أن يُدخِل المستخدم سنة. ثم يطبع ما إذا كانت السنة كبيسة أم لا.

  > ./leap_year
  2013
  2013 is not a leap year

لننظر الآن في بنية هذا البرنامج. يقرأ السطر الأول عددًا صحيحًا من الدخل القياسي:

  let year = read_int ()

يحتوي هذا السطر وحده على عدة مفاهيم من لغة أوسمل. أولًا، إنه إعلان متغير (variable declaration) بالشكل التالي:

  let year = ...

يُهيّئ هذا متغيرًا جديدًا year بنتيجة التعبير الواقع على يمين الرمز =. ولا يلزم التصريح بنوع المتغير year؛ إذ يستنتجه المترجم أو المفسّر تلقائيًا. والتعبير الواقع على يمين الرمز = هو استدعاء دالة (function call). إنه استدعاء للدالة المعرَّفة مسبقًا read_int.

       ... = read_int ()

هنا، تشير () إلى أن الدالة read_int لا تأخذ أي وسيط ذي معنى. إنها تُعيد فقط عددًا صحيحًا مقروءًا من الدخل القياسي.

يُعرِّف السطر الثاني متغيرًا منطقيًا leap قيمته true إذا وفقط إذا كانت year سنة كبيسة، أي إذا كانت تقبل القسمة على 4 دون 100، أو إذا كانت تقبل القسمة على 400.

  let leap =
    (year mod 4 = 0 && year mod 100 <> 0) || year mod 400 = 0

تُعيد المعاملة (العامل) mod باقي قسمة الأعداد الصحيحة. ويمثّل العاملان && و|| العمليتين المنطقيتين «و» و«أو» على التوالي. وكما في year، يُستنتج نوع المتغير leap تلقائيًا. ويُعرِّف السطر التالي متغيرًا ثالثًا، msg، يحوي سلسلة نصية:

  let msg = if leap then "is" else "is not"

سيحوي المتغير msg السلسلة "is" إذا كانت leap صحيحة، والسلسلة "isnot" إذا كانت خاطئة. (تُحدَّد السلاسل بعلامتي تنصيص مزدوجتين ".) لاحظ أن البنية if-then-else تُستخدَم هنا لبناء تعبير، ألا وهو سلسلة نصية.

أخيرًا، يطبع السطر الأخير رسالة تبيّن ما إذا كانت السنة المُدخَلة كبيسة أم لا.

  let () = Printf.printf "%d %s a leap year\n" year msg

يُنجَز ذلك باستدعاء دالة المكتبة Printf.printf بثلاث وسائط: سلسلة تنسيق "%d %s a leap year\n" مع القيمتين، year وmsg، اللتين تحلّان على التوالي محل %d و%s في الرسالة المطبوعة. وكما ترى، يُرمَز إلى استدعاء الدالة بمجرد تجاور الدالة ووسائطها. وخلافًا للغات أخرى، لا تستخدم أوسمل أقواسًا حول الوسائط.

     ... = Printf.printf "%d %s a leap year\n" year msg

نُحيل القارئ إلى دليل أوسمل لمزيد من المعلومات عن المكتبة القياسية، وبوجه خاص عن الدالة Printf.printf. يتوفّر الدليل على الإنترنت على العنوان: https://ocaml.org/manual. وأخيرًا، لاحظ أن استدعاء الدالة printf مُضمَّن في إعلان ذي شكل محدَّد:

  let () = ...

هذا غامض بعض الشيء، وسنتركه كذلك في الوقت الحالي. وسنشرحه حين نتناول مطابقة الأنماط (pattern matching) في القسمين 2.6 رسم منحنى و2.12 عزف مقطوعة موسيقية. ويكفي الآن القول إن برنامج أوسمل، بشكل عام، سلسلة من الإعلانات تُقيَّم من الأعلى إلى الأسفل، أي بالترتيب الذي تظهر به في الملف المصدر. وخلافًا للغات مثل C أو Java، لا توجد نقطة دخول main. ويُستخدَم الشكل المحدَّد let()=... للحفاظ على التنسيق نفسه في حالة التعبيرات التي لا تُعيد قيمة. وعند استخدام هذا الشكل، يتحقق أوسمل من أن التعبير لا يُعيد قيمة فعلًا.

معلومات إضافية

سطر الأوامر

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

  > ./leap_year 2013
  2013 is not a leap year

للقيام بذلك، نستبدل السطر letyear=read_int() بـ:

  let year = int_of_string Sys.argv.(1)

يستدعي هذا السطر الدالة المعرَّفة مسبقًا int_of_string بالوسيط Sys.argv.(1). وتحتوي القيمة Sys.argv.(1) على السنة الممرَّرة كوسيط على سطر الأوامر. وكما هو الحال في لغات برمجة أخرى (Java أو C، مثلًا)، يمكننا استرجاع القيم الممرَّرة إلى البرنامج على شكل مصفوفة من السلاسل النصية، تُسمّى Sys.argv في أوسمل. وبشكل أدق، تُسمّى المصفوفة argv، وهي متاحة ضمن وحدة Sys، التي تشكّل واجهة لنظام التشغيل. ويتعلّق الترميز Sys.argv بـنظام الوحدات في أوسمل، الذي ينظّم المكتبات في وحدات تُسمّى وحدات (modules)، تحتوي هي نفسها على قيم مختلفة. ودون الخوض في تفاصيل نظام الوحدات، يكفي القول الآن إننا نشير إلى قيمة داخل وحدة بكتابة اسم الوحدة، متبوعًا باسم القيمة، مفصولين بنقطة. (سنناقش هذا بمزيد من التفصيل في القسم 2.11 لوجو ترتل (Logo Turtle).) وعليه، يجب قراءة Sys.argv على أنها «المصفوفة argv التي تنتمي إلى الوحدة Sys».

نستخدم الترميز t.(i) للوصول إلى العنصر رقم i في مصفوفة t. وسنعود إلى مفهوم المصفوفات في القسم 2.5 غربال إراتوستينس (The Sieve of Eratosthenes). العنصر الأول من Sys.argv هو Sys.argv.(0) لأن فهرسة المصفوفات تبدأ من 0. وهذا هو اسم البرنامج (هنا leap_year). والعنصر الثاني هو Sys.argv.(1). وهذا أول وسيط يُمرَّر إلى البرنامج (2013 في مثالنا). وبما أنه سلسلة نصية، يجب تحويله إلى عدد صحيح باستدعاء الدالة int_of_string، التي تنتمي إلى وحدة Stdlib. وهذه وحدة خاصة لا يلزم أن تُكتب Stdlib. قبل أسماء قيمها.

التحقق من الأنواع

لننظر الآن في بعض التفاصيل الإضافية المتعلقة بأنواع البيانات المقدَّمة في برنامجنا الأول. وبينما تُستنتَج أنواع المتغيرات تلقائيًا، يمكن أيضًا عرضها باستخدام الخيار -i للمترجم:

  > ocamlc -i leap_year.ml
  val year : int
  val leap : bool
  val msg : string

نرى إذن أن المتغيرات year وleap وmsg من الأنواع int وbool وstring على التوالي. وهذه ثلاثة أنواع معرَّفة مسبقًا في أوسمل. لنفحص هذه الأنواع وأنواعًا أخرى متعلقة بها باستخدام الطرفية التفاعلية.

الأنواع int و int32 و int64

لنبدأ بالنوع int، الذي يقابل الأعداد الصحيحة الأصلية للمعالج، وتُسمّى أيضًا الأعداد الصحيحة الآلية. ويمكن كتابة ثابتة صحيحة بالترميز العشري، أو الثنائي (السابقة 0b)، أو الثماني (السابقة 0o)، أو السداسي عشر (السابقة 0x). وهكذا يمكن كتابة الثابتة العشرية 91 على هيئة 0b1011011 في النظام الثنائي، و0o133 في النظام الثماني، و0x5B في النظام السداسي عشر.

العمليات المعتادة على النوع int هي الجمع (+)، والطرح (-)، والضرب (*)، وقسمة الأعداد الصحيحة (/)، والباقي (mod).

  # 2 * (7 / 2) + 7 mod 2;;
  - : int = 7

لمزيد من الوضوح، يمكن فصل الأرقام باستخدام شرطة سفلية (_).

  # 0x2f_ff_ff_ff + 268_435_456;;
  - : int = 1073741823

تعتمد دقة النوع int على معمارية الآلة. ويُعطى الحدّان الأدنى والأقصى للنوع int بالثابتتين min_int وmax_int.

  # min_int;;
  - : int = -1073741824

على آلة ذات 32 بت، تُرمَّز قيم النوع int كأعداد صحيحة مؤشَّرة ذات 31 بت[1]، بحيث تأخذ min_int وmax_int القيمتين −230 و 230 − 1 على التوالي. وعلى آلة ذات 64 بت، تُرمَّز قيم النوع int كأعداد صحيحة مؤشَّرة ذات 63 بت. ويستخدم التمثيل الآلي للأعداد الصحيحة تمثيل المتمّم الثنائي، ويمكن التعامل معه بمساعدة عمليات الإزاحة (lsl وlsr وasr) والعمليات البتّية (land وlor وlxor وlnot). فعلى سبيل المثال، يمكنك اختبار البتة الخامسة في تمثيل العدد الصحيح 42 باستخدام:

  # 42 land (1 lsl 5);;
  - : int = 32

لمعالجة الأعداد الصحيحة المؤشَّرة ذات 32 بت أو 64 بت، تقدّم أوسمل نوعين خاصين: int32 وint64. وتُكتَب الثوابت الصحيحة من النوع int32 (أو int64) باللاحقة l (أو L).

  # 123l;;
  - : int32 = 123l
  # 10_000_000_000_000L;;
  - : int64 = 10000000000000L

يمكن العثور على العمليات الحسابية على هذين النوعين في وحدتي أوسمل Int32 وInt64.

النوع bool

يمثّل النوع bool القيم المنطقية، أي true وfalse. والعمليات على النوع bool هي العطف (&&)، والفصل (||)، والنفي (not).

  # not true && false || true;;
  - : bool = true

للنفي الأسبقية الأعلى، يليه العطف، ثم الفصل. لذا يُقرأ التعبير السابق على النحو التالي:

  # ((not true) && false) || true;;
  - : bool = true

ترتيب تقييم المعاملتين && و|| ثابت من اليسار إلى اليمين. وعلاوةً على ذلك، لا يُقيَّم الوسيط الثاني إلا عند الحاجة، أي فقط إذا كان الوسيط الأول للمعاملة && (أو || على التوالي) صحيحًا (أو خاطئًا على التوالي). وهاتان هما المعاملتان الوحيدتان المحدَّد لهما ترتيب التقييم. وعلاوةً على ذلك، هاتان هما المعاملتان الوحيدتان اللتان يكون تقييمهما كسولًا (lazy).

تُعيد عمليات المقارنة =, <>, ``, = قيمة منطقية.

  # 1 < 2 && 3 = 4;;
  - : bool = false

تُستخدَم التعبيرات المنطقية أساسًا في البنية الشرطية ife1thene2elsee3. ووفقًا لكون التعبير e1 صحيحًا أو خاطئًا، يُقيَّم إما التعبير e2 وإما التعبير e3.

  # if 1 < 2 then 3 else 4;;
  - : int = 3

وكما هو واضح في هذا المثال، فإن البنية ifthenelse تعبير كأي تعبير آخر. وبوجه خاص، لكي يكون هذا التعبير سليم النوع (well-typed)، يجب أن يكون للفرعين e2 وe3 النوع نفسه، الذي يصبح عندئذ نوع التعبير ككل.

النوعان char و string

تُمثَّل المحارف بالنوع char. وتُكتَب بين علامتي تنصيص مفردتين: ’a’. أما المحارف غير القابلة للطباعة فتُدخَل باستخدام ترميز بالشكل ’``\c’، حيث يمكن أن يكون c محرفًا (n أو r أو t أو ) أو رمز ASCII (بين 0 و255)، مكتوبًا بثلاثة أرقام عشرية (\ddd) أو رقمين سداسيَّين عشريَّين (\xdd).

  # ’a’;;
  - : char = ’a’
  # ’\n’;;
  - : char = ’\n’
  # ’\\’;;
  - : char = ’\\’
  # ’\126’;;
  - : char = ’~’
  # ’\x7E’;;
  - : char = ’~’

يمكنك تحويل محرف إلى رمزه ASCII والعكس بمساعدة الدالتين Char.code وChar.chr من وحدة Char.

تُمثَّل السلاسل النصية بالنوع string. وتُكتَب بين علامتي تنصيص مزدوجتين: "abc". ويمكن داخل السلسلة النصية إدخال المحارف غير القابلة للطباعة بالصيغة نفسها المستخدمة للنوع char.

  # "a";;
  - : string = "a"
  # "hello world\n";;
  - : string = "hello world\n"
  # "";;
  - : string = ""
  # "abc\126def";;
  - : string = "abc~def"

وكما هو واضح في هذا المثال، لا تملك السلسلة "a" النوع نفسه الذي يملكه المحرف ’a’. وبشكل عام، لا يوجد تحويل بين هذين النوعين. ويمكنك الوصول إلى المحرف رقم i في سلسلة s بالترميز s.[i]، حيث يكون للمحرف الأول الفهرس 0.

  # "abc".[1];;
  - : char = ’b’

يُعطى طول سلسلة نصية بالدالة String.length من وحدة String. وأخيرًا، يمكن دمج سلسلتين نصيتين باستخدام المعاملة ^.

  # String.length ("abc" ^ "def");;
  - : int = 6

نُحيل القارئ إلى دليل أوسمل لمزيد من التفاصيل بشأن الوحدات المعروضة في هذا الفصل.

الإدخال/الإخراج

أبسط دوال الإدخال/الإخراج هي تلك التي تطبع قيمًا من الأنواع الأساسية، مثل print_string، التي استُخدمت أعلاه لطباعة Hello world. ومن هذه الدوال أيضًا print_char وprint_int وprint_float؛ وprint_newline لطباعة إرجاع عربة؛ وprint_endline لطباعة سلسلة نصية يتبعها إرجاع عربة. وتكتب دوال الطباعة الست هذه إلى الخرج القياسي. أما الكتابة إلى الخطأ القياسي، فثمّ ست دوال أخرى: prerr_char وprerr_string وغيرها. وبالمثل، توجد دوال تقرأ من الدخل القياسي، وهي read_int وread_float وread_line. وهناك أيضًا صيغة من الدالة printf للكتابة إلى الخطأ القياسي، هي Printf.eprintf. وستجد مزيدًا من التفاصيل بشأن الإدخال/الإخراج في القسم 2.7 نسخ ملف.

2.2 طريقة مونت كارلو

برنامجنا الثاني (انظر الصفحة 46)، approx_pi.ml، يحسب قيمة π تجريبيًا باستخدام طريقة مونت كارلو (Monte-Carlo). وتتمثّل هذه الطريقة في توليد نقاط عشوائيًا داخل مربع طول ضلعه 1، ومساحته بالتالي 1، ثم عدّ عدد هذه النقاط الواقعة داخل ربع دائرة نصف قطرها 1 مرسوم داخل هذا المربع. ومساحة ربع الدائرة هي π∕4. ويوضّح الشكل 2.1 الفكرة.

الشكل 2.1: حساب π باستخدام طريقة مونت كارلو.

نترجم البرنامج approx_pi.ml، مثلًا باستخدام ocamlopt (لكفاءة أكبر)، على النحو التالي:

  > ocamlopt -o approx_pi approx_pi.ml

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

  > ./approx_pi
  500
  3.136000
  > ./approx_pi
  5000
  3.113600
  > ./approx_pi
  50000
  3.149920
  > ./approx_pi
  500000
  3.142184

غير أنه في الممارسة العملية، تعطي هذه الطريقة قيمة لـ π صحيحة فقط حتى بضعة منازل عشرية. فمثلًا، مع 10 ملايين نقطة، تكون القيمة صحيحة فقط حتى المنزلة العشرية الثالثة.

كما في برنامجنا الأول، يحصل السطر الأول من approx_pi.ml على العدد n من النقاط المطلوب توليدها بقراءة عدد صحيح من الدخل القياسي:

  let n = read_int ()

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

يُسمّى الحساب بهذه الطريقة، بتعديل محتوى متغير، حسابًا بواسطة الآثار الجانبية (side effects). وبشكل أعم، يُستخدَم مصطلح الأثر الجانبي بالنسبة إلى التعبيرات التي لا تُعيد قيمة عند تقييمها. وكما ذكرنا في القسم السابق، يُستخدَم إعلان بالشكل let()=... لتقييم مثل هذه التعبيرات.

تتألف بقية البرنامج من التعبير الذي يلي علامة =. ويبدأ بتهيئة متغير p بإعلان بالشكل التالي:

     let p = ... in
     ...

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

يُهيَّأ المتغير p بـمرجع (reference)، أي خلية ذاكرة يمكن تعديل محتواها، وتحوي في البداية القيمة 0. وسيُستخدَم هذا المرجع لعدّ عدد النقاط الواقعة داخل ربع الدائرة.

     let p = ref 0 in
     ...

يُنشأ المتغير p باستدعاء الدالة المعرَّفة مسبقًا ref (المعرَّفة في وحدة Stdlib) بالعدد الصحيح 0 كوسيط. ويترتّب على تطبيق هذه الدالة تخصيص خلية ذاكرة جديدة وتهيئة محتواها بالقيمة 0. والنوع الذي يستنتجه أوسمل للمتغير p هو intref، ويُقرأ على أنه «مرجع يحوي قيمة من النوع int».

يُعرِّف السطر التالي حلقة for تقيّم التعبير الواقع بين الكلمتين المفتاحيتين do وdone عدد n من المرات، مع تغيير محتوى المتغير k من 1 إلى n:

     for k = 1 to n do
      ...
     done

المتغير k هو فهرس الحلقة، والتعبير الواقع بين do وdone هو جسم الحلقة. يُهيَّأ الفهرس k بالقيمة 1. ثم يُقيَّم الجسم. هذه هي التكرار الأول للحلقة. بعد ذلك يُزاد k، ويُقيَّم الجسم مرة أخرى. هذا هو التكرار الثاني للحلقة. وهكذا دواليك. وبعد التقييم الذي تكون فيه k مساوية لـ n، تنتهي الحلقة.

يبدأ جسم الحلقة بتوليد إحداثيات نقطة (x,y) عشوائيًا داخل مربع طول ضلعه 1.

      let x = Random.float 1.0 in
      let y = Random.float 1.0 in

ولهذا الغرض، يُهيَّأ متغيران محليان، x وy، باستدعاءين للدالة Random.float بالوسيط العدد ذي الفاصلة العائمة 1.0. ويُعيد كلٌّ من هذين الاستدعاءين عددًا ذا فاصلة عائمة بين 0 و1 (يشمل 0 ويستثني 1). وكما سنرى لاحقًا، تفرّق أوسمل تفريقًا صارمًا بين أعداد الفاصلة العائمة، وهي من النوع float، والأعداد الصحيحة، وهي من النوع int. والمهم أنه يجب إدراج نقطة بعد العدد 1 لتمثيل العدد ذي الفاصلة العائمة 1. لذا نكتب 1.0 أو 1. لتمييزه عن العدد الصحيح 1 من النوع int.

تزيد البنية الشرطية التي تلي محتوى المرجع p إذا كانت النقطة (x,y) داخل ربع الدائرة، أي إذا كان x2 + y2 ≤ 1.

      if x *. x +. y *. y <= 1.0 then
        p := !p + 1

وكما نرى في التعبير x*.x+.y*.y، فإن المعاملات الحسابية على أعداد الفاصلة العائمة تتميّز أيضًا صرفيًا (syntactically) عن معاملات الأعداد الصحيحة: يجب إضافة نقطة . بعد إشارة كل معاملة (+ و- وغيرها). وهكذا فإن +. هي معاملة الجمع على العوائم، و*. معاملة الضرب، وهكذا. ومع ذلك، تُستخدَم المعاملة نفسها <= لمقارنة العوائم والأعداد الصحيحة. (انظر الفصل 3 لمزيد من التفاصيل حول معاملات المقارنة.)

يُستخدَم التعبير p:=!p+1 لزيادة المرجع p بمقدار 1. هنا، تعمل معاملة الإسناد := على تعديل محتوى مرجع، بينما تُستخدَم معاملة إلغاء المرجع (dereference) الأحادية البادئة ! لاسترجاع محتوى مرجع. وعليه، إذا كان p مرجعًا من النوع intref، فإن القيمة !p من النوع int. وتنتهي الحلقة بعد التكرار الذي تكون فيه k مساوية لـ n. ثم يستمر التقييم بالتعبير الذي يلي المعاملة ;.

     for k = 1 to n do
      ...
     done;

تُسمّى سلسلة التقييمات هذه تسلسل تعبيرات (expression sequence). ولكي يقبل أوسمل تسلسل تعبيرات، يجب ألا يُعيد التعبير الذي قبل الفاصلة المنقوطة قيمة، أي يجب ألا يُحدِث سوى آثار جانبية.

يُعرِّف الإعلان الذي يلي حلقة for متغيرًا محليًا pi يحوي تقريب π.

      let pi = 4.0 *. float !p /. float n in

لإجراء قسمة على أعداد الفاصلة العائمة، تُحوَّل القيمتان الصحيحتان !p وn إلى عوائم باستخدام الدالة float (المعرَّفة في وحدة Stdlib).

أخيرًا، نعرض تقريب π المحسوب بهذه الطريقة باستخدام الدالة Printf.printf:

      Printf.printf "%f\n" pi

وكما استخدمنا %d في سلسلة تنسيق لعرض عدد صحيح، نستخدم هنا %f لعرض عدد ذي فاصلة عائمة.

معلومات إضافية

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

النوع float

تُمثَّل الأعداد الحقيقية في الحاسوب باستخدام نوع خاص من الترميز يُسمّى أعداد الفاصلة العائمة (floating-point numbers)، أو ببساطة العوائم (floats). وفي أوسمل، تُرمَّز أعداد الفاصلة العائمة باستخدام معيار IEEE 754 مزدوج الدقة (64 بت). ولا توجد في أوسمل أعداد فاصلة عائمة أحادية الدقة (32 بت).

كما لاحظنا سابقًا، نوع أعداد الفاصلة العائمة هو float. وتُكتَب ثابتة من النوع float إما بالترميز العشري (مثل 3.14) وإما بالترميز العلمي (مثل 6.02214e23). ويجب دائمًا استخدام نقطة في الترميز العشري، للإشارة إلى أن الثابتة ليست من النوع int. أما في حالة الترميز العلمي، فليست النقطة إلزامية.

  # 3 ;;
  - : int = 3
  # 3. ;;
  - : float = 3.
  # 1e6 ;;
  - : float = 1000000.

تختلف العمليات على النوع float عن تلك التي على النوع int. ويتبعها نقطة، كما في حالة ثوابت أعداد الفاصلة العائمة: +. و-. و*. و/.. وخلافًا لما في لغات أخرى، تختلف أسماء العمليات الحسابية وفقًا لكون الأعداد صحيحة أو ذات فاصلة عائمة، ولا توجد تحويلات ضمنية بين النوعين int وfloat.

  # 2 +. 3.14;;
  Error: This expression has type int but an expression was
  expected of type float

يجب استخدام دالتي التحويل float وtruncate لتحويل الأعداد الصحيحة إلى أعداد الفاصلة العائمة والعكس.

  # 3.14 /. float 2;;
  - : float = 1.57
  # truncate 3.141592;;
  - : int = 3

تتوفر عمليات عديدة على النوع float في وحدة Stdlib، مثل الرفع إلى قوة **، والجذر التربيعي sqrt، والدوال المثلثية، والدوال اللوغاريتمية، وغيرها. وهكذا يمكن حساب قيمة π، غير المعرَّفة مسبقًا في أوسمل، باستخدام التعبير التالي:

  # 4. *. atan 1.;;
  - : float = 3.14159265358979312

وخلافًا للنوع int، يتضمّن النوع float ثلاث قيم إضافية، neg_infinity وinfinity وnan، تمثّل حسابات لا نتيجة ذات معنى لها.

  # -1. /. 0.;;
  - : float = neg_infinity
  # 1. /. 0.;;
  - : float = infinity
  # 0. /. 0.;;
  - : float = nan

وخلافًا للغات أخرى، تقدّم أوسمل نوعًا واحدًا فقط من أعداد الفاصلة العائمة، ألا وهو أعداد الفاصلة العائمة المزدوجة الدقة 64-بت المطابقة لمعيار IEEE 754. وتقع أعداد الفاصلة العائمة بين قيمة دنيا min_float وقيمة قصوى max_float.

  # min_float;;
  - : float = 2.22507385850720138e-308
  # max_float;;
  - : float = 1.79769313486231571e+308
بنيتا let و let-in

تُستخدَم البنيتان let وlet-in، على التوالي، لتعريف المتغيرات العامة والمحلية. ويجب ملاحظة نقطتين مهمتين بخصوص المتغيرات:

  • المتغيرات مهيَّأة بالضرورة.
  • يُستنتج نوع المتغير تلقائيًا.

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

يمكنك استخدام الطرفية التفاعلية لمعرفة النوع المستنتَج لمتغير. على سبيل المثال، إذا كتبنا الإعلان التالي:

  # let x = 1+2;;

يعرض المفسّر الاستجابة:

  val x : int = 3

يشير هذا إلى أننا عرّفنا متغيرًا عامًا x، مهيَّأً بالعدد الصحيح 3. ويُستنتج نوع x من التعبير 1+2، ألا وهو int.

من المهم بالقدر نفسه إتقان قواعد النطاق (scoping rules) للمتغيرات المعرَّفة بواسطة بنية let أو let-in. يبدأ نطاق المتغير العام x مباشرةً بعد الإعلان let x =... المستخدم لتعريفه. ويمتد هذا النطاق حتى نهاية البرنامج. أما نطاق المتغير المحلي المُعرِّف بواسطة بنية let-in فيقتصر على التعبير الذي يلي الكلمة المفتاحية in. وعليه فإن كل إعلان من الإعلانات الثلاثة أدناه يُحدِث خطأ في النطاق:

  # let x = x + 1;;
  Error: Unbound value x
  # (let v = 1 + 2 in v * v) + v;;
  Error: Unbound value v
  # let z = 1 + z in z * 2;;
  Error: Unbound value z

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

  let x = 10
  let y = x+2

وفي المقابل، البرنامج أدناه خاطئ:

  let y = x+2
  let x = 10

من المهم ملاحظة أنه في التعبير letx=e1ine2;e3، يمتد نطاق المتغير x إلى التعبير e2;e3 بأكمله. وأسبقية المعاملة ; أعلى من أسبقية البنية let. وبعبارة أخرى، يجب قراءة هذا التعبير على النحو التالي: letx=e1in(e2;e3). ويستفيد البرنامج 2 من قاعدة النطاق هذه في إعلان المتغير المحلي p.

  let () =
    let p = ... in
    for k = 1 to n do
      ...
      p := !p + 1
    done;
    let pi = 4. *. float !p /. float n in
    ...

وهكذا يكون المتغير p مرئيًا في حلقة for وفي جسم إعلان المتغير pi معًا.

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

  let x = 10
  let y = x + 2
  let x = 20
  let () = Printf.printf "x=%d y=%d\n" x y

يُعرِّف الإعلان letx=20 متغيرًا جديدًا x، يحجب نطاق المتغير السابق. وعليه تكون الرسالة المعروضة عند تنفيذ البرنامج x=20y=12.

حلقة for

كما رأينا في مثالنا، تُستخدَم حلقات for لتقييم تعبير معيّن عددًا محدَّدًا من المرات. ولها الشكل التالي:

  for i = e1 to e2 do
    e
  done

يُعرِّف بناء for فهرس الحلقة، أي المتغير i. ولا يمكن للمستخدم تعديل قيمته. ويقتصر نطاقه على جسم الحلقة (التعبير e)، ولذلك لا يمكن استخدامه في التعبيرين e1 وe2. ويُقيَّم هذان التعبيران مرة واحدة فقط، قبل تنفيذ الحلقة. ويمكن ملاحظة ذلك بالبرنامج التالي:

  let () =
    for i = (Printf.printf "*"; 0) to (Printf.printf "."; 5) do
      Printf.printf "%d" i
    done

عند تنفيذ هذا البرنامج، يعرض السلسلة *.012345. يبدأ تقييم حلقة for بتهيئة الفهرس i بقيمة التعبير (Printf.printf "*"; 0). ويؤدي تقييم هذا التسلسل أولًا إلى طباعة الرمز *. ثم تُعاد القيمة الصحيحة 0. وتشير كون المحرف المطبوع الثاني نقطة . إلى أن التعبير (Printf.printf".";5)، الذي يوافق القيمة النهائية للفهرس، يُقيَّم بعد ذلك. وبما أن بقية الرسالة لا تحوي سوى الأعداد التي يعرضها التعبير Printf.printf "%d" i من جسم الحلقة، فيمكن استنتاج أن التعبيرين e1 وe2 لا يُقيَّمان مرة أخرى. ومن المهم أيضًا ملاحظة أنه إذا كانت قيمة e1 أكبر تمامًا من قيمة e2، فلن يُنفَّذ جسم الحلقة أبدًا.

توجد أيضًا صيغة من البنية for تسير بالاتجاه المعاكس. على سبيل المثال، يعرض البرنامج التالي الأعداد 9876543210 بهذا الترتيب.

  let () =
    for i = 9 downto 0 do
      Printf.printf "%d " i
    done

لاحظ أن الفهرس يمكن أن يزداد أو ينقص بمقدار 1 فقط في كل تكرار. ولتحقيق زيادات أخرى، يمكن استخدام حلقة while، التي ستُناقَش لاحقًا.

من باب الاستيفاء، لنلاحظ أن جسم حلقة for في البرنامج 2 لا يستخدم فهرس الحلقة k. ويمكن لمترجم أوسمل كشف ذلك وإصدار تحذير، إذا أضفنا خيار سطر الأوامر -w +a:

  > ocamlopt -w +a -o approx_pi approx_pi.ml
  Warning 35 [unused-for-index]: unused for-loop index k.

يتمثّل أحد الحلول في تجنّب تسمية فهرس الحلقة، باستبداله بشرطة سفلية _.

  for _ = 1 to n do

لا يغيّر هذا سلوك حلقة for بأي شكل.

2.3 رسم قلب (cardioid)

برنامجنا الثالث (انظر الصفحة 62)، cardioid.ml، يرسم قلبًا (cardioid)، وهو منحنى يمثّل مسار نقطة ثابتة على دائرة تدور حول دائرة ثانية بالقطر نفسه، كما هو مبيّن في الشكل 2.2.

الشكل 2.2: رسم قلب (cardioid).

PIC

رياضيًا، القلب (cardioid) منحنى جبري مستوٍ يمكن تعريفه بالمعادلتين الوسيطيتين (parametric equations) التاليتين: {x(θ)=a(1−sin(θ))cos(θ)y(θ)=a(1−sin(θ))sin(θ)\begin{cases} x(\theta ) = a(1 - sin(\theta )) cos(\theta ) y(\theta ) = a(1 - sin(\theta )) sin(\theta ) \end{cases}

حيث a هو نصف قطر كل دائرة.

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

  open Graphics

وبهذا سنتمكن من استخدام قيم هذه المكتبة ودوالها دون الحاجة إلى إضافة اسم الوحدة Graphics كسابقة في كل مرة.

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

  let () = open_graph " 300x200"

تفتح هذه التعليمة نافذة بحجم 300 × 200، أي بعرض 300 بكسل وارتفاع 200 بكسل. (لاحظ أن الفراغ في بداية السلسلة إلزامي.) ثم نرسم داخل هذه النافذة باستخدام إحداثيات صحيحة، حيث يقع أصل الإحداثيات في أسفل يسار النافذة، وتأخذ إحداثيات x القيم من 0 إلى 299 وإحداثيات y من 0 إلى 199 (انظر الشكل 2.3).

0x0yxy∙2199-a-a99xxiiss

الشكل 2.3: نظام إحداثيات مكتبة الرسوميات.

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

  let () = ...

تعتمد الدوال التي سنستخدمها لرسم القلب على مفهوم النقطة الحالية. ويمكن تحديد موضع هذه النقطة باستخدام moveto. ويقوم استدعاء lineto x y برسم قطعة مستقيمة من النقطة الحالية إلى النقطة ذات الإحداثيات (x,y)، التي تصبح بعد ذلك النقطة الحالية الجديدة.

نبدأ بوضع النقطة الحالية عند (200,150)، باستدعاء الدالة moveto، بغية رسم قلب يبدأ من هذه النقطة:

    moveto 200 150;

نستخدم حلقة for لتغيير الزاوية 𝜃 بين 0 و2π. ولتحقيق ذلك، نستعمل فهرسًا صحيحًا i يتغيّر من 0 إلى 200، ونستفيد من أن arctan(1) = π∕4 لحساب 𝜃 كـ arctan(1) × i∕25.

    for i = 0 to 200 do
     let th = atan 1. *. float i /. 25. in
     ...
    done

في أوسمل، يُحسَب ظل الزاوية للقوس (arctangent)، معبَّرًا عنه بالراديان، باستخدام الدالة atan من المكتبة القياسية Stdlib.

يُعرِّف السطر التالي متغيرًا محليًا r بقيمة التعبير الجزئي الوسيط a(1 − sin(𝜃))، حيث يُثبَّت نصف قطر القلب a عند 50 بكسل:

    let r = 50. *. (1. -. sin th) in

يُستخدَم هذا المتغير لإخراج جزء من حساب إحداثيات النقطة (x(𝜃),y(𝜃)).

أخيرًا، باستخدام الدالة lineto، نرسم قطعة مستقيمة بين النقطة الحالية والنقطة ذات الإحداثيات (x(𝜃),y(𝜃)). وبما أن الإحداثيات الرسومية أعداد صحيحة، نستخدم الدالة truncate لاستخراج الجزء الصحيح من التعبيرات المستخدمة في حساب الإحداثيات.

    lineto (150 + truncate (r *. cos th))
           (150 + truncate (r *. sin th))

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

    ignore (read_key())

بما أننا ننتظر فقط ضغط مفتاح، فإننا نتجاهل المحرف الفعلي الذي تُعيده الدالة read_key باستخدام الدالة المعرَّفة مسبقًا ignore.

الترجمة

من أجل ترجمة البرنامج cardioid.ml، يجب أن نخبر المترجم صراحةً بأننا نرغب في استخدام مكتبة Graphics. ولا حاجة إلى ذلك في حالة الوحدات التي رأيناها سابقًا، مثل Sys وArg وPrintf، التي تنتمي إلى المكتبة القياسية لأوسمل. ومكتبة Graphics موجودة في الملف graphics.cmxa، الذي يجب إضافته إلى سطر الأوامر. وعلاوةً على ذلك، يجب أن نخبر المترجم بموقع هذا الملف، الذي نصّبه opam. ويمكن القيام بذلك باستخدام الأمر التالي:

  > ocamlopt -I ‘ocamlfind query graphics‘ graphics.cmxa cardioid.ml -o cardioid

تتيح أداة ocamlfind إيجاد موقع مكتبة graphics، الذي يُمرَّر بعد ذلك إلى مترجم أوسمل باستخدام الخيار -I. (لاحظ أنه يجب وضع الأمر ocamlfind query graphics بين علامتي اقتباس خلفية.) وإذا رغبت في استخدام المترجم ocamlc، فينبغي أن تستبدل اللاحقة .cmxa بـ .cma. وكما سنرى في القسم 2.10 بريك أوت بدون طوب (Breakout without Bricks)، فإن ترتيب الملفات على سطر أوامر المترجم مهم: هنا، يجب أن يظهر graphics.cmxa قبل cardioid.ml لأن الأخير يستخدم مكتبة Graphics.

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

  (executable
   (name cardioid)
   (libraries graphics))

يحدّد هذا أننا نرغب في بناء ملف تنفيذي اسمه cardioid، ويستخدم مكتبة graphics. وبافتراض أن ملفَّينا cardioid.ml وdune موجودان في الدليل my-first-project/، يجب أولًا تنفيذ خطوة تهيئة بالأمر التالي:

  > dune init project my-first-project/

يمكننا بعد ذلك الانتقال إلى الدليل my-first-project/ وبناء الملف التنفيذي هناك:

  > cd my-first-project/
  > dune build

أخيرًا، يمكننا تنفيذ البرنامج بالأمر التالي:

  > dune exec ./cardioid.exe

يُسمّى الملف التنفيذي cardioid.exe، حيث تُضيف dune الامتداد .exe. وهو مخزَّن في دليل فرعي _build/default/، ويتيح لنا الأمر dune exec تشغيله مباشرةً.

لاستخدام مكتبة Graphics من داخل الطرفية التفاعلية ocaml، يكفي كتابة الأمر التالي في الطرفية:

  > ocaml -I ‘ocamlfind query graphics‘ graphics.cma
  OCaml version 4.14.0
  #

لاحظ أن مكتبة Graphics يمكن أيضًا استخدامها مباشرةً من داخل TryOCaml.

مكتبة الرسوميات

إضافةً إلى الدالتين moveto وlineto المستخدمتين في برنامجنا cardioid.ml، تقدّم مكتبة Graphics دوال أخرى متنوعة: plot لرسم نقطة؛ وset_color لتعديل لون العرض؛ وdraw_circle لرسم دائرة؛ وset_line_width لتغيير سماكة الخط؛ وfill_rect لتظليل مستطيل؛ وdraw_string لعرض سلسلة نصية، وغيرها. نُحيل القارئ إلى الصفحة الإلكترونية لدليل أوسمل للحصول على وصف كامل لهذه المكتبة. ومن المهم ملاحظة أنه، على الرغم من أن ميزات Graphics محدودة، فإن لهذه المكتبة ميزة كونها متاحة على معماريات عديدة. وإذا رغبت في استخدام مكتبة أكثر تطورًا، فيمكنك استخدام (حسب نظام تشغيلك):

  • OCaml-Canvas: إطار عمل Canvas محمول لأوسمل، بواجهة مشابهة لـ HTML5 Canvas.
  • LablTk: مكتبة Tcl/Tk تتيح إنشاء واجهات رسومية (GUI) بقوائم منسدلة وأزرار وغيرها.
  • LablGtk: تشبه LablTk لكنها مبنية على مكتبة الرسوميات Gtk.
  • OCamlsdl: مكتبة SDL تُستخدَم أساسًا لإنشاء ألعاب الفيديو.

هذه القائمة ليست شاملة.

2.4 مجموعة ماندلبروت (Mandelbrot set)

يُرسِم البرنامج 4 (انظر الصفحة 80) مجموعة ماندلبروت (انظر الشكل 2.4). وتُعرَّف بأنها مجموعة النقاط (a,b) من المستوى التي لا يميل أيٌّ من التتابعين العوديين (recursive sequences) التاليين إلى اللانهاية في قيمته المطلقة.

x0 = 0
y0 = 0
xn+1 = xn2 − yn2 + a
yn+1 = 2xnyn + b

الشكل 2.4: مجموعة ماندلبروت.

على الرغم من عدم وجود طريقة دقيقة لتحديد ما إذا كان هذا الشرط متحققًا، يمكن إثبات أن أحد هذين التتابعين لا بد أن يميل إلى اللانهاية حالما تكون xn2 + yn2 > 4. تتيح لنا هذه النتيجة، أولًا، أن نستنتج أن نقاط مجموعة ماندلبروت تنتمي إلى قرص (disc) نصف قطره 2 ومركزه (0,0). وثانيًا، تمكننا من رسم تقريب لمجموعة ماندلبروت، معرَّفةً بمجموعة النقاط (a,b) التي تحقق xn2 + yn2 ≤ 4 لأول k حدٍّ من هذين التتابعين. ولاحظ أن دقة هذا التقريب تعتمد فقط على عدد الحدود k.

يبدأ البرنامج بتوجيه (directive) openGraphics لتبسيط استخدام دوال مكتبة الرسوميات. ويستمر بتعريف متغيرين عامين width وheight، يحويان على التوالي عرض النافذة الرسومية التي نرغب في فتحها وارتفاعها (هنا 800 × 800):

  let width = 800
  let height = 800

بعد ذلك، نُثبّت القيمة k، أي العدد الأقصى للحدود المطلوب حسابها (ويكفي 100 حدٍّ للحصول على تقريب جيد):

  let k = 100

يُعرِّف الإعلان التالي دالة norm2 تأخذ وسيطين x وy، وتُعيد قيمة التعبير x2 + y2.

  let norm2 x y = x *. x +. y *. y

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

تحدد الدالة التالية، mandelbrot، ما إذا كانت نقطة ذات إحداثيات (a,b) تنتمي إلى مجموعة ماندلبروت، وذلك بحساب أول k حدٍّ من التتابعين العوديين (xn) و(yn). وبطريقة مشابهة لإعلان norm2، نُعلن الدالة mandelbrot بوسيطين a وb على النحو التالي:

  let mandelbrot a b = ...

لحساب حدود التتابعين العوديين، نعرّف دالة محلية عودية mandel_rec بثلاثة وسائط: x وy وi.

     let rec mandel_rec x y i =
      ...
     in

يحوي الوسيطان الأولان x وy من mandel_rec القيمتين رقم i، أي xi وyi، من التتابعين العوديين، ويحوي الوسيط الثالث الفهرس i.

وقبل أن نتناول جسم هذه الدالة، لاحظ أنه، من الناحية الصرفية، يُستخدَم إعلان بالشكل letrec لتعريف دالة عودية، أي دالة يمكنك استخدام اسمها نفسه داخل جسمها. وعلاوةً على ذلك، وكما هو الحال مع إعلانات المتغيرات المحلية، فإن نطاق الدالة المحلية، سواء أُدخلت بالشكل let-rec-in أم let-in ببساطة، يقتصر على التعبير الذي يلي الكلمة المفتاحية in.

يبدأ جسم الدالة mandel_rec باختبار لتحديد ما إذا كنا قد وصلنا إلى حساب الحد رقم k من التتابع، أو ما إذا كان شرط الإيقاف xi2 + yi2 > 4 متحققًا:

       if i = k || norm2 x y > 4. then i = k
       else

في الحالتين، تنتهي الدالة mandel_rec وتُعيد قيمة منطقية تشير إلى ما إذا كانت النقطة في المجموعة أم لا. وإذا لم يتحقق أيٌّ من هذين الشرطين، نحسب xi+1 وyi+1 بتطبيق معادلتي التتابعين العوديين، ونخزّنهما في المتغيرين المحليين x’ وy’:

         let x’ = x *. x -. y *. y +. a in
         let y’ = 2. *. x *. y +. b in

ثم نستدعي الدالة mandel_rec مرة أخرى لحساب الحدود التالية:

         mandel_rec x’ y’ (i + 1)
       in

أخيرًا، تبدأ الدالة mandelbrot الحساب باستدعاء الدالة المحلية mandel_rec بالقيمتين الابتدائيتين x0 وy0 كوسيطين:

       in
       mandel_rec 0. 0. 0

لرسم مجموعة ماندلبروت، يكفي أن نجتاز كل صف وكل عمود من النافذة الرسومية، وأن نعرض البكسلات (a,b) التي تُعيد الدالة mandelbrot لها القيمة true.

يحتوي كود الرسم على دالة draw تُعلَن على النحو التالي:

  let draw () = ...

يُستخدَم إعلان بهذا الشكل لتعريف دوال بلا وسائط. وبشكل دقيق، يُعرِّف هذا الإعلان دالة بوسيط وحيد، يُرمَز إليه بـ()، وهو القيمة الوحيدة لنوع خاص، هو unit. وكما سنرى في القسم 2.6 رسم منحنى، هذا مثال على دالة تُعرَّف بواسطة مطابقة الأنماط (pattern matching).

تجتاز الدالة draw صفوف النافذة الرسومية وأعمدتها باستخدام حلقتين for متداخلتين:

    for w = 0 to width - 1 do
      for h = 0 to height - 1 do
        ...
      done
    done

لرسم مجموعة ماندلبروت في نافذة بحجم width×height، نعيد قياس إحداثيات النافذة إلى نقاط (a,b) في الفترة [−2,2] × [−2,2]، حيث يكون a وb متغيرين معرَّفين على النحو التالي:

        let a = 4. *. float w /. float width -. 2. in
        let b = 4. *. float h /. float height -. 2. in

لم يبقَ سوى تحديد ما إذا كانت النقطة (a,b) تنتمي إلى المجموعة، باستدعاء الدالة mandelbrot ورسم النقطة باستخدام الدالة plot:

        if mandelbrot a b then plot w h
      done
    done

لإكمال البرنامج، نفتح نافذة رسومية بحجم width × height ببناء سلسلة نصية بالشكل " wxh" حيث يُستبدَل w وh بالقيمتين المحتوتين في المتغيرين width وheight.

  let () =
    let dim = Printf.sprintf " %dx%d" width height in
    open_graph dim;

تُبنى السلسلة النصية باستدعاء الدالة Printf.sprintf بسلسلة تنسيق "``%``dx``%``d" والوسيطين width وheight. والدالة Printf.sprintf مشابهة للدالة printf، إلا أنها تُعيد السلسلة نتيجةً بدلًا من عرضها.

أخيرًا، نرسم مجموعة ماندلبروت باستدعاء الدالة draw. ثم ننتظر حتى يُضغَط مفتاح لإنهاء البرنامج:

    draw ();
    ignore (read_key ())

لاحظ أن الصياغة نفسها تُستخدَم في استدعاء الدالة draw كما تُستخدَم في إعلانها.

إعلانات الدوال

لنعد إلى مفهوم الدالة في أوسمل. تُعلَن الدالة بالكلمة المفتاحية let. وهكذا، تُكتب دالة عامة f تربط x بـ x + 1 ببساطة على النحو التالي:

  # let f x = x + 1;;
  val f : int -> int = <fun>

وكما هو الحال مع المتغيرات، يُستنتَج نوعها تلقائيًا. وبشكل أدق، يُستنتَج نوع وسيطها (هنا int) ونوع نتيجتها (وهو أيضًا int) معًا. ونوع f بالشكل int->int، حيث يكون النوع الواقع على يسار السهم -> هو نوع الوسيط، والنوع الواقع على يمينه هو نوع النتيجة. غير أن قيمة f لا تُعرض. ولا يُعرض سوى ``، ما يدل على أنها دالة.

يمكن أن تكون الدوال محلية، وتخضع لقواعد النطاق نفسها التي تخضع لها المتغيرات.

  # let sqr x = x * x in sqr 3 + sqr 4;;
  - : int = 25
  # (let sqr x = x * x in sqr 3) + sqr 4;;
  Error: Unbound value sqr

افتراضيًا، لا تكون الدوال عودية.

  # let fact x = if x = 0 then 1 else x * fact (x-1);;
  Error: Unbound value fact

يجب استخدام البنية letrec صراحةً لتعريف دالة عودية.

  # let rec fact x = if x = 0 then 1 else x * fact (x-1);;
  val fact : int -> int = <fun>
  # fact 10;;
  - : int = 3628800

لاحظ أننا كتبنا في المثال السابق fact(x-1) وليس factx-1. فالتعبير الثاني يُفهم على أنه (factx)-1، لأن تطبيق الدالة هو المعاملة ذات الأسبقية الأعلى.

يجب تعريف الدوال العودية المتبادلة بشكل متزامن باستخدام الكلمة المفتاحية and. على سبيل المثال، يمكننا تعريف دالتين عوديتين متبادلتين f وg على النحو التالي:

  let rec f x = ... g ...
  and     g x = ... f ...

يمكن أن تأخذ الدالة عدة وسائط، تُكتَب متجاورة ببساطة في التعريف وعند الاستدعاء. على سبيل المثال، يُعرِّف الإعلان التالي دالة plus بوسيطين:

  # let plus x y = x + y ;;
  val plus : int -> int -> int = <fun>
  # plus 3 4;;
  - : int = 7

النوع الذي يستنتجه أوسمل لهذه الدالة هو int->int->int. وإضافة أقواس تُنتج النوع int->(int->int) (المعاملة -> ترابطية يمنى (right-associative))، الذي يُقرأ على النحو التالي: «دالة تأخذ قيمة من النوع int وتُعيد دالة من النوع int إلى int». ولذلك تُرى الدالة plus على أنها دالة بوسيط واحد تُعيد دالة تنتظر الوسيط الثاني. وهكذا، بالمعنى الدقيق، لا تملك أوسمل دوالًا تأخذ عدة وسائط. فما توجد إلا دوال عالية الرتبة (higher-order) بوسيط واحد، أي دوال تأخذ وسيطًا واحدًا وتُعيد دالة أخرى. وسنتناول مثل هذه الدوال لاحقًا (القسم 2.6 رسم منحنى).

2.5 غربال إراتوستينس (Sieve of Eratosthenes)

يحدد برنامجنا التالي (انظر الصفحة 88) أولية الأعداد الصحيحة n ≤ N بالنسبة إلى عدد صحيح معطى N. وللقيام بذلك، يستخدم خوارزمية تُسمّى غربال إراتوستينس (sieve of Eratosthenes). فلنوضّح كيف تعمل من أجل N = 23. نكتب جميع الأعداد الصحيحة من 0 إلى N، ثم نحذف تدريجيًا جميع الأعداد الصحيحة غير الأولية. ومن هنا جاء اسم الغربال. ونبدأ بملاحظة أن 0 و1 ليسا أوليين.

بعد ذلك، نحدد أول عدد صحيح لم يُحذف بعد، ألا وهو 2. فنحذف جميع مضاعفاته، أي جميع الأعداد الزوجية الأكبر من 2. وهذه مظلَّلة أدناه.

ثم نكرر العملية. العدد الصحيح التالي الذي لم يُحذف بعد هو 3. فنحذف جميع مضاعفات 3، كما هي مظلَّلة أدناه.

لاحظ أن بعض الأعداد الصحيحة سبق حذفها (مضاعفات 6 في هذه الحالة).

العدد الصحيح التالي الذي يجب أخذه في الاعتبار هو 5. وبما أن 5 × 5 > 23، يكون الغربال قد اكتمل: فجميع مضاعفات 5، أي k × 5، إما حُذفت (إذا كان k < 5) وإما أكبر من 23 (إذا كان k ≥ 5). والأعداد الصحيحة المتبقية هي الأعداد الأولية الأصغر من أو تساوي N: 2 و3 و5 و7 و11 و13 و17 و19 و23.

ينفّذ البرنامج sieve.ml غربال إراتوستينس لقيمة N تُدخَل على الدخل القياسي. نخزّن هذه القيمة في متغير max.

  let max = read_int ()

ثم ننشئ مصفوفة من القيم المنطقية prime حجمها max+1. ولهذا الغرض، نستخدم دالة المكتبة Array.make. وهي تأخذ كوسيطين حجم المصفوفة وقيمة افتراضية لعناصرها، هي هنا true.

  let prime = Array.make (max + 1) true

تذكّر أن المصفوفات تُفهرس بدءًا من 0. وبالتالي، فإن فهارس المصفوفة prime هي الأعداد الصحيحة من 0 إلى max، وكلاهما مشمول. ونبدأ بالإشارة إلى أن العددين 0 و1 ليسا أوليين، بإسناد القيمة false إلى العنصرين الموافقَين من المصفوفة prime.

  let () =
    prime.(0) <- false;
    prime.(1) <- false;

ولهذا، استخدمنا البنية t.(i). وكان يمكننا أيضًا أن نكتب Array.setprime0false`.

نواصل البرنامج بتحديد أكبر عدد يجب أخذه في الاعتبار. هذا العدد هو ⌊⌋، الذي يمكن حسابه على النحو التالي:

    let limit = truncate (sqrt (float max)) in

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

    for n = 2 to limit do
      if prime.(n) then begin
        ...
      end

تُقدّم البنية begin-end كتلة (block)، أي جزءًا من البرنامج محدَّدًا، يُشار إليه هنا بنقاط الحذف. وفي أوسمل، لا يوجد تمييز بين التعبيرات والتعليمات؛ فلا توجد إلا تعبيرات. والجزء المحدَّد من الكود ليس إذن سوى تعبير؛ وكان يمكن تحديده بأقواس. ورغم ذلك، تُبرز استخدام begin-end الطابع الأمرّي (imperative) لهذا التعبير.

لنناقش الآن هذه الكتلة. فهي تتكون من حلقة ثانية تحذف جميع مضاعفات n في المصفوفة prime. والمنطق نفسه الذي يتيح لنا إيقاف الغربال حالما يكون n×n > N يتيح لنا أيضًا بدء الحذف من n×n (بدلًا من 2n)، لأن المضاعفات الأصغر سبق حذفها. وللتكرار على جميع المضاعفات الصحيحة لـ n انطلاقًا من n2، نهيّئ مرجعًا m بالقيمة الابتدائية:

        let m = ref (n * n) in

ثم نستخدم حلقة تُسند false إلى prime.(!m) وتزيد m بمقدار n، ما دام التعبير !m<=max متحققًا. تُكتب مثل هذه الحلقة باستخدام بنية while، على النحو التالي:

        while !m <= max do
          prime.(!m) <- false;
          m := !m + n
        done

لاحظ أنه، كما في حالة حلقة for,يُحدَّد جسم حلقة while بالكلمتين المفتاحيتين do وdone.

بهذا يكتمل الغربال. وتشير قيم المصفوفة prime الآن إلى الأعداد الأصغر من أو تساوي max التي تكون أولية. ويمكننا عرض هذه الأعداد الأولية باستخدام حلقة أخرى.

  let () =
    for n = 2 to max do
      if prime.(n) then Printf.printf "%d\n" n
    done

كان يمكننا بدلًا من ذلك عرض الأعداد الأولية عند العثور عليها، أي أثناء تنفيذ الغربال. غير أن حلقة الغربال تتوقف عندما يكون n = ⌊⌋، لذلك كانت ستلزم حلقة أخرى على أي حال لعرض الأعداد الأولية الواقعة بين ⌊⌋ + 1 وmax.

معلومات إضافية

نعود هنا إلى البنيتين while وbegin-end المقدَّمتين في هذا القسم، ثم نتناول المصفوفات.

حلقة while

بشكل عام، صياغة حلقة while هي:

  while e1 do
   e2
  done

يجب أن يكون التعبير e1 من النوع bool والتعبير e2 من النوع unit.

كتلة begin-end

البنية begin-end مكافئة لزوج من الأقواس. وهكذا، يمكنك كتابة:

  # 2 * begin 1 + 2 end;;
  - : int = 6

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

المصفوفات

يمكن بناء مصفوفة صراحةً بتحديد القيم المكوِّنة لها.

  # let t = [| 12; 32; 3; 8 |];;
  val t : int array = [|12; 32; 3; 8|]

لتخصيص مصفوفة بحجم اعتباطي، وبوجه خاص غير معروف ساكنًا (statically)، نستخدم دالة المكتبة Array.make. وهي تأخذ كوسيطين حجم المصفوفة وقيمة تُستخدَم لتهيئة جميع خلاياها. (وكما هو الحال مع أي قيمة في أوسمل، يجب أن تُهيَّأ المصفوفة.)

  # let u = Array.make 1024 ’a’;;
  val u : char array = [|’a’; ’a’; ’a’; ... |]

يمكن الحصول على حجم مصفوفة باستخدام دالة المكتبة Array.length.

  # Array.length u;;
  - : int = 1024

لاحظ أخيرًا أن الوصول إلى مصفوفة بفهرس يقع خارج نطاق الفهارس الصالحة يُنتج خطأً وقت التنفيذ، يُشار إليه باستثناء (exception):

  # u.(4012);;
  Exception: Invalid_argument "index out of bounds".

ستُناقَش الاستثناءات بالتفصيل لاحقًا.

المصفوفات (matrices)

لا يوجد نوع معرَّف مسبقًا للمصفوفات (matrices)، ولا، بشكل أعم، للمصفوفات متعددة الأبعاد (multidimensional arrays). فنستخدم ببساطة مصفوفات من المصفوفات. خذ على سبيل المثال المصفوفة:

()10M=(23)( ) 1 0 M = ( 2 3 )

تُمثَّل بالتعبير:

  # let m = [| [| 1; 0 |];
               [| 2; 3 |] |];;
    val m : int array array = [|[|1; 0|]; [|2; 3|]|]

يُوصَل إلى العنصر Mi,j باستخدام m.(i).(j)، وهو ليس سوى عمليتي وصول متتاليتين: أولًا، نصل إلى الصف i باستخدام m.(i)، ثم إلى عنصره الواقع عند الفهرس j.

  # m.(1).(0);;
  - : int = 2

تُنفَّذ جميع العمليات على المصفوفات باستخدام عمليات المصفوفات. ومع ذلك، تقدّم الوحدة Array عملية لإنشاء مصفوفة، هي make_matrix، تأخذ كوسائط أبعاد المصفوفة والقيمة الابتدائية لعناصرها. وسنعود إلى المصفوفات في القسم 10.4 حساب المصفوفات من الفصل 10.

الاسم المستعار (aliasing)

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

يُحصل على مثال نموذجي للاسم المستعار بتخصيص مصفوفة مهيَّأة جميع عناصرها بالمصفوفة نفسها. خذ التعبير التالي:

  Array.make 3 (Array.make 4 v)

قد تظن أنك تبني مصفوفة 3 × 4، كل عنصر من عناصرها هو v. وفي الواقع، يبني هذا التعبير مصفوفة واحدة حجمها 4 —لنسمِّها a— عناصرها لها القيمة v، ومصفوفة حجمها 3، عناصرها الثلاثة هي نفسها المصفوفة a. وبعبارة أخرى، تكون النتيجة على النحو التالي:

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

2.6 رسم منحنى

برنامجنا السادس (انظر الصفحة 104)، plot.ml، يرسم منحنى محدَّدًا بمجموعة من النقاط في المستوى. وتقوم الخوارزمية على وصل هذه النقاط بقطع مستقيمة (line segments)، متجهين بترتيب تزايدي لإحداثياتها السينية. فعلى سبيل المثال، يُعرض المنحنى المرسوم لمجموعة النقاط {(20,15),(2,2),(30,10),(10,15)} في الشكل 2.5.

0x0y11∙2∙22∙3∙1--05000aaxxiiss

الشكل 2.5: رسم منحنى.

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

  let n = read_int ()

بعد ذلك، نعرّف دالة تقرأ إحداثيات نقطة من الدخل القياسي:

  let read_pair () =
    let x = read_int () in
    let y = read_int () in
    (x, y)

بعد قراءة العدد الصحيح الأول، x، والثاني، y، من الدخل القياسي باستدعاءين للدالة read_int، تُعيد الدالة read_pair زوج الأعداد الصحيحة (x,y)، المُنشأ بشكل طبيعي جدًا باستخدام الصياغة (x,y). ويُكتب نوع هذا الزوج على شكل int*int في أوسمل. وسنناقش الأزواج، وبشكل أعم الثنائيات (n-tuples)، بمزيد من التفصيل في نهاية هذا القسم.

ننشئ بعد ذلك مصفوفة data بحجم n، نهيّئها بأزواج الأعداد الصحيحة المقروءة من الدخل القياسي. وللقيام بذلك، نستخدم دالة المكتبة Array.init التي تأخذ كوسيطين حجم المصفوفة ودالة تُستخدَم لتهيئة خلايا المصفوفة:

  let data = Array.init n (fun i -> read_pair ())

يوضح استدعاء الدالة Array.init مفهومين جديدين. أولًا، التعبير funi->... الممرَّر كوسيط إلى Array.init هو دالة مجهولة (anonymous). ويمثل الرمز i الواقع يسار السهم -> وسيط الدالة، أما التعبير الواقع يمينه فجسم (body) الدالة. ثانيًا، يُظهر هذا الاستدعاء أن الدوال في أوسمل قيم مثلها مثل أي قيم أخرى. ونقول أيضًا إنها قيم من الدرجة الأولى (first-class). يمكن تمريرها كوسائط، وكما سنرى لاحقًا، إعادتها كناتج لدوال أخرى. والدالة مثل Array.init التي تأخذ دالة كوسيط، تُسمّى دالة من الرتبة الأعلى (higher-order).

تُعيد الدالة Array.init مصفوفة تُحصَل عليها بتهيئة الخلية ذات الرقم k (المتراوح من 0 إلى n− 1) بالقيمة الناتجة عن تطبيق الدالة (funi->read_pair()) على k.

وهكذا، إذا كانت الأعداد الصحيحة المُدخَلة على الدخل القياسي مؤلفة من المتتالية 420152230101015، فتعريف الإعلانات السابقة متغيرًا n يحتوي العدد الصحيح 4 ومصفوفة data تُعرض محتوياتها بيانيًا على النحو التالي:

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

  let compare (x1, y1) (x2, y2) = x1 - x2

تُعيد هذه الدالة عددًا صحيحًا. ويفسّر خوارزم الفرز (sorting algorithm) إشارته على النحو التالي:

  • إذا كان x1 - x2 = 0، يعدّ الزوجان متساويين؛
  • إذا كان x1 - x2 > 0، يعدّ الزوج الأول أكبر؛
  • إذا كان x1 - x2 < 0، يعدّ الزوج الأول أصغر.

قبل مواصلة وصف برنامجنا، لنتوقف لحظة وننظر في شكل هذا الإعلان.

وسيطا الدالة compare ليسا معرفين بسيطين، بل أنماط (patterns). لكل منهما شكل زوج (xi,yi). ويتيح لنا استخدام الأنماط هنا استرجاع المكونين xi وyi للزوجين الممرَّرين كوسيطين للدالة بسهولة. وهذا إعلان بواسطة مطابقة الأنماط (pattern matching). وهذا الشكل من الإعلان شائع جدًا في برامج أوسمل، وسنستخدمه في مناسبات عديدة في هذا الكتاب.

لفرز المصفوفة، نستخدم الدالة من الرتبة الأعلى Array.sort التي، بالإضافة إلى المصفوفة المراد فرزها، تأخذ كوسيط أول دالة تقارن عناصر المصفوفة. ويتم هذا الفرز في نفس المكان (in-place)، أي مباشرةً داخل المصفوفة data. ولا يُحدث استدعاء Array.sort سوى آثار جانبية (side effects).

  let () = Array.sort compare data

في نهاية هذا الاستدعاء، تكون محتويات data على النحو التالي:

لا يتبقى سوى رسم المنحنى بوصل النقاط المرتَّبة بهذا الشكل، بقطع مستقيمة نستهل الأمر بتوجيه (directive) openGraphics. ثم نفتح نافذة رسوميات بحجم 200 × 200. ويحدد الاستدعاء set_line_width3 سُمك قطع المستقيمة.

  open Graphics
  let () =
   open_graph " 200x200";
   set_line_width 3;

نسترجِع بعد ذلك الزوج الأول (x0,y0) من الخلية ذات الرقم 0 في المصفوفة data، ونستخدمه لتثبيت إحداثيات النقطة الحالية باستخدام الدالة moveto:

    let (x0,y0) = data.(0) in moveto x0 y0;

هنا أيضًا نستخدم إعلانًا بواسطة مطابقة الأنماط لاستخراج المكونين لزوج مخزَّن في المصفوفة. وتُطابَق القيمة الموجودة في data.(0)

بوساطة النمط (x0,y0)، الذي يعرّف متغيرين محليين x0 و y0.

نمرّ بعد ذلك على جميع عناصر المصفوفة data بمساعدة حلقة for لوصل النقاط:

    for i = 1 to n-1 do
      let (x,y) = data.(i) in
      lineto x y
    done;

يسترجِع جسم الحلقة الإحداثيين (x,y) لكل نقطة باستخدام إعلان محلي بمطابقة الأنماط (مطابق للإعلان أعلاه)، ويرسم خطًا من النقطة الحالية إلى النقطة ذات الإحداثيين (x,y).

معلومات إضافية

الأزواج والثنائيات (pairs and n-tuples)

يمكن إنشاء زوج من قيمتين v1 وv2 باستخدام الترميز التقليدي (v1,v2). ويستخدم نوع الأزواج الترميز الرياضي للجداء الديكارتي (Cartesian product).

  # (1, true);;
  - : int * bool = (1, true)

ستلاحظ أن الفاصلة تُستخدَم لإنشاء الزوج بينما يُستخدَم الرمز * لإنشاء نوع الزوج. ويُكتب الإسقاطان (projections) fst وsnd على التوالي.

  # fst (1 + 2, true);;
  - : int = 3
  # snd (1, not true);;
  - : bool = false

قد تكون الأزواج متداخلة بشكل تعسفي (arbitrarily nested).

  # ((1, true), (3.14, false));;
  - : (int * bool) * (float * bool) = ((1, true), (3.14, false))

الأزواج حالة خاصة من الثنائيات (n-tuples)، وتستخدم الصياغة نفسها للقيم والأنواع.

  # (1, true, 3.14);;
  - : int * bool * float = (1, true, 3.14)

تجدر الإشارة إلى أن النوع (int*int)*int والنوع int*(int*int) و النوع int*int*int ليست متطابقة:

  • الأول هو نوع زوج مكونه الأول زوج؛
  • الثاني هو نوع زوج مكونه الثاني زوج؛
  • الثالث هو نوع ثالوث (triple).
الإسقاطات بمطابقة الأنماط والنمط البديل (wildcard pattern)

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

  # let (x, (y, z), t) = (1, (true, "hello"), 3.4);;
  val x : int = 1
  val y : bool = true
  val z : string = "hello"
  val t : float = 3.4

إذا أردت الوصول إلى مكونات معينة فقط من ثنائية، يمكنك استخدام نمط بديل (wildcard pattern)، يُكتب على شكل _، لتجنب إدخال أسماء متغيرات غير ضرورية. على سبيل المثال، إذا أردت الوصول فقط إلى المكونين x وz من الثالوث أعلاه، يمكنك كتابة مطابقة الأنماط التالية:

  # let (x, (_, z), _) = (1, (true, "hello"), 3.4);;
  val x : int = 1
  val z : string = "hello"

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

  # let (x, _, t) = (1, (true, "hello"), 3.4);;
  val x : int = 1
  val t : float = 3.4
الدوال ذات الوسائط المتعددة والثنائيات

من المهم أيضًا التمييز بوضوح بين دالة ذات وسائط متعددة ودالة تأخذ وسيطًا واحدًا هو ثنائية. لنأخذ، على سبيل المثال، الدالة التالية pyth:

  # let pyth (x, y, z) = x*x + y*y = z*z;;
  val pyth : int * int * int -> bool = <fun>

تأخذ ثالوث أعداد صحيحة كوسيط. ولذلك تستدعيها باستخدام وسيط وحيد بالشكل (e1,e2,e3)، كما في الاستدعاء التالي:

  # pyth (3, 4, 5);;
  - : bool = true

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

  # let pyth x y z = x*x + y*y = z*z;;
  val pyth : int -> int -> int -> bool = <fun>

يجب استدعاء هذه الدالة بمجرد تجاور اسمها مع ثلاثة وسائط، كما في الاستدعاء التالي:

  # pyth 3 4 5;;
  - : bool = true

النوعان int*int*int->bool وint->int->int->bool يوضحان بوضوح الفرق بين هاتين الصيغتين. وفي هذا الكتاب، نعتمد أسلوب كاري (Curry)، الذي تأخذ فيه الدوال n من الوسائط بدلًا من ثنائية واحدة. ويتيح هذا الأسلوب، بوجه خاص، الاستخدام الجزئي (partial application) للدوال: إذ يمكنك تمرير عدد وسائط للدالة أقل مما تتوقعه، والحصول في المقابل على دالة أخرى. على سبيل المثال، بتطبيق الدالة pyth على عدد صحيح، تحصل على دالة تأخذ وسيطين:

  # let f = pyth 3;;
  val f : int -> int -> bool = <fun>

يمكنك بعد ذلك تطبيقها عدة مرات:

  # f 4 5;;
  - : bool = true
  # f 6 7;;
  - : bool = false
السجلات (records)

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

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

يمكننا بعد ذلك إنشاء قيمة من النوع date بالصياغة التالية.

  # let valentine’s_day = { day = 14; month = 2; year = 2014 };;
  val valentine’s_day : date = { day = 14; month = 2; year = 2014 }

نصل إلى الحقل f من سجل e باستخدام الترميز e.f.

  # valentine’s_day.month;;
  - : int = 2

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

  # let d = { valentine’s_day with day = 15 };;
  val d : date = {day = 15; month = 2; year = 2014}

وهذا مطابق للإعلان التالي:

  # let d = { day = 15;
              month = valentine’s_day.month;
              year = valentine’s_day.year };;
  val d : date = {day = 15; month = 2; year = 2014}

من مزايا السجلات الأخرى مقارنة بالثنائيات أن ترتيب الحقول غير ذي أهمية. ولذلك يمكننا كتابة:

  # let us_valentine’s_day = { month = 2; day = 14; year = 2014; };;
  val us_valentine’s_day : date = {day = 14; month = 2; year = 2014}
  # us_valentine’s_day = valentine’s_day;;
  - : bool = true

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

  # let { day; month; year } = valentine’s_day;;
  val day : int = 14
  val month : int = 2
  val year : int = 2014

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

  # let { day; month; _ } = valentine’s_day;;

ومع ذلك، تظل الثنائيات مفيدة، وبوجه خاص لأنها لا تتطلب منا الإعلان عن نوع.

السجلات ذات الحقول القابلة للتعديل (mutable fields)

يصرّح المفتاح mutable عن حقل سجل يمكن تعديله.

  # type student = { number : int; mutable age : int };;
  type student = { number : int; mutable age : int; }

يُعدَّل حقل سجل باستخدام البنية <-.

  # let birthday e = e.age <- e.age + 1;;
  val birthday : student -> unit = <fun>

لا تُعيد هذه العملية قيمة. ولذلك يكون نوعها unit. ونلاحظ هذا الآثار الجانبية في المثال التالي:

  # let e = { number = 123456; age = 21 };;
  val e : student = {number = 123456; age = 21}
  # birthday e;;
  - : unit = ()
  # e;;
  - : student = {number = 123456; age = 22}

يمكننا استخدام سجل ذي حقل mutable لمحاكاة المفهوم التقليدي للمتغير القابل للتعديل. على سبيل المثال، في حالة متغير من النوع int، يكفي الإعلان عن نوع ذي حقل قابل للتعديل وحيد value.

  # type variable = { mutable value : int };;
  type variable = { mutable value : int; }

نستخدم بعد ذلك x.value للوصول إلى محتويات المتغير x، والإسناد x.value<-e لتعديله.

  # let x = { value = 41 };;
  val x : variable = {value = 41}
  # x.value <- x.value + 1;;
  - : unit = ()
  # x.value;;
  - : int = 42

بالمعنى الدقيق، لا نعدّل المتغير x نفسه. إنما نعدّل فقط القيمة الموجودة في السجل الذي يشير إليه x. وبشكل أدق، إنما هو مفهوم المؤشر (pointer) المستخدم هنا.

ولتجنب الاضطرار إلى تعريف نوع من هذا القبيل في كل مرة نحتاج فيها إلى متغير قابل للتعديل، توفّر أوسمل النوع المعرَّف مسبقًا لـالمراجع (references)، الذي استخدمناه بالفعل (انظر القسم 2.2 تقريبπ). ويُنشأ المرجع باستخدام المفتاح ref.

  # let x = ref 41;;
  val x : int ref = {contents = 41}

كما هو واضح، فإن نوع المرجع، المكتوب على شكل intref، هو نوع سجل، ذي حقل وحيد contents. ونصل إلى هذا الحقل باستخدام الترميز !، ونعدّل محتوياته باستخدام الترميز :=.

  # x := !x + 1;;
  - : unit = ()
  # !x;;
  - : int = 42
ترتيب التقييم (evaluation order)

لا تحدد لغة أوسمل ترتيب تقييم مكونات الثنائيات والسجلات. وهكذا، في الزوج (e1,e2)، لا يمكن معرفة مسبقًا ما إذا كان التعبير e1 سيُقيَّم قبل e2 أم بالعكس.

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

  # (read_int (), read_int ());;
  4
  5
  - : int * int = (5, 4)

نلاحظ هنا أن التعبير e2 هو الذي يُقيَّم أولًا، لأن العدد الصحيح الأول المُدخَل، وهو هنا 4، يُخزَّن في المكون الثاني من الزوج.

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

  # let x = read_int () in let y = read_int () in (x, y);;
  4
  5
  - : int * int = (4, 5)
الدوال المجهولة (anonymous functions)

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

  # fun x y -> x + y;;
  - : int -> int -> int = <fun>

ومن المثير للاهتمام ملاحظة أن الإعلانين التاليين متكافئان تمامًا:

  # let f = fun x -> x + 1;;
  val f : int -> int = <fun>
  # let f x = x + 1;;
  val f : int -> int = <fun>

2.7 نسخ ملف

برنامجنا التالي، copy_file.ml، ينسخ محتويات ملف إلى ملف آخر، مع تمرير اسمَي الملفين على سطر الأوامر.

ولهذا، نكتب دالة copy_file تأخذ كوسيطين اسمي الملفين، كسلسلتين نصيتين f1 وf2. نبدأ بفتح قناتين c1 وc2 على الملفين f1

وf2، على التوالي.

  let copy_file f1 f2 =
    let c1 = open_in f1 in
    let c2 = open_out f2 in

تُفتح الأولى، c1، للقراءة والثانية، c2، للكتابة.

ثم ننفّذ حلقة لا نهائية (whiletrue) تقرأ الحروف من c1 وتكتبها إلى c2.

      while true do output_char c2 (input_char c1) done

عندما لا يتبقى أي حرف لقراءته، تُطلق الدالة input_char استثناءً معرَّفًا مسبقًا، ألا وهو End_of_file. يقاطع هذا تنفيذ حلقة while، وبوجه عام تنفيذ البرنامج الجاري، حتى يُلتقط (caught) الاستثناء. وهنا، نلتقط هذا الاستثناء خارج حلقة while مباشرةً، وذلك باستخدام البناء try-with.

  let () =
    try
      while true do ... done
    with End_of_file ->
      close_in c1; close_out c2

معنى البناء try e1 with E -> e2 هو كما يلي: نبدأ بتقييم التعبير e1. وإذا حصلنا على قيمة، فهي قيمة التعبير try-with بأكمله. أما إذا أطلق تقييم e1 الاستثناء E، فإننا نقيّم التعبير e2، ويكون ذلك هو ناتج التعبير ككل. وأخيرًا، إذا أطلق e1 استثناءً غير E، فلا يُلتقط الاستثناء، ويكون التعبير try-with بأسره هو ما يُطلقه.

وفي حالتنا هذه، التعبير e1 حلقة لا نهائية، ولن ينتهي تقييمها أبدًا. غير أنها تنتهي بإطلاق الاستثناء End_of_file، الذي يُلتقط بعد ذلك، فيُغلَق الملفان c1 وc2.

ولا يتبقى بعد ذلك سوى استدعاء الدالة copy_file بالوسيطين الأولين لسطر الأوامر، وهما Sys.argv.(1) وSys.argv.(2).

معلومات إضافية

قنوات الإدخال/الإخراج (input/output channels)

تُمثَّل أجهزة الإدخال/الإخراج بواسطة قنوات (channels). وقنوات الإدخال من النوع المعرَّف مسبقًا in_channel، وقنوات الإخراج من النوع out_channel. وتمثل ثلاث قيم معرَّفة مسبقًا، على التوالي، الدخل القياسي، والخرج القياسي، والخطأ القياسي للبرنامج الجاري تنفيذه: stdin من النوع in_channel، وstdout وstderr من النوع out_channel.

تتوفر دوال للقراءة والكتابة على القنوات. وتقرأ الدالة input_char، من النوع in_channel->char، حرفًا واحدًا من القناة الممرَّرة كوسيط. وهكذا يمكننا قراءة حرف من الدخل القياسي، stdin، على النحو التالي:

  # let c = input_char stdin;;
  a
  val c : char = ’a’

ويمكن استخدام دالة أعم، input، لقراءة n حرفًا من قناة إدخال وتخزينها في موضع معين داخل سلسلة نصية.

وبالمثل، تكتب الدالة output_char، من النوع out_channel->char->unit، حرفًا إلى قناة إخراج. أما الدالة الأعم output، فتكتب سلسلة فرعية معينة. وتوجد أيضًا دالة Printf.fprintf تكتب إلى قناة إخراج، بطريقة مماثلة للدالة Printf.printf التي استخدمناها سابقًا.

يمكن أيضًا التعامل مع الملفات كقنوات. وهكذا، يُفتح ملف للقراءة باستخدام الدالة open_in، من النوع string->in_channel، وللكتابة باستخدام الدالة open_out، من النوع string->out_channel. وترمز السلسلة النصية إلى اسم الملف. وبشكل متماثل، نغلق قناة بالدالتين close_in وclose_out.

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

الترميز (marshalling)

إضافةً إلى الحروف، يمكن استخدام القنوات لقراءة وكتابة قيم أوسمل من أنواع اعتباطية. ويُعرف هذا باسم الترميز (marshalling). وتكتب الدالة output_value قيمة من نوع اعتباطي إلى قناة إخراج.

  # let c = open_out "foo" in
    output_value c (1, 3.14, true);
    close_out c;;
  - : unit = ()

الصيغة المستخدمة خاصة بأوسمل (بل وبنسخته تحديدًا). والدالة التي تقوم بالعملية العكسية هي input_value. وعندما تقرأ قيمة مرمَّزة بالدالة input_value، يُستنتج (inferred) نوعها وفقًا لكيفية استخدامها. ومن الممارسات الجيدة تحديد نوع القيمة المقروءة بتعليق نوع (type annotation). وفيما يلي، نعيد قراءة القيمة المكتوبة في الملف "foo"، محدِّدين أن نوعها هو int*float*bool:

  # let c = open_in "foo";;
  val c : in_channel = <abstr>
  # let v : int * float * bool = input_value c;;
  val v : int * float * bool = (1, 3.14, true)

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

  # let c = open_in "foo";;
  val c : in_channel = <abstr>
  # let v = input_value c in fst (fst v);;

  Process caml-toplevel segmentation fault

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

الاستثناءات (exceptions)

بعض العمليات جزئية (partial)، أي أنها غير معرَّفة لجميع القيم الممكنة لوسائطها. فعلى سبيل المثال، القسمة الصحيحة على الصفر غير معرَّفة. وإذا حاولت، رغم ذلك، إجراء هذه العملية، يُطلق استثناء.

  # 1/0;;
  Exception: Division_by_zero.

لا ينتج عن تقييم التعبير قيمة؛ بل يفشل عند إطلاق الاستثناء، كما تدل الرسالة التي تبدأ بـException. وهنا، Division_by_zero استثناء معرَّف مسبقًا. وهناك استثناء آخر معرَّف مسبقًا في أوسمل، Invalid_argument، يُستخدم غالبًا للإشارة إلى استخدام دالة خارج نطاق تعريفها.

  # Random.int (-4);;
  Exception: Invalid_argument "Random.int".
  # Char.chr 257;;
  Exception: Invalid_argument "Char.chr".

كما يتضح من هذه الأمثلة، ترتبط سلسلة نصية بالاستثناء Invalid_argument، تحدد اسم الدالة التي أطلقت الاستثناء.

إن إطلاق استثناء يقاطع الحساب، كما نرى بتقييم التعبير التالي.

  # print_endline "before"; print_int (1/0); print_endline "after";;
  before
  Exception: Division_by_zero.

ورغم ذلك، يمكن التقاط استثناء لمواصلة التقييم بتعبير آخر. وتستخدم لهذا الغرض البناء trywith، كما يلي:

  # let test x y =
      try let q = x / y in Printf.printf "quotient = %d\n" q
      with Division_by_zero -> Printf.printf "error\n";;
  val test : int -> int -> unit = <fun>
  # test 4 0;;
  error
  - : unit = ()

هنا، نحاول حساب x/y وعرض قيمته. وفي حالة الفشل، أي عندما تستثير القسمة الاستثناء Division_by_zero، نلتقط الاستثناء ونعرض رسالة خطأ. لذلك ينتهي تقييم الدالة test دائمًا بقيمة من النوع unit.

بشكل عام، يُقيَّم التعبير trye1withE->e2 كما يلي:

  • يُقيَّم التعبير e1 أولًا. وإذا لم يُطلق استثناءً، يكتمل الحساب، وتكون قيمته هي قيمة e1.

  • أما إذا أطلق التعبير استثناءً، فثمة احتمالان:

    إذا كان الاستثناء هو E، يستمر التقييم بـe2؛

  • إذا كان الاستثناء غير E، يُنشر (propagated) دون تقييم e2.

في التعبير trye1withE->e2، يجب أن يكون للتعبيرين الفرعيين e1 وe2 النوع نفسه، وهو أيضًا نوع التعبير ككل.

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

  # exception Stop;;
  exception Stop

بدلًا من ذلك، قد يأخذ الاستثناء وسيطًا واحدًا أو أكثر، على سبيل المثال، Invalid_argument:

  # exception Error of string;;
  exception Error of string

لإطلاق استثناء، تستخدم البناء raise. يأخذ هذا البناء استثناءً كوسيط.

  # let f x =
      if x < 0 then raise (Error "negative argument");
      123 mod x;;
  val f : int -> int = <fun>

هنا، يُنشأ الاستثناء بتطبيق المُنشئ (constructor) Error على السلسلة النصية "negativeargument". ويمكنك ملاحظة إطلاق الاستثناء باستدعاء f بوسيط سالِب.

  # f (-1);;
  Exception: Error "negative argument".

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

  # let e = Error "invalid argument";;
  val e : exn = Error "invalid argument"
  # raise e;;
  Exception: Error "invalid argument".

البناء raise ليس سوى دالة تأخذ وسيطًا من النوع exn. ويمكن للتعبير raisee أن يأخذ أي نوع. وفي المثال السابق، يأخذ التعبير raise(Error"invalidargument") النوع unit، لكنه يمكن أن يأخذ أيضًا النوع int إذا أردنا كتابة الدالة f مع else:

  # let f x =
      if x < 0 then raise (Error "invalid argument") else 123 mod x;;
  val f : int -> int = <fun>

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

  try
    while true do
      let st = wait_next_event [Key_pressed] in
      if st.keypressed && st.key = ’q’ then raise Exit;
      ...
    done
  with Exit ->
    close_graph ();
    ...

إن إطلاق الاستثناء Exit يقاطع الحلقة اللانهائية whiletrue. نلتقط الاستثناء، ونغلق النافذة الرسومية بالدالة close_graph، ثم نواصل البرنامج. وقد وردت أمثلة أخرى على استخدام الاستثناءات لتغيير تدفق التحكم في التمرينين 2.15 و5.7.

أخيرًا، لاحظ أن المكتبة القياسية لأوسمل توفر دالتين، failwith وinvalid_arg. عند استدعائهما بسلسلة نصية s، تُطلقان الاستثناءين Failures وInvalid_argument s، على التوالي. وتوفر أوسمل أيضًا بناءً خاصًا assert e، يقيّم تعبيرًا e من النوع bool ويُطلق الاستثناء Assert_failure إذا كان e هو false.

2.8 عكس ترتيب الأسطر في نص

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

  first line
  second line
  third line

بمجرد أن نشير إلى نهاية الدخل (بالضغط، على سبيل المثال، على المفتاحين ctrl وD)، يعرض البرنامج الأسطر بترتيب معكوس:

  third line
  second line
  first line

لتحقيق ذلك، يجب على البرنامج أن يخزن جميع الأسطر المقروءة قبل أن يتمكن من عرضها، لأن أول سطر يُعرض هو آخر سطر يُقرأ. لذلك، نحتاج إلى بنية بيانات (data structure) لتخزين الأسطر المقروءة. والمصفوفة غير مناسبة لأننا لا نعرف العدد الإجمالي للأسطر[2]. لذا سنستخدم قائمة (list).

توفر أوسمل نوعًا مدمجًا (built-in) للقوائم. وتُنشأ القوائم من القائمة الفارغة، الممثلة بـ[]، وبإضافة عنصر x إلى مقدمة قائمة موجودة l، ممثلة على الشكل x :: l. والقوائم في أوسمل غير قابلة للتعديل (immutable): بمجرد إنشاء قائمة، لا يعود من الممكن تعديلها.

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

  let lines = ref []

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

    while true do lines := read_line () :: !lines done

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

نلتقط هذا الاستثناء خارج الحلقة مباشرةً:

    try  while true do ... done
    with End_of_file -> ()

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

  let rec print l =

تفحص هذه الدالة القائمة l، معالِجةً حالة القائمة الفارغة وحالة القائمة التي تحتوي عنصرًا واحدًا على الأقل، بشكل منفصل. ونميّز بين الحالتين باستخدام بناء أوسمل match-with، كما يلي:

    match l with
    | []     -> ...case 1...
    | s :: r -> ...case 2...

يُقرأ هذا البناء الخاص بمطابقة الأنماط كما يلي: إذا كانت القائمة l على الشكل []، أي إذا كانت هي القائمة الفارغة، نقيّم الكود المشار إليه أعلاه بـ...case 1.... وإذا كانت القائمة l، مع ذلك، على الشكل s::r، أي إذا كانت تحتوي عنصرًا أول s يليه عناصر أخرى تشكل قائمة r، نقيّم الكود المشار إليه أعلاه بـ...case 2.... وهنا، يأخذ المتغيران s وr قيمة العنصر الأول وبقية عناصر l. وفي الدالة print، لا نفعل شيئًا في الحالة الأولى. وفي الحالة الثانية، نعرض السلسلة النصية s ثم نستدعي print بشكل عودي على القائمة r. لذلك، يكون جسم الدالة print كما يلي:

    match l with
    | []     -> ()
    | s :: r -> print_endline s; print r

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

  let () = print !lines

معلومات إضافية

القوائم (lists)

نوع القوائم معرَّف مسبقًا في أوسمل؛ وهو list. وهذا النوع عام (generic)، بمعنى أننا نستطيع إنشاء قوائم من قيم من أي نوع كان، شريطة أن تكون جميع عناصر قائمة معينة من النوع نفسه.

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

  # 1 :: ’a’ :: 3 :: [];;
  Error: This expression has type char but an expression
         was expected of type int

كما نرى في المثال الأول، تعرض الطرفية التفاعلية قائمة على الشكل [1;2;3]. وهذا الترميز يمكن استخدامه أيضًا لإنشاء قائمة من عناصرها.

  # [’a’; ’b’; ’c’];;
  - : char list = [’a’; ’b’; ’c’]
مطابقة الأنماط (pattern matching)

عندما عرضنا الثنائيات (n-tuples)، شرحنا أنه يمكن تفكيك الأزواج باستخدام البناء let(x,y)=e1ine2. في الواقع، هذه المطابقة مطابقة تمامًا، من كل وجه، لتلك التي ناقشناها أعلاه بخصوص القوائم. والبناء let ليس سوى اختصار للتعبير matche1with(x,y)->e2. وبشكل عام، يمكن استخدام البناء let بنمط اعتباطي كوسيط أول، حتى لو كان النمط في أغلب الأحيان مختزلًا إلى متغير.

تعمل الدالة print بواسطة مطابقة الأنماط على وسيطها l. وهذه الدوال شائعة جدًا في أوسمل حتى إن هناك كلمة مفتاحية، function، تقدّم دالة تعمل بواسطة مطابقة الأنماط على وسيطها. وهكذا، يمكننا أن نكتب:

   let rec print = function
    | []     -> ()
    | s :: r -> print_endline s; print r

بعبارة أخرى، الكلمة المفتاحية function اختصار لـfunx->matchxwith. لاحظ أيضًا أن function تقدّم دالة بوسيط واحد فقط، حيث يمكن لمطابقة الأنماط أن تحتوي على نمط واحد أو أكثر. وفي المقابل، تعرّف fun دالة بعدة وسائط، حيث يُطابَق كل وسيط بنمط واحد. وهكذا، يمكننا أن نكتب:

  fun x (y, z) -> x + y * z
اجتياز القوائم (list traversals)

الدالة print التي كتبناها لعرض جميع عناصر القائمة !lines هي مثال على اجتياز قائمة (traversal)، حيث تُعامل جميع عناصر القائمة بالطريقة نفسها، وبالترتيب الذي تظهر به. وهذه الاجتيازات متكررة جدًا حتى إن هناك دالة مكتبة لها، ألا وهي List.iter. وهذه دالة من الرتبة الأعلى، مثل Array.init أو Array.sort، اللتين عرضناهما سابقًا. تأخذ List.iter كوسيط الدالة التي ينبغي تطبيقها على كل عنصر. وهكذا، يمكننا إعادة كتابة print ببساطة على النحو التالي:

  let print l = List.iter print_endline l

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

  let () = List.iter print_endline !lines
مكدس الاستدعاءات (call stack)

لنفترض أننا نريد لبرنامجنا أن يعرض العدد الإجمالي للأسطر التي تمت قراءتها وعكسها، في رسالة من الشكل:

  113 lines read

لهذا، نكتب دالة length تحسب طول قائمة. وكما هو الحال مع print، نكتبها في شكل دالة عودية تعمل بمطابقة الأنماط:

  let rec length = function
    | []     -> 0
    | _ :: r -> 1 + length r

لاحظ النمط البديل (wildcard pattern) _ المستخدم مكان العنصر الأول من القائمة في النمط الثاني. لا يلزم تسمية هذه القيمة لأنها لا تُستخدم في حساب طول القائمة. ولا يتبقى الآن سوى عرض الطول المحسوب بهذه الطريقة:

  let () = Printf.printf "%d lines read\n" (length !lines)

إذا شغّلنا البرنامج عدة مرات، سنلاحظ أنه يعطي فعلًا النتيجة المتوقعة. غير أننا لو حاولنا إمداد البرنامج بعدد كبير جدًا من الأسطر—لنقل 700,000 سطر—سنفاجأ بمفاجأة غير سارة: سيُعطينا البرنامج خطأً[3] حتى مع أن كل شيء عمل بشكل جيد تمامًا إلى غاية النقطة التي حاولنا فيها عرض عدد الأسطر:

  seq 700000 | ./tac
  Fatal error: exception Stack_overflow

لتفسير هذه الظاهرة، من الضروري فهم المبدأ الكامن وراء تنفيذ دالة عودية مثل length.

لنأخذ على سبيل المثال تنفيذ الاستدعاء length[1;2;3]. يمكننا «رمزيًا» فكّ هذا الاستدعاء كما يلي:

  length [1; 2; 3] = 1 + length [2; 3]
                   = 1 + (1 + length [3])
                   = 1 + (1 + (1 + length []))
                   = 1 + (1 + (1 + 0))
                   = 1 + (1 + 1)
                   = 1 + 2
                   = 3

يخصص كل استدعاء لـlength خلية ذاكرة لتخزين وسيط الدالة. وبشكل عام، يخصص استدعاء دالة، سواء أكان عوديًا أم لا، مساحة الذاكرة الضرورية لوسائطها ومتغيراتها المحلية. وتُحرَّر هذه المساحة بمجرد انتهاء استدعاء الدالة. وفي حالة الدالة العودية length، لا ينتهي الاستدعاء حتى يكتمل الاستدعاء العودي وتُجرى عملية الجمع 1+.... وبوجه خاص، يتطلب الاستدعاء length[1;2;3] حتى أربعة استدعاءات دوال متداخلة للوصول إلى الاستدعاء الأخير length[]. وهكذا، ستكون هناك حاجة إلى أربع خلايا ذاكرة لتخزين وسائط كلٍّ من الاستدعاءات الأربعة، كما هو موضح في الشكل 2.6.

الشكل 2.6: تمثيل مكدس الاستدعاءات.

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

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

الاستدعاءات الذيلية (tail calls)

قد تتساءل لماذا لا يسبب الاستدعاء print!lines فيضان مكدس، على عكس length!lines. الفرق بين الدالتين هو أنه، في الدالة print، يكون الاستدعاء العودي آخر تعبير يُقيَّم في جسم الدالة. وهذا ليس هو الحال في الدالة length، حيث تبقى عملية جمع لإجرائها بعد الاستدعاء العودي. وفي حالة print، يقوم المترجم بتحسين (optimization) يتمثل في إزالة الاستدعاء الحالي من مكدس الاستدعاءات، قبل إجراء الاستدعاء العودي. وهكذا، لا يحتوي مكدس الاستدعاءات إطلاقًا إلا على الاستدعاء الأخير لـprint، ومن ثم لا يزداد في الحجم.

بشكل عام، عندما يكون استدعاء دالة هو آخر تعبير يُقيَّم في جسم دالة، نقول إنه استدعاء ذيلي (tail call). لاحظ أن هذا المفهوم ينطبق على كل من الدوال العودية وغير العودية. وفي الحالة الأولى، إذا كان كل استدعاء عودي

استدعاءً ذيليًا، توصف الدالة بأنها عودية ذيلية (tail recursive). وهكذا، print عودية ذيلية بينما length ليست كذلك. لاحظ أن الدالة العودية يمكن أن تحتوي على استدعاءات ذيلية واستدعاءات غير ذيلية معًا. وهذا هو حال دالة مكارثي (McCarthy) الشهيرة 91.

 let rec f91 n =
   if n > 100 then n - 10 else f91 (f91 (n + 11))

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

  let rec length_term acc = function
    | []     -> acc
    | _ :: r -> length_term (1 + acc) r

في هذه النسخة، يكون الاستدعاء العودي لـlength_term استدعاءً ذيليًا. ولحساب طول قائمة، يكفي استدعاء length_term بالوسيط الأول 0.

  let length l = length_term 0 l

يمكننا حتى تعريف الدالة length كنتيجة للتطبيق الجزئي (partial application) للدالة length_term على 0.

  let length = length_term 0

2.9 تحويل الأعداد الصحيحة من أساس تعسّفي (arbitrary base)

برنامجنا التالي (انظر الصفحة 144)، radix.ml، يستقبل أعدادًا مكتوبةً بأساسٍ ما B، حيث 2 ≤ B ≤ 36، ويحوّلها إلى الأساس 10. يُمرَّر الأساس عبر سطر الأوامر (command line). بعد ذلك، يقرأ البرنامج أعدادًا من الدخل القياسي (standard input) ويعرضها بالأساس 10.

إليك مثالًا أول بالأساس 16:

  > radix 16
  7FFF
   -> 32767
  A0
   -> 160

بعد تشغيل البرنامج بالأساس المعطى، نُدخل الرقم 7FFF على الدخل القياسي، فيعرض البرنامج نتيجة التحويل، أي 32767. ثم نُدخل الرقم A0 فنحصل على 160.

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

  > radix 36
  ZORRO
   -> 59942292

كما ترى في هذه الأمثلة، تُكتب الأعداد باستخدام المحارف 0 إلى 9، وA (للرقم 10) إلى Z (للرقم 35).

لننتقل الآن إلى تنفيذ البرنامج. في البداية، نستخرج الأساس من سطر الأوامر ونخزّنه في متغير base.

  let base = int_of_string Sys.argv.(1)

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

نواصل بتعريف دالة list_of_string، تحوّل سلسلة نصية (من النوع string) إلى قائمة محارف (من النوع charlist).

  let list_of_string s =
    let digits = ref [] in
    for i = 0 to String.length s - 1 do
      digits := s.[i] :: !digits
    done;
    !digits

نجتاز السلسلة النصية s، مبتدئين بحرفها الأول، بحيث نبني قائمة يكون حرف s الأخير — أي الرقم الأقل دلالة (least significant digit) في العدد — في رأس القائمة.

بعد ذلك، نكتب دالة digit_of_char لتحويل محرفٍ يمثل رقمًا إلى العدد الصحيح الموافق له.

  let digit_of_char c =
    match c with
      | ’0’..’9’ -> Char.code c - Char.code ’0’
      | ’A’..’Z’ -> 10 + Char.code c - Char.code ’A’
      | c -> Printf.eprintf "invalid character %c\n" c; exit 1

تعالج حالة مطابقة الأنماط الأولى |’0’..’9’-> حالة محرف c بين ’0’ و’9’. تُحصل قيمته العددية ببساطة على أنها الفرق بين رمز ASCII للمحرف c ورمز المحرف 0. وتسير الحالة الثانية على النحو نفسه، وذلك للمحارف بين ’A’ و’Z’. وبالنسبة إلى سائر المحارف، تعرض الحالة الأخيرة رسالة على الخطأ القياسي (standard error) باستخدام Printf.eprintf وتنهي البرنامج باستخدام الدالة المعرَّفة مسبقًا exit.

ثم نكتب دالة check_digit تتحقق من أن d رقم صالح للأساس المعطى، أي أنه يقع بين 0 وbase−1.

  let check_digit d =
    if d < 0 || d >= base then begin
      Printf.eprintf "invalid digit %d\n" d; exit 1
    end

لا تُعيد هذه الدالة أي نتيجة. فهي توقف البرنامج إذا لم يكن الرقم d صالحًا.

الجزء الرئيسي من البرنامج هو حلقة لا نهائية (infinite loop) تقرأ سلسلة نصية s من الدخل القياسي وتحوّل العدد الموافق لها إلى الأساس 10.

  let () =
    while true do
      let s = read_line () in
      ...
    done

نبدأ بتحويل السلسلة النصية s إلى قائمة محارف cl باستخدام الدالة list_of_string.

      let cl = list_of_string s in

لتحويل القائمة cl إلى قائمة أرقام، نطبق الدالة digit_of_char على كل عنصر من عناصر cl. ولتحقيق ذلك، نستخدم دالة المكتبة List.map، التي تبني قائمة جديدة بتطبيق دالة معطاة على جميع عناصر قائمة.

      let dl = List.map digit_of_char cl in

مثلًا، إذا كانت cl هي القائمة [’A’;’0’]، فإن dl هي القائمة [10;0]. وبشكل أعم، إذا عُطيت دالة f وقائمة l [e1;e2;...;en]، فإن لدينا:

List.mapfl=[fe1;fe2;...;fen]List.map f l = [f e1;f e2; ...;f en]

ثم نتحقق من أن كل رقم في القائمة dl صالح بتطبيق الدالة check_digit تباعًا على كل عنصر من عناصر dl.

      List.iter check_digit dl;

في هذه الحالة لا نرغب في بناء قائمة جديدة بل في تطبيق check_digit. سيُوقف البرنامج بأكمله إذا رصدت check_digit رقمًا غير صالح. وبشكل عام، إذا عُطيت دالة f وقائمة l تساوي [e1;e2;...;en]، فإن التطبيق List.iter f l يعادل التسلسل التالي:

List.iterfl=fe1;fe2;⋅⋅⋅;fenList.iter f l = f e1;f e2; \cdot \cdot \cdot ;f en

أخيرًا، سنحسب التمثيل بالأساس 10 ونعرضه. القائمة dl على الشكل [d0;d1;…;dn−1]، حيث d0 هو الرقم الموافق للحرف الأخير في السلسلة النصية، أي الرقم الأقل دلالة. لذلك من الضروري حساب القيمة التالية:

n∑−1di×baseii=0n\sum -1 di \times basei i = 0

إن أكثر الطرق كفاءة لتقليل عدد عمليات الضرب (وبخاصة لتجنب حساب basei المكلف) هي قاعدة هورنر (Horner’s rule)، التي تعيد كتابة المجموع السابق على النحو التالي:

d0+base×(d1+base×(...(dn−2+base×(dn−1+base×0))...))d0 + base \times (d1 + base \times (...(dn- 2 + base \times (dn-1 + base\times 0))...))

يمكننا بسهولة برمجة ما سبق باستخدام دالة المكتبة List.fold_right، التي تتيح لنا اجتياز القائمة dl من العنصر الأخير dn−1 إلى العنصر الأول d0، بتطبيق دالة f على كل عنصر على النحو التالي:

List.foldrightflacc=fd0(...(fdn−2(fdn−1acc)...))List.fold_right f l acc = f d0 (...(f dn-2 (f dn-1 acc) ...))

تُمرَّر القيمة المحسوبة لكل عنصر من عناصر القائمة إلى الدالة f بصورة منهجية بوصفها الوسيط الثاني، ويُسمى المُرتاكِم (accumulator). قيمته الابتدائية، المستخدمة عند استدعاء f على العنصر الأخير dn−1 من القائمة، هي الوسيط الثالث لـList.fold_right، ويسمى هنا acc. للحصول على صيغة هورنر، يكفي جعل f الدالة fundacc->d+base*acc. وهكذا تكون نهاية البرنامج ببساطة:

    let v = List.fold_right (fun d acc -> d + base * acc) dl 0 in
    Printf.printf " -> %d\n" v

معلومات إضافية

تعدد الأشكال (Polymorphism)

لكي تكون دوال المكتبة List، مثل iter وmap وfold_right، مفيدة، يجب أن تكون عامة (generic) بالنسبة إلى نوع عناصر القائمة التي تُطبق عليها، وبالنسبة إلى العملية المنفَّذة عليها كذلك. تُسمى هذه العمومية تعدد الأشكال (polymorphism). ويمكن توضيح المفهوم باستخدام الدالة length لحساب طول قائمة:

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

يمكن لهذه الدالة، بطبيعة الحال، أن تُطبق على قائمة أعداد صحيحة. مثلًا:

  # length [1; 6; 2; 8; 3] ;;
  - : int = 5

غير أن هذه الدالة لا تستخدم مباشرة عناصر القائمة l الممرَّرة بوصفها وسيطًا (كما يدلّ عليه تطابق الأنماط _::r). لذلك يمكن لهذه الدالة في الواقع أن تُطبق على أي قائمة، سواء كانت قائمة سلاسل نصية أم قائمة أعداد كسرية (floating-point numbers). مثلًا:

  # length ["hello"; "world"; "!"] ;;
  - : int = 3
  # length [ [3.4; .2]; []; [1.2]; [5.]] ;;
  - : int = 4

لكي يكون ما سبق ممكنًا، يجب أن تقبل الدالة length وسائط من الأنواع intlist وstringlist وحتى floatlistlist. وهذه الدالة في الواقع قابلة للتطبيق على قوائم من أي نوع. وفي أوسمل، يُعطى لها النوع:

’alist->int

حيث يمثل متغير النوع (type variable) ’a أي نوع. يُقال عن نوع مثل نوع length، الذي يحوي متغير نوع واحدًا على الأقل، إنه متعدد الأشكال (polymorphic).

إضافةً إلى تمثيل أي نوع، تُفيد متغيرات الأنواع أيضًا في إقامة علاقات بين الأجزاء العامة لنوع متعدد الأشكال. مثلًا، في الدالة f المعرَّفة بـletfgx=(gx)+1، يجب أن يكون نوعا الوسيطين g وx مرتبطين لأن الدالة g تُطبق على x. ومع ذلك، يبقى x (ومن ثم g) متعدد الأشكال، لعدم وجود قيد نوع آخر يتعلق بهذه القيمة في جسم f. وهكذا، في نوع f، أي (’a->int)->’a->int، يربط المتغير ’a نوع وسيط g بنوع x، دون إضافة أي قيود إضافية. وبالمثل، تكون لدالة iter من المكتبة List نوع متعدد الأشكال:

iter : (’a -> unit) -> ’a list -> unit

وهذا يربط نوع الدالة الممرَّرة بوصفها وسيطًا بنوع عناصر القائمة التي تجتازها الدالة.

يمكن لنوع متعدد الأشكال أن يحوي عدة متغيرات أنواع، لتمثيل أنواع عامة غير مرتبطة. ولنتأمل مثلًا الدالة make_pair المعرَّفة بـ:

  let make_pair x y = (x, y)

هنا، يمكن أن يكون الوسيطان x وy من أي نوع، ولا يلزم أن يكونا مرتبطين. ومن ثم يكون لهذه الدالة نوع متعدد الأشكال بمتغيرين، أي ’a->’b->’a*’b.

بالطريقة نفسها، تكون للدالتين map وfold_right من المكتبة List الأنواع متعددة الأشكال التالية:

map : (’a -> ’b) -> ’a list -> ’b list
fold_right : (’a -> ’b -> ’b) -> ’a list -> ’b -> ’b

هذه الأنواع هي الأكثر عموميةً على الإطلاق.

المُكرِّرات (iterators) على القوائم من اليمين إلى اليسار ومن اليسار إلى اليمين

يتيح لنا الجمع بين دوال الرتب الأعلى (higher-order functions) والأنواع متعددة الأشكال تعريف مُكرِّرات (iterators)، أي دوال تجتاز بنى بيانات عامة، مثل القوائم.

مثلًا، يمكن تعريف المُكرِّر fold_right المستخدم في برنامج radix.ml على النحو التالي:

  # let rec fold_right f l e =
      match l with
      | [] -> e
      | x :: r -> f x (fold_right f r e);;
  val fold_right : (’a -> ’b -> ’b) -> ’a list -> ’b -> ’b = <fun>

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

  # let sum l = fold_right (fun x y -> x *. y) l 1. ;;
  val mult : float list -> float = <fun>

سبب تسمية هذا المُكرِّر fold_right هو أنه يعالج عناصر القائمة من اليمين إلى اليسار. فالقائمة في الواقع تُجتاز من اليسار إلى اليمين، لكن الاستدعاء العودي يُنفَّذ قبل تطبيق الدالة الممرَّرة بوصفها وسيطًا. وهذا يعني أن بقية القائمة تُعالج قبل عنصرها الأول. ويمكننا التأكد من هذا السلوك بتطبيق fold_right على دالة تطبع وسيطها الأول:

  # fold_right (fun x () -> print_int x) [1;2;3;4] ();;
  4321- : unit = ()

من الطبيعي هنا أن ننظر إلى المُكرِّر الآخر، الذي يجتاز العناصر ويعالجها من اليسار إلى اليمين. يُسمى طبيعيًا fold_left ويُكتب على النحو التالي:

  # let rec fold_left f e = function
      | [] -> e
      | x :: r -> fold_left f (f e x) r;;
  val fold_left : (’a -> ’b -> ’a) -> ’a -> ’b list -> ’a = <fun>

من الواضح أن العناصر تُعالج فعلًا من اليسار إلى اليمين:

  # fold_left (fun () x -> print_int x) () [1;2;3;4];;
  1234- : unit = ()

يمكننا كتابة الدالة mult بـfold_left كما فعلنا بـfold_right:

  # let mult l = fold_left (fun x y -> x *. y) 1. l ;;
  val mult : float list -> float

غير أن هناك فرقًا طفيفًا. فعلى قائمة تحوي مئات الآلاف من العناصر، قد تُحدث الدالة mult المكتوبة بـfold_right فيضًا في المكدس (stack overflow)، ينجم عنه إما استثناء Stack_overflow أو توقف البرنامج فجأة. وذلك لأن الاستدعاء العودي لـfold_right ليس استدعاءً ذيليًا (tail call). (وبما أن الاستدعاء يجب أن يُنفَّذ قبل إجراء العملية، فمن الضروري حفظ قيمة العنصر الأول من القائمة.) وفي المقابل، في حالة fold_left، يكون الاستدعاء العودي استدعاءً ذيليًا. (لا حاجة إلى المكدس لأن القيمة x تُستخدم قبل الاستدعاء العودي لـfold_left).

من المهم ملاحظة أن مُكرِّرًا مثل fold_left أو fold_right يجتاز جميع عناصر القائمة الممرَّرة بوصفها وسيطًا. وإذا أردنا إيقاف الحساب عند عنصر محدد، فلدينا احتمالان على الأقل[4]: إما أن نكتب دالة عودية تجتاز القائمة وتتوقف متى شئنا، وإما أن نستخدم مُكرِّرًا ونُثير استثناءً (exception) لمقاطعة اجتياز القائمة. لنعد إلى مثال الدالة mult. قد نرغب في إيقاف الحساب عند مواجهة القيمة 0. ويمكن كتابة النسخة التي تستخدم الاستثناء على النحو التالي:

  let mult l =
    try
      List.fold_left
        (fun x y -> if y = 0. then raise Exit else x *. y) 1. l
    with Exit -> 0.

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

2.10 بريك أوت دون الطوب (Breakout without Bricks)

برنامجنا العاشر (انظر الصفحة 160) نسخة مبسطة من لعبة بريك أوت (Breakout)، دون الطوب. تتمثل اللعبة في جعل كرة ترتد داخل إطار، بواسطة مجداف (paddle) يُتحكم فيه باستخدام الفأرة.

الشكل 2.7: بريك أوت دون الطوب.

بيانيًا، تكون نافذة اللعبة كما في الشكل 2.7، ممثلة بإطار رمادي، مع دائرة سوداء تمثل الكرة، ومستطيل أسود في أسفل نافذة اللعبة يمثل المجداف.

تتضمن برمجة مثل هذه اللعبة ثلاثة مكونات رئيسية. أولًا، يجب أن نعرّف ثوابت (constants) اللعبة، أي أبعاد النافذة (ارتفاعها وعرضها، بالبكسل)، وأبعاد الكرة (أي نصف قطر الدائرة)، والمجداف (ارتفاع المستطيل وعرضه). ثانيًا، يجب أن نحدد حالة (state) اللعبة، أي مجموعة القيم التي تميزها في أي لحظة. وهنا، هي إحداثيات مركز الكرة، وسرعتها، وموضع المجداف، الذي يمكن تحديده بإحداثيات زاويته السفلية اليسرى. وتبسيطًا للأمور، يمكننا استخدام نظام الإحداثيات نفسه الذي تستخدمه المكتبة Graphics؛ أي أن النقطة ذات الإحداثيات (0,0) تقع في أسفل يسار النافذة، وأن محوري x وy هما على التوالي الحافتان السفلية واليسرى للنافذة. وأخيرًا، تُلعب اللعبة باستخدام خوارزمية تنفذ الخطوات التالية:

  1. تهيئة حالة اللعبة (موضع الكرة وسرعتها، وموضع المجداف).

  2. مسح النافذة البيانية.

  3. حساب موضع المجداف بوصفه دالةً في الإحداثي x للفأرة.

  4. عرض الكرة والمجداف.

  5. حساب الحالة الجديدة للعبة، أي:

    الموضع الجديد للكرة، بوصفه دالةً في موضعها الحالي ومتجه سرعتها؛

  6. متجه السرعة الجديد للكرة، بوصفه دالةً في ارتدادها عن جانبي النافذة وموضع المجداف.

والعودة إلى الخطوة 2.

وكما ترى، فإن الأفعال المنفَّذة في هذه الخطوات من نوعين: أفعال بيانية صِرفة (الخطوات 2 و3 و4)، وأفعال تتعامل مع حالة اللعبة (الخطوات 1 و5 و6). نختار تقسيم شيفرة أوسمل إلى ملفين: draw.ml وbreakout.ml. يحوي الأول جميع ثوابت اللعبة ودوالها البيانية؛ ويحافظ الثاني على الحالة الحالية وينفذ الخوارزمية. وبشكل عام، لتوضيح بنية البرامج الأكبر حجمًا، من الجيد تقسيمها إلى عدة ملفات تسمى وحدات الترجمة (compilation units).

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

  > ocamlc -I ‘ocamlfind query graphics‘ -o breakout graphics.cma \
        draw.ml breakout.ml

وكما سنرى قريبًا، فإن ترتيب أسماء الملفات على سطر الأوامر مهم.

يبدأ الجزء البياني (الملف draw.ml، البرنامج 10) بتعريف أبعاد نافذة اللعبة، مع الإعلان عن أربعة ثوابت: left وright وdown وup.

  let left = 0.
  let right = 300.
  let down = 0.
  let up = 200.

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

تعرف الثوابت الثلاثة التالية على التوالي نصف قطر الكرة، وطول المجداف، وعرضه (بالبكسل).

  let ball = 5
  let paddle = 50
  let thick = 8

أخيرًا، نصرّح عن لون gray، يُحصَل عليه بتحديد قيم مكوناته الثلاثة — الأحمر والأخضر والأزرق — باستخدام الدالة rgb.

  let gray = rgb 240 240 240

تهيّئ الدالة init نافذة اللعبة بفتح لوحة بيانية (canvas) بأبعاد right×up.

  let init () =
    let s = Printf.sprintf " %dx%d" (truncate right) (truncate up) in
    open_graph s;
    auto_synchronize false

وبما أن الثابتين right وup قيمتان من النوع float، نستخدم الدالة المعرَّفة مسبقًا truncate من المكتبة القياسية لاقتطاع قيمتيهما وتحويلهما إلى عددين صحيحين. والاستدعاء auto_synchronizefalse يفعّل وضع التخزين المؤقت المزدوج (double buffering) بالجهاز البياني. وعند تفعيل هذا الوضع، تُنفَّذ جميع عمليات العرض (رسم دائرة أو مستطيل، وما إلى ذلك) في منطقة ذاكرة تُسمى مخزن الدعم (backing store)، وليس مباشرة على الشاشة. ويجب بعد ذلك استخدام الدالة synchronize صراحةً لنسخ محتويات مخزن الدعم إلى الشاشة. وبما أن هذا النسخ لحظي، فإنه يزيل أي تأثيرات «وميض» أثناء الحركة.

نكتب الآن دالة لكل خطوة بيانية من خوارزمية اللعبة. تنفَّذ الخطوة 2 بدالة clear تمسح اللوحة برسم مستطيل رمادي بأبعاد النافذة البيانية نفسها.

  let clear () =
    set_color gray;
    fill_rect 0 0 (truncate right) (truncate up)

تنفَّذ الخطوة 3 من الخوارزمية بدالة get_paddle_pos. تبدأ باسترجاع الإحداثي x للموضع الحالي للفأرة (بالدالة mouse_pos). ولضمان عدم خروج المجداف خارج نافذة اللعبة من الجهة اليمنى، نأخذ الحد الأدنى بين القيمة المحصَّلة وtruncateright-paddle.

let get_paddle_pos () =
  let x = fst (mouse_pos ()) in
  max 0 (min x (truncate right - paddle))

تأخذ الدالة البيانية الرئيسية، game، الإحداثيين x وy للكرة بوصفهما وسيطين، وتنفذ الخطوات 2 و3 و4 من الخوارزمية.

  let game x y =
    clear ();
    set_color black;
    fill_circle (truncate x) (truncate y) ball;
    let x = get_paddle_pos () in
    fill_rect x 0 paddle thick;
    synchronize ();
    x

ينفذ الملف الثاني، breakout.ml (انظر الصفحة 166)، الخطوات 1 و5 و6 من الخوارزمية. تُرمَّز حالة اللعبة بزوجين من الأعداد الكسرية: (x,y) و(vx,vy)، يمثلان على التوالي إحداثيات الكرة وسرعتها.

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

  let bounce (x, y) (vx, vy) xp =
    ...

لحساب المركبة الجديدة vx، يجب مقارنة الإحداثي x للكرة بالحافتين اليسرى واليمنى لنافذة اللعبة. وبما أن الثابتين left وright قد عُرِّفا في الملف draw.ml، فيجب استخدام تدوين النقطة Draw.left وDraw.right للإشارة إليهما. فكل وحدة ترجمة تعرّف فعلًا وحدة نمطية (module) تحمل اسم الملف نفسه، لكن بحرف أول كبير.

    let vx =
      if x <= Draw.left || x >= Draw.right then -. vx else vx in

وبالطريقة نفسها، لحساب المركبة الجديدة vy، يجب مقارنة الإحداثي y للكرة بأعلى النافذة Draw.up. ويتغير اتجاه سرعة الكرة أيضًا إذا اصطدمت الكرة بالمجداف، أي إذا كان الإحداثي x واقعًا بين xp وxp+.floatDraw.paddle، وكان الإحداثي y أقل من سماكة المجداف Draw.thick.

    let vy =
      if y <= float Draw.thick && x >= xp &&
         x <= xp +. float Draw.paddle || y >= Draw.up
      then -. vy else vy
    in
    (vx, vy)

تعيد الدالة التالية الموضع الجديد للكرة بجمع الإحداثيين x وy، على التوالي، إلى إحداثيي السرعة vx وvy.

  let new_position (x, y) (vx, vy) = x +. vx, y +. vy

تنفذ الدالة play الحلقة بين الخطوتين 2 و6. انطلاقًا من الحالة الحالية للعبة، الممرَّرة بوصفها وسيطًا، نبدأ بالتحقق من أن الكرة لا تتجاوز أسفل نافذة اللعبة، بمقارنة الإحداثي y بالثابت Draw.down. وإذا تجاوزته الكرة، تنتهي اللعبة باستدعاء الدالة failwith من المكتبة القياسية:

  let rec play (x, y) (vx, vy) =
    if y <= Draw.down then failwith "game over";

إذا لم تكن اللعبة قد انتهت، نعرض الكرة والمجداف باستخدام الدالة Draw.game، التي تعيد الإحداثي x للمجداف.

    let xp = Draw.game x y in

بعد ذلك، نحسب إحداثيات متجه السرعة الجديدة، ثم إحداثيات الكرة.

    let vx, vy = bounce (x, y) (vx, vy) (float xp) in
    let x’, y’ = new_position (x, y) (vx, vy) in

نعود إلى الخطوة 2 باستدعاء عودي للدالة play بالحالة الجديدة للعبة بوصفها وسيطًا.

    play (x’, y’) (vx, vy)

يفتح الجزء الرئيسي من البرنامج نافذة اللعبة باستدعاء Draw.init.

  let () =
    Draw.init();

ثم ينشئ متجه سرعة عشوائيًا (vx,vy):

    let speed = 0.1 in
    let vx = speed *. Random.float 1. in
    let vy = speed *. Random.float 1. in

أخيرًا، تبدأ اللعبة باستدعاء الدالة play، واضعةً الكرة فوق المجداف وفي مركز النافذة:

    play (Draw.right /. 2., float Draw.thick) (vx, vy)

معلومات إضافية

الترجمة المنفصلة والربط (separate compilation and linking)

يمكن تفكيك سطر الأوامر المعطى أعلاه لترجمة بريك أوت إلى عدة أوامر. يمكننا البدء بترجمة الملف draw.ml وحده، بالأمر:

  > ocamlc -I ‘ocamlfind query graphics‘ -c draw.ml

يحدد خيار المترجم -c أننا لا نرغب في إنشاء ملف تنفيذي، بل في ترجمة الشيفرة فقط. تتكون النتيجة من ملفين: draw.cmi وdraw.cmo. يحوي الأول معلومات الأنواع (typing)، ويحوي الثاني الشيفرة. وهذه الشيفرة ليست مكتفية بذاتها؛ فهي على وجه الخصوص تشير إلى دوال من الوحدة النمطية Graphics غير مضمَّنة في هذا الملف.

يمكننا بعد ذلك ترجمة الملف الثاني بأمر مماثل.

  > ocamlc -c breakout.ml

وبما أن هذا الملف يشير إلى الوحدة النمطية Draw، فقد كان علينا ترجمة الملف draw.ml أولًا. والمعلومات اللازمة لفحص الأنواع (type-checking) للملف breakout.ml موجودة في الملف draw.cmi. وهنا أيضًا، الشيفرة المحصَّلة ليست مكتفية بذاتها؛ فالملف breakout.cmo يشير إلى قيم ودوال من الوحدة النمطية Draw موجودة في draw.cmo.

للحصول على ملف تنفيذي، يجب إجراء عملية ربط (linking)، تتكون من ضم عدة قطع من الشيفرات مع التحقق من إمكانية حل كل إشارة. وهنا، القطع الثلاث المعنية هي قطع مكتبة أوسمل graphics.cma (التي تجمع مجموعة ملفات cmo معًا) والملفان draw.cmo وbreakout.cmo.

  > ocamlc -I ‘ocamlfind query graphics‘ -o breakout graphics.cma \
        draw.cmo breakout.cmo

وكما أوضحنا أعلاه، فإن ترتيب أسماء الملفات على سطر الأوامر هذا مهم. وعلى وجه الخصوص، يجب أن يكون متوافقًا مع التبعيات بين وحدات الترجمة. هنا، breakout.cmo يعتمد على draw.cmo، الذي يعتمد هو نفسه على graphics.cma. وفضلاً عن ذلك، يجب إدراك أن برنامج أوسمل لا يملك نقطة دخول محددة. فالشيفرة المحصَّلة بعد الربط تنفذ ببساطة شيفرات الملفات المختلفة الممرَّرة على سطر الأوامر، بالترتيب الذي تظهر به.

الواجهات (interfaces)

يحوي الملف draw.cmi الناتج عن الترجمة معلومات الأنواع لجميع القيم المعرَّفة في الملف draw.ml. ويمكن الحصول على المعلومات نفسها باستخدام خيار المترجم -i.

  > ocamlc -I ‘ocamlfind query graphics‘ -i draw.ml
  val left : float
  val right : float
  ...
  val game : float -> float -> int

غير أننا قد نرغب في جعل بعض هذه القيم غير قابلة للوصول من بقية البرنامج. مثلًا، قد نرغب في إخفاء الدالة clear. ولتحقيق ذلك، يمكننا تعريف واجهة (interface) للملف draw.ml، في شكل ملف draw.mli.

يُعطى مثل هذا الملف في البرنامج 12. نكتبه باستخدام الصياغة نفسها التي يستخدمها خيار المترجم -i. ونترجم draw.mli قبل ترجمة draw.ml.

  > ocamlc -c draw.mli
  > ocamlc -I ‘ocamlfind query graphics‘ -c draw.ml

يُنتج الأمر الأول الملف draw.cmi. ويُنتج الثاني draw.cmo ويتحقق من توافقه مع draw.cmi، أي أنه يعرّف قيمًا لها الأسماء والأنواع المحددة في الملف draw.cmi. وعند وجود ملف draw.mli، يرفض المترجم ترجمة draw.ml حتى يُترجم draw.mli. وإذا حاولنا بعد ذلك استخدام قيمة في breakout.ml غير مذكورة في draw.mli، مثل clear، يُثار خطأ.

  > ocamlc -c breakout.ml
  Error: Unbound value Draw.clear

ليست الواجهات مجرد وسيلة لتحديد رؤية القيم المعرَّفة في وحدة ترجمة. فهي تمكّن أيضًا من الترجمة المنفصلة (separate compilation). وهذا يعني أن شيفرة كل وحدة ترجمة يمكن ترجمتها بصورة مستقلة عن شيفرات الوحدات الأخرى، لأنها تعتمد على واجهاتها فقط. وبمجرد ترجمة draw.mli، يمكننا ترجمة draw.ml أو breakout.ml بأي ترتيب. وبوجه خاص، يتيح هذا تقسيم العمل بين عدة مطورين بمجرد وضع الواجهات. وعلاوةً على ذلك، تساعد الترجمة المنفصلة في تجنب إعادة الترجمة غير الضرورية للشيفرة. مثلًا، تغيير شيفرة الدالة Draw.clear يستدعي فقط إعادة ترجمة draw.ml، ثم إعادة عملية الربط. ولا حاجة إلى إعادة ترجمة أي وحدة أخرى تستخدم Draw (مثل breakout.ml).

الترجمة المنفصلة باستخدام dune

لترجمة برنامجنا باستخدام dune، نكتب ملف الإعداد التالي:

  (executable
   (name breakout)
   (modules draw breakout)
   (libraries graphics))

يسرد السطر (modules draw breakout) الوحدات النمطية اللازمة لترجمة البرنامج. وسيترجم أداة dune الوحدتين النمطيتين Draw وBreakout تباعًا، كما فعلنا يدويًا أعلاه. وعلى وجه الخصوص، إذا وُجد ملف .mli، فإنه يُترجم قبل ملف .ml الموافق له. وعلاوةً على ذلك، يشير السطر (libraries graphics) إلى أن الملفات يجب أن تُترجم باستخدام المكتبة Graphics.

الوحدات النمطية (modules)

استخدمنا حتى الآن وحدات نمطية شتى، بما فيها وحدات المكتبة القياسية، مثل Array وList، والوحدتين النمطيتين Draw وBreakout من المثال السابق. وقد كانت هذه الوحدات النمطية تطابق دائمًا وحدات ترجمة، أي أزواج ملفات .ml و.mli. غير أن مفهومي الوحدة النمطية والواجهة أدقّ من مفهوم الملف؛ فهما يقابلان منشآت (constructs) من اللغة. وهكذا، يمكننا تعريف واجهة I تحوي ثابتًا a ودالة f بالصياغة التالية:

  module type I = sig
    val a: int
    val f: int -> int
  end

يمكننا بعد ذلك تعريف وحدة نمطية M بهذه الواجهة، بالصياغة التالية:

  module M : I = struct
    let a = 42
    let b = 3
    let f x = a * x + b
  end

ينفذ المترجم بعد ذلك العمليات نفسها كما لو كتبنا الواجهة I في ملف m.mli والوحدة النمطية M في ملف m.ml. وعلى وجه الخصوص، نصل إلى الثابت a بتدوين M.a، بينما لا يمكن الوصول إلى الثابت b خارج الوحدة النمطية M.

2.11 السلحفاة لوجو (Logo Turtle)

برنامجنا التالي، turtle.ml، نسخة مبسطة من سلحفاة لوجو (Logo turtle). فعلى الرغم من أن لغة البرمجة لوجو قد خرجت من الاستخدام اليوم، فإنها تبقى من الناحية المفاهيمية مثيرة للاهتمام كما كانت دائمًا. وأبرز ما تتميز به سلحفاة يمكن تحريكها بتعليمات على غرار «تقدَّم 3 وحدات» أو «انعطف يمينًا 30 درجة»، ثم يُعرَض مسارها على الشاشة.

الشكل 2.8: مثال على رسم باستخدام سلحفاة لوجو.

يمكننا بالتالي تتبّع مربع بسهولة، عبر تكرار التسلسل «تقدَّم، ثم انعطف يسارًا 90 درجة»، أو حتى رسم الشكل 2.8 بتكرار التسلسل «ارسم مربعًا، ثم انعطف بمقدار 20 درجة» عدة مرات.

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

يتبادر إلى الذهن سؤال طبيعي عند كتابة شيفرة السلحفاة: كيف نمثّل الزاوية التي تحدّد اتجاه السلحفاة؟

يمكننا اختيار تمثيل الزاوية بالدرجات أو بالتقديرات الدائرية (radians)، كعدد صحيح أو كعدد كسري، وهكذا. وهنا، قررنا عدم الاختيار بين هذه الاحتمالات، وبدلًا من ذلك، نُبارمِد (parametrize) الشيفرة بوحدة A توفّر نوع الزوايا.

نبدأ وفقًا لذلك بإنشاء بصمة (signature) لمثل هذه الوحدة، وهي:

  module type ANGLE = sig
    type t
    val of_degrees: float -> t
    val add: t -> t -> t
    val cos: t -> float
    val sin: t -> float
  end

النوع t هو نوع الزوايا. ليس له تعريف؛ نقول عنه إنه نوع مجرَّد (abstract type). غير أننا نستطيع مع ذلك استخدامه في تنفيذ سلحفاتنا، لأننا مُنِحنا ما يلي: دالة of_degrees، لتحويل زاوية معبَّر عنها بالدرجات إلى قيمة من النوع t؛ ودالة add، لجمع زاويتين؛ وأخيرًا الدالتان sin وcos، لحساب جيب تمام الزاوية وجيبها.

يمكننا بالتالي كتابة سلحفاة لوجو على هيئة وحدة Turtle، مبارَمة بوحدة A ذات البصمة ANGLE. وتُسمّى مثل هذه الوحدة مُبَرْمِجًا (functor)، وتُعرَّف على النحو التالي:

  module Turtle(A: ANGLE) = struct

داخل الوحدة Turtle، تكون الوحدة A ذات البصمة ANGLE مرئية ويمكن استخدامها مثل أي وحدة أخرى. فمثلًا، يمكننا إدخال مرجع (reference) باسم angle يحتوي على الاتجاه الحالي للسلحفاة، باستخدام:

    let angle = ref (A.of_degrees 0.)

يمكننا أيضًا كتابة دالة rotate_left لجعل السلحفاة تنعطف d درجة إلى اليسار:

    let rotate_left d = angle := A.add !angle (A.of_degrees d)

تُعطى الشيفرة الكاملة للسلحفاة المبارَمة في البرنامج 13 (انظر أدناه). وهناك نجد المرجعين tx وty اللذين يتابعان الموضع الحالي للسلحفاة، ودالة advance لجعلها تتقدّم إلى الأمام. ويشير المرجع المنطقي (boolean) draw إلى ما إذا كان قلم السلحفاة مرفوعًا أم منخفضًا، ويُعدَّل بالدالتين pen_up وpen_down.

لاستخدام المُبَرْمِج Turtle، يجب أن نبدأ بتوفير وحدة محدَّدة ذات الواجهة ANGLE. فإذا اخترنا تمثيل الزوايات بالتقديرات الدائرية (radians) وبأعداد كسرية، فيمكن تعريف وحدة Angle على النحو التالي:

  module Angle: ANGLE = struct
    type t = float
    let add = (+.)
    let pi_over_180 = atan 1. /. 45.
    let of_degrees d = d *. pi_over_180
    let cos = Stdlib.cos
    let sin = Stdlib.sin
  end

نحصل بعد ذلك على وحدة T بتطبيق المُبَرْمِج Turtle على الوحدة Angle، وهو ما يُكتب على النحو التالي:

  module T = Turtle(Angle)

أخيرًا، يمكننا استخدام الوحدة T لتتبُّع الشكل 2.8 بكتابة ما يلي مثلًا:

  let square d =
    for k = 1 to 4 do T.advance d; T.rotate_left 90. done
  let squares d a =
    for k = 1 to truncate (360. /. a) do
      square d; T.rotate_left a
    done
  let () = squares 100. 20.

هنا، ترسم الدالة squared مربعًا طول ضلعه d، وترسم الدالة squaresda مجموعة من المربعات طول ضلع كل منها d، مع دوران بمقدار a درجة بين أي مربعين متتاليين.

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

معلومات إضافية

الأنواع المجرَّدة (Abstract Types)

في المثال أعلاه، نوع الزوايا A.t نوع مجرَّد، لأننا لا نعرف بعد كيف سيُنفَّذ. ويمكننا أيضًا استخدام مفهوم الأنواع المجرَّدة لـإخفاء تنفيذ ملموس، حتى عندما يكون معروفًا سلفًا. وهذا ما نسميه الإخفاء (encapsulation). فلنفترض مثلًا أننا نرغب في تعريف وحدة للتلاعب بأعداد صحيحة بين 0 و30، والتأكد من أن جميع الأعداد الصحيحة التي نستخدمها تقع ضمن هذا المجال. نبدأ بتعريف بصمة INT31 لهذه الوحدة:

  module type INT31 = sig
    type t
    val create : int -> t
    val value : t -> int
  end

تصرّح هذه البصمة بنوع مجرَّد t، وبدالتين create وvalue. ونلاحظ أنه بحكم الطبيعة المجرَّدة للنوع t، لا يمكن بناء قيمة من هذا النوع إلا باستخدام الدالة create. بعد ذلك، يمكننا بناء وحدة Int31 بهذه البصمة.

  module Int31 : INT31 = struct
    type t = int
    let check x = if x < 0 || x > 30 then invalid_arg "Int31.create"
    let create x = check x; x
    let value x = x
  end

داخل هذه الوحدة، نُعطي النوع t تعريفًا، وهو int. أما خارج الوحدة Int31، فيبقى النوع t مجرَّدًا، أي إننا لا نعلم أن قيم النوع Int31.t أعداد صحيحة. واستطاعتنا بذلك فرض الثابتة التي تقضي بأن أي قيمة من النوع Int31.t تقع بين 0 و30. فما كان بوسعنا فعل ذلك لو كتبنا typet=int في الواجهة INT31.

يتجلى الطابع المجرَّد للنوع t في الطريقة التي تُعرَض بها القيم في مُفسِّر أوسمل:

  # let x = Int31.create 7;;
  x : Int31.t = <abstr>

هنا، القيمة المعروضة لـx هي ``، وهي تُشير إلى قيمة ذات نوع مجرَّد. وبالتالي، لا يمكن استخدام x كعدد صحيح:

  # x + 10;;
  Error: This expression has type Int31.t
         but an expression was expected of type int

وبالتالي، يميّز نظام الأنواع بين النوعين Int31.t وint. ومع ذلك، فإن قيمة x (أي العدد الصحيح 7) هي ذاتها تمامًا كما لو كان x من النوع int. فاستخدام نوع مجرَّد لا يُحدث أي كلفة إضافية في زمن التشغيل. وإذا أردنا إضافة قيمة x إلى 10، فلا بدّ من تطبيق الدالة Int31.value على x لاستعادة قيمة من النوع int.

  # Int31.value x + 10;;
  - : int = 17
الأنواع الخاصة (Private Types)

كما رأينا مع النوع Int31.t، يمكن استخدام نوع مجرَّد لفرض ثابتة (invariant). فلننظر في مثال الوحدة Polar، المستخدمة لتمثيل الأعداد المركَّبة (complex numbers) بالإحداثيات القطبية، بالنوع:

  type t = { rho : float; theta : float; }

إذا أردنا فرض الثابتة 0 ≤rho على هذا النوع، أو ضمان أن 0 ≤theta < 2π، فأحد الحلول هو تعريف نوع مجرَّد. غير أننا في هذه الحالة لم نعد قادرين على الوصول إلى الحقلين rho وtheta من خارج الوحدة Polar، وكان لا بدّ بالتالي من توفير دالتي وصول (accessor):

  val rho : t -> float
  val theta : t -> float

أما الحل الأنقت فيتمثل في جعل النوع t نوعًا خاصًّا (private type). ونمنح الوحدة بصمة يكون فيها تعريف النوع t مؤهَّلًا بـprivate.

  type t = private { rho : float; theta : float; }

يظل تعريف النوع t داخل الوحدة على ما هو عليه. ويترتب على الطابع الخاص للنوع t أنه لم يعد ممكنًا بناء سجل من النوع Polar.t خارج الوحدة. وبالتالي، إذا كتبنا التعبير { Polar.rho = 1.; Polar.theta = 0. }، فسيُثار الخطأ التالي:

  Error: Cannot create values of the private type Polar.t

ومع ذلك، يظل ممكنًا بناء قيم من هذا النوع داخل الوحدة Polar. ويمكننا بالتالي توفير دالة — أو عدة دوال — لبناء قيم من النوع t، مثلًا:

  val create : float -> float -> t

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

المُكرِّرات (Iterators) والأنواع المجرَّدة

تتيح المُكرِّرات اجتياز بنية بيانات (انظر القسم 2.9 تحويل الأعداد الصحيحة من أساس تعسّفي (arbitrary base)). في حالة الأنواع الملموسة، مثل القوائم، يمكننا دائمًا اختيار تعريف دالة عودية مباشرة. أما في حالة الأنواع المجرَّدة، فإن ذلك لم يعد ممكنًا. ولذلك، من الحكمة توفير مُكرِّر أيضًا، على هيئة دالة iter أو fold. فمثلًا، إذا كانت وحدة S توفر نوعًا مجرَّدًا لمجموعات الأعداد الصحيحة — ولنُسمِّه set — فيمكنها أيضًا توفير دالة:

  fold: (int -> ’a -> ’a) -> set -> ’a -> ’a

يمكننا استخدام هذه الدالة لحساب مجموع عناصر مجموعة معيَّنة، وذلك رغم أننا لا نعرف تمثيلها.

المُبَرْمِجات (Functors)

تتيح لنا المُبَرْمِجات بناء بنى بيانات مبارَمة ببنى بيانات أخرى. فالمكتبة القياسية لأوسمل تحوي أربعة أمثلة على بنى بيانات مُعرَّفة على هيئة مُبَرْمِجات: Hashtbl.Make وSet.Make وMap.Make وWeak.Make. كما يحوي الجزء الثاني من هذا الكتاب أمثلة عديدة من هذا القبيل. ويمكن للمُبَرْمِجات أن تساعدنا أيضًا على كتابة خوارزميات مبارَمة ببنى بيانات أو حتى بخوارزميات أخرى (انظر الأمثلة المتنوعة في الجزء الثالث). وبصفة عامة، تُعدّ المُبَرْمِجات طريقة أنيقة لإعادة استخدام الشيفرة، عبر كتابتها بأكبر قدر ممكن من العمومية. ورغم الاختلافات العديدة بينهما، فإنها تُقارَن بـقوالب C++ (templates).

2.12 عزف مقطوعة موسيقية (Playing a Musical Score)

برنامجنا التالي (انظر الصفحة 202)، music.ml، يعزف مقطوعة موسيقية. والمقطوعات البسيطة التي سنعزفها مُمثَّلة بيانيًا كما في الشكل 2.9.

الشكل 2.9: مقطوعة موسيقية.

هناك عدة أنواع من الإشارات (signs) هنا:

  • تُحدَّد النوتات (notes) بدرجتها (أي بموضعها) على المقطوعة وبمدّتها. ونحن مهتمون فقط بالنوتات ذات مدتين محددتين: نصف النوتات (half notes) وربع النوتات (quarter notes). فنصف النوتة ضعف ربع النوتة طولًا.
  • الأصوات الساكنة (silences)، التي نعتبر فيها بالمثل فقط تلك التي تبلغ مدتها مدّة نصف النوتة أو مدّة ربع النوتة.

إلى هذه الإشارات، نُضيف الإيقاع (tempo)، الذي يحدّد عدد ربع النوتات في الدقيقة. وفي المثال أعلاه، الإيقاع هو 60 ربع نوتة في الدقيقة.

لعزف النوتات، يلزمنا معرفة تردداتها الخاصة (بالهرتز). ولتسهيل هذا الحساب، نُمثّل درجة النوتة لا بموضعها على المقطوعة، بل باستخدام معلومتين اثنتين:

  • نوتة رئيسة — دو، ري، مي، فا، صول، لا، سي؛
  • أوكتاف 0 أو 1 أو 2 أو 3، إلى آخره.

يتيح لنا هذا التمثيل تحديد تردد النوتة بسهولة، باستخدام الصيغة التالية:

of=f0×2o f = f0 \times 2

هنا، f0 هو تردد نوتتها الرئيسة في الأوكتاف 0، وo هو أوكتافها. ويعطي الجدول 2.10 الترددات في الأوكتاف 0 للنوتات الرئيسة.

الشكل 2.10: الترددات في الأوكتاف 0 للنوتات الموسيقية الرئيسة.

NoteFrequency(Hz)−−−−−−−−−−for−octave0−−−−do33re37mi41fa44sol49la55si62Note Frequency (Hz) - - - - - - - - - - for - octave 0 - - - - do 33 re 37 mi 41 fa 44 sol 49 la 55 si 62

كي يتمكن برنامجنا من تمثيل جميع عناصر المقطوعة، يبدأ بتعريف عدة أنواع. فالنوتات الرئيسة مُمثَّلة بالنوع note على النحو التالي [5]:

  type note = Do | Re | Mi | Fa | Sol | La | Si

هذا نوع مُعدَّد (enumerated)، يُعرّف مجالًا محدودًا يتكون من سبعة عناصر (Do وRe وغيرها)، تُسمّى بواني إنشاء (constructors). وبصياغة نحوية، يطلب أوسمل أن يبدأ اسم الباني بحرف كبير.

بمجرد تعريف هذا النوع، أصبح بإمكاننا التعامل مع قيم النوع note بمجرد استخدام أسماء بواني إنشائها:

  # Re;;
  - : note = Re

تُرمَّز درجة النوتات بسجلات (records) من النوع pitch ذات حقلين، note وoctave، يجب أن يحتويا أعدادًا صحيحة غير سالبة.

  type pitch = { note : note; octave : int }

أما المدد، التي هي من النوع duration، فمُمثَّلة بالبانيين Half (نصف نوتة) وQuarter (ربع نوتة).

  type duration = Half | Quarter

ولتمثيل نوعي الإشارات الذين قد يظهران في المقطوعات الموسيقية، نُعرّف النوع symbol على النحو التالي:

  type symbol = Note of pitch * duration | Rest of duration

هذا نوع جَبْري (algebraic type)، يتيح لنا التمييز بين النوتات والأصوات الساكنة بواسطة بانيين، Note وRest. وخلافًا لبواني الإنشاء في النوعين المُعدَّدين note وduration، فإن البانيين Note وRest لهما وسائط. ففي حالة Note، الوسائط من النوعين pitch وduration. أما Rest فله وسيط من النوع duration. فلإنشاء صمت مدته ربع نوتة، مثلًا، نكتب:

  # Rest Quarter;;
  - : symbol = Rest Quarter

وبالمثل، لإنشاء نوتة ري في الأوكتاف 1 وبمدّة نصف نوتة، نكتب:

  # Note ({ note = Re; octave = 1 }, Half);;
  - : signe = Note ({note = Re; octave = 1}, Half)

أخيرًا، تُرمَّز المقطوعات بنوع السجل score، المكوَّن من قائمة إشارات وإيقاع (tempo) يحدّد عدد ربع النوتات في الدقيقة.

  type score = { symbols : symbol list;  metronome : int }

تحسب الدالة الأولى في البرنامج التردد المرتبط بدرجة النوتة، استنادًا إلى الصيغة وجدول الترددات المعطيين أعلاه.

  let frequency { note = n; octave = o } =

إذًا، بنوتة n من النوع note وأوكتاف o، تبدأ الدالة frequency بتحديد التردد f0 للنوتة الرئيسة n، باستخدام بنية مطابقة الأنماط matchnwith، على النحو التالي:

    let f0 =
     match n with
       | Do -> 33
       | Re -> 37
       | Mi -> 41
       | Fa -> 44
       | Sol -> 49
       | La -> 55
       | Si -> 62
    in
    ...

تُعيد هذه البنية قيمًا مختلفة بحسب الباني المستخدم في إنشاء n. إذًا، إذا كان n هو الباني Do، فإن البنية matchnwith تُعيد العدد الصحيح 33. وإلا، إذا كان n هو الباني Re، فهو العدد الصحيح 37 الذي يُعاد، وهكذا دواليك. ثُمّ يُستخدَم التردد الرئيس f0 لحساب تردد النوتة:

    f0 * truncate (2. ** float o)

تحسب الدالة الثانية الزمن (بالمِلّيثوان) المقابل لمدّة d (نصف نوتة أو ربع نوتة)، لإيقاع معيَّن t.

  let milliseconds d t = ...

نبدأ بحساب زمن ربع النوتة، (quarter)، للإيقاع المعيَّن:

    let quarter = 60000 / t in

بعد ذلك، وتبعًا للمدّة d، نُعيد quarter*2 مِلّيثوان لربع النوتة، وquarter مِلّيثوان لنصف النوتة:

    match d with
    | Half -> quarter * 2
    | Quarter -> quarter

الدالة التالية، sound، إما تعزف نوتة موسيقية وإما تُخرِج صمتًا:

  let sound t s = ...

بإيقاع t وإشارة s، تُجرِي الدالة sound مطابقة أنماط على s لتحديد ما إذا كانت نوتة موسيقية أم صمتًا:

    match s with
      | Note (p, d) ->
          ...
      | Rest r ->
          ...

تتيح لنا بنية مطابقة الأنماط هذه ليس فقط التمييز بين الباني المستخدم في إنشاء s، بل أيضًا استرجاع وسائط هذا الباني. إذًا، إذا كان s يقابل أول نمط (pattern)، وهو Note(p,d)، فإن المتغيرين p وd يُمثّلان على التوالي درجة النوتة ومدّتها المرتبطتين بهذا الباني. وفي النمط الثاني، يُمثّل المتغير r الصمت المرتبط بالباني Rest. وفي الحالتين، نطاق المتغيرات التي تُدخِلها الأنماط مقتصر على التعبير الواقع على الجانب الأيمن من السهم ->.

عندما يكون s على الشكل Note(p,d)، نحسب التردد f المرتبط بدرجة النوتة p باستخدام الدالة frequency. ثُمّ نستخدم الدالة Graphics.sound لإصدار صوت بتردد f مدّة (millisecondsdt):

      | Note (p, d) ->
        let f = frequency p in
        Graphics.sound f (millisecondes d t)

وعندما يكون s صمتًا على الشكل Restr، نصدر صوتًا بتردد صفر مدّة (millisecondsrt) مِلّيثوان.

      | Rest r ->
        Graphics.sound 0 (millisecondes r t)

أخيرًا، تعزف الدالة الأخيرة نوتات المقطوعة الواحدة تلو الأخرى، باستخدام الدالة sound:

  let play_score { symbols = l; metronome = t } =
    List.iter (sound t) l

معلومات إضافية

مطابقة الأنماط (Pattern Matching)

بصفة عامة، تُعمِّم بنية مطابقة الأنماط matchvwith ما اطلعنا عليه سابقًا في حالة القوائم (القسم 2.8 عكس ترتيب الأسطر في نص). فهي تحوي k فرعًا، يربط كل فرع نمطًا بتعبير:

  match v with
    | pattern_1 -> e_1
    | pattern_2 -> e_2
    | ...
    | pattern_k -> e_k

تُقيَّم القيمة v أوّلًا، ثُمّ تُقارَن، من الأعلى إلى الأسفل، بكل نمط. والتعبير الوحيد الذي تُقيّمه هذه البنية هو e_i المقابل لأول نمط متوافق مع شكل v.

صياغة الأنماط صياغة معبِّرة جدًا. فهي تتيح لنا تفكيك القيم المعقَّدة بسهولة، مثل القيم المعرَّفة باستخدام النوعين t وu التاليين:

  type t = A of int * float | B of string
  type u = { a : t; b : int * t }

وبالتالي، يتيح لنا النمط { b = (_, A (x, _)) } استرجاع العدد الصحيح 1 الممرَّر بوصفه وسيطًا للباني A في القيمة التالية:

  { a = B "foo"; b = (10, A(1, 4.5)) }

وبصورة غير رسمية، يُقرأ النمط { b = (_, A (x, _)) } على أنه «سجل يحوي حقله b زوجًا، مكوّنه الثاني قيمة مبنية باستخدام A بوسيطين، أولّهما مُسمًّى x».

يستطيع أوسمل أيضًا التحقق من شمولية (exhaustivity) مطابقة الأنماط، بما يضمن تغطية جميع الحالات الممكنة فعلًا. إذًا، بالنسبة إلى أي قيمة v من النوع u، يكشف المُصرِّف أن مطابقة الأنماط التالية غير شاملة:

  match v with
    | { a = A(_, x); b = (_, B y) } -> ...
    | { a = A(_, x); b = (_, A (y, _)) } -> ...
    | { a = B x; b = (_, B y) } -> ...

إنه يُشير حتى إلى أن القيم على الشكل { a=B _; b=(_, A (_, _)) } لا تُعالَج في مطابقة الأنماط هذه، مما قد يؤدي إلى خطأ في زمن التشغيل. وعلى النقيض، يتحقق المُصرِّف من أن البنية التالية شاملة فعلًا، وإن كان ذلك غير بديهي من باب الأولوية (a priori):

  match v with
    | { a = A(_, x); b = (_, B y) } -> ...
    | { a = A(_, x); b = (_, A (y, _)) } -> ...
    | { a = B x; b = (_, B y) } -> ...
    | { a = _;  b = (_, A(_, y)) } -> ...

تتيح لنا بنية مطابقة الأنماط أيضًا ربط التعبير ذاته بعدة أنماط. وهذه الأنماط، التي تُسمّى الأنماط البديلة (or-patterns)، تتخذ الشكل التالي:

  match v with
    | pattern_1 | pattern_2 | ... | pattern_k -> e
    | ...

القيد النحوي الوحيد هو أن كل نمط يجب أن يُدخِل أسماء المتغيرات نفسها، وأن تكون من النوع نفسه. فمثلًا، يمكننا كتابة النمط البديل التالي على قيم النوع u:

  match v with
    | { a = A(x, _) } | { b = (x, _) } -> ...
    | ...

ومن الممكن أيضًا ربط أسماء متغيرات بالأجزاء الفرعية لنمط باستخدام الترميز as، كما في المثال التالي:

  match v with
    | { a = B _ ; b = (_, (A (y, _) as z)) } -> (y, z)
    | ...

هنا، يُشير المتغير z إلى القيمة التي يُطابَقها النمط الفرعي (sub-pattern) A(y,_). وبالتالي، فإن تطبيق مطابقة الأنماط هذه على { a = B "foo"; b = (10, A(1, 4.5)) } سيُنتج الزوج (1,A(1,4.5)).

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

  match v with
    | pattern_1 when e -> e_1
    | ...

فمثلًا، يمكننا مطابقة قيم النوع u التي حقلها a على الشكل A(x,_)، مع x أكبر من 10، على النحو التالي:

  match v with
    | { a = A(x, _) } when x > 10 -> ...
    | ...

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

الأنواع الجَبْرية (Algebraic Types)

من الممكن أيضًا تعريف أنواع جبرية متعددة الأشكال (polymorphic). ولكي، يجب أن نشير إلى قائمة متغيرات الأنواع (أو البارامترات) التي تظهر في التعريف. فلننظر في المثال التالي:

  type (’a, ’b) t = C of ’a * int | D of ’b | E of int

هنا، النوع t مُبارمَد بمتغيرين ’a و’b. والبانيان C وD متعددا الأشكال. إذًا، كما في حالة الدالة متعددة الأشكال، يمكن تطبيق هذين البانيين على وسائط من أي نوع:

  # let v = C(3, "foo");;
  val v : (int, string) t = C(3, "foo")

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

  type ’a list = [] | :: of ’a * ’a list

ومثال آخر على النوع الجَبْري متعدد الأشكال هو النوع option في المكتبة القياسية، المعرَّف بـ:

  type ’a option = None | Some of ’a

وهو يُستخدم خاصةً لتمثيل قيمة لم تُهيَّأ بعد، أو نتيجة اختيارية. فمثلًا، تُعيد الدالة التالية إمّا None، عندما يتعذّر قسمة x على y، وإمّا Some(x/y):

  let division x y = if y = 0 then None else Some (x / y)

  # division 2 0;;
  - : int option = None

2.13 الأشجار الرباعية (Quadtrees)

برنامجنا التالي (الصفحة 219)، quad.ml، يعالج صورًا مربّعة بالأبيض والأسود بحجم 2n × 2n. إذا كانت الصورة سوداء أو بيضاء بالكامل، فتُعرض باستخدام ثابت يدل على لونها. وإلا، فتُفكَّك إلى أربع صور جزئية، كلٌّ منها بحجم 2n−1 × 2n−1، وفق الترتيب الموضَّح في الشكل 2.11.

الشكل 2.11: تفكيك صورة.

الصورة هي اتحاد الصور الجزئية الأربع. وفي برنامجنا، يقابل النوع quad هذا التمثيل.

  type quad = White | Black | Node of quad * quad * quad * quad

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

فلننظر في الصورة الواردة في الشكل 2.12. وتُعرض بالقيمة التالية من النوع quad:

  Node (Node (Black, Black, Black, White),
        Black,
        Node (Black, Black, Black, White),
        White)

الشكل 2.12: صورة بحجم 4 × 4.

ويمكننا أيضًا أن نعرض هذه القيمة بيانيًا على النحو التالي:

ولهذا نتحدَّث عن أشجار (trees) فيما يتعلق بمثل هذه القيم.

فلنكتب الآن دالة checker_board، التي تبني شجرةً ربعيةً مقابلةً لرقعة شطرنج بحجم 2n × 2n. وبذلك، تقابل checker_board3 الصورة الواردة في الشكل 2.13.

الشكل 2.13: رقعة شطرنج بحجم 8 × 8.

نسلك طريقة التعاود (recursion) على n. فإذا كان n يساوي 0، فنجري اختيارًا اعتباطيًا ونُعيد مربعًا أسود.

let rec checker_board = function
  | 0 -> Black

وإذا كان n = 1، نُعيد رقعة شطرنج بحجم 2 × 2:

  | 1 -> Node (White, Black, White, Black)

وأخيرًا، إذا كان n > 1، نبني رقعة شطرنج بحجم 2n−1 × 2n−1 نستخدمها أربع مرات لبناء رقعة شطرنج بحجم 2n × 2n.

  | n -> let q = checker_board (n - 1) in Node (q, q, q, q)

فلنكتب الآن دالة draw ترسم الصورة التي تمثلها شجرة رباعية. تأخذ هذه الدالة وسيطين هما إحداثيات المربع الذي نرغب في رسم الصورة فيه: الموضع (x,y) للنقطة السفلية اليسرى من الصورة، وطول الضلع w للمربع. ونسلك طريقة التعاود على بنية الشجرة الرباعية.

  let rec draw x y w = function

إذا كانت الشجرة تتألف من ورقة واحدة فقط، فنميّز بين حالتين: فبالنسبة للورقة البيضاء لا نفعل شيئًا؛ وبالنسبة للورقة السوداء نُظلّل المربع المحدَّد بـ x وy وw.

    | White -> ()
    | Black -> Graphics.fill_rect x y w w

أما إذا كنا في حالة الباني Node، فنبدأ بحساب طول ضلع الصور الجزئية الأربع، وهو w∕2.

    | Node (q1, q2, q3, q4) ->
        let w = w / 2 in

ثم نرسم الصور الجزئية بأربع نداءات تعاوبية للدالة draw. نمرر في كل حالة إحداثيات الزاوية السفلية اليسرى للصورة الجزئية المقابلة.

        draw x       y       w q1;
        draw (x + w) y       w q2;
        draw (x + w) (y + w) w q3;
        draw x       (y + w) w q4

وبهذه الطريقة، يمكننا رسم رقعة شطرنج بحجم 8 × 8 في مربع طول ضلعه 256 بنداء draw00256(checker_board3).

معلومات إضافية

البواني مع السجلّات (Records)

مع النوع quad الخاص بالأشجار الرباعية، من السهل أن يخطئ المرء في ترتيب الأشجار الفرعية للباني Node. فيجب أن نكون يقظين جدًا وأن نحفظ الشكل 2.11 في الذهن باستمرار. وبديل ذلك هو تسمية الأشجار الفرعية الأربعة، كما نفعل مع أنواع السجلّات:

  type quad =
    | White
    | Black
    | Node of { sw: quad; se: quad; ne: quad; nw: quad }

سواء داخل نمط مطابقة أو عند بناء قيمة، نستخدم صيغة السجلّات للتعامل مع وسائط الباني Node. وهكذا، نبني عقدة (node) على النحو التالي:

  Node { nw = a; sw = b; se = c; ne = d }

وكما نرى هنا، فإن ترتيب الحقول في الإعلان غير مهم. وكما هو الحال مع السجلّات، يمكننا استخدام مطابقة الأنماط (pattern matching) لاسترجاع قيمها:

  match q with
    | ...
    | Node { sw; se; ne; nw } -> ...

غير أننا لا نستطيع كتابة ما يلي:

  match q with
    | ...
    | Node r -> ...

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

ولفهم الفرق، لنقارن الباني Node الوارد أعلاه بالباني C من النوع t أدناه:

  type r = { a: int; b: bool; c: int }
  type t = C of r | ...

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

  match ... with
  | C r -> f r

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

اللوازم (Invariants)

قد نرغب في ضمان خاصية ألّا تتألف شجرة رباعية قط من أربع أوراق باللون نفسه، إذ سيكون ذلك تمثيلًا معقَّدًا بلا داعٍ. ولفرض هذه اللازمة، يجب أن نجعل quad نوعًا مجرَّدًا (abstract) أو نوعًا خاصًا (private). وبديلًا عن البواني Black وWhite وNode، يجب أن نوفّر ثابتين black وwhite، ودالة node معرَّفة بحيث تضمن اللازمة.

  let node = function
    | White, White, White, White -> White
    | Black, Black, Black, Black -> Black
    | q1, q2, q3, q4 -> Node (q1, q2, q3, q4)

ويُعرف هذا باسم باني ذكي (smart constructor).

المشاركة (Sharing)

سيُلاحظ القارئ اليقظ أن الدالة checker_board تجري نداءً تعاوبيًا وحيدًا، إذ تعيد استخدام نتيجتها أربع مرات. فما بنيناه ليس إذن شجرة، بل رسم موجَّه لا حلقات (DAG). ولهذا، يكون تصوير نتيجة checker_board3 الذي يعكس تمثيلها في الذاكرة بأدقّ وجه هو:

على وجه الخصوص، checker_board ن تعمل بزمن O(n) ومساحة O(n). وبالمقابل، فإن رسم نتيجتها يستغرق زمنًا قدره O(4n) لأن الدالة draw تجتاز الصور الجزئية الأربع تباعًا. وبعبارة أخرى، تجتاز الدالة draw شجرة دون أن تأخذ المشاركة القائمة في الذاكرة في الحسبان. ويشرح القسم 11.4 Hash-consing كيفية استغلال مثل هذه المشاركة.

الأشجار الثنائية (Binary Trees)

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

  type tree = Leaf | Node of tree * int * tree

ومثلًا، تقابل الأشجار ذات الأوراق الموسومة بسلاسل نصية النوع:

  type tree = Leaf of string | Node of tree * tree

سيجد القارئ أمثلة عديدة من مثل هذه الأشجار في الصفحات التالية.

الأشجار المتعددة الفروع (n-ary Trees)

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

  type tree = Node of tree list

ومن الجدير بالملاحظة أننا لم نعد بحاجة إلى باني خاص لتمثيل الأوراق، لأن القيمة Node[] تؤدي هذا الدور. وبالطبع، يمكننا توسيم عقد هذه الشجرة إن أردنا ذلك. ومثال على ذلك موجود في القسم 5.4 Prefix Trees.

2.14 حلّ مسألة الملكات N (N-Queens Problem)

نتعرض هنا للمسألة الكلاسيكية للملكات N: يجب وضع N ملكة على رقعة شطرنج بحجم N × N بحيث لا تتهدَّد أيٌّ منها الأخرى. ويعرض الشكل 2.14 أحد الحلول الـ92 عندما N = 8.

الشكل 2.14: أحد حلول مسألة الملكات الثماني.

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

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

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

لنفترض أننا وضعنا ملكات بالفعل على الأسطر الثلاثة الأولى. وليس ثمة حاجة إلى النظر سوى في خمسة أعمدة في السطر الرابع (في أسفل رقعة الشطرنج).

(1)

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

(2)

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

(3)

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

(4)

سيسير برنامجنا بطريقة تعاودية، متتبعًا في كل لحظة ثلاث مجموعات من الأعمدة: المجموعة cols وهي الأعمدة التي بقيت للنظر فيها؛ والمجموعة d1 وهي الأعمدة التي يجب تجنبها لأن الملكات الموضوعة فيها ستكون متهدَّدة على قُطْر أيسر؛ والمجموعة d2 وهي الأعمدة التي يجب تجنبها لأن الملكات الموضوعة فيها ستكون متهدَّدة على قُطْر أيمن. وفي مثالنا، إذا رقّمنا الأعمدة بدءًا من اليمين، فلدينا cols = {0,2,5,6,7} وd1 = {3,5,6} و d2 = {0,3}، كما هو موضَّح في الأشكال أعلاه (على التوالي في (1) و(2) و(3)). ومجموعة الأعمدة التي يمكن وضع الملكات فيها تُحصَّل بحساب

الفرق النظري للمجموعات cols∖d1∖d2، وهو ما يعطي المجموعة {2,7}، كما هو موضَّح في الشكل (4).

وللتعامل مع مثل هذه المجموعات من الأعداد الصحيحة، نستخدم الوحدة Set.Make من المكتبة القياسية لأوسمل. وهذا مُوَلِّد (functor) نُعرِضه (instantiate) بنوع مجهَّز بترتيب كلي. (وسيُشرح قانون (code) مثل هذا المولِّد لاحقًا في هذا الكتاب، في القسم AVL من الفصل 5.)

نختار هنا الترتيب المعتاد على الأعداد الصحيحة، الذي توفره الدالة compare من المكتبة Stdlib.

  module S = Set.Make(struct type t = int let compare = compare end)

تُوفّر الوحدة الناتجة S بنية بيانات S.t تمثل مجموعة من الأعداد الصحيحة، وثابتًا S.empty يقابل المجموعة الخالية، وعمليات مثل S.add (إضافة عنصر) وS.remove (إزالة عنصر) وS.diff (الفرق النظري للمجموعات)، إلخ. وخاصية مهمة لهذه البنية هي دوامها (persistence). وهذا يعني أن العمليات المطبَّقة على هذه البنية لا تعدّلها، بل تُعيد بدلًا من ذلك بنى جديدة. وهكذا، إذا كان لدينا مجموعة s من النوع S.t، فإن التعبير S.add4s يدل على مجموعة جديدة (تحوي 4 وجميع عناصر s)، في حين تبقى المجموعة s دون تعديل.

فلنكتب الآن برنامجنا باستخدام دالة تعاوبية count تأخذ كوسائط المجموعات الثلاث cols وd1 وd2 الموضَّحة أعلاه:

  let rec count cols d1 d2 =

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

  if S.is_empty cols then 1 else

وإلا، نحسب مجموعة الأعمدة التي يمكن وضع الملكات فيها باستعمال التعبير

S.diff(S.diffcolsd1)d2، كما شُرح أعلاه. ثم نجتاز عناصر هذه المجموعة باستخدام المكرِّر (iterator) S.fold، بحيث يكون المُجمِّع هو عدد الحلول الموجودة حتى الآن.

    S.fold
      (fun c res -> ...)
      (S.diff (S.diff cols d1) d2)
      0

بالنسبة لكل عمود c يمكن وضع ملكة فيه، يكفي نداء count نداءً تعاوبيًا بالمجموعات الثلاث بعد تعديلها على النحو الواجب. ولكي نعدّل cols، يكفي إزالة العنصر c باستخدام S.remove. ولكي نعدّل d1 وd2، نستخدم S.add لإضافة العمود c إلى كل منها، ثم نزيح عناصرها بمقدار وحدة واحدة على الوجه اللائق. ولفعل ذلك، نعرّف دالة map تطبّق دالة f على جميع عناصر المجموعة s، أي إنها تبني المجموعة {f(x)∣x ∈ s}. ويمكننا كتابتها مثلًا باستخدام S.fold.

  let map f s = S.fold (fun x s -> S.add (f x) s) s S.empty

بالانطلاق من هذه الدالة، يمكن تعديل المجموعة d1 باستخدام mapsucc، حيث succ هي الدالة المعرَّفة مسبقًا funx->x+1. وكذلك تُعدَّل المجموعة d2 باستخدام mappred، حيث pred هي الدالة المعرَّفة مسبقًا funx->x-1. ولذلك تكون الدالة الممرَّرة كوسيط إلى S.fold بالشكل التالي:

      (fun c res ->
        let d1 = map succ (S.add c d1) in
        let d2 = map pred (S.add c d2) in
        res + count (S.remove c cols) d1 d2)

بهذا تكون الدالة count مكتملة. ومن المهم أن نلاحظ هنا الدور المحوري الذي يلعبه دوام المجموعات cols وd1 وd2. فهذه المجموعات تُعاد استعادتها لكل قيمة من قيم c، ولذلك يجب ألّا تعدّلها العمليتان S.add وS.remove.

ولحلّ مسألة الملكات N، يكفي نداء count مع cols مساويةً للمجموعة {0,1,…,N − 1}، وd1 وd2 مساويتين كلًّا منهما للمجموعة الخالية. ولهذه الغاية، نعرّف دالة upto تبني المجموعة {0,1,…,n}.

  let rec upto n = if n < 0 then S.empty else S.add n (upto (n-1))

والجزء الرئيسي من البرنامج يسترجع قيمة N من سطر الأوامر ثم يعرض النتيجة التي تحصّلت عليها count.

let () =
  let n = int_of_string Sys.argv.(1) in
  Format.printf "%d@." (count (upto (n - 1)) S.empty S.empty)

وهكذا يمكننا حصر 365,596 حلًّا لمسألة الملكات الأربعة عشر في أقلّ من دقيقة.

معلومات إضافية

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

تتألف العملية من تعديل اثنين من المؤشّرات، على النحو التالي:

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

وبالمقابل، فإن بنية البيانات الدائمة (persistent) هي بنية بيانات لا تعدّل عملياتها وسائطها قط؛ بل تُعاد قيم جديدة بدلًا من ذلك. وبالطبع، يمكننا تحويل بنية بيانات إلى بنية دائمة بنسخها بصورة منتظمة، غير أن ذلك سيكون غير فعّال على نحو فظيع. وهناك وسائل أخرى أكثر فعاليةً لتحويل بنية بيانات أمرِيّة إلى بنية دائمة. انظر مثلًا القسم 4.4 Persistent Arrays.

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

إذا عرّفنا قائمة l بـ letl=[1;2;3]، فإن l، من حيث تمثيلها في الذاكرة، مؤشّر. فهي تشير إلى كتلة أولى تحوي 1 ومؤشّرًا إلى كتلة ثانية، وهكذا دواليك:

وإذا عرّفنا الآن قائمة l’ بإضافة عنصر آخر إلى القائمة l، بالإعلان letl’=0::l، فسنكون أمام الوضع التالي:

يثمر تطبيق الباني :: من تخصيص كتلة جديدة، عنصرها الأول هو 0 وعنصرها الثاني مؤشّر له القيمة نفسها التي للمؤشّر l. ويستمر المتغير l في الإشارة إلى الكتل نفسها كما كان من قبل. وبصفة عامة، فإن أي دالة قد نكتبها على القوائم تتميّز بأنها لا تعدّل القوائم الممرَّرة إليها كوسائط.

من المهم جدًا أن نفهم أن ما ورد أعلاه ينطوي على مشاركة. فإعلان l’ يخصّص كتلةً وحيدة (لأننا طبّقنا بانيًّا واحدًا فقط)، وتُعاد استخدام الكتل المكوِّنة لـ l دون تعديل. فلدينا قائمتان فيهما ثلاثة عناصر وأربعة عناصر على التوالي، هما [1;2;3] و[0;1;2;3]، لكن ثمة أربع كتل في الذاكرة فحسب. وعلى وجه الخصوص، لا يجري أي نسخ. وبصفة عامة، لا تجري أوسمل نسخًا للقيم قط، إلا إذا كتبنا صراحةً دالةً لفعل ذلك. ومثل هذه الدالة ستكون بلا فائدة في حالة القوائم لأن القائمة لا يمكن تعديلها في موضعها. والدالة التي تنسخ القيم غير مفيدة إلا إذا كانت بنى البيانات المعنية قابلةً للتعديل.

صار من الواضح الآن لماذا كان إضافة عنصر إلى نهاية القائمة أصعب من إضافته إلى مقدّمتها. والسبب هو أن ذلك يستلزم تعديل القائمة l في موضعها:

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

  let rec append l1 l2 = match l1 with
    | [] -> l2
    | x :: l -> x :: append l l2

نلاحظ أن هذه الدالة تُنشئ عددًا من الكتل مساويًا لعدد كتل l1 ولا تشارك إلا في كتل l2. وهكذا، إذا أعلنّا letl’=[4;5] وربطنا l وl’ بـ letl’’=appendll’، فسنكون أمام الوضع التالي:

جرى نسخ كتل l ومشارَكة كتل l’.

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

ومن الأهمية بمكان أن عناصر القائمة لا تنسخها الدالة append هي نفسها. ففي الواقع، المتغير x في قانون append يدل على عنصر من نوع اعتباطي ولا يُنسخ هو نفسه. وهذا الأمر يُحدث فرقًا في الواقع عند التعامل مع قوائم الأعداد الصحيحة. لكن إذا كانت لدينا قائمة l بثلاثة عناصر من نوع أكثر تعقيدًا، مثل القائمة [(1,2,3);(4,5,6);(7,8,9)]، فإن هذه العناصر ستكون مشترَكةً بين l وappendl[(10,11,12)]:

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

  type ’a mlist = Nil | Cons of ’a * ’a mlist ref

هنا، الوسيط الثاني للباني Cons هو مرجع (reference). وبخلاف اللغات الأمرِيّة، تُتيح أوسمل إمكانية تعريف بنى بيانات لا يتغيّر عليها الحال بصورة طبيعية وآمنة في الوقت نفسه. (وحتى لو برمجنا بنية بيانات دائمة بلغغة C، فإن نظام الأنواع لا يمكن أن يمنع التعديل في الموضع، لأن جميع البيانات في C قابلة للتعديل).

وأخيرًا، يجب ألّا ننسى أن الذاكرة غير المستخدمة تُستعاد تلقائيًا. فلننظر مثلًا في التعبير التالي:

  let l = [1;2;3] in append l [4;5;6]

الكتل الثلاث لـ l تُنسخ فعليًا أثناء بناء القائمة [1;2;3;4;5;6]، لكن يمكن استعادتها مباشرةً إذ لم يبقَ هناك ما يشير إليها في أي موضع. (ويقدّم الفصل 3 تفاصيل أكثر عن إدارة الذاكرة.)

المزايا العملية للدوام

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

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

الدوام ليس مفيدًا للصحّة فقط، بل هو أيضًا أداة قوية في السياقات التي يكون فيها الرجوع إلى الخلف ضروريًا. فلنفترض مثلًا أننا نكتب برنامجًا لإيجاد طريق للخروج من متاهة باستخدام دالة find تأخذ كوسيط حالةً دائمة وتُعيد قيمة منطقية تدل على نجاح البحث. وتُعيد دالة possible_moves التحرّكات الممكنة من حالة معيّنة في صورة قائمة. ولما كانت نوع البيانات دائمًا، فإن دالةً أخرى، move، تُعيد الحالة الناتجة عن تحرّك ما إلى جانب الحالة الحالية. كما نفترض أن دالةً منطقيةً is_exit تُعيد ما إذا كانت حالةٌ معيّنة تقابل المخرج. ويمكننا حينئذٍ كتابة الدالة find على النحو التالي:

  let rec find e =
    is_exit e || try_move e (possible_moves e)
  and try_move e = function
    | [] -> false
    | d :: r -> find (move d e) || try_move e r

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

  let rec find () =
    is_exit () || try_move (possible_moves ())
  and try_move = function
    | [] -> false
    | d :: r -> (move d; find ()) || (undo_move d; try_move r)

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

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

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

   try
     ... perform modifications ...
   with e ->
     ... restore the database to a coherent state,
         then handle the error ...

إذا استخدمنا بنية بيانات دائمة لقاعدة البيانات، فيمكن تخزينها في مرجع. فلنُسمِّه db. والعملية التي تُعدّل قاعدة البيانات تضبط قيمة هذا المرجع:

   let db = ref ( ... initial database ... )
   ...
   try
     db := ... operation that modifies the database !db ...
   with e ->
     ... handle the error ...

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

الواجهات والدوام

نوع بيانات القوائم دائم بجلاء لأنه نوع ذو تعريف معلوم، أي إنه ملموس (concrete) ولا يتغيّر عليه الحال. وعندما تُنفّذ وحدةٌ من وحدات أوسمل بنية بيانات، معلنةً كنوع مجرَّد (abstract)، فإن طبيعتها الدائمة أو الأمرِيّة غير بيّنة. وبالطبع، يمكن إحاطة المبرمج بهذا الأمر عن طريق تعليق مناسب في الواجهة. غير أنه، عمليًا، هي أنواع العمليات التي تُوفّر هذا المعلومة. فلننظر في مثال بنية بيانات دائمة تمثل المجموعات المنتهية من الأعداد الصحيحة. تبدو واجهة مثل هذه الوحدة هكذا:

  type set
  val empty : set
  val add : int -> set -> set
  val remove : int -> set -> set
  ...

الطبيعة الدائمة للمجموعات ضمينيّة في الواجهة: فالعمليتان add وremove تُعيدان قيمة من النوع set، أي مجموعةً جديدةً. وحقيقة أن المجموعة الخالية empty ثابتٌ وليست دالةً تجعل الدوام أوضح بعد. فجميع مواضع empty ستكون مشتركةً بصرف النظر عن تمثيلها. وهذا ما لم يكن ممكنًا مع بنية قابلة للتعديل.

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

  type set
  val create : unit -> set
  val add : int -> set -> unit
  val remove : int -> set -> unit
  ...

هنا، دالة الإضافة، add، لا تُعيد شيئًا لأنها تضيف عنصرًا في موضعه إلى بنية البيانات، والأمر نفسه ينطبق على العمليات الأخرى. وتحلّ دالة create التي تأخذ وسيطًا من النوع unit محلّ القيمة empty. فكل نداء لـ create يجب أن يبني نسخةً جديدةً من بنية البيانات حتى لا تؤثر تعديلات إحداها في موضعها على الأخرى.

وللأسف، فإن نظام أنواع أوسمل لا يمنع الخلط بين نوعي بنى البيانات. وهكذا، يمكنك أن تعطي النوع int->set->set لدالة تضيف عنصرًا إلى مجموعة عبر الآثار الجانبية، مثلًا بإعادة المجموعة الممرَّرة إليها كوسيط. وعلى العكس، يمكنك أن تعطي النوع unit->set لدالة empty تُعيد مجموعةً خاليةً دائمة. وفي الحالتين، هذا بلا فائدة وخطر محتمل.

غير أن هذا لا يعني أن بنية البيانات الدائمة يجب أن تُبرمج بالضرورة دون أي آثار جانبية. فالتعريف الجيّد لـ دائم هو:

دائم = لا يتغيّر عليه الحال من وجهة الرصد (observationally immutable)

وبعبارة أخرى، ليس تطبيقيًا خالصًا (purely applicative)، بمعنى غياب الآثار الجانبية. وليس لدينا سوى تضمين في اتجاه واحد:

تطبيقي خالص ⇒ دائم

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

الشكل 2.15: أصناف مختلفة من بنى البيانات.

2.15 تمارين

رسم قلب

2.1 عدِّل البرنامج 2 ليرسم مجموعة النقاط الواردة في الشكل 2.1.

2.2 اكتب برنامجًا يرسم الشكل أدناه.

مجموعة ماندلبروت

2.3 عدِّل رسم مجموعة ماندلبروت عبر تلوين النقاط التي لا تنتمي إلى المجموعة بحسب أول قيمة للعدد i تتحقق عندها المتراجحة xi2 + yi2 > 4. ويمكن اختيار اللون، مثلًا، بالاستكمال الخطي (interpolation) بين لونين محدَّدين سابقًا، ثم باستعمال الدالة Graphics.rgb (انظر القسم 2.10بريك أوت دون الطوب) وقاعدة الثلاثة البسيطة.

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

2.5 اكتب برنامجًا يرسم ندفة ثلج كوخ (Koch snowflake). وتُحصَّل الندفة بتتبُّع ثلاث منحنيات كوخ على الأضلاع الثلاثة لمثلث متساوي الأضلاع. ويُعرَّف منحنى كوخ بعمق n بين نقطتين A و B على النحو التالي: عندما n = 0، يكون هو الواصل بين A و B.

وعندما n > 0، يُقسَّم الواصل [A,B] إلى ثلاثة وصول متساوية الطول، وهي [A,C] و [C,E] و [E,B]. وتُعرَّف النقطة D على أنها الرأس الثالث للمثلث متساوي الأضلاع CED:

ثم نرسم أربعة منحنيات كوخ بعمق n − 1 على الوصلات الأربعة [A,C] و [C,D] و [D,E] و [E,B].

وباختيار عمق ابتدائي كبير بما يكفي، نحصل على رسم بالشكل التالي:

2.6 ليكن u0 عددًا صحيحًا أكبر من 1، وليكن (un) المتتالية المعرَّفة بالعلاقة:

{u/2ifuisevenun+1=nn3un+1otherwise\begin{cases} u /2 if u is even un + 1 = n n 3un + 1 otherwise \end{cases}

اكتب برنامجًا يقرأ قيمة u0 باستعمال read_int ثم يعرض القيم المتتالية للمتتالية (un) ما دام un > 1. (تنص فرضية كولاتز (Collatz conjecture) على أنه لأي قيمة لـ u0 نصل دائمًا إلى الدورة 1 → 4 → 2 → 1 →…. وقد صيغت هذه الفرضية سنة 1928، وهي لا تزال تستعصي على أفضل جهود الرياضيين.)

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

اكتب برنامجًا باسم hanoi يقرأ قيمة n ثم يعرض تتابعًا صحيحًا من الحركات لحل المسألة، مثلًا على النحو التالي:

  > ./hanoi
  4
  moving disk from 1 to 3
  moving disk from 1 to 2
  moving disk from 3 to 2
  moving disk from 1 to 3
  ...

غربال إراتوستينس

2.8 اكتب دالةً من النوع sum:intarray->int تحسب مجموع عناصر مصفوفة، أولًا باستعمال حلقة for، ثم بدالية تكرارية (recursive function).

2.9 اكتب دالةً من النوع occurs:intarray->int->bool تحدد، لمصفوفة أعداد صحيحة a وقيمة صحيحة v، ما إذا كانت v تظهر في a. اكتب نسختين من البرنامج، إحداهما باستعمال حلقة while والأخرى بدالية تكرارية.

2.10 اكتب دالةً من النوع binary_search:intarray->int->bool تحدد، لمصفوفة أعداد صحيحة a مرتبةً ترتيبًا تصاعديًا، وقيمة صحيحة v، ما إذا كانت v تظهر في a. استعمل البحث الثنائي (binary search) لتحصل على تعقيد O(log n)، حيث n هو طول المصفوفة a.

2.11 اكتب دالةً من النوع shuffle:intarray->unit تخلط عناصر مصفوفةً عشوائيًا باستعمال الخوارزمية التالية، المسماة «خلط نوث» (Knuth shuffle)، حيث n هو حجم المصفوفة:

لكل i من 1 إلى n − 1
ليكن j عددًا صحيحًا عشوائيًا بين 0 و i (شاملًا الطرفين)
بادل العنصرين ذَي المؤشرين i و j

يمكنك استعمال Random.int k للحصول على عدد صحيح عشوائي بين 0 و k − 1. وبالطبع، يمكن استعمال هذه الخوارزمية للمصفوفات من أي نوع.

رسم منحنى

2.12 اكتب دالةً من النوع sum:(int->int)->int->int->int تأخذ دالة f وعددين صحيحين i و j وسيطين، وتحسب المجموع التالي:

k=j∑f(k).k=ik = j \sum f(k). k = i

2.13 اكتب دالة dicho من النوع:

dicho:(float->float)->float->float->float

تبحث عن صفر دالة رتيبة (monotonic function) f على فترة [a,b] باستعمال البحث التقريبي الثنائي (dichotomic search). والفكرة كالتالي: احسب نقطة المنتصف x للفترة [a,b]، وقارن إشارتَي f(a) و f(x). بحسب النتيجة، أعد الحساب على الفترة [a,x] أو [x,b]. توقف عندما يكون a و b قريبين من بعضهما بما يكفي. يمكنك افتراض أن [a,b] تحتوي صفرًا للدالة f.

نسخ ملف

2.14 عدِّل البرنامج 7 بحيث يعالج بشكل صحيح الحالة التي يتعذر فيها فتح أحد الملفين. وهذا يثير استثناءً (exception) من الشكل Sys_error s، حيث s سلسلة تشرح طبيعة الخطأ (الملف غير موجود، الإذن مرفوض، إلى آخره). ويجب عرض هذه الرسالة قبل إنهاء البرنامج باستعمال exit1.

2.15 في لغات مثل C و Java، تُخرج الجملةُ break أقرب حلقةٍ محيطة، وتقفز الجملةُ continue إلى التكرار التالي للحلقة. وبالتالي، يعرض كود C التالي 124567:

  for (int i = 0; i < 10; i++) {
    if (i == 3) continue;
    if (i == 8) break;
    printf("%d", i);
  }

اشرح كيف تُترجم هاتين الجملتين إلى أوسمل. يمكنك استعمال استثناءين، Break و Continue، لتحقيق ذلك.

عكس ترتيب الأسطر في نص

2.16 اكتب دالة mult:intlist->int تحسب حاصل ضرب جميع عناصر قائمة من الأعداد الصحيحة. تأكد من إعادة 0 عند أول ظهور للعدد الصحيح 0.

2.17 أعد التمرين السابق، ولكن هذه المرة ارفع استثناءً إذا صودف 0، لتجنب ضرب العناصر الأولى من القائمة دون داعٍ.

2.18 أعد التمرين 2.16 بكتابة الدالة mult كدالة تكرارية ذيلية (tail-recursive).

2.19 اكتب دالة insert:int->intlist->intlist تُدخِل عددًا صحيحًا في قائمة من الأعداد الصحيحة مرتبة ترتيبًا تصاعديًا. تجنَّب إنشاء نسخة غير ضرورية من الجزء من القائمة الأولية الواقع بعد نقطة الإدخال.

2.20 باستخدام الدالة insert أعلاه، اكتب دالة insertion_sort:intlist->intlist ترتب قائمة من الأعداد الصحيحة ترتيبًا تصاعديًا باستخدام الخوارزمية التالية، المعروفة باسم الترتيب بالإدخال (insertion sort): بدءًا من القائمة الفارغة، أدخِل كل عنصر بالتتابع، باستخدام الدالة insert. يُوصَف الترتيب بالإدخال بالتفصيل في الفصل 12.

تحويل الأعداد الصحيحة من أساس عشوائي

2.21 اكتب دالة mem:’a->’alist->bool تحدد ما إذا كان عنصر موجودًا في قائمة، باستخدام عامل المساواة =. توجد هذه الدالة في المكتبة القياسية تحت اسم List.mem.

2.22 اكتب دالة count:’a->’alist->int تحسب عدد مرات ظهور عنصر في قائمة، باستخدام عامل المساواة =.

2.23 أعد كتابة دالة count من التمرين السابق باستخدام مكرِّر (iterator).

2.24 اكتب دالة append:’alist->’alist->’alist تلصق قائمتين. إذا كانت l1 = [x1;…;xn] و l2 = [y1;…;ym]، فإن نتيجة append l1 l2 يجب أن تكون القائمة [x1;…;xn;y1;…;ym] ذات الطول n + m. تصرَّف بالتكرار على القائمة الأولى، وبالتالي إجراء n استدعاء تكراري. توفر مكتبة أوسمل القياسية هذه الدالة تحت اسم List.append وكعامل الوصل @.

2.25 باستخدام الدالة append أعلاه، اكتب دالة rev من النوع ’alist->’alist تعكس ترتيب عناصر قائمة، أي بحيث rev [x1;…;xn] = [xn;…;x1]. في القسم التالي، سنناقش طريقة أكثر كفاءة لتنفيذ هذه الدالة.

2.26 اكتب دالة subseq:’alist->’alist->bool تحدد ما إذا كانت قائمة w1 تسلسلًا فرعيًا (sub-sequence) لقائمة أخرى w2، أي يمكن الحصول على w1 بإزالة صفر أو أكثر من عناصر w2. على سبيل المثال، [1;5;4;1] تسلسل فرعي لـ [3;1;1;5;0;4;1].

2.27 اكتب دالة exists:(’a->bool)->’alist->bool تأخذ دالة بولية p وقائمة l كوسيطين، وتحدد ما إذا كانت l تحتوي على عنصر واحد على الأقل x بحيث p(x) تساوي true.

2.28 باستخدام List.fold_left، اكتب دالة forall:(’a->bool)->’alist->bool تحدد ما إذا كانت جميع عناصر قائمة من النوع ’alist تفي بشرط معطى بدالة من النوع ’a->bool. ما هي مشكلة هذا الحل؟ اقترح نسخة أكثر كفاءة.

2.29 اكتب دالة filter:(’a->bool)->’alist->’alist تأخذ دالة بولية p وقائمة l كوسيطين، وتعيد قائمة جميع العناصر x من l التي تحقق p(x) = true. حافظ على ترتيب العناصر. توجد هذه الدالة في المكتبة القياسية تحت اسم List.filter.

2.30 باستخدام مكرِّر، اكتب دالة max_seq:boollist->int تعيد طول أطول تسلسل من القيم true المتتالية في قائمة معينة.

2.31 اكتب دالة first:(’a->bool)->’alist->’a تعيد أول عنصر من القائمة الممررة كوسيطة يحقق الشرط المعطى. إذا لم يكن مثل هذا العنصر موجودًا، يجب أن ترفع الدالة الاستثناء Not_found.

2.32 اكتب مكرِّر fold_pairs من النوع:

fold_pairs:(’a->’b->’b->’a)->’a->’blist->’a

يأخذ المكرِّر كوسيطين دالة f، قيمة v، وقائمة [x1;…;xn]، ويعيد:

f(f(...f(f(v,x1,x2),x2,x3),...,xn−1,xn),xn,x1)f(f(...f(f(v,x1,x2),x2,x3),...,xn -1,xn),xn,x1)

بعبارة أخرى، تجتاز الدالة جميع أزواج العناصر المتتالية (xi,xi+1)، حيث تُعتبَر القائمة دائرية.

2.33 اقترح دالة لإنشاء مصفوفة init_matrix، مشابهة لـ Array.init، من النوع:

    init_matrix: (int -> int -> ’a) -> int -> int -> ’a array array

2.34 اكتب دالة تجول:

    iter_matrix: (int -> int -> ’a -> unit) -> ’a array array -> unit

تطبِّق دالة معينة على جميع عناصر مصفوفة. الوسيطان الأولان للدالة هما مؤشرا العنصر المقابل. اشرح لماذا يكون تجول المصفوفة صفًا صفًا (row-wise) أكثر كفاءة من تجولها عمودًا عمودًا (column-wise).

بريك أوت دون الطوب

2.35 بالنظر إلى ملف a.ml يحتوي على let()=Printf.printf"A\n" وملف b.ml يحتوي على let()=Printf.printf"B\n"، قم بترجمة هذين الملفين بشكل منفصل وتحقق من الحصول على نتائج مختلفة اعتمادًا على الترتيب الذي تُمرَّر به الملفات إلى الرابط (linker).

2.36 بالنظر إلى ستة ملفات a.mli، a.ml، b.ml، c.ml، d.mli، و d.ml، وبمعرفة أن A و B يعتمدان على C، وأن C يعتمد على D، أعطِ جميع الطرق الممكنة لترجمة وربط برنامج يحتوي على وحدات الترجمة الأربع A، B، C، و D.

2.37 أعد كتابة كود بريك أوت (Breakout) في ملف واحد مع وحدتين فرعيتين Draw و Breakout. أعطِ الوحدة Draw نفس الواجهة المعرفة في draw.mli.

سلحفاة لوغو

2.38 أعد التمرين 2.5 الذي يرسم ندفة ثلج كوخ باستخدام سلحفاة لوغو.

تلميح: اكتب دالة تكرارية von_koch:int->float->unit يكون وسيطها الأول عدد الخطوات التكرارية والثاني طول المقطع [A,B].

2.39 أعد كتابة الدالة الدالية Turtle כך تكون أيضًا مُعَلَّمَة بوحدة ذات توقيع:

    val open_graph: int -> int -> unit
    val draw_line: int -> int -> int -> int -> unit

هنا، open_graph w h تفتح نافذة بأبعاد w ×h و draw_line x1 y1 x2 y2 ترسم مقطعًا بين النقطتين (x1,y1) و (x2,y2). ثم نفِّذ وحدة بواجهة كهذه باستخدام Graphics.

2.40 نريد تعريف وحدة تمثل ملفات مزودة بأذونات قراءة وكتابة. لهذا الغرض، نقدم نوع permission.

    type permission = Read | Write

عرِّف وحدة Access للتعامل مع حقوق الوصول. ستوفر هذه الوحدة نوعًا مجردًا t، قيمة من النوع t هي default، تمثل الوصول للقراءة والكتابة، ودالتين get و set تسمحان، على التوالي، بالحصول على إذن وتعيينه.

    val get : t -> permission -> bool
    val set : t -> permission -> bool -> t

ثم عرِّف وحدة أخرى File لتمثيل ملف مزود بحقوق وصول. ستصدِّر هذه الوحدة نوع سجل خاص t، يحتوي على اسم الملف في حقل من النوع string وحقوق الوصول في حقل mutable من النوع Access.t. ستوفر دالة create:string->t تأخذ اسم الملف كوسيطة، دالة chmod لتعديل حقوق الوصول، دالة open_in:t->in_channel لفتح ملف للقراءة، ودالة open_out:t->out_channel لفتح ملف للكتابة. الدالتان الأخيرتان

سترفعان استثناء PermissionDenied في حال عدم كفاية الأذونات.

2.41 اكتب وحدات متعددة للتعامل مع القيم النقدية بعملات مختلفة. يجب أن تكون لجميع الوحدات نفس التوقيع:

  module type MONEY = sig
    type t = private { i : int; f : int }
    val create : int -> int -> t
    val add : t -> t -> t
  end

تمثَّل القيمة النقدية بعدد صحيح i وكسر f بين 0 و 99، يمثل عدد السنتات. العدد الصحيح i موقع. اكتب وحدة Money تنفذ التوقيع MONEY. اشتق منها وحدتين Euro و Dollar، كلتاهما ذات توقيع MONEY وبنية Money، لكن بنوعي Euro.t و Dollar.t متميزين. أخيرًا، اكتب دالة euros_to_dollars:float->Euro.t->Dollar.t تحوِّل اليورو إلى دولارين عند إعطاء سعر صرف.

2.42 اكتب وحدة لتمثيل مجموعات من الأعداد الصحيحة بقوائم مرتبة ترتيبًا تصاعديًا، بالتوقيع التالي:

  module type ISET = sig
    type t
    val empty : t
    val add : int -> t -> t
    val union : t -> t -> t
    val mem : int -> t -> bool
  end

ما هي ميزة جعل النوع t نوعًا مجردًا؟

2.43 أعد كتابة كود التمرين السابق على شكل دالة دالية (functor) مُعلمة بنوع العناصر ودالة تحدد ترتيبًا كليًا عليها، أي:

  module type ELT = sig type t val compare: t -> t -> int end
  module Set(E: ELT) : ... = struct ... end

هنا، قيمة compare x y سالبة قطعًا إذا x < y، صفرية إذا x = y، وموجبة قطعًا إذا x > y.

2.44 طبِّق دالة الدالة من التمرين السابق للحصول على مجموعات من الأعداد الصحيحة الزوجية، مانحًا إياها ترتيبًا كليًا عشوائيًا.

2.45 اكتب بنية بيانات لحدوديات متغير واحد. الفكرة هي تمثيل حدية باستخدام القائمة المرتبة لحدودها (monomials)، حيث يمثَّل كل حدٍّ بزوج من معامل وأس. وهكذا، تُمثَّل الحدية X7 − 3X4 + 2 بالقائمة [(1,7);(−3,4);(2,0)]. من أجل أن تكون عامة بالنسبة لحلقة المعاملات، اكتب بنية الحدوديات كدالة دالية Poly مُعلمة بوحدة ذات توقيع:

    module type Ring = sig
      type t
      val zero : t
      val one : t
      val add : t -> t -> t
      val mul : t -> t -> t
      val equal : t -> t -> bool
    end

إذا كان R يُشير إلى وسيط دالة الدالة Poly، يجب أن توفر الأخيرة الدوال التالية:

    type t
    val create: (R.t * int) list -> t
    val add: t -> t -> t
    val eval: t -> R.t -> R.t

هنا، t هو نوع الحدوديات، create تنشئ حدية بناءً على قائمة من الحدود، add تجمع حديتين، و eval تقيِّم حدية عند نقطة. تلميح: ابدأ بالدالة add (انظر التمرين 2.42) ثم استخدمها لكتابة الدالة create.

2.46 واصِل التمرين السابق بإضافة ثابتتين، zero و one، ودالتين، mul و equal، إلى توقيع دالة الدالة Poly. هذا يمنح الحدوديات بنية حلقة. بعبارة أخرى، يمكن كتابة توقيع دالة الدالة Poly بمصطلحات التوقيع Ring. البنيان include هو اختصار نحوي لتضمين تعريف توقيع في آخر:

    sig
      include Ring
      val create: (R.t * int) list -> t
      val eval: t -> R.t -> R.t
    end

وبذلك، يمكن الحصول على حدوديات بعدة متغيرات بتطبيق دالة الدالة Poly عدة مرات متتالية. على سبيل المثال، تُحصل بنية حدوديات ثلاثة متغيرات ومعاملات صحيحة كالتالي:

    module P = Poly(Poly(Poly(Int)))

يُفترَض هنا أن Int تنفذ التوقيع Ring للأعداد الصحيحة.

أشجار رباعية (Quadtrees)

2.47 اكتب دالة rotate:quad->quad تدير صورة عكس اتجاه عقارب الساعة بمقدار 90 درجة.

2.48 اكتب دالة mirror:quad->quad تبني التماثل المرآتي على المحور العمودي لصورة ممثلة بشجرة رباعية. هكذا، تسمح الدالة mirror بالتبديل بين الصورتين التاليتين:

2.49 اكتب دالة fractal:int->quad تبني شجرة رباعية تمثل كسير سجادة سيربينسكي (Sierpiński carpet fractal)، بتكرار عملية التحلل التالية:

حل مشكلة N-Queens (الملكات N)

2.50 عدِّل البرنامج 16 ليعيد أول حل موجود، في شكل مصفوفة a تعطي العمود a[i] للملكة الموجودة في الصف i. عندما لا يوجد حل، يجب رفع الاستثناء Not_found.

  1. حل آخر، تتبناه جداول التجزئة (hash tables) في مكتبة أوسمل القياسية، يتكون في استخدام مصفوفة حجمها n قوة لـ 2. يمكن حينئذ تنفيذ عملية الباقي (modulo) بـ land(n-1)، مع ميزة إضافية هي كونها أرخص بكثير من القسمة. ↩︎

  2. يأتي هذا من كلمة retrieval (الاسترجاع). ↩︎

  3. البرنامج seq أداة يونكس (Unix) تعرض جميع الأعداد الصحيحة من 1 إلى n، عدد صحيح واحد في كل سطر. إنها أبسط طريقة للحصول على n أسطر نصية بالضبط. ↩︎

  4. سيقدم الفصل 9 نوعًا آخر من المكرِّرات (iterators) يمكنه حل هذه المشكلة. ↩︎

  5. هنا، نستخدم نظام التسمية الفرنسي للرموز الموسيقية، المُستخدَم في العديد من البلدان الأخرى أيضًا. ↩︎

السابق بيئة العمل التالي مفاهيم OCaml