مفاهيم OCaml

3. مفاهيم OCaml: نظرة عن قرب

ما الذي تفعله إذا كان برنامجك سيئ الأنواع (ill-typed) أو يستهلك موارد كثيرة جدًّا (ذاكرةً أو وقتًا)؟ لتشخيص المشكلة تشخيصًا صحيحًا، لا بد من فهم كيفية عمل المترجم (compiler) والشيفرة التي ينتجها.

نتناول في هذا الفصل مسائل تتعلق بالتحقق من الأنواع (type-checking)، واستخدام الذاكرة، ووقت التنفيذ.

3.1 خوارزمية التحقق من الأنواع (type-checking)

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

لحساب نوع تعبير ما، يكفي أن نجتاز تعريفه من اليسار إلى اليمين، بدءًا من النوع الأكثر عمومية ممكن، ’a، مع تجميع قيود الأنواع.

لنتأمل، على سبيل المثال، تعريف الدالة التالي:

  let f x y = if x y then [] else [y + 1]

نبدأ بإعادة كتابة هذا التعريف على النحو التالي:

  let f = fun x -> fun y -> if x y then [] else [y + 1]

بعد ذلك، لنفترض:

  val f : ’a

بما أن f تعبير من الشكل funx->e1، نستنتج أن ’a يجب أن يكون نوع دالة، هو ’a1->’a2:

  val f : ’a1 -> ’a2

وبالمثل، فإن e1 دالة من الشكل funy->e2، ومن ثمَّ فإن ’a2 يساوي نوعًا من الشكل ’b1->’b2:

  val f : ’a1 -> ’b1 -> ’b2

نستخرج الآن قيود الأنواع المفروضة على المتغيرات ’a1 و’b1 و’b2 والناشئة عن التعبير e2، الذي يساوي:

  if x y then [] else [y + 1]

من تطبيق الدالة xy، نستنتج أن x دالة. وبعبارة أخرى، فإن ’a1 يساوي نوعًا من الشكل ’c1->’c2. وعليه نحصل على:

  val f : (’c1 -> ’c2) -> ’b1 -> ’b2

بعد ذلك، بما أن y يُمرَّر وسيطًا إلى x، نستنتج أن المتغير ’c1 يساوي ’b1، بحيث يصبح نوع f:

  val f : (’b1 -> ’c2) -> ’b1 -> ’b2

علاوة على ذلك، بما أن xy يُستخدم شرطًا في بنية if، نستنتج أن ’c2 يساوي bool:

  val f : (’b1 -> bool) -> ’b1 -> ’b2

يُرجع الفرع الأول من if القائمة الفارغة []. وعليه، فإن ’b2 يساوي ’dlist:

  val f : (’b1 -> bool) -> ’b1 -> ’d list

أخيرًا، يوفّر الفرع الثاني [y+1] القيدين الأخيرين. من عملية الجمع y+1، نستنتج أن y من النوع int. وعليه فإن القائمة [y+1] من النوع intlist، والمتغير ’d يساوي int. ومن ثمَّ فإن النوع الكامل للدالة f هو:

  val f : (int -> bool) -> int -> int list

لندرس الآن حالة دالة سيئة الأنواع. تأخذ الدالة g أدناه وسيطين، هما x وy. وتكتشف خوارزمية استنتاج الأنواع (type inference) الخطأ التالي:

  # let g x y = if x y then [x] else [y] ;;
  Error: This expression has type ’a but an expression was expected
         of type ’a -> bool
         The type variable ’a occurs inside ’a -> bool

الخطوات الأولية في تحديد نوع g هي نفسها في حالة f. وهكذا، بعد فحص التعبير xy، نستنتج أن g له النوع التالي:

  val g : (’b1 -> bool) -> ’b1 -> ’b2

يُرجع الفرع الأول من if القائمة [x]. وعليه، يجب أن يساوي المتغير ’b2 النوع (’b1->bool)list. وبالمثل، يُرجع الفرع الثاني القائمة [y]. لذا يجب أن يكون ’b2 من النوع ’b1list. وعليه، لكي تكون g جيدة الأنواع، يجب أن يتساوى النوعان (’b1->bool)list و’b1list. وهذا يستلزم أن تكون لمعادلة الأنواع ’b1=’b1->bool حلٌّ، وهو أمر غير ممكن في OCaml (ما لم نُمكّن الخيار -rectypes في المترجم أو المفسّر). نفهم الآن رسالة الخطأ أعلاه: فهي تشير إلى أن المتغير y من النوع ’a، بينما يجب أن يكون من النوع ’a->bool، وهو أمر غير ممكن لأن المتغير ’a يظهر داخل النوع ’a->bool.

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

إذا-فإن-وإلا (If-then-else)

في الشرط ife1thene2elsee3، يجب أن يكون التعبير e1 من النوع bool، ويجب أن يكون التعبيران e2 وe3 من النوع نفسه، أيًّا كان. ونوع الشرط هو نوع e2 (ومن ثمَّ أيضًا نوع e3).

إذا-فإن (If-then)

التعبير الشرطي ife1thene2 (من دون فرع else) من النوع unit. ويجب أن يكون التعبير e1 من النوع bool وe2 من النوع unit.

حلقة while (While)

في الحلقة whilee1doe2done، يجب أن يكون التعبير e1 من النوع bool وe2 من النوع unit. وحلقة while من النوع unit.

حلقة for (For)

في الحلقة fori=e1toe2doe3done، يجب أن يكون التعبيران e1 وe2 من النوع int والتعبير e3 من النوع unit. وحلقة for من النوع unit.

التتابع (Sequence)

في التتابع e1;e2، يجب أن يكون التعبير e1 من النوع unit بينما قد يكون e2 من أي نوع. ونوع e2 هو الذي يحدد نوع التتابع. وإذا لم يكن e1 من النوع unit، يمكننا كتابة let_=e1ine2 أو ignoree1;e2.

التعريف (Declaration)

في التعريف المحلي letp=e1ine2، يجب أن يكون النمط p والتعبير e1 من النوع نفسه. وقد يكون التعبير e2 من أي نوع. وهذا أيضًا هو نوع التعريف. وفي التعريف العالمي letp=e، يجب أن يكون نوع p مطابقًا لنوع e.

الدالة (Function)

الدالة من الشكل functionp->e أو funp->e من النوع t1->t2، حيث t1 هو نوع النمط p وt2 هو نوع التعبير e.

التطبيق (Application)

يتطلب التطبيق e1e2 أن يكون e1 من النوع t1->t2 وأن يكون e2 من النوع t1. ونوع نتيجة التطبيق هو t2.

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

لنتأمل بنية المطابقة (pattern matching):

  match e with
   | p1 when b1 -> e1
   | ...
   | pk when bk -> ek

القيود المرتبطة هي أن جميع التعبيرات e1، …، ek يجب أن تكون من النوع نفسه، وأن جميع التعبيرات b1، …، bk يجب أن تكون من النوع bool. ويجب أن تكون جميع الأنماط p1، …، pk من النوع نفسه الذي عليه e. والنوع الكلي لهذه البنية هو نوع التعبيرات e1، …، ek.

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

لنتأمل كتلة try-with من الشكل:

  try
   e
  with
   | p1 -> e1
   | ...
   | pk -> ek

هنا، يجب أن تكون جميع التعبيرات e، e1، …، ek من النوع نفسه. ويجب أن تشير الأنماط p1، …، pk إلى استثناءات (من النوع المعرَّف مسبقًا exn). ونوع كتلة try-with هو نوع التعبير e.

3.2 نموذج وقت التشغيل (Runtime Model)

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

تمثيل القيم (Value Representation)

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

