برنامه‌نویسی مجموعه جواب

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

در مفهوم عمومی‌تر، ASP شامل همه کاربردهای مجموعه جواب در نمایش دانش است، و از ارزیابی پرسمان شبه-پرولوگ برای حل مسائلی که در این کاربردها بروز می‌کند، استفاده می‌کند.

تاریخچه 
یکی از مثال‌های اولیه برنامه‌نویسی مجموعه جواب، روش برنامه‌ریزی بود که در سال ۱۹۹۳ توسط دیموپولوس، نبل و کوهلر ارائه شد. دیدگاه آن‌ها مبتنی بر رابطه بین برنامه‌ها و مدل‌های پایدار بود. سوینینن و نیملا آنچه امروزه برنامه‌نویسی مجموعه جواب نامیده می‌شود را به مسئله پیکربندی محصول اعمال کرد. استفاده از حل‌کننده‌های مجموعه جواب برای جستجو توسط مارک و تروشسینسکی به عنوان یک پارادایم برنامه‌نویسی، اولین بار در مقاله ای که چشم‌انداز ۲۵ ساله دربارهٔ پارادایم برنامه‌نویسی منطقی در سال ۱۹۹۹ منتشر شد، و در [Niemelä 1999] شناسایی شد. در واقع اصطلاح‌شناسی جدید «مجموعه جواب» به جای «مدل پایدار» اولین بار توسط لیفشیتس در یک مقاله که نمایش دهنده مجلدهای پیش‌نگرانه در مقاله مارک-تروشچینسکی بود، پیشنهاد شد.

زبان برنامه‌نویسی مجموعه جواب AnsProlog 
Lparse نام برنامه‌ای است که در اصل به عنوان یک ابزار زمینه‌ای (front-end) برای حل‌کننده مجموعه جواب smodels ساخته شده‌است. امروزه به زبانی که Lparse می‌پذیرد، معمولاً AnsProlog گفته می‌شود، که کوته‌نوشتی برای عبارت «برنامه‌نویسی مجموعه جواب در منطق» است. از این زبان امروزه در خیلی از حل‌کننده‌های مجموعه جواب دیگر، شامل  assat, clasp, cmodels, gNt, nomore++ و pbmodels استفاده می‌شود. (اما زبان dlv یک اسثتثنا است زیرا نحو برنامه‌های ASP نوشته شده به dlv متفاوت است).

برنامه AnsProlog شامل قواعدی از حالت
<head> :- <body> .نماد :- (یعنی اگر) اگر قسمت بدنه (یعنی <body>) خالی باشد، حذف می‌شود؛ به این نوع از قواعد، «واقعیت» یا fact گفته می‌شود. ساده‌ترین نوع قواعد Lparse, قواعد محدودیت‌دار هستند.

یک ساختار مفید دیگر که در این زبان وجود دارد، مفهوم «گزینه یا choice» است. برای مثال، قاعده گزینه
{p,q,r}.می‌گوید: به صورت دلخواه انتخاب کنید که کدامیک از اتم‌های  در مدل پایدار شامل بشود. برنامه Lparse ای که شامل این قاعده انتخاب است و هیچ قاعده دیگری ندارد، به تعداد ۸ عدد مدل پایدار دارد-که زیرمجموعه‌های دلخواه  هستند. تعریف یک مدل پایدار را می‌توان به برنامه‌های دارای قواعد انتخاب تعمیم داد. قواعد گزینه می‌تواند به صورت اختصاری از کوتاه شده‌ای از فرمول‌های گزاره‌ای تحت معناشناسی مدل پایدار رفتار کنند. برای مثال، قاعده گزینه بالا را می‌توان به صورت نوع مختصری برای عطف سه فرمول «اصل طرد ثالث» در نظر گرفت:

زبان Lparse به ما امکان نوشتن قواعد گزینه «محدودشده» را نیز می‌دهد، مثل
1{p,q,r}2.این قاعده می‌گوید: حداقل یکی از اتم‌های  ، اما نه بیشتر از ۲ تا اتم را انتخاب کنید. معنای این قاعده تحت معناشناسی مدل پایدار توسط فرمول گزاره‌ای زیر نمایش می‌یابد:

محدوده‌های کاردینالیتی (تعدادی)، در بدنه یک قاعده هم قابل استفاده اند، برای مثال
:- 2{p,q,r}.اگر این محدودیت را به برنامه Lparse اضافه کنیم، مدل‌های پایداری که حداقل دو اتم  را حذف می‌کند. معنی این قاعده را می‌توان توسط توسط فرمول گزاره‌ای زیر نمایش داد:

در Lparse از متغیرها (که مثل پرولوگ بزرگ هستند) برای مختصرنویسی مجموعه قاعده‌هایی استفاده می‌شود که از الگوی مشابهی پیروی می‌کنند، همچنین برای مختصرنویسی مجموعه اتم‌ها در داخل یک قاعده مشابه نیز استفاده می‌شود. برای مثال، برنامه Lparse زیر
p(a). p(b). p(c).
q(X) :- p(X), X!=a.

معنای مشابهی با

p(a). p(b). p(c).
q(b). q(c).

دارد. برنامه زیر

p(a). p(b). p(c).
{q(X):-p(X)}2.

یک مختصرنویسی برای

p(a). p(b). p(c).
{q(a),q(b),q(c)}2.

است، یک «محدوده یا range» حالت زیر را دارد:
(start..end)
که در آن start و end عبارات حسابی ثابت مقدار هستند. یک محدوده یک میانبر نمادین است که در اصل برای تعریف دامنه‌های عددی، به روش سازگار، از آن استفاده می‌شود. برای مثال، واقعیت زیر

a(1..3).

یک میانبر برای

a(1). a(2). a(3).

است. با معناشناسی مشابه، محدوده‌ها را در بدنه قاعده نیز می‌توان استفاده نمود.

یک «لیترال شرطی» فرم زیر را دارد:

p(X):q(X)

اگر گسترش q به صورت {q(a1),q(a2), … ,q(aN)} باشد، شرط بالا به صورت معنایی معادل نوشتن {p(a1),p(a2), … ,p(aN)} در محل شرط است. برای مثال

q(1..2).
a :- 1 {p(X):q(X)}.

یک میانبر برای

q(1). q(2).
a :- 1 {p(1), p(2)}.

است.

تولید مدل‌های پایدار 
برای یافتن یک مدل پایدار برنامه Lparse که در فایل ${filename} ذخیره شده‌است، ما از فرمان زیر استفاده می‌کنیم

% lparse ${filename} | smodels

گزینه ۰ به smodels دستور می‌دهد تا «همه» مدل‌های پایدار برنامه را پیدا کند. برای مثال، اگر فایل test شامل این قواعد باشد

1{p,q,r}2.
s :- not p.

آنوقت فرمان این خروجی را می‌سازد:

% lparse test | smodels 0
Answer: 1
Stable Model: q p
Answer: 2
Stable Model: p
Answer: 3
Stable Model: r p
Answer: 4
Stable Model: q s
Answer: 5
Stable Model: r s
Answer: 6
Stable Model: r q s

مثال‌هایی از برنامه‌های ASP

رنگ‌آمیزی گراف 
رنگ‌آمیزی  تایی یک گراف  یک تابع  such that  برای هر جفت از راس‌های مجاور  است. ما می‌خواهیم از ASP استفاده کنیم تا یک رنگ‌آمیزی تایی از یک گراف داده شده را پیدا کنیم (یا تعیین کنیم که چنین رنگ‌آمیزی وجود ندارد).

این موضوع از طریق برنامه Lparse زیر قابل انجام است:

c(1..n).
1 {color(X,I) : c(I)} 1 :- v(X).
:- color(X,I), color(Y,I), e(X,Y), c(I).

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

اگر ما این فایل را با یک تعریف از  مثل تعریف زیر ترکیب کنیم:

v(1..100). % 1,...,100 are vertices
e(1,55). % there is an edge from 1 to 55
. . .

و smodels را روی آن اجرا کنیم، که مقدار عددی  در خط فرمان تعیین می‌شود، آنوقت اتم‌های دارای فرم  موجود در خروجی smodels، نمایش‌دهنده رنگ‌آمیزی تایی از  است.

برنامه موجود در این مثال نمایش‌دهنده سازمان «تولید-و-آزمون» است که معمولاً در برنامه‌های ASP ساده یافت می‌شود. قاعده گزینه یک مجموعه از «جواب‌های بالقوه» را تعریف می‌کند- که یک فرامجموعه ساده از مجموعه جواب‌ها برای مسئله جستجوی معین است. در ادامه، یک محدودیت آمده‌است، که همه جواب‌های بالقوه که قابل قبول نیستند را حذف می‌کند. با این حال، فرایند جستجوی استفاده شده در smodels و دیگر حل‌کننده‌های مجموعه جواب براساس سعی و خطا نیستند.

