GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it
#############################################################################
##
## CAP package
##
## Copyright 2013, Sebastian Gutsche, TU Kaiserslautern
## Sebastian Posur, RWTH Aachen
##
#! @Chapter Managing Derived Methods
#!
##
#############################################################################
####################################
##
#! @Section Info Class
##
####################################
#! @Description
#! Info class for derivations.
DeclareInfoClass( "DerivationInfo" );
#!
DeclareGlobalFunction( "ActivateDerivationInfo" );
#!
DeclareGlobalFunction( "DeactivateDerivationInfo" );
####################################
##
#! @Section Derivation Objects
##
####################################
#! @Description
#! A derivation object describes a derived method.
#! It contains information about which operation the derived method
#! implements, and which other operations it relies on.
DeclareCategory( "IsDerivedMethod", IsObject );
#! @Description
#! Creates a new derivation object.
#! The argument <A>name</A> is an arbitrary name used to
#! identify this derivation, and is useful only for debugging
#! purposes.
#! The argument <A>target_op</A> is the operation which
#! the derived method implements.
#! The argument <A>used_ops_with_multiples</A> contains each
#! operation used by the derived method, together with a positive
#! integer specifying how many times that operation is used.
#! This is given as a list of lists, where each sublist has as
#! first entry an operation and as second entry an integer.
#! The argument <A>weight</A> is an additional number to add
#! when calculating the resulting weight of the target operation
#! using this derivation. Unless there is any particular reason
#! to regard the derivation as exceedingly expensive, this number
#! should be <C>1</C>.
#! The argument <A>implementations_with_extra_filters</A> contains
#! one or more functions with the actual implementation of the
#! derived method, together with lists of extra argument filters
#! for each function. The argument is a list with entries of the
#! form <C>[fun, filters]</C>, where <C>fun</C> is a function and
#! <C>filters</C> is a (not necessarily dense) list of argument
#! filters. If only one function is given, then <C>filters</C>
#! should be the empty list; in this case the argument's value
#! would be [[fun,[]]], where <C>fun</C> is the function.
#! The argument <A>category_filter</A> is a filter describing
#! which categories the derivation is valid for. If it is valid
#! for all categories, then this argument should have the value
#! <C>IsCapCategory</C>.
#! @Arguments name, target_op, used_ops_with_multiples, weight, implementations_with_extra_filters, category_filter
DeclareOperation( "MakeDerivation",
[ IsString, IsFunction, IsDenseList,
IsPosInt, IsDenseList, IsFunction ] );
#! @Description
#! The name of the derivation. This is a name identifying this
#! particular derivation, and normally not the same as the name
#! of the operation implemented by the derivation.
#! @Arguments d
DeclareAttribute( "DerivationName", IsDerivedMethod );
#! @Description
#! Extra weight for the derivation.
#! @Arguments d
DeclareAttribute( "DerivationWeight", IsDerivedMethod );
#! @Description
#! The implementation(s) of the derivation, together with lists
#! of extra filters for each implementation.
#! @Arguments d
DeclareAttribute( "DerivationFunctionsWithExtraFilters", IsDerivedMethod );
#! @Description
#! Filter describing which categories the derivation is valid for.
#! @Arguments d
DeclareAttribute( "CategoryFilter", IsDerivedMethod );
#! @Description
#! Checks if the derivation is known to be valid for a given category.
#! @Arguments d, C
#! @Returns <C>true</C> if the category <A>C</A> is known to satisfy
#! the category filter of the derivation <A>d</A>.
DeclareOperation( "IsApplicableToCategory", [ IsDerivedMethod, IsCapCategory ] );
#! @Arguments d
#! @Returns
#! The name (as a string) of the operation implemented
#! by the derivation <A>d</A>
DeclareAttribute( "TargetOperation", IsDerivedMethod );
#! @Arguments d
#! @Returns
#! The names (as strings) of the operations used by the
#! derivation <A>d</A>
DeclareAttribute( "UsedOperations", IsDerivedMethod );
#! @Arguments d
#! @Returns
#! Multiplicities of each operation used by the derivation
#! <A>d</A>, in order corresponding to the operation names
#! returned by <C>UsedOperations(d)</C>.
DeclareAttribute( "UsedOperationMultiples", IsDerivedMethod );
#! @Arguments d
#! @Returns
#! The names of the operations used by the derivation <A>d</A>,
#! together with their multiplicities.
#! The result is a list consisting of lists of the form
#! <C>[op_name, mult]</C>, where <C>op_name</C> is a string
#! and <C>mult</C> a positive integer.
DeclareAttribute( "UsedOperationsWithMultiples", IsDerivedMethod );
#! @Description
#! Install the derived method <A>d</A> for the category <A>C</A>.
#! The integer <A>weight</A> is the computed weight of the operation
#! implemented by this derivation.
#! @Arguments d, weight, C
DeclareOperation( "InstallDerivationForCategory",
[ IsDerivedMethod, IsPosInt, IsCapCategory ] );
#! @Description
#! Computes the resulting weight of the target operation of this
#! derivation given a list of weights for the operations it uses.
#! The argument <A>op_weights</A> should be a list of integers
#! specifying weights for the operations given by
#! <C>UsedOperations( d )</C>, in the same order.
#! @Arguments d, op_weights
DeclareOperation( "DerivationResultWeight",
[ IsDerivedMethod, IsDenseList ] );
####################################
##
#! @Section Derivation Graphs
##
####################################
#! @Description
#! A derivation graph consists of a set of operations and a set of derivations
#! specifying how some operations can be implemented in terms of other operations.
DeclareCategory( "IsDerivedMethodGraph", IsObject );
#! @Description
#! Make a derivation graph containing the given set of operations and no derivations.
#! The argument <A>operations</A> should be a list of strings, the names of the
#! operations. The set of operations is fixed once the graph is created.
#! Derivations can be added to the graph by calling <C>AddDerivation</C>.
#! @Arguments operations
DeclareOperation( "MakeDerivationGraph", [ IsDenseList ] );
#! @Description Adds a list of operation names <A>operations</A> to a given derivation graph <A>graph</A>.
#! This is used in extensions of CAP which want to have their own primitive operations,
#! but do not want to pollute the CAP kernel any more. Please use it with caution. If
#! a weight list/category was created before it will not be aware of the operations.
#! @Arguments graph, operations
DeclareOperation( "AddOperationsToDerivationGraph", [ IsDerivedMethodGraph, IsDenseList ] );
#! @Description
#! Add a derivation to a derivation graph.
#! @Arguments G, d
DeclareOperation( "AddDerivation", [ IsDerivedMethodGraph, IsDerivedMethod ] );
#!
DeclareOperation( "AddDerivation", [ IsDerivedMethodGraph, IsFunction, IsDenseList, IsObject ] );
#!
DeclareOperation( "AddDerivation", [ IsDerivedMethodGraph, IsFunction, IsDenseList ] );
#!
DeclareOperation( "AddDerivation", [ IsDerivedMethodGraph, IsFunction, IsFunction ] );
#!
DeclareOperation( "AddDerivationPair", [ IsDerivedMethodGraph, IsFunction, IsFunction, IsDenseList, IsDenseList, IsDenseList ] );
DeclareOperation( "AddDerivationPair", [ IsDerivedMethodGraph, IsFunction, IsFunction, IsDenseList, IsDenseList ] );
DeclareOperation( "AddDerivationPair", [ IsDerivedMethodGraph, IsFunction, IsFunction, IsDenseList, IsFunction, IsFunction ] );
DeclareOperation( "AddDerivationPair", [ IsDerivedMethodGraph, IsFunction, IsFunction, IsFunction, IsFunction ] );
#!
DeclareGlobalFunction( "AddDerivationToCAP" );
#!
DeclareGlobalFunction( "AddDerivationPairToCAP" );
#!
DeclareGlobalFunction( "AddWithGivenDerivationPairToCAP" );
#! @Description
#! Gives the operations in the graph <A>G</A>, as a list of strings.
#! @Arguments G
DeclareAttribute( "Operations", IsDerivedMethodGraph, "mutable" );
#! @Description
#! Finds all the derivations in the graph <A>G</A> that use the operation named
#! <A>op_name</A>, and returns them as a list.
#! @Arguments G, op_name
DeclareOperation( "DerivationsUsingOperation", [ IsDerivedMethodGraph, IsString ] );
#! @Description
#! Finds all the derivations in the graph <A>G</A> targeting the operation named
#! <A>op_name</A> (that is, the derivations that provide implementations of this
#! operation), and returns them as a list.
#! @Arguments G, op_name
DeclareOperation( "DerivationsOfOperation", [ IsDerivedMethodGraph, IsString ] );
####################################
##
#! @Section Managing Derivations in a Category
##
####################################
#! @Description
#! An operation weight list manages the use of derivations in a single category $C$.
#! For every operation, it keeps a weight value which indicates how costly it is
#! to perform that operation in the category $C$. Whenever a new operation is
#! implemented in $C$, the operation weight list should be notified about this and
#! given a weight to assign to this operation. It will then automatically install
#! all possible derived methods for $C$ in such a way that every operation has the
#! smallest possible weight (the weight of a derived method is computed by using
#! the weights of the operations it uses; see <C>DerivationResultWeight</C>).
DeclareCategory( "IsOperationWeightList", IsObject );
#! @Description
#! Create the operation weight list for a category.
#! This should only be done once for every category, and the category should
#! afterwards remember the returned object.
#! The argument <A>C</A> is the CAP category this operation weight list is associated to,
#! and the argument <A>G</A> is a derivation graph containing operation names and derivations.
#! @Arguments C, G
DeclareOperation( "MakeOperationWeightList", [ IsCapCategory, IsDerivedMethodGraph ] );
#! @Description
#! Returns the derivation graph used by the operation weight list <A>owl</A>.
#! @Arguments owl
DeclareAttribute( "DerivationGraph", IsOperationWeightList );
#! @Description
#! Returns the CAP category associated to the operation weight list <A>owl</A>.
#! @Arguments owl
DeclareAttribute( "CategoryOfOperationWeightList", IsOperationWeightList );
#! @Description
#! Returns the current weight of the operation named <A>op_name</A>.
#! @Arguments owl, op_name
DeclareOperation( "CurrentOperationWeight", [ IsOperationWeightList, IsString ] );
#! @Description
#! Finds out what the weight of the operation implemented by the derivation <A>d</A>
#! would be if we had used that derivation.
#! @Arguments owl, d
DeclareOperation( "OperationWeightUsingDerivation",
[ IsOperationWeightList, IsDerivedMethod ] );
#! @Description
#! Returns the derivation which is currently used to implement the operation
#! named <A>op_name</A>.
#! If the operation is not implemented by a derivation (that is, either implemented
#! directly or not implemented at all), then <C>fail</C> is returned.
#! @Arguments owl, op_name
DeclareOperation( "DerivationOfOperation", [ IsOperationWeightList, IsString ] );
#! @Description
#! Performs a search from the operation <A>op_name</A>, and installs all derivations
#! that give improvements over the current state.
#! This is used internally by <C>AddPrimitiveOperation</C> and <C>Reevaluate</C>.
#! It should normally not be necessary to call this function directly.
#! @Arguments owl, op_name
DeclareOperation( "InstallDerivationsUsingOperation",
[ IsOperationWeightList, IsString ] );
#! @Description
#! Reevaluate the installed derivations, installing better derivations if possible.
#! This should be called if new derivations become available for the category,
#! either because the category has acquired more knowledge about itself
#! (e.g. it is told that it is abelian)
#! or because new derivations have been added to the graph.
#! @Arguments owl
DeclareOperation( "Reevaluate", [ IsOperationWeightList ] );
#! @Description
#! Add the operation named <A>op_name</A> to the operation weight list <A>owl</A>
#! with weight <A>weight</A>.
#! This causes all operations that can be derived, directly or indirectly,
#! from the newly added operation to be installed as well
#! (unless they are already installed with the same or lower weight).
#! @Arguments owl, op_name, weight
DeclareOperation( "AddPrimitiveOperation", [ IsOperationWeightList, IsString, IsInt ] );
#! @Description
#! Print a tree representation of the way the operation named <A>op_name</A>
#! is implemented in the category of the operation weight list <A>owl</A>.
#! @Arguments owl, op_name
DeclareOperation( "PrintDerivationTree",
[ IsOperationWeightList, IsString ] );
#! @Description
#! Prints a tree structure.
DeclareOperation( "PrintTree", [ IsObject, IsFunction, IsFunction ] );
DeclareOperation( "PrintTreeRec",
[ IsObject, IsFunction, IsFunction, IsInt ] );
####################################
##
#! @Section Min Heaps for Strings
##
####################################
#! This section describes an implementation of min heaps for storing strings with
#! associated integer keys, used internally by operation weight lists.
#! @Description
#! A string min heap is a min heap where every node contains a string label and an
#! integer key.
DeclareCategory( "IsStringMinHeap", IsObject );
#! @Description
#! Create an empty string min heap.
DeclareGlobalFunction( "StringMinHeap" );
#! @Description
#! Add a new node containing the label <A>string</A> and the key <A>key</A>
#! to the heap <A>H</A>.
#! @Arguments H, string, key
DeclareOperation( "Add", [ IsStringMinHeap, IsString, IsInt ] );
#! @Description
#! Remove a node with minimal key value from the heap <A>H</A>, and return it.
#! The return value is a list <C>[ label, key ]</C>, where <C>label</C>
#! is the extracted node's label (a string) and <C>key</C> is the
#! node's key (an integer).
#! @Arguments H
DeclareOperation( "ExtractMin", [ IsStringMinHeap ] );
#! @Description
#! Decrease the key value for the node with label <A>string</A> in the
#! heap <A>H</A>. The new key value is given by <A>key</A> and must be
#! smaller than the node's current value.
#! @Arguments H, string, key
DeclareOperation( "DecreaseKey", [ IsStringMinHeap, IsString, IsInt ] );
#! @Description
#! Returns <C>true</C> if the heap <A>H</A> is empty, <C>false</C> otherwise.
#! @Arguments H
DeclareOperation( "IsEmptyHeap", [ IsStringMinHeap ] );
#! @Description
#! Returns the number of nodes in the heap <A>H</A>.
#! @Arguments H
DeclareOperation( "HeapSize", [ IsStringMinHeap ] );
#! @Description
#! Returns <C>true</C> if the heap <A>H</A> contains a node with
#! label <A>string</A>, and <C>false</C> otherwise.
#! @Arguments H, string
DeclareOperation( "Contains", [ IsStringMinHeap, IsString ] );
#! @Description
#! Swaps two elements in the list used to implement the heap,
#! and updates the heap's internal mapping of labels to list indices.
#! This is an internal function which should only be called from the
#! functions that implement the heap functionality.
#! @Arguments H, i, j
DeclareOperation( "Swap", [ IsStringMinHeap, IsPosInt, IsPosInt ] );
#! @Description
#! Heapify the heap <A>H</A>, starting from index <A>i</A>.
#! This is an internal function.
#! @Arguments H, i
DeclareOperation( "Heapify", [ IsStringMinHeap, IsPosInt ] );
#################################
##
## Some print functions
##
#################################
DeclareGlobalFunction( "InstalledMethodsOfCategory" );
DeclareGlobalFunction( "DerivationsOfMethodByCategory" );
DeclareGlobalFunction( "ListInstalledOperationsOfCategory" );
DeclareGlobalFunction( "ListPrimitivelyInstalledOperationsOfCategory" );
DeclareGlobalFunction( "CAP_INTERNAL_DERIVATION_SANITY_CHECK" );