• إذا كان عددًا صحيحًا فرديًّا 2n + 1، فإننا نفسّره على أنه القيمة الصحيحة n؛
• وإذا كان عددًا صحيحًا زوجيًّا، فإننا نفسّره على أنه مؤشر (pointer).

باختصار، قيمة OCaml إما عدد صحيح وإما مؤشر. فإذا كانت عددًا صحيحًا، فيمكنها تمثيل قيمة من النوع int، أو حرف، أو قيمة منطقية، أو حتى باني ثابت (constant constructor) مثل [] أو None. لاحظ أن هذا يفسّر قصر النوع int على 31 بت (63 بت في آلة 64 بت)، كما ذُكر سابقًا. أما إذا كانت القيمة مؤشرًا، فإنه يشير إلى كتلة (block) مخصَّصة في الذاكرة. وتشغل الكتلة k + 1 كلمة ذاكرة، مع k ≥ 1.

وتؤدي الكلمة الأولى من الكتلة، المسماة الترويسة (header)، دورًا خاصًّا سنشرحه لاحقًا. وتحتوي الكلمات k التالية على قيم OCaml، ونقول إن k هو حجم الكتلة. وسنُمثّل كتلة بحجم 5 على النحو التالي:

وهكذا، يُمثَّل الزوج (1,2) بمؤشر إلى كتلة تحتوي على قيمتين، هما القيمتان الصحيحتان 3 و5 اللتان تمثّلان على التوالي العددين الصحيحين 1 و2:

وبشكل أعم، يُمثَّل الصفّ المكوَّن من n عنصرًا (n-tuple) بمؤشر إلى كتلة بحجم n. كما تُمثَّل المصفوفات والسجلات في الذاكرة بمؤشرات إلى كتل. وهكذا، فإن المصفوفة [|1;2|] والسجل {a=1; b=2} لهما بالضبط التمثيل نفسه في الذاكرة الذي للزوج (1,2). وقد شرحنا سابقًا أن المرجع ليس إلا حالة خاصة من السجلات، بحقل واحد هو contents (انظر المعلومات الإضافية في القسم 2.6 تتبّع منحنى). ونستنتج من ذلك أن القيمة ref1 تُمثَّل في الذاكرة على هيئة كتلة بحجم 1، أي:

وتعني صفة mutable للحقل contents أن القيمة الموجودة في هذه الكتلة، وهي هنا 3، يمكن تعديلها في مكانها. وينطبق الأمر نفسه على قيم المصفوفة.

لنتأمل الآن تمثيل الأنواع الملموسة. الفكرة بسيطة: تُمثَّل البواني الثابتة أعدادًا صحيحة، بينما تُمثَّل البواني الأخرى بـ(مؤشرات إلى) كتل. خذ على سبيل المثال النوع:

  type t = A | B of t * t | C | D of char

يُمثَّل البانيان الثابتان A وC بالعددين الصحيحين 1 و3 على التوالي. ويُمثَّل البانيان غير الثابتين B وD بمؤشرين إلى كتلتين بحجم 2 و1 على التوالي. وهكذا، تقابل القيمة B(A,B(D’a’,C)) ثلاث كتل، على النحو التالي:

هنا، تقابل القيمة 195 المقدار 2 × 97 + 1، حيث 97 هو رمز الحرف ’a’.

وللوصول الأسرع، يشير المؤشر إلى الكتلة إلى حقلها الأول بدلًا من ترويستها. وتحتوي هذه الأخيرة على وسم الباني (tag)، وهنا B أو D. وتُستخدم هذه المعلومة بخاصة عند المطابقة (pattern matching).

لنتأمل نوع القوائم كمثال ثانٍ: يُمثَّل الباني الثابت [] بالعدد الصحيح 1. ويُمثَّل الباني :: بـ(مؤشر إلى) كتلة بحجم 2. وعليه تُمثَّل القائمة 1::2::3::[] في الذاكرة على النحو التالي:

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

