[MathJax off]
8 Managing Derived Methods
8.1 Info Class
8.1-1 DerivationInfo
‣ DerivationInfo | ( info class ) |
Info class for derivations.
8.1-2 ActivateDerivationInfo
‣ ActivateDerivationInfo( arg ) | ( function ) |
8.1-3 DeactivateDerivationInfo
‣ DeactivateDerivationInfo( arg ) | ( function ) |
8.2 Derivation Objects
8.2-1 IsDerivedMethod
‣ IsDerivedMethod( arg ) | ( filter ) |
Returns: true or false
A derivation object describes a derived method. It contains information about which operation the derived method implements, and which other operations it relies on.
8.2-2 MakeDerivation
‣ MakeDerivation( name, target_op, used_ops_with_multiples, weight, implementations_with_extra_filters, category_filter ) | ( operation ) |
Creates a new derivation object. The argument name is an arbitrary name used to identify this derivation, and is useful only for debugging purposes. The argument target_op is the operation which the derived method implements. The argument used_ops_with_multiples 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 weight 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 1. The argument implementations_with_extra_filters 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 [fun, filters], where fun is a function and filters is a (not necessarily dense) list of argument filters. If only one function is given, then filters should be the empty list; in this case the argument's value would be [[fun,[]]], where fun is the function. The argument category_filter 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 IsCapCategory.
8.2-3 DerivationName
‣ DerivationName( d ) | ( attribute ) |
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.
8.2-4 DerivationWeight
‣ DerivationWeight( d ) | ( attribute ) |
Extra weight for the derivation.
8.2-5 DerivationFunctionsWithExtraFilters
‣ DerivationFunctionsWithExtraFilters( d ) | ( attribute ) |
The implementation(s) of the derivation, together with lists of extra filters for each implementation.
8.2-6 CategoryFilter
‣ CategoryFilter( d ) | ( attribute ) |
Filter describing which categories the derivation is valid for.
8.2-7 IsApplicableToCategory
‣ IsApplicableToCategory( d, C ) | ( operation ) |
Returns: true if the category C is known to satisfy the category filter of the derivation d.
Checks if the derivation is known to be valid for a given category.
8.2-8 TargetOperation
‣ TargetOperation( d ) | ( attribute ) |
Returns: The name (as a string) of the operation implemented by the derivation d
8.2-9 UsedOperations
‣ UsedOperations( d ) | ( attribute ) |
Returns: The names (as strings) of the operations used by the derivation d
8.2-10 UsedOperationMultiples
‣ UsedOperationMultiples( d ) | ( attribute ) |
Returns: Multiplicities of each operation used by the derivation d, in order corresponding to the operation names returned by UsedOperations(d).
8.2-11 UsedOperationsWithMultiples
‣ UsedOperationsWithMultiples( d ) | ( attribute ) |
Returns: The names of the operations used by the derivation d, together with their multiplicities. The result is a list consisting of lists of the form [op_name, mult], where op_name is a string and mult a positive integer.
8.2-12 InstallDerivationForCategory
‣ InstallDerivationForCategory( d, weight, C ) | ( operation ) |
Install the derived method d for the category C. The integer weight is the computed weight of the operation implemented by this derivation.
8.2-13 DerivationResultWeight
‣ DerivationResultWeight( d, op_weights ) | ( operation ) |
Computes the resulting weight of the target operation of this derivation given a list of weights for the operations it uses. The argument op_weights should be a list of integers specifying weights for the operations given by UsedOperations( d ), in the same order.
8.3 Derivation Graphs
8.3-1 IsDerivedMethodGraph
‣ IsDerivedMethodGraph( arg ) | ( filter ) |
Returns: true or false
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.
8.3-2 MakeDerivationGraph
‣ MakeDerivationGraph( operations ) | ( operation ) |
Make a derivation graph containing the given set of operations and no derivations. The argument operations 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 AddDerivation.
8.3-3 AddOperationsToDerivationGraph
‣ AddOperationsToDerivationGraph( graph, operations ) | ( operation ) |
Adds a list of operation names operations to a given derivation graph graph. 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.
8.3-4 AddDerivation
‣ AddDerivation( G, d ) | ( operation ) |
Add a derivation to a derivation graph.
8.3-5 AddDerivation
‣ AddDerivation( arg1, arg2, arg3, arg4 ) | ( operation ) |
8.3-6 AddDerivation
‣ AddDerivation( arg1, arg2, arg3 ) | ( operation ) |
8.3-7 AddDerivation
‣ AddDerivation( arg1, arg2, arg3 ) | ( operation ) |
8.3-8 AddDerivationPair
‣ AddDerivationPair( arg1, arg2, arg3, arg4, arg5, arg6 ) | ( operation ) |
8.3-9 AddDerivationPair
‣ AddDerivationPair( arg1, arg2, arg3, arg4, arg5 ) | ( operation ) |
8.3-10 AddDerivationPair
‣ AddDerivationPair( arg1, arg2, arg3, arg4, arg5, arg6 ) | ( operation ) |
8.3-11 AddDerivationPair
‣ AddDerivationPair( arg1, arg2, arg3, arg4, arg5 ) | ( operation ) |
8.3-12 AddDerivationToCAP
‣ AddDerivationToCAP( arg ) | ( function ) |
8.3-13 AddDerivationPairToCAP
‣ AddDerivationPairToCAP( arg ) | ( function ) |
8.3-14 AddWithGivenDerivationPairToCAP
‣ AddWithGivenDerivationPairToCAP( arg ) | ( function ) |
8.3-15 Operations
‣ Operations( G ) | ( attribute ) |
Gives the operations in the graph G, as a list of strings.
8.3-16 DerivationsUsingOperation
‣ DerivationsUsingOperation( G, op_name ) | ( operation ) |
Finds all the derivations in the graph G that use the operation named op_name, and returns them as a list.
8.3-17 DerivationsOfOperation
‣ DerivationsOfOperation( G, op_name ) | ( operation ) |
Finds all the derivations in the graph G targeting the operation named op_name (that is, the derivations that provide implementations of this operation), and returns them as a list.
8.4 Managing Derivations in a Category
8.4-1 IsOperationWeightList
‣ IsOperationWeightList( arg ) | ( filter ) |
Returns: true or false
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 DerivationResultWeight).
8.4-2 MakeOperationWeightList
‣ MakeOperationWeightList( C, G ) | ( operation ) |
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 C is the CAP category this operation weight list is associated to, and the argument G is a derivation graph containing operation names and derivations.
8.4-3 DerivationGraph
‣ DerivationGraph( owl ) | ( attribute ) |
Returns the derivation graph used by the operation weight list owl.
8.4-4 CategoryOfOperationWeightList
‣ CategoryOfOperationWeightList( owl ) | ( attribute ) |
Returns the CAP category associated to the operation weight list owl.
8.4-5 CurrentOperationWeight
‣ CurrentOperationWeight( owl, op_name ) | ( operation ) |
Returns the current weight of the operation named op_name.
8.4-6 OperationWeightUsingDerivation
‣ OperationWeightUsingDerivation( owl, d ) | ( operation ) |
Finds out what the weight of the operation implemented by the derivation d would be if we had used that derivation.
8.4-7 DerivationOfOperation
‣ DerivationOfOperation( owl, op_name ) | ( operation ) |
Returns the derivation which is currently used to implement the operation named op_name. If the operation is not implemented by a derivation (that is, either implemented directly or not implemented at all), then fail is returned.
8.4-8 InstallDerivationsUsingOperation
‣ InstallDerivationsUsingOperation( owl, op_name ) | ( operation ) |
Performs a search from the operation op_name, and installs all derivations that give improvements over the current state. This is used internally by AddPrimitiveOperation and Reevaluate. It should normally not be necessary to call this function directly.
8.4-9 Reevaluate
‣ Reevaluate( owl ) | ( operation ) |
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.
8.4-10 AddPrimitiveOperation
‣ AddPrimitiveOperation( owl, op_name, weight ) | ( operation ) |
Add the operation named op_name to the operation weight list owl with weight weight. 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).
8.4-11 PrintDerivationTree
‣ PrintDerivationTree( owl, op_name ) | ( operation ) |
Print a tree representation of the way the operation named op_name is implemented in the category of the operation weight list owl.
8.4-12 PrintTree
‣ PrintTree( arg1, arg2, arg3 ) | ( operation ) |
Prints a tree structure.
8.4-13 PrintTreeRec
‣ PrintTreeRec( arg1, arg2, arg3, arg4 ) | ( operation ) |
8.5 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.
8.5-1 IsStringMinHeap
‣ IsStringMinHeap( arg ) | ( filter ) |
Returns: true or false
A string min heap is a min heap where every node contains a string label and an integer key.
8.5-2 StringMinHeap
‣ StringMinHeap( arg ) | ( function ) |
Create an empty string min heap.
8.5-3 Add
‣ Add( H, string, key ) | ( operation ) |
Add a new node containing the label string and the key key to the heap H.
8.5-4 ExtractMin
‣ ExtractMin( H ) | ( operation ) |
Remove a node with minimal key value from the heap H, and return it. The return value is a list [ label, key ], where label is the extracted node's label (a string) and key is the node's key (an integer).
8.5-5 DecreaseKey
‣ DecreaseKey( H, string, key ) | ( operation ) |
Decrease the key value for the node with label string in the heap H. The new key value is given by key and must be smaller than the node's current value.
8.5-6 IsEmptyHeap
‣ IsEmptyHeap( H ) | ( operation ) |
Returns true if the heap H is empty, false otherwise.
8.5-7 HeapSize
‣ HeapSize( H ) | ( operation ) |
Returns the number of nodes in the heap H.
8.5-8 Contains
‣ Contains( H, string ) | ( operation ) |
Returns true if the heap H contains a node with label string, and false otherwise.
8.5-9 Swap
‣ Swap( H, i, j ) | ( operation ) |
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.
8.5-10 Heapify
‣ Heapify( H, i ) | ( operation ) |
Heapify the heap H, starting from index i. This is an internal function.