From 5d67fac7966b6f05611d014420eb4971b8016c31 Mon Sep 17 00:00:00 2001 From: "Kartik K. Agaram" Date: Thu, 11 Feb 2016 16:13:10 -0800 Subject: 2646 - redo static dispatch algorithm The old approach of ad hoc boosts and penalties based on various features was repeatedly running into exceptions and bugs. New organization: multiple tiered scores interleaved with tie-breaks. The moment one tier yields one or more candidates, we stop scanning further tiers. Just break ties and return. --- 021check_instruction.cc | 9 ++ 057static_dispatch.cc | 224 ++++++++++++++++++++++++++++---------------- 059shape_shifting_recipe.cc | 181 ++++++++++++++++++----------------- 070text.mu | 3 +- 4 files changed, 246 insertions(+), 171 deletions(-) diff --git a/021check_instruction.cc b/021check_instruction.cc index de5d8394..cf0a8d74 100644 --- a/021check_instruction.cc +++ b/021check_instruction.cc @@ -117,6 +117,15 @@ bool types_match(const reagent& to, const reagent& from) { return types_strictly_match(to, from); } +bool types_strictly_match_except_literal_against_boolean(const reagent& to, const reagent& from) { + // to sidestep type-checking, use /unsafe in the source. + // this will be highlighted in red inside vim. just for setting up some tests. + if (is_literal(from) + && to.type && to.type->value == get(Type_ordinal, "boolean")) + return boolean_matches_literal(to, from); + return types_strictly_match(to, from); +} + bool boolean_matches_literal(const reagent& to, const reagent& from) { if (!is_literal(from)) return false; if (!to.type) return false; diff --git a/057static_dispatch.cc b/057static_dispatch.cc index fcae37ee..9c71ac38 100644 --- a/057static_dispatch.cc +++ b/057static_dispatch.cc @@ -160,35 +160,40 @@ void resolve_ambiguous_calls(recipe_ordinal r) { for (long long int index = 0; index < SIZE(caller_recipe.steps); ++index) { instruction& inst = caller_recipe.steps.at(index); if (inst.is_label) continue; - if (get_or_insert(Recipe_variants, inst.name).empty()) continue; + if (non_ghost_size(get_or_insert(Recipe_variants, inst.name)) == 0) continue; + trace(9992, "transform") << "instruction " << inst.original_string << end(); resolve_stack.push_front(call(r)); resolve_stack.front().running_step_index = index; - replace_best_variant(inst, caller_recipe); + string new_name = best_variant(inst, caller_recipe); + if (!new_name.empty()) + inst.name = new_name; assert(resolve_stack.front().running_recipe == r); assert(resolve_stack.front().running_step_index == index); resolve_stack.pop_front(); } } -void replace_best_variant(instruction& inst, const recipe& caller_recipe) { - trace(9992, "transform") << "instruction " << inst.original_string << end(); +string best_variant(instruction& inst, const recipe& caller_recipe) { vector& variants = get(Recipe_variants, inst.name); -//? trace(9992, "transform") << "checking base: " << get(Recipe_ordinal, inst.name) << end(); - long long int best_score = variant_score(inst, get(Recipe_ordinal, inst.name)); - trace(9992, "transform") << "score for base: " << best_score << end(); - for (long long int i = 0; i < SIZE(variants); ++i) { - if (variants.at(i) == -1) continue; - trace(9992, "transform") << "checking variant " << i << ": " << header_label(variants.at(i)) << end(); - long long int current_score = variant_score(inst, variants.at(i)); - trace(9992, "transform") << "score for variant " << i << ": " << current_score << end(); - if (current_score > best_score) { - trace(9993, "transform") << "switching " << inst.name << " to " << get(Recipe, variants.at(i)).name << end(); - inst.name = get(Recipe, variants.at(i)).name; - best_score = current_score; - } - } - // End Instruction Dispatch(inst, best_score) - if (best_score == -1 && get(Recipe_ordinal, inst.name) >= MAX_PRIMITIVE_RECIPES) { + vector candidates; + + // Static Dispatch Phase 1 + candidates = strictly_matching_variants(inst, variants); + if (!candidates.empty()) return best_variant(inst, candidates).name; + + // Static Dispatch Phase 2 (shape-shifting recipes in a later layer) + // End Static Dispatch Phase 2 + + // Static Dispatch Phase 3 + candidates = strictly_matching_variants_except_literal_against_boolean(inst, variants); + if (!candidates.empty()) return best_variant(inst, candidates).name; + + // Static Dispatch Phase 4 + candidates = matching_variants(inst, variants); + if (!candidates.empty()) return best_variant(inst, candidates).name; + + // error messages + if (get(Recipe_ordinal, inst.name) >= MAX_PRIMITIVE_RECIPES) { // we currently don't check types for primitive variants raise_error << maybe(caller_recipe.name) << "failed to find a matching call for '" << inst.to_string() << "'\n" << end(); for (list::iterator p = /*skip*/++resolve_stack.begin(); p != resolve_stack.end(); ++p) { const recipe& specializer_recipe = get(Recipe, p->running_recipe); @@ -209,83 +214,144 @@ void replace_best_variant(instruction& inst, const recipe& caller_recipe) { } } } + return ""; } -bool next_stash(const call& c, instruction* stash_inst) { - const recipe& specializer_recipe = get(Recipe, c.running_recipe); - long long int index = c.running_step_index; - for (++index; index < SIZE(specializer_recipe.steps); ++index) { - const instruction& inst = specializer_recipe.steps.at(index); - if (inst.name == "stash") { - *stash_inst = inst; - return true; - } +// phase 1 +vector strictly_matching_variants(const instruction& inst, vector& variants) { + vector result; + for (long long int i = 0; i < SIZE(variants); ++i) { + if (variants.at(i) == -1) continue; + trace(9992, "transform") << "checking variant (strict) " << i << ": " << header_label(variants.at(i)) << end(); + if (all_header_reagents_strictly_match(inst, get(Recipe, variants.at(i)))) + result.push_back(variants.at(i)); } - return false; + return result; } -long long int variant_score(const instruction& inst, recipe_ordinal variant) { - long long int result = 100; - if (variant == -1) return -1; // ghost from a previous test -//? cerr << "variant score: " << inst.to_string() << '\n'; - if (!contains_key(Recipe, variant)) { - assert(variant < MAX_PRIMITIVE_RECIPES); - return -1; +bool all_header_reagents_strictly_match(const instruction& inst, const recipe& variant) { + for (long long int i = 0; i < min(SIZE(inst.ingredients), SIZE(variant.ingredients)); ++i) { + if (!types_strictly_match(variant.ingredients.at(i), inst.ingredients.at(i))) { + trace(9993, "transform") << "strict match failed: ingredient " << i << end(); + return false; + } } - const vector& header_ingredients = get(Recipe, variant).ingredients; -//? cerr << "=== checking ingredients\n"; - for (long long int i = 0; i < min(SIZE(inst.ingredients), SIZE(header_ingredients)); ++i) { - if (!types_match(header_ingredients.at(i), inst.ingredients.at(i))) { - trace(9993, "transform") << "mismatch: ingredient " << i << end(); -//? cerr << "mismatch: ingredient " << i << '\n'; - return -1; + for (long long int i = 0; i < min(SIZE(inst.products), SIZE(variant.products)); ++i) { + if (is_dummy(inst.products.at(i))) continue; + if (!types_strictly_match(variant.products.at(i), inst.products.at(i))) { + trace(9993, "transform") << "strict match failed: product " << i << end(); + return false; } - if (types_strictly_match(header_ingredients.at(i), inst.ingredients.at(i))) { - trace(9993, "transform") << "strict match: ingredient " << i << end(); -//? cerr << "strict match: ingredient " << i << '\n'; + } + return true; +} + +// phase 3 +vector strictly_matching_variants_except_literal_against_boolean(const instruction& inst, vector& variants) { + vector result; + for (long long int i = 0; i < SIZE(variants); ++i) { + if (variants.at(i) == -1) continue; + trace(9992, "transform") << "checking variant (strict except literals-against-booleans) " << i << ": " << header_label(variants.at(i)) << end(); + if (all_header_reagents_strictly_match_except_literal_against_boolean(inst, get(Recipe, variants.at(i)))) + result.push_back(variants.at(i)); + } + return result; +} + +bool all_header_reagents_strictly_match_except_literal_against_boolean(const instruction& inst, const recipe& variant) { + for (long long int i = 0; i < min(SIZE(inst.ingredients), SIZE(variant.ingredients)); ++i) { + if (!types_strictly_match_except_literal_against_boolean(variant.ingredients.at(i), inst.ingredients.at(i))) { + trace(9993, "transform") << "strict match failed: ingredient " << i << end(); + return false; } - else if (boolean_matches_literal(header_ingredients.at(i), inst.ingredients.at(i))) { - // slight penalty for coercing literal to boolean (prefer direct conversion to number if possible) - trace(9993, "transform") << "boolean matches literal: ingredient " << i << end(); - result--; + } + for (long long int i = 0; i < min(SIZE(variant.products), SIZE(inst.products)); ++i) { + if (is_dummy(inst.products.at(i))) continue; + if (!types_strictly_match_except_literal_against_boolean(variant.products.at(i), inst.products.at(i))) { + trace(9993, "transform") << "strict match failed: product " << i << end(); + return false; } - else { - // slightly larger penalty for modifying type in other ways - trace(9993, "transform") << "non-strict match: ingredient " << i << end(); -//? cerr << "non-strict match: ingredient " << i << '\n'; - result-=10; + } + return true; +} + +// phase 4 +vector matching_variants(const instruction& inst, vector& variants) { + vector result; + for (long long int i = 0; i < SIZE(variants); ++i) { + if (variants.at(i) == -1) continue; + trace(9992, "transform") << "checking variant " << i << ": " << header_label(variants.at(i)) << end(); + if (all_header_reagents_match(inst, get(Recipe, variants.at(i)))) + result.push_back(variants.at(i)); + } + return result; +} + +bool all_header_reagents_match(const instruction& inst, const recipe& variant) { + for (long long int i = 0; i < min(SIZE(inst.ingredients), SIZE(variant.ingredients)); ++i) { + if (!types_match(variant.ingredients.at(i), inst.ingredients.at(i))) { + trace(9993, "transform") << "strict match failed: ingredient " << i << end(); + return false; } } -//? cerr << "=== done checking ingredients\n"; - const vector& header_products = get(Recipe, variant).products; - for (long long int i = 0; i < min(SIZE(header_products), SIZE(inst.products)); ++i) { + for (long long int i = 0; i < min(SIZE(variant.products), SIZE(inst.products)); ++i) { if (is_dummy(inst.products.at(i))) continue; - if (!types_match(header_products.at(i), inst.products.at(i))) { - trace(9993, "transform") << "mismatch: product " << i << end(); -//? cerr << "mismatch: product " << i << '\n'; - return -1; - } - if (types_strictly_match(header_products.at(i), inst.products.at(i))) { - trace(9993, "transform") << "strict match: product " << i << end(); -//? cerr << "strict match: product " << i << '\n'; + if (!types_match(variant.products.at(i), inst.products.at(i))) { + trace(9993, "transform") << "strict match failed: product " << i << end(); + return false; } - else if (boolean_matches_literal(header_products.at(i), inst.products.at(i))) { - // slight penalty for coercing literal to boolean (prefer direct conversion to number if possible) - trace(9993, "transform") << "boolean matches literal: product " << i << end(); - result--; + } + return true; +} + +// tie-breaker for each phase +const recipe& best_variant(const instruction& inst, vector& candidates) { + assert(!candidates.empty()); + long long int min_score = 999; + long long int min_index = 0; + for (long long int i = 0; i < SIZE(candidates); ++i) { + const recipe& candidate = get(Recipe, candidates.at(i)); + long long int score = abs(SIZE(candidate.products)-SIZE(inst.products)) + + abs(SIZE(candidate.ingredients)-SIZE(inst.ingredients)); + assert(score < 999); + if (score < min_score) { + min_score = score; + min_index = i; } - else { - // slightly larger penalty for modifying type in other ways - trace(9993, "transform") << "non-strict match: product " << i << end(); -//? cerr << "non-strict match: product " << i << '\n'; - result-=10; + } + return get(Recipe, candidates.at(min_index)); +} + +long long int non_ghost_size(vector& variants) { + long long int result = 0; + for (long long int i = 0; i < SIZE(variants); ++i) + if (variants.at(i) != -1) ++result; + return result; +} + +bool next_stash(const call& c, instruction* stash_inst) { + const recipe& specializer_recipe = get(Recipe, c.running_recipe); + long long int index = c.running_step_index; + for (++index; index < SIZE(specializer_recipe.steps); ++index) { + const instruction& inst = specializer_recipe.steps.at(index); + if (inst.name == "stash") { + *stash_inst = inst; + return true; } } - // the greater the number of unused ingredients/products, the lower the score - return result - abs(SIZE(get(Recipe, variant).products)-SIZE(inst.products)) - - abs(SIZE(inst.ingredients)-SIZE(get(Recipe, variant).ingredients)); + return false; } +:(scenario static_dispatch_disabled_in_recipe_without_variants) +recipe main [ + 1:number <- test 3 +] +recipe test [ + 2:number <- next-ingredient # ensure no header + reply 34 +] ++mem: storing 34 in location 1 + :(scenario static_dispatch_disabled_on_headerless_definition) % Hide_warnings = true; recipe test a:number -> z:number [ diff --git a/059shape_shifting_recipe.cc b/059shape_shifting_recipe.cc index f83b09f0..a4af884c 100644 --- a/059shape_shifting_recipe.cc +++ b/059shape_shifting_recipe.cc @@ -66,29 +66,27 @@ string original_name; :(before "End Recipe Refinements") result.original_name = result.name; -:(before "End Instruction Dispatch(inst, best_score)") -if (best_score == -1) { - trace(9992, "transform") << "no variant found; checking for variant with suitable type ingredients" << end(); - recipe_ordinal exemplar = pick_matching_shape_shifting_variant(variants, inst, best_score); - if (exemplar) { - trace(9992, "transform") << "found variant to specialize: " << exemplar << ' ' << get(Recipe, exemplar).name << end(); - recipe_ordinal new_recipe_ordinal = new_variant(exemplar, inst, caller_recipe); - if (new_recipe_ordinal == 0) goto done_constructing_variant; - variants.push_back(new_recipe_ordinal); - recipe& variant = get(Recipe, new_recipe_ordinal); - // perform all transforms on the new specialization - if (!variant.steps.empty()) { - trace(9992, "transform") << "transforming new specialization: " << variant.name << end(); - for (long long int t = 0; t < SIZE(Transform); ++t) { - (*Transform.at(t))(new_recipe_ordinal); - } +:(after "Static Dispatch Phase 2") +candidates = strictly_matching_shape_shifting_variants(inst, variants); +if (!candidates.empty()) { + recipe_ordinal exemplar = best_shape_shifting_variant(inst, candidates); + trace(9992, "transform") << "found variant to specialize: " << exemplar << ' ' << get(Recipe, exemplar).name << end(); + recipe_ordinal new_recipe_ordinal = new_variant(exemplar, inst, caller_recipe); + if (new_recipe_ordinal == 0) goto skip_shape_shifting_variants; + variants.push_back(new_recipe_ordinal); // side-effect + recipe& variant = get(Recipe, new_recipe_ordinal); + // perform all transforms on the new specialization + if (!variant.steps.empty()) { + trace(9992, "transform") << "transforming new specialization: " << variant.name << end(); + for (long long int t = 0; t < SIZE(Transform); ++t) { + (*Transform.at(t))(new_recipe_ordinal); } - variant.transformed_until = SIZE(Transform)-1; - inst.name = variant.name; - trace(9992, "transform") << "new specialization: " << inst.name << end(); } - done_constructing_variant:; + variant.transformed_until = SIZE(Transform)-1; + trace(9992, "transform") << "new specialization: " << variant.name << end(); + return variant.name; } +skip_shape_shifting_variants:; //: make sure we have no unspecialized shape-shifting recipes being called //: before running mu programs @@ -101,6 +99,73 @@ if (contains_key(Recipe, inst.operation) && inst.operation >= MAX_PRIMITIVE_RECI } :(code) +// phase 2 of static dispatch +vector strictly_matching_shape_shifting_variants(const instruction& inst, vector& variants) { + vector result; + for (long long int i = 0; i < SIZE(variants); ++i) { + if (variants.at(i) == -1) continue; + if (!any_type_ingredient_in_header(variants.at(i))) continue; + if (all_concrete_header_reagents_strictly_match(inst, get(Recipe, variants.at(i)))) + result.push_back(variants.at(i)); + } + return result; +} + +bool all_concrete_header_reagents_strictly_match(const instruction& inst, const recipe& variant) { + if (SIZE(inst.ingredients) < SIZE(variant.ingredients)) { + trace(9993, "transform") << "too few ingredients" << end(); + return false; + } + if (SIZE(variant.products) < SIZE(inst.products)) { + trace(9993, "transform") << "too few products" << end(); + return false; + } + for (long long int i = 0; i < SIZE(variant.ingredients); ++i) { + if (!concrete_types_strictly_match(variant.ingredients.at(i), inst.ingredients.at(i))) { + trace(9993, "transform") << "concrete-type match failed: ingredient " << i << end(); + return false; + } + } + for (long long int i = 0; i < SIZE(inst.products); ++i) { + if (is_dummy(inst.products.at(i))) continue; + if (!concrete_types_strictly_match(variant.products.at(i), inst.products.at(i))) { + trace(9993, "transform") << "strict match failed: product " << i << end(); + return false; + } + } + return true; +} + +// tie-breaker for phase 2 +recipe_ordinal best_shape_shifting_variant(const instruction& inst, vector& candidates) { + assert(!candidates.empty()); + // primary score + long long int max_score = -1; + for (long long int i = 0; i < SIZE(candidates); ++i) { + long long int score = number_of_concrete_types(candidates.at(i)); + assert(score > -1); + if (score > max_score) max_score = score; + } + // break any ties at max_score by a secondary score + long long int min_score2 = 999; + long long int best_index = 0; + for (long long int i = 0; i < SIZE(candidates); ++i) { + long long int score1 = number_of_concrete_types(candidates.at(i)); + assert(score1 <= max_score); + if (score1 != max_score) continue; + const recipe& candidate = get(Recipe, candidates.at(i)); + long long int score2 = (SIZE(candidate.products)-SIZE(inst.products)) + + (SIZE(inst.ingredients)-SIZE(candidate.ingredients)); + assert(score2 < 999); + if (score2 < min_score2) { + min_score2 = score2; + best_index = i; + } + } + return candidates.at(best_index); +} + + string header(const recipe& caller) { if (!caller.has_header) return maybe(caller.name); ostringstream out; @@ -120,65 +185,6 @@ string header(const recipe& caller) { return out.str(); } -recipe_ordinal pick_matching_shape_shifting_variant(vector& variants, const instruction& inst, long long int& best_score) { -//? cerr << "---- " << inst.name << ": " << non_ghost_size(variants) << '\n'; - recipe_ordinal result = 0; - for (long long int i = 0; i < SIZE(variants); ++i) { - if (variants.at(i) == -1) continue; // ghost from a previous test -//? cerr << "-- variant " << i << "\n" << debug_string(get(Recipe, variants.at(i))); - trace(9992, "transform") << "checking shape-shifting variant " << i << ": " << header_label(variants.at(i)) << end(); - long long int current_score = shape_shifting_variant_score(inst, variants.at(i)); - trace(9992, "transform") << "final score: " << current_score << end(); -//? cerr << get(Recipe, variants.at(i)).name << ": " << current_score << '\n'; - if (current_score > best_score) { - trace(9992, "transform") << "matches" << end(); - result = variants.at(i); - best_score = current_score; - } - } - return result; -} - -long long int shape_shifting_variant_score(const instruction& inst, recipe_ordinal variant) { -//? cerr << "======== " << inst.to_string() << '\n'; - if (!any_type_ingredient_in_header(variant)) { - trace(9993, "transform") << "no type ingredients" << end(); -//? cerr << "no type ingredients\n"; - return -1; - } - const vector& header_ingredients = get(Recipe, variant).ingredients; - if (SIZE(inst.ingredients) < SIZE(header_ingredients)) { - trace(9993, "transform") << "too few ingredients" << end(); -//? cerr << "too few ingredients\n"; - return -1; - } - for (long long int i = 0; i < SIZE(header_ingredients); ++i) { - if (!deeply_equal_concrete_types(header_ingredients.at(i), inst.ingredients.at(i))) { - trace(9993, "transform") << "mismatch: ingredient " << i << end(); -//? cerr << "mismatch: ingredient " << i << ": " << debug_string(header_ingredients.at(i)) << " vs " << debug_string(inst.ingredients.at(i)) << '\n'; - return -1; - } - } - if (SIZE(inst.products) > SIZE(get(Recipe, variant).products)) { - trace(9993, "transform") << "too few products" << end(); -//? cerr << "too few products\n"; - return -1; - } - const vector& header_products = get(Recipe, variant).products; - for (long long int i = 0; i < SIZE(inst.products); ++i) { - if (is_dummy(inst.products.at(i))) continue; - if (!deeply_equal_concrete_types(header_products.at(i), inst.products.at(i))) { - trace(9993, "transform") << "mismatch: product " << i << end(); -//? cerr << "mismatch: product " << i << '\n'; - return -1; - } - } - // the greater the number of unused ingredients, the lower the score - return 100 - (SIZE(get(Recipe, variant).products)-SIZE(inst.products)) - - (SIZE(inst.ingredients)-SIZE(get(Recipe, variant).ingredients)) // ok to go negative - + number_of_concrete_types(variant); -} - bool any_type_ingredient_in_header(recipe_ordinal variant) { const recipe& caller = get(Recipe, variant); for (long long int i = 0; i < SIZE(caller.ingredients); ++i) { @@ -192,10 +198,10 @@ bool any_type_ingredient_in_header(recipe_ordinal variant) { return false; } -bool deeply_equal_concrete_types(reagent to, reagent from) { +bool concrete_types_strictly_match(reagent to, reagent from) { canonize_type(to); canonize_type(from); - return deeply_equal_concrete_types(to.properties.at(0).second, from.properties.at(0).second, from); + return concrete_types_strictly_match(to.properties.at(0).second, from.properties.at(0).second, from); } long long int number_of_concrete_types(recipe_ordinal r) { @@ -222,7 +228,7 @@ long long int number_of_concrete_types(const string_tree* type) { return result; } -bool deeply_equal_concrete_types(const string_tree* to, const string_tree* from, const reagent& rhs_reagent) { +bool concrete_types_strictly_match(const string_tree* to, const string_tree* from, const reagent& rhs_reagent) { if (!to) return !from; if (!from) return !to; if (is_type_ingredient_name(to->value)) return true; // type ingredient matches anything @@ -238,8 +244,8 @@ bool deeply_equal_concrete_types(const string_tree* to, const string_tree* from, return rhs_reagent.name == "0"; //? cerr << to->value << " vs " << from->value << '\n'; return to->value == from->value - && deeply_equal_concrete_types(to->left, from->left, rhs_reagent) - && deeply_equal_concrete_types(to->right, from->right, rhs_reagent); + && concrete_types_strictly_match(to->left, from->left, rhs_reagent) + && concrete_types_strictly_match(to->right, from->right, rhs_reagent); } bool contains_type_ingredient_name(const reagent& x) { @@ -470,13 +476,6 @@ void ensure_all_concrete_types(/*const*/ reagent& x, const recipe& exemplar) { } } -long long int non_ghost_size(vector& variants) { - long long int result = 0; - for (long long int i = 0; i < SIZE(variants); ++i) - if (variants.at(i) != -1) ++result; - return result; -} - :(scenario shape_shifting_recipe_2) recipe main [ 10:point <- merge 14, 15 diff --git a/070text.mu b/070text.mu index 56291b75..a37e8a6e 100644 --- a/070text.mu +++ b/070text.mu @@ -297,7 +297,8 @@ recipe to-text n:number -> result:address:shared:array:character [ # add sign { break-unless negate-result:boolean - tmp <- append tmp, 45 # '-' + minus:character <- copy 45/- + tmp <- append tmp, minus } # reverse buffer into text result len:number <- get *tmp, length:offset -- cgit 1.4.1-2-gfad0