« Blogglunch i Malmö-söndagen den 16:e december | Main | Mailen strular förhoppningsvis inte längre »

april 05, 2008

Constraint Programming: Minizinc, Gecode/flatzinc och ECLiPSe/minizinc

Minizinc är ett relativt nytt constraint programming-system (startade 2005). Det tillhör G12-projektet som är menat att bli ett öppet (som i open source) state-of-the-art-system.

Samtidigt som det mer kompletta systemet Zink håller på att utvecklas, utvecklas Minizinc en mindre variant som även föreslås att användas som ett gemensamt språk för benchmarks av olika constraint solvers (dvs de system som faktiskt löser problemen, se nedan).

Zinc (storebrodern) finns inte tillgängligt för närvarande. Det finns däremot Minizinc, dels i en officiell version 0.7.1, dels en utvecklingsversion (jag använder utvecklingsversionen). Se vidare Download för nedladdningar.

Specifikationen för både Zinc och MiniZinc är Zinc spec (PDF). Detta dokument och andra nyttigheter finns via MiniZinc and FlatZinc. Uppdaterade versioner av dokumenten finns i utvecklingsversionen.

Många Minizinc-exempel finns här. Fler exempel finns i distributionens kataloger examples respektive benchmark samt till viss del i katalogen test/minizinc.

Jag tycker att Minizinc är ett mycket trevligt och lättarbetat system. Språket har syntaktiskt socker på en bra nivå och är numera min favorit bland constraint programming-systemen.

Det kommer att bli mycket intressant när Zinc släpps eftersom det har en massa skoj finesser som jag saknar i Minizinc, men jag lämnar det för nu. Här nedan kommer jag alltså i stort sett endast att prata om Minizinc.


Lite om Minizinc


En av de stora fördelarna med att använda constraint programming-språk liknande Minizinc är att de är deklarativa, dvs man beskriver vad som ska göras och inte hur saker ska göras (så är i alla fall idealet).

Prolog är ett av de mest kända exemplen på denna typ av programspråk. [Några mindre kända sådana språk är inom stable models/answer set programming-paradigmet såsom smodels/lparse, som nog kan uppfattas som än mer magiska än Prolog.]

Minizinc är dock inget "komplett programspråk" såsom Prolog, t.ex. saknas stöd för rekursion (detta av design för att göra det enkelt att arbeta med för olika solvers), det finns ingen filläsning förutom inkluderande av andra Minizinc-modeller eller data, hantering av strängar är synnerligen begränsat etc.

Trots dessa begränsningar är kan väldigt många problem modelleras i Minizinc. Se den officiella exempelsamlingen som innehåller olika typer av standardproblem från constraint programming, operations research och matematisk programmering. Nedan finns något av det som jag själv knåpat ihop.


Några speciellt trevliga saker i Minizinc

- definition av predicate

Man kan definiera predikat som sedan kan återanvändas via include-direktivet. Det finns en samling sådana i lib/zinc/globals.mzn som är väl värt att studera.

(I Zinc kommer det att finnas möjlighet att definiera funktioner som returnerar värden, men i Minizinc använder man samma teknik som i Prolog för att "returnera" värden, dvs att ange returvärdet i parameterlistan.)


- "bidirectional" predikat

Liksom Prolog har Minizinc den trevliga egenskapen att predikat kan vara "bidirect", dvs att flödet mellan parametrarna kan verka åt båda hållen, kan vara ut- eller in-data. Ett enkelt exempel på detta är konvertering mellan tal och en vektor (givet en bas). Jag har definierat toNum på följande sätt.

predicate toNum(array[int] of var int: vec, var int: n, float: base) =
let {
int: len = length(vec)
}
in
% summera ihop elementen i vec för den givna basen
n = sum(i in 1..len) (
ceil(pow(base, int2float(len-i))) * vec[i] % se nedan för varför denna används
)
% samtliga element i vec måste vara 0
/\ forall(i in 1..len) (vec[i] >= 0)
;

