برمجة المنطق المقيد

برمجة المنطق المقيد هي شكل من أشكال برمجة القيود ، حيث يتم توسيع برمجة المنطق لتشمل مفاهيم من إرضاء القيود . برنامج منطق القيود هو برنامج منطقي يحتوي على قيود في نص البنود. مثال على بند يتضمن قيدًا هو . في هذه الفقرة، يوجد قيد؛ و ، و هي أحرف حرفية كما هو الحال في برمجة المنطق العادية. تنص هذه الفقرة على شرط واحد ينطبق عليه البيان : أكبر من الصفر وكلاهما و صحيحان. A(X,Y) :- X+Y>0, B(X), C(Y)X+Y>0A(X,Y)B(X)C(Y)A(X,Y)X+YB(X)C(Y)

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

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

ب ( X ، 1 ):-  X < 0. 
ب ( X ، Y ):-  X = 1 ،  Y > 0. 
أ ( X ، Y ):-  X > 0 ،  ب ( X ، Y ).

كما هو الحال في البرمجة المنطقية العادية، فإن تقييم هدف مثل A(X,1)يتطلب تقييم نص الجملة الأخيرة باستخدام Y=1. وكما هو الحال في البرمجة المنطقية العادية، فإن هذا بدوره يتطلب إثبات الهدف B(X,1). وعلى عكس البرمجة المنطقية العادية، فإن هذا يتطلب أيضًا تلبية قيد: X>0، القيد الموجود في نص الجملة الأخيرة. (في البرمجة المنطقية العادية، لا يمكن إثبات أن X>0 ما لم يكن X مرتبطًا بمصطلح أساسي كامل وسيفشل تنفيذ البرنامج إذا لم يكن الأمر كذلك.)

لا يمكن تحديد ما إذا كان القيد قد تم تلبيته دائمًا عند مواجهة القيد. في هذه الحالة، على سبيل المثال، لا يتم تحديد قيمة Xعند تقييم البند الأخير. ونتيجة لذلك، X>0لا يتم تلبية القيد أو انتهاكه في هذه المرحلة. بدلاً من المضي قدمًا في تقييم B(X,1)ثم التحقق مما إذا كانت القيمة الناتجة عن ذلك Xموجبة بعد ذلك، يخزن المترجم القيد X>0ثم يمضي في تقييم B(X,1)؛ بهذه الطريقة، يمكن للمترجم اكتشاف انتهاك القيد X>0أثناء تقييم ، والعودة على الفور إذا كانت هذه هي الحالة، بدلاً من انتظار انتهاء B(X,1)تقييم .B(X,1)

بشكل عام، يتم تقييم برنامج منطق القيود كما هو الحال مع برنامج المنطق العادي. ومع ذلك، يتم وضع القيود التي تواجه أثناء التقييم في مجموعة تسمى مخزن القيود. على سبيل المثال، A(X,1)يتم تقييم الهدف من خلال تقييم نص الجملة الأولى بـ Y=1؛ يضيف هذا التقييم إلى مخزن القيود ويتطلب إثبات X>0الهدف . أثناء محاولة إثبات هذا الهدف، يتم تطبيق الجملة الأولى ولكن تقييمها يضيف إلى مخزن القيود. تجعل هذه الإضافة مخزن القيود غير قابل للإشباع. ثم يتراجع المترجم، ويزيل الإضافة الأخيرة من مخزن القيود. يضيف تقييم الجملة الثانية و إلى مخزن القيود. نظرًا لأن مخزن القيود قابل للإشباع ولم يتبق أي حرف آخر لإثباته، يتوقف المترجم عند الحل . B(X,1)X<0X=1Y>0X=1, Y=1

يمكن تعريف دلالات برامج منطق القيود من حيث المترجم الافتراضي الذي يحتفظ بزوج أثناء التنفيذ. يسمى العنصر الأول من هذا الزوج الهدف الحالي؛ يسمى العنصر الثاني مخزن القيود. يحتوي الهدف الحالي على القيم الحرفية التي يحاول المترجم إثباتها وقد يحتوي أيضًا على بعض القيود التي يحاول تلبيتها؛ يحتوي مخزن القيود على جميع القيود التي افترض المترجم أنها قابلة للوفاء بها حتى الآن. ${\displaystyle \langle G,S\rangle }$

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

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

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

