Extension and Optimising Compilation of Constraint Handling Rules (Uitbreiding en optimaliserende compilatie van constraint handling rules)
Author:
Abstract:
Constraint Handling Rules (CHR) is een hoog-niveau declaratieve programm eertaal gebaseerd op meerhoofdige multiset-herschrijfregels, gecombineer d met aspecten uit logische en constraint-gebaseerde programmeertalen. H oewel oorspronkelijk ontworpen voor het uitbreiden van bestaande gasttal en met gebruikersgedefinieerde constraint solvers, is CHR in het voorbij e decennium geëvolueerd tot een krachtige, elegante, algemeen bruikbare programmeertaal, met een breed spectrum van toepassingsdomeinen. Deze verhandeling heeft tot doel de praktische bruikbaarheid van CHR als programmeertaal verder te verbeteren. In een eerste stap, herontwerpen we de syntax, taalelementen, en operationele semantiek van de taal, tene inde een meer hoog-niveau, declaratieve programmeerstijl te ondersteunen . Onze gestroomlijnde CHR2 syntax resulteert in meer natuurlijke, leesba re, en compacte regeldefinities. De operationele semantiek van CHR2 prog ramma's is ontworpen om zo non-deterministisch mogelijk te zijn, maar to ch nog de effectieve uitvoeringscontrole te bieden die onontbeerlijk is voor praktisch programmeren. In overeenstemming met de 'wat, niet h oe' en 'algoritme = logica + controle' motto's van declaratief prog rammeren, bepaalt het CHR2 systeem normaal zelf volledig de uitvoeringss trategie. Echter, wanneer nodig kan de programmeur de uitvoeringsvolgord e van de regels en conjuncties bijsturen met een combinatie van twee ort hogonale, vertrouwde mechanismes voor uitvoeringscontrole: regelpriorite iten en sequentiële conjuncties. Prioriteiten worden gespecificeerd via symbolische beperkingen (constraints), die flexibeler zijn dan eerdere v oorstellen, en een betere scheiding bieden van de logische en controle-a specten van een programma. Verder breiden we de CHR taal uit met expressieve taalabstracties genaam d aggregaten. Aggregaten zijn krachtige, bondige regeltoepasbaarheidsvoo rwaarden die informatie verzamelen over grotere delen van de constraint store. Vertrouwde voorbeelden zijn onder andere min, sum, count, en find all. Het voorgestelde raamwerk ondersteunt geneste aggregaatsuitdrukking en, efficiënte incrementele berekening van aggregaten, en toepassingsspe cifieke, gebruikersgedefinieerde aggregaten. Dankzij aggregaten worden t ypische laag-niveau encoderingen overbodig, waardoor CHR zijn hoog-nivea u, declaratief karakter herwint. Een volgend cruciaal aspect van de praktische bruikbaarheid van een prog rammeertaal is de performantie van haar implementaties. Omdat CHR2 regel s geschreven zijn op een zeer hoog niveau van abstractie, is het bepalen van de optimale laag-niveau uitvoeringsstappen om deze regels te evalue ren bijzonder uitdagend. Het laatste deel van de verhandeling introducee rt, evalueert en verfijnt daarom nieuwe en bestaande analyse- en optimal isatietechnieken voor CHR programma's. Twee problemen worden meer gedeta illeerd behandeld: We herwerken het compilatieschema voor CHR om het rui mtegebruik van recursieve programs te optimaliseren, en ontwerpen nieuwe technieken om op een optimale manier---zowel qua ruimte als tijd---te v oorkomen dat zogenaamde propagatieregels meerdere malen worden toegepast . Om CHR echt nuttig bruikbaar te maken voor praktische toepassingen, moet CHR ingebed worden in een mainstream gasttaal. Daarom hebben we het K.U .Leuven JCHR systeem ontwikkeld, een state-of-the-art CHR systeem voor J ava. De thesis behandelt zowel taalontwikkelingsaspecten gerelateerd aan de integratie van CHR met imperatieve gasttalen, alsook de technische u itdagingen die opdagen bij het compileren van CHR naar dergelijke talen. JCHR is momenteel een van de meest complete en efficiënte CHR implement aties beschikbaar, en is typisch meerdere grootteordes efficiënter dan a ndere regelgebaseerde systemen. Ons JCHR2 systeem is bovendien een eerst e referentie-implementatie van de verbeterde CHR2 taal, uitgebreid met n egation as absence.