Poängen är att man kan använda detta predikat för att konvertera från ett decimaltal (n) till en vektor (vec) av heltal i den givna basen base, eller konvertera från vektorn av heltal till ett tal (givet en bas). toNum används t.ex. i debruijn_binary.mzn, vilken se. (I teorin skulle man också kunna räkna ut vilken bas som används givet vec och n, men det går inte i Minizinc eftersom pow() inte kan användas på en var-deklarerad variablen utan måste definieras som en fix parameter.)

Här blir n = 7

% ...
constraint
% ....
toNum([1,1,1], n, 2.0)
;

och här blir vec = [1,1,1]:

% ...
constraint
% ...
toNum(vec, 7, 2.0)
;


Det är mycket denna bidirektionella egenskap gör att programmering i Minizinc (och liknande deklarativa språk) känns riktigt magiskt. Och det är synnerligen skoj.

Tyvärr är Minizinc hårt typat så man måste själv konvertera flyttal till heltal, vilket frustrerar mig. [I Zinc/Minizinc-specen står att sådan konvertering kommer att göras automatiskt i storebroderna Zinc, men inte i Minizinc. Jag hoppas att specifikatörerna besinnar sig.] Och eftersom pow()-funktionen för heltal inte funkar i den aktuella versionen är man tvungen att använda float-varianten vilket innebär att man måste använda göra ceil(...)-hacket. Det är ju en hel del sådant i betaversioner som det tar tid att komma på och runt.

Ett något mer avancerad exempel på bidirection är mortgage.mzn (beräkning av lån), som är ett (annat) standardexempel i constraint logic programming (där ofta just Prolog användas som grund eller inspiration för implementationerna). På samma sätt som i toNum kan samma kodbas - med olika initialvärden - användas för att räkna ut de andra parametrarna. Se kommentarerna i programmet för vidare info. Not: för närvarande är det endast ECLiPSe-solvern som klarar detta problem.

Exempel på mer användande av toNum finns i programmen debruijn_binary och gray_code.mzn som beskrivs mer nedan.


* global constraints

I filen lib/zinc/globals.mzn finns ett flertal "global constraints" implementerade (och det antyds att det kommer att fyllas på med fler). Global constraints kan ses som standardrutiner ("standardmönster") att lösa vissa typer av (del)problem, t.ex. all_different(x) som kräver att samtliga element i en vektor ska vara olika, global_cardinality_constraint som räknar hur antal förekomster av olika element det finns i en vektor (och med bidirect-principen kan man ställa krav på antalet förekomster), etc.

Det finns en stor samling definitioner/beskrivningar av sådana global constraints (men tyvärr inga implementationer) i Global Constraint Catalog.

Min personliga fascination för sådana globala constraints är på modelleringsnivå eftersom de kan ses som byggstenar (tankehjälp) för modellering. Som övning har några av dessa implementerats såsom circuit.mzn (som i min implementation bygger på några observationer kring s.k. orbits i permutationer), cycle etc.

En stora vinst med sådana global constraints är att underliggande solvers kan göra specialoptimimeringar, vilket naturligtvis snabbar upp systemen. Studiet av sådana global constraints är en viktig del i forskningen kring constraint programming.


* stöd för flera olika solvers

Språket Minizinc är egentligen bara en del av systemet och det löser inga problem. I stället konverteras till ett annat språk (Flatzinc) som olika solvers kan arbeta med för att faktiskt lösa problemet. (Man skulle kunna översätta "solver" med "problemlösare", men eftersom det ryser varje gång jag använder den svenska versionen av Excels Solver så gör jag inte det :-). I distributionen finns det en solver med: flatzinc.

Redan nu finns det redan tre solvers: flatzinc, Gecode/flatzinc samt ECLiPSe-modulen minizinc. De gås igenom nedan.

Exempel

Som första lite längre kommenterade exempel visas här SEND + MORE = MONEY-problemet (saknas av någon anledning i Minizinc-exempelsamlingen). Problemet är helt enkelt: Byt ut bokstäverna mot unika siffror (0..9) i additionen SEND + MORE = MONEY. Det är ett paradigmatiskt exempel (dvs har "Hello, world"-status) i constraint programming-världen och finns i alla läroböcker.

