الصياغة والدلالات في البرمجة المنطقية
المحتويات
بدايةً، البرمجة المنطقية هي نموذج برمجة يعتمد على لغات تستند إلى المنطق الرسمي، وتشمل من بينها Datalogو Prolog. وتتناول هذه المقالة بناء الجملة ودلالات المجموعة الفرعية الإعلانية البحتة من هذه اللغات. ومن الجدير بالذكر أن اسم "البرمجة المنطقية" يُستعمل كذلك للإشارة إلى لغة برمجة محددة تتوافق بدرجة كبيرة مع المجموعة الفرعية التصريحية من Prolog، مما قد يسبب بعض الالتباس. ولسوء الحظ، سيتعين استخدام هذا المصطلح بكلا المعنيين في هذه المقالة. وفيما يلي تفاصيل أوسع عن ذلك.
من جهة ثانية، تضيف الكثير من تطبيقات Datalog و برولوغواللغات ذات الصلة ميزات إجرائية مثل عامل القطع في برولوغ أو ميزات غير منطقية مثل واجهة وظيفة أجنبية. إن الدلالات الرسمية لمثل هذه الامتدادات تقع خارج نطاق هذه المقالة.
إضافةً إلى ذلك، المعنى هو "إذا كان كل حد في جسم القاعدة (Bi) صحيحًا، إذن فإن رأس القاعدة (H) يكون صحيحًا". تقوم برامج البرمجة المنطقية بحساب مجموعة الحقائق التي تستلزمها قواعدها.
وفي السياق ذاته، تتكون برامج المنطق التصريحي بالكامل من قواعد من النموذجH :- B1, ..., BN.حيث يمكن قراءة كل قاعدة من هذه القواعد باعتبارها نتيجة ضمنية:
النفي
الدلالات
ومن جهة أخرى، تتمتع البرمجة المنطقية (التي لا تتضمن النفي) بالخاصية المرغوبة المتمثلة في اتفاق التعريفات الثلاثة الرئيسية لدلالات البرامج المنطقية (دلالات نظرية النموذج، ودلالات نقطة الإصلاح، ودلالات نظرية الإثبات). في المقابل، هناك الكثير من المقترحات المتضاربة فيما يتعلق بدلالات البرامج المنطقية التي تتضمن النفي. ويكمن مصدر هذا الخلاف في أن البرامج المنطقية الخالية من النفي لها نموذج هيربراند الأدنى الفريد، ولكن بشكل عام، لا تمتلك برامج البرمجة المنطقية (أو حتى Datalog) التي تتضمن النفي مثل هذا النموذج الفريد.
بناء الجملة
تمديدات أخرى
في هذا الإطار، لقد تم اقتراح ودراسة الكثير من التوسعات الأخرى للغة Datalog، والتي تشمل:
وفي السياق ذاته، المتغيرات التي تدعم الثوابت والوظائف الصحيحة (بما في ذلك DatalogZ). يسمح هذا التوسع بإجراء عمليات حسابية مباشرة ضمن قواعد Datalog.
ومن جهة أخرى، تسمح برمجة منطق القيود (Constraint Logic Programming - CLP) بظهور قيود على مجالات معينة، مثل الأعداد الحقيقية أو الصحيحة، مباشرةً ضمن نصوص القواعد. هذا يدمج قوة البرمجة المنطقية مع قدرة حل القيود، مما يتيح التعبير عن وحل المشكلات التي تتضمن علاقات بين المتغيرات تخضع لقيود معينة.
في هذا الإطار، والوظائف التجميعية (Aggregate functions). تسمح هذه الوظائف بإجراء عمليات مثل العد والمتوسط والحد الأقصى والحد الأدنى على مجموعات من القيم المستنبطة.
وعلى صعيد آخر، قيود عدم المساواة في أجسام القواعد. يتيح ذلك تحديد شروط يجب ألا تكون فيها قيم معينة متساوية.
- انظر كذلك
- هيكل هيربراند
- البرمجة المنطقية
- النفي كفشل
- بناء الجملة والدلالات في لغة البرولوج
- مراجع
- ملحوظات
النموذج النظري
مثلًا، هذا البرنامج:edge(x, y).
R 2بثوابت معينة.
ومن جهة أخرى، تُسمى القاعدة أرضية (ground) إذا كانت جميع ذراتها (الرأس والجسم) أرضية - أي لا تحتوي على أي متغيرات. وتُعتبر القاعدة الأرضية R1 مثالًا أساسيًا (ground instance) لقاعدة أخرى R 2 إذا كانت R 1 هي نتيجة استبدال جميع المتغيرات الموجودة في
وفي هذا الصدد، نموذج برنامج Datalog P هو تفسير للبرنامج P الذي يحتوي على جميع الحقائق الأساسية الموجودة في P، ويجعل جميع قواعد P صحيحة في . وتنص دلالات نظرية النموذج(Model-theoretic semantics) على أن معنى برنامج Datalog هو نموذجه الأدنى (least model) (أو تقاطع جميع نماذجه).
edge(y, z).
وفي السياق ذاته، قاعدة هيربراند ( Herbrand base) لبرنامج Datalog هي مجموعة جميع الذرات الأرضية (الذرات التي لا تحتوي على متغيرات) التي يمكن إنشاؤها باستخدام الثوابت التي تظهر في البرنامج. ويُعرف التفسير (interpretation) كذلك باسم مثيل قاعدة البيانات (database instance) وهو عبارة عن مجموعة فرعية من قاعدة هيربراند. وتكون الذرة الأساسية صحيحة في التفسير إذا كانت عنصرًا من . وتكون القاعدة صحيحة في التفسير إذا كان لكل مثال أساسي لتلك القاعدة، فإنه عندما تكون جميع الذرات في جسم القاعدة صحيحة في ، فإن رأس القاعدة يكون صحيحًا كذلك في .
path(A, B) :-
path(A, C) :-
edge(A, B).
path(A, B),
edge(B, C).
في هذا الإطار، وهذه هي قاعدة هيربراند: 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)
هل يوجد هذا الكون هيربراند : x ، y ، z
path(A, B) :-
path(A, C) :-
edge(A, B).
بناء الجملة
ومن جهة أخرى، كل نموذج مستقر (stable model) هو كذلك نموذج هيربراند أدنى (least Herbrand model). برنامج Datalog الذي لا يحتوي على نفي يمتلك نموذجًا مستقرًا واحدًا فقط، وهو بالتحديد نموذج هيربراند الأدنى الخاص به. وتُعرّف دلالات النموذج المستقر (stable model semantics) معنى برنامج منطقي يتضمن النفي بأنه نموذجه المستقر، إن وُجد. ومع ذلك، قد يكون من المفيد دراسة جميع النماذج المستقرة للبرنامج (أو على الأقل عدد منها)؛ وهذا هو الهدف الأساسي لـ برمجة مجموعة الإجابات (Answer Set Programming - ASP).
وفي هذا السياق، يمتد بناء جملة البرمجة المنطقية ليشمل بناء جملة Datalog عن طريق إضافة استخدام رموز الوظائف (function symbols). كما تتخلى البرمجة المنطقية عن تقييد النطاق (range restriction) الموجود في Datalog، مما يسمح بظهور متغيرات في رؤوس القواعد لا تظهر في أجسامها.
إثبات نظري
إضافةً إلى ذلك، بالنسبة لقاعدة في P تُعرّف دلالات نظرية الإثبات (Proof-theoretic semantics) معنى برنامج Datalog بأنه مجموعة الذرات الأساسية التي يمكن استنتاجها من مثل هذه الأشجار. وتتوافق هذه المجموعة تحديدًا مع نموذج هيربراند الأدنى (least Herbrand model).
وفي السياق ذاته، بالنظر إلى برنامج P، فإن شجرة إثبات (proof tree) للذرة الأرضية A هي شجرة ذات جذر مُسمى بـ A، وأوراق مُسماة بذرات أرضية تمثل رؤوس الحقائق في P، وفروع ذات أطفال A1,...,An مُصنفة بواسطة ذرات أرضية G بحيث توجد حالة أرضية لقاعدة في P يكون رأسها A وجسمها
كذلك، قد يكون المرء مهتمًا بمعرفة ما إذا كانت ذرة أرضية معينة تنتمي إلى نموذج هيربراند الأدنى (least Herbrand model) لبرنامج Datalog أم لا، ربما دون الحاجة إلى حساب النموذج بأكمله. وتشير القراءة من أعلى إلى أسفل لأشجار الإثبات الموضحة سابقًا إلى خوارزمية لحساب نتائج مثل هذه الاستعلامات، وهذه القراءة تحديدًا تزودنا بخوارزمية حل SLD (SLD-resolution)، والتي تشكل الأساس لتقييم استعلامات Prolog.
G :- A 1, ... , A n .
مثال
edge(y, z).
علاوةً على ذلك، حيث انهو يقوم البرنامج التالي بحساب path العلاقة، وهو الإغلاق المتعدي edge العلاقة.edge(x, y).
}،{ 𝑞}
.
دلالات راسخة
برنامج القاعدة الواحدةp :- not p. ليس لديه نماذج مستقرة.
وعلى صعيد آخر، كل نموذج مستقر (stable model) هو كذلك نموذج هيربراند الأدنى (least Herbrand model). برنامج Datalog الذي لا يتضمن نفيًا يمتلك نموذجًا مستقرًا وحيدًا، وهو نفسه نموذج هيربراند الأدنى الخاص به. وتُعرّف دلالات النموذج المستقر (stable model semantics) معنى البرنامج المنطقي الذي يحتوي على نفي بأنه نموذجه المستقر، وذلك في حال وجود نموذج مستقر وحيد. ومع ذلك، قد يكون من المفيد استكشاف جميع النماذج المستقرة لبرنامج ما (أو على الأقل عدد منها)؛ وهذا هو الهدف من برمجة مجموعة الإجابات (Answer Set Programming - ASP).
البرمجة المنطقية
وفي هذا الصدد، في حين أن اسم "البرمجة المنطقية" يُستعمل للإشارة إلى النموذج الكامل للغات البرمجة بما في ذلك Datalog و Prolog، فإنه عند مناقشة الدلالات الرسمية، يشير عمومًا إلى امتداد Datalog يتضمن رموز الوظائف (function symbols). وتُسمى البرامج المنطقية كذلك جمل هورن (Horn clauses). وترتبط البرمجة المنطقية كما نوقشت في هذه المقالة ارتباطًا وثيقًا بالمجموعة الفرعية "الخالصة" أو التصريحية من Prolog.
السكر النحوي
علاوةً على ذلك، توسع الكثير من تطبيقات البرمجة المنطقية القواعد النحوية المذكورة أعلاه للسماح بكتابة الحقائق بدون :-، مثل:r(x) :- . يسمح الكثير من تطبيقات Datalog كذلك بكتابة العلاقات الصفرية (0-ary relations) بدون أقواس، مثل هذا:p :- q.هذه مجرد اختصارات نحوية (syntactic sugar) سكر نحوي؛ وليس لها أي تأثير على دلالات البرنامج.
طرق أخرى
وفي هذا الصدد، عمومية.مممممم تمت دراسة دلالات Datalog كذلك في سياق نقاط التثبيت على الحلقات شبه الدائرية (semirings) الأكثر عمومية. يوفر هذا التوجه إطارًا جبريًا لدراسة دلالات Datalog، حيث يتم استبدال القيم المنطقية (صحيح/خاطئ) بعناصر من الحلقة شبه الدائرية، وعمليات الاتحاد والتقاطع بعمليات الجمع والضرب في الحلقة شبه الدائرية على التوالي. يتيح هذا التعميم نمذجة مفاهيم إضافية مثل التكلفة أو الاحتمالية ضمن قواعد Datalog.
سجل البيانات
في هذا الإطار، Datalog هي أبسط لغات البرمجة المنطقية التي حظيت بدراسة واسعة. وهناك ثلاثة تعريفات رئيسية لدلالات Datalog، وهي كلها متكافئة. أما بناء الجملة ودلالات لغات البرمجة المنطقية الأخرى فهي عبارة عن امتدادات وتعميمات لتلك الخاصة بلغة Datalog.
دلالات النموذج المستقر
q :- not p.يحتوي على نموذجين مستقرين{ 𝑝
من جهة ثانية، قد يحتوي البرنامج المنطقي الذي يتضمن النفي على عدة نماذج مستقرة مختلفة، أو قد لا يمتلك أي نموذج مستقر على الإطلاق. مثلًا، البرنامج التالي:p :- not q.
وفي هذا السياق، تُعرّف دلالات النموذج المستقر (Stable Model Semantics) شرطًا لتحديد أي من نماذج هيربراند (Herbrand models) لبرنامج معين يمكن اعتبارها "مستقرة". وبشكل بديهي، تمثل النماذج المستقرة "مجموعات المعتقدات المتماسكة التي يمكن أن يتبناها وكيل عقلاني، بناءً على البرنامج المنطقي المقدم كفرضيات."
path(A, B),
edge(B, C).
بناء الجملة
إضافةً إلى ذلك، ::= | "," | "" تُعرف الذرات كذلك باسم الحدودية (literals). وتُسمى الذرة الموجودة على يسار الرمز :- رأس القاعدة (head)؛ أما الذرات الموجودة على اليمين فتُسمى جسم القاعدة (body). ويجب أن يستوفي كل برنامج Datalog الشرط الذي ينص على أن كل متغير يظهر في رأس القاعدة يجب أن يظهر كذلك في جسم القاعدة (يُطلق على هذا الشرط أحيانًا اسم تقييد النطاق (range restriction))
إضافةً إلى ذلك، يتكون برنامج Datalog من قائمة من القواعد (جمل هورن). إذا كانت C و V مجموعتين قابلتين للعد من الثوابت والمتغيرات على التوالي، وكانت R عبارة عن مجموعة قابلة للعد من رموز المسند، فإن قواعد BNF التالية تعبر عن بنية برنامج Datalog: ::= | ""
::= ":-" "."
وفي هذا الصدد، تُسمى القواعد ذات الأجسام الفارغة حقائق (facts). مثلًا، القاعدة التالية هي حقيقة:r(x) :- .
::= "(" ")"
النفي الطبقي
كذلك، win(X) :- move(X, Y), not win(Y).هذا البرنامج ليس طبقيًا (stratified)، ولكن يبدو من المعقول أن نستنتج أن a يجب أن يفوز في اللعبة.
دلالات النموذج المثالي
كذلك، تستعمل الكثير من تطبيقات Datalog نموذج تقييم من الأسفل إلى الأعلى مستوحى من دلالات نقطة الإصلاح (fixpoint semantics). ونظرًا لأن هذه الدلالات قادرة على التعامل مع النفي الطبقي (stratified negation)، فإن الكثير من تطبيقات Datalog تنفذ آلية النفي الطبقي.
ومن ناحية أخرى، على الرغم من أن النفي الطبقي (stratified negation) هو امتداد شائع للغة Datalog، إلا أن هناك برامج منطقية معقولة لا يمكن تقسيمها إلى طبقات. يصف البرنامج التالي لعبة بين لاعبين، حيث يفوز أحد اللاعبين إذا لم يكن لدى خصمه أي حركات متاحة:move(a, b).
دلالات الإكمال
وفي هذا السياق، يُعتبر البرنامج المنطقي الذي يتضمن النفي طبقيًا (stratified) عندما يكون من الممكن تعيين كل علاقة (predicate) إلى طبقة معينة، بحيث إذا ظهرت علاقة R منفية (not R) في جسم قاعدة تحدد علاقة S، فإن الطبقة المخصصة لـ R تكون أقل من الطبقة المخصصة لـ S. ويمكن توسيع كل من دلالات نظرية النموذج (model-theoretic semantics) و دلالات نقطة الإصلاح (fixpoint semantics) للغة Datalog للتعامل مع النفي الطبقي، وقد تم إثبات أن هذه الامتدادات متكافئة.
الدلالات
وفي هذا السياق، هناك ثلاثة أساليب مستعملة على نطاق واسع لدلالات برامج Datalog: النظرية النموذجية ، والنقطة الثابتة ، والنظرية الإثباتية . يمكن إثبات أن هذه الأساليب الثلاثة متكافئة.
في هذا الإطار، تُسمى الذرة أرضية (ground) إذا لم يكن أي من مصطلحاتها الفرعية متغيرًا. وبشكل بديهي، تحدد كل الدلالات معنى البرنامج المنطقي (الذي لا يتضمن النفي) على أنه مجموعة جميع الذرات الأساسية التي يمكن استنتاجها من قواعد البرنامج، بدءًا من الحقائق.
نقطة ثابتة
ومن جهة أخرى، ليكن I مجموعة جميع التفسيرات لبرنامج Datalog P، أي، حيث H هي قاعدة هيربراند لـ P و P هو مشغل مجموعة القوى (power set operator). مشغل النتائج المباشرة (immediate consequence operator) لـ P هو الخريطة التالية TP من I إلى I: لكل مثال أرضي لكل قاعدة في P، إذا كانت كل جملة في جسم القاعدة موجودة في تفسير الإدخال، فقم بإضافة رأس المثال الأرضي إلى تفسير الإخراج. هذه الخريطة TP رتيبة فيما يتعلق بالترتيب الجزئي المعطى من خلال تضمين المجموعة الفرعية (⊆) على I. وبحسب نظرية كناستر-تارسكي (Knaster-Tarski theorem)، تحتوي هذه الخريطة على أقل نقطة ثابتة؛ وبحسب نظرية كليين للنقطة الثابتة، (Kleene fixpoint theorem)، فإن أقل نقطة ثابتة هي الحد الأعلى للسلسلة: TP(∅),TP,...إن أقل نقطة ثابتة لـ TP تتطابق مع نموذج هيربراند الأدنى (least Herbrand model) للبرنامج P.
علاوةً على ذلك، تشير دلالات نقطة الإصلاح (Fixpoint semantics) إلى خوارزمية لحساب نموذج هيربراند الأدنى (least Herbrand model): ابدأ بمجموعة الحقائق الأساسية الموجودة في البرنامج، ثم أضف بشكل متكرر جميع العواقب التي يمكن استنتاجها من تطبيق القواعد حتى يتم الوصول إلى نقطة الإصلاح (حيث لا يمكن إضافة المزيد من الحقائق). تُسمى هذه الخوارزمية بالتقييم الساذج (naive evaluation).
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