سینتکس و مفاهیم پرولوگ

این مقاله در مورد معناشناسی عملیاتی است. برای معناشناسی ریاضی رسمی برنامه‌های منطقی، به سینتکس و معناشناسی برنامه‌نویسی منطقی مراجعه کنید.

سینتکس و معناشناسی prolog ، یک زبان برنامه‌نویسی، مجموعه‌ای از قوانین هستند که تعریف می‌کنند چگونه یک برنامه Prolog نوشته می‌شود و چگونه تفسیر می‌شود.

قوانین در استاندارد ISO / IEC ۱۳۲۱۱ [‏ ۱ ]‏ قرار داده شده‌اند، اگرچه تفاوت‌هایی در پیاده‌سازی Prolog وجود دارد.

انواع داده‌ها

پرولوگ بصورت پویا تایپ می‌شود. آن یک نوع داده واحد دارد، این اصطلاح، چندین نوع فرعی دارد: اتم‌ها، اعداد، متغیرها و اصطلاحات ترکیبی.

اتم یک نام عمومی بدون هیچ معنای ذاتی است. آن از یک توالی از کاراکترها تشکیل شده‌است که توسط خواننده Prolog به عنوان یک واحد تجزیه شده‌است. اتم‌ها معمولا کلماتی ساده در کد Prolog هستند که بدون ترکیب خاصی نوشته شده‌اند. با این حال، اتم‌های حاوی فضا یا شخصیت‌های خاص دیگر باید توسط نقل‌قول‌های منفرد احاطه شوند. همچنین باید از اتم‌هایی که با حرف بزرگ شروع می‌شوند، نقل‌قول کرد تا آن‌ها را از متغیرها متمایز کند. فهرست خالی، نوشته شده [‏ ]‏، نیز یک اتم است. مثال‌های دیگر اتم‌ها عبارتند از 'x، blue،' Taco و 'some atom'.

اعداد می‌توانند شناور یا اعداد صحیح باشند. بسیاری از پیاده‌سازی‌های Prolog همچنین اعداد صحیح نامحدود و اعداد منطقی را ارایه می‌دهند.

متغیرها با رشته ای متشکل از حروف، اعداد و کاراکترهای زیرخط نشان داده می شوند و با یک حرف بزرگ یا زیرخط شروع می شوند.. متغیرها از نظر منطقی به متغیر ها شباهت نزدیکی دارند زیرا برای اصطلاحات دلخواه جای دارند. یک متغیر می‌تواند از طریق یک پارچه سازی معرفی شود (‏با یک عبارت خاص برابر شود)‏. یک زیرخط (‏_)‏یک متغیر ناشناس را نشان می‌دهد و به معنای "هر اصطلاح" است. برخلاف سایر متغیرها، زیرخط نشان‌دهنده ارزش یک‌سان در هر جایی که در تعریف گزاره رخ می‌دهد نیست.

یک عبارت ترکیبی از یک اتم به نام "عمل‌کننده" و تعدادی از "استدلال‌ها یا برهان" که دوباره اصطلاح هستند تشکیل شده‌است. عبارات مرکب معمولا به عنوان یک عمل‌کننده یا تابع نوشته می‌شوند و به دنبال آن یک لیست ا از عبارات استدلالی جدا شده با کاما که در پرانتز وجود دارد، قرار می‌گیرد. تعداد استدلال‌ها "ارزش یا درجه" نامیده می‌شود. یک اتم می‌تواند به عنوان یک عبارت ترکیبی با درجه یا آریتی صفر در نظر گرفته شود.

نمونه‌هایی از عبارات مرکب عبارتند از سال کامیون (‏"مزدا"، ۱۹۸۶)‏و دوستان پرسون (‏زلدا، [تام، جیم])‏. اصطلاحات ترکیبی با تابع هایی که به عنوان عملگرها اعلام شده‌اند را می توان در پیشوند یا پسوند نوشت. برای مثال، عبارات (‏z)‏-، (‏a، b) +‏و (‏X، Y) ‏=نیز می‌توانند به ترتیب به صورت z، a + b -و X = Y نوشته شوند. کاربران می‌توانند توابع دل‌خواه را به عنوان عملگرهایی با الویت های متفاوت اعلام کنند.تا نمادهای خاص دامنه را ممکن سازد. نماد f / n معمولا برای نشان دادن یک عبارت با تابع f و arity n به کار می‌رود.

موارد خاص اصطلاحات مرکب :

