An Extension of Erlang with Finite Domain Constraints


Uppsala Masters Theses in Computing Science Examensarb ete D V ISSN An Extension of Erlang with Finite Domain Constrain ts Gr e ger Ottosson Computing Science Departmen t Uppsala Univ ersit y Bo x S Uppsala Sw eden ERICSSON Utv ec klings AB Arm b orstv agen Bo x S Alvsj o Sw eden Sup ervisor Bj orn Carlson Mats Carlsson and Bogumi l Hausman Examiner Mats Carlsson Abstract This rep ort describ es the design and implemen tation of a nite domain constrain t solv er for Erlang The constrain t solv er handles linear arith metic constrain ts o v er natural n um b ers whic h are appro ximated using arc and in terv al consistency W e use a sc heme with functional rules for constrain t propagation and consistency main tainance and plain bac ktrac king programmed in Erlang to searc h for solutions Keyw ords constrain t satisfaction problems nite domain constrain ts constrain t solving concurren t functional languages Con ten ts In tro duction Bac kground CLP X Erlang FD Summary Rep ort Ov erview Preliminaries Finite Domain Constrain ts Arithmetic Finite Domain Constrain ts Constrain ts and Constrain t Stores Ask T ell ArcConsistency In terv alConsistency Indexicals Erlang History and Language Characteristics Data Ob jects Source Co de P attern Matc hing Con trol Structures BuiltIn F unctions i Concurrency Distribution Dynamic Co de Managemen t The BEAM Erlang implemen tation Design Erlang FD Structure Erlang FD Em ulator In terface Implemen tation Compilation of Arithmetic Constrain ts Inlined Indexicals Library Constrain ts Inlined Indexicals vs Library Constrain ts Equiv alen t Indexicals The Propagation Algorithm Propagation Optimizations The Optimized Propagation Algorithm Compiling and Ev aluating Ranges The Em ulator Compiling to Byte Co de Determining Monotonicit y of Indexicals Searc hing for Solutions A Bac ktrac king Sc heme V ariable Ordering Data Structures Finite Domain V ariables Finite Domains Finite Domain Indexicals ii Ev aluation Benc hmark Programs P erformance Figures Discussion Dierences Bet w een The Solv ers Proling Erlang FD Summary and P ossible Impro v emen ts Conclusion Summary F uture W ork F uture Dev elopmen t of Erlang FD Ongoing W ork with Constrain t Solv ers Ac kno wledgemen ts Bibliograph y A Erlang FD BIFs A CompileTime BIFs A Em ulator BIFs A Debugging BIFs A Misc BIFs B User Man ual B In tro duction B Initialization B Allo cating V ariables B T elling Constrain ts B Using Arithmetic Constrain ts B Using Indexicals iii B Generating Solutions B User Library C Example Programs C Send More Money C Queens C Alpha C Equations C Equations C Fiv e Houses C Magic Series C Suudoku D Libraries D User Library D V ariable Ordering D Library Constrain ts iv List of Figures Syn tax of indexicals Design of Erlang FD T rail and c hoice p oin t stac k in the bac ktrac king sc heme v vi List of T ables Library constrain ts Com bination of prunings Byte co de instructions T ranslation of ranges and terms to b yte co de Monotonicit y of term expressions Monotonicit y of range expressions Erlang FD execution sp eed SICStus FD execution sp eed AKL FD execution sp eed The most time consuming functions in Erlang FD vii viii List of Algorithms A C An arcconsistency algorithm A simplistic propagation algorithm An optimized propagation algorithm The monotonicit y algorithm ix x Chapter In tro duction This c hapter giv es some bac kground of the eld in tro duces our w ork in that con text and presen ts our aim and goals Bac kground Man y computational problems can b e stated as constrain ts o v er v ariables of some abstract domain P ac king sc heduling and allo cation are problems whic h can often b e describ ed using nite domain c onstr aints Basically a Constr aint Satisfaction Pr oblem CSP is comp osed of a nite set of v ariables of nite domains and a set of constrain ts that restrict the v alues the v ariables can sim ultaneously tak e The task is to assign a v alue to all v ariables satisfying the constrain ts Solving a CSP can b e divided in to t w o steps pr oblem r e duction whic h in v olv es reducing the v ariable domains b y remo ving redundan t v alues and tigh tening the constrain ts and se ar ching for a v alid solution through en umeration CSPs has b een the sub ject of gro wing in terest and researc h for the last ten y ears and man y dieren t approac hes ha v e b een made Both sp ecialpurp ose programs with domainsp ecic kno wledge and generic solv ers for classes of problems ha v e emerged T o the latter one ma y coun t the extension to logic programming forming Constr aint L o gic Pr o gr amming CLP F rom a CSP p ersp ectiv e constrain t solv ers in CLP are an in tert wined mixture of the t w o phases problem reduction and searc h men tioned ab o v e The CLP comm unit y ha v e approac hed the CSP b y using dieren t tec hniques for dieren t domains and th us there are CLP B CLP FD and CLP R for solving b o olean nite and rational domain problems resp ectiv ely Bo olean constrain t prob lems can for example b e solv ed using b o ole an unic ation while problems with rational CHAPTER INTR ODUCTION n um b ers are commonly dealt with using some deriv ativ e of the simplex algorithm In this rep ort w e will describ e one approac h for solving nite domain problems CLP X The theory b ehind the family of CLPlanguages CLP X is based on logic pro gramming where unic ation is replaced with c onstr aint hand ling in a constrain t sys tem Hen tenryc k Hen tenryc ks CLP sc heme denes a class of languages of whic h an instance can b e obtained b y considering a sp ecic constrain t system a computation domain and for that pro vide a constrain t solv er The output from a CLP X language is an answ er substitution v alues for the v ariables or a conjunction of answ er constrain ts The CLP framew ork has later b een extended b y the researc h on Concurr ent Con str aints Pr o gr amming The original notion of addingp osting a constrain t c to a constrain t store ie 0 c is called tel ling The term ask is in tro duced with whic h w e mean to c hec k if a constrain t c is en tailed in the constrain t store ie c Erlang FD This w ork aims at em b edding nite domain constrain ts within the concurren t func tional language Erlang The ob ject is to mak e the language more v ersatile and exible and to extend the class of target problems Wh y adding the notion of constrain ts to a language lik e Erlang W ell the high lev el a v or of Erlang and its concurrency mak es it go o d for reactiv e and distributed systems but it lac ks supp ort for programming complex sc heduling planning and con trol The em b edding of constrain ts within Erlang w ould mak e up for this and mak e it feasible to program reactiv e constrain t solving and distributed constrain t systems A constrain t system used in a reactiv e en vironmen t needs sp ecial prop erties suc h as the abilit y to susp end during sa y logging or bac kup pro cedures and the abilit y to in teract with pro cesses In Erlang an in terfaceable constrain t store from whic h pro cesses could extract and subscrib e to information and ev en ts w ould b e v aluable With this feature at hand the pr ovider of information sa y a sensor a user in terface or a telephone switc h w ould not ha v e to care ab out what information is used and b y what pro cess P osting the information as en tailed constrain ts in a store w ould b e sucien t since pro cesses from there could extract the information in an in telligen t manner SUMMAR Y In this rst attempt w e do as m uc h as p ossible inside Erlang reusing its memory managemen t pro cess sc heduling con trol structures and syn tax The bulk of our implemen tation is written in Erlang itself This mak es our solv er preemptiv e and fulls our need for a susp ending solv er W e further aim at making it p ossible for pro cesses in Erlang to in terface to our constrain ts in a manner similar to agents in Concurr ent Constr aint Pr o gr amming This ask primitiv e if optionally async hronous w ould mak e it p ossible for pro cesses to subscrib e to ev en ts Our approac h is based on the w ork of Bj orn Carlson with AKL FD Carlson Dierences b et w een AKL and Erlang as w ell as our aim to use Erlang as the primary implemen tation language has forced us to mak e dieren t design decisions esp ecially concerning the searc h and the in terface to Erlang Ho w ev er those familiar with Carlsons w ork will recognize the similarities Our main fo cus is th us on implemen tation asp ects and design issues regarding the in terface to Erlang Our w ork has b een mainly practical and this rep ort is therefore mainly a description of what has b een done Summary Summarizing these are the goals of this w ork to in v estigate the feasibilit y of em b edding nite domain constrain ts within Er lang to determine the appropriate user in terface of suc h an extension to implemen t the notion of ask in a w a y that mak es it useful in Erlang pro gramming and to ev aluate the p erformance and reect up on the design decisions and the im plemen tation Rep ort Ov erview This rep ort is structured as follo ws Chapter Rep ort in tro duction and o v erview CHAPTER INTR ODUCTION Chapter Co v ers bac kground kno wledge and in tro duces concepts needed in later c hap ters T opics are nite domain constrain ts constrain t stores satisabilit y con sistency and indexicals W e also giv e an in tro duction to Erlang and one of its implemen tations BEAM Chapter The design of Erlang FD W e sho w the structure and presen t our design decisions Chapter A detailed c hapter ab out the implemen tation of Erlang FD Kno wledge of the topics co v ered in Chapter is needed Chapter An ev aluation of Erlang FD with resp ect to p erformance W e compare our w ork to SICStus FD and AKL FD Chapter Conclusions and future w ork W e summarize what ha v e b een done in this w ork and name some areas that need further atten tion App endices A user man ual some example programs in Erlang FD and v arious libraries for those with in terest in the implemen tation Chapter Preliminaries This c hapter in tro duces some basic concepts used in CSPs and constrain t solv ers Kno wledge ab out these concepts is needed in subsequen t c hapters W e describ e the notions of c onstr aints and c onstr aint stor es satisability c onsistency and indexic als W e giv e an in tro duction to Erlang and one of its implemen tations BEAM Finite Domain Constrain ts The idea of programming with constrain ts is based on the notion of c onstr aints and a c onstr aint stor e A constrain t in tuitiv ely expresses some relation on a set of v ariables A constrain t store is simply a set of constrain ts In this section w e consider our constrain ts Section and the collection of them in a constrain t store Section on the next page W e also dene c onsistency and an algorithm for ac hieving consistency Section on page Finally w e describ e the indexic als Section on page whic h are the functional rules w e ha v e c hosen to ac hiev e and main tain consistency Arithmetic Finite Domain Constrain ts Since w e are dealing with nite domain constrain ts our constrain ts are expressed as arithmetic expressions o v er subset of the natural n um b ers N An arithmetic constrain t consists of t w o linear terms together with a relation n x n k x k n k x k n n x n where f g 1 W e only consider linear terms nonlinear terms can b e treated Carlson but ha v e not b een implemen ted in our w ork CHAPTER PRELIMINARIES Constrain ts and Constrain t Stores A constrain t is a relation o v er one or more v ariables eg X Y A domain constrain t is a constrain t X f n n k g where n i N A constrain t store is a set of domain constrain ts The value of x in a store x is thereb y N f d x d g F or example x where f x f g x f gg equals f g and for an y unconstrained y y equals N Let b e a constrain t store the follo wing is dened satisabilit y I is said to b e satisable i no x is empt y for an y x extension 0 is an extension of i x 0 x for an y x Put dieren tly 0 is an extension of i 0 That is 0 is a strengthening of the domain constrain ts in en tailmen t A constrain t c is said to b e entaile d in i c is true in all satisable extensions of Put dieren tly c will alw a ys b e true whatev er strengthening of constrain ts is done in satisabilit y II A constrain t c is satisable in i it is en tailed b y some extension of That is a constrain t is satisable as long as it has the p ossibilit y of b eing en tailed inconsistency wrt prop ert y Consistency is a concept with whic h one ma y exercise pr oblem r e duction A constrain t store is said to b e c onsistent with resp ect to certain prop erties i the prop erties hold Main taining consistency th us implies remo ving v alues and tigh tening constrain ts to main tain the prop erties A constrain t store is inc onsistent if it is not consisten t ie it do es not satisfy the prop erties Consistency with a certain prop ert y is not a sucien t condition for a problem to b e solv able A problem na y b e consisten t but unsatisable Dieren t algorithms ac hiev e dieren t lev els of consistency satisability b eing the b est An algorithm guaran teeing satisability is often called c omplete When talking ab out consistency w e annotate the term with the prop erties w e main tain F or example Section on the facing page and on page will dene t w o common consistency lev els arc and in terv alconsistency 2 Confused Do not w orry most of this terminology will b ecome apparen t b y example FINITE DOMAIN CONSTRAINTS F or a through examination of satisabilit y and consistency from a viewp oin t of con strain t satisfaction problems see Tsang Mac kw orth Example Giv en a constrain t store f X Y f gg Then is satisable no x for an y x f X f g Y f gg is an extension of X is satisable in X is not satisable in X is en tailed in F or the rest of the rep ort the follo wing notation will b e used A constrain t store c A constrain t c v v n An instan tiated n ary constrain t Can b e true satised or false X Y Constrain t v ariable or in teger V V alue in teger X The domain of v ariable X in X The constrain ts on X in X V The assignmen t of v alue V to v ariable X Ask T ell The concepts of ask and tel l originated in the area of Concurr ent Concurr ent Pr o gr amming Sarasw at and w as adopted in CLP Hen tenryc k By tel l w e mean to add a constrain t c in a constrain t store ie 0 c The term ask means c hec king if a constrain t c is en tailed a the constrain t store ie c W e will use this terminology throughout the rep ort ArcConsistency The traditional tec hnique for ac hieving and main taining consistency in nite domain constrain t solv ers has b een arcconsistency see eg Mac kw orth Tsang In tuitiv ely the consistency prop ert y is that all constrain ts should b e individually satisable Arcconsistency for n ary constrain ts can b e dened more precisely as follo ws CHAPTER PRELIMINARIES Denition A constrain t c is ar cc onsistent i for eac h v ariable x i with domain D i and v alue v i D i there exists v alues v v i v i v n in D D i D i D n suc h that c v v n is satised A constrain t store is ar c c onsistent i all constrain ts in are arcconsisten t Arcconsistency is ac hiev ed b y eliminating v alues from v ariable domains that are inconsisten t with an y single constrain t An arcconsistency algorithm for binary constrain ts only called A C is presen ted as Algorithm Algorithm A C An arcconsistency algorithm NC No de consistency handling unary constrain ts BEGIN FOR each variable X DO FOR each V X DO IF NOT X V satisfies X THEN REMOVE V from the domain of X END AC Arc consistency algorithm NC BEGIN Q f X Y j X Y g WHILE Q DO DELETE any element X Y from Q FOR each a X IF there exists no b Y such that X a and Y b satisfies X Y THEN REMOVE a from the domain of X Q Q f Z X j Z X Z X Z Y g END What the algorithm do es is to c hec k all constrain ts and remo v e an y v alues from the corresp onding target domain that do not satisfy the constrain ts on the v ariable If v alues are remo v ed from a v ariable domain constrain ts that ma y b e aected b y this are requeued This is rep eated un til it stabilizes ie the queue of constrain ts is empt y There are some remarks that need to b e made ab out this approac h and this algorithm 3 In the previous section w e represen ted v ariable domains as domain constrain ts T o remo v e a v alue from a domain in this con text w ould b e to add a new domain constrain t with a smaller domain FINITE DOMAIN CONSTRAINTS Eciency The algorithm is not naiv e with resp ect to whic h constrain ts it c hec ks Whereas a naiv e algorithm referred to as A C in the literature see eg Tsang w ould consider and c hec k all constrain ts rep eatedly A C a v oids this b y main taining a queue of constrain ts that need to b e c hec k ed Constrain ts are only added to this queue if there is reason to b eliev e that they need to b e c hec k ed ie a v ariable domain of the constrain t has b een reduced Although not naiv e A C is not optimal With resp ect to constrain t c hec ks there exists an optimal algorithm called A C see eg Tsang This algorithm has b etter timecomplexit y but has w orse spacecomplexit y ie it requires a larger amoun t of space to main tain arcconsistency for a problem It is not commonly used in constrain t solv ers and w e will not consider it further Constrain t arit y As p oin ted out ab o v e A C only deals with unary through NC and binary constrain ts F or most purp oses suc h as ours this is not enough There ex ists an extension of A C called HYPER A C whic h deals with constrain ts with higher arit y but since w e use a sligh tly dieren t approac h of handling constrain ts that solv es this problem w e do not consider it here Consistency It is imp ortan t to once again p oin t out that the consistency main tained b y A C is not equiv alen t to satisabilit y T o illustrate this let us consider t w o examples Example Giv en constrain t x y and domains x f g y f g one w ould b e able to remo v e from the domain of y since there is no v alue in the domain of x that satises the constrain t when Y An arc consistency algorithm suc h as A C will accomplish this Example A constrain t x y z x all dieren t and domains x y z f g is not satisable since there are three v ariables and only t w o v alues But since the arcconsistency tec hnique do es not consider the constrain t as a whole but as binary constrain ts it will not disco v er the unsatisabilit y In other w ords the constrain ts are only arcconsisten t not satisable In terv alConsistency In Denition on the facing page w e used domain reasoning ab out constrain ts to ac hiev e arcconsistency This can sometimes b e incon v enien t or to o exp ensiv e to carry out Therefore w e sometimes use in terv al reasoning instead 4 W e use indexicals see Section on the next page CHAPTER PRELIMINARIES Denition Let D  j f min D j max D j g A constrain t c is intervalc onsistent i for eac h v ariable x i with domain D i and v alue v i D  i there exist v alues v v i v i v n in D  D  i D  i D  n suc h that c v v n is satised A constrain t store is intervalc onsistent i all constrain ts in are in terv alconsisten t Let sup x b e suprem um and inf x inm um of an expression x Then in terv al consistency is ac hiev ed using min and max reasoning as in the follo wing example Example A constrain t x y can b e in terpreted as x should at least b e greater than the smallest p ossible v alue of y implying that x f a a inf y g As y ou see w e do not c hec k that for ev ery single elemen t from the domain of x there is a satisable elemen t from the domain of y Instead w e ensure that the lo w er b ound of x s in terv al is greater than the lo w er b ound of y s in terv al As y ou will see later in Section on page our implemen tation tec hnique is based on an arcconsistency algorithm op erating on constrain ts with an y arit y W e use indexicals in tro duced in Section as our programming language to ac hiev e consistency and the consistency main tained is most often arcconsistency or in terv al consistency Indexicals An indexical has the form X in r where X is a v ariable and r is a range The range is an expression that ev aluates to a set and the indexical as a whole can b e seen as a functional rule from a set of v ariables the v ariables in the range expression to the v ariable X Figure on the next page denes the syn tax of indexicals When an indexical is ev aluated in a constrain t store it ev aluates to a new domain constrain t X r N where r is the v alue of the set expression r in the constrain t store Th us the ev aluation of an indexical results in an extension of the constrain t store see Section on page for a denition of extension In the rest of this rep ort w e will sa y that w e pr op agate the indexicals when w e ev aluate a series of indexicals and that w e prune v ariable domains when w e add new domain constrain ts FINITE DOMAIN CONSTRAINTS I X in R X x a v ariable R T T range j R R in tersection j R R union j R R set dierence j R R if R is nonempt y then R else empt y range j R T p oin twise addition j R T p oin twise subtraction j R mod N p oin twise mo dulo j dom X the domain of a v ariable as a range ie X j diffdom X same as ab o v e but indexical is not susp ended on X Susp ension is explained in Section on page N X j i an in teger j inf T N j T T j T T j T T j T divd T division rounded do wn j T divu T division rounded up j T mod N j min X minim um v alue of domain of X j max X maxim um v alue of domain of X j size X domain size of X Figure Syn tax of indexicals CHAPTER PRELIMINARIES Monotonicit y of Indexicals An indexical range is considered monotone in if its v alue a set shrinks when is extended If it gro ws it is considered antimonotone An indexical is considered antimonotone if its range is an timonotone If its range is b oth monotone and an timonotone it is considered c onstant th us it will neither shrink nor gro w The monotonicit y of an indexicals is computed at compiletime see Section on page and is used b y the propagation algorithm in the solv er Section on page Erlang In this section w e will giv e a short in tro duction to the programming language Erlang F or a complete guide to the language w e refer to Concurr ent Pr o gr amming in Erlang Armstrong et al History and Language Characteristics Erlang is a sym b olic high lev el functional and concurren t programming language dev elop ed at Ericsson Computer Science Lab oratory It is aimed for implemen ting soft realtime fault toleran t systems mainly for telecom applications Language features are declarativ e syn tax functional seman tics largely free from side eects concurrency based on ligh tw eigh t pro cesses robust error handling dynamic co de managemen t allo wing co de to b e replaced in running systems language builtin memory managemen t and features for distribution o v er ph ysical mac hines Data Ob jects Erlang supp orts constan ts v ariables and comp ound terms V alid constan ts are in te gers o ats atoms and pr o c ess identiers A comp ound term is either a list or 5 Normally referred to as Pids ERLANG a tuple lists are dynamically gro wing structures while tuples are of xed size The follo wing example sho ws some comp ound ob jects Example List T uple Memory for data structures are automatically allo cated and deallo cated when no longer used V ariables are singleassignment ie they are instan tiated on creation and do not c hange their v alue V ariables are un t yp ed and need not b e declared Source Co de Erlang source co de are divided in to mo dules whic h in turn consist of functions F unctions are b y default lo cal to a mo dule and m ust b e explicitly exp orted to b e seen outside the mo dule Eac h function consists of one or more clauses The follo wing example sho ws a mo dule dening t w o not en tirely uncommon op erations on lists Example modulelists exportmember append memberX X true memberX Y memberX Y memberX false appendHT Z HappendT Z append X X External calls to a mo dule are done b y naming the mo dule explicitly as in listsappend CHAPTER PRELIMINARIES P attern Matc hing P attern matc hing is the fundamen tal concept used in Erlang to c ho ose clauses and assign v ariables The follo wing example sho ws its use in assignmen t Example A Succeeds A is b ound to in teger B foo Succeeds B is b ound to atom foo CC F ails since C cannot b e b ound to b oth the in teger and the list The next section will sho w the use of pattern matc hing in con trol structures Con trol Structures As w e men tioned earlier pattern matc hing is used to c ho ose the clause within a function P attern matc hing is also used for c ho osing execution path inside the b o dy of clauses ie with if and case statemen ts case Expr of Pattern when Guard Seq Pattern when Guard Seq PatternN when GuardN SeqN end if Guard Seq Guard Seq GuardN SeqN end The case clause ev aluates Expr and matc hes the result against the patterns The corresp onding sequence to the rst succeeding matc h is c hosen Pattern can b e an y data structure with v ariables Anon ymous v ariables can b e used and if used in single ie case A of it will b e a c atch al l matc hing an ything Guards are used to extend the pattern matc hing and consist of one ore more sp ecial tests on the v ariables in the pattern Eg one can c hec k if a v ariable is an atom or if it is a list and has a certain length User dened guards ie de ep guar ds are not allo w ed ERLANG The if clause executes guards and ev aluates the sequence corresp onding to the rst guard that succeeds In b oth case and if clauses it is considered an error of no patternguard matc hessucceeds BuiltIn F unctions Erlang has a n um b er of builtin functions BIFs needed and used for tasks that are not p ossible to program in Erlang itself Con v ersion b et w een data t yp es and pro cess creation see the follo wing section are examples of tasks that can b e done using BIFs See Armstrong et al for a complete listing Concurrency Erlang pro cesses are created dynamically using the builtin function spawn Pro cess comm unication is done b y async hronous message passing using the op erator The follo wing example sho ws ho w these features can b e com bined to start t w o pro cesses who send ping messages to eac h other Example moduleping exportstartloop start Pid spawnpingloop Pid spawnpingloop Pid ping Pid loop receive WhatWho Who Whatself loop end Messages whic h can b e an y Erlang terms are receiv ed selectiv ely b y a pro cess using the receive clause This construct susp ends the receiving pro cess un til a message arriv es that matc hes some pattern receive Pattern when Guard Sequence CHAPTER PRELIMINARIES Pattern when Guard Sequence PatternN when GuardN SequenceN after Time TimeOutSequence end Messages to a pro cess are queued up in a mailb ox When the pro cess en ters the receiv e clause the messages are matc hed in rst come rst serv ed order and the Sequence corresp onding to the matc hing Pattern is executed If a message in the mailb o x do not matc h an y pattern it is left in the mailb o x and the next message is c hec k ed If no message has arriv ed in Time milliseconds the TimeOutSequence is executed Distribution An Erlang system running one or more Erlang pro cesses is called a no de Sev eral Erlang no des can coexist and comm unicate on a single mac hine or on sev eral ma c hines in a net w ork The distribution facilities of Erlang ensure transparency ev en b et w een dieren t arc hitectures This means that pro cesses can b e spa wned remote co de managemen t can b e global and error handling can b e distributed Dynamic Co de Managemen t Erlang source co de is compiled and loaded on need in a p ermo dule basis Co de can b e recompiled and reloaded during execution of the system Pro cesses doing function calls with explicit mo dules eg listsappend will automatically use the latest loaded mo dule Other pro cesses will con tin ue to use the old co de Th us there ma y sim ultaneously exist more than one co de v ersion of a single mo dule in the system The BEAM Erlang implemen tation BEAM is one of the curren tly a v ailable implemen tations of Erlang It pro vides a run time en vironmen t and a compiler Erlang source co de can b e compiled in t w o w a ys to C co de and then b y a C compiler to ob ject co de or to threaded co de These sc hemes can b e mixed in the run time en vironmen t remem b er that mo dules are compiled separately W e ha v e used the threaded co de compiler and em ulator for dev elopmen t and debug ging and the compilation to C co de for nal execution F or details ab out the BEAM Erlang implemen tation see Hausman Chapter Design This c hapter describ es the design of Erlang FD ho w it is structured and ho w w e ha v e in terfaced with Erlang Erlang FD Structure User Pro cess on ml hi jk Constrain t Solv er Pro cess o o xy z The cen tral blo c k of Erlang FD is the con strain t solv er whic h is lo cated in a separate pro cess Allo cation of v ariables and telling of constrain ts are done b y sending messages to the solv er pro cess although this is not visi ble b y the programmer The execution of the user pro cess is th us separated ie preemptiv ely sc heduled b y Erlang from the solv er whic h has b oth negativ e and p ositiv e eects Robustness The user pro cess is not dep enden t on the solv er and ma y run concurren tly Easier to main tain a state of the solv er algorithm Easier to distribute the solv er Message sending o v erhead since all comm unication with the solv er uses mes sages Figure on the follo wing page sho ws the structure or Erlang FD The program mers source co de con tains constrain ts either arithmetic or directly stated as in dexicals When the program is compiled the arithmetic constrain ts are transformed in to library constrain ts Section on page whic h in turn consist of indexicals 1 T el l is explained in Section on page CHAPTER DESIGN Variables Arithmetic Constraints Indexicals Indexicals Variables Indexicals VariablesSource Program Compile Time Run Time Library Constraints Byte code Emulator User Process Solver Process Figure Design of Erlang FD ERLANG FD EMULA TOR INTERF A CE Consequen tly when a program has b een compiled its constrain ts consist solely of indexicals These indexicals are at runtime sen t to the constrain t solv er pro cess along with the nite domain v ariables the program allo cates The constrain t solv er pro cess running a propagation algorithm ev aluates the indexicals as they come in and prunes the domain of the v ariables See Section on page The propagation algorithm mak es calls to a b yte co de em ulator to ev aluate the ranges of the indexicals based on the curren t v alues of the nite domain v ariables This em ulator is describ ed in more detail in Section on page The in terface to the em ulator is based on BIFs and is describ ed in Section When ask ed for a solution a set of v alues for the nite domain v ariables the constrain t solv er nds a solution using a standard bac ktrac king sc heme Since Erlang do es not pro vide means for searc h neither bac ktrac king nor otherwise this had to b e implemen ted in the solv er See Section on page for details Erlang FD Em ulator In terface T o get an ecien t in terface to the em ulator whic h is written in C w e c hose to extend Erlang with a few BIFs gaining access to the em ulator whic h w as link ed in with the Erlang run time system These BIFs are describ ed in App endix A on page CHAPTER DESIGN Chapter Implemen tation Compilation of Arithmetic Constrain ts W e will no w consider t w o approac hes to handle nite domain arithmetic constrain ts The rst is based on compiling directly to indexicals The second whic h uses an in termediate represen tation called libr ary c onstr aints is the one used in our imple men tation Inlined Indexicals The straigh tforw ard w a y to compile a constrain t of sa y x y z is to extract eac h v ariable in turn and for eac h create an inlined indexical whic h main tains the relation from righ t to left only This tec hnique has previously b een used in Diaz and Co dognet Carlson and Carlsson Our example can b e expressed as three indexicals X in min z max y divu max z min x divd Y in min z max x max z min x Z in min x min y max x max y main taining intervalc onsistency see Section on page of the constrain t This indexical approac h has one ma jor dra wbac k the co de size for the required indexicals gro ws quadratically The amoun t of indexicals required is the amoun t of v ariables n and the size of the indexicals almost the same n making the gro wth O n CHAPTER IMPLEMENT A TION This fact mak es this w a y of expressing constrain ts unattractiv e for constrain ts with high arit y Library Constrain ts The problem with translating high arit y arithmetic constrain ts directly to indexicals comes from the fact that co de is v ery m uc h duplicated Eac h part of a term will o ccur almost iden tically in n of n indexicals This can b e a v oided b y in tro ducing in termediate v ariables a tec hnique whic h is exploited in this approac h The follo wing translation is done partly compiletime and partly runtime W e in tro duce a middlestep b et w een arithmetic constrain ts and indexicals called libr ary c onstr aints whic h denes the temp orary v ariables in terms of sub expressions of the arithmetic constrain t The metho d is dened and used in Diaz and Co dognet Carlson and Carlsson arithmetic expressions compiletime library constrain ts runtime indexicals The library constrain ts are in fact ordinary Erlang functions consisting solely of indexicals These indexicals main tain in terv alconsistency on the argumen ts to the function T able sho ws in an abstract manner the library constrain ts w e ha v e used x y and t are v ariables a b and c are constan ts App endix D on page includes their implemen tation x t where f g x c where f g ax t x y t ax c t x c where f g t x c where f g ax by t T able Library constrain ts Cho osing whic h library constrain ts to use is a balance b et w een in tro ducing a lot of indexicals or in tro ducing a lot of in termediate v ariables Simple library constrain ts reduce the n um b er of indexicals created but in turn the comp osition of these library constrain ts requires more in termediate v ariables Hyp othetically sp eaking using ar bitrarily complex library constrain ts means a v oiding comp osition whic h is equiv alen t to compiling directly to indexicals as in Section on the preceding page COMPILA TION OF ARITHMETIC CONSTRAINTS Compiling arithmetic expression in to library constrain ts is here done in three steps as sho wn b elo w Strict arithmetic relations and are eliminated from the arithmetic ex pression This is done b y replacing expressions A B with A B and A B with A B The expression is normalized A normalized expression is on the form S j T i where S n x n k x k T n k x k n n x n f g and either j or i is zero and the other is The normalized expression is nally decomp osed in to the appropriate library constrain ts The nal step is w orth some in v estigating Decomp osing a normalized expression can either b e done using line ar or lo garithmic de c omp osition A simple example will illustrate these tec hniques whic h are due to Carlson and Carlsson Example The term a x x x can either b e decomp osed line arly as x x t t x t t x t t x t t x a or lo garithmic al ly as x x t x x t x x t t t t t t a Both generate the same amoun t of library constrain ts the dierence sho ws during execution A c hange made to v ariable x propagates through the library constrain ts to aect a Using the line ar de c omp osition this will reev aluate all v e constrain ts This is not the case with the lo garithmic de c omp osition whic h will only reev aluate three This tec hnique is similar to using trees instead of lists in ordinary data structures CHAPTER IMPLEMENT A TION Inlined Indexicals vs Library Constrain ts The c hoice b et w een using inlined indexicals or library constrain ts is not ob vious Our implemen tation is based solely on library constrain ts but probably a mixture w ould b e preferable Arithmetic constrain ts with small arit y can b e compiled as inlined indexicals while constrain ts with high arit y can b e compiled as library constrain ts This w ould not in tro duce in termediate v ariable when unnecessary Another question when using library constrain ts is that of consistency W e kno w that individual library constrain ts ensures in terv alconsistency but is this prop ert y preserv ed when library constrain ts are comp osed using in termediate v ariables Prop osition Compilation of linear arithmetic expressions ensures in terv alconsistency for these constrain ts regardless if compiled to inline indexicals or to library con strain ts Consider a small example of propagation comparing inlined indexicals and library constrain ts Example Consider a constrain t X x x x x x x x f g x f g and X undened The follo wing propagation is ac hiev ed using inlined indexicals and library constrain ts resp ectiv ely The expression is logarithmically decomp osed as library constrain ts t x x t x x and X t t Inlined Indexical Library Constrain ts V alue of X X f g t 1 f g t 2 f g X f g x 2 f g added X f g t 1 f g t 2 f g X f g X f g added x 1 f g x 2 f g t 1 f g t 2 f g x 3 f g x 4 f g x 1 f g x 2 f g x 3 f g x 4 f g By noting that inf inf e sup e inf e and that sup inf e sup e sup e w e see that upp er and lo w er b ounds in terv als propagate correctly through in terme diate v ariables and th us library constrain ts preserv e the in terv alconsistency prop ert y when comp osed EQUIV ALENT INDEXICALS Equiv alen t Indexicals Tw o indexicals are considered e quivalent i one is en tailed whenev er the other is This is often the case in library constrain ts F or example the library constrain t xyXY fdtell X in minYmaxY Y in minXmaxX con tains t w o indexicals whic h are equiv alen t Erlang FD treats t w o indexicals as equiv alen t if they o ccur in the same fdtell statemen t in the source co de see the User Man ual in App endix B on page The equiv alence prop ert y is exploited in an optimization see Section on page The Propagation Algorithm The core of the constrain t solv er is the propagation algorithm It ensures some lev el of consistency in the constrain t solv er b y ev aluating indexicals and pruning v ariables The basic idea is as follo ws V ariables reside in the constrain t solv er connected to eac h other b y constrain ts The constrain ts are expressed as indexicals The domains of v ariables are pruned b y the ev aluation of indexicals and this triggers other indexicals whic h prune some v ariables etc As y ou migh t ha v e noticed b y the description this is in man y w a ys similar to the A C Algorithm on page The dierence is that A C propagates and queues directed binary constrain ts while w e use indexicals A naiv e algorithm is presen ted in Algorithm on the follo wing page Q is a queue of pruned v ariables Some notes on the algorithm The algorithm terminates when the queue of pruned v ariables is empt y V ari ables are queued when they are pruned V ariables ha v e indexicals susp ende d on them and it is these susp ended index icals that are reev aluated when a v ariable is tak en from the queue F or a v ariable x ev ery indexical X in r where x o ccurs in r is susp ended on x The motiv ation these indexicals ma y need to b e reev aluated if x is pruned 1 By this remark w e simply mean that it do es not ensure satisabilit y or ev en arcconsistency alw a ys The lev el of consistency ac hiev ed dep ends on the indexicals and ho w w ell they propagate constrain ts b et w een v ariables CHAPTER IMPLEMENT A TION Algorithm A simplistic propagation algorithm prop Q BEGIN WHILE Q not empty DO Q Q n f y g S suspended indexicals on y FOR each X in r in S DO I x r CASE I of IF r monotone in THEN fail ELSE continue x IF r antimonotone in THEN mark the indexical entailed and continue otherwise IF r not monotone in THEN continue f x I g Q Q x END Remem b er that x is a notation for the domain of x in and r is the range r ev aluated in If a monotone indexical ev aluates to the empt y set the algorithm returns with failure An empt y domain of a v ariable implies that there is no solution to the constrain t problem An an timonotone indexical one whose range gro ws is simply ignored if it ev aluates to the empt y set An an timonotone indexical whose v ariable domain b ecomes a subset of its range is mark ed entaile d and will nev er b e ev aluated again Since its range only gro ws it will b e satised in an y extension of When the domain of a v ariable x has b een pruned in x is queued In Section on page w e presen ted A C an arcconsistency algorithm What w e ha v e describ ed in this section is something similar but not iden tical in aim con text and p erformance THE PR OP A GA TION ALGORITHM Con text A C deals with arcs ie directed binary constrain ts and c hec ks that single v alues are c onsistent with those constrain ts Our propagation algorithm is more sp ecic and has co ded the constrain ts as indexicals instead of c hec king constrain ts as in A C w e ev aluate indexicals Instead of remo ving single v alues w e prune v ariable domains Aim A C ensures arcconsistency Our propagation algorithm do es not The lev el of consistency ac hiev ed here dep ends on the indexicals stated and when they are ev aluated in turn dep ending on their monotonicit y prop ert y Eciency In similarit y to A C our propagation algorithm do es not reev aluate all con strain ts indexicals but only those that ha v e a c hance to p erform some pruning some v ariable domain in the range expression of the indexical ha v e c hanged Ev en more can b e done as w e shall see in Section Constrain t arit y Since w e are no w co ding constrain ts as indexicals w e are able to handle con strain ts of greater arit y than t w o The next section in tro duces the optimizations in the algorithm Propagation Optimizations Here w e describ e the optimizations implemen ted V ariable Dep endencies V ariable dep endencies are an optimization exploited in this implemen tation of the indexical sc heme It reduces the amoun t of indexicals ev aluated b y the pruning of a v ariable Eac h v ariable has a list of indexicals susp ended on it These are ev aluated eac h time a pruning has b een made to the domain of the v ariable Man y of the indexical ev aluations will not ha v e an y eect T o reduce this w aste of time w e attac h a dep endency atom with eac h susp ended indexical F urthermore eac h time a v ariable is pruned a pruning atom is calculated These dep endency atoms and pruning atoms are one of the follo wing CHAPTER IMPLEMENT A TION A tom Meaning as indexical dep endency Meaning as pruning none Indexical not aected of v ariable not used since suc h indexicals are not ev en attac hed No pruning w as made to the v ariable int Indexical aected when v ariable b ecomes determined Pruned int V ariable w as pruned to a single in teger determined min Indexical aected when v ariable is pruned min minmax or int V ariable w as pruned of one or more of its lo w er v alues max Indexical aected when v ariable is pruned max minmax or int V ariable w as pruned of one or more of its upp er v alues minmax Indexical aected when v ariable is pruned min max minmax or int V ariable w as pruned of b oth lo w er and upp er v alues dom Indexical aected when v ariable is pruned an ything but none V ariable w as pruned of v alues inside its domain According to the rules in the ab o v e table an indexical is ae cte d and th us re ev aluated only when the pruning triggers the dep endency atom Note that the dep endencies min max and minmax are triggered b y an int pruning ie a v ariable b e comes determined This is due to the fact that these indexicals ma y b ecome en tailed and that should b e c hec k ed for since w e then ma y trigger the next optimization En tailed Marking Equiv alen t indexicals Section on page share a common en tailed ag as sho wn in Section on page Using this a v oids the o v erhead of ev aluating indexicals whic h are already en tailed When one of t w o or more equiv alen t indexicals is en tailed none of them will b e ev aluated again V ariable Queue treated as a Set When a v ariables domain is pruned it is to b e queued b y the propagation algorithm There is ho w ev er no need to queue the v ariable if it is already in the queue Therefore w e c hec k if the v ariable is in the queue b y examining a b o olean ag eac h v ariable has see Section on page on data structures If it already is in the queue w e only com bine its old pruning information with the new pruning since they ma y dier T able on the facing page sho ws ho w the up dating pro cedure is done b et w een an old pruning P and a new pruning P 0 It preserv es the prop ert y that all indexicals for either pruning old and new are to b e triggered b y the com bined pruning That is the com bined pruning is in some sense the strongest of the t w o prunings COMPILING AND EV ALUA TING RANGES Result PNONE PDOM PMIN PMAX PMINMAX PINT PNONE NONE DOM MIN MAX MINMAX INT PDOM DOM DOM MIN MAX MINMAX INT PMIN MIN MIN MIN MINMAX MINMAX INT PMAX MAX MAX MINMAX MAX MINMAX INT PMINMAX MINMAX MINMAX MINMAX MINMAX MINMAX INT PINT INT INT INT INT INT INT T able Com bination of prunings The Optimized Propagation Algorithm W e no w presen t our propagation algorithm as it lo oks with the optimizations de scrib ed in Section on page added In Algorithm on page Q is a queue of pruned v ariables and is our constrain t store Compiling and Ev aluating Ranges In the propagation algorithm describ ed earlier in Algorithm on page ev aluation of a range r in is referred to as r In this section w e describ e ho w this ev aluation is p erformed The ev aluation of ranges in our solv er is prepared for at compile time b y compiling the range expression of the indexical to b yte co de for an abstract mac hine Up on ev aluation an em ulator for this abstract mac hine executes the b yte co de Section is an o v erview of the em ulator while the compilation to b yte co de is describ ed in on page Ho w the monotonicit y information is extracted is describ ed in on page The Em ulator The range em ulator in our implemen tation originates in the AKLFDw ork carried out b y Bj orn Carlson for his PhD thesis Carlson The source co de has b een somewhat mo died and adapted to t in to the runtime en vironmen t of Erlang The in terface to the em ulator in through BIFs and they are describ ed in App endix A on page The FD em ulator ev aluates ranges in a store ie giv en a range r it computes r F urthermore it p erforms the in tersection x r as sho wn in Algorithm on page W e use a simpleminded abstract mac hine where the em ulator is stac k based Eac h FD op erator is in terpreted b y a corresp onding instruction whic h tak es its argumen ts from the stac k CHAPTER IMPLEMENT A TION c i Action const v j c i i i val k c i v j a k i i dom k c i v j dom a k i i dom min k c i v j min a k i i dom max k c i v j max a k i i range n v j m v j v j n m i i set add d v j n v j v j d n i i set sub d v j n v j v j d n i i union d v j d 0 v j v j d d 0 i i inter d v j d 0 v j v j d d 0 i i diff d v j d 0 v j v j d n d 0 i i check if v j equals then j j i c i else i i set mod d v j m v j v j d mo d m i i add n v j m v j v j n m i i sub n v j m v j v j n m i i mult n v j m v j v j n m i i divu n v j m v j v j d nm e i i divd n v j m v j v j b nm c i i mod n v j m v j v j n mo d m i i min d v j v j min d i i max d v j v j max d i i size d v j v j size d i i halt return T able Byte co de instructions COMPILING AND EV ALUA TING RANGES Algorithm An optimized propagation algorithm prop Q BEGIN WHILE Q not empty DO Q Q n f y g S suspended indexicals on y FOR each f X in r in S DO IF f is marked entailed THEN continue IF f not affected by the pruning of y THEN continue I x r CASE I of IF r monotone in THEN fail ELSE continue x IF r antimonotone in THEN mark the indexical entailed and continue otherwise IF r not monotone in THEN continue f x I g IF x queued THEN update pruning of x ELSE Q Q f x g set pruning of x IF r constant in THEN mark f as entailed END The em ulator is pro vided with the b yte co de and the call frame a for the co de represen ted b y a v ector of domain v ariables F urthermore the em ulator op erates on three data areas the co de area c the v alue stac k v con taining in tegers or references to domains and the domain heap d con taining all in terv als and sets constructed in the em ulation A t eac h in v o cation of the em ulator d is assumed empt y Hence all memory in d is automatically reclaimed at eac h in v o cation CHAPTER IMPLEMENT A TION Let i b e the curren t co de index and j the curren t top of the v alue stac k The instructions are straigh tforw ard and dened in T able on page where c i is the curren t instruction dispatc hed on d and d 0 denote domains m and n denote in tegers and the arithmetic op erators are applied p oin twise where appropriate Besides computing the set and the in tersection our em ulator calculates the pruning made to the target v ariable This information is used as an optimization in our propagation algorithm see Section on page Compiling to Byte Co de The translation of a range r in to b yte co de is straigh tforw ard and is dened recur siv ely b y T able Basically a p ostx P olish notation is used where w e assume r T r t t T t 2 T t 1 range dom x dom A x r r T r 2 T r 1 set add r r T r 2 T r 1 set sub r r T r 2 T r 1 union r r T r 2 T r 1 inter r n r T r 2 T r 1 diff r r T r 1 check l T r 2 l r mo d x T x T r 0 set mod t T t n const n x val A x t t T t 2 T t 1 add t t T t 2 T t 1 sub t t T t 2 T t 1 mult t t T t 2 T t 1 div t mo d x A x T t 0 mod min x dom min A x max x dom max A x min r T r min max r T r max size r T r size T able T ranslation of ranges and terms to b yte co de that an argumen t mapping A x is giv en suc h that A x equals the p osition of x in the argumen t frame The b yte co de for a range r is alw a ys terminated with a halt instruction Determining Monotonicit y of Indexicals When ev aluating an indexical w e m ust kno w whether it is monotone or an timonotone Section on page The propagation algorithm in Section on page uses the monotonicit y information T o mak e the monotonicit y c hec k easier at runtime w e prepare at compiletime b y iden tifying those v ariables in the range that need to b e determined for the range to b e monotone This is done recursiv ely as indicated b y the follo wing tables COMPILING AND EV ALUA TING RANGES T able denes t w o sets S t G t con taining the v ariables that m ust b e determined for a linear term to decreaseincrease with extensions of x is a function whose v alue is if x is a n um b er and f x g if x is a v ariable t S t G t x x x t t S t 1 S t 2 G t 1 G t 2 t t S t 1 G t 2 G t 1 S t 2 x t S t x G t x x t G t x S t x tx S t x G t x t x G t x S t x t mo d x S t x G t x min x x max x x size x x min r M r max r A r size r A r T able Monotonicit y of term expressions T able builds on the previous denition of shrinkinggro wing v ariable sets for terms and denes the monotonicit y prop ert y for ranges F or example a range t t is monotone if t gro ws and t shrinks and th us is monotone if G t 1 S t 2 is determined r M r A r t t G t 1 S t 2 S t 1 G t 2 dom x x r r f g M r 1 M r 2 A r 1 A r 2 r n r M r 1 A r 2 A r 1 M r 2 r x f mo d g M r x A r x T able Monotonicit y of range expressions The computation outlined b y the recursiv e rules ab o v e is p erformed at compiletime and is annotated to the indexicals set at runtime see Chapter on page for con text Using these M r and A r sets w e can at runtime in v ok e a simple and ecien t algo rithm for determining the monotonicit y see Algorithm on the next page Note that when all v ariables in M r A r are determined in M A will b e in and all extensions of CHAPTER IMPLEMENT A TION Algorithm The monotonicit y algorithm monotonicity M r A r M M r n f x x deter mined in g A A r n f x x deter mined in g IF M A THEN RETURN constant IF M THEN RETURN monotone IF A THEN RETURN antimonotone Searc hing for Solutions The propagation algorithm previously describ ed in Section on page ac hiev es and main tains consistency This is w ell but not enough Not only do w e need a consisten t constrain t store whic h propagates constrain ts and prunes v ariable domains w e also need to nd sp ecic solutions to our stated constrain t problem A Bac ktrac king Sc heme The state of the constrain t store is that w e ha v e some v ariables with more or less pruned domains eg X f g and Y f g Along with them there are a bunc h of constrain ts as indexicals Remem b er that since our solv er is not c omplete ie the propagation algorithm do es not ensure satisabilit y not alw a ys arcconsistency either not all com binations of v alues from the v ariable domains are solutions T o nd those com binations whic h are true solutions w e use searc h W e pic k a v ariable and instan tiate it to some v alue from its domain Then w e propagate this and ma yb e get some pruning on other domains W e pic k another etc and rep eat this un til w e ha v e determined all v ariables and w e ha v e a solution Inheren t in this sc heme is the c hoice of v ariable to instan tiate and to what v alue These c hoices create c hoice p oin ts in our bac ktrac king based searc h Figure on the next page sho ws the en tities used to implemen t the bac ktrac king A c hoice p oin t is created on the choic e p oint stack eac h time w e pic k a v ariable and a v alue During the propagation w e sa v e data of v ariables and indexicals on the tr ail stack This is depicted as data in the gure The data on the trail stac k is separated b y marks choice to indicate where eac h new c hoice p oin t b egins The dashed arro ws indicate that these marks implicitly refer to c hoice p oin ts Using the data on the trail stac k w e ma y later undo the c hanges made to v ariables and indexicals ie b ack up to the previous c hoice p oin t This is necessary when w e SEAR CHING F OR SOLUTIONS Choice Point Stack {Var1, NextVal, RestOfVars} {Var2, NextVal, RestOfVars} Trail Stack choice choice choice Figure T rail and c hoice p oin t stac k in the bac ktrac king sc heme nd that the curren t instan tiation of v ariables is not a solution or when w e w an t more than one solution to our problem The data on the tr ail stack is either data from a v ariable or an indexical The follo wing table sho ws whic h parts that are trailed F or more details on what they represen t see Section on the follo wing page on data structures V ariable f Var Erlang p oin ter to the v ariable Queued flag Domain Trailed flag g CHAPTER IMPLEMENT A TION Indexical f Ind Erlang p oin ter to the indexical Entailed flag M A g The Trailed ag is true for a v ariable if the v ariable has b een sa v ed on the trail stac k since the last c hoice p oin t This is used as a timespace optimization a v ariable is nev er trailed t wice for a giv en c hoice p oin t V ariable Ordering Our implemen tation has no sp ecial heuristic for c ho osing the v alue for v ariable but w e ha v e made use of t w o standard tec hniques from CSP see eg Tsang for an o v erview of suc h heuristics to c ho ose the v ariable to instan tiate naive and rstfail Naiv e Naiv e lab eling c ho oses the rst v ariable at hand th us making the c hoice more or less random FirstF ail Firstfail lab eling c ho oses the v ariable with the smallest domain or the largest amoun t of constrain ts susp ended on it This heuristic is dynamic c hec k for smallest domain is made at runtime and suggests that the task whic h is most lik ely to fail should b e p erformed rst Searc h can b e a v oided b y recognizing deadends as so on as p ossible This tec hnique is useful only when nding one or a few solutions to a problem when searc hing for all solutions w e ha v e to tra v erse the en tire searc h space and it will not matter in whic h order w e do it The p erformance dierence b et w een these heuristics are all but negligible Some tim ings for actual problems can b e found in Section on page The implemen tation of these heuristics can b e found in App endix D on page Data Structures This section presen ts the represen tation of our data structures variables domains and indexic als D A T A STR UCTURES Finite Domain V ariables There are actually t w o represen tations of a nite domain v ariablethe represen tation in the user pro cess and the represen tation in the solver pro cess The nite domain v ariable is represen ted as a tuple consisting of the follo wing parts Solv er f fd var A tom iden tifying t yp e of structure Reference Unique structure iden tifying this instance of t yp e nite domain v ariable Common to the user and solv er represen tation of the v ariable and th us common to the user pro cess and solv er pro cess Used when transferring v ariables b et w een usersolv er pro cesses Indexicals List of susp ended indexicals Trailed Bo olean ag indicating if v ariable has b een trailed since the last c hoice p oin t Domain The domain of the v ariable See Section Queuedflag Bo olean ag true if v ariable is queued in the propagation algo rithm see Algorithm on page Pruning One of f noneintminmaxminmaxdom g T ells the t yp e of the last pruning g User f fd client var A tom iden tifying t yp e of structure Reference Unique structure iden tifying this instance Same as in the solver represen tation ab o v e g Finite Domains A nite domain in Erlang FD is either an Erlang in teger or a tuple of the follo wing format f fd dom A tom indicating that this tuple represen ts a nite domain Type Either interval or set Lower Lo w er b ound dened if in terv al or set Upper Upp er b ound dened if in terv al or set Bitvector Bitv ector dened if set only g CHAPTER IMPLEMENT A TION Finite Domain Indexicals The represen tation is a tuple f fd ind A tom indicating that this tuple represen ts an indexical Reference Unique iden tier X T arget v ariable of the indexical Args tuple Argumen t v ariables in the indexical range Deps tuple Dep endencies see Section on page for the argumen t v ariables Byte Code Byte co de for ev aluating the range expression of the indexical in the em ulator f Entailed g Flag set if indexical is en tailed This ag is shared b et w een sev eral equiv alen t indexicals th us residing inside a tuple allo wing one to preserv e the sharedness using destructiv e up date M Monotonicit y set Mr A An tiMonotonicit y set Ar g Chapter Ev aluation In the follo wing w e ev aluate the execution sp eed of Erlang FD compared to other constrain t solv ers namely SICStus FD and AKL FD Our b enc hmark programs are a suite of more or less articial programs but in some resp ect represen tativ e for the class of problems that nite domains constrain t solv ers are aimed for Benc hmark Programs The programs are the follo wing a more complete description and a solution in Erlang FD can b e found in App endix C on page Queens The problem of placing n queens on a n n c hess b oard suc h that no t w o queens threaten eac h other Consists solely of indexicals expressing dierence b et w een v ariables Send More Money The task is to assign n um b ers to letters suc h that the equation S E N D M O R E M O N E Y holds Consists of library constrain ts and all different in Erlang FD and AKL FD F or SICStus FD w e sho w b oth this approac h and the library constrain ts replaced with inlined indexicals Fiv e Houses A logic puzzle Consists of library constrain ts all different and indexicals in Erlang FD AKL FD uses inlined indexicals and all different as do SICStus FD T o express the disjunction Erlang FD and AKL FD uses indexicals while SICStus FD mak e use of cardinalit y reasoning CHAPTER EV ALUA TION T en equations A system of linear arithmetic equations with a single solution Library con strain ts are used in Erlang FD and AKL FD F or SICStus FD w e sho w inlined indexicals to o Tw en t y equations A system of linear arithmetic equations with a single solution Library con strain ts are used in Erlang FD and AKL FD F or SICStus FD w e sho w inlined indexicals to o Alpha Assigning n um b ers to letters Consists of library constrain ts and all diff erent in Erlang FD AKL FD has all different plus a mixture of indexicals and library constrain ts Both library constrain ts and inlined indexi cals are sho wn for SICStus FD Magic Series Computing magic series Consists of library constrain ts in all three solv ers Suudoku Assigning distinct n um b ers to squares in a grid Solely all different for all solv ers P erformance Figures The problem name is annotated with the amoun t of solutions requested one or all the v ariable ordering see Section on page naiv e or FirstF ail inl if compilation to inlined indexicals are p erformed and nally ind if sp ecial purp ose indexicals are used The columns are as follo ws F ails The n um b er of times indexicals failed ev aluated to the empt y set and the searc h had to bac ktrac k Pruned The n um b er of times the ev aluation of an indexical pruned the domain of a v ariable Useless The n um b er of times the ev aluation of an indexical resulted in neither pruning of a v ariable domain nor failure These indexical ev aluations are useless DISCUSSION Time The execution time of the problem milliseconds this gure ha v e b een tak en from the execution on a SP AR Cstation with Megab ytes of RAM PT The ratio pruned domains p er millisecond In some sense the sp eed of the propagation algorithm Not comparable if dieren t compilation metho ds for arithmetics are used ie inlined indexicals and library constrain ts Problem F ails Pruned Useless Time PT Queensonenaiv eind Queensoneind Queensallnaiv eind Queensallind Queensonenaiv eind Queensoneind SendMoreMoney onenaiv e Fiv e Housesonenaiv eind Fiv e Housesoneind Equationsonenaiv e Equationsone Equationsonenaiv e Equationsone Alphaone Magiconenaiv e Magiconenaiv e Magicone Magicone Suudokuonenaiv e Suudokuone T able Erlang FD execution sp eed Discussion W e will here giv e some analyzing commen ts to the gures giv en in the previous section As y ou ma y ha v e noticed w e presen ted no gures regarding the eect of the v arious optimizations describ ed in Section on page suc h an analysis can b e found in Carlson W e will start with some questions and answ ers 1 The gures regarding AKL FD are not executed on the same mac hine but are scaled appropriately CHAPTER EV ALUA TION Problem F ails Pruned Useless Time PT Queensonenaiv eind Queensoneind Queensallnaiv eind Queensallind Queensonenaiv eind Queensoneind SendMoreMoney onenaiv e SendMoreMoney onenaiv einl Fiv e Housesonenaiv e Fiv e Housesone Equationsonenaiv e Equationsonenaiv einl Equationsone Equationsoneinl Equationsonenaiv e Equationsonenaiv einl Equationsone Equationsoneinl Alphaone Alphaoneinl Magiconenaiv e Magiconenaiv e Magicone Magicone Suudokuonenaiv e Suudokuone T able SICStus FD execution sp eed Wh y do fails dier b et w een naive and rstfail lab eling As w e p oin ted out in Section on page the c hoice of v ariable ordering is crucial for the eciency when nding a single solution but almost negligible when w e are tra v ersing the en tire searc h space This is clear b y the timing of Queens and Queens ab o v e Wh y do fails dier b et w een rstfail lab eling in dieren t solv ers Their rstfail algorithm is not iden tical only similar A small c hange of strat egy in v ariable c hoice can ha v e big impact on certain problems Wh y do fails dier b et w een naive lab eling in dieren t solv ers This happ ens if the problem form ulations are dieren t making the programs express dieren t lev els of consistency F or example tak e Fiv e Houses where SICStus FD uses a dieren t strategy for expressing disjunction compared to AKL FD and Erlang FD DISCUSSION Problem F ails Pruned Useless Time PT Queensonenaiv eind Queensoneind Queensallnaiv eind Queensallind Queensonenaiv eind Queensoneind SendMoreMoney onenaiv eind Fiv e Housesonenaiv einlind Fiv e Housesoneinlind Equationsonenaiv e Equationsone Equationsonenaiv e Equationsone Alphaone Magiconenaiv e Magiconenaiv e Magicone Magicone Suudokuonenaiv e Suudokuone T able AKL FD execution sp eed Wh y do pruned domains dier b et w een inline d indexic als and libr ary c onstr aints Ob viously the n um b er and the t yp e of indexicals dier in the t w o approac hes whic h has an eect on the n um b er of prunings p erformed though it do es not ha v e an y eect on the n um b er of fails since b oth approac hes main tain interval c onsistency see Section on page As w e men tioned previously using library constrain ts solely see Section on page it is far from optimal and a mixture is preferable as in AKL FD Carlson Before lo oking at the dieren t gures for fails and prunings y ou probably noticed that Erlang FD is m uc h slo w er compared to AKL FD and SICStus FD The p erformance gap to SICStus FD is a factor ranging from to dep ending on the problem with an a v erage v alue of The factor to AKL FD ranges from to with an a v erage of In Section on the follo wing page w e describ e the dierences b et w een the solv ers and in Section on the next page w e sho w in what sections the time is sp en t in Erlang FD 2 The execution times used for SICStus FD are those using library constrain ts If instead c ho osing the gures for the inlined indexicals v ersion the a v erage v alue is ab out : CHAPTER EV ALUA TION Dierences Bet w een The Solv ers W e here giv e a short listing of the dierences b et w een the nite domain constrain t solv ers compared Erlang FD SICStus FD and AKL FD Erlang FD SICStus FD AKL FD Inlined indexicals vs library constrain ts Uses library constrain ts solely Uses either congurable b y the user when compiling Uses a mixture dep ending on the arit y of the constrain t Implemen tation language Range em ulator in C propagation algorithm in Erlang T railedbased bac ktrac king searc h in Erlang A total of lines of Erlang co de and lines of C co de Range em ulator in C propagation algorithm mainly in Prolog but with some more exp ensiv e functions co ded in C Prologs standard trailedbased bac ktrac king searc h is used A total of lines of Prolog co de and lines of C co de En tirely in C T railedbased bac ktrac king searc h in C not using cop yingbased searc h a la AKL Propagation optimizations V ariable dep endencies en tailed ag v ariable queue with unique v ariables As Erlang FD unique susp ension lists for eac h dep endency and v ariable main tains a queue of indexicals instead of v ariables As Erlang FD time stamps for indexicals Summarizing the basis propagation of indexicals are alik e but the implemen tation tec hnique and implemen tation lev el dier somewhat Proling Erlang FD In this section w e do a proled execution of Erlang FD running the en tire suite of b enc hmarks There is a to ol eprof for Erlang used to prole the execution of Erlang PR OFILING ERLANG FD co de but unfortunately it requires an Erlang implemen tation and Erlang FD is implemen ted using Erlang BEAM W e then use gprof and get a view of the time sp en t from C lev el T able sho ws the most time consuming functions The rst column Time is in p ercen t of the total execution time the second column is the n um b er of calls made and the third column denotes the a v erage time sp en t p er call in milliseconds The three righ tmost columns Time Calls msCalls Name R T E C gc p indexical propagate p fd mon monotonicit y p fd dyn tup elemen t p do mixed comp p fd mon remo v e determined p ev aluate range p elemen t p fd trail trail ind p sc hedule p lo okup v ar p c hange heap p fd trail trail v ar p size p eq p in tersect fd p cop y struct p T able The most time consuming functions in Erlang FD mark if the function is executed within Erlangs runtime system Erlang FD co de written in Erlang or Erlang FD co de written in C The last column is th us the functions evaluate range and intersect fd whic h b elong to the range em ulator of Erlang FD By summing up the t w o righ tmost columns one ma y notice that of the time sp en t executing Erlang FD is sp en t on running co de written in Erlang Th us the time sp en t executing Erlang FD co de written in C is less than of the total time This gure if considering all functions not just the most time consuming whic h is sho wn here shrinks ev en more to ab out of the total time 3 Of course Erlang FD runs on JAM to o but is ab out times slo w er and th us the proling information is not reliable regarding the ratio b et w een time sp en t in C and Erlang 4 Including BIFs called from within Erlang co de CHAPTER EV ALUA TION Summary and P ossible Impro v emen ts W e ha v e dev elop ed a constrain t solv er with p o or p erformance gures compared to existing solv ers in AKL and SICStus Prolog The ma jorit y of the execution time is sp en t on Erlanglev el Time sp en t on Clev el is almost negligible The time sp en t running Erlang co de is fairly w ell spread o v er the en tire propagation algorithm there are no single functionstasks resp onsible for more than What c hanges should b e made to impro v e p erformance W ell there are quite a few implemen tation c hoices and constrain ts that aect the p erformance Here w e will consider implementation factsimpro v emen ts related to the curren t indexical sc heme see Section on page for ideas in general to impro v e the eciency of solving nite domain constrain ts Represen tation of abstract data t yp es Finite domain v ariables and indexicals are represen ted as tuples This is natural and ecien t but the in terface to these structures could b e impro v ed As of no w ev ery access to a nite domain or indexical triggers a function call Small tests ha v e indicated that replacing these functions with macros to a v oid the function call o v erhead could impro v e o v erall p erformance with Another c hoice w ould b e to use records tuples with named elds whic h are presen t in the JAM Erlang implemen tation and whic h w e b eliev e are to b e in tro duced in forthcoming v ersions of the Erlang language Cyclic structures The implemen tations of Erlang w e ha v e used BEAM and JAM do es not supp ort cyclic data structures This is unfortunate since the v ariables and indexicals naturally form a cyclic graph in the memory The lac k of cyclic structures forces us to use a clumsy and somewhat inecien t v ariable database where lo okups for v ariables are done when ev aluating the range of an indexical This is exp ensiv e as can b e seen in the table ab o v e The function fd dyntup element is the one used to mak e lo okups in this database whic h is implemen ted as a dynamically gro wing tuple Bac ktrac king Bac ktrac king with c hoicep oin t stac k and trail w ould not ordinarily b e imple men ted in a highlev el language The reason for co ding the searc h in Erlang w as t w ofold T o a v oid problem with the garbage collection mec hanism and to mak e it easier to exp erimen t with dieren t searc h strategies Implemen tation language W e b eliev e that our c hoice of Erlang as main implemen tation language coun ts 5 Constrain ts imp osed b y the Erlang language and its implemen tation w e are not referring to nite domain constrain ts Nice for a c hange ::: SUMMAR Y AND POSSIBLE IMPR O VEMENTS for a large part of the p erformance dierence compared to AKL FD en tirely in C and SICStus FD most of the more exp ensiv e functions in C With a larger part of the Erlang FD co de written in C p erformance could b e impro v ed generally T o mak e it easier to use C for extensions lik e Erlang FD Erlang should b etter supp ort in terfacing to the sc heduler and the garbage collector as AKL do es With suc h primitiv es an ecien t searc h could b e implemen ted in C Along with implemen ting the propagation algorithm in C Erlang FD w ould b e ap pro ximately as fast as AKL FD pro vided that the o v erhead caused b y lac k of cyclic structures could b e eliminated Propagation optimizations The are a n um b er of small tric ks that can b e applied to the propagation of index icals that w e ha v e not made use of Some of them are exploited in SICStus FD Before queueing a v ariable with pruning P w e could c hec k that there an index ical susp ended that will b e triggered b y P If not there is no need to queue the v ariable V ariables can ha v e sev eral susp ension lists one for eac h dep endency t yp e This w ould mak e the aected calculation more ecien t CHAPTER EV ALUA TION Chapter Conclusion W e end this rep ort b y summarizing our w ork and p eek forw ard to see what can and what will b e done in the future Summary This rep ort ha v e describ ed the w ork of em b edding nite domain constrain t in to the functional programming language Erlang W e ha v e extended the expressiv eness of the language b y allo wing arithmetic expressions to b e stated as facts and dev elop ed a solv er for generating solutions satisfying these facts as constrain ts Our p erformance ev aluation and comparison to other constrain t solv ers sho ws that Erlang FD lac ks in p erformance With resp ect to the fact that the gap is quite large w e ha v e p oin ted out p ossible w eaknesses in the implemen tation and suggested solutions Of our goals with this w ork w e succeeded with all but one There w as not time to implemen t the ask primitiv e and th us our vision of pro cesses in teracting with the constrain t store lik e agen ts in concurren t constrain t programming w as not fullled W e still think that this is p ossible and that the expressiv eness of Erlang w ould gain from it The follo wing section is concerned with the further dev elopmen ts of constrain ts in Erlang and constrain t solv ers in general CHAPTER CONCLUSION F uture W ork With the history of Constrain t Satisfaction Problems and the ev olution of Constrain t Logic Programming in mind w e will here try to p oin t at some p ossible uses and ap proac hes regarding constrain t solv ers in general and constrain ts in Erlang esp ecially F uture Dev elopmen t of Erlang FD First one of the ma jor tasks with further dev elopmen t on Erlang FD w ould b e to gain p erformance Although this is not the single k ey to mak e constrain ts in Erlang useful one m ust sho w reasonable eciency Being appro ximately a magnitude slo w er than comparable solv ers is not acceptable for realw orld programs Secondly the askprimitiv e should b e designed and implemen ted Its seman tics is not as ob vious as in CLP since there is no searc h in Erlang to in teract with as it do es in logic programming Finally the aim of em b edded constrain ts in a language lik e Erlang should b e to blend and help with the kind of tasks that Erlang are used to solv e W e imagine the primary use of constrain ts in Erlang w ould b e of seman tics not on ra w sp eed In eg soft realtime systems lik e telecomm unication and sim ulation there are other demands What is almost en tirely lac king in solv ers of to da y are in teractivit y user con trol execution time estimates preemptiv e searc h and reactivit y Pro cesses in teracting with the solv er should b e able to b oth add and remo v e constrain ts con trol the searc h and through the constrain t store aect other pro cesses These are all features that w ould distinguish a constrain t solv er in Erlang from others and at the same time blend nicely with other prop erties of the language Ongoing W ork with Constrain t Solv ers W e are curren tly b eginning w ork on constrain ts main taining a greater lev el of consis tency than arc and in terv alconsistency Consider for example the all different constrain t This is a t ypical case where one b y using a higher consistency w ould b e able to prune domains Example di X X n X i X j i j FUTURE W ORK di X X X X f g X f g X f g X The pruning of X is not ac hiev ed when all different is expressed using binary relations as in Erlang FD see co de in App endix D on page R egin sho ws ho w to express the ab o v e dierence relation to ac hiev e the desired pruning It is based on expressing v ariables and v alues as sides in a bipartite graph and use graph matc hing to eliminate edges that represen t the domains of the v ariables A constrain t lik e all different in that shap e considering all v ariables at once could b e called a glob al c onstr aint CHIP Dincbas et al a no w commercial constrain t solv er use this kind of constrain ts hea vily Ma yb e this is the w a y to real constrain t solving p erformance There are denitely more to b e done despite the follo wing w ords that allegedly ha v e b een uttered once Ev erything that can b e in v en ted has b een in v en ted Charles H Duell Commissioner US Oce of P aten ts CHAPTER CONCLUSION Ac kno wledgemen ts Before an ything else I o w e a lot to Bj orn Carlson He inspired me to this w ork he pro vided the framew ork and guided me through This w ould not ha v e b een p ossible without his advises en th usiasm and supp ort I w ould also lik e to thank Bogumi l Hausman for sharing the secrets of BEAM with me and Mats Carlsson for his advices and thorough reading of this rep ort I w ould also lik e to men tion Martin Wikb org since Wikb org inspired me when I wrote m y in tro duction to Erlang and Mik ael Sj odin and Kristina Sirh ub er for reading and commen ting on this rep ort My p ersonal gratitude to Kiina for b eing there for me CHAPTER CONCLUSION Bibliograph y Armstrong et al J Armstrong R Virding and M Williams Concurr ent Pr o gr amming in ERLANG Pren tice Hall Carlson and Carlsson B Carlson and M Carlsson Constrain t Solving and En tailmen t Algorithms for ccFD ESPRIT Pro ject A CCLAIM deliv er able SICS Carlson Bj orn Carlson Compiling and Exe cuting Finite Domain Constr aints Uppsala theses in computing science Uppsala Univ ersit y Ma y Diaz and Co dognet D Diaz and P Co dognet Compiling constrain ts in clpFD Researc h rep ort INRIA Dincbas et al M Dincbas P V an Hen tenryc k H Simonis A Aggoun T Graf and F Berthier The Constrain t Logic Programming Language CHIP In Pr o c e e dings of the International Confer enc e on Fifth Gener ation Computer Sys tems Hausman B Hausman T urb o Erlang Approac hing the Sp eed of C In Ev an Tic k and Giancarlo Succi editors Implementations of L o gic Pr o gr amming Systems pages Klu w er Academic Publishers Hen tenryc k P ascal V an Hen tenryc k Constrain t logic programming The Know le dge Engine ering R eview Mac kw orth Alan Mac kw orth Consistency in net w orks of relations A rticial Intel ligenc e Mac kw orth Alan K Mac kw orth Constrain t satisfaction In Encyclop e dia of A rticial Intel ligenc e v olume pages R egin JC R egin A ltering algorithm for constrain ts of dierence in CSPs T ec hnical Rep ort RRLIRMM LIRM Dec Sarasw at V A Sarasw at Concurr ent Constr aint Pr o gr amming L anguages PhD thesis CarnegieMellon Univ ersit y Jan uary BIBLIOGRAPHY Tsang Edw ard Tsang F oundations of Constr aint Satisfaction Academic Press Wikb org Martin Wikb org Comparing erlang and SDLSDT for soft w are dev elopmen t Masters thesis Dept of Computer Systems Uppsala Univ ersit y App endix A Erlang F D BIFs Here w e list al l BIFs that ha v e b een added to Erlang A CompileTime BIFs fd map opOp Giv en an atom represen ting an em ulator instruction this BIF maps this atom to the corresp onding em ulator instruction n um b er A Em ulator BIFs fd init em ulator Sets up necessary data structures in the em ulator fd ev aluate indexicalIndexical V ariable Domain Args This the main BIF for accessing the em ulator Giv en an indexical the b yteco de is the one thing used the domain of the target v ariable and the argumen t v ariables it calculates what in Algorithm on page is denoted as I x r Ie it calculates the set v alue of the indexical range Returned is the pruning made to the target v ariable X The new domain of X is not returned but is accessible through the next BIF fd get in tersectionV ariable Domain Giv en a domain it lls in the resulting in tersected domain from the last in v o cation of the previous BIF fd evaluate indexical APPENDIX A ERLANG FD BIFS A Debugging BIFs fd prin t bitvBitv ector Giv en a bitv ector from a domain as a binery this BIF returns a readable string represen tation of the bitv ector as a binary A Misc BIFs fd sizeV ariable Returns the size regarded as set of the domain of the argumen t fd in domainIn teger V ariable Domain Returns true if In teger is in the domain of V ariable false otherwise fd setelemen tIndex T uple V alue Returns T uple with V alue replacing index Index Lik e the standard BIF set element Armstrong et al but with destructiv e up date and without t yp e c hec king unless during debugging fd elemen tIndex T uple Returns the Indexed elemen t of T uple Lik e the standard BIF element but without t yp e c hec king unless during debugging App endix B User Man ual This do cumen t describ es ho w to use Erlang FD whic h is an extension of Erlang with a solv er for nite domain constrain ts When reading this man ual y ou migh t nd it handly to sim ultaneously glance at App endix C on page with some example programs B In tro duction A constrain t program in general consists of three phases allo cating v ariables telling constrain ts and solving for a solution See eg the program Send More Money App endix C on page Before doing an y of these in Erlang FD though just m ust initialize the solv er pro cess The follo wing sections address in order these sub jects B Initialization Before allo cating v ariables and telling constrain ts just m ust initialize the solv er pro cess and when y ou are done y ou ma y kill the solv er This is done through the follo wing functions fdinit Initializes the solv er pro cess and th us enables Erlang FD fdclose Stops the solv er pro cess and th us exits Erlang FD APPENDIX B USER MANUAL B Allo cating V ariables Finite domain v ariables m ust b e explicitly allo cated in Erlang FD This is done using either of fdrangeLowerUpper Variable Returns a nite domain v ariable with optional in terv al b ounds Lo w er and Upp er fdrange listNLowerUpper Variables Returns a list of N nite domain v ariables with optional in terv al b ounds Lo w er and Upp er If not sp ecied lo w er b ound equals and upp er b ound equals B T elling Constrain ts Constrain ts can b e set using t w o dieren t approac hes arithmetic c onstr aints or in dexic als In b oth cases the function to use is fdtell B Using Arithmetic Constrain ts Y ou can state y our linear arithmetic constrain ts directly eg as in fdtellX There is nothing more to it actually B Using Indexicals In addition to the arithmetic constrain ts y ou can state y our indexicals directly see eg the program Queens App endix C on page constrainXYN fdtellX in diffdomX domY domYN domYN Y in diffdomY domX domXN domXN W e will not dw elv e in to the science of indexicals here but just note a few things B GENERA TING SOLUTIONS syn tax seman tics In Section on page y ou nd a description of ho w indexicals lo ok and b eha v e equiv alen t indexicals Bev are that indexicals inside the same fdtell are treated as e quivalent see Section on page B Generating Solutions Solutions as v alues to y our v ariables can b e requested using the follo wing functions fdsolveListOfVariable sM odu leF unct ion Values Giv en a list of previously allo cated nite domain v ariables this function re turns a solution ie a list with v alues for y our v ariables This can b e used rep eatedly getting one solution at a time If f Mo duleF unction g is sp ecied it is used as the v ariable selection function in the solv er Predened are f fd libfirst g and f fd libff g giving leftrigh t ordering and rstfail ordering resp ectiv ely Leftrigh t ordering is default fdsolve allListOfVariables Values As ab o v e but returns al l solutions at once If no more solution can b e found fail is returned B User Library In addition to the builtin functions describ ed ab o v e there exists some highlev el library functions They reside in the same mo dule as the library constrain ts see App endix D on page all differentVars Constrains the v ariables to all ha v e dieren t v alues eq iffXV B Library constrain t B eq iff X V expressing B if X equals V otherwise See Program Magic Series App endix C on page for an example of use APPENDIX B USER MANUAL App endix C Example Programs C Send More Money The problem amoun ts to computing an assignmen t of n um b ers from to to the letters S E N D M O R and Y suc h that adding the w ords SEND and MORE equals MONEY F urthermore S and M cannot b e assigned and no t w o dieren t letters can b e assigned the same n um b er The solution to this problem using nite domain constrain ts comes out as follo ws Let x s x e x n x d x m x o x r and x y b e v ariables suc h that eac h one of them is con tained in the set f g The constrain ts mo deling the problem are th us x s x m all different x s x e x n x d x m x o x r x y x s x e x n x d x m x o x r x e x m x o x n x e x y where all different x x k is true i x i x j is true where i j and i j k Since x s and x m m ust b e dieren t from it follo ws that x s x m f g The only solution to this problem is ie x s x e x n x d x m x o x r and x y send fdinit SM fdrangelist ENDORY fdrangelist fdliballdifferentS EN D MO RY fdtellSE ND M O R E APPENDIX C EXAMPLE PR OGRAMS MON EY Sol fdsolveSENDMORY fdclose Sol C QUEENS C Queens The Nqueens problem needs v ery little in tro duction Giv en a c hess b oard of size n n place n queens suc h that no t w o queens threaten eac h other This is form ulated b y asso ciating one v ariable x i p er queen in the range b et w een and n stating that no t w o queens can share column ro w or diagonal Assume that v ariable x i is assigned to ro w i hence w e only need to w orry ab out the columns and the diagonals The constrain ts whic h main tain the nothreat relation are th us as follo ws x i x j if i j dieren t columns x i x i x i x i i n dieren t diagonals x i x i x i x i i n x x n n x n n x queensNType queensNTypefdlibnai ve queensNTypeF fdinit LdomainlistNN constrainlistL case Type of all Sol fdsolveallLF Sol fdsolveLF end fdclose Sol domainlistN domainlistMN fdrangeNdomainl ist M N constrainlist true constrainlistXL constraineachXL constrainlistL constraineachXN true constraineachXYLN constrainXYN constraineachXLN APPENDIX C EXAMPLE PR OGRAMS constrainXYN fdtellX in diffdomX domY domYN domYN Y in diffdomY domX domXN domXN C ALPHA C Alpha The n um b ers ha v e b een randomly assigned to the letters of the alphab et The n um b ers b eside eac h w ord are the total of the v alues assigned to the letters in the w ord eg for L YRE LYRE migh t equal and resp ectiv ely or an y other com bination that add up to The problem What is the v alue of D BALLET POLKA CELLO QUAR TET CONCER T SAX OPHONE FLUTE SCALE FUGUE SOLO GLEE SONG JAZZ SOPRANO L YRE THEME OBOE VIOLIN OPERA W AL TZ Solution AB CD E FG H I J K LMN O P QR S TUV WX Y Z alpha alphafdlibnaive alphaLab fdinit LD fdrangelist ABCDEFGHIJK LM NO PQ RS T UV WX YZ LD fdliballdifferentLD fdtell B A L L E T C E L L O C O N C E R T F L U T E F U G U E G L E E J A Z Z L Y R E O B O E O P E R A P O L K A Q U A R T E T S A X O P H O N E S C A L E APPENDIX C EXAMPLE PR OGRAMS S O L O S O N G S O P R A N O T H E M E V I O L I N W A L T Z Sol fdsolveLDLab fdclose Sol C EQUA TIONS C Equations The follo wing is a simple system of linear equations o v er the natural n um b ers where the v ariables range b et w een and with exactly one solution The problem is th us to compute this solution x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x The ab o v e equations can b e stated directly as nite domain constrain ts adding the domain constrain ts x i f g where i eq eqone fdlibnaive eqTypeLab fdinit XXXXXXX fdrangelist fdtell XXX X X XX XX X X X X X APPENDIX C EXAMPLE PR OGRAMS XX X XX X X XX X X X X X XX X X X X X XX XX X X X XX X X X XX XX X X X XX XX X XX X X XX X XX X X case Type of all Sol fdsolveallXXXX X XX Lab Sol fdsolveXXXXXX X Lab end fdclose Sol C EQUA TIONS C Equations The follo wing is a simple system of linear equations o v er the natural n um b ers where the v ariables range b et w een and with exactly one solution The problem is th us to compute this solution x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x APPENDIX C EXAMPLE PR OGRAMS x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x The ab o v e equations can b e stated directly as nite domain constrain ts adding the domain constrain ts x i f g where i eq eqfdlibnaive eqLab fdinit XXXXXXX fdrangelist fdtell XX X XX X X X XX X X X X XX XX X X X XX X X XX X X XX X X X X XX X XX X X XX XX X X X XX X X XX X XX X X C EQUA TIONS XX X XX X X XX X XX X X X XX XX X XX X X XX X XX X X XX X X X XX XX X X X XX XX X X XX X XX X XX X X XX X X XX X XX X XX X X XX X XX X X Sol fdsolveallXXXX X X X Lab fdclose Sol APPENDIX C EXAMPLE PR OGRAMS C Fiv e Houses The v e house problem is a logical puzzle whic h is naturally form ulated as a nite domain problem Fiv e men of dieren t nationalit y England Spain Japan Italy Norw a y liv e in the rst v e houses on a street They all eac h ha v e a profession pain ter diplomat violinist do ctor sculptor one animal dog zebra fo x snail horse and one fa v orite drink juice w ater tea coee milk all dieren t from the others Eac h of the houses is pain ted in a color dieren t from all the others green red y ello w blue white F urthermore The Englishman liv es in the red house The Spaniard o wns the dog The Japanese is the pain ter The Italian lik es tea The Norw egian liv es in the leftmost house The o wner of the green house lik es coee The green house is to the righ t of the white one The sculptor breeds snails The diplomat liv es in the y ello w house Milk is drunk in the third house The Norw egians house is next to the blue one The violinist lik es juice The fo x is in the house next to the do ctors house The horse is in the house next to the diplomats The problem is th us to infer who o wns the zebra and who drinks w ater Let n i c i p i a i and d i range b et w een and where i range b et w een and denoting the corresp onding house Let n i represen t the nationalities eg n denotes the nationalit y of the p erson in house c i represen t the colors p i represen t the professions a i represen t the animals and d i the drinks Hence it m ust hold that n i n j where i j and similarly for c i p i a i and d i F urthermore the follo wing m ust b e satised C FIVE HOUSES n c n a n p n d n c d c c p a p c d n c c n p d a p p a a p p a The ab o v e constrain ts ha v e only one solution th us determining the Japanese as the o wner of the zebra and the Norw egian as the one who drinks w ater five fivefdlibnaive fiveLab fdinit L fdrangelist NNNNN CCCCC PPPPP AAAAA DDDDD L fdtellN fdtellD fdliballdifferentC C C C C fdliballdifferentP P P P P fdliballdifferentN N N N N fdliballdifferentA A A A A fdliballdifferentD D D D D fdtell N C N A N P APPENDIX C EXAMPLE PR OGRAMS N D P D C D P A P C C C pormAP pormAP pormNC Sol fdsolveCCCCC PPPPP NNNNN AAAAA DDDDD Lab fdclose Sol The follo wing function expresses plus or min us on X Y and Z ie either X Y Z or X Y Z is true pormXYZ fdtell X in minYminZmaxY max Z minYmaxZmaxYmin Z Y in minXminZmaxX max Z minXmaxZmaxXmin Z Z in minYmaxXmaxY min X minXmaxYmaxXmin Y C MA GIC SERIES C Magic Series A magic serie is a sequence x x x n suc h that eac h x i is the n um b er of o ccurrences of i in the serie ie x i P b j i where b j i is if x j i and if x j i Tw o redundan t constrain ts are used n X i i n and n X i i x i n Solutions N Solution and none and N N s magicN magicNfdlibnaive magicNF fdinit L fdrangelistNN case catch constraintsLLNN of fail fdclose fail Sol fdsolveLF fdclose Sol end constraintsSS fdlibxyS fdlibxyS constraintsXXsLIS S Occ sumLI fdlibxyXOcc S fdrange S fdrange fdlibxytSXS redundant constraint cI X S S APPENDIX C EXAMPLE PR OGRAMS constraintsXsLISS c S S fdlibxySS cI X S S fdlibaxytIXSS redundant constraint sum sumXXsI S sumXsI B fdlibeqiffXI S fdrange fdlibxytBSS S C SUUDOKU C Suudoku The problem is to ll partially lled x squares of squares suc h that eac h ro w and column are p erm utations of and eac h x square where the leftmost column mo dulo is is a p erm utation of suudokuP fdinit InitialProblem problemP ioformatnInitialn sn n pInitialProblem Problem domainproblemInitialPr oble m rowconstraintProblem columnconstraintProbl em blockconstraintProble m Vars listsappendProblem Sol fdsolveVars case Sol of fail ioformatfailn ioformatSolutionn sn n pmakesuuSol end done p pRowRows listsappendiolibfo rmat prowRow pRows prow n prowVR when integerV listsappendiolibfor mat w V prowR prowVR when Vv listsappend prowR makesuu makesuuCCCCC CC C C Cs CCCCCCC CC makesuuCs domainproblem domainproblemRowRows domainproblemrowRow domainproblemRows domainproblemrow domainproblemrowVR when integerV V domainproblemrowR domainproblemrowVR when Vv fdrange domainproblemrowR APPENDIX C EXAMPLE PR OGRAMS rowconstraint true rowconstraintRRt fdliballdifferentR rowconstraintRt columnconstraintCC C C C CC C C columnconstraintCCC C C C C CC columnconstraint true columnconstraintCC t C Ct C C t C Ct CCtCCtCC t C Ct C C t fdliballdifferentC C CC C C C CC columnconstraintCtCt C tC tC tC tC tC t Ct blockconstraintCC C C CC C C C blockconstraintCCC blockconstraintCCC blockconstraintCCC blockconstraint true blockconstraintCC C Ct C C C Ct C C C Ct fdliballdifferentC C CC C C C CC blockconstraintCtCt Ct problem shokyuu vvvvvv vvvvv vvvvvv vvvvvv vvvvv vvvvvv vvvvvv vvvvv vvvvvv problem shokyuu vvvvvv vvvvvvv vvvvv vvvvvv vvvvv vvvvvvvv vvvvvv vvvvv C SUUDOKU vvvvvv problem chuukyuu vvvvvvvv vvvvvv vvvvvv vvvvvv vvvvvv vvvvvv vvvvvv vvvvvv vvvvvvvv problem joukyuu vvvvvv vvvvvv vvvvvvv vvvvvvv vvvvv vvvvvvv vvvvvvv vvvvvv vvvvvv problem shokyuu from Mr Horai vvvvv vvvvv vvvvv vvvv vvvvvvv vvvv vvvvv vvvvv vvvvv problem Hard suudoku Pvvvvvvv vvvvv vvvvv vvvvvv vvvvvvvv vvvvvv vvvvv vvvvv APPENDIX C EXAMPLE PR OGRAMS vvvvvvv App endix D Libraries D User Library alldifferent alldifferentEL differentEL alldifferentL differentX X differentXEL fdtellX in diffdomX domE E in diffdomE domX differentXL D V ariable Ordering naiveL hdL tlL ffEL ffL EfdsizeE EL ff SmallestESmallestSize Orig SmallestE deleteSmallestEOrig ffEL SmallestESmallestSize Orig NewSize fdsizeE if NewSize SmallestSize ffL E NewSize Orig true APPENDIX D LIBRARIES ffL SmallestE SmallestSize Orig end deleteItem ItemRest Rest deleteItem HRest HdeleteItem Rest deleteItem D Library Constrain ts Library constrain ts on form x t xyXY fdtell X in minYmaxY Y in minXmaxX xyXY fdtell X in diffdomX minYmaxY Y in diffdomY minXmaxX xyXY fdtell X in minYinf Y in maxX xyXY fdtell X in maxY Y in minXinf D LIBRAR Y CONSTRAINTS Library constrain ts on form x c where f g tcTC fdtellT in C tcTC fdtellT in diffdomT C tcTC fdtellT in Cinf tcTC fdtellT in C Library constrain ts on form ax by c z where f g axtAXT fdtell T in AminXAmaxX X in minT divu AmaxT divd A axytAXYT fdtell T in AminX minYAmaxX maxY X in minT maxY divu AmaxT minY divd A Y in minT AmaxXmaxT AminX axbytAXBYT fdtell T in AminX BminYAmaxX BmaxY X in minT BmaxY divu AmaxT BminY divd A Y in minT AmaxX divu BmaxT AminX divd B Library constrain ts on form x y t xytX Y T fdtell T in minX minYmaxX maxY Y in minT maxXmaxT minX X in minT maxYmaxT minY APPENDIX D LIBRARIES Library constrain ts on form t u c where f g tucXYC fdtell X in minY CmaxY C Y in minX CmaxX C tucXYC fdtell X in diffdomX minYCmaxYC Y in diffdomY minXCmaxXC tucXYC fdtell X in minY Cinf Y in maxX C tucXYC fdtell X in maxY C Y in minX Cinf Library constrain ts on form t u c where f g tucXYC fdtell X in C maxYC minY Y in C maxXC minX tucXYC fdtell X in diffdomX C maxYC minY Y in diffdomY C maxXC minX D LIBRAR Y CONSTRAINTS tucXYC fdtell X in C maxYinf Y in C maxXinf tucXYC fdtell X in C minY Y in C minX Library constrain t B eq i X V expressing B if X equals V otherwise eqiffX V B fdrange fdtellX in domB V domB diffdomX V B in domX V domX V B PREDICATE minxyz PURPOSE Express the constraint minXYZ minxyzX Y Z fdtellX Z fdtellY Z fdtellX in domYdomZ inf domZ fdtellY in domXdomZ inf domZ fdtellZ in domXdomY
还剩100页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 5 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf