پرولوگ

تاریخچه

این زبان برای اولین بار در اوایل ۱۹۷۰ توسط گروهی به سرپرستی «آلن کلمرار» در مارسی فرانسه به وجود آمد و اولین سیستم Prolog در سال ۱۹۷۲ توسط کلمرار و فیلیپ راسل توسعه داده شد. با این حال، دیوید اچ دی وارن با ایجاد ماشین خلاصه وارن در اوایل کامپایلر Prolog با نفوذ را نوشت و «Edinburgh Prolog» را تعریف نمود که گویشی است که اساس برای نحو بسیاری از پیاده‌سازی مدرن است. Prolog یکی از زبان‌های برنامه‌نویسی منطق مرتبه اول بود، و امروزه رایج‌ترین این گونه زبان‌ها باقی مانده‌است، همراه با تعداد زیادی از پیاده‌سازی‌های آن که به صورت رایگان و تجاری در دسترس هستند. در حالی که در ابتدا با هدف پردازش زبان طبیعی ساخته شد اما به تدریج بخاطر استفاده و پشتیبانی سیستم‌های خبره، بازی‌ها، سیستم پاسخ خودکار، ontologies و سیستم‌های کنترل پیچیده، تغییر کرد و محیط‌های Prolog مدرن و با حمایت از ایجاد واسط کاربر گرافیکی، به عنوان برنامه‌های اداری و شبکه.. معرفی گردید و الحاقات بعدی از Prolog که توسط تیم اصلی ایجاد گشت محدودیت توانایی در منطق برنامه‌نویسی را در پیاده‌سازی از بین بردند.

زمزمه‌های ایجاد یک زبان منطق گرا از دهه ۷۰ میلادی از شمال آمریکا شکل گرفت. بعداً در نسل پنجم رایانه‌ها نیز از پرولوگ برای نوشتن کرنل سیستم‌عامل نیز در ایجاد پروژه سیستم FGCS استفاده شد.

ماژول‌ها

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

برنامه‌نویسی در پرولوگ

برنامه پرلوگ مجموعه‌ای از روابط است که توسط بندهای خاص تعریف شده‌اند. این بندها محدود به بندهای horn و تورینگ است که زیر مجموعه کاملی از منطق منظور اول است (first-order predicate logic). بندها به دو دستهٔ قوانین و حقیقت‌ها تقسیم می‌شوند. یک مثال از قانون:
Head :- Body. سر: -- بدن است.
سر یک عضوی از بدن است؛ و بعد با پرس و جوهای انجام شده با توجه به قوانین موجود و حقایق اولیه نتایج ثانویه که حقایق جدیدی هستند شکل می‌گیرد. پرس و جوها می‌توانند براساس لیست‌های پیوندی نیز باشد و طبق قوانین از پیش تعیین شده نتایجی را در اختیار کاربر گذاشت. مثل اندازه لیست. عنصر آخر لیست و ... . به همین خاطر مجموعه‌ای از کتابخانه‌های این زبان شکل گرفته‌است و در راستای آن هم دستورهایی برای چاپ داده‌ها و امثال آن شکل گرفته‌است.

بررسی

بررسی ابتدا با یک پرس و جو شروع می‌شود و با توجه به حقایق موجود که درست یا غلط است نتیجه منتقل می‌شود. اساس کار بدین گونه است که به‌دنبال اولین غلط یا تکذیب مسئله می‌یابد و با توجه به نوع مسئله در صورت نیافتن آن همین روال را برای دیگر داده‌ها نیز انجام می‌دهد و در صورت حصول نتیجه حقیقت داده‌های قبلی به صورت بازگشتی معلوم می‌گردد. با این استراتژی که Backtracking نیز گفته می‌شود اساس یافت جواب در زبان پرلوگ اطلاق می‌شود. به‌طور مثال:
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
طبق قانون وقتی دونفر خواهر و برادرند که والدین آن‌ها یکی باشد پس زبان به دنبال والدین می‌گردد و آن‌ها را برمی‌گرداند و جواب را به جای گزاره‌های مذکور می‌گذارد و طبق قانون اگر دو گزاره یکی باشند درست برمی‌گرداند. پس روش کلی روشی بازگشتی اثبات بندهاست و جایگزینی نتایج آنها.

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

