التخزين المؤقت

تُستخدم تقنية التخزين المؤقت (Memoization) بكثرة في مُجمِّعات لغات البرمجة الوظيفية ، التي غالبًا ما تعتمد استراتيجية التقييم بالاسم . ولتجنب العبء الزائد الناتج عن حساب قيم الوسائط، تستخدم مُجمِّعات هذه اللغات بكثرة دوالًا مساعدة تُسمى " ثونكس" (thunks) لحساب قيم الوسائط، وتُخزِّن هذه الدوال مؤقتًا لتجنب تكرار العمليات الحسابية.

بينما يُمكن إضافة التخزين المؤقت للدوال داخليًا وبشكل صريح من قِبل مُبرمج الحاسوب بنفس طريقة factorialتنفيذ النسخة المُخزّنة مؤقتًا المذكورة أعلاه، يُمكن أيضًا تخزين الدوال الشفافة مرجعيًا مؤقتًا تلقائيًا خارجيًا . ^{[ 1 ]} لا تقتصر تطبيقات التقنيات التي استخدمها بيتر نورفيج على لغة Common Lisp (اللغة التي عرض فيها بحثه التخزين المؤقت التلقائي)، بل تشمل أيضًا لغات برمجة أخرى متنوعة . كما تم استكشاف تطبيقات التخزين المؤقت التلقائي رسميًا في دراسة إعادة كتابة المصطلحات ^{[ 4 ]} والذكاء الاصطناعي . ^{[ 5 ]}

في لغات البرمجة التي تُعتبر فيها الدوال كائنات من الدرجة الأولى (مثل Lua و Python و Perl ^{[ 6 ]} )، يُمكن تطبيق التخزين المؤقت التلقائي عن طريق استبدال الدالة (أثناء التشغيل) بقيمتها المحسوبة بمجرد حساب قيمة لمجموعة معينة من المعاملات. ويمكن للدالة التي تُجري هذا الاستبدال أن تُغلّف أي دالة شفافة مرجعيًا. انظر إلى الشفرة الزائفة التالية (حيث يُفترض أن الدوال قيم من الدرجة الأولى):

دالة الاستدعاء المُخزّن ( F هو مُعامل كائن الدالة) إذا لم يكن للملف F أي قيم مصفوفة مرفقة ، قم بتخصيص مصفوفة ترابطية تسمى القيم ؛ قم بإرفاق قيم بـ F ؛ نهاية الشرط؛ إذا كانت F.values [arguments] فارغة، فإن F.values [ arguments ] = F (arguments)؛ نهاية الشرط؛ أعد F. values[arguments] ; نهاية الدالة

لاستدعاء نسخة مُخزّنة تلقائيًا factorialباستخدام الاستراتيجية المذكورة أعلاه، بدلاً من الاستدعاء factorialالمباشر، يستدعي الكود الدالة `require` . يتحقق كل استدعاء أولًا من وجود مصفوفة مُخصصة لتخزين النتائج، وإذا لم تكن موجودة، يُلحق تلك المصفوفة. إذا لم يكن هناك عنصر في الموضع (حيث تُستخدم `require` كمفتاح للمصفوفة الترابطية)، يُجرى استدعاء فعلي للدالة `require` مع الوسائط المُقدمة. أخيرًا، يُعاد العنصر الموجود في المصفوفة عند موضع المفتاح إلى المُستدعي.memoized-call(factorial)(n)values[arguments]argumentsfactorial

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

دالة بناء-دالة-مخزنة-مؤقتة ( F هو مُعامل كائن دالة) قم بتخصيص كائن دالة يسمى memoized-version ؛ let memoized-version(arguments) be إذا لم يكن للكائن self أي قيم مصفوفة مرفقة، فإن [ self هو مرجع لهذا الكائن ] قم بتخصيص مصفوفة ترابطية تسمى القيم ؛ إرفاق القيم بالذات ؛​ نهاية الشرط؛ إذا كانت قيمة self.values[arguments] فارغة، self.values [arguments] = F (arguments); نهاية الشرط؛ أعد قيمة self.values [arguments] ؛ end let; إرجاع النسخة المخزنة مؤقتًا ؛ نهاية الدالة

