rahmenlose Ansicht.gi DruckansichtUnknown {[0] [0] [0]} [Methode: Schwerpunktbildung, einfache Gewichte, sechs Dimensionen]
# SPDX-License-Identifier: GPL-2.0-or-later
# CAP: Categories, Algorithms, Programming
#
# Implementations
#
#! @Chapter Managing Derived Methods
BindGlobal( "TheFamilyOfDerivations",
NewFamily( "TheFamilyOfDerivations" ) );
BindGlobal( "TheFamilyOfDerivationGraphs",
NewFamily( "TheFamilyOfDerivationGraphs" ) );
BindGlobal( "TheFamilyOfOperationWeightLists",
NewFamily( "TheFamilyOfOperationWeightLists" ) );
BindGlobal( "TheTypeOfDerivedMethods", NewType( TheFamilyOfDerivations, IsDerivedMethod ) );
BindGlobal( "TheTypeOfDerivationsGraphs", NewType( TheFamilyOfDerivationGraphs, IsDerivedMethodGraph ) );
BindGlobal( "TheTypeOfOperationWeightLists", NewType( TheFamilyOfOperationWeightLists, IsOperationWeightList ) );
InstallGlobalFunction( "ActivateDerivationInfo",
function( )
SetInfoLevel( DerivationInfo, 1 );
end );
InstallGlobalFunction( "DeactivateDerivationInfo",
function( )
SetInfoLevel( DerivationInfo, 0 );
end );
InstallGlobalFunction( CreateDerivation, function( target_op_name, description, used_ops_with_multiples_and_category_getters, func, weight, category_filter, loop_multiplier, category_getters )
local number_of_proposed_arguments, current_function_argument_number, used_op_names_with_multiples_and_category_getters, collected_list, wrapped_category_filter, derivation, x;
if target_op_name <> "internal dummy function of a final derivation" then
if not IsBound( CAP_INTERNAL_METHOD_NAME_RECORD.(target_op_name) ) then
Error( "trying to create a derviation for a method not in CAP_INTERNAL_METHOD_NAME_RECORD" );
fi;
number_of_proposed_arguments := Length( CAP_INTERNAL_METHOD_NAME_RECORD.(target_op_name).filter_list );
current_function_argument_number := NumberArgumentsFunction( func );
if current_function_argument_number >= 0 and current_function_argument_number <> number_of_proposed_arguments then
Error( "while adding a derivation for ", target_op_name, ": given function has ", current_function_argument_number, " arguments but should have ", number_of_proposed_arguments );
fi;
fi;
#= comment for Julia
if PositionSublist( String( category_filter ), "CanCompute" ) <> fail then
Print( "WARNING: The CategoryFilter of a derivation for ", target_op_name, " uses `CanCompute`. Please register all preconditions explicitly.\n" );
fi;
# =#
# canonicalize used ops
used_op_names_with_multiples_and_category_getters := [ ];
for x in used_ops_with_multiples_and_category_getters do
if Length( x ) < 2 or not IsFunction( x[1] ) or not IsInt( x[2] ) then
Error( "preconditions must be of the form `[op, mult, getter]`, where `getter` is optional" );
fi;
if (Length( x ) = 2 or (Length( x ) = 3 and x[3] = fail)) and NameFunction( x[1] ) = target_op_name then
Error( "A derivation for ", target_op_name, " has itself as a precondition. This is not supported because we cannot compute a well-defined weight.\n" );
fi;
if Length( x ) = 2 then
Add( used_op_names_with_multiples_and_category_getters, [ NameFunction( x[1] ), x[2], fail ] );
elif Length( x ) = 3 then
if x <> fail and not (IsFunction( x[3] ) and NumberArgumentsFunction( x[3] ) = 1) then
Error( "the category getter must be a single-argument function" );
fi;
Add( used_op_names_with_multiples_and_category_getters, [ NameFunction( x[1] ), x[2], x[3] ] );
else
Error( "The list of preconditions must be a list of pairs or triples." );
fi;
od;
#= comment for Julia
if target_op_name <> "internal dummy function of a final derivation" then
collected_list := CAP_INTERNAL_FIND_APPEARANCE_OF_SYMBOL_IN_FUNCTION( func, RecNames( CAP_INTERNAL_METHOD_NAME_RECORD ), loop_multiplier, CAP_INTERNAL_METHOD_RECORD_REPLACEMENTS, category_getters );
if Length( collected_list ) <> Length( used_op_names_with_multiples_and_category_getters ) or not ForAll( collected_list, c -> c in used_op_names_with_multiples_and_category_getters ) then
SortBy( used_op_names_with_multiples_and_category_getters, x -> x[1] );
SortBy( collected_list, x -> x[1] );
Print(
"WARNING: You have installed a derivation for ", target_op_name, " with preconditions ", used_op_names_with_multiples_and_category_getters,
" but the automated detection has detected the following list of preconditions: ", collected_list, ".\n",
"If this is a bug in the automated detection, please report it.\n"
);
fi;
fi;
# =#
if NumberArgumentsFunction( category_filter ) = 0 or NumberArgumentsFunction( category_filter ) > 1 then
Error( "the CategoryFilter of a derivation must accept exactly one argument" );
fi;
if ForAny( used_op_names_with_multiples_and_category_getters, x -> x[3] <> fail ) and category_filter = IsCapCategory then
Print( "WARNING: A derivation for ", target_op_name, " depends on other categories (e.g. RangeCategoryOfHomomorphismStructure) but does no test via the CategoryFilter if the other categories are available (e.g. by testing HasRangeCategoryOfHomomorphismStructure).\n" );
fi;
if IsProperty( category_filter ) then
# for Julia
wrapped_category_filter := cat -> Tester( category_filter )( cat ) and category_filter( cat );
#= comment for Julia
wrapped_category_filter := Tester( category_filter ) and category_filter;
# =#
else
wrapped_category_filter := category_filter;
fi;
derivation := CreateGapObjectWithAttributes( TheTypeOfDerivedMethods,
Description, description,
AdditionalWeight, weight,
DerivationFunction, func,
CategoryFilter, wrapped_category_filter,
TargetOperation, target_op_name,
UsedOperationsWithMultiplesAndCategoryGetters, used_op_names_with_multiples_and_category_getters
);
return derivation;
end );
InstallMethod( String,
[ IsDerivedMethod ],
function( d )
return Concatenation( "derivation ", Description( d ),
" of operation ", TargetOperation( d ) );
end );
InstallMethod( ViewString,
[ IsDerivedMethod ],
function( d )
return Concatenation( "<", String( d ), ">" );
end );
InstallMethod( IsApplicableToCategory,
[ IsDerivedMethod, IsCapCategory ],
function( d, C )
return CategoryFilter( d )( C );
end );
InstallMethod( InstallDerivationForCategory,
[ IsDerivedMethod, IsPosInt, IsCapCategory ],
FunctionWithNamedArguments(
[
[ "IsFinalDerivation", false ],
],
function( CAP_NAMED_ARGUMENTS, d, weight, C )
local method_name, func;
method_name := TargetOperation( d );
func := DerivationFunction( d );
if HasFunctionCalledBeforeInstallation( d ) then
FunctionCalledBeforeInstallation( d )( C );
fi;
AddCapOperation( method_name, C, func, weight : IsDerivation := not(CAP_NAMED_ARGUMENTS.IsFinalDerivation), IsFinalDerivation := CAP_NAMED_ARGUMENTS.IsFinalDerivation );
end ) );
InstallMethod( MakeDerivationGraph,
[ IsDenseList ],
function( operations )
local G, op_name;
G := rec( derivations_by_target := rec(),
derivations_by_used_ops := rec() );
G := ObjectifyWithAttributes( G, TheTypeOfDerivationsGraphs );
SetOperations( G, operations );
for op_name in operations do
G!.derivations_by_target.( op_name ) := [];
G!.derivations_by_used_ops.( op_name ) := [];
od;
# derivations not using any operations
G!.derivations_by_used_ops.none := [];
return G;
end );
InstallMethod( AddOperationsToDerivationGraph,
[ IsDerivedMethodGraph, IsDenseList ],
function( graph, operations )
local op_name;
Append( Operations( graph ), operations );
for op_name in operations do
graph!.derivations_by_target.( op_name ) := [];
graph!.derivations_by_used_ops.( op_name ) := [];
od;
end );
InstallMethod( String,
[ IsDerivedMethodGraph ],
function( G )
return "derivation graph";
end );
InstallMethod( ViewString,
[ IsDerivedMethodGraph ],
function( G )
return Concatenation( "<", String( G ), ">" );
end );
InstallGlobalFunction( AddDerivation,
function( graph, target_op, description, used_ops_with_multiples_and_category_getters, func, weight, category_filter, loop_multiplier, category_getters, function_called_before_installation, is_with_given_derivation, is_autogenerated_by_CompilerForCAP )
local target_op_name, derivation, x;
target_op_name := NameFunction( target_op );
derivation := CreateDerivation(
target_op_name,
description,
used_ops_with_multiples_and_category_getters,
func,
weight,
category_filter,
loop_multiplier,
category_getters
);
if function_called_before_installation <> false then
SetFunctionCalledBeforeInstallation( derivation, function_called_before_installation );
fi;
derivation!.is_with_given_derivation := is_with_given_derivation;
derivation!.is_autogenerated_by_CompilerForCAP := is_autogenerated_by_CompilerForCAP;
if derivation!.is_with_given_derivation and derivation!.is_autogenerated_by_CompilerForCAP then
Error( "WithGiven derivations should not be marked as being autogenerated by CompilerForCAP" );
fi;
Add( graph!.derivations_by_target.(target_op_name), derivation );
derivation!.position_in_derivations_by_target := Length( graph!.derivations_by_target.(target_op_name) );
for x in UsedOperationsWithMultiplesAndCategoryGetters( derivation ) do
# We add all operations, even those with category getters: In case the category getter
# returns the category itself, this allows to recursively trigger derivations correctly.
Add( graph!.derivations_by_used_ops.(x[1]), derivation );
od;
if IsEmpty( UsedOperationsWithMultiplesAndCategoryGetters( derivation ) ) then
Add( graph!.derivations_by_used_ops.none, derivation );
fi;
end );
BindGlobal( "CAP_INTERNAL_DERIVATION_GRAPH", MakeDerivationGraph( [ ] ) );
InstallGlobalFunction( AddDerivationToCAP, FunctionWithNamedArguments(
[
# When compiling categories, a derivation does not cause overhead anymore, so we would like to simply set `Weight` to 0.
# However, the weight 1 is currently needed to prevent the installation of cyclic derivations.
[ "Weight", 1 ],
[ "CategoryFilter", IsCapCategory ],
[ "WeightLoopMultiple", 2 ],
[ "CategoryGetters", Immutable( rec( ) ) ],
[ "FunctionCalledBeforeInstallation", false ],
[ "is_with_given_derivation", false ],
[ "is_autogenerated_by_CompilerForCAP", false ],
],
function( CAP_NAMED_ARGUMENTS, target_op, description, used_ops_with_multiples_and_category_getters, func )
local weight, category_filter, loop_multiplier, category_getters, function_called_before_installation, option_is_with_given_derivation, option_is_autogenerated_by_CompilerForCAP;
weight := CAP_NAMED_ARGUMENTS.Weight;
category_filter := CAP_NAMED_ARGUMENTS.CategoryFilter;
loop_multiplier := CAP_NAMED_ARGUMENTS.WeightLoopMultiple;
category_getters := CAP_NAMED_ARGUMENTS.CategoryGetters;
function_called_before_installation := CAP_NAMED_ARGUMENTS.FunctionCalledBeforeInstallation;
option_is_with_given_derivation := CAP_NAMED_ARGUMENTS.is_with_given_derivation;
option_is_autogenerated_by_CompilerForCAP := CAP_NAMED_ARGUMENTS.is_autogenerated_by_CompilerForCAP;
AddDerivation( CAP_INTERNAL_DERIVATION_GRAPH, target_op, description, used_ops_with_multiples_and_category_getters, func, weight, category_filter, loop_multiplier, category_getters, function_called_before_installation, option_is_with_given_derivation, option_is_autogenerated_by_CompilerForCAP );
end ) );
InstallMethod( DerivationsUsingOperation,
[ IsDerivedMethodGraph, IsString ],
function( G, op_name )
return G!.derivations_by_used_ops.( op_name );
end );
InstallMethod( DerivationsOfOperation,
[ IsDerivedMethodGraph, IsString ],
function( G, op_name )
return G!.derivations_by_target.( op_name );
end );
InstallMethod( MakeOperationWeightList,
[ IsCapCategory, IsDerivedMethodGraph ],
function( C, G )
local operation_weights, operation_derivations, owl, op_name;
operation_weights := rec( );
operation_derivations := rec( );
for op_name in Operations( G ) do
operation_weights.( op_name ) := infinity;
operation_derivations.( op_name ) := fail;
od;
owl := ObjectifyWithAttributes(
rec( operation_weights := operation_weights, operation_derivations := operation_derivations ), TheTypeOfOperationWeightLists,
DerivationGraph, G,
CategoryOfOperationWeightList, C
);
return owl;
end );
InstallMethod( String,
[ IsOperationWeightList ],
function( owl )
return Concatenation( "operation weight list for ",
String( CategoryOfOperationWeightList( owl ) ) );
end );
InstallMethod( ViewString,
[ IsOperationWeightList ],
function( owl )
return Concatenation( "<", String( owl ), ">" );
end );
InstallMethod( CurrentOperationWeight,
[ IsOperationWeightList, IsString ],
function( owl, op_name )
return owl!.operation_weights.( op_name );
end );
InstallMethod( OperationWeightUsingDerivation,
[ IsOperationWeightList, IsDerivedMethod ],
function( owl, d )
local category, category_operation_weights, weight, operation_weights, operation_weight, x;
category := CategoryOfOperationWeightList( owl );
category_operation_weights := owl!.operation_weights;
weight := AdditionalWeight( d );
for x in UsedOperationsWithMultiplesAndCategoryGetters( d ) do
if x[3] = fail then
operation_weights := category_operation_weights;
else
operation_weights := x[3](category)!.derivations_weight_list!.operation_weights;
# the category `x[3](category)` might have been finalized before the operation `x[1]` was added to CAP
if not IsBound( operation_weights.(x[1]) ) then
return infinity;
fi;
fi;
operation_weight := operation_weights.(x[1]);
if operation_weight = infinity then
return infinity;
fi;
weight := weight + operation_weight * x[2];
od;
return weight;
end );
InstallMethod( DerivationOfOperation,
[ IsOperationWeightList, IsString ],
function( owl, op_name )
return owl!.operation_derivations.( op_name );
end );
BindGlobal( "TryToTriggerDerivation", function ( owl, d )
local new_weight, target, current_weight, current_derivation;
if not IsApplicableToCategory( d, CategoryOfOperationWeightList( owl ) ) then
return fail;
fi;
new_weight := OperationWeightUsingDerivation( owl, d );
if new_weight = infinity then
return fail;
fi;
target := TargetOperation( d );
current_weight := CurrentOperationWeight( owl, target );
current_derivation := DerivationOfOperation( owl, target );
if new_weight < current_weight or (new_weight = current_weight and current_derivation <> fail and d!.position_in_derivations_by_target < current_derivation!.position_in_derivations_by_target) then
Info( DerivationInfo, 1, Concatenation( "derive(",
String( new_weight ),
") ",
target,
": ",
Description( d ), "\n" ) );
owl!.operation_weights.( target ) := new_weight;
owl!.operation_derivations.( target ) := d;
# if the weight has not changed, there is no need to re-trigger the chain of derivations
if new_weight <> current_weight then
TriggerDerivationsUsingOperation( owl, target );
fi;
fi;
end );
InstallMethod( TriggerDerivationsUsingOperation,
[ IsOperationWeightList, IsString ],
function( owl, op_name )
local d;
for d in DerivationsUsingOperation( DerivationGraph( owl ), op_name ) do
TryToTriggerDerivation( owl, d );
od;
end );
InstallMethod( Reevaluate,
[ IsOperationWeightList ],
function( owl )
local new_weight, op_name, d;
for op_name in Operations( DerivationGraph( owl ) ) do
for d in DerivationsOfOperation( DerivationGraph( owl ), op_name ) do
TryToTriggerDerivation( owl, d );
od;
od;
end );
InstallMethod( Saturate,
[ IsOperationWeightList ],
function( owl )
local current_weight_list;
while true do
current_weight_list := StructuralCopy( owl!.operation_weights );
Reevaluate( owl );
if current_weight_list = owl!.operation_weights then
break;
fi;
od;
end );
InstallMethod( AddPrimitiveOperation,
[ IsOperationWeightList, IsString, IsInt ],
function( owl, op_name, new_weight )
owl!.operation_weights.( op_name ) := new_weight;
Assert( 0, owl!.operation_derivations.( op_name ) = fail );
end );
InstallMethod( PrintDerivationTree,
[ IsOperationWeightList, IsString ],
function( owl, op_name )
local print_node, get_children;
print_node := function( node )
local w, mult, op, d;
mult := node[ 2 ];
op := node[ 1 ];
if op = fail then
Print( " ", mult );
return;
fi;
w := CurrentOperationWeight( owl, op );
d := DerivationOfOperation( owl, op );
if mult <> fail then
Print( "+ ", mult, " * " );
fi;
if w = infinity then
Print( "(not installed)" );
else
Print( "(", w, ")" );
fi;
Print( " ", op );
if w <> infinity then
Print( " " );
if d = fail then
Print( "[primitive]" );
else
Print( "[derived:", Description( d ), "]" );
fi;
fi;
end;
get_children := function( node )
local op, d;
op := node[ 1 ];
if op = fail then
return [];
fi;
d := DerivationOfOperation( owl, op );
if d = fail then
return [];
else
return Concatenation( [ [ fail, AdditionalWeight( d ) ] ],
UsedOperationsWithMultiplesAndCategoryGetters( d ) );
fi;
end;
PrintTree( [ op_name, fail ],
print_node,
get_children );
end );
InstallMethod( PrintTree,
[ IsObject, IsFunction, IsFunction ],
function( root, print_node, get_children )
PrintTreeRec( root, print_node, get_children, 0 );
end );
InstallMethod( PrintTreeRec,
[ IsObject, IsFunction, IsFunction, IsInt ],
function( node, print_node, get_children, level )
local i, child;
for i in [ 1 .. level ] do
Print( " " );
od;
print_node( node );
Print( "\n" );
for child in get_children( node ) do
PrintTreeRec( child, print_node, get_children, level + 1 );
od;
end );
#################################
##
## Final derivations
##
#################################
InstallValue( CAP_INTERNAL_FINAL_DERIVATION_LIST, [ ] );
InstallGlobalFunction( AddFinalDerivation, FunctionWithNamedArguments(
[
# When compiling categories, a derivation does not cause overhead anymore, so we would like to simply set `Weight` to 0.
# However, the weight 1 is currently needed to prevent the installation of cyclic derivations.
[ "Weight", 1 ],
[ "CategoryFilter", IsCapCategory ],
[ "WeightLoopMultiple", 2 ],
[ "CategoryGetters", Immutable( rec( ) ) ],
[ "FunctionCalledBeforeInstallation", false ],
],
function( CAP_NAMED_ARGUMENTS, target_op, description, can_compute, cannot_compute, func )
AddFinalDerivationBundle(
description, can_compute, cannot_compute, [ target_op, can_compute, func ] :
Weight := CAP_NAMED_ARGUMENTS.Weight,
CategoryFilter := CAP_NAMED_ARGUMENTS.CategoryFilter,
WeightLoopMultiple := CAP_NAMED_ARGUMENTS.WeightLoopMultiple,
CategoryGetters := CAP_NAMED_ARGUMENTS.CategoryGetters,
FunctionCalledBeforeInstallation := CAP_NAMED_ARGUMENTS.FunctionCalledBeforeInstallation
);
end ) );
InstallGlobalFunction( AddFinalDerivationBundle, FunctionWithNamedArguments(
[
# When compiling categories, a derivation does not cause overhead anymore, so we would like to simply set `Weight` to 0.
# However, the weight 1 is currently needed to prevent the installation of cyclic derivations.
[ "Weight", 1 ],
[ "CategoryFilter", IsCapCategory ],
[ "WeightLoopMultiple", 2 ],
[ "CategoryGetters", Immutable( rec( ) ) ],
[ "FunctionCalledBeforeInstallation", false ],
],
function( CAP_NAMED_ARGUMENTS, description, can_compute, cannot_compute, additional_functions... )
local weight, category_filter, loop_multiplier, category_getters, function_called_before_installation, operations_to_install, union_of_collected_lists, derivations, derivation, used_op_names_with_multiples_and_category_getters, dummy_derivation, final_derivation, i, x, current_additional_func;
weight := CAP_NAMED_ARGUMENTS.Weight;
category_filter := CAP_NAMED_ARGUMENTS.CategoryFilter;
loop_multiplier := CAP_NAMED_ARGUMENTS.WeightLoopMultiple;
category_getters := CAP_NAMED_ARGUMENTS.CategoryGetters;
function_called_before_installation := CAP_NAMED_ARGUMENTS.FunctionCalledBeforeInstallation;
if IsEmpty( additional_functions ) then
Error( "trying to add a final derivation without any functions to install" );
fi;
for i in [ 1 .. Length( additional_functions ) ] do
if not (IsList( additional_functions[i] ) and Length( additional_functions[i] ) = 3) then
Error( "additional functions must be given as triples [ <operation>, <preconditions>, <function> ]" );
fi;
if IsList( Last( additional_functions[i] ) ) then
Error( "passing lists of functions to `AddFinalDerivation` is not supported anymore" );
fi;
if not additional_functions[i][1] in cannot_compute then
Print( "WARNING: A final derivation installs ", NameFunction( additional_functions[i][1] ), " but does not list it in its exclude list.\n" );
fi;
od;
for x in can_compute do
if Length( x ) < 2 or not IsFunction( x[1] ) or not IsInt( x[2] ) then
Error( "preconditions must be of the form `[op, mult, getter]`, where `getter` is optional" );
fi;
# check that preconditions do not appear in cannot_compute (which in particular includes all operations installed by this final derivation, as checked above)
if (Length( x ) = 2 or (Length( x ) = 3 and x[3] = fail)) and x[1] in cannot_compute then
Error( "A final derivation for ", NameFunction( additional_functions[1][1] ), " has precondition ", NameFunction( x[1] ), " which is also in its exclude list.\n" );
fi;
od;
if Length( additional_functions ) = 1 and StartsWith( NameFunction( additional_functions[1][1] ), "IsomorphismFrom" ) then
Print( "WARNING: You are installing a final derivation for ", NameFunction( additional_functions[1][1] ), " which does not include its inverse. You should probably use a bundled final derivation to also install its inverse.\n" );
fi;
## Find symbols in functions
operations_to_install := [ ];
union_of_collected_lists := [ ];
derivations := [ ];
for current_additional_func in additional_functions do
derivation := CreateDerivation(
NameFunction( current_additional_func[1] ),
Concatenation( description, " (final derivation)" ),
current_additional_func[2],
current_additional_func[3],
weight,
category_filter,
loop_multiplier,
category_getters
);
Add( derivations, derivation );
used_op_names_with_multiples_and_category_getters := UsedOperationsWithMultiplesAndCategoryGetters( derivation );
# Operations may use operations from the same final derivation as long as the latter are installed before the former.
# In this case, the used operations are no preconditions and thus should not go into union_of_collected_lists.
used_op_names_with_multiples_and_category_getters := Filtered( used_op_names_with_multiples_and_category_getters, x -> not x[1] in operations_to_install );
Add( operations_to_install, NameFunction( current_additional_func[1] ) );
union_of_collected_lists := CAP_INTERNAL_MERGE_PRECONDITIONS_LIST( union_of_collected_lists, used_op_names_with_multiples_and_category_getters );
od;
# only used to check if we can install all the derivations in `derivations`
dummy_derivation := CreateDerivation(
"internal dummy function of a final derivation",
"dummy derivation",
can_compute,
ReturnTrue,
1,
category_filter,
loop_multiplier,
category_getters
);
used_op_names_with_multiples_and_category_getters := UsedOperationsWithMultiplesAndCategoryGetters( dummy_derivation );
if Length( union_of_collected_lists ) <> Length( used_op_names_with_multiples_and_category_getters ) or not ForAll( union_of_collected_lists, c -> c in used_op_names_with_multiples_and_category_getters ) then
used_op_names_with_multiples_and_category_getters := ShallowCopy( used_op_names_with_multiples_and_category_getters );
SortBy( used_op_names_with_multiples_and_category_getters, x -> x[1] );
SortBy( union_of_collected_lists, x -> x[1] );
Print(
"WARNING: You have installed a final derivation for ", TargetOperation( derivations[1] ), " with preconditions ", used_op_names_with_multiples_and_category_getters,
" but the following list of preconditions was expected: ", union_of_collected_lists, ".\n",
"If this is a bug in the automated detection, please report it.\n"
);
fi;
final_derivation := rec(
dummy_derivation := dummy_derivation,
cannot_compute := List( cannot_compute, x -> NameFunction( x ) ),
derivations := derivations,
function_called_before_installation := function_called_before_installation,
);
Add( CAP_INTERNAL_FINAL_DERIVATION_LIST, final_derivation );
end ) );
#################################
##
## Installing derivations
##
#################################
InstallGlobalFunction( InstallDerivations, function( category )
local weight_list, derivation_list, current_install, current_final_derivation, op_name, new_weight, current_weight, i, derivation, operation;
weight_list := MakeOperationWeightList( category, CAP_INTERNAL_DERIVATION_GRAPH );
category!.derivations_weight_list := weight_list;
for op_name in RecNames( category!.operations ) do
Assert( 0, category!.operations.(op_name).type in [ "primitive_installation", "precompiled_derivation" ] );
AddPrimitiveOperation( weight_list, op_name, category!.operations.(op_name).weight );
od;
# Trigger ordinary derivations, but do not install them yet:
# While triggering derivations, cheaper derivations can become available, but we do not want to overwrite methods.
TriggerDerivationsUsingOperation( weight_list, "none" );
for op_name in SortedList( RecNames( weight_list!.operation_weights ) ) do
if weight_list!.operation_weights.(op_name) <> infinity and weight_list!.operation_derivations.(op_name) = fail then
Info( DerivationInfo, 1, Concatenation( "add(",
String( weight_list!.operation_weights.(op_name) ),
") ",
op_name,
": primitive installation\n" ) );
TriggerDerivationsUsingOperation( weight_list, op_name );
fi;
od;
# Trigger and install final derivations
derivation_list := ShallowCopy( CAP_INTERNAL_FINAL_DERIVATION_LIST );
while true do
current_install := fail;
for i in [ 1 .. Length( derivation_list ) ] do
current_final_derivation := derivation_list[ i ];
# check if all conditions for installing the final derivation are met
if not IsApplicableToCategory( current_final_derivation.dummy_derivation, category ) then
continue;
fi;
if ForAny( current_final_derivation.cannot_compute, operation_name -> CurrentOperationWeight( weight_list, operation_name ) < infinity ) then
continue;
fi;
if OperationWeightUsingDerivation( weight_list, current_final_derivation.dummy_derivation ) = infinity then
continue;
fi;
# if we get here, everything matched
current_install := i;
break;
od;
if current_install = fail then
break;
else
current_final_derivation := Remove( derivation_list, current_install );
## call function before adding the method
if current_final_derivation.function_called_before_installation <> false then
current_final_derivation.function_called_before_installation( category );
fi;
for derivation in current_final_derivation.derivations do
op_name := TargetOperation( derivation );
new_weight := OperationWeightUsingDerivation( weight_list, derivation );
current_weight := CurrentOperationWeight( weight_list, op_name );
Assert( 0, new_weight <> infinity );
# When installing a final derivation bundle, the installation of the first operations in the bundle
# might trigger (normal) derivations of later operations it the bundle, which might be cheaper then
# the derivations provided in the bundle.
if new_weight <= current_weight then
Info( DerivationInfo, 1, Concatenation( "derive(",
String( new_weight ),
") ",
op_name,
": ",
Description( derivation ), "\n" ) );
weight_list!.operation_weights.( op_name ) := new_weight;
weight_list!.operation_derivations.( op_name ) := fail;
InstallDerivationForCategory( derivation, new_weight, category : IsFinalDerivation := true );
# if the weight has not changed, there is no need to re-trigger the chain of derivations
if new_weight <> current_weight then
TriggerDerivationsUsingOperation( weight_list, op_name );
fi;
fi;
od;
fi;
od;
# Actually install ordinary derivations
for operation in Operations( DerivationGraph( weight_list ) ) do
if DerivationOfOperation( weight_list, operation ) <> fail then
InstallDerivationForCategory( DerivationOfOperation( weight_list, operation ), CurrentOperationWeight( weight_list, operation ), category );
fi;
od;
end );
#################################
##
## Some print functions
##
#################################
##
InstallGlobalFunction( InstalledMethodsOfCategory,
function( cell )
local weight_list, list_of_methods, i, current_weight, can_compute, cannot_compute;
if IsCapCategory( cell ) then
weight_list := cell!.derivations_weight_list;
elif IsCapCategoryCell( cell ) then
weight_list := CapCategory( cell )!.derivations_weight_list;
else
Error( "Input must be a category or a cell" );
fi;
list_of_methods := Operations( CAP_INTERNAL_DERIVATION_GRAPH );
list_of_methods := AsSortedList( list_of_methods );
can_compute := [ ];
cannot_compute := [ ];
for i in list_of_methods do
current_weight := CurrentOperationWeight( weight_list, i );
if current_weight < infinity then
Add( can_compute, [ i, current_weight ] );
else
Add( cannot_compute, i );
fi;
od;
Print( "Can do the following basic methods at the moment:\n" );
for i in can_compute do
Print( "+ ", i[ 1 ], ", weight ", String( i[ 2 ] ), "\n" );
od;
Print( "\nThe following is still missing:\n" );
for i in cannot_compute do
Print( "- ", i, "\n" );
od;
Print( "\nPlease use DerivationsOfMethodByCategory( <category>, <name> ) to get\n",
"information about how to add the missing methods\n" );
end );
##
InstallGlobalFunction( DerivationsOfMethodByCategory,
function( category, name )
local current_derivation, currently_installed_func, weight_list, category_getter_string, possible_derivations, category_filter, weight, found, x, final_derivation;
if IsFunction( name ) then
name := NameFunction( name );
fi;
if not IsString( name ) then
Error( "Usage is <category>,<string> or <category>,<CAP operation>\n" );
return;
fi;
if not IsBound( CAP_INTERNAL_METHOD_NAME_RECORD.(name) ) then
Error( name, " is not the name of a CAP operation." );
return;
fi;
if CanCompute( category, name ) then
Print( Name( category ), " can already compute ", TextAttr.b4, name, TextAttr.reset, " with weight " , OperationWeight( category, name ), ".\n" );
if category!.operations.( name ).type = "primitive_installation" then
Print( "It was installed primitively.\n" );
elif category!.operations.( name ).type = "final_derivation" then
Print( "It was installed as a final derivation.\n" );
elif category!.operations.( name ).type = "precompiled_derivation" then
Print( "It was installed as a precompiled derivation.\n" );
elif category!.operations.( name ).type = "ordinary_derivation" then
current_derivation := DerivationOfOperation( category!.derivations_weight_list, name );
Print( "It was derived by ", TextAttr.b3, Description( current_derivation ), TextAttr.reset, " using \n" );
for x in UsedOperationsWithMultiplesAndCategoryGetters( current_derivation ) do
if x[3] = fail then
weight_list := category!.derivations_weight_list;
category_getter_string := "";
else
weight_list := x[3](category)!.derivations_weight_list;
category_getter_string := Concatenation( " in category obtained by applying ", String( x[3] ) );
fi;
Print( "* ", TextAttr.b2, x[1], TextAttr.reset, " (", x[2], "x)", category_getter_string );
Print( " installed with weight ", String( CurrentOperationWeight( weight_list, x[1] ) ) );
Print( "\n" );
od;
Assert( 0, IsIdenticalObj( category!.operations.( name ).func, DerivationFunction( current_derivation ) ) );
else
Error( "this should never happen" );
fi;
currently_installed_func := category!.operations.( name ).func;
Print( "\nThe following function was installed for this operation:\n\n" );
Display( currently_installed_func );
Print( "\n" );
Print( "Source: ", FilenameFunc( currently_installed_func ), ":", StartlineFunc( currently_installed_func ), "\n" );
Print( "\n" );
Print( "#######\n\n" );
else
Print( TextAttr.b4, name, TextAttr.reset, " is currently not installed for ", Name( category ), ".\n\n" );
fi;
Print( "Possible derivations are:\n\n" );
possible_derivations := List( DerivationsOfOperation( CAP_INTERNAL_DERIVATION_GRAPH, name ), d -> rec( derivation := d ) );
for final_derivation in CAP_INTERNAL_FINAL_DERIVATION_LIST do
for current_derivation in final_derivation.derivations do
if TargetOperation( current_derivation ) = name then
Add( possible_derivations, rec(
derivation := current_derivation,
can_compute := UsedOperationsWithMultiplesAndCategoryGetters( final_derivation.dummy_derivation ),
cannot_compute := final_derivation.cannot_compute,
) );
fi;
od;
od;
for current_derivation in possible_derivations do
category_filter := CategoryFilter( current_derivation.derivation );
# `SizeScreen()[1] - 3` is taken from the code for package banners
Print( ListWithIdenticalEntries( SizeScreen()[1] - 3, '-' ), "\n" );
if category_filter( category ) then
Print( TextAttr.b4, name, TextAttr.reset, " can be derived by\n" );
else
if IsFilter( category_filter ) then
Print( "If ", Name( category ), " would be ", JoinStringsWithSeparator( Filtered( NamesFilter( category_filter ), name -> not StartsWith( name, "Has" ) ), " and " ) );
else
Print( "If ", Name( category ), " would fulfill the conditions given by\n\n" );
Display( category_filter );
fi;
Print( "\nthen ", TextAttr.b4, name, TextAttr.reset, " could be derived by\n" );
fi;
for x in UsedOperationsWithMultiplesAndCategoryGetters( current_derivation.derivation ) do
if x[3] = fail then
if CanCompute( category, x[1] ) then
weight := OperationWeight( category, x[1] );
else
weight := infinity;
fi;
category_getter_string := "";
else
if category_filter( category ) and CanCompute( x[3](category), x[1] ) then
weight := OperationWeight( x[3](category), x[1] );
else
weight := infinity;
fi;
category_getter_string := Concatenation( " in the category obtained by applying ", String( x[3] ) );
fi;
if weight < infinity then
Print( "* ", TextAttr.b2, x[1], TextAttr.reset, " (", x[2], "x)", category_getter_string, ", (already installed with weight ", weight,")" );
else
Print( "* ", TextAttr.b1, x[1], TextAttr.reset, " (", x[2], "x)", category_getter_string );
fi;
Print( "\n" );
od;
Print( "with additional weight ", AdditionalWeight( current_derivation.derivation ) );
Assert( 0, IsBound( current_derivation.can_compute ) = IsBound( current_derivation.cannot_compute ) );
if IsBound( current_derivation.can_compute ) then
Print( "\n\nas a final derivation\nif the following additional operations could be computed\n" );
found := false;
for x in current_derivation.can_compute do
if x[3] = fail then
if CanCompute( category, x[1] ) then
weight := OperationWeight( category, x[1] );
else
weight := infinity;
fi;
category_getter_string := "";
else
if category_filter( category ) and CanCompute( x[3](category), x[1] ) then
weight := OperationWeight( x[3](category), x[1] );
else
weight := infinity;
fi;
category_getter_string := Concatenation( " in the category obtained by applying ", String( x[3] ) );
fi;
if weight = infinity then
Print( "* ", x[1], category_getter_string, "\n" );
found := true;
fi;
od;
if not found then
Print( "(none)\n" );
fi;
Print( "\nand the following additional operations could not be computed\n" );
found := false;
for x in current_derivation.cannot_compute do
if CanCompute( category, x ) then
Print( "* ", x, "\n" );
found := true;
fi;
od;
if not found then
Print( "(none)\n" );
fi;
else
Print( ".\n" );
fi;
Print( "\n" );
od;
end );
