diff options
| -rw-r--r-- | picat/basic.pi | 276 | ||||
| -rw-r--r-- | picat/cp.pi | 484 | ||||
| -rw-r--r-- | picat/exs.pi | 594 |
3 files changed, 1354 insertions, 0 deletions
diff --git a/picat/basic.pi b/picat/basic.pi new file mode 100644 index 0000000..effe0cf --- /dev/null +++ b/picat/basic.pi @@ -0,0 +1,276 @@ +module basic. % imported by default + +'!='(X,Y) => X != Y. +'!=='(X,Y) => X !== Y. +'*'(X,Y) = X * Y. +'**'(X,Y) = X ** Y. +'+'(X) = X. +'+'(X,Y) = X + Y. +'++'(X,Y) = X ++ Y. +'-'(X) = -X. +'-'(X,Y) = X - Y. +'/'(X,Y) = X / Y. +'//'(X,Y) = X // Y. +'/<'(X,Y) = X /< Y. +'/>'(X,Y) = X /> Y. +'/\\'(X,Y) = X /\ Y. +'<'(X,Y) => X < Y. +'<<'(X,Y) = X << Y. +'<='(X,Y) => X <= Y. +'='(X,Y) => X = Y. +'=:='(X,Y) => X =:= Y. +'=<'(X,Y) => X <= Y. +'=='(X,Y) => X == Y. +'=\\='(X,Y) => X =\= Y. +'=..'(X,Y) => '=..'(X,Y). +'>'(X,Y) => X > Y. +'>='(X,Y) => X >= Y. +'>>'(X,Y) = X >> Y. +'@<'(X,Y) => X @< Y. +'@<='(X,Y) => X @=< Y. +'@=<'(X,Y) => X @=< Y. +'@>'(X,Y) => X @> Y. +'@>='(X,Y) => X @>= Y. +'\\/'(X,Y) = X \/ Y. +'^'(X, Y) = Res => bp.b_XOR_ccf(X,Y,Res). +'~'(X) = ~X. +'\\+'(Call) => throw($meta_meta_call_not_allowed('\\+'(Call))). +acyclic_term(Term) => acyclic_term(Term). +and_to_list(Conjunction) = and_to_list(Conjunction). +append(X,Y, Z) => append(X,Y,Z). +append(X,Y,Z, T) => append(X,Y,Z,T). +apply(S) = _ => throw($meta_meta_call_not_allowed(apply(S))). +apply(S, A1) = _ => throw($meta_meta_call_not_allowed(apply(S,A1))). +apply(S,A1, A2) = _ => throw($meta_meta_call_not_allowed(apply(S,A1,A2))). +apply(S,A1,A2, A3) = _ => throw($meta_meta_call_not_allowed(apply(S,A1,A2,A3))). +apply(S,A1,A2,A3, A4) = _ => throw($meta_meta_call_not_allowed(apply(S,A1,A2,A3,A4))). +apply(S,A1,A2,A3,A4, A5) = _ => throw($meta_meta_call_not_allowed(apply(S,A1,A2,A3,A4,A5))). +apply(S,A1,A2,A3,A4,A5, A6) = _ => throw($meta_meta_call_not_allowed(apply(S,A1,A2,A3,A4,A5,A6))). +apply(S,A1,A2,A3,A4,A5,A6, A7) = _ => throw($meta_meta_call_not_allowed(apply(S,A1,A2,A3,A4,A5,A6,A7))). +apply(S,A1,A2,A3,A4,A5,A6,A7, A8) = _ => throw($meta_meta_call_not_allowed(apply(S,A1,A2,A3,A4,A5,A6,A7,A8))). +apply(S,A1,A2,A3,A4,A5,A6,A7,A8, A9) = _ => throw($meta_meta_call_not_allowed(apply(S,A1,A2,A3,A4,A5,A6,A7,A8,A9))). +apply(S,A1,A2,A3,A4,A5,A6,A7,A8,A9, A10) = _ => throw($meta_meta_call_not_allowed(apply(S,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10))). +arg(I,T, A) => arg(I,T,A). +arity(Term) = arity(Term). +array(Term) => array(Term). +ascii_digit(Char) => digit(Char). +ascii_alpha(Char) => ascii_alpha(Char). +ascii_alpha_digit(Char) => ascii_alpha_digit(Char). +ascii_lowercase(Char) => lowercase(Char). +ascii_uppercase(Char) => uppercase(Char). +atom(Term) => atom(Term). +atom_chars(Atm) = atom_chars(Atm). +atom_codes(Atm) = atom_codes(Atm). +atomic(Term) => atomic(Term). +attr_var(Term) => attr_var(Term). +avg(ListOrArray) = avg(ListOrArray). +between(From,To, X) => between(From,To,X). +bigint(Term) => bigint(Term). +bind_vars(Term, Val) => bind_vars(Term,Val). +call(S) => throw($meta_meta_call_not_allowed(call(S))). +call(S, A1) => throw($meta_meta_call_not_allowed(call(S,A1))). +call(S,A1, A2) => throw($meta_meta_call_not_allowed(call(S,A1,A2))). +call(S,A1,A2, A3) => throw($meta_meta_call_not_allowed(call(S,A1,A2,A3))). +call(S,A1,A2,A3, A4) => throw($meta_meta_call_not_allowed(call(S,A1,A2,A3,A4))). +call(S,A1,A2,A3,A4, A5) => throw($meta_meta_call_not_allowed(call(S,A1,A2,A3,A4,A5))). +call(S,A1,A2,A3,A4,A5, A6) => throw($meta_meta_call_not_allowed(call(S,A1,A2,A3,A4,A5,A6))). +call(S,A1,A2,A3,A4,A5,A6, A7) => throw($meta_meta_call_not_allowed(call(S,A1,A2,A3,A4,A5,A6,A7))). +call(S,A1,A2,A3,A4,A5,A6,A7, A8) => throw($meta_meta_call_not_allowed(call(S,A1,A2,A3,A4,A5,A6,A7,A8))). +call(S,A1,A2,A3,A4,A5,A6,A7,A8, A9) => throw($meta_meta_call_not_allowed(call(S,A1,A2,A3,A4,A5,A6,A7,A8,A9))). +call(S,A1,A2,A3,A4,A5,A6,A7,A8,A9, A10) => throw($meta_meta_call_not_allowed(call(S,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10))). +call_cleanup(S, Cleanup) => throw($meta_meta_call_not_allowed(call_cleanup(S,Cleanup))). +catch(S,Exception, Handler) => throw($meta_meta_call_not_allowed(catch(S,Exception,Handler))). +char(Term) => char(Term). +chr(Code) = chr(Code). +clear(Map) => clear(Map). +compare_terms(Term1, Term2) = compare_terms(Term1,Term2). +compound(Term) => compound(Term). +copy_term(Term) = copy_term(Term). +copy_term_shallow(Term) = copy_term_shallow(Term). +del(Map,Key) => del(Map,Key). +delete(List, X) = delete(List,X). +delete_all(List, X) = delete_all(List,X). +different_terms(Term1, Term2) => different_terms(Term1,Term2). +digit(Char) => digit(Char). +div(X,Y) = X div Y. +dvar(Term) => dvar(Term). +bool_dvar(Term) => bool_dvar(Term). +dvar_or_int(Term) => dvar_or_int(Term). +fail => fail. +false => false. +find_all(Template, S) = _ => throw($meta_meta_call_not_allowed(find_all(Template,S))). +findall(Template, S) = _ => throw($meta_meta_call_not_allowed(findall(Template,S))). +count_all(S) = _ => throw($meta_meta_call_not_allowed(count_all(S))). +first(Compound) = first(Compound). +flatten(List) = flatten(List). +float(Term) => float(Term). +fold(F,Acc, List) = fold(F,Acc,List). +freeze(X, Goal) => throw($meta_meta_call_not_allowed(freeze(X,Goal))). +functor(T,F, N) => functor(T,F,N). +get(Map, Key) = get(Map,Key). +get(Map,Key, Default) = get(Map,Key,Default). +get_attr(AttrVar, Key) = get_attr(AttrVar,Key). +get_attr(AttrVar,Key, DefaultVal) = get_attr(AttrVar,Key,DefaultVal). +get_global_map = get_global_map(). +get_global_map(Id) = get_global_map(Id). +get_heap_map = get_heap_map(). +get_heap_map(Id) = get_heap_map(Id). +get_table_map = get_table_map(). +get_table_map(Id) = get_table_map(Id). +ground(Term) => ground(Term). +handle_exception(Exception, Source) => handle_exception(Exception,Source). +has_key(Map, Key) => has_key(Map,Key). +hash_code(Term) = hash_code(Term). +head(List) = head(List). +heap_is_empty(Heap) => heap_is_empty(Heap). +heap_pop(Heap) = heap_pop(Heap). +heap_push(Heap, Elm) => heap_push(Heap,Elm). +heap_size(Heap) = heap_size(Heap). +heap_to_list(Heap) = heap_to_list(Heap). +heap_top(Heap) = heap_top(Heap). +insert(List,Index, Elm) = insert(List,Index,Elm). +insert_all(List,Index, AList) = insert_all(List,Index,AList). +insert_ordered(OrderedList, Elm) = insert_ordered(OrderedList,Elm). +insert_ordered_no_dup(OrderedList, Elm) = insert_ordered_no_dup(OrderedList,Elm). +insert_ordered_down(OrderedList, Elm) = insert_ordered_down(OrderedList,Elm). +insert_ordered_down_no_dup(OrderedList, Elm) = insert_ordered_down_no_dup(OrderedList,Elm). +int(Term) => int(Term). +integer(Term) => integer(Term). +is(X, Y) => is(X,Y). +keys(Map) = keys(Map). +last(Compound) = last(Compound). +length(ArrayOrList) = length(ArrayOrList). +len(ArrayOrList) = len(ArrayOrList). +list(Term) => list(Term). +list_to_and(List) = list_to_and(List). +lowercase(Char) => lowercase(Char). +map(Func,List1, List2) = map(Func,List1,List2). +map(FuncOrList, ListOrFunc) = map(FuncOrList,ListOrFunc). +map(Term) => map(Term). +map_to_list(Map) = map_to_list(Map). +max(ListOrArray) = max(ListOrArray). +max(X, Y) = max(X,Y). +maxint_small() = maxint_small(). +maxof(Call, Exp) => throw($meta_meta_call_not_allowed(maxof(Call,Exp))). +maxof(Call,Exp, ReportCall) => throw($meta_meta_call_not_allowed(maxof(Call,Exp,ReportCall))). +maxof_inc(Call, Exp) => throw($meta_meta_call_not_allowed(maxof_inc(Call,Exp))). +maxof_inc(Call,Exp, ReportCall) => throw($meta_meta_call_not_allowed(maxof_inc(Call,Exp,ReportCall))). +membchk(Term, List) => membchk(Term,List). +member(Term, List) => member(Term,List). +min(ListOrArray) = min(ListOrArray). +min(X, Y) = min(X,Y). +minint_small() = minint_small(). +minof(Call, Exp) => throw($meta_meta_call_not_allowed(minof(Call,Exp))). +minof(Call,Exp, ReportCall) => throw($meta_meta_call_not_allowed(minof(Call,Exp,ReportCall))). +minof_inc(Call, Exp) => throw($meta_meta_call_not_allowed(minof_inc(Call,Exp))). +minof_inc(Call,Exp, ReportCall) => throw($meta_meta_call_not_allowed(minof_inc(Call,Exp,ReportCall))). +mod(X,Y) = X mod Y. +name(Struct) = name(Struct). +new_array(D1) = new_array(D1). +new_array(D1, D2) = new_array(D1,D2). +new_array(D1,D2, D3) = new_array(D1,D2,D3). +new_array(D1,D2,D3, D4) = new_array(D1,D2,D3,D4). +new_array(D1,D2,D3,D4, D5) = new_array(D1,D2,D3,D4,D5). +new_array(D1,D2,D3,D4,D5, D6) = new_array(D1,D2,D3,D4,D5,D6). +new_array(D1,D2,D3,D4,D5,D6, D7) = new_array(D1,D2,D3,D4,D5,D6,D7). +new_array(D1,D2,D3,D4,D5,D6,D7, D8) = new_array(D1,D2,D3,D4,D5,D6,D7,D8). +new_array(D1,D2,D3,D4,D5,D6,D7,D8, D9) = new_array(D1,D2,D3,D4,D5,D6,D7,D8,D9). +new_array(D1,D2,D3,D4,D5,D6,D7,D8,D9, D10) = new_array(D1,D2,D3,D4,D5,D6,D7,D8,D9,D10). +new_min_heap(IntOrList) = new_min_heap(IntOrList). +new_max_heap(IntOrList) = new_max_heap(IntOrList). +new_list(N) = new_list(N). +new_list(N, InitVal) = new_list(N,InitVal). +new_map() = new_map(). +new_map(Int, PairsList) = new_map(Int,PairsList). +new_map(IntOrPairsList) = new_map(IntOrPairsList). +new_set() = new_set(). +new_set(Int, PairsList) = new_set(Int,PairsList). +new_set(IntOrPairsList) = new_set(IntOrPairsList). +new_struct(Name, IntOrList) = new_struct(Name,IntOrList). +nonvar(Term) => nonvar(Term). +not(Call) => throw($meta_meta_call_not_allowed(not(Call))). +nth(I,L, V) => nth(I,L,V). +number(Term) => number(Term). +number_chars(Num) = number_chars(Num). +number_codes(Num) = number_codes(Num). +number_vars(Term, N0) = number_vars(Term,N0). +number_vars(Term) => number_vars(Term). +once(Call) => throw($meta_meta_call_not_allowed(once(Call))). +ord(Char) = ord(Char). +parse_radix_string(String, Base) = parse_radix_string(String,Base). +parse_term(String) = parse_term(String). +parse_term(String,Term, Vars) => parse_term(String,Term,Vars). +post_event(X, Event) => post_event(X,Event). +post_event_any(X, Event) => post_event_any(X,Event). +post_event_bound(X) => post_event_bound(X). +post_event_dom(X, Event) => post_event_dom(X,Event). +post_event_ins(X) => post_event_ins(X). +prod(ListOrArray) = prod(ListOrArray). +put(Map,Key, Val) => put(Map,Key,Val). +put(Map, Key) => put(Map,Key,not_a_value). +put_attr(AttrVar,Key, Val) => put_attr(AttrVar,Key,Val). +real(Term) => real(Term). +reduce(ListOrF, FOrList) = reduce(ListOrF,FOrList). +reduce(ListOrF,FOrList, InitVal) = reduce(ListOrF,FOrList,InitVal). +rem(X,Y) = X rem Y. +remove_dups(List) = remove_dups(List). +repeat => repeat. +reverse(ListOrArray) = reverse(ListOrArray). +second(Compound) = second(Compound). +select(X,List, ResList) => select(X,List,ResList). +size(Map) = size(Map). +slice(ListOrArray, From) = slice(ListOrArray,From). +slice(ListOrArray,From, To) = slice(ListOrArray,From,To). +sort(ListOrArray) = sort(ListOrArray). +sort(ListOrArray, KeyIndex) = sort(ListOrArray,KeyIndex). +sort_down(ListOrArray) = sort_down(ListOrArray). +sort_down(ListOrArray, KeyIndex) = sort_down(ListOrArray,KeyIndex). +sort_down_remove_dups(ListOrArray) = sort_down_remove_dups(ListOrArray). +sort_down_remove_dups(ListOrArray, KeyIndex) = sort_down_remove_dups(ListOrArray,KeyIndex). +sort_remove_dups(ListOrArray) = sort_remove_dups(ListOrArray). +sort_remove_dups(ListOrArray, KeyIndex) = sort_remove_dups(ListOrArray,KeyIndex). +sorted(ListOrArray) => sorted(ListOrArray). +sorted_down(ListOrArray) => sorted_down(ListOrArray). +string(Term) => string(Term). +struct(Term) => struct(Term). +subsumes(Term1, Term2) => subsumes(Term1,Term2). +sum(ListOrArray) = sum(ListOrArray). +tail(List) = tail(List). +throw(E) => throw(E). +to_array(List) = to_array(List). +to_atom(String) = to_atom(String). +to_binary_string(Int) = to_binary_string(Int). +to_codes(Term) = to_codes(Term). +to_fstring(Term) = to_fstring(Term). +to_fstring(Format, A1) = to_fstring(Format,A1). +to_fstring(Format,A1, A2) = to_fstring(Format,A1,A2). +to_fstring(Format,A1,A2, A3) = to_fstring(Format,A1,A2,A3). +to_fstring(Format,A1,A2,A3, A4) = to_fstring(Format,A1,A2,A3,A4). +to_fstring(Format,A1,A2,A3,A4, A5) = to_fstring(Format,A1,A2,A3,A4,A5). +to_fstring(Format,A1,A2,A3,A4,A5, A6) = to_fstring(Format,A1,A2,A3,A4,A5,A6). +to_fstring(Format,A1,A2,A3,A4,A5,A6, A7) = to_fstring(Format,A1,A2,A3,A4,A5,A6,A7). +to_fstring(Format,A1,A2,A3,A4,A5,A6,A7, A8) = to_fstring(Format,A1,A2,A3,A4,A5,A6,A7,A8). +to_fstring(Format,A1,A2,A3,A4,A5,A6,A7,A8, A9) = to_fstring(Format,A1,A2,A3,A4,A5,A6,A7,A8,A9). +to_fstring(Format,A1,A2,A3,A4,A5,A6,A7,A8,A9, A10) = to_fstring(Format,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10). +to_hex_string(Int) = to_hex_string(Int). +to_integer(NumOrCharOrString) = to_integer(NumOrCharOrString). +to_int(NumOrCharOrString) = to_int(NumOrCharOrString). +to_list(Struct) = to_list(Struct). +to_lowercase(StringOrChar) = to_lowercase(StringOrChar). +to_number(NumOrCharOrString) = to_number(NumOrCharOrString). +to_oct_string(Int) = to_oct_string(Int). +to_radix_string(Int, Base) = to_radix_string(Int,Base). +to_real(NumOrString) = to_real(NumOrString). +to_float(NumOrString) = to_float(NumOrString). +to_string(Term) = to_string(Term). +to_uppercase(StringOrChar) = to_uppercase(StringOrChar). +true => true. +uppercase(Char) => uppercase(Char). +values(Map) = values(Map). +var(Term) => var(Term). +variant(Term1, Term2) => variant(Term1,Term2). +vars(Term) = vars(Term). +zip(Lists) = zip(Lists). +zip(List1, List2) = zip(List1,List2). +zip(List1,List2, List3) = zip(List1,List2,List3). +zip(List1,List2,List3, List4) = zip(List1,List2,List3,List4). diff --git a/picat/cp.pi b/picat/cp.pi new file mode 100644 index 0000000..6663df1 --- /dev/null +++ b/picat/cp.pi @@ -0,0 +1,484 @@ +module cp. +import common_constr. + +% X #!= Y +% X #/\ Y +% X #< Y +% X #<= Y +% X #<=> Y +% X #= Y +% X #=< Y +% X #=> Y +% X #> Y +% X #>= Y +% X #\/ Y +% X #^ Y +% #~ X +% Vars::Exp +% Vars notin Exp +% acyclic(Vs,Es) +% acyclic_d(Vs,Es) +% all_different(FDVars) +% all_different_except_0(FDVars) +% all_distinct(FDVars) +% assignment(FDVars1,FDVars2) +% at_least(N,L,V) +% at_most(N,L,V) +% circuit(FDVars) +% count(V,FDVars,N) +% count(V,FDVars,Rel,N) +% cumulative(Ss,Ds,Rs,Limit) +% decreasing(L) +% decreasing_strict(L) +% diffn(RectangleList) +% disjunctive_tasks(Tasks)(cp only) +% element(I,List,V) +% element0(I,List,V) +% exactly(N,L,V): +% fd_degree(FDVar)=Degree(cp only) +% fd_disjoint(DVar1,DVar2) +% fd_dom(FDVar) = List +% fd_false(FDVar,Elm) +% fd_max(FDVar) = Max +% fd_min(FDVar) = Min +% fd_min_max(FDVar,Min,Max) +% fd_next(FDVar,Elm) = NextElm +% fd_prev(FDVar,Elm) = PrevElm +% fd_set_false(FDVar,Elm)(cp only) +% fd_size(FDVar) = Size +% fd_true(FDVar,Elm) +% fd_vector_min_max(Min,Max) +% global_cardinality(List,Pairs) +% hcp(Vs,Es) +% hcp(Vs,Es,K) +% hcp_grid(A) +% hcp_grid(A,Es) +% hcp_grid(A,Es,K) +% increasing(L) +% increasing_strict(L) +% indomain(Var)(nondet)(cp only) +% indomain_down(Var)(nondet)(cp only) +% lex_le(L_1,L_2) +% lex_lt(L_1,L_2) +% matrix_element(Matrix,I,J,V) +% matrix_element0(Matrix,I,J,V) +% neqs(NeqList)(cp only) +% new_dvar() = FDVar +% new_fd_var() = FDVar +% path(Vs,Es,Src,Dest) +% path_d(Vs,Es,Src,Dest) +% regular(X,Q,S,D,Q0,F) +% scalar_product(A,X,Product) +% scalar_product(A,X,Rel,Product) +% scc(Vs,Es) +% scc(Vs,Es,K) +% scc_d(Vs,Es) +% scc_d(Vs,Es,K) +% scc_grid(A) +% scc_grid(A,K) +% serialized(Starts,Durations) +% solve(Opts,Vars)(nondet) +% solve(Vars)(nondet) +% solve_all(Opts,Vars) = List +% solve_all(Vars) = List +% solve_suspended(Opt)(cp only) +% solve_suspended(cp only) +% subcircuit(FDVars) +% subcircuit_grid(A) +% subcircuit_grid(A,K) +% table_in(DVars,R) +% table_notin(DVars,R) +% tree(Vs,Es) +% tree(Vs,Es,K) + +include "cp_sat_mip_smt.pi". % common built-ins for cp, sat, mip, and smt + +'::'(Vars,Domain) => + bp.'_$_picat_in'(cp,Vars,Domain). + +% '#='(X,Y) => '#='(X,Y) +'#='(X,Y) => bp.'#='(X,Y). + +% '#>='(X,Y) => '#>='(X,Y) +'#>='(X,Y) => bp.'#>='(X,Y). + +% '#>'(X,Y) => '#>'(X,Y) +'#>'(X,Y) => bp.'#>'(X,Y). + +% '#<'(X,Y) => '#<'(X,Y) +'#<'(X,Y) => bp.'#<'(X,Y). + +% '#=<'(X,Y) => '#=<'(X,Y) +'#=<'(X,Y) => bp.'#=<'(X,Y). + +% '#!='(X,Y) => '#!='(X,Y) +'#!='(X,Y) => bp.'#\\='(X,Y). + +% '#\\='(X,Y) => '#\\='(X,Y) +'#\\='(X,Y) => bp.'#\\='(X,Y). + +% '#<=>'(X,Y) => '#<=>'(X,Y) +'#<=>'(X,Y) => bp.'#<=>'(X,Y). + +% '#=>'(X,Y) => '#=>'(X,Y) +'#=>'(X,Y) => bp.'#=>'(X,Y). + +% '#/\\'(X,Y) => '#/\\'(X,Y) +'#/\\'(X,Y) => bp.'#/\\'(X,Y). + +% '#\\/'(X,Y) => '#\\/'(X,Y) +'#\\/'(X,Y) => bp.'#\\/'(X,Y). + +% '#^'(X,Y) => '#^'(X,Y) +'#^'(X,Y) => bp.'#\\'(X,Y). + +% '#~'(X) => '#~'(X) +'#~'(X) => bp.'#\\'(X). + +% solve(Vars) => solve(Vars). +solve(Vars) => + (bp.dvar_or_int_list(Vars) -> VList = Vars; vars(Vars) = VList), + bp.labeling([],VList). + +% solve(Options,Vars) => solve(Options,Vars) +solve(Options,Vars) => + (bp.dvar_or_int_list(Vars) -> VList = Vars; vars(Vars) = VList), + (select($report(ReportCall), Options,Options1) -> + MetaCalls = [$report('$dyna_eval_pred'(['$picat_top_level'],ReportCall))] + ; + Options1 = Options, + MetaCalls = [] + ), + (select($label(LabelPred), Options1,Options2) -> + (atom(LabelPred) -> true; handle_exception($atom_expected(LabelPred), solve)), + (bp.'$dyna_resolve_name'(['$picat_top_level'],LabelPred,1,pred,MLabelPred) -> + true + ; + bp.c_module_qualified_pred_name(glb,LabelPred,MLabelPred) + ), + MetaCalls1 = [$label(MLabelPred)|MetaCalls] + ; + Options2 = Options1, + MetaCalls1 = MetaCalls + ), + bp.labeling(MetaCalls1 ++ Options2,VList). + +% solve_all(Vars) = solve_all(Vars). +solve_all(Vars) = + solve_all([],Vars). + +% solve_all(Options,Vars) = solve_all(Options,Vars). +solve_all(Options,Vars) = + findall(Vars, solve(Options,Vars)). + +% solve_suspended => solve_suspended. +solve_suspended => + bp.frozen(FL), + FVars = [FVar : FVar in vars(FL), dvar(FVar)], + bp.labeling([],FVars). + +solve_suspended(Options) => + bp.frozen(FL), + FVars = [FVar : FVar in vars(FL), dvar(FVar)], + bp.labeling(Options,FVars). + +% fd_degree(FDVar) = fd_degree(FDVar). +fd_degree(FDVar) = Degree, dvar(FDVar) => bp.fd_degree(FDVar,Degree). +fd_degree(FDVar) = Degree, integer(FDVar) => Degree = 0. +fd_degree(FDVar) = _Degree => handle_exception($dvar_expected(FDVar), fd_degree). + +% fd_set_false(FDVar,Elm) => fd_set_false(FDVar,Elm). +fd_set_false(FDVar,Elm), dvar_or_int(FDVar), integer(Elm) => + bp.domain_set_false(FDVar,Elm). +fd_set_false(FDVar,Elm) => + Source = fd_set_false, + (integer(Elm) -> + handle_exception($dvar_expected(FDVar), Source) + ; + handle_exception($integer_expected(Elm), Source) + ). + +% all_different(FDVars) => all_different(FDVars). +all_different(FDVars) => + (array(FDVars) -> to_list(FDVars) = List; List = FDVars), + bp.alldifferent(List). + +% all_distinct(FDVars) => all_distinct(FDVars). +all_distinct(FDVars) => + (array(FDVars) -> to_list(FDVars) = List; List = FDVars), + bp.all_distinct(List). + +% assignment(FDVars1,FDVars2) => assignment(FDVars1,FDVars2). +assignment(FDVars1,FDVars2) => + (array(FDVars1) -> to_list(FDVars1) = List1; List1 = FDVars1), + (array(FDVars2) -> to_list(FDVars2) = List2; List2 = FDVars2), + bp.assignment(List1,List2). + +% circuit(FDVars) => circuit(FDVars). +circuit(FDVars) => + (array(FDVars) -> to_list(FDVars) = List; List = FDVars), + bp.circuit(List). + +% cumulative(Starts,Durations,Resources,Limit) => cumulative(Starts,Durations,Resources,Limit). +cumulative(Starts,Durations,Resources,Limit) => + (array(Starts) -> to_list(Starts) = SList; SList = Starts), + (array(Durations) -> to_list(Durations) = DList; DList = Durations), + (array(Resources) -> to_list(Resources) = RList; RList = Resources), + bp.bp_cumulative(SList,DList,RList,Limit,cp). + +% diffn(RectangleList) => diffn(RectangleList). +diffn(RectangleList) => + (array(RectangleList) -> to_list(RectangleList) = RList; RList = RectangleList), + bp.bp_diffn(RList,cp). + +% disjunctive_tasks(Tasks) => disjunctive_tasks(Tasks). +disjunctive_tasks(Tasks) => + (array(Tasks) -> to_list(Tasks) = TList; TList = Tasks), + bp.post_disjunctive_tasks(TList). + +% element(I,Terms,V) => element(I,Terms,V). +element(I,Terms,V) => + (array(Terms) -> to_list(Terms) = List; List = Terms), + (bp.dvar_or_int_list(List) -> true; handle_exception($dvar_or_int_list_expected(List), element)), + bp.element(I,List,V). + +% 0-based indexing +% element0(I,FDVars,V) => element0(I,FDVars,V). +element0(I,FDVars,V) => + (array(FDVars) -> to_list(FDVars) = List; List = FDVars), + (bp.dvar_or_int_list(List) -> true; handle_exception($dvar_or_int_list_expected(List), element)), + bp.element0(I,List,V). + +% fd_set_false(FDVar,Elm) => fd_set_false(FDVar,Elm). +% global_cardinality(FDVars,Pairs) => global_cardinality(FDVars,Pairs). +global_cardinality(List,Pairs) => + (bp.check_pairs(Pairs) -> true; handle_exception($pairs_expected(Pairs), global_cardinality)), + bp.global_cardinality(List,Pairs). + +% indomain(Var) => indomain(Var). +indomain(Var), dvar(Var) => + bp.indomain_dvar(Var). +indomain(Var), integer(Var) => true. +indomain(Var) => + handle_exception($dvar_expected(Var), indomain). + +% indomain_down(Var) => indomain_down(Var). +indomain_down(Var), dvar(Var) => + bp.domain_min_max(Var,_,Max), + bp.indomain_dvar_backward(Var,Max). +indomain_down(Val), integer(Val) => true. +indomain_down(Var) => + handle_exception($dvar_expected(Var), indomain_down). + +% neqs(Neqs) => neqs(Neqs). +neqs(Neqs) => + (array(Neqs) -> to_list(Neqs) = List; List = Neqs), + check_neqs_args(List,List1), + bp.post_neqs(List1). + +% serialized(Starts,Durations) => serialized(Starts,Durations). +serialized(Starts,Durations) => + (array(Starts) -> to_list(Starts) = SList; SList = Starts), + (array(Durations) -> to_list(Durations) = DList; DList = Durations), + bp.disjunctive_tasks(SList,DList). + +% subcircuit(FDVars) => subcircuit(FDVars). +subcircuit(FDVars) => + (array(FDVars) -> to_list(FDVars) = List; List = FDVars), + bp.subcircuit(List). + +%%%%%%%%%%%%%%%%%%%%%%%% common to cp and sat modules %%%%%%%%%%%%%%%%%%%%%% +%% +table_in(Vars,Tuples) => + bp.table_in(Vars,Tuples). + +%% +notin(Vars,Domain) => + bp.'_$_picat_notin'(cp,Vars,Domain). + +%% +table_notin(Vars,Tuples) => + bp.table_notin(Vars,Tuples). + +/************************************************************************* + regular(L,Q,S,M,Q0,Fs) + + L : A sentence (an IntVar array or list) + Q : number of states + S : input_max, inputs are from 1 to S + M : transition matrix: M[I,J] (I in 1..S, J in 1..Q) is a list of outgoing states for NFA (0 means an error). + Q0: initial state + Fs : accepting states +***************************************************************************/ +regular(L, Q, S, M, Q0, Fs) => + regular_constr(L, Q, S, M, Q0, Fs, cp). + +%% +%% lex_le(L1,L2): collection L1 is lexicographically less than or equal to L2 +%% +lex_le(L1,L2), list(L1), list(L2) => + check_args_lex(L1,L2,L11,L22), + lex_le_aux(L11,L22). +lex_le(L1,L2), array(L1), array(L2) => + check_args_lex(to_list(L1), to_list(L2), L11,L22), + lex_le_aux(L11,L22). +lex_le(L1,L2) => + throw($invalid(lex_le(L1,L2))). + +%% +%% lex_lt(L1,L2): collection L1 is lexicographically less than L2 +%% +lex_lt(L1,L2), list(L1), list(L2) => + check_args_lex(L1,L2,L11,L22), + lex_lt_aux(L11,L22). +lex_lt(L1,L2), array(L1), array(L2) => + check_args_lex(to_list(L1), to_list(L2), L11,L22), + lex_lt_aux(L11,L22). +lex_lt(L1,L2) => + throw($invalid(lex_lt(L1,L2))). + +check_args_lex(L1,L2,L11,L22) => + (bp.dvar_or_int_list(L1) -> true; handle_exception($dvar_list_expected(L1), lex)), + (bp.dvar_or_int_list(L2) -> true; handle_exception($dvar_list_expected(L2), lex)), + N1 = length(L1), + N2 = length(L2), + (N1 == N2 -> + L11 = L1, L22 = L2 + ; N1 < N2 -> + Min = min([fd_min(V) : V in L2]), + Min1 = Min-1, + L1Pad = [Min1 : _ in 1..N2-N1], + L11 = L1++L1Pad, L22 = L2 + ; + Min = min([fd_min(V) : V in L1]), + Min1 = Min-1, + L2Pad = [Min1 : _ in 1..N1-N2], + L11 = L1, L22 = L2++L2Pad + ). + +%%% +lex_le_aux([],_) => true. +lex_le_aux([X],[Y]) => + (var(X) -> + (var(Y) -> + bp.v_ge_v(Y,X) + ; + bp.domain_region_max(X,Y) + ) + ; + (var(Y) -> + bp.domain_region_min(Y,X) + ; + X =< Y + ) + ). +lex_le_aux([X|Xs],[Y|Ys]), integer(X), integer(Y) => + (X < Y -> + true + ; X == Y -> + lex_le_aux(Xs,Ys) + ; + fail + ). +lex_le_aux([X|Xs],[Y|Ys]) => + watch_lex_le(X,Y,Xs,Ys). + +watch_lex_le(X,Y,_Xs,_Ys), var(X), + {generated, ins(X), ins(Y), bound(X), bound(Y)} + => + fd_min_max(X,MinX,_), + fd_min_max(Y,_,MaxY), + (MinX > MaxY -> fail; true). +watch_lex_le(X,Y,_Xs,_Ys), var(Y), + {generated, ins(Y), bound(Y)} + => + fd_min_max(X,MinX,_), + fd_min_max(Y,_,MaxY), + (MinX > MaxY -> fail; true). +watch_lex_le(X,Y,Xs,Ys) => % come here when both X, Y become integers + (X < Y -> + true + ; X == Y -> + lex_le(Xs,Ys) + ; + fail + ). + +%%% +lex_lt_aux([],_) => true. +lex_lt_aux([X],[Y]) => + (var(X) -> + (var(Y) -> + bp.v_gt_v(Y,X) + ; + bp.domain_region_max(X,Y-1) + ) + ; + (var(Y) -> + bp.domain_region_min(Y,X+1) + ; + X < Y + ) + ). +lex_lt_aux([X|Xs],[Y|Ys]), integer(X), integer(Y) => + (X < Y -> + true + ; X == Y -> + lex_lt_aux(Xs,Ys) + ; + fail + ). +lex_lt_aux([X|Xs],[Y|Ys]) => + watch_lex_lt(X,Y,Xs,Ys). + +watch_lex_lt(X,Y,_Xs,_Ys), var(X), + {generated, ins(X), ins(Y), bound(X), bound(Y)} + => + fd_min_max(X,MinX,_), + fd_min_max(Y,_,MaxY), + (MinX > MaxY -> fail; true). +watch_lex_lt(X,Y,_Xs,_Ys), var(Y), + {generated, ins(Y), bound(Y)} + => + fd_min_max(X,MinX,_), + fd_min_max(Y,_,MaxY), + (MinX > MaxY -> fail; true). +watch_lex_lt(X,Y,Xs,Ys) => % come here when both X, Y become integers + (X < Y -> + true + ; X == Y -> + lex_lt(Xs,Ys) + ; + fail + ). + +%% +nvalue(N, L) => bp.nvalue(N,L). + +%% The following constraints are proposed and implemented by Hakan Kjellerstrand +matrix_element(M,I,J,MIJ) => + check_matrix(M,NRows,NCols), + matrix_element(M,NRows,NCols,I,J,MIJ,cp). + +% +% Requires that all non-zero values in Xs are distinct. +% +alldifferent_except_0(Xs) => + all_different_except_0(Xs). + +all_different_except_0(Xs) => + (list(Xs) -> + Arr = to_array(Xs) + ;array(Xs) -> + Arr = Xs + ; + handle_exception($dvar_or_int_collection_expected(Xs), all_different_except_0) + ), + all_different_except_0_aux(Arr). + +all_different_except_0_aux(Xs) => + N = len(Xs), + foreach(I in 1..N-1, J in I+1..N) + Xs[I] #= 0 #\/ Xs[J] #= 0 #\/ Xs[I] #!= Xs[J] + end. + diff --git a/picat/exs.pi b/picat/exs.pi new file mode 100644 index 0000000..17f8083 --- /dev/null +++ b/picat/exs.pi @@ -0,0 +1,594 @@ +/* Several examples in Picat */ +/**** begin file exs.pi ****/ +import cp, planner. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%% PREDICATES AND FUNCTIONS +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +% Here are several versions for computing Fibonacci numbers +% A predicate +fibp(0,F) => F = 1. +fibp(1,F) => F = 1. +fibp(N,F),N>1 => fibp(N-1,F1), fibp(N-2,F2), F = F1+F2. + +% A function +fibf(0)=F => F = 1. +fibf(1)=F => F = 1. +fibf(N)=F, N>1 => F = fibf(N-1)+fibf(N-2). + +% A function with function facts +fibfa(0) = 1. +fibfa(1) = 1. +fibfa(N) = fibfa(N-1)+fibfa(N-2). + +% Using if-then-else +fibi(N) = F => + if N == 0 then + F = 1 + elseif N == 1 then + F = 1 + else + F = fibg(N-1)+fibg(N-2) + end. + +% Using Prolog-style if-then-else +fibg(N) = F => + (N == 0 -> + F = 1 + ;N == 1 -> + F = 1 + ; + F = fibg(N-1)+fibg(N-2) + ). + +% Using a conditional expression +fibc(N) = cond((N == 0; N == 1), 1, fibc(N-1)+fibc(N-2)). + +% A tabled function +table +fibt(0) = 1. +fibt(1) = 1. +fibt(N) = fibt(N-1)+fibt(N-2). + +% A nondeterministic predicate with a backtrackable rule +my_member(Y,[X|_]) ?=> Y = X. +my_member(Y,[_|L]) => my_member(Y,L). + +my_between(From,To,X), From == To => X = From. +my_between(From,To,X),From < To => X = From; my_between(From+1,To,X). + +my_select(Y,[X|L],LR) ?=> Y = X, LR = L. +my_select(Y,[X|L],LR) => LR = [X|LRR], my_select(Y,L,LRR). + +my_permutation([],P) => P = []. +my_permutation(L,P) => + P = [X|PR], + my_select(X,L,LR), + my_permutation(LR,PR). + +% predicate facts +index(+,-) (-,+) +edge(1,2). +edge(1,3). +edge(2,3). +edge(3,2). + +% several sort algorithms +merge_sort([]) = []. +merge_sort([X]) = [X]. +merge_sort(L) = SL => split(L,L1,L2), SL = merge(merge_sort(L1),merge_sort(L2)). + +split([X,Y|Zs],L1,L2) => L1 = [X|LL1], L2 = [Y|LL2], split(Zs,LL1,LL2). +split(Zs,L1,L2) => L1 = Zs,L2 = []. + +merge([],Ys) = Ys. +merge(Xs,[]) = Xs. +merge([X|Xs],Ys@[Y|_]) = [X|Zs], X < Y => Zs = merge(Xs,Ys). % Ys@[Y|_] is an as-pattern +merge(Xs,[Y|Ys]) = [Y|Zs] => Zs = merge(Xs,Ys). + +insert_sort([]) = []. +insert_sort([H|T]) = insert(H,insert_sort(T)). + +private +insert(X,[]) = [X]. +insert(X,Ys@[Y|_]) = Zs, X =< Y => Zs = [X|Ys]. +insert(X,[Y|Ys]) = [Y|insert(X,Ys)]. + +% two versions that return the minumum and maximum of a list +% a predicate +min_max_p([H|T],Min,Max) => min_max_p_aux(T,H,Min,H,Max). + +% A private function is not visiable outside +private +min_max_p_aux([],CMin,Min,CMax,Max) => CMin = Min,CMax = Max. +min_max_p_aux([H|T],CMin,Min,CMax,Max) => min_max_p_aux(T,min(CMin,H),Min,max(CMax,H),Max). + +% a function that returns the minimum and maximum of a list as a pair +min_max([H|T]) = min_max_aux(T,H,H). + +private +min_max_aux([],CMin,CMax) = (CMin,CMax). +min_max_aux([H|T],CMin,CMax) = min_max_aux(T,min(CMin,H),max(CMax,H)). + +% return the sum of a list +sum_list(L) = Sum => + sum_list_aux(L,0,Sum). + +% a private predicate is never exported +private +sum_list_aux([],Acc,Sum) => Sum = Acc. +sum_list_aux([X|L],Acc,Sum) => sum_list_aux(L,Acc+X,Sum). + +% two lists that are structually equal, e.g., struct_equal(X,[a]) fails +struct_equal(A,B),atomic(A) => A == B. +struct_equal([H1|T1],[H2|T2]) => + struct_equal(H1,H2), + struct_equal(T1,T2). + +is_sorted([]) => true. +is_sorted([_]) => true. +is_sorted([X|L@[Y|_]]) =>X @<= Y, is_sorted(L). + +% An empty tree is represented by {}, and a non-empty binary tree is +% represented by its root, which takes form {Val,Left,Right}. + +is_btree({}) => true. +is_btree({_Val,Left,Right}) => + is_btree(Left), + is_btree(Right). + +inorder({}) = []. +inorder({Val,Left,Right}) = inorder(Left) ++ [Val] ++ inorder(Right). + +% binary search tree +is_bstree({}) => true. +is_bstree(BT@{Val,Left,Right}) => + is_bstree(Left,min_bstree(BT),Val), + is_bstree(Right,Val,max_bstree(BT)). + +is_bstree({},_,_) => true. +is_bstree({Val,Left,Right},Min,Max) => + Val @>= Min, Val @=< Max, + is_bstree(Left,Min,Val), + is_bstree(Right,Val,Max). + +min_bstree({Elm,{},_Right}) = Elm. +min_bstree({_Elm,Left,_Right}) = min_bstree(Left). + +max_bstree({Elm,_Left,{}}) = Elm. +max_bstree({_Elm,_Left,Right}) = max_bstree(Right). + +lookup_bstree({Elm,_,_},Elm) => true. +lookup_bstree({Val,Left,_},Elm), Elm < Val => + lookup_bstree(Left,Elm). +lookup_bstree({_,_,Right},Elm) => + lookup_bstree(Right,Elm). + +tree_inst1 = {6, {5, {4, {}, {}}, + {7, {}, {}}}, + {8, {3, {}, {}}, + {9, {}, {}}}}. + +tree_inst2 = {7, {5, {4, {}, {}}, + {6, {}, {}}}, + {8, {8, {}, {}}, + {9, {}, {}}}}. + +test_btree => + Tree1 = tree_inst1(), + println(inorder(Tree1)), + println(cond(is_bstree(Tree1),"a binary search tree","not a binary search tree")), + Tree2 = tree_inst2(), + println(inorder(Tree2)), + println(cond(is_bstree(Tree2),"a binary search tree","not a binary search tree")). + +% An example that uses data constructors +% A term in the form of $f(X) is a data constructor +divide_main => + Exp= $((((((((x/x)/x)/x)/x)/x)/x)/x)/x)/x, + d(Exp,x,D), + writeln(D). + +d(U+V,X,D) => + D = $DU+DV, + d(U,X,DU), + d(V,X,DV). +d(U-V,X,D) => + D = $DU-DV, + d(U,X,DU), + d(V,X,DV). +d(U*V,X,D) => + D = $DU*V+U*DV, + d(U,X,DU), + d(V,X,DV). +d(U/V,X,D) => + D = $(DU*V-U*DV)/(^(V,2)), + d(U,X,DU), + d(V,X,DV). +d(^(U,N),X,D) => + D = $DU*N*(^(U,N1)), + integer(N), + N1 = N-1, + d(U,X,DU). +d(-U,X,D) => + D = $-DU, + d(U,X,DU). +d(exp(U),X,D) => + D = $exp(U)*DU, + d(U,X,DU). +d(log(U),X,D) => + D = $DU/U, + d(U,X,DU). +d(X,X,D) => D=1. +d(_,_,D) => D=0. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%% LOOPS +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% another version for summing up a list +sum_list_imp(L) = Sum => + S = 0, + foreach (X in L) + S := S+X + end, + Sum = S. + +% using a loop to find the minimum and maximum of a list +min_max_ip([H|T], Min, Max) => + LMin = H, + LMax = H, + foreach (E in T) + LMin := min(LMin, E), + LMax := max(LMax, E) + end, + Min = LMin, + Max = LMax. + +% draw the Pascal triangle +pascal => + print("enter an integer:"), + N = read_int(), + foreach(I in 0..N) + Num := 1, + foreach(K in 1..I+1) + printf("%d ",Num), + Num := Num*(I-K+1) div K + end, + nl + end. + +% another solution +pascal2 => + print("enter an integer:"), + N = read_int(), + Row = [1], + foreach(_I in 1..N) + writeln(Row), + Row := next_row(Row) + end. + +private +next_row(Row)=Res => + NewRow = [1], Prev = 1, + foreach (K in tail(Row)) + NewRow := [Prev+K|NewRow], + Prev := K + end, + Res = [1|NewRow]. + +/* another definition, not so efficient because Row[I] takes O(I) time +private +next_row(Row) = [1] ++ [Row[I]+Row[I+1] : I in 1..Row.length-1] ++ [1]. +*/ + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%% LIST COMPREHENSION +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +% a list comprehension inside another list comprehension +% Picat> L=list_of_lists(5) +% L = [[1],[1,2] [1,2,3],[1,2,3,4],[1,2,3,4,5]] +list_of_lists(N) = [[Y : Y in 1..X] : X in 1..N]. + +% another definition +another_list_of_lists(N) = [1..X : X in 1..N]. + +qsort([]) = []. +qsort([H|T]) = qsort([E : E in T, E =< H])++[H]++qsort([E : E in T, E>H]). + +power_set([]) = [[]]. +power_set([H|T]) = P1++P2 => + P1 = power_set(T), + P2 = [[H|S] : S in P1]. + +% generate permutations +perm([]) = [[]]. +perm(Lst) = [[E|P] : E in Lst, P in perm(Lst.delete(E))]. + +%another definition +perm1([]) = [[]]. +perm1([H|T]) = [insert(P,I,H) : P in Ps, I in 1..P.length+1] => Ps = perm1(T). + +% A*B=C +matrix_multi(A,B) = C => + C = new_array(A.length,B[1].length), + foreach(I in 1..A.length, J in 1..B[1].length) + C[I,J] = sum([A[I,K]*B[K,J] : K in 1..A[1].length]) + end. + +% Sieve of Eratosthenes +my_primes(N) = L => + A = new_array(N), + foreach(I in 2..floor(sqrt(N))) + if (var(A[I])) then + foreach(J in I**2..I..N) + A[J] = 0 + end + end + end, + L = [I : I in 2..N, var(A[I])]. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%% TABLING +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +% mode-directed tabling +% finding shortest paths on a graph given by the relation edge/3. +table(+,+,-,min) +sp(X,Y,Path,W) ?=> + Path=[(X,Y)], + edge(X,Y,W). +sp(X,Y,Path,W) => + Path = [(X,Z)|PathR], + edge(X,Z,W1), + sp(Z,Y,PathR,W2), + W = W1+W2. + +index(+,-,-) (+,+,-) +edge(1,2,1). +edge(1,3,2). +edge(2,3,3). +edge(3,2,4). + +% binomial coefficient +bc(_N,0) = 1. +bc(N,N) = 1. +bc(N,1) = N. +bc(N,K) = bc(N-1,K-1) + bc(N-1,K). + +% computing the minimal editing distance of two given lists +table(+,+,min) +edit([],[],D) => D=0. +edit([X|Xs],[X|Ys],D) => % copy + edit(Xs,Ys,D). +edit(Xs,[_Y|Ys],D) ?=> % insert + edit(Xs,Ys,D1), + D = D1+1. +edit([_X|Xs],Ys,D) => % delete + edit(Xs,Ys,D1), + D = D1+1. + +% the Farmer's problem (use planner) +farmer => + S0 = [s,s,s,s], + plan(S0,Plan), + println(Plan). + +final([n,n,n,n]) => true. + +action([F,F,G,C],S1,Action,ActionCost) ?=> + Action = farmer_wolf, + ActionCost = 1, + opposite(F,F1), + S1 = [F1,F1,G,C], + not unsafe(S1). +action([F,W,F,C],S1,Action,ActionCost) ?=> + Action = farmer_goat, + ActionCost = 1, + opposite(F,F1), + S1 = [F1,W,F1,C], + not unsafe(S1). +action([F,W,G,F],S1,Action,ActionCost) ?=> + Action = farmer_cabbage, + ActionCost = 1, + opposite(F,F1), + S1 = [F1,W,G,F1], + not unsafe(S1). +action([F,W,G,C],S1,Action,ActionCost) => + Action = farmer_alone, + ActionCost = 1, + opposite(F,F1), + S1 = [F1,W,G,C], + not unsafe(S1). + +index (+,-) (-,+) +opposite(n,s). +opposite(s,n). + +unsafe([F,W,G,_C]),W == G,F !== W => true. +unsafe([F,_W,G,C]),G == C,F !== G => true. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%% CONSTRAINT PROGRAMS (using cp) +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +% SEND+MORE=MONEY +sendmory => + Vars = [S,E,N,D,M,O,R,Y], % generate variables + Vars :: 0..9, + all_different(Vars), % generate constraints + S #!= 0, + M #!= 0, + 1000*S+100*E+10*N+D+1000*M+100*O+10*R+E + #= 10000*M+1000*O+100*N+10*E+Y, + solve(Vars), % search + writeln(Vars). + +% N-queens +queens(N) => + Qs = new_array(N), + Qs :: 1..N, + foreach (I in 1..N-1, J in I+1..N) + Qs[I] #!= Qs[J], + abs(Qs[I]-Qs[J]) #!= J-I + end, + solve([ff],Qs), + writeln(Qs). + +% another program for N-queens +queens2(N, Q) => + Q = new_list(N), + Q :: 1..N, + Q2 = [$Q[I]+I : I in 1..N], + Q3 = [$Q[I]-I : I in 1..N], + all_different(Q), + all_different(Q2), + all_different(Q3), + solve([ff],Q). + +% graph coloring (reuse edge/2 defined above) +color(NV,NC) => + A = new_array(NV), + A :: 1..NC, + foreach(I in 1..NV-1, J in I+1..NV) + if edge(I,J);edge(J,I) then + A[I] #!= A[J] + end + end, + solve(A), + writeln(A). + +% a 0-1 integer model for graph coloring +bcolor(NV,NC) => + A = new_array(NV,NC), + A :: [0,1], + foreach(I in 1..NV) + sum([A[I,K] : K in 1..NC]) #= 1 + end, + foreach(I in 1..NV-1, J in I+1..NV) + if edge(I,J);edge(J,I) then + foreach(K in 1..NC) + #~ A[I,K] #\/ #~ A[J,K] + end + end + end, + solve(A), + writeln(A). + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%% I/O +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +% Read a list of integers, stopping when 0 is read +read_array_main => + A = new_array(100), + Len = read_array(A), + foreach (I in 1..Len) + writeln(A[I]) + end. + +read_array(A) = Len => + Count = 0, + E = read_int(), % read from stdin + while (E != 0) + Count := Count+1, + A[Count] = E, + E := read_int() + end, + Len = Count. + +% copy a text file line-by-line +copy(IName,OName) => + IStream = open(IName), + OStream = open(OName,write), + Line = IStream.read_line(), + while (Line != end_of_file) + OStream.printf("%s%n",Line), + Line := IStream.read_line() + end, + close(IStream), + close(OStream). + +% Picat> output_students([$student("john","cs",3),$student("mary","math",4.0)]) +% john cs 3.00 +% mary math 4.00 +output_students(Students) => + foreach($student(Name,Major,GPA) in Students) + printf("%10s %10s %5.2f%n",Name,Major,to_real(GPA)) + end. + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%% HIGHER-ORDER (not recommended because of poor performance) +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +% Picat> my_map(-,[1,2,3]) = L +% L = [-1,-2,-3] +% Picat> my_map(+,[1,2,3],[4,5,6]) = L +% L = [5,6,7] +% Picat> my_fold(+,0,[1,2,3]) = S +% S = 6 + +my_map(_F,[]) = []. +my_map(F,[X|Xs]) = [apply(F,X)|my_map(F,Xs)]. + +my_map(_F,[],[]) = []. +my_map(F,[X|Xs],[Y|Ys]) = [apply(F,X,Y)|my_map(F,Xs,Ys)]. + +my_fold(_F,Acc,[]) = Acc. +my_fold(F,Acc,[H|T]) = my_fold(F, apply(F,H,Acc),T). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%% ACTION RULES +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +test_ar => + watch_event(X), + watch_dom(X), + watch_dom_any(X), + watch_ins(X), + watch_bound(X), + X.post_event(event), + X.post_event_dom(dom), + X.post_event_ins(), + X.post_event_bound(), + X.post_event_any(any). + +watch_event(X), + {event(X,T)} +=> + writeln($event(T)). + +watch_dom(X), + {dom(X,T)} +=> + writeln($dom(T)). + +watch_dom_any(X), + {dom_any(X,T)} +=> + writeln($dom_any(T)). + +watch_ins(X), + {ins(X)} +=> + writeln($ins(X)). + +watch_bound(X), + {bound(X)} +=> + writeln($bound(X)). + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%% EXCEPTIONS +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +catch_divided_by_zero => + catch(write(myd(4,0)),E, $handle(E)). + +myd(X,Y)=X/Y. + +handle(E) => + writeln(E), + throw(E). % just re-throw it + +/**** end file exs.pi ****/ |