داغوبا: قاعدة بيانات رسومية في الذاكرة

Dann يستمتع بالأشياء التي يبنيها، مثل لغات البرمجة، وقواعد البيانات، والأنظمة الموزّعة، ومجتمعات البشر الأذكياء الودودين، وقلاع الخيول المصغّرة مع ابنه الذي يبلغ سنتين.

مقدّمة

"حين نحاول أن ننتزع أي شيء بمفرده، نجد أن ألف خيطٍ خفيّ لا يمكن كسره تربطه بكل ما في الكون." —جون مور

"ما الذي ينطلق إلى أطراف العالم ليتجوّل في كل شيء إلا نفسه: الله، والشمس، وشكسبير، وبائع متجوّل؟ فحين يتجوّل في الواقع ذاته يصير هو ذلك الشيء." —جيمس جويْس

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

ثم جاءت ثورة الوصول العشوائي، وراحت البيانات ترعى بحرّية فوق سفوح التلال. وصار رعي البيانات مصدرَ قلقٍ جادّ: إن كنت تستطيع الوصول إلى أي قطعة بيانات في أي وقت، فكيف تعرف أيَّها تختار تاليًا؟ طُوّرت تقنيات لحصر البيانات في حظيرة عبر تشكيل روابط بين العناصر^[1]، ورصف مجموعات من الوحدات في تشكيلات من خلال تجمّعات روابطها. أمّا السؤال عن البيانات فكان يعني انتقاء خروف وسحب كل ما يتّصل به.

وفيما بعد، ابتعد المبرمجون عن هذا التقليد، ففرضوا مجموعةً من القواعد على كيفية تجميع البيانات^[2]. فبدلًا من وصل البيانات المتفرّقة ببعضها مباشرةً، كانوا يجمّعون بحسب المحتوى، فيفكّون البيانات إلى قطع بحجم لقمة، تُجمع في حظائر وتُوسَم ببطاقات أسماء. وكانت الأسئلة تُطرح تصريحيًّا، مما ينتج تراكم قطع من بيانات متفكّكة جزئيًّا (حالة يسمّيها أصحاب النظرية العلائقية «طبيعية») في مجموعةٍ هجينة تُعاد إلى المبرمج.

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

غيّرت الثورة الموزّعة كل شيء، مرّة أخرى. تحرّرت البيانات من القيود المكانية وانتشرت من آلة إلى أخرى. وحطّم حَمَلةُ نظريّة CAP الاحتكارَ العلائقي، فانفتح الباب أمام تقنيات رعي جديدة—بعضها يرجع إلى أقدم المحاولات لتدجين الوصول العشوائي. وسننظر في إحداها، وهو نمطٌ يُعرف بقاعدة البيانات الرسومية.

لقطة أولى

سنبني في هذا الفصل قاعدة بيانات رسومية (graph database)^[3]. وبينما نبنيها، سنستكشف مساحة المشكلة، ونولّد حلولًا متعددة لقراراتنا التصميمية، ونقارن تلك الحلول لنفهم المقايضات بينها، ثم نختار في النهاية الحلّ المناسب لنظامنا. ويُوضع أولويةٌ أعلى من المعتاد على اختصار الشيفرة، لكن هذه العملية، فيما عدا ذلك، ستعاكس العمليةَ التي استخدمها مهنيو البرمجة منذ الأزل. والغرض من هذا الفصل هو تعليم هذه العملية، وبناء قاعدة بيانات رسومية^[4].

سيسمح لنا استخدام قاعدة بيانات رسومية بحلّ بعض المسائل المثيرة بأناقة. فالرسوم البيانية بنية بياناتٍ طبيعية جدًا لاستكشاف الروابط بين الأشياء. والرسم البياني بهذا المعنى مجموعةُ رؤوس (vertices) ومجموعةُ حوافّ (edges)؛ بمعنى آخر، هو مجموعة نقاط موصولة بخطوط. وقاعدة البيانات؟ «قاعدة البيانات» مثل حصن للبيانات. تضع البيانات فيها وتستخرج البيانات منها.

فأيّ نوع من المسائل يمكننا حلّه بقاعدة بيانات رسومية؟ لنفترض أنك تستمتع بتتبّع شجرة الأنساب: الآباء، والأجداد، وأبناء العمومة من الدرجة الثانية مُبعدين مرة، وما شابه. وتودّ تطويرَ نظامٍ يتيح لك صياغةَ استعلاماتٍ (queries) طبيعيةً وأنيقة، مثل «مَن هم أبناء عمومة ثور من الدرجة الثانية مُبعدين مرة؟» أو «ما صلةُ فرييا بفالكيريات؟»

قد يكون مخططٌ معقول لهذه البنية هو وجود جدولٍ للكيانات وجدولٍ للعلاقات. وقد يبدو استعلامُ آباء ثور كما يلي:

SELECT e.* FROM entities as e, relationships as r
WHERE r.out = "Thor" AND r.type = "parent" AND r.in = e.id

لكن كيف نوسّع ذلك ليشمل الأجداد؟ سنحتاج إلى استعلامٍ فرعيّ (subquery)، أو إلى استخدام نوعٍ آخر من الامتدادات الخاصة بالمورّد في SQL. وحين نصل إلى أبناء العمومة من الدرجة الثانية مُبعدين مرة، سيكون أمامنا الكثير من SQL.

فما الذي نودّ كتابته؟ شيءٌ موجزٌ ومرنٌ معًا؛ شيءٌ يصوغ استعلامنا بصورة طبيعية ويمتد إلى استعلاماتٍ أخرى من نوعه. فـ second_cousins('Thor') موجز، لكنه لا يمنحنا أي مرونة. أمّا SQL أعلاه فهو مرن، لكنه يفتقر إلى الاختصار.

شيءٌ مثل Thor.parents.parents.parents.children.children.children يصيب توازنًا معقولًا إلى حدٍّ لا بأس به. فالأساسيات (primitives) تمنحنا مرونةَ طرح أسئلةَ كثيرةٍ متشابهة، لكن الاستعلام موجزٌ وطبيعي. وهذا التعبير بعينه يعطينا نتائجَ أكثر مما نريد، لأنه يضم أبناء العمومة من الدرجة الأولى والأشقاء، لكننا نستهدف الصورة الكلّية هنا.

ما أبسطُ شيءٍ يمكننا بناؤه ليمنحنا هذا النوع من الواجهة؟ يمكننا إنشاء قائمة رؤوس (vertices) وقائمة حوافّ (edges)، تمامًا كما في المخطط العلائقي، ثم بناء بعض دوال المساعِدة. وقد يبدو شيءٌ من هذا القبيل:

V = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 ]
E = [ [1,2], [1,3],  [2,4],  [2,5],  [3,6],  [3,7],  [4,8]
    , [4,9], [5,10], [5,11], [6,12], [6,13], [7,14], [7,15] ]

parents = function(vertices) {
  var accumulator = []
  for(var i=0; i < E.length; i++) {
    var edge = E[i]
    if(vertices.indexOf(edge[1]) !== -1)
      accumulator.push(edge[0])
  }
  return accumulator
}

جوهرُ الدالة أعلاه هو المرورُ على قائمة، وتقييمُ بعض الشيفرة لكل عنصر، وبناءُ مُراكِم (accumulator) للنتائج. غير أنها ليست واضحةً تمامًا كما يمكن أن تكون، لأن بنيةَ التكرار تُدخل بعض التعقيد غير الضروري.

كان أجمل لو توفّر بناءُ تكرارٍ أكثر تحديدًا مصمَّمٌ لهذا الغرض. وتبيّن أن دالة reduce تفعل ذلك بالضبط: فمعطى قائمةٍ ودالة، فإنها تقيّم الدالة لكل عنصرٍ من عناصر القائمة، مع تمرير المُراكِم عبر كل تمريرة تقييم.

وعند كتابتها بهذا النمط الوظيفي (functional) الأكثر، تصبح استعلاماتنا أقصرَ وأوضح:

parents  = (vertices) => E.reduce( (acc, [parent, child])
         => vertices.includes(child)  ? acc.concat(parent) : acc , [] )
children = (vertices) => E.reduce( (acc, [parent, child])
         => vertices.includes(parent) ? acc.concat(child)  : acc , [] )

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

هذه الدوال JavaScript صالحة، لكنها تستخدم بعض المزايا التي لم تنفّذها المتصفحات حتى لحظة كتابة هذا الكتاب. وهذه النسخة المترجَمة ستعمل اليوم:

parents  = function(x) { return E.reduce(
  function(acc, e) { return ~x.indexOf(e[1]) ? acc.concat(e[0]) : acc }, [] )}
children = function(x) { return E.reduce(
  function(acc, e) { return ~x.indexOf(e[0]) ? acc.concat(e[1]) : acc }, [] )}

الآن يمكننا أن نقول شيئًا كهذا:

    children(children(children(parents(parents(parents([8]))))))

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

نحن نتعامل مع الحوافّ بوصفها متغيّرًا عامًّا (global)، ما يعني أنه لا يمكن أن يكون لدينا سوى قاعدة بياناتٍ واحدة في كل مرة عند استخدام دوال المساعِدة هذه. وهذا محدودٌ نوعًا ما.

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

ينطبق الأمرُ نفسه على حوافّنا: فهي تحوي رأس «داخل» (in) ورأس «خارج» (out)^[5]، لكن دون وسيلةٍ أنيقة لدمج معلوماتٍ إضافية. وسنحتاج إلى ذلك للإجابة عن أسئلةٍ مثل «كم عدد الآباء البدلاء لدى لوكي؟» أو «كم عدد أبناء Odin قبل أن يُولد ثور؟»

لا تحتاج إلى أن تُغمض عينيك بقوةٍ كي تلاحظ أن شيفرةَ المنتقيين (selectors) لدينا متشابهةٌ جدًا، وهو ما يشير إلى أنه قد يوجد تجريد (abstraction) أعمق تنبع منه.

هل ترى مشكلاتٍ أخرى؟

ابنِ رسمًا بيانيًّا أفضل

لنحلّ بعض المشكلات التي اكتشفناها. فكون رؤوسنا وحوافّنا بنىً عامّةً يحدّنا إلى رسمٍ بيانيٍّ واحد في كل مرة، لكننا نودّ أن يكون لدينا أكثر من ذلك. ولحلّ هذا سنحتاج إلى بعض البنية. لنبدأ باسم فضاء (namespace).

Dagoba = {}                                     // the namespace

سنستخدم كائنًا (object) بوصفه اسم الفضاء. فالكائن في JavaScript هو في معظمه مجردُ مجموعة أزواج مفتاح/قيمة غير مرتّبة. ولا نملك في JavaScript سوى أربع بنى بياناتٍ أساسيةٍ للاختيار من بينها، لذا سنستخدم هذه كثيرًا. (السؤالُ الممتعُ الذي يمكن طرحُه على الناس في الحفلات هو: «ما هي بنى البيانات الأساسية الأربع في JavaScript؟»)

الآن نحتاج إلى بعض الرسوم البيانية. يمكننا بناؤها بنمط OOP كلاسيكيّ، لكن JavaScript تتيح لنا الوراثة النماذُجية (prototypal inheritance)، ما يعني أننا نستطيع أن نبني كائن prototype—سنسميه Dagoba.G—ثم أن ننشئ نسخًا منه باستخدام دالة مصنِع (factory function). ومن مزايا هذه المقاربة أننا يمكننا إعادةُ أنواعٍ مختلفةٍ من الكائنات من المصنع، بدلًا من ربط عملية الإنشاء بباني صنفٍ واحد. فنحصل بذلك على بعض المرونة الإضافية مجانًا.

Dagoba.G = {}                                   // the prototype

Dagoba.graph = function(V, E) {                 // the factory
  var graph = Object.create( Dagoba.G )

  graph.edges       = []                        // fresh copies so they're not shared
  graph.vertices    = []
  graph.vertexIndex = {}                        // a lookup optimization

  graph.autoid = 1                              // an auto-incrementing ID counter

  if(Array.isArray(V)) graph.addVertices(V)     // arrays only, because you wouldn't
  if(Array.isArray(E)) graph.addEdges(E)        //   call this with singular V and E

  return graph
}

سنقبل وسيطين اختياريَّين: قائمة رؤوس وقائمة حوافّ. وJavaScript متساهلةٌ نوعًا ما بشأن الوسائط، لذا فجميع الوسائط المسمّاة اختياريةٌ وتُعيَّن إلى undefined (غير معرَّف) إن لم تُقدَّم^[6]. وغالبًا ما سنكون قد يملكنا الرؤوس والحوافّ قبل بناء الرسم البياني وسنستخدم الوسيطَين V وE، لكن من الشائع أيضًا ألّا يكون لدينا هما وقت الإنشاء وأن نبني الرسم البياني برمجيًّا^[7].