بشكل عام، تحتوي الترويسة على وسم الكتلة. وإلى جانب الحالات التي وضّحناها، يمكن للترويسة أيضًا أن تحدد عددًا عشريًّا (floating-point number)، أو مصفوفة أعداد عشرية، أو سلسلة نصية، أو كائنًا، أو دالة، وما إلى ذلك. لاحظ أن الوسم يوفّر قدرًا أقل بكثير من المعلومات من نوع القيمة. وبشكل عام، لا يتضمن تمثيل الذاكرة لقيم OCaml معلومات الأنواع. وتوفّر المكتبة القياسية في OCaml وحدة Obj يمكن استخدامها لاستكشاف هذا التمثيل. وهكذا يمكننا اختبار ما إذا كانت قيمة ممثَّلة ككتلة، وإن كان الأمر كذلك نستعيد وسمها وحجمها وحقولها، وما إلى ذلك. ويجب استخدام هذه الوحدة بحذر نظرًا لطبيعتها غير المصنَّفة الأنواع بشدة.

الترميز (Notation)

في ما يلي، سنبسّط التمثيل البياني لقيم OCaml: لن تُرسم الترويسات، ولن تُحوَّل القيم الصحيحة باستخدام n↦2n + 1. وهكذا، ستُمثَّل القائمة [1;2;3] ببساطة على النحو التالي:

معامِلات المقارنة (Comparison Operators)

يمكن تطبيق معامِل التساوي = الذي استخدمناه سابقًا عدة مرات على أي قيمتين، بشرط أن تكونا من النوع نفسه. وهكذا، يمكننا استخدامه لمقارنة قيم من النوع التالي:

  # type ty = D | A of int | B of bool | C;;
  type ty = D | A of int | B of bool | C
  # A 1 = A 1 ;;
  - : bool = true
  # D = B true ;;
  - : bool = false

يقارن هذا المعامِل بين بنيتَي قيمتين، ولذلك فهو يقابل المفهوم الرياضي المعتاد للمساواة. ويُسمّى معامِل التساوي البنيوي (structural equality). وتُكتب نقيضه على الصورة <>.

كما توفّر OCaml معامِل تساوٍ آخر هو ==. ويُسمّى معامِل التساوي الفيزيائي (physical equality). وتُكتب نقيضه على الصورة !=. ويقارن المعامِل == بين القيم كأعداد صحيحة، حتى لو كانت هذه الأعداد تمثّل عناوين ذاكرة. وبناءً على ذلك، يمكننا أن نلاحظ أن تطبيقَي بانيين يخصّصان كتلتي ذاكرة مختلفتين:

  # A 1 == A 1 ;;
  - : bool = false

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

وينتهي معامِل التساوي الفيزيائي دائمًا في زمن ثابت، بينما قد يستغرق التساوي البنيوي زمنًا اعتباطيًّا، بل قد يدخل في حلقة لا نهائية على بيانات دائرية. ولنوضّح هذه النقطة بمثال. ننشئ قائمة دائرية l باستخدام ميزة في OCaml تتيح لنا تعريف قيمة باستخدام let-rec:

  # let rec l = 1 :: l ;;
  l : int list = [1; 1; 1; ... ]

ينتهي تقييم l==l بينما لا ينتهي تقييم l=l.

  # l == l ;;
  - : bool = true
  # l = l ;;

توفّر OCaml معامِلات مقارنة بنيوية أخرى: من جهة، ``, = من النوع ’a->’a->bool؛ ومن جهة أخرى، علاقة ترتيب Stdlib.compare من النوع ’a->’a->int، متوافقة مع المعامِلات السابقة.

  # C < A 1 ;;
  - : bool = true
  # A 1 < B true ;;
  - : bool = true
  # Stdlib.compare (A 1) (B true);;
  - : int = -1

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

