برنامه‌نویسی مجموعه جواب
برنامه‌نویسی مجموعه جواب با کوته‌نوشت ASP نوعی برنامه‌نویسی اعلانی است که به سمت مسائل جستجوی مشکل (در اصل ان‌پی سخت) گرایش دارد. ASP مبتنی بر معناشناسی مدل پایدار (مجموعه جواب) در برنامه‌نویسی منطقی است. در ASP مسائل جستجو به محاسبه مدل‌های پایدار کاهش می‌یابد، و از حل‌کننده‌های مجموعه جواب (برنامه‌های تولیدکننده مدل‌های پایدار) برای انجام جستجو استفاده می‌شود. فرایند محاسباتی استفاده شده در طراحی بسیاری از حل‌کننده‌های مجموعه جواب، نوعی بهبود الگوریتم DPLL هستند، و در اصل همیشه خاتمه می‌یابند (برخلاف ارزیابی پرسمان در پرولوگ، که می‌تواند منجر به حلقه بی‌پایان شود).
در مفهوم عمومی‌تر، ASP شامل همه کاربردهای مجموعه جواب در نمایش دانش است، و از ارزیابی پرسمان شبه-پرولوگ برای حل مسائلی که در این کاربردها بروز می‌کند، استفاده می‌کند.
یکی از مثال‌های اولیه برنامه‌نویسی مجموعه جواب، روش برنامه‌ریزی بود که در سال ۱۹۹۳ توسط دیموپولوس، نبل و کوهلر ارائه شد. دیدگاه آن‌ها مبتنی بر رابطه بین برنامه‌ها و مدل‌های پایدار بود. سوینینن و نیملا آنچه امروزه برنامه‌نویسی مجموعه جواب نامیده می‌شود را به مسئله پیکربندی محصول اعمال کرد. استفاده از حل‌کننده‌های مجموعه جواب برای جستجو توسط و تروشسینسکی به عنوان یک پارادایم برنامه‌نویسی، اولین بار در مقاله ای که چشم‌انداز ۲۵ ساله دربارهٔ پارادایم برنامه‌نویسی منطقی در سال ۱۹۹۹ منتشر شد، و در [Niemelä 1999] شناسایی شد. در واقع اصطلاح‌شناسی جدید «مجموعه جواب» به جای «مدل پایدار» اولین بار توسط لیفشیتس در یک مقاله که نمایش دهنده مجلدهای پیش‌نگرانه در مقاله مارک-تروشچینسکی بود، پیشنهاد شد.
Lparse نام برنامه‌ای است که در اصل به عنوان یک ابزار (front-end) برای حل‌کننده مجموعه جواب smodels ساخته شده‌است. امروزه به زبانی که Lparse می‌پذیرد، معمولاً AnsProlog گفته می‌شود، که کوته‌نوشتی برای عبارت «برنامه‌نویسی مجموعه جواب در منطق» است. از این زبان امروزه در خیلی از حل‌کننده‌های مجموعه جواب دیگر، شامل assat, clasp, cmodels, gNt, nomore++ و pbmodels استفاده می‌شود. (اما زبان dlv یک اسثتثنا است زیرا نحو برنامه‌های ASP نوشته شده به dlv متفاوت است).
برنامه AnsProlog شامل قواعدی از حالت
:-  . نماد codice_1 (یعنی اگر) اگر قسمت بدنه (یعنی codice_2) خالی باشد، حذف می‌شود؛ به این نوع از قواعد، «واقعیت» یا fact گفته می‌شود. ساده‌ترین نوع قواعد Lparse, هستند.
یک ساختار مفید دیگر که در این زبان وجود دارد، مفهوم «گزینه یا choice» است. برای مثال، قاعده گزینه
می‌گوید: به صورت دلخواه انتخاب کنید که کدامیک از اتم‌های formula_1 در مدل پایدار شامل بشود. برنامه Lparse ای که شامل این قاعده انتخاب است و هیچ قاعده دیگری ندارد، به تعداد ۸ عدد مدل پایدار دارد-که زیرمجموعه‌های دلخواه formula_2 هستند. تعریف یک مدل پایدار را می‌توان به برنامه‌های دارای قواعد انتخاب تعمیم داد. قواعد گزینه می‌تواند به صورت اختصاری از کوتاه شده‌ای از رفتار کنند. برای مثال، قاعده گزینه بالا را می‌توان به صورت نوع مختصری برای عطف سه فرمول «اصل طرد ثالث» در نظر گرفت: زبان Lparse به ما امکان نوشتن قواعد گزینه «محدودشده» را نیز می‌دهد، مثل
1{p,q,r}2. این قاعده می‌گوید: حداقل یکی از اتم‌های formula_1 ، اما نه بیشتر از ۲ تا اتم را انتخاب کنید. معنای این قاعده تحت معناشناسی مدل پایدار توسط زیر نمایش می‌یابد:
محدوده‌های کاردینالیتی (تعدادی)، در بدنه یک قاعده هم قابل استفاده اند، برای مثال
اگر این محدودیت را به برنامه Lparse اضافه کنیم، مدل‌های پایداری که حداقل دو اتم formula_1 را حذف می‌کند. معنی این قاعده را می‌توان توسط توسط فرمول گزاره‌ای زیر نمایش داد:
در 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). یک مختصرنویسی برای p(a). p(b). p(c). است، یک «محدوده یا range» حالت زیر را دارد:
که در آن 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 که در فایل codice_3 ذخیره شده‌است، ما از فرمان زیر استفاده می‌کنیم % lparse ${filename} | smodels گزینه 0 به smodels دستور می‌دهد تا «همه» مدل‌های پایدار برنامه را پیدا کند. برای مثال، اگر فایل codice_4 شامل این قواعد باشد 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 رنگ‌آمیزی formula_9 تایی یک گراف formula_10 یک تابع formula_11 such that formula_12 برای هر جفت از راس‌های مجاور formula_13 است. ما می‌خواهیم از ASP استفاده کنیم تا یک رنگ‌آمیزی formula_9تایی از یک گراف داده شده را پیدا کنیم (یا تعیین کنیم که چنین رنگ‌آمیزی وجود ندارد).
این موضوع از طریق برنامه Lparse زیر قابل انجام است: c(1..n). 1 {color(X,I) : c(I)} 1 :- v(X). خط ۱ تعریف کننده اعداد formula_15 به عنوان رنگ‌ها است. بر اساس قاعده انتخاب موجود در خط ۲، یک رنگ یکتا formula_16 را باید به هر راس formula_17 انتساب داد. محدودیت موجود در خط ۳ از انتساب رنگ مشابه به راس‌های formula_17 و formula_19، موقعی که یک یال آن‌ها را به هم متصل کند، جلوگیری می‌کند.
اگر ما این فایل را با یک تعریف از formula_20 مثل تعریف زیر ترکیب کنیم: v(1..100). % 1...,100 are vertices e(1,55). % there is an edge from 1 to 55
و smodels را روی آن اجرا کنیم، که مقدار عددی formula_9 در خط فرمان تعیین می‌شود، آنوقت اتم‌های دارای فرم formula_22 موجود در خروجی smodels، نمایش‌دهنده رنگ‌آمیزی formula_9تایی از formula_20 است.
برنامه موجود در این مثال نمایش‌دهنده سازمان «تولید-و-آزمون» است که معمولاً در برنامه‌های ASP ساده یافت می‌شود. قاعده گزینه یک مجموعه از «جواب‌های بالقوه» را تعریف می‌کند- که یک فرامجموعه ساده از مجموعه جواب‌ها برای مسئله جستجوی معین است. در ادامه، یک محدودیت آمده‌است، که همه جواب‌های بالقوه که قابل قبول نیستند را حذف می‌کند. با این حال، فرایند جستجوی استفاده شده در smodels و دیگر حل‌کننده‌های مجموعه جواب براساس سعی و خطا نیستند.
یک کلیک در یک گراف یک مجموعه از راس‌های مجاور جفت‌شده هستند. برنامه Lparse زیر یک کلیک با سایز formula_25 را در یک گراف داده شده می‌یابد، یا اعلام می‌کند که هیچ کلیکی وجود ندارد: n {in(X) : v(X)}. این یک مثال دیگر برای سازمان «تولید و آزمون» است. قاعده گزینه در خط ۱ «تولیدکننده» همه مجموعه‌های شامل formula_25 راس است. محدودیت خط ۲، همه مجموعه‌هایی که کلیک نیستند را «هرس می‌کند».
یک دور همیلتونی در یک گراف جهت‌دار یک دور است که از هر راس گراف دقیقاً یکبار عبور می‌کند. برنامه Lparse زیر را می‌توان برای یافتن یک دور همیلتونی در یک گراف جهت‌دار معین استفاده کرد (اگر موجود باشد)؛ فرض می‌کنیم که 0 یکی از راس‌ها باشد.
r(X) :- in(0,X), v(X). r(Y) :- r(X), in(X,Y), e(X,Y).
قاعده گزینه در خط ۱ همه زیرمجموعه‌های مجموعه یال‌ها را «تولید می‌کند». سه محدودیت، زیرمجموعه‌هایی که دور همیلتونی نیستند را «هرس می‌کنند». آخرین آن‌ها از گزارهٔ کمکی formula_27 (formula_17 قابل دستیابی از 0 است) استفاده می‌کند تا راس‌هایی که این شرط را برآورده نمی‌کنند را ممنوع‌سازی کند. این گزاره در خطوط ۶ و ۷ به صورت بازگشتی تعریف شده‌اند.
این برنامه یک مثال از سازمان کلی‌تر «تولید، تعریف، و آزمون» است: شامل تعریف یک گزاره کمکی است که به ما کمک می‌کند تا همه راه‌حل‌های بالقوه «بد» را حذف کند.
در پردازش زبان‌های طبیعی، «تجزیه‌کننده مبتنی بر وابستگی» را می‌توان توسط یک برنامه 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(latinus, a, fem, acc, sg)) :- word(X, latinam). 1{ node(X, attr(puella, n, fem, nom, sg)); 1{ node(X, attr(villa, n, fem, nom, sg)); 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. path(X, Y) :- arc(X, Y, _). path(X, Z) :- arc(X, Y, _), path(Y, Z). leaf(X) :- node(X, _), not arc(X, _, _). کارگروه استانداردسازی 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) از در اصل زمینه جلوگیری می‌کنند، این کار از طریق ترکیبی از رزلوشن و انجام می‌شود.