TOY(FD): Version 0.8User ManualAntonio J. Fern´andez1Lenguajes y Ciencias de la Computaci´onCampus Teatinos, University of M´alaga,M´alaga 29071, Spai
x LIST OF FIGURES
List of Tables1.1 Predefined Datatypes for FD Constraints . . . . . . . . . . . . . . . . . 91.2 The Predefined Set of FD Constraints . . . . . . . . .
xii LIST OF TABLES
Chapter 1The TOY(FD) System1.1 What is TOY(FD)?1.1.1 In Brief Words, TOY(FD) ...• ... is an implementation of a functional logic language with finite d
2 CHAPTER 1. The TOY(FD) SystemIn TOY(FD), finite domain (FD) constraints are integrated as functions to makethem first-class citizens, which means that
1.2. The Current Implementation 31.2.5 DistributionThe current distribution is freely available as a compressed file toyfd.zip that containsthe files sh
4 CHAPTER 1. The TOY(FD) System• primFunct.pl, primFunctGra.pl, primFunctIo.pl, primitivCod.pl,primitivCodClpr.pl, primitivCodGra.pl, primitivCodIo.pl
1.2. The Current Implementation 5• queens.toy The n-queens problem. Example in the FD.• scheduling.toy A task scheduling problem.• eq10.toy and eq20.t
6 CHAPTER 1. The TOY(FD) System• Uncompress the file toyfd.zip in your working directory (e.g.,C:\SICSTUS382\bin\toyfd; observe that this path does not
1.3. Interpreter Commands 71.3.1 Calls to the Operating System (OS)Some commands calls directly to the operating system, as for example the following:
ii
8 CHAPTER 1. The TOY(FD) SystemTo load the new definition choose ‘y’; however, if we have redefined a set of func-tions is useful to choose the option ‘
1.4. FD Constraints 9• /cflpfdThis command is necessary to see important information about constraint solving.Below we show an example.TOY(FD)>doma
10 CHAPTER 1. The TOY(FD) SystemIn the following, we describe one by one all the FD constraints supported byTOY(FD). Table 1.2 shows the whole set of
1.4. FD Constraints 11• Example in the TOY(FD)command level:Next goal returns true and constrains X and Y to have values in the range [1,10].TOY(FD)&g
12 CHAPTER 1. The TOY(FD) SystemTOY(FD)> domain [X,Y] 1 10, X #> YyesY in 1..9X in 2..10Elapsed time: 0 ms.(#∗)/2, (#+)/2, (#−)/2, (#/)/2• Type
1.4. FD Constraints 13• Type declaration:sum :: [int] → (int → int → bool) → int → bool• Definition: sum L Op V is true if the sum of all elements in L
14 CHAPTER 1. The TOY(FD) System• Type declaration:assignment :: [int] → [int] → bool• Definition: ’assignment’ is a function applied over two lists of
1.4. FD Constraints 15TOY(FD)> L == [X,1,2], domain [X] 1 2, count 1 L (#=) 2yesL == [ 1, 1, 2 ]X == 1Elapsed time: 0 ms.exactly/3• Type declaratio
16 CHAPTER 1. The TOY(FD) System• Type declaration:serialized :: [int] → [int] → boolserialized’ :: [int] → [int] → [newOptions] → boolcumulative :: [
1.4. FD Constraints 17all different/1all different’/2all distinct/1all distinct’/2• Type declaration:all different :: [int] → boolall different’ :: [i
AcronymsAcronym MeaningCFLP Constraint Functional Logic ProgrammingCFLP(FD) Constraint Functional Logic Programming over Finite DomainsCLP Constraint
18 CHAPTER 1. The TOY(FD) System• Type declaration:indomain :: int → bool• Definition: ‘indomain X’ assigns a value, from the minimum to the maximumin
1.4. FD Constraints 193. The third group demands to find all the solutions (all) or only one solution tomaximize (resp. minimize) the domain of a varia
20 CHAPTER 1. The TOY(FD) Systemfd statistics’ :: bool• Definition: fd statistics’ always returns true and displays a set of useful statistics(usually
1.5. Some more constraints... 211.5 Some more constraints...TOY(FD) also provides a set of constraints (not shown in Table 1.2), called reflectionc
22 CHAPTER 1. The TOY(FD) System
Chapter 2TOY(FD) ProgrammingExamples2.1 Important Note about Programming with TOY(FD)In many cases, it can be useful to modularize a program and divid
24 CHAPTER 2. TOY(FD) Programming Examples2.2 Introductory TOY(FD) Examples2.2.1 Send+More = MoneyBelow, a TOY(FD) program (included in the distributi
2.2. Introductory TOY(FD) Examples 25N queens in a chessboard in such a way that no queen attacks each other. Observe theuse of the directive include
26 CHAPTER 2. TOY(FD) Programming ExamplesElapsed time: 0 ms.more solutions (y/n/d) [y]? ; %% Do not look for more solutionsTOY(FD)>2.2.3 A Cryptoa
2.2. Introductory TOY(FD) Examples 27C #+ E #+ L #+ L #+ O #= 43,C #+ O #+ N #+ C #+ E #+ R #+ T #= 74,F #+ L #+ U #+ T #+ E #= 30,F #+ U #+ G #+ U #+
iv
28 CHAPTER 2. TOY(FD) Programming Examplesconstrain L L 0 Cs, % essentialsum L (#=) N, % redundant #1scalar_product Cs L (#=) N, % redundant #2labelin
2.3. More Complex Examples 292.3 More Complex Examples2.3.1 A Scheduling ProblemHere, we consider the problem of scheduling tasks that require resourc
30 CHAPTER 2. TOY(FD) Programming Examplesschedule :: [task] -> int -> int -> boolschedule TL Start End = true <== horizon TL Start End,sc
2.3. More Complex Examples 31noOverlaps T1 T2 = true <== precedes T2 T1A task is modelled (via the type task) as a 5-tuple which holds its name, du
32 CHAPTER 2. TOY(FD) Programming ExamplesS5 == 7S6 == 10Elapsed time: 0 ms.more solutions (y/n/d) [y]?yesS1 == 1S2 == 4S3 == 12S4 == 1S5 == 7S6 == 11
2.3. More Complex Examples 33for specifying logical circuits, what are its weaknesses, and how they can effectively besolved with the integration of co
34 CHAPTER 2. TOY(FD) Programming ExamplesFigure 2.2: Basic Modules.01sSymbolSum of products equivalenceFigure 2.3: Two-Input Multiplexer Circuit.TPY(
2.3. More Complex Examples 35B==i0, P==0,B==i1, P==0,B==i2, P==0,B==not i0, P==1,. . .,B==not (not i0), P==2, . . ..Declaratively, it is fine; but our
36 CHAPTER 2. TOY(FD) Programming Examplesreflect the current state of the circuit during its generation. By contrast with the firstexample, we do not “
2.3. More Complex Examples 37because the add operation is monotonic. The mechanism which allows this “test”when “generating” is the set of propagators
RemarkThis document is a user manual exclusively developed for TOY(FD) and, as a conse-quence, does not treat directly about TOY, although it provides
38 CHAPTER 2. TOY(FD) Programming Examplesdomain [A] 0 maxArea,domain [P] 0 maxPower,domain [C] 0 maxCost,domain [D] 0 maxDelay,genCir (A,P,C,D) == (B
2.3. More Complex Examples 39type behaviour = bool -> bool -> bool -> booltype circuit = (behaviour, state)type functionality = [bool]%%%%%%%
40 CHAPTER 2. TOY(FD) Programming ExamplescircuitOutput4 = [true,true,true,true,true,true,true,false] % NANDcircuitOutput5 = [true,false,false,false,f
2.3. More Complex Examples 41domain [C] ((fd_min C) + notGateCost) (fd_max C)genBeh (A, P, C, D) = andGate (genBeh (A, P, C, D)) (genBeh (A, P, C, D))
42 CHAPTER 2. TOY(FD) Programming ExamplesgenCir’ (A, P, C, D) = (i0, (A, P, C, D))genCir’ (A, P, C, D) = (i1, (A, P, C, D))genCir’ (A, P, C, D) = (i2
2.3. More Complex Examples 43(Behaviour false false true) == Outcome1,(Behaviour false true false) == Outcome2,(Behaviour false true true) == Outcome3
44 CHAPTER 2. TOY(FD) Programming ExamplesyesF == [ true, false, false, false, false, false, false, false ]CIRCUIT == ((notGate (orGate i0 (orGate i2
2.4. Colour Problem 451234567891011121314151617 1819202122232425Figure 2.4: puzzleall_different [I6, I7],all_different [I6, I13],all_different [I6, I1
46 CHAPTER 2. TOY(FD) Programming Examplesproblem:TOY(FD)> color LyesL == [ 1, 2, 3, 2, 3, 1, 3, 1, 2, 1, 3, 1, 2, 3, 2, 1,2, 3, 1, 3, 2, 1, 2, 3,
2.5. Lazy Constraint Programs 47where the operation α/2 is defined as follows:[] α V = V : []U α [] = U : [][X|Xs] α [Y |Y s] = X : (Xs α Y s) ⇐⇒ X ==
48 CHAPTER 2. TOY(FD) Programming Examples2.5.2 Lazy Magic SequencesNow we present a lazy solution (included in the distribution in the directory Exam
2.5. Lazy Constraint Programs 49%%%%%%%%%% NOW WE GENERATE AN INFINITE LIST OF LISTS%%%%%%%%%% CONTAINING THE MAGIC SEQUENCES FROM A NUMBER N%%%%%%%%%
50 CHAPTER 2. TOY(FD) Programming ExamplesThis simple example gives an idea of the nice features of TOY(FD) that combinesFD constraint solving, manage
BibliographyBeldiceanu, N. (2000). Global constraints as graph properties on a structured networkof elementary constraints of the same type. In Dechte
52 BIBLIOGRAPHYMarriot, K. and Stuckey, P. J. (1998). Programming with constraints. The MIT Press,Cambridge, Massachusetts.R´egin, J.-C. (1994). A filt
Appendix ATOY(FD) GrammarFD constraints are declared as classical TOY functions and, as a consequence, thegrammar of TOY(FD)is equivalent to the gramm
54 CHAPTER A. TOY(FD) GrammarThe identifiers let, where, in and subtype correspond to non-implemented con-structions in the current version, but they a
55Also, it is allowed to use two different kinds of comments inserted in the programtext:• Comments in one sentence (i.e., in one line in a text) start
56 CHAPTER A. TOY(FD) GrammarBASIC GRAMMARprogram −→ ( { topdecl } )+top-level declarationstopdecl −→data typeLhs = constrs datatype declaration| type
57FUNCTION RULES AND CLAUSESfunrule −→ ruleLhs = exp [conditionrule] function ruleruleLhs −→ function rule left-hand sidepat funop pat rule for infix o
ContentsAcronyms iiiRemark v1 The TOY(FD) System 11.1 What is TOY(FD)? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1.1 In Brief Words
58 CHAPTER A. TOY(FD) Grammar| con constructor name| integer integer number| real real number| ( ) unit| exp parenthesised expression| ( atomic op ) l
Appendix BDeclaration of Primitives (filebasic.toy)/*** THIS FILE DEFINES THE PREDEFINED FUNCTIONS AND TYPES OF THE SYSTEM ***/data bool = true | false
60 CHAPTER B. Declaration of Primitives (file basic.toy):: real -> real -> real% integer powersprimitive (^) :: real -> int -> real% binary
Appendix CCommon Functions (filemisc.toy)% FILE: misc.toy% A collection of useful functions and type declarations,% many of them taken from Gofer’s pre
62 CHAPTER C. Common Functions (file misc.toy)false ‘or‘ false = false% Sequential andfalse /\ _ = falsetrue /\ X = X% Sequential ortrue \/ X = truefal
63hnf X = X <== X /= _% (strict F) is the restriction of F to finite, totally defined arguments.% Operationally, it forces the evaluation to nf of
64 CHAPTER C. Common Functions (file misc.toy)%% Fold primitives: The foldl and scanl functions, variants foldl1 and%% scanl1 for non-empty lists, and
65scanr F Q0 [X|Xs] = auxForScanr F X (scanr F Q0 Xs)%whereauxForScanr F X Ys = [F X (head Ys)|Ys]scanr1 :: (A -> A -> A) -> [A] -> [A]sca
66 CHAPTER C. Common Functions (file misc.toy)takeWhile P [X|Xs] = if P X then [X| takeWhile P Xs] else []takeUntil :: (A -> bool) -> [A] -> [
67%% Standard combinators: %% %% %% %% %% %% %% %% %% %% %% %% %% %%const :: A -> B -> Aconst K X = Kid :: A -> Aid X = X% non-deterministic
viii CONTENTS2 TOY(FD) Programming Examples 232.1 Important Note about Programming with TOY(FD) . . . . . . . . . . . 232.2 Introductory TOY(FD) Examp
68 CHAPTER C. Common Functions (file misc.toy)lcm X Y = if ((X==0) \/ (Y == 0)) then 0else abs ((X ‘div‘ (gcd X Y)) * Y)%%%% Standard list processing f
69transpose = foldrauxForTranspose[]%whereauxForTranspose Xs Xss = zipWith (:) Xs (Xss ++ repeat [])%% (\\) is used to remove the first occurrence of
List of Figures2.1 Precedence Graph. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.2 Basic Modules. . . . . . . . . . . . . . . . .
Comments to this Manuals