على سبيل المثال، يمكننا استخدام Stdlib.compare لبناء بُنى معقّدة تتطلب علاقة ترتيب، مثل المجموعات (sets):

  # module S = Set.Make(
       struct type t = ty
              let compare = Stdlib.compare
       end);;

هنا، ليس تعريف Stdlib.compare مهمًّا ما دام علاقة ترتيب. ومع ذلك، إذا دعت الحاجة إلى مفهوم مقارنة محدَّد، توجّب تعريفه.

دوال عامة أخرى (Other Generic Functions)

توفّر OCaml دوال عامة أخرى، مثل:

• دالة تجزئة (hash function) هي Hashtbl.hash من النوع ’a -> int؛
• دوال التسلسل (marshalling functions)، المذكورة سابقًا (انظر المعلومات الإضافية في القسم 2.7 نسخ ملف).

الإدارة التلقائية للذاكرة (Automatic Memory Management)

كما في لغات أخرى، مثل Lisp وJava، فإن إدارة الذاكرة في OCaml آلية. وهذا يعني أن المبرمج يحدّد عمليات التخصيص صراحةً (ببناء مصفوفة أو سجل، أو تطبيق باني، وما إلى ذلك) لكنه لا يحدّد عمليات التحرير. ويُنفَّذ التحرير تلقائيًّا بواسطة جامع المهملات (garbage collector, GC). يرتبط عمل جامع المهملات (GC) ارتباطًا وثيقًا بتمثيل قيم OCaml. فمن جهة، يستطيع جامع المهملات التمييز بين المؤشرات والقيم الأخرى بفحص زوجية القيمة. ومن جهة أخرى، في حالة كتلة، تحتوي الترويسة على المعلومات التي يحتاجها جامع المهملات: الوسم (كما شُرح أعلاه)، وحجم الكتلة، وبضع بتات لتمييز الكتلة بأنها قيد الاستخدام. وهكذا، في معمارية 32 بت، تكون الترويسة على الشكل التالي:

بما أن حجم الكتلة مُرمَّز في 22 بت، فإنه محدود نسبيًّا (حتى 222 − 1، أي 4194303). وهذا، على سبيل المثال، هو الحجم الأقصى لمصفوفات OCaml. ويمكن الحصول عليه باستخدام Sys.max_array_length. أما الحجم الأقصى للسلاسل النصية فهو أكبر بأربعة أضعاف، لأن للسلاسل النصية تمثيلًا أكثر إحكامًا من المصفوفات. وهكذا، Sys.max_string_length = 224 − 5 = 16777211. أما في آلة 64 بت، فهذه الحدود تتجاوز بكثير ما يمكن تخصيصه في الذاكرة (على التوالي 254 − 1 و257 − 9).

تمثيل الدوال (Representation of Functions)

كلما أمكن استخدام دالة كقيمة من الرتبة الأولى (first-class value) (انظر القسم 2.6 تتبّع منحنى)، فإنها تُمثَّل بمؤشر إلى كتلة. ونتحدث حينئذ عن إغلاق (closure). ويحتوي الإغلاق على شيئين:

• مؤشر إلى الشيفرة المراد تنفيذها؛
• قيم المتغيرات التي قد تستخدمها هذه الشيفرة، وتُسمّى البيئة (environment).

وبالتالي يتكوّن إنشاء الإغلاق من تخصيص كتلة يتحدَّد حجمها بحجم البيئة، أي بعدد المتغيرات الحرة في جسم الدالة. وبالمقابل، يتكوّن تطبيق إغلاق f على قيمة v من استدعاء الدالة التي يشير إليها مؤشر الشيفرة في f وتمرير وسيطين إلى الدالة، هما البيئة (على هيئة الإغلاق f نفسه) والقيمة v. لنتأمل المثال التالي:

  let diff_quotient dx f x = (f (x +. dx) -. f x) /. dx
  let derivative = diff_quotient 1e-10
  let my_cos = derivative sin