Så här ser min rättframma implementation ut:

% globals.mzn innehåller den globala constrainten all_different
include "globals.mzn";

% definierar varje bokstav som en variabel
% de är samtliga heltal mellan 0 och 9
var 0..9: S;
var 0..9: E;
var 0..9: N;
var 0..9: D;
var 0..9: M;
var 0..9: O;
var 0..9: R;
var 0..9: Y;

% vektorrepresentationen av de 8 variablerna för att kunna
% använda all_different
array[1..8] of var int: fd =
[S,E,N,D,M,O,R,Y];


%
% De olika begränsningarna som ska göras, både för själva problemet och
% eventuella hjälpstrukturer
%
constraint

% all_different kräver att alla siffror ska vara olika
all_different(fd) /\

% definiera själva problemet, dvs hur relationen mellan bokstäverna
% ser ut
1000*S + 100*E + 10*N + D +
1000*M + 100*O + 10*R + E =
10000*M + 1000*O + 100*N + 10*E + Y
/\
% varken S eller M får vara 0
S > 0 /\
M > 0
;

%
% solve satisfy ger en lösning, dvs inget att minimera eller maximera
%
solve satisfy;

%
% utskriften
%
output [
% show(fd), "\n",
"S:", show(S), " E:", show(E), " N:", show(N), " D:", show(D),
" M:", show(M), " O:", show(O), " R:", show(R), " Y:", show(Y),
"\n\n",

" ", show(S), show(E), show(N), show(D),"\n",
" + ", show(M), show(O), show(R), show(E),"\n",
" = ", show(M), show(O), show(N), show(E), show(Y), "\n"

];

Sedan kör man programmet lite olika beroende på vilken solver man använder. Jag brukar testa med samtliga tre för att se vilken som är snabbast etc.

Minizinc (anropar flatzinc automatiskt)

minizinc send_more_money.mzn

eller programmet flatzinc direkt via konvertering till .fzn-format.


mzn2fzn send_more_money.mzn
flatzinc send_more_money.fzn

Gecode/flatzinc:

mzn2fzn send_more_money.mzn
fz send_more_money.fzn

ECLiPSe:

eclipse -e "minizinc:mzn_run('send_more_money.mzn',zn_options{solver:fzn_ic})"

Resultatet blir samma för alla

S:9 E:5 N:6 D:7 M:1 O:0 R:8 Y:2

9567
+ 1085
= 10652

Fler exempel

Här är några andra exempel som inte finns på MiniZinc-sajten eller i distributionen. Flera av dem är sådana jag brukar ha som standardproblem för att för att testa olika constraint-system vad gäller språk, performance och rent allmänt hur det är att arbeta med. T.ex. så kollade jag i höstas in AMPL (ett mycket trevligt system för "matematisk programming") men där var man i vissa fall tvungen att trixa ordentligt - i och för sig vedertagna och väl dokumenterade tricks - för att göra sådant såsom "all_different". Minizinc (och de flesta andra constraint system) har all_different implementerat som standard.


I Choco: Constraint Programming i Java gavs några exempel på problem som löstes i constraint programming-systemet Choco. Dessa har nu skrivits om i Minizinc. Som jämförelse länkas även till Choco-varianten.

* Planering av möbelflyttande, använder "global constraint" cumulative

furniture_moving.mzn (FurnitureMoving.java)

* Ett enkelt knapsack-problem (minimering)

knapsack.mzn (Knapsack.java)

* Least diff (minsta differensproblemet som beskrivs i ovanstående blogganteckning)

least_diff.mzn (LeastDiff2.java)

* Sesemans klosterproblem

seseman.mzn (Seseman.java). Se Sesemans matematiska klosterproblem samt lite Constraint Logic Programming för en förklaring av detta problem.


* set_covering_deployment.mzn