الگوریتم‌های Iterative (پشت سرهمی) می‌توانید به وسیلهٔ predicates بازگشتی به اجرا درآیند. سیستم‌های Prolog معمولاً به روش بهینه‌سازی معروفی به نام تماس دم (tco) پایبندند که ملتزم به بازگشت قطعی است و حتماً در این روش بهینه‌سازی می‌بایست به دم برسد. به همین خاطر در روش بازگشتی از یک پشته با یک نوع محدودیت بهره می‌گیرد و بدین وسیله می‌تواند حلقه‌های متعدد و بازگشتی را با اطمینان به بازگشت به جواب را جوابگو باشد.

خنثی‌سازی

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

ملاحظات عملیاتی

یکسری قوانینی تعبیه شده‌است که در آن کاربر با استفاده از آن می‌تواند از ایجاد لوپ‌های تودرتو جلوگیری کند؛ و البته با نظم دادن به دستورها می‌توان از ایجاد آن‌ها جلوگیری کرد به‌طور مثال:
predicate1(X) :-
predicate2(X,X).
predicate2(X,Y) :-
predicate1(X),
X \= Y.
برای پرسش
?- predicate1(atom).
ایجاد یک حلقه بی‌نهایت توسط کاربر می‌کند ولی اگر دستورها را این‌گونه نظم دهیم چنین اتفاقی نمی‌افتد
predicate2(X,Y) :-
X \= Y,
predicate1(X).

تجزیه

یک نماد ویژه‌به نام گرامرهای قطعی (DCGs) وجود دارد. یک قاعده تعریف شده به عنوان -> به جای -: که با استفاده از آن می‌توان به تجزیه کردن و ایجاد یک رابط مناسب برای یک لیست بکار گرفت. DCG‌ها اغلب برای نوشتن پارسرها یا ژنراتورهای لیست استفاده می‌شوند، زیرا آن‌ها همچنین یک رابط کاربری مناسب برای لیست‌های متفاوت فراهم می‌کنند. در زیر یک مثال از این مورد را می‌بینید:
<sentence> ::= <stat_part>
<stat_part> ::= <statement> | <stat_part> <statement>
<statement> ::= <id> = <expression> ;
<expression> ::= <operand> | <expression> <operator> <operand>
<operand> ::= <id> | <digit>
<id> ::= a | b
<digit> ::= ۰..۹
<operator> ::= + | - | *

و با استفاده از 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].

برنامه‌نویسی سفارشی

یکی دیگر امکاناتی که در پرلوگ با توجه به ماهیت آن به وجود آمده‌است برنامه‌نویسی سفارشی است. با توجه به روند BachTracking و روش بهینه‌سازی بازگشت قطعی می‌توانیم حالاتی را ایجاد کنیم که از آن طریق برنامه به‌طور خودکار و تنها با داشتن یک قاعده ساده به دنبال جواب در یک لیست پیوندی بگردد. به‌طور مثال شمارش اعداد و پیدا کردن اعداد اول.
 perfect(N) :-
 between(1, inf, N), U is N // 2,
 findall(D, (between(1,U,D), N mod D =:= 0), Ds),
 sumlist(Ds, N).

متا - مترجم و انعکاس

prolog یک زبان homoiconic  است و بسیاری از امکانات را برای انعکاس را در اختیار ما می‌گذارد. این زبان امکان نوشتن meta-circular evaluator را نیز فراهم می‌سازد که اغلب از آن به عنوان متا- مترجم یاد می‌شود. به دلیل آنکه برنامه‌های به زبان پرلوگ دنباله‌ای از اصطلاحات خود این زبان است، خواندن آن راحت و مکانیزم ساده ایی جهت ترجمه را دارا است.