کلیک‌های بزرگ 
یک کلیک در یک گراف یک مجموعه از راس‌های مجاور جفت‌شده هستند. برنامه Lparse زیر یک کلیک با سایز  را در یک گراف داده شده می‌یابد، یا اعلام می‌کند که هیچ کلیکی وجود ندارد:

n {in(X) : v(X)}.
:- in(X), in(Y), v(X), v(Y), X!=Y, not e(X,Y), not e(Y,X).

این یک مثال دیگر برای سازمان «تولید و آزمون» است. قاعده گزینه در خط ۱ «تولیدکننده» همه مجموعه‌های شامل  راس است. محدودیت خط ۲، همه مجموعه‌هایی که کلیک نیستند را «هرس می‌کند».

دور همیلتونی 
یک دور همیلتونی در یک گراف جهت‌دار یک دور است که از هر راس گراف دقیقاً یکبار عبور می‌کند. برنامه Lparse زیر را می‌توان برای یافتن یک دور همیلتونی در یک گراف جهت‌دار معین استفاده کرد (اگر موجود باشد)؛ فرض می‌کنیم که ۰ یکی از راس‌ها باشد.

{in(X,Y)} :- e(X,Y).

:- 2 {in(X,Y) : e(X,Y)}, v(X).
:- 2 {in(X,Y) : e(X,Y)}, v(Y).

r(X) :- in(0,X), v(X).
r(Y) :- r(X), in(X,Y), e(X,Y).

:- not r(X), v(X).

قاعده گزینه در خط ۱ همه زیرمجموعه‌های مجموعه یال‌ها را «تولید می‌کند». سه محدودیت، زیرمجموعه‌هایی که دور همیلتونی نیستند را «هرس می‌کنند». آخرین آن‌ها از گزارهٔ کمکی  ( قابل دستیابی از ۰ است) استفاده می‌کند تا راس‌هایی که این شرط را برآورده نمی‌کنند را ممنوع‌سازی کند. این گزاره در خطوط ۶ و ۷ به صورت بازگشتی تعریف شده‌اند.

این برنامه یک مثال از سازمان کلی‌تر «تولید، تعریف، و آزمون» است: شامل تعریف یک گزاره کمکی است که به ما کمک می‌کند تا همه راه‌حل‌های بالقوه «بد» را حذف کند.

تجزیه‌کننده وابستگی 
در پردازش زبان‌های طبیعی، «تجزیه‌کننده مبتنی بر وابستگی» را می‌توان توسط یک برنامه ASP فرمول‌دهی کرد. کد زیر جمله لاتین "Puella pulchra in villa linguam latinam discit" (یعنی «دختر زیبا در ویلا زبان لاتین می‌آموزد») را تجزیه می‌کند. درخت نحوی توسط گزاره‌های «arc» بیان می‌شوند، که نمایش‌دهنده وابستگی‌های بین کلمات موجود در جمله است. ساختار محاسبه شده یک درخت ریشه‌دار با مرتبه خطی است.

% ********** input sentence **********
word(1, puella). word(2, pulchra). word(3, in). word(4, villa). word(5, linguam). word(6, latinam). word(7, discit).
% ********** lexicon **********
1{ node(X, attr(pulcher, a, fem, nom, sg));
   node(X, attr(pulcher, a, fem, abl, sg)) }1 :- word(X, pulchra).
node(X, attr(latinus, a, fem, acc, sg)) :- word(X, latinam).
1{ node(X, attr(puella, n, fem, nom, sg));
   node(X, attr(puella, n, fem, abl, sg)) }1 :- word(X, puella).
1{ node(X, attr(villa, n, fem, nom, sg));
   node(X, attr(villa, n, fem, abl, sg)) }1 :- word(X, villa).