Implementation av exemplet på Set Covering Deployment för att optimera antal arméer i gamla romarriket. Problemet beskrivs i detalj i R.R. Rubalcaba Fractional Domination, Fractional Packings, and Fractional Isomorphisms of Graphs (PDF).


de Bruijn-sekvener och "arbiträra de Bruijn-sekvenser"


Jag har länge varit fascinerad att de Bruijn-sekvenserna och publicerat två (eller tre beroende på hur man räknar) webbaserade program:

- de Bruijn sequence, samma som Java Applet

- de Bruijn arbitrary sequences, där man använder "de Bruijn-egenskapen" men tillåter sekvenslängden bestäms av användaren.

Se respektive de Bruijn-sekvenser (portkodsproblemet) och de Bruijn-sekvenser av godtycklig längd för förklaringar av programmen.

Naturligtvis var detta en sak som skulle kodas i Minizinc. Första versionen av programmet byggde liksom webbversionen av "de Bruijn arbitrary sequences" på en speciell typ av graf som traverserades på ett visst sätt. Denna implementation var dock lite trixig att genereralisera till andra baser än n=2. Därefter skrevs en variant där man programmerar de Bruijn-egenskapen direkt i stället för att gå via en graf, vilket gjorde det hela mycket mer generellt och (oftast) snabbare.

Denna senare variant finns att beskåda i debruijn_binary.mzn. (Anledningen till att programmet heter "_binary" är bl.a. för att jag fick idén till implementationen några minuter efter jag kodat klart Gray-koder).


Exempelkörning
Problemet som jag kallar för 2/4/16 är base = 2, n = 4 (antal bitar att använda), m = 16 (längden på sekvensen). Programmet spottar ur sig lite olika typer av information:

- bin_code / binary_code: själva de Bruijn-sekvensen
- x är decimalrepresentationen av vektorerna som utgör sekvensen
- gcc (förkorting av global cardinality constraint) kontrollerar hur många olika siffror (0..base-1) som används. Det finns en begränsning att det måste vara exakt lika många förekomster av de olika siffrorna om det är matematiskt möjligt. Och det är just denna begränsning som gör problemet både intressant och tungt. I exemplet ser vi alltså att det finns 8 stycken 0:or och 8 stycken 1:or.
- sedan kommer listningen av "bit-representation" av vektorerna


n: 4 m: 16 base: 2
bin_code: [0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1]
gcc: [8, 8]
binary code: 0000100110101111
x (decimal representation):
[0, 1, 2, 4, 9, 3, 6, 13, 10, 5, 11, 7, 15, 14, 12, 8]
0 0 0 0
0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 1
0 0 1 1
0 1 1 0
1 1 0 1
1 0 1 0
0 1 0 1
1 0 1 1
0 1 1 1
1 1 1 1
1 1 1 0
1 1 0 0
1 0 0 0


Ett problem som är betydligt tyngre att lösa är 4/3/52, dvs bas=4 (dvs siffrorna 0, 1, 2 och 3 används), 3 "bitar" i varje tals vektor, samt en sekvenslängd på 52. Detta är så tungt så man inte kan använde solve satisfy utan måste använda sökheuristiker för att inte vänta förgäves på en lösning.

