summary refs log tree commit diff stats
path: root/compiler/ccgtrav.nim
Commit message (Expand)AuthorAgeFilesLines
* fixes #3794Andreas Rumpf2016-01-301-0/+2
* Get rid of deprecation warningsdef2015-04-071-49/+49
* implemented mixed mode codegenAraq2014-10-031-4/+4
* Nimrod renamed to NimAraq2014-08-281-1/+1
* fixes #1434Araq2014-08-141-1/+1
* 'nil' as a statement is deprecated, use an empty 'discard' insteadAraq2014-01-191-1/+1
* case consistency: next stepsAraq2013-12-291-1/+1
* case consistency part 4Araq2013-12-271-2/+2
* Revert "Revert "bugfix: emulated thread vars used in combination with the mar...Zahary Karadjov2013-08-191-2/+6
* Revert "bugfix: emulated thread vars used in combination with the mark & swee...Araq2013-05-271-6/+2
* bugfix: emulated thread vars used in combination with the mark & sweep GCZahary Karadjov2013-05-261-2/+6
* make some tests greenAraq2013-03-031-2/+3
* first version of a simple mark&sweep GC; activate with --gc:markAndSweepAraq2013-02-071-2/+19
* disables the compile-time rope formatting during bootstrappingZahary Karadjov2012-11-281-5/+5
* idetools improvements; preparation of first class iterators; fixes #183Araq2012-08-021-5/+4
* closures shouldn't leak anymoreAraq2012-07-161-2/+4
* proper indentation in the generated C codeZahary Karadjov2012-06-121-11/+11
* C variables are created in their enclosing block instead of their enclosing f...Zahary Karadjov2012-04-121-11/+13
* fixes #102Araq2012-03-231-0/+1
* bugfix: GC marker procs; making tests green againAraq2012-03-231-1/+5
* implemented marker procs for the GC resulting in huge speedupsAraq2012-03-211-0/+121
258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320
 module planner.

% best_plan(S,Limit,Plan) => best_plan(S,Limit,Plan).
% best_plan(S,Limit,Plan,PlanCost) => best_plan(S,Limit,Plan,PlanCost).
% best_plan(S,Plan,PlanCost) => best_plan(S,Plan,PlanCost).
% best_plan(S,Plan) => best_plan(S,Plan).
% best_plan_bin(S,Limit,Plan) => best_plan_bin(S,Limit,Plan).
% best_plan_bin(S,Limit,Plan,PlanCost) => best_plan_bin(S,Limit,Plan,PlanCost).
% best_plan_bin(S,Plan,PlanCost) => best_plan_bin(S,Plan,PlanCost).
% best_plan_bin(S,Plan) => best_plan_bin(S,Plan).
% best_plan_bb(S,Limit,Plan) => best_plan_bb(S,Limit,Plan).
% best_plan_bb(S,Plan,PlanCost) => best_plan_bb(S,Plan,PlanCost).
% best_plan_bb(S,Limit,Plan,PlanCost) => best_plan_bb(S,Limit,Plan,PlanCost).
% best_plan_bb(S,Plan) => best_plan_bb(S,Plan).
% best_plan_nondet(S,Limit,Plan) => best_plan_nondet(S,Limit,Plan).
% best_plan_nondet(S,Plan,PlanCost) => best_plan_nondet(S,Plan,PlanCost).
% best_plan_nondet(S,Limit,Plan,PlanCost) => best_plan_nondet(S,Limit,Plan,PlanCost).
% best_plan_nondet(S,Plan) => best_plan_nondet(S,Plan).
% best_plan_unbounded(S,Limit,Plan) => best_plan_unbounded(S,Limit,Plan).
% best_plan_unbounded(S,Plan,PlanCost) => best_plan_unbounded(S,Plan,PlanCost).
% best_plan_unbounded(S,Limit,Plan,PlanCost) => best_plan_unbounded(S,Limit,Plan,PlanCost).
% best_plan_unbounded(S,Plan) => best_plan_unbounded(S,Plan).
% current_plan() = current_plan().
% current_resource() = current_resource().
% current_resource_plan(Amount,Plan) => current_resource_plan(Amount,Plan).
% current_resource_plan_cost(Amount,Plan,Cost) => current_resource_plan_cost(Amount,Plan,Cost).
% insert_state_list(StateL,Elm) = insert_state_list(StateL,Elm).
% is_tabled_state(S) => is_tabled_state(S).
% new_state_list(List) = new_state_list(List).
% plan(S,Limit,Plan) => plan(S,Limit,Plan).
% plan(S,Plan,PlanCost) => plan(S,Plan,PlanCost).
% plan(S,Limit,Plan,PlanCost) => plan(S,Limit,Plan,PlanCost).
% plan(S,Plan) => plan(S,Plan).
% plan_unbounded(S,Limit,Plan) => plan_unbounded(S,Limit,Plan).
% plan_unbounded(S,Plan,PlanCost) => plan_unbounded(S,Plan,PlanCost).
% plan_unbounded(S,Limit,Plan,PlanCost) => plan_unbounded(S,Limit,Plan,PlanCost).
% plan_unbounded(S,Plan) => plan_unbounded(S,Plan).