لیست‌ها به صورت استقرایی تعریف می‌شوند: اتم []یک لیست است. اصطلاح ترکیبی با تابع . (‏نقطه)‏و مقدار یا آریتی۲ که آرگومان دوم آن یک لیست است، خود یک لیست است. دستور خاصی برای نشان دادن لیست‌ها وجود دارد: (‏A، B)‏. معادل [ ‏ A|B ]‏ است. برای مثال، این لیست.(1, .(2, .(3, []))) همچنین میتواند به عنوان [1 | [2 | [3 | []]]] یا حتی فشرده تر به عنوان [1,2,3] نوشت.

رشته‌ها: دنباله‌ای از کاراکترها که با نقل قول احاطه شده اند ، معادل با فهرستی از کدهای کاراکتری (‏عددی)‏است که معمولا در کدگذاری کارا کترهای محلی یا یونی‌کد در صورتی که سیستم از یونی‌کد پشتیبانی کند، وجود دارد.

برنامه‌های پرولوگ(prolog)

برنامه‌های prolog ، روابطی را توصیف میکند که با استفاده از بندها تعریف می شوند . Pure Prologبه بند هورن، زیر مجموعه کامل تورینگ از منطق گزاره مرتبه اول محدود می‌شود. دو نوع بند وجود دارد: حقایق و قوانین. یک قانون به شکل زیر است:

Head :- Body.

و به این صورت خوانده می‌شود که "اگر body درست باشد، head درست است". بدنه یک قانون شامل فراخوان‌هایی برای پیش‌بینی است که اهداف قانون نامیده می‌شوند. گزاره داخلی ,/2 ، (‏به معنای یک عملگر دو آریتی با نام،)‏نشان‌دهنده اهداف، و ;/2 نشان‌دهنده انفصال یا تفکیک است. حروف ربط و منفصل فقط در body ظاهر می شوند، نه در head یا راس یک قاعده. جملاتی که بدن های خالی دارند، واقعیت نامیده می شوند.مثالی از یک واقعیت این است:

cat(tom).

که معادل قاعده است:

cat(tom) :- true.

مثال دیگر:

X is 3+2.

و هنگامی که آن را اجرا کنید، نتیجه خواهد بود:

X=5
 Yes.

گزاره داخلی true/0 همیشه درست است.

ارزیابی

اجرای یک برنامه Prolog با ارسال یک هدف توسط کاربر به نام query آغاز می‌شود. به طور منطقی، موتور Prolog تلاش می‌کند تا یک رد قطعنامه برای پرس و جوی رد شده پیدا کند. روش تفکیک مورد استفاده توسط Prolog، رزولوشن SLD نامیده می‌شود. اگر پرسوجوی منفی را بتوان رد کرد، نتیجه این است که پرسوجو، با پیوندهای متغیر مناسب، یک نتیجه منطقی از برنامه است. در این حالت، تمام پیوندهای متغیر تولید شده به کاربر گزارش می‌شوند و گفته می‌شود که پرس و جو موفق بوده‌است. از نظر عملیاتی، استراتژی اجرای prolog را می‌توان به عنوان تعمیمی از فراخوانی‌های تابع در زبان‌های دیگر در نظر گرفت، یکی از این تفاوت‌ها این است که سربندهای چندگانه می‌توانند با یک فراخوانی‌ معین مطابقت داشته باشند. در این حالت، سیستم یک نقطه انتخاب ایجاد می‌کند، هدف را با سر بند گزینه اول یکسان می‌کند، و با اهداف اولین جایگزین ادامه می‌یابد. اگر هر هدفی در طول اجرای برنامه شکست بخورد، تمام اتصالات متغیری که از زمان ایجاد آخرین نقطه انتخاب ایجاد شده‌اند، لغو می شوند و اجرا با جایگزین بعدی آن نقطه انتخاب ادامه می‌یابد. این استراتژی اجرا، عقبگرد زمانی نامیده می‌شود.

mother_child(trude, sally).
 
father_child(tom, sally).
father_child(tom, erica).
father_child(mike, tom).
 
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).
Yes

