بناء الجملة ودلالات لغة برولوج

تُعرَّف قواعد بناء الجملة ودلالات لغة البرمجة برولوج بأنها مجموعة القواعد التي تُحدد كيفية كتابة برنامج برولوج وكيفية تفسيره، على التوالي. وقد وُضِّحت هذه القواعد في معيار ISO/IEC 13211 ^{[ 1 ]} ، مع وجود اختلافات بين تطبيقات برولوج المختلفة .

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

الذرة اسم عام لا يحمل معنىً جوهريًا. تتكون من سلسلة من الأحرف يحللها قارئ لغة برولوج كوحدة واحدة. عادةً ما تكون الذرات كلمات مجردة في كود برولوج، تُكتب بدون قواعد نحوية خاصة. مع ذلك، يجب وضع الذرات التي تحتوي على مسافات أو أحرف خاصة أخرى بين علامتي اقتباس مفردتين. كما يجب وضع الذرات التي تبدأ بحرف كبير بين علامتي اقتباس لتمييزها عن المتغيرات. القائمة الفارغة، المكتوبة ،[] هي أيضًا ذرة. من الأمثلة الأخرى على الذرات x: ، blue، 'Taco'، و 'some atom'.

يمكن أن تكون الأرقام أعدادًا عشرية أو أعدادًا صحيحة . كما توفر العديد من تطبيقات لغة برولوج أعدادًا صحيحة غير محدودة وأعدادًا نسبية .

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

يتكون الحد المركب من عنصر أساسي يُسمى "دالة" وعدد من "الوسائط"، وهي بدورها حدود. تُكتب الحدود المركبة عادةً على شكل دالة متبوعة بقائمة من الوسائط مفصولة بفواصل، ومُضمنة بين قوسين. يُسمى عدد الوسائط "معامل الحد" . يمكن اعتبار العنصر الأساسي حدًا مركبًا بمعامل يساوي صفرًا.

من أمثلة الحدود المركبة truck_year('Mazda', 1986)و 'Person_Friends'(zelda,[tom,jim]). يمكن كتابة الحدود المركبة التي تحتوي على دوال مُعرَّفة كعوامل باستخدام تدوين البادئة أو التدوين الوسطي. على سبيل المثال، يمكن كتابة الحدود و و على التوالي كـ -(z)و +(a,b)و . يمكن للمستخدمين تعريف دوال عشوائية كعوامل ذات أسبقية مختلفة للسماح باستخدام تدوينات خاصة بالمجال. يُستخدم التدوين f/n عادةً للدلالة على حد ذي دالة f وعدد معاملات n .=(X,Y)-za+bX=Y

حالات خاصة من المصطلحات المركبة:

• تُعرَّف القوائم[] استقرائيًا: الذرة هي قائمة. المصطلح المركب ذو الدالة .(نقطة) وعدد المعاملات 2، والذي يكون وسيطه الثاني قائمة، هو نفسه قائمة. توجد صيغة خاصة للدلالة على القوائم: .(A, B)تُكافئ . على سبيل المثال، يمكن كتابة [A|B]القائمة أيضًا على النحو التالي : ، أو بشكل أكثر اختصارًا على النحو التالي : ..(1, .(2, .(3, [])))[1 | [2 | [3 | []]]][1,2,3]
• السلاسل النصية : سلسلة من الأحرف محاطة بعلامات اقتباس تعادل قائمة من رموز الأحرف (الرقمية)، وعادة ما تكون في ترميز الأحرف المحلي أو Unicode إذا كان النظام يدعم Unicode.

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

الرأس :- الجسم .

وتُقرأ على النحو التالي: "يكون الرأس صحيحًا إذا كان الجسم صحيحًا". يتكون جسم القاعدة من استدعاءات للمسندات، والتي تُسمى أهداف القاعدة. يُشير المسند المُدمج ,/2(أي عامل ثنائي المعاملات يحمل اسمًا ,) إلى ربط الأهداف، بينما ;/2يُشير إلى الفصل . لا يمكن أن تظهر عمليات الربط والفصل إلا في جسم القاعدة، وليس في رأسها.

