Кіріспе

Қатар шектеулер логикалық бағдарламалау тілі

Constraint Handling Rules (CHR) – 1991 жылы Том Фрювирттің (сол кезде Еуропалық компьютерлік индустрия зерттеу орталығы (ECRC) Мюнхенде жұмыс істеген) енгізген декларативтік, ережелерге негізделген бағдарламалау тілі. Бастапқыда шектеулерді бағдарламалау үшін жасалған CHR, грамматикалық индукция, типтік жүйелер, абдуктивті қорытынды, көп агенттік жүйелер, табиғи тілді өңдеу, компиляция, жоспарлау, кеңістіктік-уақыттық қорытынды, сынақтан өткізу және тексеру салаларында қолданылады. CHR бағдарламасы, кейде шектеулерді өңдеуші деп аталады, – логикалық формулалардың көп жиынтығын қамтитын шектеулерді сақтау жиынтығы. Ережелерді орындау формулаларды қосу немесе алып тастау арқылы сақтаудың күйін өзгертеді. Белгілі бір шектеулер жиынында ережелердің "іске қосылу" реті абстрактілі семантикасына сәйкес детерминистік емес, ал нақтыланған семантикасына сәйкес детерминистік (жоғарыдан төменге ережелерді қолдану) болады. CHR Тьюринг толық болғанымен, ол жеке бағдарламалау тілі ретінде кеңінен қолданылмайды. Керісінше, ол хост тілін шектеулермен кеңейту үшін қолданылады. Prolog – ең танымал хост тілі және CHR бірнеше Prolog нұсқаларына кіреді, оның ішінде SICStus және SWI Prolog, сонымен қатар CHR нұсқалары Haskell, Java, C, SQL және JavaScript үшін де бар. Prolog-тан айырмашылығы, CHR ережелері көп бағытты және алға тізбектеу алгоритмін қолдана отырып, міндетті таңдау әдісімен орындалады.

Тілдер туралы жалпы түсінік

CHR бағдарламаларының нақты синтаксисі хост тіліне байланысты, және шын мәнінде бағдарламалар кейбір ережелерді өңдеу үшін орындалатын хост тіліндегі операторларды кіріктіреді. Хост тілі логикалық айнымалыларды қоса алғанда, терминдерді ұсыну үшін дерек құрылымын қамтамасыз етеді. Терминдер бағдарламаның проблемалық домені туралы «фактілер» ретінде қарастырылатын шектеулерді көрсетеді. Дәстүрлі түрде Prolog хост тілі ретінде қолданылады, сондықтан оның дерек құрылымдары мен айнымалылары пайдаланылады. Осы бөлімнің қалған бөлігі КХР әдебиетінде кең таралған бейтарап, математикалық нотацияны қолданады. Сонда CHR бағдарламасы шектеулер қоймасы деп аталатын осы терминдердің көп жиынтығын манипуляциялайтын ережелерден тұрады. Ережелер үш түрлі болады: бірақ көптеген жағдайларда LEAPS деп аталатын жалқау алгоритм қолданылады. CHR семантикасының бастапқы спецификациясы толығымен детерминистік емес еді, бірақ Duck және тағы басқалардың «жетілдірілген операциялық семантикасы» детерминизмнің көп бөлігін жойды, бұл қолданба жазушыларға өз бағдарламаларының орындалу реті мен дұрыстығына сенуге мүмкіндік береді. КХР-дың көптеген қолданыстары қайта жазу процесінің конfluentті болуын қажет етеді; әйтпесе, қанағаттандырарлық тапсырманы іздеудің нәтижелері детерминистік емес және болжауға келмейтін болады. Конfluentтілікті орнату әдетте келесі үш қасиет арқылы жүзеге асырылады: CHR бағдарламасы жергілікті конfluentті болып есептеледі, егер оның барлық маңызды жұптары біріктірілсе. Егер шексіз есептеулер болмаса, CHR бағдарламасы тоқтатылатын болады. Тоқтатылатын CHR бағдарламасы барлық маңызды жұптары біріктірілсе, конfluentті болып табылады.