این مورد به صورت زیر به دست می‌آید: در ابتدا، تنها انطباق بند - هد برای خواهر و برادر پرسوجو (‏یعنی، اریکا)‏اولین مورد است، بنابراین اثبات پرسوجو برابر با اثبات بدنه آن بند با پیوندهای متغیر مناسب در مکان است، یعنی حرف ربط (‏والد - فرزند (Z,سالی )‏، والد - فرزند (Z,اریکا ))‏. هدف بعدی که باید اثبات شود چپ‌ترین هدف از این پیوند است، یعنی والد - فرزند (‏Z,سالی)‏. دو سر بند با این هدف مطابقت دارند. این سیستم یک نقطه انتخاب ایجاد می‌کند و اولین جایگزین را امتحان می‌کند که بدن آن پدر - فرزند است. این هدف را می توان با استفاده از پدر - فرزند (‏تام، سالی)‏اثبات کرد، بنابراین پیوند Z = تام تولید می‌شود، و هدف بعدی که باید اثبات شود بخش دوم رابطه بالا است: والد - فرزند (‏تام، اریکا)‏. باز هم، این موضوع را می توان با واقعیت مربوطه اثبات کرد. از آنجا که همه اهداف را می توان اثبات کرد، پرس و جو موفق می‌شود. از آنجا که پرس و جو حاوی هیچ متغیری نبود، هیچ پیوندی به کاربر گزارش نشده است. یک پرس و جو با متغیرهایی مانند:

?- father_child(Father, Child).

تمام پاسخ‌های معتبر در مورد بازخورد را برمی شمارد.

