Polymorphic Functions

In the rulefiles you can define polymorphic functions and methods resembling, to some extent, the features of programming languages C++ or Java. The general syntax is described among other rulefile elements, here we discuss the definition and overload resolution in deeper details.

Let's recall that a polymorphic function is introduced with the following header:

category label : name < type parameters > [ typecheck ] ( signature ) : attributes

category can be method, function, etc., as described in the general syntax rules.

Name and signature are mandatory, while label, type parameters, and attributes are optional.

The signature describes the number and types of arguments expected by an overloaded instance, as well as default values for optional arguments. The syntax of the most primitive elements is borrowed from the standard perl function prototypes, enriched with further elements for property types and “big” object types, option lists and other keyword arguments, etc. The “standard” elements are encoded with one-symbol codes, they can be written in traditional style glued together, or in a more legible style with commas and white spaces in between. Advanced elements must be separated with commas.

Signatures of pure perl functions and wrapped C++ functions share many common elements, but also have few differences. Unless mentioned explicitly, the elements described below may be used in both cases. C++ functions are recognized by the c++ attribute.

$

Denotes a single argument of an arbitrary type. Even an undef value would be accepted.

*

Denotes a single argument of an arbitrary type with a restriction that is must have been declared as a property type with C++ binding. This is a special form for C++ function wrappers. The actual type of the argument passed to the function will be pasted into the auto-generated C++ wrapper code.

typename

Denotes a single argument of the given type. The type must be declared as property type or “big” object type in the rulefiles. For simple types, the signature will match any object of the named type or derived thereof; for parametrized types, any instance or derivation will be matched. If the feasible argument type should be just the type instance with all default type parameters, an empty parameter list <> must be appended.

If a parametrized type is used for a wrapped C++ function, the concrete type of the actually passed argument is pasted into the auto-generated wrapper code.

The primitive types Int, Float, and String can be used to restrict the feasible value set to built-in integral numbers, floating-point numbers, and text strings respectively. Note that no complex object type like Rational or Vector would fit these signature elements, even if it could be converted to a built-in number or a string.

typename < parameter, … >

Denotes a single argument of a type being an instantiation of a parametrized type, or derived thereof. If all parameters are concrete types, only arguments belonging to the resulting type instance will be accepted. If some parameters are replaced with _, i.e. wildcards, any matching type instances will be accepted. Specifying all parameters as wildcards is equivalent to omitting the entire parameter list, that is, this function will accept any instance of the parametrized family. Specifying an empty parameter list <> means assuming default values for all parameters, which eventually yields one concrete type instance.

type_upgrades_to< typename >

Denotes a single argument of the given type or of another type that can be upgraded to it, directly or transitively. For functions implemented in C++, the argument received by the function will be upgraded automatically by calling an appropriate constructor of the target type - just as a consequence of C++ type coercion rules. Functions implemented in perl, however, will see the original value as passed by the caller. They can use convert_to<TYPE>() to obtain an object of the desired type.

can_convert_to< typename >

Denotes a single argument of the given type or any other type accepted by its constructor. Depending on the target type, this can include plain strings, scalars and anonymous lists. The conversion, if needed, always takes place before entering the function, including ones implemented in pure perl.

@

Denotes arbitrarily many (trailing) arguments of any types. This element must be the last one among all arguments in the signature. This is only allowed with functions implemented in perl. For C++ functions, an appropriate container type (Array, Vector, etc.) must be used.

%option_list

Refers to an option list defined in the rulefiles before. Trailing argument pairs of the form keyword => value with keywords matching the keys of the option list are collected together in an anonymous hash map, which is passed to the function body by reference.

A signature may contain more than one option list reference. The arguments passed to the function are reorganized to match the keys of each option list; each anonymous hash map is then passed to the function body per separate reference. If the option lists share some keys, the keyword arguments matching several lists are copied in all corresponding hash maps.

If the argument list already contains a reference to a hash map at the position where keyword-value pairs are expected, this reference is passed unchanged and unchecked to the function body; this allows to gradually define families of polymorphic functions delegating work to each other without expensive re-checking and reordering of keyword arguments.

{ key => default value, … }