تُسمى الجمل التي لا تحتوي على عبارات حقائق . ومن أمثلة الحقائق:

قط ( ذكر ).

وهو ما يعادل القاعدة التالية:

cat ( tom ) :- صحيح .

مثال آخر هو:

س = 3 + 2.

وعند تشغيله، ستكون النتيجة

X = 5 نعم .

تكون المسندة المضمنة true/0صحيحة دائمًا.

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

mother_child ( trude , sally ).الأب والابن ( توم ، سالي ). الأب والابن ( توم ، إريكا ). الأب والابن ( مايك ، توم ).sibling ( X , Y ) :- parent_child ( Z , X ), parent_child ( Z , Y ).parent_child ( X , Y ) :- father_child ( X , Y ). parent_child ( X , Y ) :- mother_child ( X , Y ).

وينتج عن ذلك تقييم الاستعلام التالي على أنه صحيح:

؟- شقيق ( سالي ، إريكا ). نعم

يتم ذلك على النحو التالي: في البداية، يكون رأس العبارة الوحيد المطابق للاستعلام sibling(sally, erica)هو الأول، لذا فإن إثبات الاستعلام يُعادل إثبات جسم تلك العبارة مع وجود روابط المتغيرات المناسبة، أي العطف (parent_child(Z,sally), parent_child(Z,erica)). الهدف التالي الذي يجب إثباته هو الهدف الأيسر من هذا العطف، أي parent_child(Z, sally). يتطابق رأسا عبارتين مع هذا الهدف. يُنشئ النظام نقطة اختيار ويُجرّب البديل الأول، الذي جسمه هو father_child(Z, sally). يمكن إثبات هذا الهدف باستخدام الحقيقة father_child(tom, sally)، لذا يتم إنشاء الرابط Z = tom، والهدف التالي الذي يجب إثباته هو الجزء الثاني من العطف أعلاه: parent_child(tom, erica). مرة أخرى، يمكن إثبات هذا بواسطة الحقيقة المقابلة. بما أنه يمكن إثبات جميع الأهداف، ينجح الاستعلام. بما أن الاستعلام لا يحتوي على متغيرات، فلا يتم الإبلاغ عن أي روابط للمستخدم. استعلام يحتوي على متغيرات، مثل:

?- father_child ( Father , Child ).

يسرد جميع الإجابات الصحيحة عند التراجع.

لاحظ أنه باستخدام الكود المذكور أعلاه، ?- sibling(sally, sally).ينجح الاستعلام أيضًا. ويمكن إضافة أهداف إضافية لوصف القيود ذات الصلة، إذا لزم الأمر.

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

سيؤدي استخدام دالة القطع ( ) !داخل القاعدة إلى منع لغة برولوج من التراجع عن أي مسندات خلف القطع:

predicate ( X ) :- one ( X ), !, two ( X ).

سيفشل إذا كانت القيمة الأولى التي تم العثور عليها Xوالتي one(X)تكون صحيحة تؤدي إلى two(X)كونها خاطئة.

المتغيرات المجهولة _لا ترتبط أبدًا بقيمة ويمكن استخدامها عدة مرات في الشرط.

على سبيل المثال، البحث في قائمة عن قيمة معينة:

يحتوي على ( V ، [ V | _ ]). يحتوي على ( V ، [ _ | T ]) :- يحتوي على ( V ، T ).

\+/1تُتيح خاصية Prolog المُدمجة النفي كفشل ، مما يسمح بالاستدلال غير الرتيب . الهدف \+ illegal(X)في القاعدة

قانوني ( X ) :- \+ غير قانوني ( X ).

يُقيّم هذا الاستثناء كما يلي: يحاول برولوج إثبات الهدف illegal(X). إذا وُجد برهان لهذا الهدف، \+ illegal(X)يفشل الهدف الأصلي (أي، ). إذا لم يُعثر على برهان، ينجح الهدف الأصلي. لذلك، \+/1يُسمى عامل البادئة عامل "غير قابل للإثبات"، لأن الاستعلام ?- \+ Goal.ينجح إذا كان الهدف غير قابل للإثبات. يكون هذا النوع من النفي سليمًا إذا كانت وسيطته "أساسية" (أي لا تحتوي على متغيرات). يفقد هذا النوع من النفي سلامته إذا احتوت الوسيطة على متغيرات. على وجه الخصوص، لا يمكن استخدام الاستعلام ?- legal(X).الآن لحصر جميع الأشياء المسموح بها.

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

