الصياغة والدلالات في البرمجة المنطقية

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

تتكون برامج المنطق التصريحي بالكامل من قواعد من النموذجH :- B1, ..., BN.حيث يمكن قراءة كل قاعدة من هذه القواعد باعتبارها نتيجة ضمنية:



المعنى هو "إذا كان كل حد في جسم القاعدة (Bi) صحيحًا، إذن فإن رأس القاعدة (H) يكون صحيحًا". تقوم برامج البرمجة المنطقية بحساب مجموعة الحقائق التي تستلزمها قواعدها.

تضيف العديد من تطبيقات Datalog و برولوغواللغات ذات الصلة ميزات إجرائية مثل عامل القطع في برولوغ أو ميزات غير منطقية مثل واجهة وظيفة أجنبية. إن الدلالات الرسمية لمثل هذه الامتدادات تقع خارج نطاق هذه المقالة.

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

 بناء الجملة 
يتكون برنامج Datalog من قائمة من القواعد (جمل هورن). إذا كانت C و V مجموعتين قابلتين للعد من الثوابت والمتغيرات على التوالي، وكانت R عبارة عن مجموعة قابلة للعد من رموز المسند، فإن قواعد BNF التالية تعبر عن بنية برنامج Datalog:<program> ::= <rule> <program> | ""
<rule> ::= <atom> ":-" <atom-list> "."
<atom> ::= <relation> "(" <term-list> ")"
<atom-list> ::= <atom> | <atom> "," <atom-list> | ""
<term> ::= <constant> | <variable>
<term-list> ::= <term> | <term> "," <term-list> | "" تُعرف الذرات أيضًا باسم الحدودية (literals). وتُسمى الذرة الموجودة على يسار الرمز :- رأس القاعدة (head)؛ أما الذرات الموجودة على اليمين فتُسمى جسم القاعدة (body). ويجب أن يستوفي كل برنامج Datalog الشرط الذي ينص على أن كل متغير يظهر في رأس القاعدة يجب أن يظهر أيضًا في جسم القاعدة (يُطلق على هذا الشرط أحيانًا اسم تقييد النطاق (range restriction))  

تُسمى القواعد ذات الأجسام الفارغة حقائق (facts). على سبيل المثال، القاعدة التالية هي حقيقة:r(x) :- .

 السكر النحوي 
توسع العديد من تطبيقات البرمجة المنطقية القواعد النحوية المذكورة أعلاه للسماح بكتابة الحقائق بدون :-، مثل:r(x) :- . يسمح العديد من تطبيقات Datalog أيضًا بكتابة العلاقات الصفرية (0-ary relations) بدون أقواس، مثل هذا:p :- q.هذه مجرد اختصارات نحوية (syntactic sugar) سكر نحوي؛ وليس لها أي تأثير على دلالات البرنامج.

 مثال 
حيث انهو يقوم البرنامج التالي بحساب path العلاقة، وهو الإغلاق المتعدي edge العلاقة.edge(x, y).
edge(y, z).
path(A, B) :- 
  edge(A, B).
path(A, C) :- 
  path(A, B), 
  edge(B, C).

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

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

 النموذج النظري 
تصغير| مخطط هاس لتفسيرات هيربراند لبرنامج داتالوغe(x, y).
e(y, z).
p(A, B) :-
 e(A, B).
p(A, C) :- 
 p(A, B),
 e(B, C).التفسير  هو نموذج هيربراند البسيط. كل التفسيرات التي فوقها هي نماذج أيضًا، وكل التفسيرات التي تحتها ليست نماذج.
تُسمى القاعدة أرضية (ground) إذا كانت جميع ذراتها (الرأس والجسم) أرضية - أي لا تحتوي على أي متغيرات. وتُعتبر القاعدة الأرضية R1 مثالًا أساسيًا (ground instance) لقاعدة أخرى R 2 إذا كانت R 1  هي نتيجة استبدال جميع المتغيرات الموجودة في