Like above, but specifying an anonymous option list used just in this single function. Default values different from undef will always be present in the anonymous hash map passed to the function body. This element may be combined with any number of references to named option lists.

%

Specifies that arbitrary keyword-value pairs may be passed to the function. The passed keywords are not checked at all, everything goes into a single anonymous hash map. This element must be the last one in a signature and can't be combined with other option lists, neither named nor anonymous.

Separators are placed between signature elements.

;

Separates the specifications of mandatory positional arguments (to the left) from optional positional arguments (to the right).

Modifiers are placed after signature elements.

= value

=( expression )

Specifies a default value for an optional positional argument. Complex expressions involving function calls or array/hash map access must be enclosed in parentheses. Optional positional arguments without default value stay undef when called with a too short list of arguments.

Expressions may involve values of preceding arguments by referring to the elements of the array @_. The references may be absolute, using non-negative indexes (remember to count the additional leading argument passed to methods), or relative to the current argument, using negative indexes.

+

Specifies that one or more objects of the given type (or derived thereof) are expected here. During overload resolution, all matching arguments are gathered into an anonymous array which is eventually passed by reference to the function body. The caller may also bundle these arguments in an anonymous array up front; the elements will still be checked for type correctness and the array reference will be passed unchanged to the body.

:int

Only applicable to a * parameter of a C++ function, tells that the expected argument may be either an object of some class or an integral number; floating-point numbers and strings have to be converted to integers before calling the C++ function.

:wary

Only applicable to a * or named type parameter of a C++ function, tells that the type name in the auto-generated C++ wrapper source code must be adorned with Wary< …> class. This usually results in additional consistency checks performed prior to the operation. Please be aware that not all classes in the Polymake Template Library support this Wary flavor; you should study the implementation of the C++ function before writing this attribute in the wrapper.

:anchor

Only allowed for C++ functions, designates an argument which will be referred to from the result of the function. For example, an object produced by Matrix minor method refers to the row and column index sets. An additional precaution is taken against vanishing of such an argument prior to the destruction of the resulting object.

&

Only applicable to a * or named type parameter of a C++ function, designates a mutable lvalue. That is, the data passed as an argument may be changed by the function. An attempt to pass a write-protected data, in particular, a `big' object property, will lead to an exception. Can't be used with optional parameters for obvious reasons.

&&

Only applicable to a * or named type parameter of a C++ function, designates a “universal reference”. A write-protected data will be passed per const reference, a mutable value stored in a variable (or as part of a larger data structure) will be passed per non-const lvalue reference, and a temporary value will be passed per rvalue reference.

&&const

Only applicable to a * or named type parameter of a C++ function, designates a “universal reference” with write-protection. A value stored in a variable (or as part of a larger data structure) will be passed per const reference, while a temporary value will be passed per rvalue reference.

Some of modifiers described above can also be provided for the implicit `this' parameter of a C++ method, namely wary, anchor, and all kinds of reference specifications. They are written at the very beginning of the signature, starting with a colon:

user_method contract_edge(:wary&, $$) : c++;

Static C++ methods which may be called via an object variable on the perl side should be designated by :static keyword at the beginning of the signature:

user_method monomial(:static, Int, Int) : c++;

The type parameter list introduces names for type placeholders which may be used in the signature as well as in the body of the function. If a type parameter occurs in the signature as a type of an argument or as a part of a complex type expression, in each call it will be deduced from the types of the actual arguments passed to the function. If the parameter occurs more than once in the signature and the deduction would lead to conflicting types, this function instance is discarded from candidates. If a type parameter does not occur in the signature or can't be deduced because of omitted optional argument, and it does not have a default value, it must be specified explicitly in the call using the familiar syntax for function templates, otherwise this function instance is discarded.

For example, the function creating a unit matrix of a given size is defined like this:

user_function unit_matrix<Scalar=Rational>($) ...

Then, if called as unit_matrix($dim), the default type Rational will be assumed, and the result will be a Matrix<Rational>, while a call unit_matrix<Integer>($dim) will deliver a Matrix<Integer>.

Actually, explicit values can also be given for deducible type parameters, but when the explicit values contradict the deduction outcome, this function instance is discarded from candidates.