predicate1 ( X ) :- predicate2 ( X , X ). predicate2 ( X , Y ) :- predicate1 ( X ), X \= Y .

بناءً على هذا الترتيب، فإن أي استعلام من هذا النوع

?- predicate1 ( atom ).

سيتكرر هذا حتى ينفد المكدس. أما إذا تم تغيير الأسطر الثلاثة الأخيرة إلى:

predicate2 ( X , Y ) :- X \= Y , predicate1 ( X ).

سيؤدي نفس الاستعلام إلى نتيجة "لا" في وقت قصير جدًا.

توجد صيغة خاصة تُسمى قواعد الجمل المحددة ( DCGs ). تُوسّع القاعدة المُعرّفة باستخدام -->/2بدلاً من بواسطة المُعالج المُسبق ( وهو مُساعدة تُشابه وحدات الماكرو في لغات أخرى) وفقًا لبعض قواعد إعادة الكتابة البسيطة، مما ينتج عنه جمل برولوج عادية. والأهم من ذلك، أن إعادة الكتابة تُزوّد ​​المُسند بوسيطين إضافيين، يُمكن استخدامهما لربط الحالة ضمنيًا، على غرار المونادات في لغات أخرى. تُستخدم قواعد الجمل المحددة غالبًا لكتابة المُحللات أو مُولّدات القوائم، لأنها تُوفّر أيضًا واجهة مُلائمة لفروق القوائم.:-/2expand_term/2

< جملة > ::= < جزء إحصائي > < جزء إحصائي > ::= < عبارة > | < جزء إحصائي > < عبارة > < عبارة > ::= < معرف > = < تعبير > ; < تعبير > ::= < معامل > | < تعبير > < عامل > < معامل > < معامل > ::= < معرف > | < رقم > < معرف > ::= a | b < رقم > ::= 0..9 < عامل > ::= + | - | * 

الجملة ( S ) --> العبارة ( S0 )، جملة_r ( S0 ، S ). جملة_r ( S ، S ) --> []. جملة_r ( S0 ، seq ( S0 ، S )) --> العبارة ( S1 )، جملة_r ( S1 ، S ).statement ( assign ( Id , E )) --> id ( Id ), [ = ], expression ( E ), [;].التعبير ( E ) --> الحد ( T )، التعبير_r ( T ، E ). التعبير_r ( E ، E ) --> []. التعبير_r ( E0 ، E ) --> [ + ]، الحد ( T )، التعبير_r ( + ( E0 ، T )، E ). التعبير_r ( E0 ، E ) --> [ - ]، الحد ( T )، التعبير_r ( - ( E0 ، T )، E ).term ( T ) --> factor ( F ), term_r ( F , T ). term_r ( T , T ) --> []. term_r ( T0 , T ) --> [ * ], factor ( F ), term_r ( times ( T0 , F ), T ).factor ( id ( ID )) --> id ( ID ). factor ( digit ( D )) --> [ D ], { ( number ( D ) ; var ( D )), between ( 0 , 9 , D )}.id ( a ) --> [ a ]. id ( b ) --> [ b ].

?- phrase ( sentence ( AST ), [ a , = , 1 , + , 3 , * , b ,;, b , = , 0 ,;]). AST = seq ( assign ( a , plus ( digit ( 1 ), times ( digit ( 3 ), id ( b )))), assign ( b , digit ( 0 ))) ;

?- طول ( الرموز ، _ )، عبارة ( جملة ( شجرة بناء الجملة المجردة )، الرموز ). الرموز = [ أ ، = ، أ ، (;)]، شجرة بناء الجملة المجردة = تعيين ( أ ، معرف ( أ )) ؛ الرموز = [ أ ، = ، ب ، (;)]، شجرة بناء الجملة المجردة = تعيين ( أ ، معرف ( ب )) إلخ .

• مقارنة تطبيقات لغة برولوج