لقد أثبت المترجم الهدف عندما يكون الهدف الحالي فارغًا ولم يتم اكتشاف عدم قابلية تلبية مخزن القيود. تكون نتيجة التنفيذ هي المجموعة الحالية من القيود (المبسطة). قد تتضمن هذه المجموعة قيودًا مثل تلك التي تجبر المتغيرات على قيمة معينة، ولكنها قد تتضمن أيضًا قيودًا مثل تلك التي تحد المتغيرات فقط دون إعطائها قيمة محددة. ${\displaystyle X=2}$${\displaystyle X>2}$

رسميًا، يتم تعريف دلالات برمجة منطق القيد من حيث الاشتقاقات . الانتقال هو زوج من أزواج الهدف/المخزن، كما هو موضح . يوضح هذا الزوج إمكانية الانتقال من حالة إلى أخرى . يكون هذا الانتقال ممكنًا في ثلاث حالات محتملة: ${\displaystyle \langle G,S\rangle \rightarrow \langle G',S'\rangle }$${\displaystyle \langle G,S\rangle }$${\displaystyle \langle G',S'\rangle }$

• عنصر من G هو قيد C ، ولدينا و ؛ بمعنى آخر، يمكن نقل القيد من الهدف إلى مخزن القيد${\displaystyle G'=G\backslash \{C\}}$${\displaystyle S'=S\c\{C\}}$
• عنصر من G هو حرفي ، يوجد جملة، عند إعادة كتابتها باستخدام متغيرات جديدة، هي ، المجموعة هي G مع استبدالها بـ ، و ؛ بعبارة أخرى، يمكن استبدال حرفي بجسم متغير جديد لجملة لها نفس المسند في الرأس، بإضافة جسم المتغير الجديد والمساواة المذكورة أعلاه للمصطلحات إلى الهدف${\displaystyle L(t_{1},\ldots ,t_{n})}$${\displaystyle L(t_{1}',\ldots ,t_{n}')\mathrel {{:}{-}} B}$${\displaystyle G'}$${\displaystyle L(t_{1},\ldots ,t_{n})}$${\displaystyle t_{1}=t_{1}',\ldots ,t_{n}=t_{n}',B}$${\displaystyle S'=S}$
• S و متكافئان وفقًا لدلالات القيد المحددة${\displaystyle S'}$

إن تسلسل التحولات هو اشتقاق. ويمكن إثبات هدف G إذا كان هناك اشتقاق من to لبعض القيود القابلة للإشباع store S . وتضفي هذه الدلالات طابعًا رسميًا على التطورات المحتملة للمترجم الذي يختار بشكل تعسفي الحرفي للهدف المراد معالجته والجملة التي تحل محل الحرفيات. بعبارة أخرى، يتم إثبات هدف بموجب هذه الدلالات إذا كان هناك تسلسل من الاختيارات بين الحرفيات والجملة، من بين العديد من الخيارات المحتملة، والتي تؤدي إلى هدف فارغ ومخزن قابل للإشباع. ${\displaystyle \langle G,\emptyset \rangle }$${\displaystyle \langle \emptyset ,S\rangle }$

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

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

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

غالبًا ما يتم الإشارة إلى المساواة الزوجية لحجج حرفيين بشكل مضغوط من خلال : هذا اختصار للقيود . يضيف أحد المتغيرات الشائعة للدلالات الخاصة ببرمجة منطق القيود مباشرةً إلى مخزن القيود بدلاً من الهدف. ${\displaystyle L(t_{1},\ldots ,t_{n})=L(t_{1}',\ldots ,t_{n}')}$${\displaystyle t_{1}=t_{1}',\ldots ,t_{n}=t_{n}'}$${\displaystyle L(t_{1},\ldots ,t_{n})=L(t_{1}',\ldots ,t_{n}')}$

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

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

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

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

في هذا الشكل من إرضاء القيود، تكون القيم المتغيرة عبارة عن مصطلحات.

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

لكي نكون أكثر دقة، فإن المصطلحات عبارة عن تعبيرات عن متغيرات وثوابت حقيقية. والمساواة بين المصطلحات هي نوع من القيود التي تكون موجودة دائمًا، حيث يولد المترجم المساواة بين المصطلحات أثناء التنفيذ. على سبيل المثال، إذا كان الحرف الأول من الهدف الحالي هو A(X+1)واختار المترجم جملة تكون A(Y-1):-Y=1بعد إعادة كتابة المتغيرات هي، فإن القيود المضافة إلى الهدف الحالي هي X+1=Y-1و . ومن الواضح أن قواعد التبسيط المستخدمة لرموز الوظائف لا تُستخدم: ليس من غير الممكن إرضاؤها لمجرد أن التعبير الأول تم إنشاؤه باستخدام والثاني باستخدام . ${\displaystyle Y=1}$X+1=Y-1+-

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

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

الفئة الثالثة من القيود المستخدمة في برمجة منطق القيود هي تلك الخاصة بالمجالات المحدودة. في هذه الحالة تؤخذ قيم المتغيرات من مجال محدود، غالبًا ما يكون من الأعداد الصحيحة . لكل متغير، يمكن تحديد مجال مختلف: X::[1..5]على سبيل المثال يعني أن قيمة Xبين 1و 5. يمكن أيضًا تحديد مجال المتغير عن طريق تعداد جميع القيم التي يمكن أن يأخذها المتغير؛ لذلك، يمكن أيضًا كتابة إعلان المجال أعلاه X::[1,2,3,4,5]. تسمح هذه الطريقة الثانية لتحديد المجال بالمجالات التي لا تتكون من أعداد صحيحة، مثل X::[george,mary,john]. إذا لم يتم تحديد مجال المتغير، فمن المفترض أنه مجموعة الأعداد الصحيحة التي يمكن تمثيلها في اللغة. يمكن إعطاء مجموعة من المتغيرات نفس المجال باستخدام إعلان مثل [X,Y,Z]::[1..5].

قد يتم تقليص نطاق المتغير أثناء التنفيذ. في الواقع، عندما يضيف المترجم قيودًا إلى مخزن القيود، فإنه يقوم بنشر القيود لفرض شكل من أشكال الاتساق المحلي ، وقد تقلل هذه العمليات من نطاق المتغيرات. إذا أصبح نطاق المتغير فارغًا، فإن مخزن القيود غير متسق، وتتراجع الخوارزمية. إذا أصبح نطاق المتغير مفردًا ، فيمكن تعيين المتغير للقيمة الفريدة في نطاقه. أشكال الاتساق التي يتم فرضها عادةً هي اتساق القوس ، واتساق القوس الفائق ، واتساق الحد . يمكن فحص النطاق الحالي للمتغير باستخدام أحرف محددة؛ على سبيل المثال، dom(X,D)يكتشف النطاق الحالي Dللمتغير X.

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

يحتوي مخزن القيود على القيود التي يُفترض حاليًا أنها قابلة للتنفيذ. ويمكن اعتبار ذلك بمثابة الاستبدال الحالي للبرمجة المنطقية العادية. عندما يُسمح فقط بمصطلحات الشجرة، يحتوي مخزن القيود على قيود في النموذج t1=t2؛ يتم تبسيط هذه القيود عن طريق التوحيد، مما يؤدي إلى قيود في النموذج variable=term؛ مثل هذه القيود تعادل الاستبدال.

ومع ذلك، قد يحتوي مخزن القيود أيضًا على قيود في النموذج t1!=t2، إذا كان الفرق !=بين المصطلحات مسموحًا به. عندما يُسمح بالقيود على الأعداد الحقيقية أو المجالات المحدودة، فقد يحتوي مخزن القيود أيضًا على قيود خاصة بالمجال مثل X+2=Y/2، وما إلى ذلك.

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

قد تأتي القيود الخاصة بالمجال إلى مخزن القيود من نص الجمل ومن مساواة حرفي برأس جملة: على سبيل المثال، إذا أعاد المترجم كتابة الحرفي A(X+2)بجملة يكون رأسها المتغير الجديد هو A(Y/2)، تتم إضافة القيد X+2=Y/2إلى مخزن القيود. إذا ظهر متغير في تعبير مجال حقيقي أو محدود، فيمكنه فقط أن يأخذ قيمة في الأعداد الحقيقية أو المجال المحدود. لا يمكن لمثل هذا المتغير أن يأخذ مصطلحًا مكونًا من دالة مطبقة على مصطلحات أخرى كقيمة. مخزن القيود غير قابل للإشباع إذا كان المتغير ملزمًا بأخذ قيمة المجال المحدد ودالة مطبقة على المصطلحات.

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

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

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

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

الاستخدام الثاني للحرفية الوسمية هو تحديد تقييم المتغيرات التي تلبي مخزن القيود. بدون الحرفية الوسمية، يتم تعيين قيم للمتغيرات فقط عندما يحتوي مخزن القيود على قيد من النموذج X=valueوعندما يقلل الاتساق المحلي من نطاق المتغير إلى قيمة واحدة. الحرفية الوسمية على بعض المتغيرات تجبر هذه المتغيرات على التقييم. بعبارة أخرى، بعد النظر في الحرفية الوسمية، يتم تعيين قيمة لجميع المتغيرات.

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

حل ( X ) : - القيود ( X )  ، قيود التسمية ( X ) 
: - ( جميع قيود CSP )     

عندما يقوم المترجم بتقييم الهدف solve(args)، فإنه يضع نص متغير جديد من الجملة الأولى في الهدف الحالي. ونظرًا لأن الهدف الأول هو constraints(X')، يتم تقييم الجملة الثانية، وتنقل هذه العملية جميع القيود في الهدف الحالي وفي النهاية إلى مخزن القيود. labeling(X')ثم يتم تقييم الحرف، مما يفرض البحث عن حل لمخزن القيود. ونظرًا لأن مخزن القيود يحتوي على قيود مشكلة إرضاء القيود الأصلية بالضبط، فإن هذه العملية تبحث عن حل للمشكلة الأصلية.

يمكن إعادة صياغة برنامج منطق القيد المعطى لتحسين كفاءته. القاعدة الأولى هي أنه يجب وضع حرفيات التسمية بعد تراكم أكبر قدر ممكن من القيود على الحرفيات المسمى في مخزن القيود. في حين أنه من الناحية النظرية يعادل ، فإن البحث الذي يتم إجراؤه عندما يواجه المترجم حرف التسمية يكون في مخزن قيود لا يحتوي على القيد . ونتيجة لذلك، قد يولد حلولاً، مثل ، والتي يتم اكتشافها لاحقًا أنها لا تلبي هذا القيد. من ناحية أخرى، في الصيغة الثانية يتم إجراء البحث فقط عندما يكون القيد موجودًا بالفعل في مخزن القيود. ونتيجة لذلك، لا يُرجع البحث إلا الحلول المتوافقة معه، مستفيدًا من حقيقة أن القيود الإضافية تقلل من مساحة البحث. A(X):-labeling(X),X>0A(X):-X>0,labeling(X)X>0X=-1

إن إعادة الصياغة الثانية التي يمكن أن تزيد من الكفاءة هي وضع القيود قبل الحروف في نص البنود. مرة أخرى، و متكافئان من حيث المبدأ. ومع ذلك، قد تتطلب الأولى المزيد من الحساب. على سبيل المثال، إذا كان مخزن القيود يحتوي على القيد ، يقوم المترجم بتقييمه بشكل متكرر في الحالة الأولى؛ إذا نجح، فإنه يكتشف بعد ذلك أن مخزن القيود غير متسق عند إضافة . في الحالة الثانية، عند تقييم هذه الفقرة، يضيف المترجم أولاً إلى مخزن القيود ثم ربما يقيم . نظرًا لأن مخزن القيود بعد إضافة تبين أنه غير متسق، فإن التقييم المتكرر لـ لا يتم إجراؤه على الإطلاق. A(X):-B(X),X>0A(X):-X>0,B(X)X<-2B(X)X>0X>0B(X)X>0B(X)

إن إعادة الصياغة الثالثة التي يمكن أن تزيد من الكفاءة هي إضافة قيود زائدة. إذا كان المبرمج يعرف (بأي وسيلة) أن حل المشكلة يلبي قيدًا معينًا، فيمكنه تضمين هذا القيد للتسبب في عدم اتساق مخزن القيود في أقرب وقت ممكن. على سبيل المثال، إذا كان من المعروف مسبقًا أن تقييم B(X)سيؤدي إلى قيمة موجبة لـ X، فقد يضيف المبرمج X>0قبل أي حدوث لـ B(X). على سبيل المثال، A(X,Y):-B(X),C(X)سيفشل في تحقيق الهدف A(-2,Z)، ولكن لا يتم اكتشاف ذلك إلا أثناء تقييم الهدف الفرعي B(X). من ناحية أخرى، إذا تم استبدال الجملة أعلاه بـ ، فإن المترجم يتراجع بمجرد إضافة القيد إلى مخزن القيود، وهو ما يحدث قبل بدء تقييم حتى. A(X,Y):-X>0,A(X),B(X)X>0B(X)

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

أ(X) <=> ب(X) | ج(X)
أ(X) ==> ب(X) | ج(X)

تنص القاعدة الأولى على أنه إذا كان B(X)الأمر يستلزم وجود المخزن، A(X)فيمكن إعادة كتابة القيد على النحو التالي C(X). على سبيل المثال، N*X>0يمكن إعادة كتابته على النحو التالي X>0إذا كان المخزن يستلزم وجود N>0. يشبه الرمز التكافؤ في المنطق، ويشير إلى أن القيد الأول يعادل الأخير. في الممارسة العملية، يعني هذا أنه يمكن استبدال<=> القيد الأول بالأخير.

تنص القاعدة الثانية بدلاً من ذلك على أن القيد الأخير هو نتيجة للقيد الأول، إذا كان القيد الموجود في المنتصف مستلزمًا لمخزن القيود. ونتيجة لذلك، إذا A(X)كان موجودًا في مخزن القيود B(X)ومستلزمًا لمخزن القيود، C(X)فيمكن إضافته إلى المخزن. وعلى عكس حالة التكافؤ، فإن هذا إضافة وليس استبدالًا: تتم إضافة القيد الجديد ولكن القيد القديم يبقى.

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

يمكن استخدام جمل البرمجة المنطقية جنبًا إلى جنب مع قواعد معالجة القيود لتحديد طريقة لتحديد مدى قابلية متجر القيود للإرضاء. تُستخدم جمل مختلفة لتنفيذ الخيارات المختلفة للطريقة؛ تُستخدم قواعد معالجة القيود لإعادة كتابة متجر القيود أثناء التنفيذ. على سبيل المثال، يمكن للمرء تنفيذ التتبع العكسي مع انتشار الوحدة بهذه الطريقة. holds(L)يمثل Let جملة اقتراحية، حيث Lتكون الأحرف الحرفية في القائمة بنفس الترتيب الذي يتم تقييمها به. يمكن تنفيذ الخوارزمية باستخدام جمل لاختيار تعيين حرفي إلى true أو false، وقواعد معالجة القيود لتحديد الانتشار. تحدد هذه القواعد أنه holds([l|L])يمكن إزالة if l=trueيلي من المتجر، ويمكن إعادة كتابته كما holds(L)لو كان if l=falseيلي من المتجر. وبالمثل، holds([l])يمكن استبداله بـ l=true. في هذا المثال، يتم تنفيذ اختيار القيمة لمتغير باستخدام جمل البرمجة المنطقية؛ ومع ذلك، يمكن ترميزه في قواعد معالجة القيود باستخدام امتداد يسمى قواعد معالجة القيود المنفصلة أو CHR ^∨ .

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

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

أ(ق).
ب(س):-أ(س).

مجموعة النتائج فارغة في البداية. في الخطوة الأولى، A(q)تكون الجملة هي الجملة الوحيدة التي يمكن إثبات نصها (لأنها فارغة)، وبالتالي A(q)تُضاف إلى مجموعة النتائج الحالية. في الخطوة الثانية، بما أنه A(q)تم إثباتها، يمكن استخدام الجملة الثانية B(q)وإضافتها إلى النتائج. نظرًا لأنه لا يمكن إثبات أي نتيجة أخرى من {A(q),B(q)}، ينتهي التنفيذ.

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

أ(ق).
ب(س):-أ(س).
أ(س):-ب(س).

على سبيل المثال، أثناء تقييم جميع الإجابات على الهدف A(X)، فإن الاستراتيجية من أعلى إلى أسفل ستنتج الاستنتاجات التالية:

أ(ق)
أ(ق):-ب(ق)، ب(ق):-أ(ق)، أ(ق)
أ(ق):-ب(ق)، ب(ق):-أ(ق)، أ(ق):-ب(ق)، ب(ق):-أ(ق)، أ(ق)

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

لا تعاني استراتيجية التصاعد من نفس العيب، حيث إن العواقب التي تم استخلاصها بالفعل ليس لها أي تأثير. في البرنامج المذكور أعلاه، تبدأ استراتيجية التصاعد من الأسفل إلى الأعلى في الإضافة A(q)إلى مجموعة العواقب؛ في الخطوة الثانية، B(X):-A(X)يتم استخدام لاستخلاص B(q)؛ في الخطوة الثالثة، الحقائق الوحيدة التي يمكن استخلاصها من العواقب الحالية هي A(q)و B(q)، والتي توجد بالفعل في مجموعة العواقب. ونتيجة لذلك، تتوقف الخوارزمية.

في المثال أعلاه، كانت الحقائق المستخدمة الوحيدة هي الأحرف الأساسية. بشكل عام، تعتبر كل جملة تحتوي فقط على قيود في النص حقيقة. على سبيل المثال، تعتبر الجملة حقيقة A(X):-X>0,X<10أيضًا. بالنسبة لهذا التعريف الموسع للحقائق، قد تكون بعض الحقائق متكافئة بينما لا تكون متساوية نحويًا. على سبيل المثال، A(q)تعادل A(X):-X=qوكلاهما متكافئان لـ A(X):-X=Y, Y=q. لحل هذه المشكلة، تُترجم الحقائق إلى شكل طبيعي يحتوي فيه الرأس على مجموعة من المتغيرات المختلفة تمامًا؛ تكون الحقيقتان متكافئتين إذا كانت أجسادهما متكافئة في متغيرات الرأس، أي أن مجموعات حلولهما هي نفسها عند تقييدهما بهذه المتغيرات.

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

أ ( 0 ). 
ا ( X ): - X > 0. 
ا ( X ): - X = Y + 1 ,  ا ( Y ).

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

تهدف الإصدارات المتزامنة من برمجة منطق القيود إلى برمجة العمليات المتزامنة بدلاً من حل مشكلات إرضاء القيود . يتم تقييم الأهداف في برمجة منطق القيود بشكل متزامن؛ وبالتالي تتم برمجة العملية المتزامنة كتقييم لهدف بواسطة المترجم .

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

تم تطبيق برمجة منطق القيود على عدد من المجالات، مثل الجدولة الآلية ، ^[1] واستنتاج النوع ، ^[2] والهندسة المدنية ، والهندسة الميكانيكية ، والتحقق من الدوائر الرقمية ، ومراقبة الحركة الجوية ، والتمويل، وغيرها. ^{[ بحاجة لمصدر ]}

تم تقديم برمجة منطق القيود بواسطة جعفر ولاسيز في عام 1987. ^[3] لقد عمموا الملاحظة القائلة بأن مصطلح المعادلات والتعديلات في Prolog II كانت شكلاً محددًا من القيود، وعمموا هذه الفكرة على لغات القيود التعسفية. كانت أولى تطبيقات هذا المفهوم هي Prolog III و CLP(R) و CHIP . ^{[ بحاجة لمصدر ]}

• ب-المقدمة
• BNR Prolog (المعروف أيضًا باسم CLP(BNR))
• قواعد التعامل مع القيود
• وداعا
• سي إل بي (ر)
• توزيع أوز موزارت
• كسوف
• جنو برولوج
• SWI-Prolog

• ديشتر، رينا (2003). معالجة القيود . مورجان كوفمان. رقم ISBN 1-55860-890-7. رقم الكتاب الدولي المعياري  1-55860-890-7
• أبت، كرزيستوف (2003). مبادئ البرمجة المقيدة . مطبعة جامعة كامبريدج. رقم ISBN 0-521-82583-0. رقم الكتاب الدولي الموحد  0-521-82583-0
• ماريوت، كيم؛ بيتر جيه ستوكي (1998). البرمجة مع القيود: مقدمة . مطبعة معهد ماساتشوستس للتكنولوجيا. رقم الكتاب الدولي المعياري  0-262-13341-5
• فروورث، توم؛ سليم عبد الناصر (2003). أساسيات برمجة القيود . سبرينغر. رقم ISBN 3-540-67623-6. رقم الكتاب الدولي المعياري  3-540-67623-6
• جعفر، جوكسان؛ مايكل جيه ماهر (1994). "برمجة المنطق المقيد: دراسة استقصائية". مجلة البرمجة المنطقية . 19/20: 503-581. doi : 10.1016/0743-1066(94)90033-7 .
• كولميراور، ألان (1987). "فتح عالم برولوج 3". بايت . أغسطس.

Original text

Rate this translation

Your feedback will be used to help improve Google Translate