روش‌های پیاده‌سازی

برای بهره‌وری از کد Prolog معمولاً به صورت کد ماشین انتزاعی ترجمه می‌شود و اغلب تحت تأثیر مجموعه دستورهای ثبت نامی براساس ماشین انتزاعی وارن (Warren Abstract Machine (WAM)) است. برای پیاده‌سازی انتزاعی متناسب به نوع اصطلاحات و اطلاعات در زمان کامپایل است. برای ترجمه بهتر و نزدیک تر بودن به زبان ماشین واقعی برای عملکرد بهتر نیاز به تحقیقات مبتنی بر جامعه منطقی برنامه‌ریزی شده‌است که دو کار اساسی براساس قواعد منطقی انجام می‌دهد یک باینری کردن عبارات و بندها و دیگری فراهم کردن پشته مبتنی بر ماشین مجازی. در نسل پنجم سعی شده‌است ماشین‌ها و سیستم‌های مبتنی بر پرلوگ نیازهای سخت‌افزاری این نوع برنامه‌سازی منطقی را نیز فراهم سازند تا سرعت اجرای آن هزاران برابر شود. به‌علاوه این پرلوگ این توانایی را نیز دارد که با پردازش موازی بندها سرعت را بهبود بخشد.

استفاده در صنعت

Prolog در Watson مورد استفاده قرار گرفته‌است. Watson از نرم افزار DeepQA IBM و  Apache UIMA استفاده می‌کند. این سیستم در زبان‌های مختلف نوشته شده بود، از جمله Java، C ++ و Prolog . این زبان برای تطبیق الگو با درختان تجزیه طبیعی استفاده می‌شود.توسعه دهندگان اظهار داشتند: "ما نیاز به یک زبان داشتیم که می‌توانستیم به راحتی قوانین تطبیق الگوی بر روی درختان تجزیه و سایر حاشیه نویسی‌ها (مانند نتایج نامفهوم نامیده شده) را بیان کنیم و یک تکنولوژی که بتواند این قوانین را بسیار مؤثر اجرا کند. توسعه دهندگان اظهار داشتند: "ما نیاز به یک زبان داشتیم که می‌توانستیم به راحتی قوانین تطبیق الگوی بر روی درختان تجزیه و سایر حاشیه نویسی‌ها (مانند نتایج نامفهوم نامیده شده) را بیان کنیم و یک تکنولوژی که بتواند این قوانین را بسیار مؤثر اجرا کند.

مثال‌ها

در اینجا مثال‌هایی از برنامه ساخته شده به زبان پرلوگ را می‌بینیم.

الگوریتم مرتب‌سازی سریع

partition([], _, [], []).
 partition([X|Xs], Pivot, Smalls, Bigs) :-
 (X @<Pivot ->
  Smalls = [X|Rest],
  partition(Xs, Pivot, Rest, Bigs)
 ; Bigs = [X|Rest],
  partition(Xs, Pivot, Smalls, Rest)).

 quicksort([]) --> [].
 quicksort([X|Xs]) -->
 { partition(Xs, X, Smaller, Bigger) },
 quicksort(Smaller), [X], quicksort(Bigger).

ماشین تورینگ

turing(Tape0, Tape) :-
perform(q0, [], Ls, Tape0, Rs),
reverse(Ls, Ls1),
append(Ls1, Rs, Tape).
perform(qf, Ls, Ls, Rs, Rs) :- !.
perform(Q0, Ls0, Ls, Rs0, Rs) :-
symbol(Rs0, Sym, RsRest),
once(rule(Q0, Sym, Q1, NewSym, Action)),
action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
perform(Q1, Ls1, Ls, Rs1, Rs).
symbol([], b, []).
symbol([Sym|Rs], Sym, Rs).
action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs).
action(stay, Ls, Ls, Rs, Rs).
action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs).
left([], [], Rs0, [b|Rs0]).
left([L|Ls], Ls, Rs, [L|Rs]).
مثالی ساده از برنامه پیاده‌سازی ماشین تورینگ
 rule(q0, 1, q0, 1, right).
 rule(q0, b, qf, 1, stay).

 ?- turing([1,1،1], Ts).
 Ts = [1, 1, 1, 1] ;