بدلاً من استدعاء الدالة ، يتم إنشاء factorialكائن دالة جديد على النحو التالي:memfact

memfact = construct-memoized-unctor(factorial)

يفترض المثال أعلاه أن الدالة factorialقد تم تعريفها مسبقًا قبل استدعائها construct-memoized-functor. من هذه النقطة فصاعدًا، يتم استدعاء الدالة كلما رغبنا في حساب مضروب العدد n . في لغات مثل Lua، توجد تقنيات أكثر تطورًا تسمح باستبدال دالة بدالة جديدة تحمل نفس الاسم، مما يتيح ما يلي:memfact(n)

المضروب = بناء دالة مُخزّنة (المضروب)

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

دالة بناء-دالة-مخزنة-مؤقتة ( F هو مُعامل كائن دالة) قم بتخصيص كائن دالة يسمى memoized-version ؛ let memoized-version (arguments) be إذا لم يكن للكائن self أي قيم مصفوفة مرفقة، فإن [ self هو مرجع لهذا الكائن ] قم بتخصيص مصفوفة ترابطية تسمى القيم ؛ إرفاق القيم بالذات ؛​ قم بتخصيص كائن دالة جديد يسمى الاسم المستعار ؛ إرفاق اسم مستعار بالذات ؛ [ لإمكانية استدعاء F بشكل غير مباشر لاحقاً ] self.alias = F ;​ نهاية الشرط؛ إذا كانت قيمة self.values[arguments] فارغة، self.values [arguments] = self.alias ( arguments); [ ليست استدعاءً مباشرًا للدالة F ] نهاية الشرط؛ أعد قيمة self.values [arguments] ؛ end let; إرجاع النسخة المخزنة مؤقتًا ؛ نهاية الدالة

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

عندما يحاول محلل نحوي من أعلى إلى أسفل تحليل مدخلات غامضة بالنسبة لقواعد نحوية خالية من السياق غامضة ، فقد يحتاج إلى عدد هائل من الخطوات (مقارنةً بطول المدخلات) لتجربة جميع بدائل القواعد النحوية الخالية من السياق لإنتاج جميع أشجار التحليل الممكنة. وهذا بدوره يتطلب مساحة ذاكرة هائلة. في عام 1991، استكشف بيتر نورفيج تقنية التخزين المؤقت كاستراتيجية تحليل ، حيث أثبت إمكانية توليد خوارزمية مشابهة لاستخدام البرمجة الديناميكية ومجموعات الحالات في خوارزمية إيرلي (1970)، والجداول في خوارزمية CYK لكوك ويونغر وكاسامي، وذلك من خلال إدخال التخزين المؤقت التلقائي إلى محلل نحوي بسيط يعتمد على التراجع التكراري لحل مشكلة التعقيد الزمني الهائل. ^{[ 1 ]} وتتلخص الفكرة الأساسية في منهج نورفيج في أنه عند تطبيق محلل نحوي على المدخلات، تُخزن النتيجة في جدول تخزين مؤقت لإعادة استخدامها لاحقًا إذا أُعيد تطبيق المحلل نفسه على المدخلات نفسها.

استخدم ريتشارد فروست وباربرا شيدلوفسكي أيضًا تقنية التخزين المؤقت لتقليل التعقيد الزمني الأسي لمُركِّبات المُحلِّل النحوي ، واصفين النتيجة بأنها مُعالِج لغة وظيفي بحت يعتمد على التخزين المؤقت ويتراجع من أعلى إلى أسفل. ^{[ 7 ]} بيّن فروست أنه يُمكن استخدام مُركِّبات المُحلِّل النحوي الأساسية المُخزَّنة مؤقتًا كعناصر بناء لإنشاء مُحلِّلات نحوية مُعقَّدة كمواصفات قابلة للتنفيذ لقواعد اللغة الخالية من السياق. ^{[ 8 ] [ 9 ]}