% A state-list is an ordered list, where the ordering of symbols is determined 
% by the addresses of the symbols in the symbol table, not by the characters that
% constitute the symbols. This ordering allows for efficient ordering of symbols. 
% Note that this ordering is different from lexicographical ordering, which is used by sort(). 

new_state_list(List) = SList => new_state_list_aux(List,[],SList).

new_state_list_aux([],SList0,SList) => SList = SList0.
new_state_list_aux([E|List],SList0,SList) => 
    bp.b_INSERT_STATE_LIST_ccf(SList0,E,SList1),
    new_state_list_aux(List,SList1,SList).

insert_state_list(SList0, Elm) = SList => bp.b_INSERT_STATE_LIST_ccf(SList0,Elm,SList).

%%%
current_resource() = Amount =>
    bp.b_PLANNER_CURR_RPC_fff(Amount,_Plan,_Cost).

current_plan() = Plan =>
    bp.b_PLANNER_CURR_RPC_fff(_Amount,Plan,_Cost).

current_resource_plan(Amount,Plan) =>
    bp.b_PLANNER_CURR_RPC_fff(Amount,Plan,_Cost).

current_resource_plan_cost(Amount,Plan,Cost) =>
    bp.b_PLANNER_CURR_RPC_fff(Amount,Plan,Cost).

%%%
plan(S,Plan), var(Plan) =>
    bp.picat_plan(S,268435455,Plan,_).    % the limit is assumed to be 268435455
plan(_S,Plan) =>
    throw_plan_arg_error(1,Plan,_,plan).

plan(S,Limit,Plan), var(Plan), integer(Limit), Limit >= 0 =>
    bp.picat_plan(S,Limit,Plan,_). 
plan(S,Plan,PlanCost), var(Plan), var(PlanCost) =>
    bp.picat_plan(S,268435455,Plan,PlanCost). 
plan(_S,Limit,Plan) =>
    throw_plan_arg_error(Limit,Plan,_,plan).

plan(S,Limit,Plan,PlanCost), var(Plan), var(PlanCost), integer(Limit), Limit >= 0 =>
    bp.picat_plan(S,Limit,Plan,PlanCost). 
plan(_S,Limit,Plan,PlanCost) =>
    throw_plan_arg_error(Limit,Plan,PlanCost,plan).

plan(S,Limit,Plan,PlanCost,FinS), var(Plan), var(PlanCost), integer(Limit), Limit >= 0 =>
    bp.picat_plan(S,Limit,Plan,PlanCost,FinS). 
plan(_S,Limit,Plan,PlanCost,_FinS) =>
    throw_plan_arg_error(Limit,Plan,PlanCost,plan).

%%%
plan_unbounded(S,Plan), var(Plan) =>
    bp.picat_plan_unbounded(S,268435455,Plan,_).    % the limit is assumed to be 268435455
plan_unbounded(_S,Plan) =>
    throw_plan_arg_error(1,Plan,_,plan_unbounded).

plan_unbounded(S,Limit,Plan), var(Plan), integer(Limit), Limit >= 0 =>
    bp.picat_plan_unbounded(S,Limit,Plan,_). 
plan_unbounded(S,Plan,PlanCost), var(Plan), var(PlanCost) =>
    bp.picat_plan_unbounded(S,268435455,Plan,PlanCost). 
plan_unbounded(_S,Limit,Plan) =>
    throw_plan_arg_error(Limit,Plan,_,plan_unbounded).