R 2بثوابت معينة.

قاعدة هيربراند ( Herbrand base) لبرنامج Datalog هي مجموعة جميع الذرات الأرضية (الذرات التي لا تحتوي على متغيرات) التي يمكن إنشاؤها باستخدام الثوابت التي تظهر في البرنامج. ويُعرف التفسير (interpretation) أيضًا باسم مثيل قاعدة البيانات (database instance) وهو عبارة عن مجموعة فرعية من قاعدة هيربراند. وتكون الذرة الأساسية صحيحة في التفسير  إذا كانت عنصرًا من . وتكون القاعدة صحيحة في التفسير  إذا كان لكل مثال أساسي لتلك القاعدة، فإنه عندما تكون جميع الذرات في جسم القاعدة صحيحة في ، فإن رأس القاعدة يكون صحيحًا أيضًا في .

نموذج برنامج Datalog P هو تفسير  للبرنامج P الذي يحتوي على جميع الحقائق الأساسية الموجودة في P، ويجعل جميع قواعد P صحيحة في . وتنص دلالات نظرية النموذج(Model-theoretic semantics) على أن معنى برنامج Datalog هو نموذجه الأدنى (least model) (أو تقاطع جميع نماذجه). 

على سبيل المثال، هذا البرنامج:edge(x, y).
edge(y, z).
path(A, B) :- 
 edge(A, B).
path(A, C) :- 
 path(A, B), 
 edge(B, C).
 هل يوجد هذا الكون هيربراند : x ، y ، z