تمت دراسة التخزين المؤقت مرة أخرى في سياق التحليل النحوي عام 1995 من قبل مارك جونسون ويوشين دوري. ^{[ 10 ] [ 11 ]} وفي عام 2002، تم فحصه بعمق كبير من قبل برايان فورد في شكل يسمى تحليل باكرات . ^{[ 12 ]}

في عام ٢٠٠٧، وصف فروست وحافظ وكالاغان خوارزمية تحليل نحوي من أعلى إلى أسفل تستخدم التخزين المؤقت لتجنب العمليات الحسابية الزائدة، وذلك لاستيعاب أي شكل من أشكال قواعد اللغة الخالية من السياق الغامضة في وقت متعدد الحدود ( Θ (n⁴ ⁾ للقواعد النحوية اليسارية المتكررة وΘ(n³ ⁾ للقواعد النحوية غير اليسارية المتكررة). تتطلب خوارزمية التحليل النحوي من أعلى إلى أسفل مساحة متعددة الحدود لأشجار التحليل النحوي الغامضة التي قد تكون أسية، وذلك من خلال "التمثيل المضغوط" و"تجميع الغموض المحلي". يُقارن تمثيلهم المضغوط بالتمثيل المضغوط لتوميتا للتحليل النحوي من أسفل إلى أعلى . ^{[ ١٣ ]} لا يقتصر استخدامهم للتخزين المؤقت على استرجاع النتائج المحسوبة مسبقًا عند تطبيق محلل نحوي على نفس موضع الإدخال بشكل متكرر (وهو أمر ضروري لمتطلبات الوقت متعدد الحدود)؛ بل إنه متخصص لأداء المهام الإضافية التالية:

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

وصف كلٌّ من فروست وحافظ وكالاغان تطبيق الخوارزمية في PADL'08 كمجموعة من الدوال العليا (تُسمى مُركِّبات المُحلِّل ) في لغة هاسكل ، مما يُتيح إنشاء مواصفات قابلة للتنفيذ مباشرةً لقواعد اللغة الخالية من السياق (CFGs) كمعالجات لغوية. وتُعدُّ قدرة خوارزميتهم متعددة الحدود على استيعاب "أي شكل من أشكال قواعد اللغة الخالية من السياق الغامضة" مع التحليل من أعلى إلى أسفل أمرًا بالغ الأهمية فيما يتعلق بتحليل بناء الجملة والدلالات أثناء معالجة اللغة الطبيعية . يُمكنكم الاطلاع على المزيد من المعلومات حول الخوارزمية وتفاصيل تطبيقها على موقع X-SAIGA .

على الرغم من أن نورفيج قد حسّن من قوة المحلل اللغوي من خلال التخزين المؤقت، إلا أن المحلل المُحسّن ظلّ معقدًا زمنيًا مثل خوارزمية إيرلي، مما يُظهر حالة استخدام التخزين المؤقت لغرض آخر غير تحسين السرعة. يُقدّم جونسون ودوري ^{[ 11 ]} تطبيقًا آخر للتخزين المؤقت لا يتعلق بالسرعة: استخدام التخزين المؤقت لتأخير حلّ القيود اللغوية إلى نقطة في التحليل حيث تتراكم معلومات كافية لحلّ تلك القيود. في المقابل، في تطبيق التخزين المؤقت لتحسين السرعة، أثبت فورد أن التخزين المؤقت يمكن أن يضمن تحليل قواعد التعبير النحوي في وقت خطي حتى تلك اللغات التي ينتج عنها سلوك تراجع في أسوأ الحالات. ^{[ 12 ]}

انظر إلى القواعد النحوية التالية :

S → (A c ) | (B d ) A → X ( a | b ) ب → س ب س → س [س]

(ملاحظة توضيحية: في المثال أعلاه، يُقرأ الإنتاج S → (A c ) | (B d ) على النحو التالي: " S إما A متبوعًا بـ c أو B متبوعًا بـ d ". ويُقرأ الإنتاج X → x [X] على النحو التالي: " X هو x متبوعًا بـ X اختياري ".)

تُنتج هذه القواعد النحوية أحد الأشكال الثلاثة التالية للسلسلة النصية : xac أو xbc أو xbd (حيث يُفهم من x هنا أنها تعني حرف x واحدًا أو أكثر ). بعد ذلك، فكّر في كيفية تأثير هذه القواعد النحوية، المستخدمة كمواصفة تحليل، على تحليل السلسلة النصية xxxxxbd من أعلى إلى أسفل ومن اليسار إلى اليمين :

ستتعرف القاعدة A على xxxxxb (عن طريق النزول أولاً إلى X للتعرف على x واحد ، ثم النزول مرة أخرى إلى X حتى يتم استهلاك جميع x ، ثم التعرف على b )، ثم تعود إلى S ، وتفشل في التعرف على c . بعد ذلك، سينزل البند التالي من S إلى B، والذي بدوره سينزل مرة أخرى إلى X ويتعرف على x من خلال العديد من الاستدعاءات المتكررة إلى X ، ثم b ، ويعود إلى S ويتعرف أخيرًا على d .

يكمن المفهوم الأساسي هنا في عبارة " ينحدر مرة أخرى إلى X" . تُعرف عملية التطلع إلى الأمام، ثم الفشل، ثم التراجع، ثم إعادة محاولة البديل التالي في التحليل النحوي باسم "التراجع"، وهو في الأساس ما يتيح فرصًا للتخزين المؤقت في التحليل النحوي. لنفترض دالة RuleAcceptsSomeInput(Rule, Position, Input)، حيث تكون المعاملات كما يلي:

• Ruleهذا هو اسم القاعدة قيد النظر.
• Positionيمثل هذا الإزاحة التي يتم النظر فيها حاليًا في المدخلات.
• Inputهذا هو المدخل قيد الدراسة.

لنفترض أن القيمة المُعادة من الدالة RuleAcceptsSomeInputهي طول المدخلات المقبولة Rule، أو صفر إذا لم تقبل تلك القاعدة أي مدخلات عند ذلك الموضع في السلسلة. في سيناريو التراجع مع هذا النوع من التخزين المؤقت، تكون عملية التحليل كما يلي:

عندما تنزل القاعدة A إلى X عند الإزاحة 0، فإنها تخزن الطول 5 مقابل ذلك الموضع والقاعدة X. بعد فشلها عند d ، تقوم القاعدة B ، بدلاً من النزول مرة أخرى إلى X ، بالاستعلام عن الموضع 0 مقابل القاعدة X في محرك التخزين المؤقت، ويتم إرجاع طول 5 إليها، مما يوفر عليها عناء النزول مرة أخرى إلى X ، وتستمر كما لو أنها نزلت إلى X بنفس عدد المرات السابقة.

في المثال أعلاه، قد يحدث نزول واحد أو أكثر إلى X ، مما يسمح بوجود سلاسل نصية مثل xxxxxxxxxxxxxxxxbd . في الواقع، قد يكون هناك أي عدد من x قبل b . بينما يجب على استدعاء S النزول بشكل متكرر إلى X بعدد مرات وجود x، لن يضطر B أبدًا إلى النزول إلى X على الإطلاق، لأن القيمة المُعادة ستكون 16 (في هذه الحالة تحديدًا).RuleAcceptsSomeInput(X, 0, xxxxxxxxxxxxxxxxbd)

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

S → (A)؟ A أ → /* قاعدة ما */

إلى نزول واحد إلى أ .

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

بما أنه بالنسبة لأي محلل نحوي يدعم التراجع أو التحقق من المسندات النحوية، لن تحتاج كل قواعد اللغة إلى التراجع أو التحقق من المسندات، فإن عبء تخزين نتائج تحليل كل قاعدة مقابل كل إزاحة في المدخلات (وتخزين شجرة التحليل إذا كانت عملية التحليل تقوم بذلك ضمنيًا) قد يُبطئ المحلل النحوي. ويمكن التخفيف من هذا التأثير عن طريق الاختيار الصريح للقواعد التي سيخزنها المحلل النحوي مؤقتًا. ^{[ 14 ]}