plan_unbounded(S,Limit,Plan,PlanCost), var(Plan), var(PlanCost), integer(Limit), Limit >= 0 =>
    bp.picat_plan_unbounded(S,Limit,Plan,PlanCost). 
plan_unbounded(_S,Limit,Plan,PlanCost) =>
    throw_plan_arg_error(Limit,Plan,PlanCost,plan_unbounded).


%%%
%%% iterative deepening
best_plan(S,Plan), var(Plan) =>
    best_plan_downward(S,0,268435455,Plan,_,_).
best_plan(_S,Plan) =>
    throw_plan_arg_error(1,Plan,_,best_plan).

best_plan(S,Limit,Plan), var(Plan), integer(Limit), Limit >= 0 =>
    best_plan_downward(S,0,Limit,Plan,_,_).
best_plan(S,Plan,PlanCost), var(Plan), var(PlanCost) =>
    best_plan_downward(S,0,268435455,Plan,PlanCost,_).
best_plan(_S,Limit,Plan) =>
    throw_plan_arg_error(Limit,Plan,_,best_plan).

best_plan(S,Limit,Plan,PlanCost), var(Plan), var(PlanCost), integer(Limit), Limit >= 0 =>
    best_plan_downward(S,0,Limit,Plan,PlanCost,_).
best_plan(_S,Limit,Plan,PlanCost) =>
    throw_plan_arg_error(Limit,Plan,PlanCost,best_plan).

best_plan(S,Limit,Plan,PlanCost,FinS), var(Plan), var(PlanCost), integer(Limit), Limit >= 0 =>
    best_plan_downward(S,0,Limit,Plan,PlanCost,FinS).
best_plan(_S,Limit,Plan,PlanCost,_FinS) =>
    throw_plan_arg_error(Limit,Plan,PlanCost,best_plan).

%%%
best_plan_downward(S,Level,_Limit,_Plan,_PlanCost,_FinS) ?=>
    (bp.global_get('_$picat_log',0, 1) -> printf("%% Searching with the bound %d\n",Level); true),
    call_picat_plan(S,Level),
    fail.
best_plan_downward(S,_Level,_Limit,Plan,PlanCost,FinS),
    Map = get_table_map('_$planner'),
    Map.has_key($current_best_plan(S))
 =>
    Map.get($current_best_plan(S)) = Plan,
    Map.get($current_best_plan_cost(S)) = PlanCost,
    Map.get($current_best_plan_fin_state(S)) = FinS.
best_plan_downward(S,Level,Limit,Plan,PlanCost,FinS) =>
    bp.global_get('_$planner_explored_depth',0,Depth),
    (Depth == 268435455 -> Level1 = Level+1; Level1 = Depth),
    Level1 =< Limit,
    best_plan_downward(S,Level1,Limit,Plan,PlanCost,FinS).

%%% iterative deeping and binary search
best_plan_bin(S,Plan), var(Plan) =>
    best_plan_downward_bin(S,0,268435455,Plan,_,_).
best_plan_bin(_S,Plan) =>
    throw_plan_arg_error(1,Plan,_,best_plan).

best_plan_bin(S,Limit,Plan), var(Plan), integer(Limit), Limit >= 0 =>
    best_plan_downward_bin(S,0,Limit,Plan,_,_).
best_plan_bin(S,Plan,PlanCost), var(Plan), var(PlanCost) =>
    best_plan_downward_bin(S,0,268435455,Plan,PlanCost,_).
best_plan_bin(_S,Limit,Plan) =>
    throw_plan_arg_error(Limit,Plan,_,best_plan).

best_plan_bin(S,Limit,Plan,PlanCost), var(Plan), var(PlanCost), integer(Limit), Limit >= 0 =>
    best_plan_downward_bin(S,0,Limit,Plan,PlanCost,_).
best_plan_bin(_S,Limit,Plan,PlanCost) =>
    throw_plan_arg_error(Limit,Plan,PlanCost,best_plan).

best_plan_bin(S,Limit,Plan,PlanCost,FinS), var(Plan), var(PlanCost), integer(Limit), Limit >= 0 =>
    best_plan_downward_bin(S,0,Limit,Plan,PlanCost,FinS).
best_plan_bin(_S,Limit,Plan,PlanCost,_FinS) =>
    throw_plan_arg_error(Limit,Plan,PlanCost,best_plan).