وهذه هي قاعدة هيربراند: edge(x,x ، edge(x, y، ... edge(z, z) ، path(x x)، .. path(z, z)

وهذاايضا نموذج هيربراند الأدنى: edge(x, y)، edge(y,z) ، path(x,y) ، path(y,z) ، path(x,z)

 نقطة ثابتة 
ليكن I مجموعة جميع التفسيرات لبرنامج Datalog P، أي، حيث H هي قاعدة هيربراند لـ P و P هو مشغل مجموعة القوى (power set operator). مشغل النتائج المباشرة (immediate consequence operator) لـ P هو الخريطة التالية TP من I إلى I: لكل مثال أرضي لكل قاعدة في P، إذا كانت كل جملة في جسم القاعدة موجودة في تفسير الإدخال، فقم بإضافة رأس المثال الأرضي إلى تفسير الإخراج. هذه الخريطة TP رتيبة فيما يتعلق بالترتيب الجزئي المعطى من خلال تضمين المجموعة الفرعية (⊆) على I. ووفقًا لنظرية كناستر-تارسكي (Knaster-Tarski theorem)، تحتوي هذه الخريطة على أقل نقطة ثابتة؛ ووفقًا <b>لنظرية كليين للنقطة الثابتة،</b> (Kleene fixpoint theorem)، فإن أقل نقطة ثابتة هي الحد الأعلى للسلسلة: TP(∅),TP,...إن أقل نقطة ثابتة لـ TP تتطابق مع نموذج هيربراند الأدنى (least Herbrand model) للبرنامج P. 

تشير دلالات نقطة الإصلاح (Fixpoint semantics) إلى خوارزمية لحساب نموذج هيربراند الأدنى (least Herbrand model): ابدأ بمجموعة الحقائق الأساسية الموجودة في البرنامج، ثم أضف بشكل متكرر جميع العواقب التي يمكن استنتاجها من تطبيق القواعد حتى يتم الوصول إلى نقطة الإصلاح (حيث لا يمكن إضافة المزيد من الحقائق). تُسمى هذه الخوارزمية <b>بالتقييم الساذج</b> (naive evaluation).

 إثبات نظري 
تصغير|شجرة الإثبات التي توضح اشتقاق path(x, z) من البرنامجedge(x, y).
edge(y, z).
path(A, B) :- 
 edge(A, B).
path(A, C) :- 
 path(A, B), 
 edge(B, C).
بالنظر إلى برنامج P، فإن شجرة إثبات (proof tree) للذرة الأرضية A هي شجرة ذات جذر مُسمى بـ A، وأوراق مُسماة بذرات أرضية تمثل رؤوس الحقائق في P، وفروع ذات أطفال A1,...,An مُصنفة بواسطة ذرات أرضية G بحيث توجد حالة أرضية لقاعدة في P يكون رأسها A وجسمها 

 G :- A 1, ... , A n .

بالنسبة لقاعدة في P تُعرّف دلالات نظرية الإثبات (Proof-theoretic semantics) معنى برنامج Datalog بأنه مجموعة الذرات الأساسية التي يمكن استنتاجها من مثل هذه الأشجار. وتتوافق هذه المجموعة تحديدًا مع نموذج هيربراند الأدنى (least Herbrand model).

قد يكون المرء مهتمًا بمعرفة ما إذا كانت ذرة أرضية معينة تنتمي إلى نموذج هيربراند الأدنى (least Herbrand model) لبرنامج Datalog أم لا، ربما دون الحاجة إلى حساب النموذج بأكمله. وتشير القراءة من أعلى إلى أسفل لأشجار الإثبات الموضحة سابقًا إلى خوارزمية لحساب نتائج مثل هذه الاستعلامات، وهذه القراءة تحديدًا تزودنا بخوارزمية حل SLD (SLD-resolution)، والتي تشكل الأساس لتقييم استعلامات Prolog.

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

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

 بناء الجملة 
يمتد بناء جملة البرمجة المنطقية ليشمل بناء جملة Datalog عن طريق إضافة استخدام رموز الوظائف (function symbols). كما تتخلى البرمجة المنطقية عن تقييد النطاق (range restriction) الموجود في Datalog، مما يسمح بظهور متغيرات في رؤوس القواعد لا تظهر في أجسامها. 

كل نموذج مستقر (stable model) هو أيضًا نموذج هيربراند أدنى (least Herbrand model). برنامج Datalog الذي لا يحتوي على نفي يمتلك نموذجًا مستقرًا واحدًا فقط، وهو بالتحديد نموذج هيربراند الأدنى الخاص به. وتُعرّف دلالات النموذج المستقر (stable model semantics) معنى برنامج منطقي يتضمن النفي بأنه نموذجه المستقر، إن وُجد. ومع ذلك، قد يكون من المفيد دراسة جميع النماذج المستقرة للبرنامج (أو على الأقل عدد منها)؛ وهذا هو الهدف الأساسي لـ برمجة مجموعة الإجابات (Answer Set Programming - ASP).

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

 بناء الجملة 
يُكتب النفي باستخدام الكلمة المفتاحية not ويمكن أن يظهر أمام أي ذرة في جسم القاعدة.<atom-list> ::= <atom> | "not" <atom> | <atom> "," <atom-list> | ""

 الدلالات 

 النفي الطبقي 
يُعتبر البرنامج المنطقي الذي يتضمن النفي طبقيًا (stratified) عندما يكون من الممكن تعيين كل علاقة (predicate) إلى طبقة معينة، بحيث إذا ظهرت علاقة R منفية (not R) في جسم قاعدة تحدد علاقة S، فإن الطبقة المخصصة لـ R تكون أقل من الطبقة المخصصة لـ S. ويمكن توسيع كل من دلالات نظرية النموذج (model-theoretic semantics) و دلالات نقطة الإصلاح (fixpoint semantics) للغة Datalog للتعامل مع النفي الطبقي، وقد تم إثبات أن هذه الامتدادات متكافئة.

تستخدم العديد من تطبيقات Datalog نموذج تقييم من الأسفل إلى الأعلى مستوحى من دلالات نقطة الإصلاح (fixpoint semantics). ونظرًا لأن هذه الدلالات قادرة على التعامل مع النفي الطبقي (stratified negation)، فإن العديد من تطبيقات Datalog تنفذ آلية النفي الطبقي.

على الرغم من أن النفي الطبقي (stratified negation) هو امتداد شائع للغة Datalog، إلا أن هناك برامج منطقية معقولة لا يمكن تقسيمها إلى طبقات. يصف البرنامج التالي لعبة بين لاعبين، حيث يفوز أحد اللاعبين إذا لم يكن لدى خصمه أي حركات متاحة:move(a, b).
win(X) :- move(X, Y), not win(Y).هذا البرنامج ليس طبقيًا (stratified)، ولكن يبدو من المعقول أن نستنتج أن a يجب أن يفوز في اللعبة.

 دلالات الإكمال 

 دلالات النموذج المثالي 

 دلالات النموذج المستقر 
تُعرّف دلالات النموذج المستقر (Stable Model Semantics) شرطًا لتحديد أي من نماذج هيربراند (Herbrand models) لبرنامج معين يمكن اعتبارها "مستقرة". وبشكل بديهي، تمثل النماذج المستقرة "مجموعات المعتقدات المتماسكة التي يمكن أن يتبناها وكيل عقلاني، بناءً على البرنامج المنطقي المقدم كفرضيات." 

قد يحتوي البرنامج المنطقي الذي يتضمن النفي على عدة نماذج مستقرة مختلفة، أو قد لا يمتلك أي نموذج مستقر على الإطلاق. على سبيل المثال، البرنامج التالي:p :- not q.
q :- not p.يحتوي على نموذجين مستقرين{ 𝑝
}،{ 𝑞}
برنامج القاعدة الواحدةp :- not p.  ليس لديه نماذج مستقرة.

كل نموذج مستقر (stable model) هو أيضًا نموذج هيربراند الأدنى (least Herbrand model). برنامج Datalog الذي لا يتضمن نفيًا يمتلك نموذجًا مستقرًا وحيدًا، وهو نفسه نموذج هيربراند الأدنى الخاص به. وتُعرّف دلالات النموذج المستقر (stable model semantics) معنى البرنامج المنطقي الذي يحتوي على نفي بأنه نموذجه المستقر، وذلك في حال وجود نموذج مستقر وحيد. ومع ذلك، قد يكون من المفيد استكشاف جميع النماذج المستقرة لبرنامج ما (أو على الأقل عدد منها)؛ وهذا هو الهدف من برمجة مجموعة الإجابات (Answer Set Programming - ASP).

.

 دلالات راسخة 

 تمديدات أخرى 
لقد تم اقتراح ودراسة العديد من التوسعات الأخرى للغة Datalog، والتي تشمل:

 المتغيرات التي تدعم الثوابت والوظائف الصحيحة (بما في ذلك <b>DatalogZ</b>). يسمح هذا التوسع بإجراء عمليات حسابية مباشرة ضمن قواعد Datalog.
 قيود عدم المساواة في أجسام القواعد. يتيح ذلك تحديد شروط يجب ألا تكون فيها قيم معينة متساوية.
 والوظائف التجميعية (Aggregate functions). تسمح هذه الوظائف بإجراء عمليات مثل العد والمتوسط والحد الأقصى والحد الأدنى على مجموعات من القيم المستنبطة.

تسمح برمجة منطق القيود (Constraint Logic Programming - CLP) بظهور قيود على مجالات معينة، مثل الأعداد الحقيقية أو الصحيحة، مباشرةً ضمن نصوص القواعد. هذا يدمج قوة البرمجة المنطقية مع قدرة حل القيود، مما يتيح التعبير عن وحل المشكلات التي تتضمن علاقات بين المتغيرات تخضع لقيود معينة.

 انظر أيضا 

 هيكل هيربراند
 البرمجة المنطقية
 النفي كفشل
 بناء الجملة والدلالات في لغة البرولوج

 مراجع 

 ملحوظات 

 مصادر 

تصنيف:برمجة منطقية
تصنيف:نحو لغات البرمجة
تصنيف:صفحات بترجمات غير مراجعة