In a C++ function, the values of type parameters (regardless whether explicit or deduced) are included in the auto-generated source call as explicit template arguments immediately following the function name.

In the body of a perl function, the type parameter names may be used as normal types in all expressions expecting package or type names, in particular in constructor calls like new TYPE(...), new Matrix<TYPE>(...), static method calls TYPE->METHOD(...), and type checks if (instanceof TYPE(…)) { … } .

Due to limitations of the perl parser, methods currently can't be called with explicit type parameters. Type deduction works fine, however.

Type deduction is flexible, in that it tries to find a type fitting all occurrences of the type parameter name in the signature.

By default, the type deduction will yield the least derived type among all candidates. For example, for a function f<T>(T, T) called with arguments Vector<Rational> and SparseVector<Rational> the type parameter T will be deduced as Vector<Rational>, because it's the super class of SparseVector<Rational>. A call with Vector<Rational>, Vector<Float> will fail as unresolved because no Vector type in question is derived from another one.

You can choose the deduction by upgrade relation if you put the type parameter names in the signature in a special meta-function type_upgrade<T>. Then the deduction will yield the type all candidates can be upgraded to. For example, for a function fu<T>(Vector<type_upgrade<T>>, Vector<type_upgrade<T>>) called with Vector<Rational> and SparseVector<Integer>, the type parameter T will be deduced as Rational, because Integer can be upgraded to Rational. Note that type parameters specified explicitly in the caller can't be changed by deduction, but if the passed arguments satisfy the upgrade relation, they will still be accepted. In the same example, in a call fu<QuadraticExtension>(…) T will be deduced as QuadraticExtension, still accepting Vector<Rational> and SparseVector<Integer> as arguments.

Both kinds of type deduction can be combined with repetition modifier +. In this case the deduction is repeatedly applied to all arguments in sequence, eventually yielding a type which would fit them all. For example, a function intersection<T>(Cone<type_upgrade<T>>+) will accept any sequence of objects Polytope<Rational>, Cone<Rational>, Polytope<QuadraticExtension>, etc., eventually deducing T as QuadraticExtension if at least one object in sequence has got this coordinate type.

A type checking clause may be specified for functions with type parameters. It can contain an expression performing arbitrary checks on the deduced or explicitly given type parameters, e.g. by calling a type checking function. Default values for type parameters, if applicable, are assigned prior to evaluation of the type checking expression. The expression should return a boolean value signaling success or failure; it must not raise exceptions. In the successful case, the function body is executed; otherwise, the function is discarded from candidates and the overload resolution continues.

Besides performing pure checks, the type checking clause may upgrade the deduced parameter values by calling a meta-function type_upgrade<T, other type>. This meta-function upgrades T to other type if it is allowed by upgrade relations and T has not been explicitly specified by the caller. Even if the upgrade is not possible, this function succeeds and simply returns the unchanged type of T.

Trailing attributes are used to modify the semantics of the leading argument of methods, describe the return value of the function, or contribute to the auto-generated wrapper code. All trailing attributes described below are only applicable to C++ functions.

c++( options for source code )

Tells that a function or method is implemented in C++ and a wrapper function must be generated by the first use of it. If the signature contains wildcards like * or parameterized types (or the method belongs to a parameterized type), a separate wrapper instance will be automatically generated for every new combination of argument types.

Options can be used to modify the look of the generated wrapper code:

include => [ "header file", ... ]

Add #include preprocessor directives with the given files to the source code. Further header files might be included depending on the argument types.

name => "function name"

Specify the C++ name of the function, if it differs from the name declared for the perl side.

If no options are needed, the empty parentheses can be omitted.

returns(lvalue)

Tells that the function returns an object which can be modified by assigning a value to it. Primarily used with methods giving access to elements of some data container like a matrix or vector.

returns( type )

Tells that the function returns an object of the given type. Usually the return value is automatically recognized by the auto-generated wrapper and hooked under an appropriately “blessed” perl reference. This attribute should only be used in special cases where the automatic recognition does not work or must be overridden. In particular, this attribute must be used with abstract property types.

returns(@)

Tells that the function returns several values in a list context. As usual in perl, when called in scalar context, the last value from the list will be taken for further processing.