node(X, attr(linguam, n, fem, acc, sg)) :- word(X, linguam).
node(X, attr(discere, v, pres, 3, sg)) :- word(X, discit).
node(X, attr(in, p)) :- word(X, in).
% ********** syntactic rules **********
0{ arc(X, Y, subj) }1 :- node(X, attr(_, v, _, 3, sg)), node(Y, attr(_, n, _, nom, sg)).
0{ arc(X, Y, dobj) }1 :- node(X, attr(_, v, _, 3, sg)), node(Y, attr(_, n, _, acc, sg)).
0{ arc(X, Y, attr) }1 :- node(X, attr(_, n, Gender, Case, Number)), node(Y, attr(_, a, Gender, Case, Number)).
0{ arc(X, Y, prep) }1 :- node(X, attr(_, p)), node(Y, attr(_, n, _, abl, _)), X < Y.
0{ arc(X, Y, adv) }1 :- node(X, attr(_, v, _, _, _)), node(Y, attr(_, p)), not leaf(Y).
% ********** guaranteeing the treeness of the graph **********
1{ root(X):node(X, _) }1.
:- arc(X, Z, _), arc(Y, Z, _), X != Y.
:- arc(X, Y, L1), arc(X, Y, L2), L1 != L2.
path(X, Y) :- arc(X, Y, _).
path(X, Z) :- arc(X, Y, _), path(Y, Z).
:- path(X, X).
:- root(X), node(Y, _), X != Y, not path(X, Y).
leaf(X) :- node(X, _), not arc(X, _, _).

استانداردسازی زبان و مسابقه ASP 
کارگروه استانداردسازی ASP یک مشخصات زبانی استاندارد به نام ASP-Core-2 تولید کردند، که بر اساس آن سامانه‌های ASP تازه همگرا می‌شدند. ASP-Core-2 زبان مرجع برای مسابقه برنامه‌نویسی مجموعه جواب است، که در آن حل‌کننده‌های ASP به صورت دوره‌ای، دربرابر تعدادی از مسائل مرجع، محک‌زنی می‌شدند.

مقایسه پیاده‌سازی‌ها 
سامانه‌ای قدیمی، مثل Smodels برای یافتن جواب‌ها از پس‌گرد استفاده می‌کردند. وقتیکه نظریه و کاربرد حل‌کننده‌های SAT بولی تکامل یافتند، تعدادی از حل‌کننده‌های ASP روی حل‌کننده‌های SAT ساخته شدند، که شامل ASSAT و Cmodels بودند. این حل‌کننده‌ها فرمول ASP را به گزاره‌های SAT تبدیل می‌کردند، سپس حل‌کننده SAT اعمال می‌شد، و سپس جواب‌ها را به حالت ASP باز تبدیل می‌کردند. سامانه‌های جدیدتر، مثل Clasp، از یک دیدگاه ترکیبی استفاده می‌کند، که از الگوریتم‌های مغایرت‌گرای الهام‌گرفته از SAT استفاده می‌کرد، و در آن نیازی به تبدیل کامل به یک حالت بولی-منطقی نبود. این دیدگاه‌ها به ما امکان بهبود کارایی قابل توجهی را می‌دهد، که معمولاً با یک مرتبه بزرگی بهتر از الگوریتم‌های پس‌گرد قدیمی بود.

پروژه پوتسکو (Potassco) به صورت چتری برای بسیاری از سامانه‌های زیر عمل می‌کند، که شامل clasp، سامانه‌های زیرین (gringo)، سامانه‌های افزایشی (iclingo)، حل‌کننده‌های محدودیتی (clingcon)، زبان عملی برای کامپایلرهای ASP یا (coala)، پیاده‌سازی‌های MPI توزیع‌شده (claspar) و خیلی موارد دیگر است.

بیشتر این سامانه‌ها از متغیرها پشتیبانی می‌کنند، اما فقط به صورت غیرمستقیم، با تحمیل زمینه، با استفاده از یک سامانه زمینی مثل Lparse or gringo به عنوان یک front-end. نیاز به زمینه می‌تواند منجر به یک انفجار ترکیبیاتی از بندها شود؛ از این رو سامانه‌هایی که از زمینه‌های on-the-fly استفاده می‌کنند، می‌توانند یک مزیت داشته باشند.

پیاده‌سازی‌های پرسمان‌گرا از برنامه‌نویسی مجموعه جواب، مثل سامانه Galliwasp و s(ASP) و s(CASP) از در اصل زمینه جلوگیری می‌کنند، این کار از طریق ترکیبی از رزلوشن و کواینداکشن انجام می‌شود.

پانویس

منابع 

برنامه‌نویسی منطقی