%%%
best_plan_downward_bin(S,Level,Limit,Plan,PlanCost,FinS) =>
    Map = get_table_map('_$planner'),
    loop_best_plan_downward_bin(S,Level,Limit,Plan,PlanCost,FinS,Map).

loop_best_plan_downward_bin(S,Level,Limit,_Plan,_PlanCost,_FinS,_Map) ?=>
    Level =< Limit,
    (bp.global_get('_$picat_log',0, 1) -> printf("%% Searching with the bound %d\n",Level); true),
    call_picat_plan(S,Level),
    fail.
loop_best_plan_downward_bin(S,_Level,_Limit,Plan,PlanCost,_FinS,Map),
    Map.has_key($current_best_plan(S))
 =>
    Lower = Map.get($current_lower_bound(S), 0),
    Upper = Map.get($current_best_plan_cost(S))-1,
    loop_best_plan_bin(S,Map,Lower,Upper,Plan,PlanCost).
loop_best_plan_downward_bin(S,Level,Limit,Plan,PlanCost,FinS,Map) =>
    bp.global_get('_$planner_explored_depth',0,Depth),
%    writeln(depth=Depth),
    (Depth == 268435455 -> Lower = Level+1; Lower = Depth),
    Map.put($current_lower_bound(S), Lower),
    Lower < Limit,
    Level1 = 2*Lower,
    NewLevel = cond(Level1 > Limit, Limit, Level1),
    loop_best_plan_downward_bin(S,NewLevel,Limit,Plan,PlanCost,FinS,Map).

% binary search
loop_best_plan_bin(S,Map,Lower,Upper,Plan,PlanCost),
    Lower =< Upper
 =>
    NewLimit = Lower + (Upper-Lower) div 2,
    (bp.global_get('_$picat_log',0, 1) -> printf("%% Searching with the bound %d\n",NewLimit); true),
    if call_picat_plan(S,NewLimit) then
        NewUpper = Map.get($current_best_plan_cost(S))-1,
        loop_best_plan_bin(S,Map,Lower,NewUpper,Plan,PlanCost)
    else
        NewLower = NewLimit+1,
        loop_best_plan_bin(S,Map,NewLower,Upper,Plan,PlanCost)
    end.
loop_best_plan_bin(S,Map,_Lower,_Upper,Plan,PlanCost) =>
    Map.has_key($current_best_plan(S)),
    Map.get($current_best_plan(S)) = Plan,
    Map.get($current_best_plan_cost(S)) = PlanCost.

%%%
best_plan_nondet(S,Plan), var(Plan) =>
    best_plan_nondet_aux(S,268435455,Plan,_).
best_plan_nondet(_S,Plan) =>
    throw_plan_arg_error(1,Plan,_,best_plan_nondet).

best_plan_nondet(S,Limit,Plan), var(Plan), integer(Limit), Limit >= 0 =>
    best_plan_nondet_aux(S,Limit,Plan,_).
best_plan_nondet(S,Plan,PlanCost), var(Plan), var(PlanCost) =>
    best_plan_nondet_aux(S,268435455,Plan,PlanCost).
best_plan_nondet(_S,Limit,Plan) =>
    throw_plan_arg_error(Limit,Plan,_,best_plan_nondet).

best_plan_nondet(S,Limit,Plan,PlanCost), var(Plan), var(PlanCost), integer(Limit), Limit >= 0 =>
    best_plan_nondet_aux(S,Limit,Plan,PlanCost).
best_plan_nondet(_S,Limit,Plan,PlanCost) =>
    throw_plan_arg_error(Limit,Plan,PlanCost,best_plan_nondet).

best_plan_nondet_aux(S,Limit,Plan,PlanCost) =>
    not not (M = get_global_map(),
             M.put('_first_best_plan',[]),
             best_plan_downward(S,0,Limit,Plan0,PlanCost0,_),     % use tabled search to find the first best plan
             M.put('_first_best_plan', (Plan0,PlanCost0))),
    get_global_map().get('_first_best_plan') = (Plan0,PlanCost),
    (    Plan = Plan0
    ;
        bp.picat_best_plan_nondet_nontabled_search(S,Plan,PlanCost),
        Plan0 != Plan
    ).