Genom experiment (föregånget av luskande i källkod och dokumentation hittades följande

solve :: int_search(x, "first_fail", "indomain_split", "credit(5,bbs(1))") satisfy

(Zinc-specen förklarar ingående vara parametrarna innebär, men det är helt enkelt lite olika metoder att traversera problemträdet.)

Den praktiska innebörden är att Eclipse-solvern hittar 1 lösning mycket snabbt, 65 lösningar på 5 sekunder (jag vet inte hur många olika lösningar som det total finns men det är väldigt många i alla fall). Med credit(4,bbs(2)) blir det 108 lösningar på 8 sekunder, credit(4,bbs(4)) hittar 1104 lösningar på 1:07 minuter etc.

En av dessa lösningar är följande

n: 3 m: 52 base: 4
bin_code: [0,0,2,0,0,3,0,1,0,1,1,0,2,1,0,3,1,1,1,2,0,1,2,1,1,3,0,2,2,0,2,3,0,3,2,0,3,3,1,2,2,1,2,3,1,3,3,2,2,3,3,3]
gcc: [13,13,13,13]
binary code: 0020030101102103111201211302202303203312212313322333
x (decimal representation):
[2,8,32,3,12,49,4,17,5,20,18,9,36,19,13,53,21,22,24,33,6,25,37,23,28,50,10,40,34,11,44,51,14,56,35,15,61,54,26,41,38,27,45,55,31,62,58,43,47,63,60,48]Total time 0.320s cpu (0.040 setup + 0.280 search)

Tyvärr har varken Flatzinc eller fz givit någon lösning alls på detta problem (jag har låtit båda programmen stå minst en timme varderna men sedan tröttnade jag). Om man däremot tar bort kravet att det ska exakt samma antal förekomster av siffror i sekvensen löser även fz problemet snabbt (men minizinc gör det inte).


Olika solvers


För närvarande finns tre olika solvers, med olika för- och nackdelar.


* flatzinc
Det är denna solver som följer med i Minizinc-distributionen.

Fördelar:
- det största fördelen är att den finns med i distributionen och kan alltså användas direkt.

Brister:
- ger endast en lösning oavsett hur många lösningar som problemet har. Detta är för mig en mycket stor brist.
- klen vad gäller beräkning av stora tal. T.ex. klarar den inte av grocery.mzn eftersom det är för stora tal inblandade.
- verkar inte vara känslig för de olika heuristikerna

* Gecode/flatzinc (fz)
Gecode/Flatzinc.

Kräver att Gecode finns installerad. Gecode är ett snabbt open source constraint programming-system (skrivet i C++) och har flera intressanta exempel. Det finns även en Java-implementation ovanpå Gecode Gecode/J. Båda dessa är väl värda att bekanta sig med helt oavsett Minizinc.

Fördelar:
- ofta mycket snabb, ibland snabbare än Eclipse-solvern (även fast man har heuristiker som hjälper Eclipse-solvern)
- ger flera lösningar (alla!) om det finns (såvida man inte "heuristicerar" bort dem)
- summerande statistik som indikerar hur svårt problemet är att lösa

Nackdelar:
- min uppfattning är att fz inte är lika känslig för sök-heuristikerna som Eclipse-solvern vilket gör att den kan vara långsammare än Eclipse-solvern för vissa problem
- klarar inte av vissa typer av flyttalsberäkningar, t.ex. mortgage exemplet ovan.
- kan reagera konstigt på sök-heuristikerna
- man måste installera gecode


* ECLiPSe
Kräver ECLiPSe Constraint Programming System. Det är en variant av Prolog (min favoritvariant och som användes i Sesemans matematiska klosterproblem samt lite Constraint Logic Programming).

För tillfället krävs en utvecklingsversion eftersom Minizinc-stödet ännu inte är officiellt släppt. Eftersom sajten crosscoreop.com kan bete sig konstigt vid hämtande av stora filer är att rekommendera att man hämta filerna från en av speglarna t.ex. http://sunsite.informatik.rwth-aachen.de/ftp/pub/mirror/ECLiPSe-CLP/.

Dokumentation hur man använder Minizinc-modulen finns i library(minizinc).

Ett tips är även att studera ECLiPSe-predikatet search/6 som är inspirationskällan för sök-heuristiken i Minizinc.


Fördelar:
- liksom fz mycket snabbt och ger alla lösningar
- klarar av flyttalsberäkningar (såsom mortgage)

Nackdelar:
- vissa saker är inte implementerade, såsom vissa set_operationer.
- man måste installera ECLiPSe-systemet.

Buggar eller brister

Här är några brister antingen i de aktuella implementationerna eller saker som stör mig i designen av språket.

* Utskrifen är inte fullständigt i den existerande beta-versionen. Det är trixigt att skriva ut mer komplicerade strukturer (se exemplen). Det finns för närvarande inget sätt att villkora så att man bara ska skriva ut vissa element i en var-deklarerad array (såsom endast de element som är större än 0). Till viss del är det ett desginbeslut, möjligen kommer fix() att lösa några av dessa problem.

* Typningen. Personligen tycker jag inte om den strikta typningen av float och int (det är enligt design) som gör att man explicit måste sköta sådant. T.ex. görs '/' (division) endast på flyttal och det gör att vissa problem blir mycket svårare att lösa (såsom några av Integer Programming-pysslen). Det är inte alltid det går att använda div-operatorn (som f.ö. är buggig i fz) eller att (på ett enkelt sätt) skriva om problemet så det inte använder division.

* Det saknas en solver som använder metoder från linjär programmering/heltalsprogramming (såsom simplex-metoden). Det antyds att det finns sådana men de är ännu ej släppta. I och för sig har ECLiPSe-systemet någon form av stöd för eplex i sin Zincinterface-katalog, men det har jag inte fått att fungera ännu. Uppdatering ett halvt dygn senare:: Jodå, eplex funkar för vissa typer av problem såsom några av exempeln i examples-kataloge; queens_ip.mzn, min_cost.mzn, product_lp och multidimknapsack_simple. Får alltså kolla in det mer...

Länkar
Annat som kan vara intressant.

* Integer Programming Puzzles (programmering av lösningarna av Martin Chlond). Detta är en härlig samling "heltalspyssel" (dvs där lösningarna är heltal, eller kan ses som heltal). Send More Money, Least Diff är några andra exempel på sådana problem.

När jag satt med AMPL i höstas konverterade jag i stort sett samtliga dessa problem från XPress till AMPL, och har nu kodat om dessa till Minizinc. Tyvärr är det inte alla Minizinc-implementationer som ger resultat inom rimlig tid. Ett projekt i vardande är att hyfsa till dem och sedan lägga ut dem på sajten.

Jag tänkte här egentligen länka till en del annat som jag hållt på med sedan oktober förra året, såsom Excel, Open Office Calc, Linear Programming, AMPL, GLPK, matematisk programming, Operations Research, andra constraint programming-system etc, men det blir i så fall i separata postningar.


Posted by hakank at april 5, 2008 09:33 EM Posted to Constraint Programming

Comments

Det var så kul att se ett inlägg här att jag läste halva på en gång, fast jag borde gå och lägga mig. Jag ångrar ibland att jag blev klar med min utbildning precis lagom till att det inte fanns några jobb att få som programmerara. Jag gillade verkligen Prolog och datamodellering, och hade säkert delat din fascination för zink-familjen, men tyvärr har jag hunnit tappa tråden för mycket för att komma tillbaks. Och blivit för gammal för att klara att köra flertrådat.

Posted by: HÃ¥kan (hakke) [TypeKey Profile Page] at april 5, 2008 10:59 EM

Ja, blev också glad att se ett nytt inlägg. Intressant, kände inte till constraint-programmering.

Posted by: Peter Lindberg [TypeKey Profile Page] at april 6, 2008 10:21 FM

Hakke och Peter: Tack för era glada tillrop. Även jag är glad att det finns ett nytt inlägg här. :-)

