Programming Constraint Services: High-Level Programming of Standard and New Constraint Services

برنامه‌نویسی محدودیت رویکردی برای مدل‌سازی و حل مسائل ترکیبی است که در بسیاری از کاربردها موفق بوده است. این مبتنی بر تکنیک‌های توسعه‌یافته در هوش مصنوعی، برنامه‌نویسی منطقی، و تحقیقات دوره‌ها است. تکنیک های کلیدی عبارتند از انتشار محدودیت و جستجوی اکتشافی. برنامه نویسی محدودیت بر اساس یک انتزاع است که یک حل کننده مسئله را به یک موتور محدودیت قابل استفاده مجدد و یک برنامه اعلامی که مسئله را مدل می کند تجزیه می کند. موتور محدودیت الگوریتم‌های جستجو و پراکندگی مورد نیاز را پیاده‌سازی می‌کند. این می تواند به عنوان یک کتابخانه برای یک زبان برنامه نویسی با هدف عمومی (به عنوان مثال C++)، به عنوان یک توسعه دهنده یک زبان موجود (مانند Prolog)، یا به عنوان یک سیستم با زبان اختصاصی خود شناخته شود. کتاب حاضر به معماری و پیاده سازی موتورهای محدودیت می پردازد. این یک معماری جدید و همزمان ارائه می دهد که بسیار برتر از معماری متوالی زیر بنای Prolog است. معماری جدید بر اساس جستجوی همزمان با کپی و محاسبه مجدد است تا جستجوی متوالی با دنباله‌روی و عقب‌نشینی. یکی از مزایای رویکرد همزمان این است که هر استراتژی جستجو را در خود جای می دهد. علاوه بر این، اجرای الگوریتم‌های انتشار محدودیت را به‌طور قابل‌توجهی ساده می‌کند، زیرا نیاز به حسابرسی برای دنبال کردن و عقب‌نشینی را از بین می‌برد. این کتاب به بررسی تعمیم صریح معماری همزمان می‌پردازد که ترکیب‌کننده‌های حفظ کننده انتشار (معروف به ترکیب‌کننده‌های محافظ عمیق) را برای نفی، تفکیک، دلالت و بازگردانی انتشار دهنده‌های محدودیت در خود جای می‌دهد. چنین ترکیب‌کننده‌هایی فراتر از محدوده فناوری Prolog هستند. در رویکرد همزمان، آنها را می توان با یک کپسوله سازی اولیه واکنشی به دست آورد.

Constraint Programming is an approach for modeling and solving combi- torial problems that has proven successful in many applications. It builds on techniques developed in Arti?cial Intelligence, Logic Programming, and - erations Research. Key techniques are constraint propagation and heuristic search. Constraint Programming is based on an abstraction that decomposes a problem solver into a reusable constraint engine and a declarative program modeling the problem. The constraint engine implements the required pr- agation and search algorithms. It can be realized as a library for a general purpose programming language (e.g. C++), as an extension of an existing language (e.g. Prolog), or as a system with its own dedicated language. The present book is concerned with the architecture and implementation of constraint engines. It presents a new, concurrent architecture that is far superior to the sequential architecture underlying Prolog. The new archit- ture is based on concurrent search with copying and recomputation rather than sequential search with trailing and backtracking. One advantage of the concurrent approach is that it accommodates any search strategy. Furth- more, it considerably simpli?es the implementation of constraint propagation algorithms since it eliminates the need to account for trailing and backtra- ing. The book investigates an expressive generalization of the concurrent - chitecture that accommodates propagation-preserving combinators (known as deep guard combinators) for negation, disjunction, implication, and re- cation of constraint propagators. Such combinators are beyond the scope of Prolog’s technology. In the concurrent approach they can be obtained with a re?ective encapsulation primitive.