When a polymorphic function is called, the first action taken always determines the instance best matching the given list of arguments. This is also often called overload resolution.

The first rough filtering is based on the number of arguments passed to the function. Then the set of candidates is gradually narrowed by analyzing the types of the arguments from left to right. For polymorphic methods, the first argument has already been used for locating the method as such, hence it does not participate in the further resolution.

The signature matching is done in greedy manner. In each round only those candidate instances “survive” whose signature elements most closely match the corresponding argument. This means, an exact match of the type is preferred over match against a super class, which in its turn is valued higher than a match against a universal element like '$' or '*'. Only if the candidate set becomes empty in some round, the resolver makes a step back and considers the next closest candidates.

The trailing keyword-value pairs are not taken into account apart from their mere presence; the search for keys in the option lists takes place after the unique matching instance is found.

It is an error if the set of candidates after having processed the entire argument list does not consist of exactly one instance. The fact that some argument list may equally good match more than one feasible candidate is recognized already during initial load of rulefiles. Not having matched any instance at all gives rise to an exception.

Please keep in mind that two signatures differing in optional and keyword arguments alone would lead to ambiguous overloading each time when only mandatory arguments are passed, and therefore will be rejected by rulefile parser. For example, the following pairs of signatures are illegal:

• ($$) and ($$;$=0)
• ($$;Class_A) and ($$;Class_B)
• ($$) and ($$;%my_options)

As already mentioned, type deduction and checking clauses actively participate in overload resolution. Failure to deduce a type of a parameter or to pass an upgrade check leads to candidate rejection and backtracking to other candidates.

You may define several instances of a polymorphic function having identical number and types of arguments and only differing in parameter deduction and/or final type check clause. Since it's in general impossible to figure out analytically which instances comprise narrowing specializations of others, the overload resolution assumes that more specific cases are defined in the rulefiles after the generic ones, and therefore tries similar candidates in the reverse order of their appearance in the rulefiles. In obvious cases, e.g. two candidates with and without a type checking clause, the candidates are tries in “right” order regardless of their placement in the rules. Nevertheless, to be on the safe side, you should always place more generic function instances, swallowing any combinations of type parameters, before the specialized instances.

Usually a function is either implemented in pure (polymake dialect of) perl or in pure C++. In the first case the instance body with the code is directly following the header, like in a standard perl subroutine, in the second case the list of attributes is concluded by a semicolon.

Sometimes you might find more convenient to combine some preliminary checks or preparations on argument values with a proper call into C++ function, or even skip the latter call under certain circumstances. Although such scenarios can surely be modeled by defining two functions, outer one written in perl, and the inner one as a wrapped C++ function, this also can be written more succinctly (and more efficiently) as a hybrid function. Such a function has both the c++ attribute and a body with perl code. The perl body is executed first; if it returns any value with an explicit return statement or raises an exception, the C++ function is not called at all; if the perl body runs to the end without executing any returns, the control is passed to the wrapped C++ function.

Usually a hybrid function looks like this:

function NAME( signature ) : c++ (attributes) {
  if (some_checks(...)) {
     return some_value;
  }
  # reached the end: call the C++ function
}

Labels allow to provide several alternative implementations for the same function or for a family of functions with compatible signatures. The choice of the function to be called is governed by active preference lists (cf. user commands prefer, prefer_now, show_preferences). First, all candidates with the label of the highest rank are considered according to usual overload resolution rules. If none has matched the argument list, the candidates with the label of the next lower rank are considered, and so on.

Labels are mandatory for global methods. The overload resolution for global methods runs slightly differently from other functions. The application first calls $method=Overload::Global::NAME(args...) to obtain the code reference pointing to the currently preferred method matching the given list of arguments. Then it creates an object of the corresponding class using something like $object=method_owner($method)->new(...); or retrieves a suitable object in whatever appropriate way, and finally calls the method, passing the obtained object as a leading argument: $method->($object, args...);

Alternatively, the application can request the full list of candidate methods from Overload::resolve_global(NAME, [ args... ]) , the argument list must be passed by reference. The result will be a reference to a list of method references, ordered according to the current label ranking.