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

{{الگوهای برنامه‌نویسی}}
'''برنامه‌نویسی مجموعه جواب''' {{به انگلیسی|Answer set programming}} با کوته‌نوشت '''ASP''' نوعی [[برنامه‌نویسی اعلانی]] است که به سمت [[الگوریتم جستجو|مسائل جستجوی]] مشکل (در اصل [[ان‌پی سخت]]) گرایش دارد. ASP مبتنی بر [[معناشناسی مدل پایدار]] (مجموعه جواب) در [[برنامه‌نویسی منطقی]] است. در ASP مسائل جستجو به محاسبه مدل‌های پایدار کاهش می‌یابد، و از '''حل‌کننده‌های مجموعه جواب''' (برنامه‌های تولیدکننده مدل‌های پایدار) برای انجام جستجو استفاده می‌شود. فرایند محاسباتی استفاده شده در طراحی بسیاری از حل‌کننده‌های مجموعه جواب، نوعی بهبود [[الگوریتم DPLL]] هستند، و در اصل همیشه خاتمه می‌یابند (برخلاف ارزیابی پرسمان در [[پرولوگ]]، که می‌تواند منجر به [[حلقه بی‌نهایت|حلقه بی‌پایان]] شود).

در مفهوم عمومی‌تر، ASP شامل همه کاربردهای مجموعه جواب در [[بازنمود دانش|نمایش دانش]] است،<ref>{{cite book|first=Chitta|last=Baral|title=Knowledge Representation, Reasoning and Declarative Problem Solving|url=https://archive.org/details/knowledgereprese00bara|url-access=registration|year=2003|publisher=Cambridge University Press|isbn=978-0-521-81802-5}}</ref><ref>{{cite book|first=Michael|last=Gelfond|chapter=Answer sets|editor1-first=Frank|editor1-last=van Harmelen|editor2-first=Vladimir|editor2-last=Lifschitz|editor3-first=Bruce|editor3-last=Porter|title=Handbook of Knowledge Representation|chapter-url=https://books.google.com/books?id=xwBDylHhJhYC&pg=PA285|year=2008|publisher=Elsevier|isbn=978-0-08-055702-1|pages=285–316}} [http://www.depts.ttu.edu/cs/research/krlab/pdfs/papers/gel07b.pdf as PDF] {{Webarchive|url=https://web.archive.org/web/20160303231241/http://www.depts.ttu.edu/cs/research/krlab/pdfs/papers/gel07b.pdf|date=2016-03-03}}</ref> و از ارزیابی پرسمان شبه-پرولوگ برای حل مسائلی که در این کاربردها بروز می‌کند، استفاده می‌کند.

== تاریخچه ==
یکی از مثال‌های اولیه برنامه‌نویسی مجموعه جواب، روش [[زمان‌بندی و برنامه‌ریزی خودکار|برنامه‌ریزی]] بود که در سال ۱۹۹۳ توسط دیموپولوس، نبل و کوهلر<ref>{{cite book|first1=Y.|editor2-first=Rachid|volume=1348|isbn=978-3-540-63912-1|publisher=Springer|year=1997|url=https://books.google.com/books?id=QSBoQgAACAAJ|title=Recent Advances in AI Planning: 4th European Conference on Planning, ECP'97, Toulouse, France, September 24–26, 1997, Proceedings|editor2-last=Alami|editor1-last=Steel|last1=Dimopoulos|editor1-first=Sam|pages=273–285|chapter=Encoding planning problems in non-monotonic logic programs|last3=Köhler|first3=J.|last2=Nebel|first2=B.|author2-link=Bernhard Nebel|series=Lecture Notes in Computer Science: Lecture Notes in Artificial Intelligence}} [ftp://ftp.informatik.uni-freiburg.de/documents/papers/ki/dimopoulos-etal-ecp97.ps.gz as Postscript]</ref> ارائه شد. دیدگاه آن‌ها مبتنی بر رابطه بین برنامه‌ها و مدل‌های پایدار بود.<ref>{{cite book|first1=V.S.|last1=Subrahmanian|first2=C.|last2=Zaniolo|chapter=Relating stable models and AI planning domains|editor-first=Leon|editor-last=Sterling|title=Logic Programming: Proceedings of the Twelfth International Conference on Logic Programming|chapter-url=https://books.google.com/books?id=vpGEyZWP1dYC&pg=PA233|year=1995|publisher=MIT Press|isbn=978-0-262-69177-2|pages=233–247}} [http://www.cs.ucla.edu/~zaniolo/papers/iclp95.ps as Postscript]</ref> سوینینن و نیملا<ref>{{citation|first1=T.|last1=Soininen|first2=I.|last2=Niemelä|title=Formalizing configuration knowledge using rules with choices|number=TKO-B142|institution=Laboratory of Information Processing Science, Helsinki University of Technology|year=1998|url=http://www.tcs.hut.fi/~ini/papers/sn-faanmr98.ps.gz|format=Postscript}}</ref> آنچه امروزه برنامه‌نویسی مجموعه جواب نامیده می‌شود را به مسئله [[پیکربندی محصول]] اعمال کرد. استفاده از حل‌کننده‌های مجموعه جواب برای جستجو توسط [[:en:Victor_W._Marek|مارک]] و تروشسینسکی به عنوان یک [[پارادایم برنامه‌نویسی]]، اولین بار در مقاله ای که چشم‌انداز ۲۵ ساله دربارهٔ پارادایم برنامه‌نویسی منطقی در سال ۱۹۹۹ منتشر شد،<ref>{{cite book|first1=V.|last1=Marek|first2=M.|last2=Truszczyński|chapter=Stable models and an alternative logic programming paradigm|editor-first=Krzysztof R.|editor-last=Apt|title=The Logic programming paradigm: a 25-year perspective|url=https://books.google.com/books?id=GIhQAAAAMAAJ|year=1999|publisher=Springer|isbn=978-3-540-65463-6|format=PDF|pages=169–181|ref={{harvid|Apt|1999}}|arxiv=cs/9809032}}</ref> و در [Niemelä 1999]<ref>{{cite journal|last=Niemelä|first=I.|year=1999|title=Logic programs with stable model semantics as a constraint programming paradigm|url=http://users.ics.aalto.fi/ini/papers/lp-csp-long.ps.gz|format=Postscript,gzipped|journal=Annals of Mathematics and Artificial Intelligence|volume=25|issue=3/4|pages=241–273|doi=10.1023/A:1018930122475}}</ref> شناسایی شد. در واقع اصطلاح‌شناسی جدید «مجموعه جواب» به جای «مدل پایدار» اولین بار توسط لیفشیتس<ref>{{cite journal|last=Lifschitz|first=V.|year=1999|title=Action Languages, Answer Sets, and Planning}} In {{harvnb|Apt|1999|pp=357–374}}</ref> در یک مقاله که نمایش دهنده مجلدهای پیش‌نگرانه در مقاله مارک-تروشچینسکی بود، پیشنهاد شد.

== زبان برنامه‌نویسی مجموعه جواب AnsProlog ==
[http://www.tcs.hut.fi/Software/smodels/lparse.ps Lparse] نام برنامه‌ای است که در اصل به عنوان یک ابزار [[:en:Symbol_grounding_problem|زمینه‌ای]] (front-end) برای حل‌کننده مجموعه جواب [http://www.tcs.hut.fi/Software/smodels/ smodels] ساخته شده‌است. امروزه به زبانی که Lparse می‌پذیرد، معمولاً AnsProlog گفته می‌شود،<ref>{{Cite thesis|type=Ph.D.|title=Superoptimisation: Provably Optimal Code Generation using Answer Set Programming|url=http://opus.bath.ac.uk/20352/1/UnivBath_PhD_2009_T_Crick.pdf|last=Crick|first=Tom|year=2009|publisher=University of Bath|docket=20352|access-date=2011-05-27|archive-url=https://web.archive.org/web/20160304035502/http://opus.bath.ac.uk/20352/1/UnivBath_PhD_2009_T_Crick.pdf|archive-date=2016-03-04|url-status=dead}}</ref> که کوته‌نوشتی برای عبارت «برنامه‌نویسی مجموعه جواب در منطق» است.<ref>{{cite web|author=Rogelio Davila|title=AnsProlog, an overview|url=http://www.rogeliodavila.com.mx/Programacion%20Logica/PL%20Notas/AnsProlog%20Overview.ppt|format=PowerPoint}}</ref> از این زبان امروزه در خیلی از حل‌کننده‌های مجموعه جواب دیگر، شامل  [https://web.archive.org/web/20110717180541/http://assat.cs.ust.hk/ assat], [http://www.cs.uni-potsdam.de/clasp/ clasp], [http://www.cs.utexas.edu/users/tag/cmodels/ cmodels], [http://www.tcs.hut.fi/Software/gnt/ gNt], <bdi>[http://www.cs.uni-potsdam.de/nomore/ nomore++]</bdi> و [http://www.cs.uky.edu/ai/pbmodels/ pbmodels] استفاده می‌شود. (اما زبان [http://www.dbai.tuwien.ac.at/proj/dlv/ dlv] یک اسثتثنا است زیرا نحو برنامه‌های ASP نوشته شده به dlv متفاوت است).

برنامه AnsProlog شامل قواعدی از حالت
<syntaxhighlight lang="prolog">
<head> :- <body> .
</syntaxhighlight>نماد <bdi><code>:-</code></bdi> (یعنی اگر) اگر قسمت بدنه (یعنی <code><body></code>) خالی باشد، حذف می‌شود؛ به این نوع از قواعد، «واقعیت» یا fact گفته می‌شود. ساده‌ترین نوع قواعد Lparse, [[:en:Stable_model_semantics#Programs_with_constraints|قواعد محدودیت‌دار]] هستند.

یک ساختار مفید دیگر که در این زبان وجود دارد، مفهوم «گزینه یا choice» است. برای مثال، قاعده گزینه
<syntaxhighlight lang="prolog">
{p,q,r}.
</syntaxhighlight>می‌گوید: به صورت دلخواه انتخاب کنید که کدامیک از اتم‌های <math>p,q,r</math> در مدل پایدار شامل بشود. برنامه Lparse ای که شامل این قاعده انتخاب است و هیچ قاعده دیگری ندارد، به تعداد ۸ عدد مدل پایدار دارد-که زیرمجموعه‌های دلخواه <math>\{p,q,r\}</math> هستند. تعریف یک مدل پایدار را می‌توان به برنامه‌های دارای قواعد انتخاب تعمیم داد.<ref>{{cite book|first1=I.|editor3-first=Gerald|series=Lecture Notes in Computer Science: Lecture Notes in Artificial Intelligence|pages=317–331|isbn=978-3-540-66749-0|publisher=Springer|year=2000|chapter-url=https://books.google.com/books?id=Abj-OpFeDjQC&pg=PA317|title=Logic Programming and Nonmonotonic Reasoning: 5th International Conference, LPNMR '99, El Paso, Texas, USA, December 2–4, 1999 Proceedings|editor3-last=Pfeifer|editor2-last=Leone|last1=Niemelä|editor2-first=Nicole|editor1-last=Gelfond|editor1-first=Michael|chapter=Stable model semantics of weight constraint rules|last3=Soinenen|first3=T.|last2=Simons|first2=P.|volume=1730}} [http://www.tcs.hut.fi/~ini/papers/nss-lpnmr99-www.ps.gz as Postscript]</ref> قواعد گزینه می‌تواند به صورت اختصاری از کوتاه شده‌ای از [[:en:Stable_model_semantics#Stable_models_of_a_set_of_propositional_formulas|فرمول‌های گزاره‌ای تحت معناشناسی مدل پایدار]] رفتار کنند.<ref>{{cite journal|last1=Ferraris|first1=P.|last2=Lifschitz|first2=V.|date=January 2005|title=Weight constraints as nested expressions|journal=Theory and Practice of Logic Programming|volume=5|issue=1–2|pages=45–74|arxiv=cs/0312045|doi=10.1017/S1471068403001923}} [http://www.cs.utexas.edu/users/vl/papers/weight.ps as Postscript]</ref> برای مثال، قاعده گزینه بالا را می‌توان به صورت نوع مختصری برای عطف سه فرمول «[[اصل طرد ثالث]]» در نظر گرفت:
:<math>(p\lor\neg p)\land(q\lor\neg q)\land(r\lor\neg r).</math>
زبان Lparse به ما امکان نوشتن قواعد گزینه «محدودشده» را نیز می‌دهد، مثل
<syntaxhighlight lang="prolog">
1{p,q,r}2.
</syntaxhighlight>این قاعده می‌گوید: حداقل یکی از اتم‌های <math>p,q,r</math> ، اما نه بیشتر از ۲ تا اتم را انتخاب کنید. معنای این قاعده تحت معناشناسی مدل پایدار توسط [[:en:Propositional_formula|فرمول گزاره‌ای]] زیر نمایش می‌یابد:

:<math>(p\lor\neg p)\land(q\lor\neg q)\land(r\lor\neg r)</math>
::<math>\land\,(p\lor q\lor r)\land\neg(p\land q\land r).</math>
محدوده‌های کاردینالیتی (تعدادی)، در بدنه یک قاعده هم قابل استفاده اند، برای مثال
<syntaxhighlight lang="prolog">
:- 2{p,q,r}.
</syntaxhighlight>اگر این محدودیت را به برنامه Lparse اضافه کنیم، مدل‌های پایداری که حداقل دو اتم <math>p,q,r</math> را حذف می‌کند. معنی این قاعده را می‌توان توسط توسط فرمول گزاره‌ای زیر نمایش داد:

::<math>\neg((p\land q)\lor(p\land r)\lor(q\land r)).</math>
در Lparse از متغیرها (که مثل [[پرولوگ#انواع داده‌ها|پرولوگ]] بزرگ هستند) برای مختصرنویسی مجموعه قاعده‌هایی استفاده می‌شود که از الگوی مشابهی پیروی می‌کنند، همچنین برای مختصرنویسی مجموعه اتم‌ها در داخل یک قاعده مشابه نیز استفاده می‌شود. برای مثال، برنامه Lparse زیر
<syntaxhighlight lang="prolog">
p(a). p(b). p(c).
q(X) :- p(X), X!=a.
</syntaxhighlight>

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

<syntaxhighlight lang="prolog">
p(a). p(b). p(c).
q(b). q(c).
</syntaxhighlight>

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

<syntaxhighlight lang="prolog">
p(a). p(b). p(c).
{q(X):-p(X)}2.
</syntaxhighlight>

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

<syntaxhighlight lang="prolog">
p(a). p(b). p(c).
{q(a),q(b),q(c)}2.
</syntaxhighlight>

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

<syntaxhighlight lang="prolog">
a(1..3).
</syntaxhighlight>

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

<syntaxhighlight lang="prolog">
a(1). a(2). a(3).
</syntaxhighlight>

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

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

<syntaxhighlight lang="prolog">
p(X):q(X)
</syntaxhighlight>

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

<syntaxhighlight lang="prolog">
q(1..2).
a :- 1 {p(X):q(X)}.
</syntaxhighlight>

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

<syntaxhighlight lang="prolog">
q(1). q(2).
a :- 1 {p(1), p(2)}.
</syntaxhighlight>

است.

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

<syntaxhighlight lang="console">
% lparse ${filename} | smodels
</syntaxhighlight>

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

<syntaxhighlight lang="prolog">
1{p,q,r}2.
s :- not p.
</syntaxhighlight>

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

<syntaxhighlight lang="console">
% 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
</syntaxhighlight>

== مثال‌هایی از برنامه‌های ASP ==
=== رنگ‌آمیزی گراف ===
[[رنگ‌آمیزی گراف|رنگ‌آمیزی]] <math>n</math> تایی یک [[گراف (ریاضی)|گراف]] <math>G = \left\lang V, E\right\rang</math> یک تابع <math>\mathrm{color}: V\to\{1,\dots,n\}</math> such that <math>\mathrm{color}(x)\neq \mathrm{color}(y)</math> برای هر جفت از راس‌های مجاور <math>(x,y)\in E</math> است. ما می‌خواهیم از ASP استفاده کنیم تا یک رنگ‌آمیزی <math>n</math>تایی از یک گراف داده شده را پیدا کنیم (یا تعیین کنیم که چنین رنگ‌آمیزی وجود ندارد).

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

<syntaxhighlight lang="prolog" line="1">
c(1..n).
1 {color(X,I) : c(I)} 1 :- v(X).
:- color(X,I), color(Y,I), e(X,Y), c(I).
</syntaxhighlight>

خط ۱ تعریف کننده اعداد <math>1,\dots,n</math> به عنوان رنگ‌ها است. بر اساس قاعده انتخاب موجود در خط ۲، یک رنگ یکتا <math>i</math> را باید به هر راس <math>x</math> انتساب داد. محدودیت موجود در خط ۳ از انتساب رنگ مشابه به راس‌های <math>x</math> و <math>y</math>، موقعی که یک یال آن‌ها را به هم متصل کند، جلوگیری می‌کند.

اگر ما این فایل را با یک تعریف از <math>G</math> مثل تعریف زیر ترکیب کنیم:

<syntaxhighlight lang="prolog">
v(1..100). % 1,...,100 are vertices
e(1,55). % there is an edge from 1 to 55
. . .
</syntaxhighlight>

و smodels را روی آن اجرا کنیم، که مقدار عددی <math>n</math> در خط فرمان تعیین می‌شود، آنوقت اتم‌های دارای فرم <math>\mathrm{color}(\dots,\dots)</math> موجود در خروجی smodels، نمایش‌دهنده رنگ‌آمیزی <math>n</math>تایی از <math>G</math> است.

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

=== کلیک‌های بزرگ ===
یک [[کلیک (نظریه گراف)|کلیک]] در یک گراف یک مجموعه از راس‌های مجاور جفت‌شده هستند. برنامه Lparse زیر یک کلیک با سایز <math>\geq n</math> را در یک گراف داده شده می‌یابد، یا اعلام می‌کند که هیچ کلیکی وجود ندارد:

<syntaxhighlight lang="prolog" line="1">
n {in(X) : v(X)}.
:- in(X), in(Y), v(X), v(Y), X!=Y, not e(X,Y), not e(Y,X).
</syntaxhighlight>

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

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

<syntaxhighlight lang="prolog" line="1">
{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).
</syntaxhighlight>

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

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

=== تجزیه‌کننده وابستگی ===
در [[پردازش زبان‌های طبیعی]]، «[[تجزیه‌کننده|تجزیه‌کننده مبتنی بر وابستگی]]» را می‌توان توسط یک برنامه ASP فرمول‌دهی کرد.<ref>{{Cite web|url=http://loqtek.com/?id=course_pars&sec=1|title=Dependency parsing|access-date=2015-04-15|archive-url=https://archive.today/20150415155632/http://loqtek.com/?id=course_pars&sec=1|archive-date=2015-04-15|url-status=dead}}</ref> کد زیر جمله لاتین "Puella pulchra in villa linguam latinam discit" (یعنی «دختر زیبا در ویلا زبان لاتین می‌آموزد») را تجزیه می‌کند. درخت نحوی توسط گزاره‌های «arc» بیان می‌شوند، که نمایش‌دهنده وابستگی‌های بین کلمات موجود در جمله است. ساختار محاسبه شده یک درخت ریشه‌دار با مرتبه خطی است.

<syntaxhighlight lang="prolog">
% ********** 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, _, _).
</syntaxhighlight>

== استانداردسازی زبان و مسابقه ASP ==
کارگروه استانداردسازی ASP یک مشخصات زبانی استاندارد به نام ASP-Core-2 تولید کردند،<ref>{{cite web|url=https://www.mat.unical.it/aspcomp2013/files/ASP-CORE-2.03c.pdf|title=ASP-Core-2 Input Language Specification|access-date=14 May 2018}}</ref> که بر اساس آن سامانه‌های ASP تازه همگرا می‌شدند. ASP-Core-2 زبان مرجع برای مسابقه برنامه‌نویسی مجموعه جواب است، که در آن حل‌کننده‌های ASP به صورت دوره‌ای، دربرابر تعدادی از مسائل مرجع، محک‌زنی می‌شدند.

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

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

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

پیاده‌سازی‌های پرسمان‌گرا از برنامه‌نویسی مجموعه جواب، مثل سامانه Galliwasp<ref>{{cite book|first1=Kyle.|last1=Marple|first2=Gopal.|last2=Gupta|chapter=Galliwasp: A Goal-Directed Answer Set Solver|editor-first=Elvira|editor-last=Albert|title=Logic-Based Program Synthesis and Transformation, 22nd International Symposium, LOPSTR 2012, Leuven, Belgium, September 18-20, 2012, Revised Selected Papers|year=2012|publisher=Springer|pages=122-136}}</ref> و s(ASP)<ref>{{Cite journal|last=Kyle|first=Marple,|last2=Elmer|first2=Salazar,|last3=Gopal|first3=Gupta,|date=2017-09-01|title=Computing Stable Models of Normal Logic Programs Without Grounding|url=http://arxiv.org/abs/1709.00501|journal=arXiv.org|language=en}}</ref> و s(CASP)<ref>{{cite journal|last1=Arias|first1=J.|last2=Carro|first2=M.|last3=Salazar|first3=E.|last4=Marple|first4=K.|last5=Gupta|first5=G.|date=2018|title=Constraint Answer Set Programming without Grounding|journal=Theory and Practice of Logic Programming|volume=18|issue=3-4|pages=337-354}}</ref> از در اصل زمینه جلوگیری می‌کنند، این کار از طریق ترکیبی از [[رزولوشن (منطق)|رزلوشن]] و [[:en:Coinduction|کواینداکشن]] انجام می‌شود.
{{چپ‌چین}}
{| class="wikitable"
|-
! colspan="3" | Platform
! colspan="5" | Features
! colspan="1" | Mechanics
|-
! style="background:#ffdead;" | Name
! style="background:#ffdead;" | OS
! style="background:#ffdead;" | Licence
! style="background:#ffdead;" | Variables
! style="background:#ffdead;" | Function symbols
! style="background:#ffdead;" | Explicit sets
! style="background:#ffdead;" | Explicit lists
! style="background:#ffdead;" | Disjunctive (choice rules) support
!
|-
|{{rh}}|[http://www.info.univ-angers.fr/pub/claire/asperix/ ASPeRiX] {{Webarchive|url=https://web.archive.org/web/20161108121331/http://www.info.univ-angers.fr/pub/claire/asperix/ |date=۸ نوامبر ۲۰۱۶}}
|[[Linux]]
|[[GPL]]
|{{yes}}
|
|
|
|{{no}}
|on-the-fly grounding
|-
|{{rh}}|[https://web.archive.org/web/20110717180541/http://assat.cs.ust.hk/ ASSAT]
|[[Solaris (operating system)|Solaris]]
|[[Freeware]]
|
|
|
|
|
|SAT-solver based
|-
|{{rh}}|[http://www.cs.uni-potsdam.de/clasp/ Clasp Answer Set Solver]
|[[Linux]], [[macOS]], [[Microsoft Windows|Windows]]
|[[MIT License]]
|{{yes|Yes, in Clingo}}
|{{yes}}
|{{no}}
|{{no}}
|{{yes}}
|incremental, SAT-solver inspired (nogood, conflict-driven)
|-
|{{rh}}|[http://www.cs.utexas.edu/users/tag/cmodels/ Cmodels]
|[[Linux]], [[Solaris (operating system)|Solaris]]
|[[GPL]]
|{{okay|Requires grounding}}
|
|
|
|{{yes}}
|incremental, SAT-solver inspired (nogood, conflict-driven)
|-
|{{rh}}|[https://github.com/MatthiasNickles/diff-SAT/ diff-SAT]
|[[Linux]], [[macOS]], [[Microsoft Windows|Windows]] ([[Java Virtual Machine]])
|[[MIT License]]
|{{okay|Requires grounding}}
|
|
|
|{{yes}}
|SAT-solver inspired (nogood, conflict-driven). Supports solving probabilistic problems and answer set sampling
|-
|{{rh}}|[[DLV]]
|[[Linux]], [[macOS]], [[Microsoft Windows|Windows]]<ref name="dlvsystem.com">{{cite web |url=http://www.dlvsystem.com |title=DLV System company page |publisher=DLVSYSTEM s.r.l. |access-date=16 November 2011}}</ref>
|free for academic and non-commercial educational use, and for non-profit organizations<ref name="dlvsystem.com"/>
|{{yes}}
|{{yes}}
|{{no}}
|{{no}}
|{{yes}}
|not Lparse compatible
|-
|{{rh}}|[http://www.mat.unical.it/dlv-complex/ DLV-Complex]
|[[Linux]], [[macOS]], [[Microsoft Windows|Windows]]
|[[GPL]]
|
|{{yes}}
|{{yes}}
|{{yes}}
|{{yes}}
|built on top of [[DLV]] — not Lparse compatible
|-
|{{rh}}|[http://www.tcs.hut.fi/Software/gnt/ GnT]
|[[Linux]]
|[[GPL]]
|{{okay|Requires grounding}}
|
|
|
|{{yes}}
| built on top of smodels
|-
|{{rh}}|[http://www.jekejeke.ch/idatab/doclet/prod/en/docs/15_min/10_docu/02_reference/07_theory/01_minimal/06_asp.html Jekejeke] {{Webarchive|url=https://web.archive.org/web/20210603113559/http://www.jekejeke.ch/idatab/doclet/prod/en/docs/15_min/10_docu/02_reference/07_theory/01_minimal/06_asp.html |date=3 ژوئن 2021}}
|[[Linux]], [[macOS]], [[Microsoft Windows|Windows]] ([[Java Virtual Machine]])
|Proprietary
|{{yes}}
|{{yes}}
|
|
|{{yes}}
|DPLL Variant via Safe Forward Chaining
|-
|{{rh}}|[http://www.cs.uni-potsdam.de/nomore/ nomore++]
|[[Linux]]
|[[GPL]]
|
|
|
|
|
|combined literal+rule-based
|-
|{{rh}}|[http://www.cs.uni-potsdam.de/platypus/ Platypus]
|[[Linux]], [[Solaris (operating system)|Solaris]], [[Microsoft Windows|Windows]]
|[[GPL]]
|
|
|
|
|
|distributed, multi-threaded nomore++, smodels
|-
|{{rh}}|[http://www.cs.uky.edu/ai/pbmodels/ Pbmodels]
|[[Linux]]
|?
|
|
|
|
|
|[[pseudo-boolean]] solver based
|-
|{{rh}}|[http://www.tcs.hut.fi/Software/smodels/ Smodels]
|[[Linux]], [[macOS]], [[Microsoft Windows|Windows]]
|[[GPL]]
|{{okay|Requires grounding}}
|{{no}}
|{{no}}
|{{no}}
|{{no}}
|
|-
|{{rh}}|[http://www.nku.edu/~wardj1/Research/smodels_cc.html Smodels-cc]
|[[Linux]]
|?
|{{okay|Requires grounding}}
|
|
|
|
|SAT-solver based; smodels w/conflict clauses
|-
|{{rh}}|[http://www.cs.utexas.edu/users/tag/sup/ Sup]
|[[Linux]]
|?
|
|
|
|
|
|SAT-solver based
|}
{{پایان چپ‌چین}}

== پانویس ==
{{پانویس|۲}}

== منابع ==
{{یادکرد-ویکی|پیوند=https://en.wikipedia.org/wiki/Answer_set_programming|عنوان=Answer set programming|زبان=انگلیسی|بازیابی=۳ ژوئن ۲۰۲۱}}
[[رده:برنامه‌نویسی منطقی]]