برنامه‌نویسی پویا

برنامه Prolog زیر از برنامه‌نویسی پویا برای یافتن توالی مشترک طولانی از دو فهرست در زمان چند جمل‌های استفاده می‌کند : پایگاه داده بند برای memoization استفاده شده‌است:
:- dynamic(stored/1).
memo(Goal) :- (stored(Goal) -> true ; Goal, assertz(stored(Goal))).
lcs([], _, []) :- !.
lcs(_, [], []) :- !.
lcs([X|Xs], [X|Ys], [X|Ls]) :- !, memo(lcs(Xs, Ys, Ls)).
lcs([X|Xs], [Y|Ys], Ls) :-
memo(lcs([X|Xs], Ys, Ls1)), memo(lcs(Xs, [Y|Ys], Ls2)),
length(Ls1, L1), length(Ls2, L2),
(L1>= L2 -> Ls = Ls1 ; Ls = Ls2).
مثال پرس و جو
?- lcs([x,m،j,y،a,u،z], [m,z،j,a،w,x،u], Ls).
Ls = [m, j, a, u]

ضمیمه‌ها

درحال حاضر تلاش در راستای توسعه این زبان برای گسترش قابلیت‌های برنامه‌سازی در جهات مختلف صورت می‌گیرد که این قابلیت‌ها عبارتند از محدودیت‌های برنامه‌نویسی منطقی (CLP)(بیشتر در تنظیمات صنعتی مانند جدول‌های زمان‌بندی)، برنامه‌نویسی شی گرای منطقی (OOLP)، همزمانی، منطق خطی و قابلیت همکاری با پایگاه‌های دانش. بدین منظور نسخه‌هایی همچون نمونه‌های زیر تهیه شده‌است:
HiLog و λProlog تمدید Prolog با بالاتربردن ویژگی‌های برنامه‌نویسی سفارشی.
اف منطق گسترش Prolog با قاب / اشیاء را برای نمایش دانش.
OW Prolog ایجاد شده‌است به منظور پاسخ به عدم Prolog است از گرافیک و رابط.
Logtalk یک شیء گرا منطق زبان برنامه‌نویسی است (بهمراه ایجاد خاصیت چندریختی و وراثت و همچنین چند نخی و همزمانی)
Prolog - MPI یک منبع باز SWI - Prolog می‌باشد که برای محاسبات توزیع شده از طریق واسط پیام‌رسان اینکار را انجام می‌دهد.
Oblog کوچک، قابل حمل، شیء گرا را به فرمت - Prolog توسط McDougall مارگارت از EdCAAD، دانشگاه ادینبورگ است.

Prolog Gnu چیست؟

gnu Prolog (همچنین به نام gprolog) یک کامپایلرکد باز توسط دانیل دیاز با یک اشکال زدایی محیط تعاملی برای Prolog در دسترس در یونیکس و ویندوز می‌باشد. همچنین پشتیبانی از برخی از الحاقات را به Prolog از جمله محدودیت‌های برنامه‌نویسی بیش از یک دامنه محدود، با استفاده از تجزیه grammars بند تصریح شده، و یک سیستم‌عامل و رابط را داراست.
کامپایلر تبدیل کد منبع را تبدیل به بایت کد می‌کند که می‌تواند توسط یک دستگاه مترجم یا مفسر وارون انتزاعی آن را به کد اجرایی رایج تبدیل کند.