Hakke: Hoppas att du även läser den andra halvan (vilken det nu än är).

Man är dock aldrig för gamal för flertrådning.

Peter: Det är bra att du nu känner till något som du inte kände till förut. Precis det är syftet.

Posted by: hakank [TypeKey Profile Page] at april 6, 2008 10:30 FM

Tack för intro och pekare till ett antal intressanta saker jag inte hade en aning om fanns.

Som du kanske kan gissa är jag dock mest intresserad av databasaspekten i det hela. Programmerare har (förståeligt nog) en tendens att sätta likhetstecken mellan att formulera ett problem och att skriva ett program. Ett annat sätt att se på det är att man ställer en fråga till en databashanterare. När jag kodade i Prolog på logikprogrammeringskursen kom jag fram till den föraktfulla ståndpunkten att Prolog inte var ett programspråk utan en riktigt ineffektiv databashanterare, som går omkring linjärt och letar efter lösningar i databasen, utan att använda smartare datastrukturer som uppenbarligen skulle tillåta markanta genvägar.

Jag har samma uppfattning idag, fast något mindre föraktfullt. Jag har på senare tid jobbat en del med att formulera databaslogik i ett Prologliknande språk, vilket är fantastiskt mycket mer kraftfullt och konceptuellt rimligt än SQL. Problemet med Prolog är att man kompromissat bort en del av kraften i den eleganta syntaxen genom att definiera exakt hur motorn ska evaluera uttrycken. Det har man gjort för att kunna använda språket till att uttrycka processer som i konventionella programspråk. Därmed förstör man möjligheten för "solvern" (om jag förstår det begreppet rätt) att göra något riktigt smart.