توجه داشته باشید که با کدی که در بالا ذکر شده ، پرس و جو؟ .(sibling(sally, sally-?

نیز موفق می‌شود. در صورت تمایل می توان اهداف اضافی را برای توصیف محدودیت های مربوطه درج کرد.

حلقه ها و بازگشت

الگوریتم های تکراری را می توان با استفاده از گزاره‌های بازگشتی اجرا کرد. سیستم‌های پرولوگ معمولا یک تکنیک بهینه‌سازی معروف به نام بهینه‌سازی تماس دنباله (‏TCO)‏را برای پیش‌بینی‌های قطعی که بازگشت دنباله را نشان می‌دهند یا، به طور کلی‌تر، فراخوانی دنباله را اجرا می‌کنند: یک چارچوب پشته قبل از انجام فراخوانی در موقعیت دنباله کنار گذاشته می‌شود. بنابراین، گزاره‌های بازگشتی قطعی با فضای پشته ثابت، مانند حلقه‌های در زبان‌های دیگر اجرا می‌شوند.

برش

برش (!) در داخل یک قاعده مانع از بازگشتprolog از هرگونه پیش بینی در پشت برش می شود:

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

اگر اولین مقدار یافت شده X که یک (X) درست است، منجر به نادرست بودن دو (X) شود، شکست خواهد خورد.

متغیرهای ناشناس

متغیرهای ناشناس _ هرگز به یک مقدار محدود نمی‌شوند و می‌توانند چندین بار در یک گزاره مورد استفاده قرار گیرند.

برای مثال جستجوی یک لیست برای یک مقدار مشخص:

contains(V, [V|_]).
contains(V, [_|T]) :- contains(V, T).

نفی

گزاره پرولوگ ساخته‌شده \+/1 ، نفی را به عنوان شکست فراهم می‌کند، که استدلال غیر یکنواخت را امکان پذیر می‌سازد. هدف \+ غیرقانونی(X) در قانون

legal(X) :- \+ illegal(X).

به صورت زیر ارزیابی می‌شود: به صورت زیر ارزیابی می شود: Prolog تلاش می کند تا غیرقانونی (X) را اثبات کند. اگر مدرکی برای اثبات این هدف یافت شود، هدف اصلی (‏یعنی + غیرقانونی (‏X)‏)‏با شکست مواجه می‌شود. اگر هیچ مدرکی پیدا نشود، هدف اصلی موفق می‌شود. بنابراین عملگر پیشوند \+ / ۱ عملگر "قابل‌اثبات" نامیده می‌شود ، زیرا عبارت ?- \+ Goal است. اگر هدف قابل اثبات نباشد موفق می شود. این نوع نفی درست است اگر استدلال آن "پایه" باشد (‏یعنی شامل هیچ متغیری نیست)‏. اگر آرگومان دارای متغیر باشد، صحت ازبین می رود. 0به طور خاص، پرس و جو ?- قانونی (X). اکنون نمی توان برای برشمردن همه چیزهایی که قانونی هستند استفاده کرد

مفاهیم

تحت یک مطالعه خبری، ترتیب قواعد و اهداف درون قواعد، بی‌ربط است، زیرا تفکیک منطقی و پیوستگی، جابجایی پذیر هستند. با این حال، در طول مسیر، اغلب مهم است که استراتژی اجرای پرولوگ را در نظر بگیریم، یا به دلایل کارایی، ویا به دلیل معنایی بودن گزاره‌های ناخالص داخلی که ترتیب ارزیابی برای آن‌ها اهمیت دارد. همچنین، همانطور که مفسرهای پرولوگ تلاش می‌کنند تا عبارات را به ترتیبی که ارایه می‌شوند یکسان کنند، عدم ارایه ترتیب صحیح می‌تواند منجر به بازگشت نامحدود شود، مانند:

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

با توجه به این دستور ,هر پرس و جو از فرم

?- predicate1(atom).

تا زمانی که پشته تمام شود تکرار می شود. با این حال، اگر 3 خط آخر به:

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

همان پرس و جو در مدت زمان بسیار کوتاهی منجر به یک نتیجه شماره می شود.

گرامرهای جملات معین

نماد خاصی به نام گرامرهای بند معین (DCG)ها وجود دارد. یک قانون تعریف‌شده از طریق - ->/2 به جای: - / ۲ توسط پیش پردازنده گسترش می‌یابد (expand _ term/2، تسهیلاتی مشابه ماکروها در زبان های دیگر) مطابق با چند قانون بازنویسی ساده، گسترش می یابد که منجر به ایجاد بندهای Prolog معمولی می شود . از همه مهم‌تر، بازنویسی، گزاره را با دو آرگومان اضافی مجهز می‌کند، که می‌تواند به طور ضمنی حالت را به هم متصل کند، مشابه مونادها در زبان‌های دیگر. DCG ها اغلب برای نوشتن تجزیه‌کننده‌ها یامولد های لیست مورد استفاده قرار می‌گیرند، چرا که یک رابط مناسب برای لیست کردن تفاوت‌ها فراهم می‌کنند.

نمونه تجزیه کننده

یک مثال بزرگ‌تر پتانسیل استفاده از Prolog در تجزیه را نشان می‌دهد.

با توجه به جمله‌ای که در قالب بک - نئور بیان شد:

<sentence>    ::=  <stat_part>
<stat_part>   ::=  <statement> | <stat_part> <statement>
<statement>   ::=  <id> = <expression> ;
<expression>  ::=  <operand> | <expression> <operator> <operand>
<operand>     ::=  <id> | <digit>
<id>          ::=  a | b
<digit>       ::=  0..9
<operator>    ::=  + | - | *

این را می توان در Prolog با استفاده از DCG ها نوشت، که مربوط به یک تجزیه‌ کننده پیش‌بینی‌ با یک نگاه به جلو است:

sentence(S)                --> statement(S0), sentence_r(S0, S).
sentence_r(S, S)           --> [].
sentence_r(S0, seq(S0, S)) --> statement(S1), sentence_r(S1, S).
 
statement(assign(Id,E)) --> id(Id), [=], expression(E), [;].
 
expression(E) --> term(T), expression_r(T, E).
expression_r(E, E)  --> [].
expression_r(E0, E) --> [+], term(T), expression_r(plus(E0,T), E).
expression_r(E0, E) --> [-], term(T), expression_r(minus(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].

این کد رابطه بین یک جمله (‏که به عنوان یک لیست از نشانه ها داده می‌شود)‏و درخت نحوی انتزاعی(AST) آن را تعریف می‌کند. مثال پرس و جوی:

?- 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))) ;

AST با استفاده از اصطلاحات Prolog نمایش داده می شود و می تواند برای اعمال بهینه سازی ها، کامپایل چنین عباراتی در کد ماشین یا تفسیر مستقیم چنین عباراتی استفاده شود. همانطور که برای ماهیت رابطه‌ای محمول‌ها معمول است، این تعاریف را می‌توان هم برای تجزیه و تولید جملات و هم برای بررسی اینکه آیا یک درخت معین با فهرست معینی از نشانه‌ها مطابقت دارد استفاده کرد. . با استفاده از روش عمیق سازی تکراری برای شمارش منصفانه، هر جمله دل‌خواه اما ثابت و AST متناظر آن در نهایت به دست می‌آید:

?- length(Tokens, _), phrase(sentence(AST), Tokens).
 Tokens = [a, =, a, (;)], AST = assign(a, id(a)) ;
 Tokens = [a, =, b, (;)], AST = assign(a, id(b))
 etc.

همچنین ببینید

مقایسه پیاده سازی های Prolog

منابع

^ISO/IEC 13211: Information technology — Programming languages — Prolog. International Organization for Standardization, Geneva


دسته بندی ها:دستور زبان برنامه نویسی \| خانواده زبان های برنامه نویسی Prolog