%%% Branch-and-Bound
best_plan_bb(S,Plan), var(Plan) =>
    loop_best_plan_bb(S,268435455,Plan,_).
best_plan_bb(_S,Plan) =>
    throw_plan_arg_error(1,Plan,_,best_plan_bb).

best_plan_bb(S,Limit,Plan), var(Plan), integer(Limit), Limit >= 0 =>
    loop_best_plan_bb(S,Limit,Plan,_PlanCost).
best_plan_bb(S,Plan,PlanCost), var(Plan), var(PlanCost) =>
    loop_best_plan_bb(S,268435455,Plan,PlanCost).
best_plan_bb(_S,Limit,Plan) =>
    throw_plan_arg_error(Limit,Plan,_,best_plan_bb).

best_plan_bb(S,Limit,Plan,PlanCost), var(Plan), var(PlanCost), integer(Limit), Limit >= 0 =>
    loop_best_plan_bb(S,Limit,Plan,PlanCost).
best_plan_bb(_S,Limit,Plan,PlanCost) =>
    throw_plan_arg_error(Limit,Plan,PlanCost,best_plan_bb).

loop_best_plan_bb(S,Limit,Plan,PlanCost),
    (bp.global_get('_$picat_log',0, 1) -> printf("%% Searching with the bound %d\n",Limit); true),
    call_picat_plan(S,Limit)        
 =>
    get_table_map('_$planner').get($current_best_plan_cost(S)) = PlanCost1,    
    loop_best_plan_bb(S,PlanCost1-1,Plan,PlanCost).
loop_best_plan_bb(S,_Limit,Plan,PlanCost) =>
    Map = get_table_map('_$planner'),
    Map.has_key($current_best_plan(S)),
    Map.get($current_best_plan(S)) = Plan,
    Map.get($current_best_plan_cost(S)) = PlanCost.

call_picat_plan(S,Limit) =>
    bp.global_set('_$planner_explored_depth',0,268435455),
    not not call_picat_plan_aux(S,Limit).   % discard exception catchers created by picat_plan

call_picat_plan_aux(S,Limit) =>
    bp.picat_plan(S,Limit,Plan,PlanCost,FinS),
    Map = get_table_map('_$planner'),
    Map.put($current_best_plan(S), Plan),
    Map.put($current_best_plan_cost(S), PlanCost),
    Map.put($current_best_plan_fin_state(S), FinS).

%%%
best_plan_unbounded(S,Plan), var(Plan) =>
    bp.picat_best_plan_unbounded(S,Plan,_).
best_plan_unbounded(_S,Plan) =>
    throw_plan_arg_error(1,Plan,_,best_plan_unbounded).

best_plan_unbounded(S,Limit,Plan), var(Plan), integer(Limit), Limit >= 0 =>
    bp.picat_best_plan_unbounded(S,Plan,PlanCost),
    PlanCost =< Limit.
best_plan_unbounded(S,Plan,PlanCost), var(Plan), var(PlanCost) =>
    bp.picat_best_plan_unbounded(S,Plan,PlanCost).
best_plan_unbounded(_S,Limit,Plan) =>
    throw_plan_arg_error(Limit,Plan,_,best_plan_unbounded).    

best_plan_unbounded(S,Limit,Plan,PlanCost), var(Plan), var(PlanCost), integer(Limit), Limit >= 0 =>
    bp.picat_best_plan_unbounded(S,Plan,PlanCost),
    PlanCost =< Limit.
best_plan_unbounded(_S,Limit,Plan,PlanCost) =>
    throw_plan_arg_error(Limit,Plan,PlanCost,best_plan_unbounded).    

%%%
is_tabled_state(S) =>
    bp.b_IS_PLANNER_STATE_c(S).

throw_plan_arg_error(_Limit,Plan,_PlanCost,Source), nonvar(Plan) =>
    handle_exception($var_expected(Plan), Source).
throw_plan_arg_error(_Limit,_Plan,PlanCost,Source), nonvar(PlanCost) =>
    handle_exception($var_expected(PlanCost), Source).
throw_plan_arg_error(Limit,_Plan,_PlanCost,Source), integer(Limit) =>
    handle_exception($nonnegative_integer_expected(Limit), Source).
throw_plan_arg_error(Limit,_Plan,_PlanCost,Source) =>
    handle_exception($integer_expected(Limit), Source).