Det finns en variant som heter Datalog som är mer databasorienterad, men arbetet med den är experimentellt och akademiskt och hänförs till ett specialområde som kallas "deduktiva databaser". Som om inte alla databaser var deduktiva!

Så vad vill jag komma till? Jo, det vore trevligt om några fler som jobbade med sådana här system ville tänka mer i databastermer, vilket innebär stora mängder data (jag pratar gigabyte) och inte så fixerade vid att lösa kluriga bevisföringsproblem. Vet du något om arbete i den riktningen skulle jag vara mycket intresserad.

Posted by: ctail at april 13, 2008 01:53 EM

ctail:

Jag tänker inte gå i polemik med dig huruvida Prolog är ett programspråk eller inte, förutom att du har fel. :-) Eller snarare att jag tycker att det synkatiska socker som finns i moderna varianter av Prolog (säg ECLiPSe) är mycket trevligt, liksom egenskaper såsom bidirection.

Ineffektiviteten i Prolog är ju också något som forskas kring med olika typer av extensions, som just constraints, linear/integer programming etc. ECLiPSe har syntaktiskt lagt till ett flertal loop-konstruktioner och lite annat skoj.


Vad gäller din fråga i slutet kommer jag direkt att tänka på mina två olästa böcker om constraint databaser som jag inköpte för länge sedan på PC-bokens konkurs-rea.

Jag känner inte till speciellt mycket om constraint databaser, men letade efter sådana system för ett tag sedan och hittade inga gigabyte-system. Sidan Constraint Databases Homepage har lite länkar.

De böcker som jag har och som du gärna får låna/bläddra i är:
* Revesz: Introduction To Constraint Databases
* Kuper, Libkin, etc: Constraint Databases.

En introducerande artikel

* Jan Van den Bussche: Constraint databases: An tutorial introduction (PDF)


Kanske är även följande relevant:

Marco Cadoli, Toni Mancini Combining Relational Algebra, sql, and Constraint Programming (ps.gz)

Posted by: hakank [TypeKey Profile Page] at april 13, 2008 06:51 EM

Ok, Prolog är naturligtvis ett programspråk (jag borde ha varit tydligare i mitt avståndstagande från mitt drastiska ungdomliga omdöme), men det är just att det har utformats för att fungera som programspråk som är så synd. I den grundläggande syntaxen är Prolog ett utmärkt databas-/logikspråk, men genom att införa restriktioner i hur evalueringen får göras (för att göra program med sidoeffekter förutsägbara) har man saboterat för den som vill optimera frågeexekveringen. Men det är förstås orättvist att angripa Prologs skapare för att de inte skapade ett perfekt databasspråk (det var ju inte det de var ute efter) när det är SQL:s skapare som verkligen förtjänar att klandras.

"Constraint databases" kan vara intressant, får kolla upp det. Men jag tar själva begreppets existens som ytterligare ett tragiskt bevis på den globala bristfälliga förståelsen av databasteori. Vilka databaser är inte "constraint databases"?

Posted by: ctail at april 13, 2008 09:03 EM