Ascend FD-23R Manual do Utilizador

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 ==

vi

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. . . . . . . . . . . . . . . . .