ثم ننشئ كائنًا جديدًا يملك كلَّ نقاطِ قوة النموذج الأولي (prototype) ولا شيءَ من نقاط ضعفه. نبني مصفوفةً جديدةً تمامًا (إحدى بنى بيانات JavaScript الأساسية الأخرى) لحوافّنا، وأخرى للرؤوس، وكائنًا جديدًا اسمه vertexIndex وعدّادَ معرّفات—وسنتحدّث عن الأخيرين لاحقًا. (فكّر: لماذا لا يمكن أن نضع هذه في النموذج الأولي؟)

ثم نستدعي addVertices وaddEdges من داخل مصنعنا، فلنعرّفهما الآن.

Dagoba.G.addVertices = function(vs) { vs.forEach(this.addVertex.bind(this)) }
Dagoba.G.addEdges    = function(es) { es.forEach(this.addEdge  .bind(this)) }

حسنًا، كان هذا سهلًا أكثر مما ينبغي—فقد اكتفينا بأن سلّمنا العملَ إلى addVertex وaddEdge. وينبغي أن نعرّفهما أيضًا الآن.

Dagoba.G.addVertex = function(vertex) {         // accepts a vertex-like object
  if(!vertex._id)
    vertex._id = this.autoid++
  else if(this.findVertexById(vertex._id))
    return Dagoba.error('A vertex with that ID already exists')

  this.vertices.push(vertex)
  this.vertexIndex[vertex._id] = vertex         // a fancy index thing
  vertex._out = []; vertex._in = []             // placeholders for edge pointers
  return vertex._id
}

إذا لم يكن للرأس خاصيةُ _id أصلًا، فنمنحه واحدةً باستخدام معرّفنا التلقائي (autoid)^[8]. أمّا إذا كانت _id موجودةً أصلًا على رأسٍ في رسمنا البياني، فإننا نرفض الرأس الجديد. لحظة، متى يحدث ذلك؟ وما هو الرأس بالضبط؟

في نظامٍ كائنيّ التوجّهٍ تقليدي، يمكننا أن نتوقّع العثورَ على صنفٍ للرؤوس، تكون كلُّ الرؤوس نسخًا منه. لكننا سنتبع مقاربةً مختلفة، ونعتبر رأسًا أيَّ كائنٍ يحوي الخاصيات الثلاث _id و_in و_out. ولماذا ذلك؟ وفي النهاية، الأمرُ يعود إلى منح Dagoba التحكّمَ في البيانات التي تُشارَك مع التطبيق المضيف (host application).

فإذا أنشأنا نسخةً من Dagoba.Vertex داخل دالة addVertex، فلن تُشارَك بياناتُنا الداخلية مع التطبيق المضيف أبدًا. أمّا إذا قبلنا نسخةً من Dagoba.Vertex كوسيطٍ لدالة addVertex، فيمكن للتطبيق المضيف أن يحتفظ بمؤشّرٍ إلى كائن الرأس ذلك ويعدّله أثناء التشغيل، فيكسر ثوابتنا (invariants).

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

يسمح لنا التوصيفُ الهيكلي (duck typing) على خصائص الرأس بأن نتّخذ هذا القرار وقت التشغيل، إما بالنسخ العميق (deep copying)^[9] للبيانات الواردة أو باستخدامها مباشرةً كـرأس^[10]. ولا نودّ دائمًا وضعَ مسؤولية الموازنة بين الأمان والأداء بيد المستخدم، لكن بما أن مجموعتَي حالات الاستخدام تتباعدان إلى هذا الحدّ، فإن تلك المرونة الإضافية مهمّة.

والآن وقد حصلتَ على رأسنا الجديد، سنضيفه إلى قائمة الرؤوس في رسمنا البياني، ونضيفه إلى vertexIndex ليُبحث عنه بكفاءة بحسب _id، ونضيف إليه خاصيتين إضافيتين: _out و_in، وسيصير كلٌّ منهما قائمةَ حوافّ^[11].

Dagoba.G.addEdge = function(edge) {             // accepts an edge-like object
  edge._in  = this.findVertexById(edge._in)
  edge._out = this.findVertexById(edge._out)

  if(!(edge._in && edge._out))
    return Dagoba.error("That edge's " + (edge._in ? 'out' : 'in')
                                       + " vertex wasn't found")

  edge._out._out.push(edge)                     // edge's out vertex's out edges
  edge._in._in.push(edge)                       // vice versa

  this.edges.push(edge)
}

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

Dagoba.error = function(msg) {
  console.log(msg)
  return false
}

ثم نضيف حافتنا الجديدة إلى قائمتَي حوافّ الرأسين: قائمة الحوافّ الخارجة لِرأس الحافة الخارج، وقائمة الحوافّ الداخلة للرأس الداخل.

وهذه كل بنية الرسم البياني التي نحتاج إليها الآن!

إلى الاستعلام

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

سنبدأ كما في السابق تمامًا، بنموذجٍ أولي ومصنع استعلام.

Dagoba.Q = {}

Dagoba.query = function(graph) {                // factory
  var query = Object.create( Dagoba.Q )

  query.   graph = graph                        // the graph itself
  query.   state = []                           // state for each step
  query. program = []                           // list of steps to take
  query.gremlins = []                           // gremlins for each step

  return query
}

والآن حان الوقت للتعرّف على بعض الأصدقاء.

البرنامج (program) سلسلةٌ من الخطوات (steps). كل خطوة تشبه أنبوبًا في خط أنابيب—تدخل قطعةُ بياناتٍ من أحد طرفيه، فتُحوَّل بطريقةٍ ما، وتخرج من الطرف الآخر. وخطُّ أنابيبنا لا يعمل تمامًا بهذه الطريقة، لكنه تقديرٌ أوّليٌّ جيّد.

يمكن لكل خطوة في برنامجنا أن تكون لها حالة (state)، وquery.state قائمةُ حالاتٍ لكل خطوة، يتوافق فهرسُها مع قائمة الخطوات في query.program.

الشرشور (gremlin) مخلوقٌ يسافر عبر الرسم البياني منفّذًا أوامرنا. قد يكون وجودُ الشرشور في قاعدة بياناتٍ أمرًا مفاجئًا، لكنّ نسبه ترجع إلى Blueprints لـTinkerpop، وإلى لغتَي استعلام Gremlin وPacer. فهو يتذكّر أين كان، ويتيح لنا إيجاد إجاباتٍ لأسئلةٍ مثيرة.

أتذكر ذلك السؤال الذي أردنا الإجابة عنه بشأن أبناء عمومة ثور مُبعدين مرة؟ وقد قرّرنا أن Thor.parents.parents.parents.children.children.children طريقةٌ جيّدة إلى حدٍّ لا بأس بها للتعبير عن ذلك. وكلُّ نسخة parents أو children هي خطوةٌ في برنامجنا. وتحتوي كلٌّ من تلك الخطوات على مرجعٍ إلى نوع الأنبوب (pipetype) الخاص بها، وهو الدالة التي تؤدّي عملية تلك الخطوة.

قد يبدو ذلك الاستعلام في نظامنا الفعلي هكذا:

    g.v('Thor').out().out().out().in().in().in()

كل خطوة من هذه الخطوات هي استدعاءُ دالة، لذا يمكنها أن تأخذ وسائط. ويمرّر المفسِّر وسائط الخطوة إلى دالة نوع الأنبوب الخاص بها، ففي الاستعلام g.v('Thor').out(2, 3) تتلقّى دالة نوع الأنبوب out القيمة [2, 3] بوصفها وسيطها الأول.

سنحتاج إلى طريقةٍ لإضافة خطواتٍ إلى استعلامنا. وهذه دالةٌ مساعدةٌ لذلك:

Dagoba.Q.add = function(pipetype, args) { // add a new step to the query
  var step = [pipetype, args]
  this.program.push(step)                 // step is a pair of pipetype and its args
  return this
}

كل خطوة كيانٌ مركَّب، يجمع بين دالة نوع الأنبوب والوسائط التي تُطبَّق على تلك الدالة. يمكننا أن نجمع الاثنين معًا في دالةٍ مطبَّقة جزئيًّا (partially applied function) في هذه المرحلة بدلًا من استخدام ثنائيّ (tuple)^[12]، لكننا عندئذٍ نفقد بعض القدرة على التأمّل في باطن (introspection) التي سيثبت لاحقًا أنها مفيدة.

سنستخدم مجموعةً صغيرة من مُهيّئات الاستعلام (query initializers) تولّد استعلامًا جديدًا من رسمٍ بياني. وهذه واحدةٌ تبدأ معظمَ أمثلتنا: الدالة v. فهي تبني استعلامًا جديدًا، ثم تستخدم دالتنا المساعدة add لملء برنامج الاستعلام الأوّلي. وهي تستعين بنوع الأنبوب vertex، الذي سننظر إليه قريبًا.

Dagoba.G.v = function() {                       // query initializer: g.v() -> query
  var query = Dagoba.query(this)
  query.add('vertex', [].slice.call(arguments)) // add a step to our program
  return query
}

لاحظ أن [].slice.call(arguments) تعني بلغة JavaScript «أعطني من فضلك مصفوفةً من وسائط هذه الدالة». ولأن arguments يتصرّف كمصفوفة في كثيرٍ من الحالات، فإن الاعتقاد بأنه مصفوفةٌ أصلًا ليس ظلمًا، لكنه يفتقد كثيرًا من الوظائف التي نستفيد منها في مصفوفات JavaScript الحديثة.

مشكلة الاستعجال

قبل أن ننظر إلى أنواع الأنابيب ذاتها، سنأخذ منعطفًا إلى عالم استراتيجيات التنفيذ المثير. وهناك مذهبان رئيسيان في التفكير: جماعة «الاستدعاء بالقيمة» (Call By Value)، وتُعرف أيضًا باسم «المتسرّعين» (eager beavers)، تشترد في إلزام تقييم كل الوسائط قبل تطبيق الدالة. أمّا الفصيل المقابل، جماعة «الاستدعاء بالحاجة» (Call By Need)، فتصفّح إلى التأجيل حتى آخر لحظةٍ ممكنة قبل أن تفعل أي شيء—بعبارةٍ واحدة، هم كسولون (lazy).

وبما أن JavaScript لغةٌ صارمة، فإنها ستعالج كل خطوة من خطواتنا لحظة استدعائها. وعندئذٍ نتوقّع أن يبدأ تقييم g.v('Thor').out().in() بإيجاد رأس ثور، ثم بإيجاد كل الرؤوس المتّصلة به عبر الحوافّ الخارجة، وأخيرًا أن يُعيد من كلٍّ من تلك الرؤوس كلَّ الرؤوس المتّصلة بها عبر الحوافّ الداخلة.

في لغةٍ غير صارمة سنحصل على النتيجة نفسها—فاستراتيجية التنفيذ لا تصنع فرقًا كبيرًا هنا. لكن ماذا لو أضفنا بضع استدعاءاتٍ إضافية؟ وبالنظر إلى مدى ترابط ثور، فإن استعلامنا g.v('Thor').out().out().out().in().in().in() قد ينتج نتائجَ كثيرة—بل قد ينتج، لأننا لا نحدّ قائمةَ رؤوسنا بالنتائج الفريدة، نتائجَ أكثر بكثير مما لدينا من رؤوسٍ في رسمنا البياني الكلّي.

ربما لا يهمّنا سوى الحصول على بضع نتائجَ فريدة، لذا سنغيّر الاستعلام قليلًا: g.v('Thor').out().out().out().in().in().in().unique().take(10). صار استعلامنا ينتج 10 نتائجٍ على الأكثر. لكن ماذا يحدث إن قيّمناه باستعجال؟ سنظلّ مضطرين إلى تراكم أسّ من النتائج قبل إعادة العشرة الأولى فقط.

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

آثارُ استراتيجية التنفيذ في نموذجنا الذهني

حتى الآن كان نموذجنا الذهني للتقييم بسيطًا إلى حدٍّ كبير:

• طلب مجموعة رؤوس
• تمرير المجموعة المُعادة كإدخالٍ إلى أنبوب
• التكرار بقدر الحاجة

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

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

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

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

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

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

• يعيد كل أنبوب نتيجةً واحدةً في كل مرة، لا مجموعة نتائج. وقد يُفعَّل كل أنبوب مرّاتٍ عديدة أثناء تقييم استعلام.
• تتحكّم رأسٌ للقراءة/الكتابة (read/write head) في تحديد الأنبوب الذي يُفعَّل تاليًا. وتبدأ الرأسُ في نهاية خط الأنابيب، ويتوجّه حركتُها بحسب نتيجة الأنبوب النشط حاليًا.
• قد تكون تلك النتيجة أحد الشراشير التي ذكرناها آنفًا. ويمثّل كل شرشور نتيجةَ استعلامٍ محتملة، ويحمل معه حالةً أثناء مروره في الأنابيب. وتُجبر الشراشيرُ الرأسَ على التحرّك إلى اليمين.
• يمكن للأنبوب أن يُعيد نتيجةً قيمتها 'pull'، وهي إشارةٌ إلى الرأس بأنه يحتاج إلى إدخال، وتحرّكه إلى اليمين.
• النتيجةُ ذات القيمة 'done' تُخبر الرأسَ بأن لا شيءَ سابقًا يحتاج إلى إعادة التفعيل، وتحرّك الرأسَ إلى اليسار.

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