القيمة derivative دالة ناتجة عن التطبيق الجزئي للدالة diff_quotient. وتُمثَّل بإغلاق يوافق مؤشر شيفرته funf->funx->...، وتحتوي بيئته على قيمة dx، وهي 1e-10. وبالمثل، فإن قيمة my_cos إغلاق يوافق مؤشر شيفرته funx->...، وتحتوي بيئته على قيمتي dx (وهي 1e-10) وf (وهي sin). والقيمة sin مثال آخر على إغلاق بيئته فارغة.

3.3 تحليل زمن تنفيذ برنامج (Analyzing the Execution Time of a Program)

مما سبق، يمكننا أن نستنتج عددًا من الحقائق المتعلقة بالتعقيد الزمني لعمليات OCaml:

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

في ما يلي، نقدّم عدة أدوات عملية ونظرية لقياس زمن تنفيذ برنامج وتحليله.

قياس زمن التنفيذ (Measuring Execution Time)

من السهل قياس الزمن الكلي لتنفيذ برنامج باستخدام ساعة توقيت، أو أفضل من ذلك، باستخدام أداة توفّرها نظم التشغيل. ويمكن قياس زمن تنفيذ جزء من برنامج OCaml بالسهولة نفسها، وبدقة كبيرة، باستخدام الدالة Unix.times من الوحدة Unix. تُرجع هذه الدالة سجلًا يحتوي حقله tms_utime على الزمن المنقضي منذ بدء البرنامج. وهو عدد عشري (floating-point number)، معبَّر عنه بالثواني، بدقة تفوق الميلي ثانية. وبحساب الفرق بين القيمتين اللتين تُرجعهما هذه الدالة عند نقطتين مختلفتين من البرنامج، نستنتج الزمن الدقيق لتنفيذ ذلك الجزء من الشيفرة. وعادةً نكتب شيئًا من قبيل:

  let start = (times ()).tms_utime in
  ...
  let stop = (times ()).tms_utime in

يمكننا بعد ذلك حساب الزمن المنقضي باستخدام stop-.start. ويركّز التمرينان 3.3 و3.4 على كتابة شيفرة عامة لمثل هذه القياسات.

مفاهيم غير صورية للتعقيد (Informal Notions of Complexity)

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

يُعرَّف تعقيد برنامج، أو بشكل أعم تعقيد خوارزمية، بأنه عدد العمليات الأولية التي يجب أن ينفّذها بدلالة حجم بيانات الإدخال. وفي المثال أعلاه، يمكن التعبير عن التعقيد بدالة f للعدد n من المدخلات: f(n) هو عدد العمليات الأولية المنفَّذة لفرز n من المدخلات.

الشكل 3.1: زمن تنفيذ f(n) عملية، بافتراض مليار عملية في الثانية. لاحظ أن «–» تشير إلى أن الزمن أقل من ثانية واحدة، وأن «∞» تشير إلى أنه أكبر من سنة.

ونعني بالعمليات الأولية العمليات الذرية بالنسبة إلى الآلة، مثل الجمع. وبافتراض أن آلة هذه الأيام تنفّذ مليار عملية في الثانية، يعطي الشكل 3.1 زمن تنفيذ f(n) عملية لدوال مختلفة f.

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

تحليل التعقيد (Complexity Analysis)

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

  for i = 1 to n - 1 do
    for j = i downto 1 do
      ...

هنا، نفترض أن الشيفرة المحذوفة (المشار إليها بـ ...) لا تحتوي إلا على عدد منتهٍ من العمليات الأولية، ولتكن C. ويمكننا حينئذ أن نستنتج أن التعقيد الكلي يساوي بالضبط:

وهذا يؤكد ملاحظتنا التجريبية بأن مضاعفة n تؤدي إلى ضرب f(n) بنحو أربعة تقريبًا. وعمليًّا، قلّما يكون تحليل التعقيد بهذه البساطة. فبعض العمليات لا تُنفَّذ إلا في حالات معيّنة، اعتمادًا على فحوص يجريها البرنامج، وهذه بدورها تتوقف على المدخلات. ونكتفي عمومًا بحساب تعقيد أسوأ حالة (worst-case)، الذي يوفّر حدًّا أعلى للعدد الكلي للعمليات المنفَّذة. ويمكننا أيضًا حساب تعقيد المتوسط على مجموعة المدخلات الممكنة ذات الحجم n، في مقابل توزيع معيّن لهذه المدخلات.

ترميز O الكبير (Big O Notation)

عمليًّا، نستخدم ترميز O الكبير لتحديد حدّ لتعقيد برنامج. وللتعبير عن أن دالة f، معرَّفة على الأعداد الطبيعية، لا تنمو أسرع من دالة أخرى g معرَّفة أيضًا على الأعداد الطبيعية، نكتب:

وهذا يعني وجود ثابت C بحيث يكون f(n) ≤ Cg(n) من أجل قيم n كبيرة بما يكفي، أو، بصورة أكثر صورية:

إذا دلّت f(n) على تعقيد خوارزمية بدلالة وسيط n، قلنا إن «تعقيد الخوارزمية من الرتبة O(g(n))» إذا كان f(n) = O(g(n)). وفي مثال الفرز، يكون التعقيد من الرتبة O(n2).

الخوارزمية التي يكون تعقيدها من الرتبة O(1) تُنفَّذ في زمن ثابت، بصرف النظر عن حجم البيانات. وبناءً على ذلك فإنها تتضمن عددًا ثابتًا من العمليات الأولية، مثل جمعتين وضربة. وتوصف الخوارزمية بأنها: لوغاريتمية إذا كان تعقيدها من الرتبة O(log n)؛ وخطية إذا كان من الرتبة O(n)؛ وشبه خطية إذا كان من الرتبة O(nlog n)؛ وتربيعية إذا كان من الرتبة O(n2)؛ وبشكل أعم كثيرة الحدود إذا وُجد ثابت k بحيث يكون تعقيدها من الرتبة O(nk)؛ وأُسّية إذا كان من الرتبة O(2n).

بشكل عام، لا نسعى إلى إظهار الثابتين C وN المخفيين في الترميز O. وإنما يهمّنا فقط رتبة المقدار المقارِبة (asymptotic order of magnitude)، على سبيل المثال عند الحكم على ما إذا كانت خوارزمية أفضل من أخرى. وبطبيعة الحال، فمن أجل قيمة محدَّدة لـ n، قد تستغرق خوارزمية من الرتبة O(n2) وقتًا أقل من أخرى من الرتبة O(log n)، بحكم الثوابت الكامنة خلف رموز O.

التعقيد المُطفَّأ (Amortized Complexity)

غالبًا ما يستحق الأمر حساب التعقيد الكلي لتتابع من n عملية ثم القسمة على n، للحصول على الكلفة المتوسطة لكل عملية. وقد تكون هذه الكلفة المتوسطة أدنى من تعقيد أسوأ حالة. ونسمّي التعقيد المتوسط الناتج بهذه الطريقة التعقيد المُطفَّأ، في مقابل تعقيد أسوأ حالة. ونقدّم أمثلة على التعقيد المُطفَّأ في الفصلين 4 و6.

  let f1 x = let y = !x + 2 in y
  let f2 n = for i = 1 to n do i + 4 done
  let f3 m n = if n = m then 1 else 2
  let f4 l = match l with [] -> [] | y :: s -> [s]
  let f5 x y = let z = x + 1 in y || z > 10
  let f6 x = let z = ref x in z + 1
  let f7 x y = for i = x to 10 do y := x :: !y done; !y
  let f8 x y z = x y z

  let foo x = x.a := (snd x.b) + 1
  let bar x = x.c <- (fst x.b) :: x.c

  val foo : ’a t -> unit
  val bar : ’a t -> unit