/******************************************************************************** A converter for converting CSP instances in CLP(FD) format into the XML format used in the second CP solver competition by Neng-Fa Zhou, July 7, 2006, Usage: 1. Start B-Prolog. c:\>bp 2. Compile and load the program: cl(pl2xcsp). 3. Convert a CLP(FD) program in a file named inFile.pl with the top goal Goal into a file named outFile.xml: pl2xcsp(inFile,outFile,Goal) If inFile and outFile are the same, simply pl2xcsp(inFile,Goal) and if the top goal is 'top', then simply pl2xcsp(inFile) Supported constraints: Arithmetic constraints: #=, #\=, #>, #>=, #<, #=< Boolean constraints: #<=>, #=>, #\/, #/\, #\ Global constraints: alldifferent/1, element/3, atmost/3, count/4 *********************************************************************************/ :-include('$BPDIR/Tools/xml.pl'). % Available at: http://www.probp.com/publib/xml.html pl2xcsp(PlFile):- pl2xcsp(PlFile,top). % assume that the top goal is 'top' pl2xcsp(PlFile,Goal):- plus_extcodes(PlFile,"xml",XMLFile), % defined in B-Prolog pl2xcsp(PlFile,XMLFile,Goal). pl2xcsp(PlFile,XMLFile,Goal):- check_cmp_file(PlFile,FullFileName), % defined in B-Prolog consult(FullFileName), '_$savecp'(CP), extract_constrs(Goal,CP,Constrs), closetail(Constrs), extract_doms_vars(Constrs,Doms,Vars), closetail(Doms), length(Doms,DTmp), DNo0 is DTmp+1, length(Vars,VTmp), VNo0 is VTmp+1, generate_pred_constr_elms(Constrs,1,1,PredElms,ConstrElms,DNo0,DummyDoms,VNo0,DummyVars), closetail(PredElms), length(PredElms,NPreds), length(ConstrElms,NConstrs), closetail(DummyDoms), closetail(DummyVars), append(Doms,DummyDoms,AllDoms), append(Vars,DummyVars,AllVars), length(AllDoms,DNo), length(AllVars,NVars), generate_dom_elms(AllDoms,DomElms), generate_var_elms(AllVars,VarElms), csp_xml(PlFile,PlXmlTerm,DNo,DomElms,NVars,VarElms,NPreds,PredElms,NConstrs,ConstrElms), xml_parse(XMLCodes,PlXmlTerm), tell(XMLFile), write_codes(XMLCodes), told. write_constrs([Constr|Constrs]):-true : writeln(Constr), write_constrs(Constrs). write_constrs(Constr):-true : true. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% extract_constrs(true,CP,Constrs):-!. extract_constrs(fail,CP,Constrs):-!. % ignore fail extract_constrs((A,B),CP,Constrs):-!, extract_constrs(A,CP,Constrs), extract_constrs(B,CP,Constrs). extract_constrs((A -> B ; C),CP,Constrs):-!, (call(A)-> extract_constrs(B,CP,Constrs); extract_constrs(C,CP,Constrs)). extract_constrs((A;B),CP,Constrs):-!, writeln(user,warning(disjunction_not_supported,(A;B))). extract_constrs((A -> B),CP,Constrs):-!, (call(A)->extract_constrs(B,CP,Constrs);fail). extract_constrs(not(A),CP,Constrs):-!, handle_exception(negation_not_supported,not(A)). extract_constrs(\+(A),CP,Constrs):-!, handle_exception(negation_not_supported,not(A)). extract_constrs('!',CP,Constrs):-!, '_$cutto'(CP). extract_constrs(call(X),CP,Constrs):- true : extract_constrs(X,CP,Constrs). extract_constrs(element(I,L,V),CP,Constrs):-!, element(I,L,V), extract_element_constr(I,L,V,1,Constrs). extract_constrs(count(Val,List,RelOp,Count),CP,Constrs):-!, count(Val,List,RelOp,Count), % writeln(user,count(Val,List,RelOp,Count)), extract_count_constr(Val,List,RelOp,0,Count,Constrs). extract_constrs(atmost(N,L,V),CP,Constrs):-!, atmost(N,L,V), extract_atmost_constr(N,L,V,0,Constrs). extract_constrs(circuit(L),CP,Constrs):-!, alldifferent(L), extract_constrs(alldifferent(L),CP,Constrs). extract_constrs(Goal,CP,Constrs):- is_constraint(Goal),!, call(Goal), attach(Goal,Constrs). extract_constrs(Goal,CP,Constrs):- is_labeling(Goal),!. extract_constrs(Goal,CP,Constrs):- b_IS_CONSULTED_c(Goal) : '_$savecp'(CP1), clause(Goal,Body), extract_constrs(Body,CP1,Constrs). extract_constrs(Goal,CP,Constrs):- true : call(Goal). % extract_count_constr(Val,[],RelOp,Count0,Count,Constrs):-true : Constr=..[RelOp,Count0,Count], extract_constrs(Constr,_,Constrs). extract_count_constr(Val,[Vi|L],RelOp,Count0,Count,Constrs):-true : Bi :: 0..1, extract_constrs(((Val #= Vi) #<=> (Bi#=1)),_,Constrs), extract_count_constr(Val,L,RelOp,Bi+Count0,Count,Constrs). % L=[V1,...,Vn] % V #\= Vi #=> I #\= i extract_element_constr(I,[],V,Index,Constrs):-true : true. extract_element_constr(I,[Vi|L],V,Index,Constrs):-true : extract_constrs((V #\= Vi #=> I #\= Index),_,Constrs), Index1 is Index+1, extract_element_constr(I,L,V,Index1,Constrs). %L=[V1,...,Vn] % V #= Vi #<=> Si#=1 extract_element_constr(N,[],V,Sum,Constrs):-true : extract_constrs(Sum#=N,_,Constrs). extract_element_constr(N,[Vi|L],V,Sum,Constrs):-true : Si :: 0..1, extract_constrs((V #= Vi #<=> Si #= 1),_,Constrs), extract_element_constr(N,L,V,Sum+Si,Constrs). extract_atmost_constr(N,L,V,0,Constrs). :-mode is_constraint(+). is_constraint(_X#=__Y). is_constraint(_X#\=_Y). is_constraint(_X#>_Y). is_constraint(_X#<_Y). is_constraint(_X#>=_Y). is_constraint(_X#=<_Y). is_constraint(_X#<=>_Y). is_constraint(_X#=>_Y). is_constraint(_X#/\_Y). is_constraint(_X#\/_Y). is_constraint(_X#\_Y). is_constraint(#\_Y). is_constraint(alldifferent(_)). is_constraint(all_different(_)). is_constraint(alldistinct(_)). is_constraint(all_distinct(_)). %is_constraint(element(_I,_L,_V)). :-mode is_labeling(+). is_labeling(indomain(_X)). is_labeling(labeling(_X)). is_labeling(labeling(_,_X)). is_labeling(labeling_ff(_X)). is_labeling(labelingff(_X)). is_labeling(labeling_ffc(_X)). is_labeling(fd_labeling(_X)). is_labeling(fd_labeling_ff(_X)). is_labeling(fd_labeling_ffc(_X)). is_labeling(labeling(_Options,_X)). is_labeling(minof(_,_)). is_labeling(maxof(_,_)). is_labeling(fd_minimize(_,_)). is_labeling(fd_maximize(_,_)). :-mode is_alldiff_constraint(+). is_alldiff_constraint(alldifferent(_)). is_alldiff_constraint(all_different(_)). is_alldiff_constraint(alldistinct(_)). is_alldiff_constraint(all_distinct(_)). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% extract_doms_vars(Constrs,Doms,Vars):- term_variables(Constrs,Vars), extract_doms(Vars,Doms,1). extract_doms([Var|Vars],Doms,VNo):-true : (dvar(Var)->true;fd_new_var(Var)), put_attr_no_hook(Var,$var_id,VNo), (dvar_bv(Var)->fd_dom(Var,Dom);fd_min_max(Var,Min,Max),Dom=Min..Max), lookup_dom(Doms,Dom,DNo), put_attr_no_hook(Var,$dom_id,DNo), VNo1 is VNo+1, extract_doms(Vars,Doms,VNo1). extract_doms(_,Doms,VNo). lookup_dom(Doms,Dom,DNo):- lookup_dom(Doms,Dom,1,DNo). lookup_dom(Doms,Dom,I,DNo):- var(Doms) : Doms=[dom(Dom,I)|_], DNo=I. lookup_dom([dom(Dom,DNo1)|_],Dom,I,DNo):-true : DNo=DNo1. lookup_dom([_|Doms],Dom,I,DNo):-true : I1 is I+1, lookup_dom(Doms,Dom,I1,DNo). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% generate_dom_elms([dom(Dom,DNo)|Doms],DomElms):-true : DomElms=[DomElm|DomElms1], DomElm=element(domain,[name=[0'D|DNoCodes], nbValues=NbValuesCodes],[pcdata(PCData)]), number_codes(DNo,DNoCodes), (Dom=[_|_]->length(Dom,NbValues); Dom=Min..Max,NbValues is Max-Min+1), number_codes(NbValues,NbValuesCodes), pcdata(Dom,PCData), generate_dom_elms(Doms,DomElms1). generate_dom_elms(_,DomElms):-true : DomElms=[]. pcdata(Min..Max,PCData):-true : name(Min,MinCodes), name(Max,MaxCodes), append(MinCodes,[0'.,0'.|MaxCodes],PCData). pcdata([Item|Items],PCData):-true : name(Item,Codes), append_diff(Codes,PCData,PCData1), PCData1=[32|PCData2], pcdata(Items,PCData2). pcdata(_,PCData):-true : PCData=[]. generate_var_elms([Var|Vars],VarElms):-true : VarElms=[VarElm|VarElms1], VarElm=element(variable,[name=[0'V|VarIdCodes], domain=[0'D|DomIdCodes]],[]), get_attr(Var,$var_id,VarId), number_codes(VarId,VarIdCodes), get_attr(Var,$dom_id,DomId), number_codes(DomId,DomIdCodes), generate_var_elms(Vars,VarElms1). generate_var_elms(Vars,VarElms):-true : VarElms=[]. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% generate_pred_constr_elms([Constr|Constrs],ConstrNo,PredNo,PredElms,ConstrElms,DNo0,DummyDoms,VNo0,DummyVars):-true ? is_alldiff_constraint(Constr),!, arg(1,Constr,Args), length(Args,Arity), create_dummy_vars(Args,NArgs,DNo0,DNo1,DummyDoms,VNo0,VNo1,DummyVars), generate_scopes(NArgs,ScopeCodes), number_codes(ConstrNo,ConstrNoCodes), number_codes(Arity,ArityCodes), ConstrElms=[ConstrElm|ConstrElms1], ConstrElm=element(constraint, [name=[0'C|ConstrNoCodes], arity=ArityCodes, scope=ScopeCodes, reference="global:allDifferent"], []), ConstrNo1 is ConstrNo+1, generate_pred_constr_elms(Constrs,ConstrNo1,PredNo,PredElms,ConstrElms1,DNo1,DummyDoms,VNo1,DummyVars). generate_pred_constr_elms([Constr|Constrs],ConstrNo,PredNo,PredElms,ConstrElms,DNo0,DummyDoms,VNo0,DummyVars):-true : term_variables(Constr,Vars), (Vars\==[]-> generate_scopes(Vars,ScopeCodes), length(Vars,Arity), number_codes(ConstrNo,ConstrNoCodes), number_codes(Arity,ArityCodes), number_codes(PredNo,PredNoCodes), generate_pred_elm(Constr,Vars,PredElms,PredNoCodes), PredNo1 is PredNo+1, ConstrElms=[ConstrElm|ConstrElms1], ConstrElm=element(constraint, [name=[0'C|ConstrNoCodes], arity=ArityCodes, scope=ScopeCodes, reference=[0'P|PredNoCodes]], [ element( parameters, [], [ pcdata(ScopeCodes) ] ) ]), ConstrNo1 is ConstrNo+1 ; PredNo1 is PredNo, ConstrElms=ConstrElms1, ConstrNo1 is ConstrNo ), generate_pred_constr_elms(Constrs,ConstrNo1,PredNo1,PredElms,ConstrElms1,DNo0,DummyDoms,VNo0,DummyVars). generate_pred_constr_elms(_,_ConstrNo,_PredNo1,_PredElms,ConstrElms,_DNo0,_DummyDoms,_VNo0,_DummyVars):- true : ConstrElms=[]. create_dummy_vars([Arg|Args],NArgs,DNo0,DNo,DummyDoms,VNo0,VNo,DummyVars):-integer(Arg) : NArgs=[NewVar|NArgs1], attach(dom([Arg],DNo0),DummyDoms), attach(NewVar,DummyVars), DNo1 is DNo0+1, fd_new_var(NewVar), put_attr_no_hook(NewVar,$var_id,VNo0), put_attr_no_hook(NewVar,$dom_id,DNo0), VNo1 is VNo0+1, create_dummy_vars(Args,NArgs1,DNo1,DNo,DummyDoms,VNo1,VNo,DummyVars). create_dummy_vars([Arg|Args],NArgs,DNo0,DNo,DummyDoms,VNo0,VNo,DummyVars):-true : NArgs=[Arg|NArgs1], create_dummy_vars(Args,NArgs1,DNo0,DNo,DummyDoms,VNo0,VNo,DummyVars). create_dummy_vars(_,NArgs,DNo0,DNo,_DummyDoms,VNo0,VNo,_DummyVars):-true : NArgs=[],DNo=DNo0,VNo=VNo0. generate_scopes([],ScopeCodes):-true : ScopeCodes=[]. generate_scopes([Var|Vars],ScopeCodes):-true : get_attr(Var,$var_id,VId), name(VId,VIdCodes), append_diff([0'V|VIdCodes],ScopeCodes,ScopeCodes1), ScopeCodes1=[32|ScopeCodes2], generate_scopes(Vars,ScopeCodes2). generate_pred_elm(Constr,Vars,PredElms,PredNoCodes):- generate_formal_params(Vars,FormalParams), generate_constr_exp(Constr,Exp), myterm2string(Exp,ExpCodes), PredElm=element( predicate, [name=[0'P|PredNoCodes]], [ element( parameters, [], [ pcdata(FormalParams) ]), element( expression, [], [ element( functional, [], [ pcdata(ExpCodes) ]) ] ) ]), attach(PredElm,PredElms). generate_formal_params([],ParamCodes):-true : ParamCodes=[]. generate_formal_params([Var|Vars],ParamCodes):-true : get_attr(Var,$var_id,VId), name(VId,VIdCodes), append_diff([0'i,0'n,0't,32,0'X|VIdCodes],ParamCodes,ParamCodes1), ParamCodes1=[32|ParamCodes2], generate_formal_params(Vars,ParamCodes2). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% :-mode generate_constr_exp(+,-). generate_constr_exp(Var,NVId):-var(Var),!, get_attr(Var,$var_id,VId), name(VId,VIdCodes), name(NVId,[0'X|VIdCodes]). generate_constr_exp(Int,NExp):-integer(Int),!, NExp=Int. generate_constr_exp(#\ Constr,not(Exp)):- generate_constr_bool_exp(Constr,Exp). generate_constr_exp(Constr1#/\Constr2,and(Exp1,Exp2)):- generate_constr_bool_exp(Constr1,Exp1), generate_constr_bool_exp(Constr2,Exp2). generate_constr_exp(Constr1#\/Constr2,or(Exp1,Exp2)):- generate_constr_bool_exp(Constr1,Exp1), generate_constr_bool_exp(Constr2,Exp2). generate_constr_exp(Constr1#\Constr2,xor(Exp1,Exp2)):- generate_constr_bool_exp(Constr1,Exp1), generate_constr_bool_exp(Constr2,Exp2). generate_constr_exp(Constr1#<=>Constr2,eq(Exp1,Exp2)):- generate_constr_bool_exp(Constr1,Exp1), generate_constr_bool_exp(Constr2,Exp2). generate_constr_exp(Constr1#=>Constr2,or(not(Exp1),Exp2)):- generate_constr_bool_exp(Constr1,Exp1), generate_constr_bool_exp(Constr2,Exp2). generate_constr_exp(Constr1#=Constr2,Exp):- (is_bool_exp(Constr1);is_bool_exp(Constr2)),!, generate_constr_exp(Constr1#<=>Constr2,Exp). generate_constr_exp(Constr1#=Constr2,eq(Exp1,Exp2)):- generate_constr_exp(Constr1,Exp1), generate_constr_exp(Constr2,Exp2). generate_constr_exp(Constr1#\=Constr2,ne(Exp1,Exp2)):- generate_constr_exp(Constr1,Exp1), generate_constr_exp(Constr2,Exp2). generate_constr_exp(Constr1#>=Constr2,ge(Exp1,Exp2)):- generate_constr_exp(Constr1,Exp1), generate_constr_exp(Constr2,Exp2). generate_constr_exp(Constr1#>Constr2,gt(Exp1,Exp2)):- generate_constr_exp(Constr1,Exp1), generate_constr_exp(Constr2,Exp2). generate_constr_exp(Constr1#= Exp=eq(Exp1,1); Exp=Exp1). :-mode is_bool_exp(+). is_bool_exp(#\ Constr). is_bool_exp(Constr1#/\Constr2). is_bool_exp(Constr1#\/Constr2). is_bool_exp(Constr1#\Constr2). is_bool_exp(Constr1#<=>Constr2). is_bool_exp(Constr1#=>Constr2). is_bool_exp(Constr1#=Constr2). is_bool_exp(Constr1#\=Constr2). is_bool_exp(Constr1#>=Constr2). is_bool_exp(Constr1#>Constr2). is_bool_exp(Constr1#=