تشكّل أنواعُ الأنابيب جوهرَ نظامنا. ومتى فهمنا كيف يعمل كل نوع منها، تتوفّر لنا أساسٌ أفضل لفهم كيفية استدعائها وترتيبها معًا في المفسِّر.

سنبدأ بصنع موضعٍ لوضع أنواع أنابيبنا، وطريقةٍ لإضافة أنواعٍ جديدة.

Dagoba.Pipetypes = {}

Dagoba.addPipetype = function(name, fun) {              // adds a chainable method
  Dagoba.Pipetypes[name] = fun
  Dagoba.Q[name] = function() {
    return this.add(name, [].slice.apply(arguments)) }  // capture pipetype and args
}

تُضاف دالةُ نوع الأنبوب إلى قائمة أنواع الأنابيب، ثم تُضاف دالةٌ جديدة إلى كائن الاستعلام. ولكل نوع أنبوب دالةُ استعلامٍ مقابلة. وتضيف تلك الدالة خطوةً جديدة إلى برنامج الاستعلام، مع وسائطها.

حين نقيّم g.v('Thor').out('parent').in('parent') يُعيد الاستدعاءُ v كائنَ استعلام، ويضيف الاستدعاءُ out خطوةً جديدة ويُعيد كائن الاستعلام، ويفعل الاستدعاءُ in الشيء نفسه. وهذا ما يُمكّن واجهةَ تسلسلِ الدوال (method-chaining API) لدينا.

لاحظ أن إضافة نوع أنبوبٍ جديد بالاسم نفسه تستبدل الموجود، مما يسمح بتعديل أنواع الأنابيب القائمة وقت التشغيل. فما ثمن هذا القرار؟ وما البدائل؟

Dagoba.getPipetype = function(name) {
  var pipetype = Dagoba.Pipetypes[name]                 // a pipetype is a function

  if(!pipetype)
    Dagoba.error('Unrecognized pipetype: ' + name)

  return pipetype || Dagoba.fauxPipetype
}

إن لم نتمكن من إيجاد نوع أنبوب، فنولّد خطأً ونُعيد نوع الأنبوب الافتراضي، الذي يتصرّف كقناةٍ فارغة: فإن جاءت رسالةٌ من أحد الطرفين، تُمرَّر من الطرف الآخر.

Dagoba.fauxPipetype = function(_, _, maybe_gremlin) {   // pass the result upstream
  return maybe_gremlin || 'pull'                        // or send a pull downstream
}

أترى تلك الشرطات السفلية؟ نستخدمها لتسمية الوسائط التي لن تُستخدم في دالتنا. وسأغلبُ أنواع الأنابيب الأخرى ستستخدم الوسائطَ الثلاثةَ كلها، وتحمل أسماءَ الوسائط الثلاثة كلها. وهذا يتيح لنا أن نميّز بنظرةٍ واحدة أيُّ الوسائط يعتمد عليها نوع أنابيبٍ بعينه.

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

الرأس

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

Dagoba.addPipetype('vertex', function(graph, args, gremlin, state) {
  if(!state.vertices)
    state.vertices = graph.findVertices(args)       // state initialization

  if(!state.vertices.length)                        // all done
    return 'done'

  var vertex = state.vertices.pop()                 // OPT: requires vertex cloning
  return Dagoba.makeGremlin(vertex, gremlin.state)  // gremlins from as/back queries
})

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

لاحظ أننا نطفرُ مباشرةً بوسيط الحالة هنا، ولا نُعيده. والبديلُ أن نُعيد كائنًا بدلًا من شرشور أو إشارة، ونُعيد الحالةَ تلكَ الطريقة. لكن ذلك يُعقّد قيمة إرجاعنا، وينتج بعضَ المهملات الإضافية^[13]. ولو سمحت JavaScript بقيم إرجاعٍ متعدّدةٍ لكان هذا الخيارُ أنيقًا.

لكننا مع ذلك سنحتاج إلى إيجاد طريقةٍ للتعامل مع الطفرات، لأن موضع الاستدعاء يحتفظ بمرجعٍ إلى المتغيّر الأصلي. وماذا لو أمكننا تحديد ما إذا كان مرجعٌ بعينه «فريدًا»—أي أنّه المرجع الوحيد إلى ذلك الكائن؟

إن علمنا أنّ مرجعًا فريد، أمكننا الاستفادةُ من مزايا الثبات (immutability) مع تجنّب مخطّطات النسخ عند الكتابة (copy-on-write) المكلفة أو بنى البيانات الدائمة المعقّدة. ومع وجود مرجعٍ واحدٍ فقط لا يمكننا تمييز ما إذا كان الكائنُ قد طُفر به أم أُعيد كائنٌ جديدٌ يحمل التغييرات التي طلبناها: أي إنّ «الثبات المرصود» (observed immutability) محفوظ^[14].

وهناك طريقتان شائعتان لتحديد ذلك: في نظامٍ مُنمَّط الأنواع إحصائيًّا (statically typed) يمكننا الاستفادةُ من أنماط التفرّد (uniqueness types)^[15] لضمان أن لكل كائنٍ مرجعًا واحدًا فقط وقت التصريف. ولو كان لدينا عدّادُ مراجع (reference counter)^[16]—ولو كان مجرّدًا عدّادًا لاصقًا رخيصًا من بتّين— لاستطعنا أن نعرف وقت التشغيل أنّ للكائن مرجعًا واحدًا فقط، ونستفيد من تلك المعرفة.

لا تمتلك JavaScript أيًّا من هاتين الأداتين، لكن يمكننا أن نحصل على الأثر نفسه تقريبًا إن كنّا منضبطين إلى حدٍّ كبير. وسنكون كذلك. الآن على الأقل.

الدخول-والخروج

المشيُ في الرسم البياني سهلٌ كطلب برغر. وهذان السطران يُعِدّان لنا نوعَي الأنابيب in وout.

Dagoba.addPipetype('out', Dagoba.simpleTraversal('out'))
Dagoba.addPipetype('in',  Dagoba.simpleTraversal('in'))

تُعيد دالةُ simpleTraversal معالِجَ نوع أنبوبٍ يقبل شرشورًا كإدخالٍ له، ويولّد شرشورًا جديدًا كلما سُئِل. وبعد نفاد تلك الشراشير، يُعيد طلبَ 'pull' للحصول على شرشورٍ جديد من سابقه.

Dagoba.simpleTraversal = function(dir) {
  var find_method = dir == 'out' ? 'findOutEdges' : 'findInEdges'
  var edge_list   = dir == 'out' ? '_in' : '_out'

  return function(graph, args, gremlin, state) {
    if(!gremlin && (!state.edges || !state.edges.length))     // query initialization
      return 'pull'

    if(!state.edges || !state.edges.length) {                 // state initialization
      state.gremlin = gremlin
      state.edges = graph[find_method](https://github.com/aosabook/500lines/blob/master/gremlin.vertex)        // get matching edges
                         .filter(Dagoba.filterEdges(args[0]))
    }

    if(!state.edges.length)                                   // nothing more to do
      return 'pull'

    var vertex = state.edges.pop()[edge_list]                 // use up an edge
    return Dagoba.gotoVertex(state.gremlin, vertex)
  }
}

يتولّى السطران الأولان الفروقَ بين نسخة الدخول ونسخة الخروج. ثم نكون مستعدين لإعادة دالة نوع الأنبوب، التي تبدو إلى حدٍّ ما أشبهَ بكثير بنوع أنبوب الرأس الذي رأيناه للتوّ. وهذا مثيرٌ بعض الشيء، لأن هذه تأخذ شرشورًا كإدخال، في حين يُنشئ نوعُ أنبوب الرأس شراشيرَ من العدم (ex nihilo).

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

بإلقاءٍ سريعٍ على هذه الشيفرة نرى !state.edges.length مكرَّرًا في كل بندٍ من البنود الثلاثة. ومن المغري إعادةُ هيكلة (refactor) هذا لتقليل تعقيد تلك الجمل الشرطية. لكن مشكلتينِ تمنعاننا من ذلك.

إحداهما ثانويّةٌ إلى حدٍّ ما: فالعبارةُ الثالثة !state.edges.length تعني شيئًا مختلفًا عن الأولى والثانية، لأن state.edges قد تغيّر بين الشرط الثاني والثالث. وهذا في الواقع يدفعنا إلى إعادة الهيكلة، لأن جعلَ التسمية نفسها تعني شيئين مختلفين داخل دالةٍ واحدة ليس مثاليًّا عادةً.

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

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

الخاصية

لنتوقّف لحظةً لنتأمّل استعلامًا نموذجيًّا مبنيًّا على أنواع الأنابيب الثلاثة التي رأيناها. يمكننا أن نطلب أجدادَ ثور هكذا^[17]:

g.v('Thor').out('parent').out('parent').run()

لكن ماذا لو أردنا أسماءَهم؟ يمكننا أن نضيف map إلى ذيل ذلك:

g.v('Thor').out('parent').out('parent').run()
 .map(function(vertex) {return vertex.name})

لكن هذه عمليةٌ شائعةٌ إلى حدٍّ كافٍ، لذا نفضّل كتابةَ شيءٍ أقرب إلى:

g.v('Thor').out('parent').out('parent').property('name').run()

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

Dagoba.addPipetype('property', function(graph, args, gremlin, state) {
  if(!gremlin) return 'pull'                                  // query initialization
  gremlin.result = gremlin.vertex[args[0]]
  return gremlin.result == null ? false : gremlin             // false for bad props
})

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

لاحظ أن إن لم تكن الخاصيةُ موجودة، فإننا نُعيد false بدلًا من الشرشور، لذا تعمل أنابيبُ الخاصية أيضًا كنوعٍ من المُرشِّحات (filter). هل يمكنك أن تتخيّل استخدامًا لذلك؟ وما المقايضاتُ في قرار التصميم هذا؟

التفرّد

إن أردنا جمعَ كل أحفاد أجداد ثور—أي أبناء عمومته وأشقّائه وهو نفسه—فيمكننا إجراءُ استعلامٍ كهذا: g.v('Thor').in().in().out().out().run(). لكن ذلك سيعطينا كثيرًا من التكرارات. بل سيكون هناك على الأقل أربعُ نسخٍ من ثور نفسه. (هل يمكنك أن تتخيّر حالةً قد يكون فيها ذلك أكثر؟)

ولحلّ ذلك نقدّم نوعَ أنبوبٍ جديد اسمه 'unique'. وينتج استعلامنا الجديد مُخرَجًا يطابق الأحفادَ واحدًا واحدًا:

    g.v('Thor').in().in().out().out().unique().run()

وتنفيذُ نوع الأنبوب:

Dagoba.addPipetype('unique', function(graph, args, gremlin, state) {
  if(!gremlin) return 'pull'                                  // query initialization
  if(state[gremlin.vertex._id]) return 'pull'                 // reject repeats
  state[gremlin.vertex._id] = true
  return gremlin
})

أنبوبُ التفرّد مُرشِّحٌ خالص: فهو إمّا يمرّر الشرشورَ دون تغيير، أو يحاول سحبَ شرشورٍ جديد من الأنبوب السابق.

نُهيّئ بأن نحاول جمعَ شرشور. فإن كان رأسُ الشرشور الحالي في ذاكرتنا المؤقتة (cache)، فقد رأيناه من قبل، فنحاول جمعَ واحدٍ جديد. وإلّا نضيف رأسَ الشرشور الحالي إلى ذاكرتنا المؤقتة ونمرّره. أيّها سهلٌ جدًّا.

الترشيح

رأينا طريقتين مبسّطتين للترشيح، لكننا نحتاج أحيانًا إلى قيودٍ أعقد. فماذا لو أردنا إيجادَ كل أشقاء ثور الذين وزنُهم أكبر من طولهم^[18]؟ سيعطينا هذا الاستعلامُ إجابتَنا:

g.v('Thor').out().in().unique()
 .filter(function(asgardian) { return asgardian.weight > asgardian.height })
 .run()

إن أردنا معرفة أيّ أشقاء ثور ينجون من راغناروك، يمكننا أن نمرّر إلى filter كائنًا:

g.v('Thor').out().in().unique().filter({survives: true}).run()

وهكذا يعمل:

Dagoba.addPipetype('filter', function(graph, args, gremlin, state) {
  if(!gremlin) return 'pull'                                  // query initialization

  if(typeof args[0] == 'object')                              // filter by object
    return Dagoba.objectFilter(gremlin.vertex, args[0])
         ? gremlin : 'pull'

  if(typeof args[0] != 'function') {
    Dagoba.error('Filter is not a function: ' + args[0])
    return gremlin                                            // keep things moving
  }

  if(!args[0](https://github.com/aosabook/500lines/blob/master/gremlin.vertex, gremlin)) return 'pull'         // gremlin fails filter
  return gremlin
})

إن لم يكن الوسيطُ الأول لـfilter كائنًا أو دالة، فإننا نُطلق خطأً ونمرّر الشرشور قادمًا. توقّف لحظةً، وتأمّل البدائل. لماذا نقرّر متابعةَ الاستعلام عند وقوع خطأ؟

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

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

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

الأخذ

لا نريد أحيانًا كلَّ النتائج دفعةً واحدة. فأحيانًا لا نحتاج إلّا إلى حفنةٍ من النتائج؛ فلنفترض أننا نريد اثنتي عشرة من معاصري ثور، فنمشي كلَّ الطريق عائدين إلى البقرة البدائية أوذومبلا:

g.v('Thor').out().out().out().out().in().in().in().in().unique().take(12).run()

من دون أنبوب take قد يستغرق ذلك الاستعلام وقتًا طويلًا لينفَّذ، لكن بفضل استراتيجية التقييم الكسول لدينا، فإن الاستعلامَ الذي فيه أنبوب take فعّالٌ جدًّا.

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

q = g.v('Auðumbla').in().in().in().property('name').take(1)

q.run() // ['Odin']
q.run() // ['Vili']
q.run() // ['Vé']
q.run() // []

يمكن أن يعمل استعلامُنا في بيئةٍ غير متزامنة (asynchronous)، مما يتيح لنا جمعَ نتائجَ أكثر عند الحاجة. وحين ننفد منها، تُعاد مصفوفةٌ فارغة.

Dagoba.addPipetype('take', function(graph, args, gremlin, state) {
  state.taken = state.taken || 0                              // state initialization

  if(state.taken == args[0]) {
    state.taken = 0
    return 'done'                                             // all done
  }

  if(!gremlin) return 'pull'                                  // query initialization
  state.taken++
  return gremlin
})

نُهيّئ state.taken إلى الصفر إن لم تكن موجودةً أصلًا. وJavaScript فيها الإكراهُ الضمني (implicit coercion)، لكنه يحوّل undefined إلى NaN، لذا علينا أن نكون صريحين هنا^[19].

وحين يصل state.taken إلى args[0] نُعيد 'done'، فنُغلق الأنابيبَ أمامنا. كما نعيد ضبط عدّاد state.taken، مما يتيح لنا تكرارَ الاستعلام لاحقًا.

ونقوم بهاتين الخطوتين قبل تهيئة الاستعلام للتعامل مع حالتَي take(0) وtake()^[20]. ثم نزيد عدّادَنا ونُعيد الشرشور.

التسمية

تعمل أنواعُ الأنابيب الأربعة التالية معًا كمجموعةٍ لتتيح استعلاماتٍ أكثر تقدّمًا. وهذا النوع يتيح لك فقط وسمَ الرأس الحالي. وسنستخدم ذلك الوسم مع نوعَي الأنابيب التاليين.

Dagoba.addPipetype('as', function(graph, args, gremlin, state) {
  if(!gremlin) return 'pull'                                  // query initialization
  gremlin.state.as = gremlin.state.as || {}                   // init the 'as' state
  gremlin.state.as[args[0]] = gremlin.vertex                  // set label to vertex
  return gremlin
})

بعد تهيئة الاستعلام، نتأكّد من أن للحالة المحلية للشرشور الوسيطَ as. ثم نضبط خاصيةً من ذلك الوسيط لتكون الرأسَ الحالي للشرشور.

الدمج

بعد أن نُسمّي الرؤوس، يمكننا استخراجُها بالدمج. فإذا أردنا آباءَ ثور وأجدادَه وأجدادَ أجداده، يمكننا أن نفعل شيئًا كهذا:

g.v('Thor').out().as('parent').out().as('grandparent').out().as('great-grandparent')
           .merge('parent', 'grandparent', 'great-grandparent').run()

وهذا هو نوع أنبوب الدمج:

Dagoba.addPipetype('merge', function(graph, args, gremlin, state) {
  if(!state.vertices && !gremlin) return 'pull'               // query initialization

  if(!state.vertices || !state.vertices.length) {             // state initialization
    var obj = (gremlin.state||{}).as || {}
    state.vertices = args.map(function(id) {return obj[id]}).filter(Boolean)
  }

  if(!state.vertices.length) return 'pull'                    // done with this batch

  var vertex = state.vertices.pop()
  return Dagoba.makeGremlin(vertex, gremlin.state)
})

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

الاستثناء

سبق أن رأينا حالاتٍ نودّ فيها أن نقول «أعطني كل أشقاء ثور ما عدا ثور». ويمكننا فعلُ ذلك بمُرشِّح:

g.v('Thor').out().in().unique()
           .filter(function(asgardian) {return asgardian._id != 'Thor'}).run()

أمّا مع as وexcept فالأمرُ أكثر وضوحًا:

g.v('Thor').as('me').out().in().except('me').unique().run()

لكن هناك أيضًا استعلاماتٌ يكون ترشيحُها عسيرًا. فماذا لو أردنا أعمامَ ثور وعمّاته؟ وكيف نُرشّح والديه؟ الأمرُ سهلٌ مع as وexcept^[21]:

g.v('Thor').out().as('parent').out().in().except('parent').unique().run()

Dagoba.addPipetype('except', function(graph, args, gremlin, state) {
  if(!gremlin) return 'pull'                                  // query initialization
  if(gremlin.vertex == gremlin.state.as[args[0]]) return 'pull'
  return gremlin
})

هنا نتحقّق ممّا إذا كان الرأسُ الحالي مساويًا للرأس الذي خزّناه سابقًا. فإن كان كذلك، نتخطّاه.

الرجوع

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

g.v('Fjörgynn').in().as('me')       // first gremlin's state.as is Frigg
 .in()                              // first gremlin's vertex is now Baldr
 .out().out()                       // clone that gremlin for each grandparent
 .filter({_id: 'Bestla'})           // keep only the gremlin on grandparent Bestla
 .back('me').unique().run()         // jump gremlin's vertex back to Frigg and exit

وهذا تعريف back:

Dagoba.addPipetype('back', function(graph, args, gremlin, state) {
  if(!gremlin) return 'pull'                                  // query initialization
  return Dagoba.gotoVertex(gremlin, gremlin.state.as[args[0]])
})

نستخدم الدالةَ المساعدة Dagoba.gotoVertex للقيام بالعمل الفعلي كلِّه هنا. فلننظر إليها هي ودوالًا مساعدةً أخرى الآن.

الدوال المساعدة

تعتمد أنواعُ الأنابيب أعلاه على بضع دوالَ مساعدةٍ لأداء عملها. فلنُلقِ نظرةً سريعةً عليها قبل أن نغوص في المفسِّر.

الشراشير

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

Dagoba.makeGremlin = function(vertex, state) {
  return {vertex: vertex, state: state || {} }
}

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

ويمكننا أيضًا أن نأخذ شرشورًا موجودًا ونرسله إلى رأسٍ جديد، كما رأينا في نوع أنبوب back ودالة simpleTraversal.

Dagoba.gotoVertex = function(gremlin, vertex) {               // clone the gremlin
  return Dagoba.makeGremlin(vertex, gremlin.state)
}

لاحظ أن هذه الدالة تُعيد في الواقع شرشورًا جديدًا تمامًا: استنساخًا للقديم أُرسل إلى الوجهة التي نريدها. وهذا يعني أن شرشورًا يمكن أن يجلس على رأسٍ بينما تُرسَل نسخُه إلى رؤوسَ أخرى كثيرةٍ لاستكشافها. وهذا هو بالضبط ما يحدث في simpleTraversal.

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

الإيجاد

يستخدم نوعُ الأنبوب vertex دالةَ findVertices لجمع مجموعةٍ من الرؤوس الأوّلية التي نبدأ منها استعلامَنا.

Dagoba.G.findVertices = function(args) {                      // vertex finder helper
  if(typeof args[0] == 'object')
    return this.searchVertices(args[0])
  else if(args.length == 0)
    return this.vertices.slice()                              // OPT: slice is costly
  else
    return this.findVerticesByIds(args)
}

تتلقّى هذه الدالة وسائطَها بوصفها قائمةً. فإن كان الأولُ منها كائنًا، فإنها تسلّمه إلى searchVertices، فتتيح استعلاماتٍ مثل:

  g.v({_id:'Thor'}).run()
  g.v({species: 'Aesir'}).run()

وإلّا، إن كانت هناك وسائط، فإنها تُسلَّم إلى findVerticesByIds، التي تتعامل مع استعلاماتٍ مثل g.v('Thor', 'Odin').run().

وإن لم تكن هناك وسائط البتّة، فإن استعلامَنا يبدو هكذا: g.v().run(). وهذا ليس شيئًا ستحبّ فعلَه كثيرًا مع رسومٍ بيانية كبيرة، وبخاصة لأننا ننسخ قائمةَ الرؤوس قبل إعادتها. وننسخها لأن بعض مواضع الاستدعاء تعدّل القائمةَ المُعادة مباشرةً بأن تُسقط عناصرَ منها أثناء العمل عليها. ويمكننا تحسين هذا الاستخدام بالاستنساخ في موضع الاستدعاء، أو بتجنّب تلك التعديلات. (يمكننا الاحتفاظ بعدّادٍ في الحالة بدلًا من الإسقاط.)

Dagoba.G.findVerticesByIds = function(ids) {
  if(ids.length == 1) {
    var maybe_vertex = this.findVertexById(ids[0])            // maybe it's a vertex
    return maybe_vertex ? [maybe_vertex] : []                 // or maybe it isn't
  }

  return ids.map( this.findVertexById.bind(this) ).filter(Boolean)
}

Dagoba.G.findVertexById = function(vertex_id) {
  return this.vertexIndex[vertex_id]
}

لاحظ استعمالَ vertexIndex هنا. فبدون ذلك الفهرس لانظرنا إلى كل رأسٍ في قائمتنا واحدًا تلو الآخر لنحكم بمطابقته للمعرّف—فنحوّل عمليةً ذات زمن ثابت (constant time) إلى عمليةٍ ذات زمن خطّي (linear time)، وأيَّ عمليات $O(n)$ تعتمد عليها مباشرةً إلى عمليات $O(n^2)$.

Dagoba.G.searchVertices = function(filter) {        // match on filter's properties
  return this.vertices.filter(function(vertex) {
    return Dagoba.objectFilter(vertex, filter)
  })
}

تستخدم دالةُ searchVertices الدالةَ المساعدة objectFilter على كل رأسٍ في الرسم البياني. وسننظر إلى objectFilter في القسم التالي، لكن في هذه الأثناء، هل يمكنك أن تتخيّر طريقةً للبحث في الرؤوس بحثًا كسولًا (lazy)؟

المُرشِّحات

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

Dagoba.filterEdges = function(filter) {
  return function(edge) {
    if(!filter)                                 // no filter: everything is valid
      return true

    if(typeof filter == 'string')               // string filter: label must match
      return edge._label == filter

    if(Array.isArray(filter))                   // array filter: must contain label
      return !!~filter.indexOf(edge._label)

    return Dagoba.objectFilter(edge, filter)    // object filter: check edge keys
  }
}

الحالةُ الأولى هي انعدام المُرشِّح أصلًا: g.v('Odin').in().run() تعبر كل الحوافّ المؤدّية إلى Odin.

والحالةُ الثانية ترشِّح بحسب وسم الحافة: g.v('Odin').in('parent').run() تعبر الحوافّ ذات الوسم 'parent'.

والحالةُ الثالثة تقبل مصفوفةً من الوسوم: g.v('Odin').in(['parent', 'spouse']).run() تعبر حوافَّ الوالدين والزوج.

والحالةُ الرابعة تستخدم دالةَ objectFilter التي رأيناها من قبل:

Dagoba.objectFilter = function(thing, filter) {
  for(var key in filter)
    if(thing[key] !== filter[key])
      return false

  return true
}

يتيح لنا هذا الاستعلامَ عن الحافة باستخدام كائن ترشيح:

`g.v('Odin').in({_label: 'spouse', order: 2}).run()`    // finds Odin's second wife

طبيعة المفسِّر

لقد بلغنا قمةَ جبل السرد، مستعدّين لاستلام جائزتنا: المفسِّر. والشيفرةُ في الواقع مضغوطةٌ نسبيًّا، لكن في النموذج شيءٌ من الدقّة.

قارنّا البرامجَ بخطوط الأنابيب في وقتٍ سابق، وهذا نموذجٌ ذهنيٌّ جيّد لكتابة الاستعلامات. لكن كما رأينا، نحتاج إلى نموذجٍ مختلفٍ للتنفيذ الفعلي. وهذا النموذج أقربُ إلى آلة تورينج (Turing machine) منه إلى خط أنابيب: فهناك رأسٌ للقراءة/الكتابة تجلس فوق خطوةٍ بعينها. فهي «تقرأ» الخطوة، وتغيّر «حالتها»، ثم تتحرّك يمينًا أو يسارًا.

قراءةُ الخطوة تعني تقييمَ دالة نوع الأنبوب. وكما رأينا أعلاه، تقبل كلُّ واحدةٍ من تلك الدوال كإدخالٍ الرسمَ البيانيَّ كاملًا، ووسائطَها الخاصة، وربما شرشورًا، وحالتها المحلية. وكإخراجٍ فهي تقدّم شرشورًا أو false أو إشارةَ 'pull' أو 'done'. وهذا المُخرَج هو ما تقرأه آلتُنا شبهُ الشبيهة بتورينج لتغيّر حالة الآلة.

تتألّف تلك الحالة من متغيّرَين فقط: أحدهما لتسجيل الخطوات التي صارت 'done'، والآخر لتسجيل results الاستعلام. ويتم تحديثُهما، ثم إمّا تتحرّك رأسُ الآلة وإمّا ينتهي الاستعلام وتُعاد النتيجة.

لقد وصفنا الآن كلَّ حالة في آلتنا. ولدينا قائمةُ نتائجٍ تبدأ فارغة:

  var results = []

وفهرسٌ لآخر خطوةٍ 'done' يبدأ خلف الخطوة الأولى:

  var done = -1

نحتاج إلى موضعٍ لتخزين مُخرَج آخر خطوة، وقد يكون شرشورًا—أو قد يكون لا شيء— لذا سنسميه maybe_gremlin:

  var maybe_gremlin = false

وأخيرًا سنحتاج إلى عدّادِ برامج (program counter) يدلّ على موضع رأس القراءة/الكتابة.

  var pc = this.program.length - 1

غير أنّ... لحظة. كيف سنحصل على الكسل^[22]؟ فالطريقة التقليدية لبناء نظامٍ كسولٍ من نظامٍ مستعجل هي تخزينُ وسائط استدعاءات الدوال بوصفها «ثنكوات» (thunks) بدلًا من تقييمها. ويمكنك أن تتخيّل الـ thunk تعبيرًا غير مقيَّم. وفي JavaScript، التي تملك دوالَّ من الطبقة الأولى (first-class functions) وإغلاقاتٍ (closures)، يمكننا إنشاء thunk بلفِّ دالةٍ ووسائطها داخل دالةٍ مجهولةٍ جديدة لا تأخذ أيّ وسائط:

function sum() {
  return [].slice.call(arguments).reduce(function(acc, n) { return acc + (n|0) }, 0)
}

function thunk_of_sum_1_2_3() { return sum(1, 2, 3) }

function thunker(fun, args) {
  return function() {return fun.apply(fun, args)}
}

function thunk_wrapper(fun) {
  return function() {
    return thunker.apply(null, [fun].concat([[].slice.call(arguments)]))
  }
}

sum(1, 2, 3)              // -> 6
thunk_of_sum_1_2_3()      // -> 6
thunker(sum, [1, 2, 3])() // -> 6

var sum2 = thunk_wrapper(sum)
var thunk = sum2(1, 2, 3)
thunk()                   // -> 6

لا يُستدعى أيُّ واحدٍ من هذه الثنكوات حتى تُحتاج إحداها فعلًا، وهو ما يعني عادةً أن نوعًا ما من المُخرَج مطلوب: في حالتنا نتيجةُ استعلام. وفي كل مرة يصطدم فيها المفسِّر باستدعاء دالةٍ جديد، نغلّفه في thunk. وتذكّر صياغتَنا الأوّلية للاستعلام: children(children(children(parents(parents(parents([8])))))). وسيكون كلُّ تلك الطبقات thunk، ملفوفًا كالبصلة.

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

عادةً ما لا تكون النقطةُ الثانية مشكلةً، بسبب الفصل بين المراحل (phase separation) بين ما تعمل فيه مُصرِّفُنا (compiler) تحسيناتَها، وما تجري فيه كل عمليات تغليف thunk وقت التشغيل. أمّا في حالتنا فلا نملك تلك الميزة: لأننا نستخدم تسلسلَ الدوال لتنفيذ واجهةٍ سلسة (fluent interface)^[23]، فإن استخدمنا أيضًا thunks لتحقيق الكسل لأغلفنا كل دالةٍ جديدة لحظة استدعائها، ما يعني أن حين نصل إلى run() لا يكون لدينا سوى thunkٍ كإدخال، ولا سبيل لدينا إلى تحسين استعلامنا.

ومن اللافت أن واجهتَنا السلسة تخفي فرقًا آخر بين لغة استعلاماتنا ولغات البرمجة الاعتيادية. فالاستعلام g.v('Thor').in().out().run() يمكن إعادةُ كتابته على Shape run(out(in(v(g, 'Thor')))) لو لم نستخدم تسلسل الدوال. وفي JavaScript كنا سنعالج g و'Thor' أولًا، ثم v، ثم in وout وrun، من الداخل إلى الخارج. أمّا في لغةٍ بدلالاتٍ غير صارمةٍ لكنا سنعمل من الخارج إلى الداخل، فنعالج كل طبقةٍ متتاليةٍ من الوسائط المتداخلة عند الحاجة فحسب.

فإن بدأنا تقييمَ استعلامنا في نهاية الجملة، عند run، وعدنا بالزحف إلى v('Thor')، أحسبنا النتائج عند الحاجة فحسب، فقد بلغنا بفعاليةٍ عدمَ الصرامة. والسرّ في خطّية استعلاماتنا. فالفروعُ تُعقّد رسمَ العملية، وتُدخل أيضًا فرصًا لاستدعاءاتٍ مكرّرة، ممّا يستلزم الحفظَ المؤقت (memoization) تفاديًا لعملٍ ضائع. وبساطةُ لغة استعلاماتنا تعني أننا نستطيع تنفيذ مفسِّرٍ بساطةٍ مماثلة قائمٍ على نموذجنا الخطّي للقراءة/الكتابة.

إلى جانب السماح بتحسيناتٍ وقت التشغيل، لهذا النمط مزايا كثيرةٌ أخرى تتعلق بسهولة التجهيز (instrumentation): السجلّ، وقابلية التراجع عن التنفيذ، والتنقيح خطوةً خطوة، وإحصاءات الاستعلامات. وكلُّ هذه سهلةُ الإضافة ديناميكيًّا لأننا نتحكّم في المفسِّر ونتركه مُقيِّمَ آلةٍ افتراضية (virtual machine) بدلًا من تصغير البرنامج إلى thunkٍ واحد.

المفسِّر، مكشوفًا

Dagoba.Q.run = function() {                 // a machine for query processing

  var max = this.program.length - 1         // index of the last step in the program
  var maybe_gremlin = false                 // a gremlin, a signal string, or false
  var results = []                          // results for this particular run
  var done = -1                             // behindwhich things have finished
  var pc = max                              // our program counter

  var step, state, pipetype

  while(done < max) {
    var ts = this.state
    step = this.program[pc]                 // step is a pair of pipetype and args
    state = (ts[pc] = ts[pc] || {})         // this step's state must be an object
    pipetype = Dagoba.getPipetype(step[0])  // a pipetype is just a function

هنا max مجردُ ثابت، بينما step وstate وpipetype تخزّن مؤقتًا معلوماتٍ عن الخطوة الحالية. وقد دخلنا حلقةَ التشغيل (driver loop)، ولن نتوقّف حتى تُنجَز الخطوة الأخيرة.

    maybe_gremlin = pipetype(this.graph, step[1], maybe_gremlin, state)

استدعاءُ دالة نوع الأنبوب الخاصة بالخطوة مع وسائطها.

    if(maybe_gremlin == 'pull') {           // 'pull' means the pipe wants more input
      maybe_gremlin = false
      if(pc-1 > done) {
        pc--                                // try the previous pipe
        continue
      } else {
        done = pc                           // previous pipe is done, so we are too
      }
    }

ولمعالجة حالة 'pull' نضبط أولًا maybe_gremlin^[24] على false. فنحن هنا نُحمّل (overload) معنى «ربما» باستخدامه قناةً لتمرير إشارتَي 'pull' و'done'، لكن بمجرّد أن تُنتزع إحدى تلك الإشارتين نعود إلى التفكير في هذا على أنه «ربما» بالمعنى الصحيح.

إن كانت الخطوةُ التي قبلنا ليست 'done'^[25]، فإننا نحرّك الرأسَ إلى الوراء ونحاول مرّةً أخرى. وإلّا فإننا نعلّم أنفسنا بأننا 'done' ونترك الرأسَ يسقط إلى الأمام طبيعيًّا.

    if(maybe_gremlin == 'done') {           // 'done' tells us the pipe is finished
      maybe_gremlin = false
      done = pc
    }

معالجةُ حالة 'done' أسهلُ من ذلك: نضبط maybe_gremlin على false ونعلّم هذه الخطوة بأنها 'done'.

    pc++                                    // move on to the next pipe

    if(pc > max) {
      if(maybe_gremlin)
        results.push(maybe_gremlin)         // a gremlin popped out of the pipeline
      maybe_gremlin = false
      pc--                                  // take a step back
    }
  }

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

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

  results = results.map(function(gremlin) { // return projected results, or vertices
    return gremlin.result != null
         ? gremlin.result : gremlin.vertex } )

  return results
}

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

محوّلات الاستعلام

لدينا الآن مفسِّرٌ مضغوطٌ جيّد لبرامج استعلاماتنا، لكننا ما زلنا نفتقر إلى شيء. فكل نظام إدارة قواعد بيانات حديث (DBMS) يأتي مع مُحسِّن استعلامات (query optimizer) كجزءٍ أساسيّ من النظام. أمّا في قواعد البيانات غير العلائقية، فإن تحسينَ خطة الاستعلام نادرًا ما يُعطي المكاسبَ الأُسّية (exponential speedups) التي نراها في نظيراتها العلائقية^[26]، لكنه يظلّ جانبًا مهمًّا من تصميم قواعد البيانات.

فما أبسطُ شيءٍ يمكننا فعله ويمكن أن نسمّيه منصفًا مُحسِّنَ استعلامات؟ حسنًا، يمكننا كتابةُ دوالَّ صغيرة لتحويل برامج استعلاماتنا قبل تشغيلها. سنُدخل برنامجًا كإدخال، ونُخرج برنامجًا مختلفًا كمُخرَج.

Dagoba.T = []                               // transformers (more than meets the eye)

Dagoba.addTransformer = function(fun, priority) {
  if(typeof fun != 'function')
    return Dagoba.error('Invalid transformer function')

  for(var i = 0; i < Dagoba.T.length; i++)  // OPT: binary search
    if(priority > Dagoba.T[i].priority) break

  Dagoba.T.splice(i, 0, {priority: priority, fun: fun})
}

الآن يمكننا إضافةَ محوّلات الاستعلام إلى نظامنا. ومحوِّلُ الاستعلام دالةٌ تقبل برنامجًا وتُعيد برنامجًا، إضافةً إلى مستوى أولوية (priority). والمحوِّلاتُ ذات الأولوية الأعلى توضع أقربَ إلى مقدّمة القائمة. ونحن نتأكّد من أن fun دالة، لأننا سنُقيّمها لاحقًا^[27].

سنفترض ألا تكون هناك إضافاتُ محوّلاتٍ بكميةٍ كبيرة، وسنمرّ على القائمة خطيًا لإضافة محوِّل جديد. وسنترك ملاحظةً احتياطًا لو تبيّن خطأُ هذا الافتراض—فالبحثُ الثنائيّ (binary search) أكثرُ مثليةً زمنيًا للقوائم الطويلة، لكنه يضيف بعض التعقيد ولا يسرّع فعليًّا القوائم القصيرة.

ولتشغيل هذه المحوّلات سنحقن سطرَ شيفرةٍ واحدًا في مقدّمة مفسّرنا:

Dagoba.Q.run = function() {                     // our virtual machine for querying
  this.program = Dagoba.transform(this.program) // activate the transformers

سنستخدم ذلك لاستدعاء هذه الدالة، التي لا تكتفي إلا بتمرير برنامجنا عبر كل محوِّل بالتناوب:

Dagoba.transform = function(program) {
  return Dagoba.T.reduce(function(acc, transformer) {
    return transformer.fun(acc)
  }, program)
}

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

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

وفي ضوء ذلك، فإن هذا النوع من «التحسين المتعامد» (orthogonal optimization) لافتٌ للاهتمام على وجه الخصوص. يمكننا إضافةَ المُحسِّنين في وحداتٍ مستقلّة أو حتى في شيفرة المستخدم، بدلًا من تشابكهم التامّ مع المحرّك. ويمكننا اختبارَهم بمعزل عن بعضهم أو في مجموعات، ثم بإضافة الاختبارات التوليدية (generative testing) يمكننا حتى أتمتةُ تلك العملية، بما يضمن أن مُحسِّنينا المتاحين يتعايشون معًا بكل ودّ.

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

الأسماء المستعارة

إنشاءُ استعلامٍ مثل g.v('Thor').out().in() مضغوطٌ إلى حدٍّ لا بأس به، لكن هل هذا أشقاءُ ثور أم زملاؤه؟ ولا التفسيرُ مقنعٌ تمامًا. وكان الأجمل أن تقول ما تعني: إمّا g.v('Thor').parents().children() أو g.v('Thor').children().parents().

ويمكننا استعمالُ محوّلات الاستعلام لصناعة أسماءٍ مستعارة بمجرّد دالتَي مساعدتين إضافيتين:

Dagoba.addAlias = function(newname, oldname, defaults) {
  defaults = defaults || []                     // default arguments for the alias
  Dagoba.addTransformer(function(program) {
    return program.map(function(step) {
      if(step[0] != newname) return step
      return [oldname, Dagoba.extend(step[1], defaults)]
    })
    }, 100)                                     // 100 because aliases run early

  Dagoba.addPipetype(newname, function() {})
}

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

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

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

Dagoba.extend = function(list, defaults) {
  return Object.keys(defaults).reduce(function(acc, key) {
    if(typeof list[key] != 'undefined') return acc
    acc[key] = defaults[key]
    return acc
  }, list)
}

الآن يمكننا أن نصنع تلك الأسماءَ المستعارة التي أردناها:

Dagoba.addAlias('parents', 'out')
Dagoba.addAlias('children', 'in')

ويمكننا أيضًا أن نبدأ في تخصيص نموذج بياناتنا أكثر قليلًا، بأن نُوسم كل حافةٍ بين أبٍ وابنه بأنها حافةُ «والد». عندئذٍ ستبدو أسماؤنا المستعارة هكذا:

Dagoba.addAlias('parents', 'out', ['parent'])
Dagoba.addAlias('children', 'in', ['parent'])

والآن يمكننا إضافةَ حوافّ للأزواج، أو للآباء من الزيجات السابقة، أو حتى للحبّين المخدوعين. وإذا حسّنّا دالةَ addAlias فيمكننا تقديمُ أسماءٍ مستعارة جديدة للأجداد، أو للأشقاء، أو حتى لأبناء العمومة:

Dagoba.addAlias('grandparents', [ ['out', 'parent'], ['out', 'parent']])
Dagoba.addAlias('siblings',     [ ['as', 'me'], ['out', 'parent']
                                , ['in', 'parent'], ['except', 'me']])
Dagoba.addAlias('cousins',      [ ['out', 'parent'], ['as', 'folks']
                                , ['out', 'parent'], ['in', 'parent']
                                , ['except', 'folks'], ['in', 'parent']
                                , ['unique']])

اسمُ cousins المستعار مرهقٌ نوعًا ما. ولعلّنا نستطيع توسيعَ دالة addAlias لتتيح لنا استعمالَ أسماءٍ مستعارة أخرى داخل أسمائنا المستعارة، وأن نستدعيها هكذا:

Dagoba.addAlias('cousins',      [ 'parents', ['as', 'folks']
                                , 'parents', 'children'
                                , ['except', 'folks'], 'children', 'unique'])

الآن، بدلًا من

g.v('Forseti').parents().as('parents').parents().children()
                        .except('parents').children().unique()

يمكنك ببساطة أن تقول g.v('Forseti').cousins().

لكننا أدخلنا أنفسنا هنا في موضعٍ شائكٍ نوعًا ما: فبينما تُحلّ دالةُ addAlias اسمًا مستعارًا، عليها أن تحلّ أسماءً مستعارةً أخرى أيضًا. فماذا لو استدعى parents اسمًا مستعارًا آخر، وحين نحلّ cousins اضطررنا إلى التوقّف لحلّ parents ثم لحلّ أسمائه المستعارة وهكذا؟ وماذا لو استدعى أحدُ أسماء parents المستعارة في النهاية cousins؟

وهذا ينقلنا إلى عالم استرجاع التبعيات (dependency resolution)^[28]، وهو مكوّنٌ أساسيٌّ في مديري الحزم الحديثين. وهناك كثيرٌ من الحيل المتقنة لاختيار الإصدارات المثلى، وهزّ الأشجار (tree shaking)، والتحسينات العامة وما شابه، لكن الفكرةَ الأساسية بسيطةٌ إلى حدٍّ ما. سنصنع رسمًا بيانيًا لكل التبعيات وعلاقاتها، ثم نحاول أن نجد طريقةً نحاذي بها الرؤوس مع جعل كل الأسهم تسير من اليسار إلى اليمين. فإن استطعنا، فتُسمّى هذه الترتيبُيةُ تحديدًا للرؤوس «ترتيبًا طوبولوجيًّا» (topological ordering)، وعندئذٍ نكون قد أثبتنا أن رسمَنا البياني للتبعيات خالٍ من الدورات: فهو رسمٌ بياني غير دوري موجّه (Directed Acyclic Graph, DAG). وإن عجزنا عن ذلك، فإن رسمَنا البياني فيه دورةٌ واحدةٌ على الأقل.

ومن ناحية أخرى، نتوقّع أن استعلاماتنا ستكون عمومًا قصيرةً نوعًا ما (فمئةُ خطوةٍ ستكون استعلامًا طويلًا جدًّا)، وأن عددَ المحوّلات لدينا سيكون منخفضًا إلى حدٍّ معقول. وبدلًا من العبث بالرسوم البيانية غير الدورية وإدارة التبعيات، يمكننا أن نُعيد 'true' من دالة التحويل إذا تغيّر شيء، ثم نشغّلها حتى تتوقّف عن أن تكون مثمرة. وهذا يتطلّب من كل محوِّل أن يكون قابلًا للتكرار (idempotent)، وهي خاصيةٌ مفيدة لأن تملكها المحوّلات. فما مزايا وعيوب هذين المسارين؟

الأداء

تشترك جميعُ قواعد البيانات الرسومية الإنتاجية في خاصية أداءٍ معيّنة: فاستعلاماتُ اجتياز الرسم البياني ذاتُ زمن ثابت (constant time) بالنسبة إلى الحجم الكلّي للرسم البياني^[29]. أمّا في قاعدة بياناتٍ غير رسومية، فإن طلبَ قائمة أصدقاء شخصٍ قد يستغرق زمنًا متناسبًا مع عدد المدخلات، لأنك في أسوأ الحالات الساذجة مضطرٌ للنظر في كل مُدخل. وهذا يعني أن استعلامًا على عشرة مدخلات يستغرق ميلي ثانية، فإن استعلامًا على عشرة ملايين مُدخلٍ سيستغرق قرابة أسبوعين. وستصل قائمتُ أصدقائك أسرعَ لو أُرسلت عبر Pony Express^[30]!

ولتخفيف هذا الأداء المُكئب، تُنشئ معظمُ قواعد البيانات فهارسَ على الحقول كثيرةِ الاستعلام، ممّا يحوّل بحثًا ذا $O(n)$ إلى بحثٍ ذا $O(log n)$. وهذا يمنح أداءَ بحثٍ أفضلَ بكثير، لكن مقابل ذلك نخسر بعضَ أداء الكتابة ونخسر مساحةً كبيرة—فالفهارسُ يمكن أن تضاعف حجمَ قاعدة البيانات بسهولة. والموازنةُ المتأنّية بين مقايضات المساحة والزمن في الفهارس جزءٌ من عملية الضبط الدائم لمعظم قواعد البيانات.

وتتجاوز قواعدُ البيانات الرسومية هذه المشكلةَ بجعلها تصل بين الرؤوس والحوافّ اتصالاتٍ مباشرة، فتصبح اجتيازاتُ الرسم البياني مجردَ قفزاتِ مؤشّرات؛ لا حاجةَ إلى المسح في كل عنصر، ولا حاجةَ إلى فهارس، ولا عملَ إضافي على الإطلاق. وصار إيجادُ أصدقائك له السعرُ نفسه مهما بلغ العددُ الكلّي للناس في الرسم البياني، من دون تكلفة إضافية في المساحة ولا في زمن الكتابة. وأحدُ عيوب هذا المقاربة أن المؤشّرات تعمل على أفضل وجه حين يكون الرسمُ البياني الكلّي في ذاكرة الآلة نفسها. فتقسيمُ قاعدة بياناتٍ رسومية فعليًّا على عدّة آلات لا يزال مجالَ بحثٍ نشطًا^[31].

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

Dagoba.G.findInEdges  = function(vertex) {
  return this.edges.filter(function(edge) {return edge._in._id  == vertex._id} )
}
Dagoba.G.findOutEdges = function(vertex) {
  return this.edges.filter(function(edge) {return edge._out._id == vertex._id} )
}

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

Dagoba.G.findInEdges  = function(vertex) { return this.inEdgeIndex [vertex._id] }
Dagoba.G.findOutEdges = function(vertex) { return this.outEdgeIndex[vertex._id] }

وهنا تعود أصدقاؤنا القدامى من جديد: جوارٌ بلا فهرس، نقيٌّ وحلو.

Dagoba.G.findInEdges  = function(vertex) { return vertex._in  }
Dagoba.G.findOutEdges = function(vertex) { return vertex._out }

نفّذ هذه بنفسك لتختبر الفرقَ الذي تُحدثه قاعدة البيانات الرسومية^[32].

التسلسل

وجودُ رسمٍ بياني في الذاكرة أمرٌ رائع، لكن كيف نضعه هناك أصلًا؟ رأينا أن باني الرسم البياني لدينا يستطيع أن يأخذ قائمة رؤوس وقائمة حوافّ وينشئ لنا رسمًا بيانيًا، لكن كيف نستخرج الرؤوس والحوافّ بعد انتهاء البناء؟

ميلُنا الطبيعي هو أن نفعل شيئًا كـ JSON.stringify(graph)، وهو يُنتج الخطأ الرهيب «TypeError: Converting circular structure to JSON». وخلال عملية بناء الرسم البياني كانت الرؤوسُ مربوطةً بحوافّها، والحوافّ كلها مربوطةٌ برؤوسها، فصار كل شيءٍ يشير إلى كل شيء. فكيف نستخرج قوائمَنا الجميلةَ المرتّبةَ مرّةً أخرى؟ إلى مُستبدِلات JSON (replacer functions) لإنقاذنا.

تأخذ دالةُ JSON.stringify قيمةً لتُسلسلها، لكنها تأخذ أيضًا وسيطين إضافيين: دالةَ مُستبدِل ورقمَ مسافاتٍ بيضاء^[33]. ويتيح لك المُستبدِل تخصيصَ كيفية سير التسلسل.

نحتاج إلى معاملة الرؤوس والحوافّ معاملةً مختلفة قليلًا، لذا سندمج الجانبين يدويًّا في سلسلة JSON واحدة.

Dagoba.jsonify = function(graph) {
  return '{"V":' + JSON.stringify(graph.vertices, Dagoba.cleanVertex)
       + ',"E":' + JSON.stringify(graph.edges,    Dagoba.cleanEdge)
       + '}'
}

وهذه هي مُستبدِلات الرؤوس والحوافّ.

Dagoba.cleanVertex = function(key, value) {
  return (key == '_in' || key == '_out') ? undefined : value
}

Dagoba.cleanEdge = function(key, value) {
  return (key == '_in' || key == '_out') ? value._id : value
}

الفرقُ الوحيد بينهما هو ما يفعلانه حين تكون هناك دورةٌ على وشك التكوّن: فأمّا الرؤوس فنتخطّى قائمةَ الحوافّ تمامًا. وأمّا الحوافّ فنستبدل كلَّ رأسٍ بمعرّفه. وبذلك نتخلّص من كل الدورات التي أنشأناها أثناء بناء الرسم البياني.

نحن نتلاعبُ بـ JSON يدويًّا في Dagoba.jsonify، وهو أمرٌ لا يُنصح به عادةً لأن صيغة JSON هشّةٌ إلى حدٍّ ما. فحتى في جرعةٍ بهذا الحجم من السهل أن يفوتك شيءٌ، ويصعب التأكّد من صحّته بالنظر.

و يمكننا أن ندمج دالتي المُستبدِل في دالةٍ واحدة، ونستعمل دالةَ المُستبدِل الجديدة على الرسم البياني كلّه عبر JSON.stringify(graph, my_cool_replacer). هذا يُعفينا من الحاجة إلى تلاعبٍ يدويّ بمُخرَج JSON، لكن الشيفرة الناتجة قد تكون فوضويّةً إلى حدٍّ كبير. جرّبها بنفسك وانظر إن استطعت أن تصل إلى حلٍّ جيّد التنظيم يتجنّب JSON المكتوب بخط اليد. (ونقاطٌ إضافية إن أمكنك حشره في تغريدة.)

الاستمرارية

الاستمرارية عادةً إحدى الأجزاء العسيرة في قاعدة البيانات: فالأقراص آمنةٌ نسبيًّا لكن بطيئة. وتجميعُ عمليات الكتابة في دفعات، وجعلُها ذرّية (atomic)، واليوميات (journaling)—هذه أمورٌ يصعب جعلُها سريعةً وصحيحةً معًا.

ولحسن الحظ، فنحن نبني قاعدةَ بياناتٍ في الذاكرة (in-memory)، لذا لا نضطر للقلق من أيّ ذلك! لكننا قد نرغب أحيانًا في حفظ نسخةٍ من قاعدة البيانات محليًّا لإعادة تشغيلٍ سريعةٍ عند تحميل الصفحة. يمكننا استعمالُ المُسلسِل (serializer) الذي بنيناه للتوّ لفعل ذلك بالضبط. لنغلّفه أولًا في دالةٍ مساعدة:

Dagoba.G.toString = function() { return Dagoba.jsonify(this) }

في JavaScript تُستدعى دالةُ toString الخاصة بالكائن كلَّما أُرغِط (coerced) ذلك الكائن في نصّ. فإذا كان g رسمًا بيانيًا، فإن g+'' سيكون سلسلةَ JSON المُسلسَلة للرسم البياني.

دالةُ fromString ليست جزءًا من مواصفة اللغة، لكن وجودُها مفيد.

Dagoba.fromString = function(str) {             // another graph constructor
  var obj = JSON.parse(str)                     // this can throw
  return Dagoba.graph(obj.V, obj.E)
}

الآن سنستعملهما في دوالّ الاستمرارية لدينا. أمّا دالةُ toString فتختفي—أتراها؟

Dagoba.persist = function(graph, name) {
  name = name || 'graph'
  localStorage.setItem('DAGOBA::'+name, graph)
}

Dagoba.depersist = function (name) {
  name = 'DAGOBA::' + (name || 'graph')
  var flatgraph = localStorage.getItem(name)
  return Dagoba.fromString(flatgraph)
}

نُسند اسمًا مستعارًا إلى الاسم لتفادي تلويث خصائص نطاق localStorage، لأن المساحة هناك يمكن أن تمتلئ حقًّا. وعادةً ما يكون هناك حدٌّ منخفض للتخزين، فمع الرسوم البيانية الأكبر ربما نرغب في استعمال Blobٍ من نوعٍ ما.

وهناك أيضًا مشكلاتٌ محتملة إذا كانت عدّةُ نوافذ متصفّحٍ من النطاق نفسه تُجري عمليات حفظٍ وإلغاء حفظٍ في الوقت نفسه. فمساحةُ localStorage مشتركةٌ بين تلك النوافذ، وقد تكون على حلقاتِ أحداثٍ مختلفة، فثمة احتمالٌ أن يُطمس أحدُها عملَ الآخر إهمالًا. ويقول المواصفة ينبغي أن يكون هناك كائنُ حِصانة (mutex) مطلوبٌ للوصول للقراءة/الكتابة في localStorage، لكن تنفيذَه غيرُ متّسقٍ بين المتصفّحات المختلفة، وحتى معه قد يظلّ تنفيذٌ بسيطٌ مثل تنفيذنا عرضةً للمشكلات.

وإذا أردنا أن يكون تنفيذُ الاستمرارية لدينا واعيًا بتزامن عدّة النوافذ، فبإمكاننا الاستفادةُ من أحداث التخزين (storage events) التي تُطلق عند تغيّر localStorage لتحديث رسمنا البياني المحلي تبعًا لذلك.

التحديثات

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

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

فسندفع ثمنَ الأداء لننسخ قائمة الحوافّ. لكن تظلّ هناك مشكلة، إذ قد لا ترى الاستعلاماتُ طويلةُ العمر تسلسلًا زمنيًا متّسقًا تمامًا. سنتجاوز كل حافةٍ تخصّ رأسًا لحظة زيارته، لكننا نزور الرؤوس عند أوقاتٍ مختلفةٍ من الساعة أثناء استعلامنا. فلنفترض أننا حفظنا استعلامًا مثل var q = g.v('Odin').children().children().take(2) ثم استدعينا q.run() لجمع حفيدين من أحفاد Odin. وبعد وقتٍ نحتاج فيه إلى سحب حفيدين آخرين، فنستدعي q.run() مرّةً أخرى. فإذا كان Odin قد أنجب حفيدًا جديدًا في الفترة بين ذلك، فقد نراه أو لا نراه، بحسب ما إذا كان رأسُ الوالدين قد زُر في المرة الأولى التي شغّلنا فيها الاستعلام.

إحدى طرق إصلاح هذا عدم الحتمية هي تغييرُ معالِجات التحديث لتضيف إصدارات (versions) إلى البيانات. سنغيّر بعدها حلقة التشغيل لتُمرِّر الإصدارَ الحالي للرسم البياني إلى الاستعلام، حتّى نرى دائمًا منظرًا متّسقًا للعالم كما كان وقت تهيئة الاستعلام لأول مرّة. وإضافةُ إصداراتٍ إلى قاعدة بياناتنا تفتح الباب أيضًا أمام المعاملات (transactions) الحقيقية، والتراجع/الإعادة الآلية بأسلوبٍ يشبه STM.

اتجاهات مستقبلية

رأينا طريقةً واحدةً لجمع الأسلاف:

g.v('Thor').out().as('parent')
           .out().as('grandparent')
           .out().as('great-grandparent')
           .merge(['parent', 'grandparent', 'great-grandparent'])
           .run()

هذا مرهقٌ نوعًا ما، ولا يتوسّع جيّدًا—فماذا لو أردنا ستَّ طبقاتٍ من الأسلاف؟ أو أردنا النظر عبر عددٍ اعتباطيٍّ من الأسلاف حتى نجد ما نريد؟

كان أجمل لو استطعنا أن نقول شيئًا كهذا بدلًا من ذلك:

g.v('Thor').out().all().times(3).run()

ما نودّ استخراجه من هذا هو شيءٌ مثل الاستعلام أعلاه—ربما:

g.v('Thor').out().as('a')
           .out().as('b')
           .out().as('c')
           .merge(['a', 'b', 'c'])
           .run()`

بعد أن تكون محوّلاتُ الاستعلام قد عملت جميعًا. يمكننا تشغيلَ محوِّل times أولًا لينتج:

    g.v('Thor').out().all().out().all().out().all().run()

ثم نشغّل محوِّل all ونجعله يحوّل كل all إلى as موسومٍ بتمييزٍ فريد، ويضع merge بعد آخر as.

لكن هناك بضع مشكلات في ذلك. فأوّلًا، لا تعمل تقنيةُ as/merge هذه إلّا إذا كان كلُّ مسارٍ موجودًا في الرسم البياني: فإذا كان ينقصنا مُدخلٌ لأحد أجداد أجداد ثور، فسنتخطّى مُدخلاتٍ صحيحة. وثانيًا، ماذا يحدث إن أردنا فعلَ هذا لجزءٍ من استعلامٍ فقط لا للاستعلام كله؟ وماذا إن كانت هناك عدّةُ all؟

ولحلّ المشكلة الأولى سنضطر إلى معاملة all بوصفه شيئًا أكثر من مجرّد as/merge. فنحتاج أن يتخطّى كل شرشورٍ أبٍ فعلًا الخطواتَ الواقعة بينهما. يمكننا أن نتخيّل هذا نوعًا من الانتقال الفوريّ (teleportation)—قفزًا من جزءٍ من خط الأنابيب إلى جزءٍ آخر مباشرة—أو أن نتخيّله خطَّ أنابيبٍ متفرّعًا من نوعٍ ما، لكن في كلتا الحالتين يُعقّد ذلك نموذجَنا بعض الشيء. ومنهجٌ آخر أن نتخيّل الشرشورَ يمرّ عبر الأنابيب الواقعة بينهما في حالٍ من التعليق المُجمَّد حتى يستيقظه أنبوبٌ خاص. غير أن تحديدَ نطاق أنابيب التعليق وإلغائه قد يكون عسيرًا.

والمشكلتان التاليتان أسهل. لتعديل جزءٍ من استعلامٍ فقط سنغلّف ذلك الجزء بخطوتي بدايةٍ ونهايةٍ خاصّتين، مثل g.v('Thor').out().start().in().out().end().times(4).run(). وفي الواقع، إن كان المفسِّر يعرف أنواعَ الأنابيب هذه الخاصة، فلن نحتاج إلى خطوة النهاية، لأن نهاية أي تسلسلٍ هي دائمًا نوعُ أنبوبٍ خاص. وسنسمي أنواعَ الأنابيب هذه «ظروفًا» (adverbs)، لأنها تعدّل أنواعَ الأنابيب العادية كما تعدّل الظروفُ الأفعال.

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

وتظلّ هناك مسألةُ البحث عبر عددٍ غير محدودٍ من الأسلاف—فمثلًا، كيف نعرف أيّ أبناء يميّر موعودون بالنجاة من راغناروك؟ يمكننا أن نصنع استعلاماتٍ فرديةً مثل g.v('Ymir').in().filter({survives: true}) و g.v('Ymir').in().in().in().in().filter({survives: true})، ونجمع النتائج بأنفسنا يدويًّا، لكن هذا فظيعٌ نوعًا ما.

نودّ استعمالَ ظرفٍ كهذا:

g.v('Ymir').in().filter({survives: true}).every()

وهو يعمل كما تعمل all+times لكن دون فرض حدٍّ. غير أننا قد نرغب في فرض استراتيجيةٍ بعينها على اجتياز الرسم البياني، مثل بحثٍ عريضٍ (BFS) متثابر أو بحثٍ عميق «يلوغو» (YOLO DFS)، فـ g.v('Ymir').in().filter({survives: true}).bfs() سيكون أكثر مرونة. وصياغتُنا الأمر على هذا النحو تتيح لنا أن نُصوغ استعلاماتٍ معقّدةٌ مثل «تحقّق من ناجيي راغناروك، مع تخطّي كل جيلٍ بالتناوب» صياغةً مباشرة: g.v('Ymir').in().filter({survives: true}).in().bfs().

الخاتمة

فماذا تعلّمنا؟ قواعدُ البيانات الرسومية عظيمةٌ لتخزين بياناتٍ مترابطة^[34] تخطّط للاستعلام عنها عبر اجتيازاتٍ في الرسم البياني. وإضافةُ الدلالات غير الصارمة تتيح واجهةً سلسةً فوق استعلاماتٍ ما كنت لتستطيع التعبيرَ عنها أبدًا في نظامٍ مستعجلٍ لأسبابٍ متعلّقة بالأداء، وتتيح لك أيضًا عبورَ الحدود غير المتزامنة. والزمنُ يعقّد الأمور، والزمنُ من منظوراتٍ متعددة (أي التزامن) يعقّد الأمور كثيرًا، لذا كلما استطعنا تفاديَ إدخال تبعيةٍ زمنية (مثل الحالة، أو الآثار المحسوسة، أو ما شابه) جعلنا التفكيرَ في نظامنا أسهل. والبناءُ بأسلوبٍ بسيطٍ مفكوكٍ وغير مُحسَّنٍ إطلاقًا يترك البابَ مفتوحًا أمام تحسيناتٍ شاملةٍ لاحقًا، واستعمالُ حلقة تشغيلٍ يتيح تحسيناتٍ متعامدة—كلٌّ منها دون أن يُدخل هشاشةَ التعقيد التي هي السمةُ المميِّزة لمعظم تقنيات التحسين.

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

شكر وتقدير

نُقدّر جزيلَ الشكر إلى Amy Brown، وMichael DiBernardo، وColin Lupton، وScott Rostrup، وMichael Russo، وErin Toliver، وLeo Zovic، على مساهماتهم القيّمة في هذا الفصل.

---

1. كان أحد أوائل تصاميم قواعد البيانات هو النموذج الهرمي (hierarchical model)، الذي كان يجمع العناصر في تدرّجات هرمية على شكل شجرة، ولا يزال مستخدَمًا كأساس لمنتج IBM المسمّى IMS، وهو نظام معالجة معاملات (transaction processing) عالي السرعة. ويمكن كذلك رؤية تأثيره في XML، وأنظمة الملفات، وتخزين المعلومات الجغرافية. أمّا النموذج الشبكي (network model)، الذي اخترعه تشارلز باخمان ومَنَّته معيار CODASYL، فقد عمّم النموذج الهرمي بالسماح بأكثر من أب، فشكّل رسمًا بيانيًا غير دوري (DAG) بدلًا من شجرة. وقد أتت هذه النماذج التنقّلية لقواعد البيانات إلى الشهرة في ستّينيات القرن الماضي، وواصلت هيمنتها حتى جعلت مكاسبُ الأداء قواعدَ البيانات العلائقية قابلةً للاستخدام في الثمانينيات. ↩︎

2. طوّر Edgar F. Codd نظرية قواعد البيانات العلائقية أثناء عمله في IBM، لكن IBM خافت من أن تُهيمن قاعدة بيانات علائقية على مبيعات IMS. ومع أن IBM بنت في النهاية نموذجًا بحثيًّا سمّته System R، إلا أنه كان مبنيًّا حول لغة جديدة غير علائقية اسمها SEQUEL، بدلًا من لغة Alpha الأصلية لكود. وقد نقل Larry Ellison لغة SEQUEL هذه إلى قاعدة بياناته Oracle Database اعتمادًا على أوراق مؤتمّرات سبقت الإطلاق، ثم غُيِّر الاسم إلى SQL تفاديًا لنزاعات العلامات التجارية. ↩︎

3. بدأت حياة قاعدة البيانات هذه بوصفها إضافةً لإدارة الرسوم البيانية غير الدورية الموجّهة (Directed Acyclic Graphs)، أو DAGs. وكان اسم «Dagoba» مقصودًا في الأصل أن ينتهي بحرف h صامت، إجلالًا للكوكب الخيالي المستنقع، لكننا حين قرأنا ظهر قطعة شوكولاتة في يومٍ ما اكتشفنا أن النسخة بلا h تشير إلى مكانٍ للتأمّل الصامت في الروابط بين الأشياء، وهو ما يبدو أنسب. ↩︎

4. غايتا هذا الفصل هما تعليم هذه العملية، وبناء قاعدة بيانات رسومية، وأن نتمتع بالأمر. ↩︎

5. لاحظ أننا نُنمذج الحوافّ كزوجٍ من الرؤوس. ولاحظ أيضًا أن تلك الأزواج مرتّبة، لأننا نستخدم مصفوفات. وهذا يعني أننا نُنمذج رسمًا بيانيًّا موجّهًا، حيث لكل حافة رأسُ بدايةٍ ورأسُ نهاية. فيتحوّل نموذجنا البصري «نقاطٌ وخطوط» إلى نموذج «نقاطٍ وأسهم». وهذا يضيف تعقيدًا إلى نموذجنا، لأننا علينا تتبّع اتجاه الحوافّ، لكنه يتيح أيضًا أن نطرح أسئلةً أكثر إثارةً للاهتمام، مثل «أيّ الرؤوس تشير إلى الرأس رقم 3؟» أو «أيّ رأس له أكبر عددٍ من الحوافّ الخارجة؟» وإن احتجنا إلى نمذجة رسمٍ بياني غير موجّه، فيمكننا إضافة حافةٍ معكوسة لكل حافةٍ موجودة في رسمنا الموجّه. وقد يكون الذهاب في الاتجاه الآخر مرهقًا: محاكاة رسمٍ موجّه انطلاقًا من رسمٍ غير موجّه. هل يمكنك أن تجد طريقةً لفعل ذلك؟ ↩︎

6. وهي متساهلةٌ في الاتجاه الآخر أيضًا: جميع الدوال متغيّرةُ العدد (variadic)، وجميع الوسائط متاحةٌ بالموضع عبر الكائن arguments، وهو أشبهُ بمصفوفةٍ دون أن يكون مصفوفةً تمامًا. («متغيّرةُ العدد» طريقةٌ فخمةٌ لقول إن دالةً ذات عددِ آخذٍ غير محدّد. و«الدالة ذات عددِ آخذٍ غير محدّد» طريقةٌ فخمةٌ لقول إنها تأخذ عددًا متغيّرًا من الوسائط.) ↩︎

7. فحوصُ Array.isArray هنا موجودةٌ للتمييز بين حالتَي الاستخدام المختلفتين، لكننا لن نطبّق عمومًا كلَّ التحققات التي يُتوقَّع أن تكون في شيفرة الإنتاج، حتى نركّز على البنية (architecture) بدلًا من سلال المهملات. ↩︎

8. لماذا لا يمكننا ببساطةٍ أن نستخدم this.vertices.length هنا؟ ↩︎

9. كثيرًا ما، حين نواجه تسريبًا في المساحة بسبب النسخ العميق، يكون الحلّ هو استخدام بنية بياناتٍ دائمة بنسخ المسارات (path-copying persistent data structure)، وهي تتيح تغييراتٍ خاليةً من الطفر مقابل $\log{}N$ فقط من المساحة الإضافية. لكن المشكلة تظلّ قائمة: فإذا احتفظ التطبيق المضيف بمؤشّر إلى بيانات الرأس، أمكنه أن يطفر بتلك البيانات في أي وقت، بغضّ النظر عن القيود التي نفرضها في قاعدة بياناتنا. والحلّ العمليّ الوحيد هو نسخُ الرؤوس نسخًا عميقًا، وهو ما يضاعف استهلاكنا للمساحة. وتتعلّق حالة الاستخدام الأصلية لـDagoba برؤوسٍ يعاملها التطبيق المضيف على أنها غير قابلة للتغيير، وهذا يتيح لنا تفادي هذه المشكلة، لكنه يتطلّب قدرًا معيّنًا من الانضباط من جانب المستخدم. ↩︎

10. يمكننا اتّخاذ هذا القرار بناءً على وسيط تهيئةٍ على مستوى Dagoba، أو تهيئةٍ خاصة بالرسم البياني، أو ربما نوعٍ ما من الاستدلال التقريبي (heuristic). ↩︎

11. نستخدم مصطلح قائمة للإشارة إلى بنية البيانات المجرّدة (abstract data structure) التي تتطلّب عمليات دفع (push) وتكرار (iterate). ونستخدم بنية البيانات الملموسة «مصفوفة» في JavaScript لتلبية واجهة البرمجة (API) التي تتطلّبها تجريديةُ القائمة. ومن الناحية التقنية، كلٌّ من «قائمة الحوافّ» و«مصفوفة الحوافّ» صحيح، لذا أيُّهما نستعمله في لحظةٍ ما يعتمد على السياق: فإن كنا نعتمد على تفاصيل مصفوفات JavaScript، مثل الخاصية .length، قلنا «مصفوفة حوافّ». وإلّا قلنا «قائمة حوافّ» للدلالة على أن أيّ تنفيذٍ للقائمة سيفي بالغرض. ↩︎

12. الثنائيُّ (tuple) بنيةُ بياناتٍ مجرّدة أخرى—أكثر تقييدًا من القائمة. وعلى وجه التحديد، للثنائيّ حجمٌ ثابت: في حالتنا هذه نستخدم ثنائيًّا من الدرجة الثانية (المعروف أيضًا بـ«زوج» في المصطلحات التقنية لباحثي بنى البيانات). واستخدامُ مصطلح أضيق بنية بياناتٍ مجرّدةٍ مطلوبة هو مجاملةٌ للمستنِدين لاحقًا. ↩︎

13. لكنّها مهملاتٌ قصيرةُ العمر جدًّا، وهي نوعيةُ المهملات الثانية الأفضل. ↩︎

14. مرجعان إلى بنية البيانات القابلة للتغيير نفسها يتصرّفان كزوجٍ من أجهزة اللاسلكي، فيسمحان لكلٍّ من يحملهما بالتواصل مباشرةً. ويمكن تمريرُ أجهزة اللاسلكي هذه من دالةٍ إلى أخرى، واستنساخُها لإنشاء كمٍّ هائلٍ من أجهزة اللاسلكي. وهذا يقلب تمامًا قنوات التواصل الطبيعية التي تمتلكها شيفرتك بالفعل. وفي نظامٍ بلا تزامن قد تستطيع أحيانًا الإفلاتَ من ذلك، لكن أدخِل التزامنَ متعدّدَ الخيوط (multithreading) أو سلوكًا غير متزامن، فيمكن لصفير أجهزة اللاسلكي كلّه أن يصبح عبئًا حقيقيًّا. ↩︎

15. أُحييت أنماطُ التفرّد في لغة Clean، ولها علاقةٌ غير خطّية بأنماط الخطّية (linear types)، التي هي بدورها نوعٌ فرعيٌّ من الأنماط البنيوية الفرعية (substructural types). ↩︎

16. تعتمدُ معظمُ بيئات تشغيل JS الحديثة جامعاتِ مهملاتٍ أجيالية (generational garbage collectors)، ويُحرص مقصودًا على إبقاء اللغة بعيدةً عن إدارة ذاكرة المحرّك، من أجل الحدّ من مصدرٍ من مصادر عدم الحتمية البرمجية. ↩︎

17. الاستدعاءُ run() في نهاية الاستعلام يستدعي المفسِّر ويُعيد النتائج. ↩︎

18. والوزنُ بوحدات skippund والطولُ بوحدات fathom، بالطبع. وبحسب كثافة لحم الآسغارد، قد يُعيد هذا الاستعلامُ نتائجَ كثيرةً أو لا شيءً البتّة. (أو فولستاغ وحده، إن كنا نسمح لشكسبير بأن يكون جزءًا من إلهنتنا عن طريق جاك كيربي.) ↩︎

19. يقول بعضُهم إن الأفضل أن تكون صريحين في كل وقت. ويقول آخرون إن نظامًا جيّدًا للاستدلال الضمني (implicits) ينتج شيفرةً أكثر إيجازًا ووضوحًا، مع شيفرةٍ تكرارية (boilerplate) أقلّ ومساحة أصغر للأخطاء. أمّا الشيءُ الوحيد الذي يمكننا جميعًا الاتفاقُ عليه هو أن الاستعمالَ الفعّال للإكراه الضمني في JavaScript يتطلّب حفظَ حالاتٍ خاصةٍ كثيرةٍ غير بديهية، ممّا يجعله حقل ألغام لمن لم يبدأ. ↩︎

20. ما الذي تتوقّع أن يُعيده كلٌّ منهما؟ وما الذي يُعيدانه فعلًا؟ ↩︎

21. هناك ظروفٌ معيّنة قد يُعطي هذا الاستعلامُ بعينه نتائجَ غير متوقّعة. هل يمكنك أن تتخيّر أيًّا منها؟ وكيف يمكنك تعديلَه للتعامل مع تلك الحالات؟ ↩︎

22. تقنيًا، نحتاج إلى تنفيذ مفسِّرٍ بدلالاتٍ غير صارمة (non-strict semantics)، ما يعني أنه لن يقيّم إلّا حين يُجبَر على ذلك. والتقييمُ الكسول (lazy evaluation) تقنيةٌ تُستخدم لتنفيذ عدم الصرامة. ومن المُكِثِر بمزج الأمرين أن نكون كسولين، لذا سنفصل بينهما فقط حين يُجبَرنا على ذلك. ↩︎

23. يتيح لنا تسلسلُ الدوال كتابةَ g.v('Thor').in().out().run() بدلًا من أسطر JS الستة غير السلسة التي يلزم لإنجاز الشيء نفسه. ↩︎

24. نسمّيه maybe_gremlin لنذكّر أنفسنا بأنه قد يكون شرشورًا، وقد يكون شيئًا آخر. وأيضًا لأنه في الأصل كان إمّا شرشورًا أو لا شيء. ↩︎

25. تذكّر أن done يبدأ من -1، فإن سابق الخطوة الأولى يكون دائمًا done. ↩︎

26. أو، بتعبيرٍ أدقّ، فالاستعلامُ السيّئ الصياغة أقلُّ احتمالًا في أن يُعطي تباطؤاتٍ أُسّية. وبصفتك مستخدمًا نهائيًا لنظام قواعد بياناتٍ علائقي، فإن جماليات جودة الاستعلام قد تكون غامضةً في كثيرٍ من الأحيان. ↩︎

27. لاحظ أننا نترك مجالَ وسيط الأولوية مفتوحًا، فيمكن أن يكون عددًا صحيحًا، أو نسبةً، أو عددًا سالبًا، أو حتى أشياءَ مثل Infinity أو NaN. ↩︎

28. يمكنك تعلّمُ المزيد عن استرجاع التبعيات في فصل Contingent من هذا الكتاب. ↩︎

29. المصطلحُ المتقن لهذا هو «الجوار بلا فهرس» (index-free adjacency). ↩︎

30. ورغم أن Pony Express لم يعمل إلّا ثمانيةَ عشرَ شهرًا بسبب ظهور التلغراف العابر للقارات واندلاع الحرب الأهلية الأمريكية، فإن Pony Express لا يزال يُذكر اليوم لأنه كان يوصّل البريد من ساحلٍ إلى ساحلٍ في عشرة أيام فقط. ↩︎

31. يتطلّب تقسيمُ قاعدة البيانات الرسومية تقسيمَ الرسم البياني. وتقسيمُ الرسم البياني الأمثل مسألةٌ من فئة NP-hard، حتى في الرسوم البيانية البسيطة مثل الأشجار والشبكات، كما أن التقريبات الجيدة تملك تعقيدًا قُعديًّا أُسّيًا. ↩︎

32. في محرّكات JavaScript الحديثة، يكون ترشيحُ قائمةٍ سريعًا إلى حدٍّ كبير—فمع الرسوم البيانية الصغيرة قد تكون النسخةُ الساذجة أسرعَ فعليًّا من النسخة بلا فهرس، بسبب بنى البيانات الأساسية وطريقة تجميع الشيفرة وقت التشغيل (JIT). جرّبها مع أحجامٍ مختلفةٍ من الرسوم البيانية لترى كيف يتوسّع كلا المقاربتين. ↩︎

33. نصيحةُ خبير: إذا كانت لديك شجرةٌ عميقة deep_tree، فإن تشغيل JSON.stringify(deep_tree, 0, 2) في وحدة تحكم JS طريقةٌ سريعةٌ لجعلها مقروءةً للبشر. ↩︎

34. لكن ليس مترابطًا إلى هذا الحدّ—فأنت تودّ أن ينمو عددُ الحوافّ طرديًّا مع عدد الرؤوس. بمعنى آخر، ينبغي ألّا يتغيّر متوسطُ عدد الحوافّ الموصولة برأسٍ مع حجم الرسم البياني. ومعظمُ الأنظمة التي نفكّر في وضعها في قاعدة بياناتٍ رسومية تملك هذه الخاصية بالفعل: فإذا كان لدى Loki مئةَ ألف حفيدٍ إضافيٍّ فلن يزداد درجةُ رأس Thor. ↩︎