Generics¶
Chapel supports generic functions and types that are parameterizable over both types and parameters. The generic functions and types look similar to non-generic functions and types already discussed.
Generic Functions¶
A function is generic if any of the following conditions hold:
Some formal argument is specified with an intent of
type
orparam
.Some formal argument has no specified type and no default value.
Some formal argument is specified with a queried type.
The type of some formal argument is a generic type, e.g.,
List
. Queries may be inlined in generic types, e.g.,List(?eltType)
.The type of some formal argument is an array type where either the element type is queried or omitted or the domain is queried or omitted.
These conditions are discussed in the next sections.
Formal Type Arguments¶
If a formal argument is specified with intent type
, then a type must
be passed to the function at the call site. A copy of the function is
instantiated for each unique type that is passed to this function at a
call site. The formal argument has the semantics of a type alias.
Example (build2tuple.chpl).
The following code defines a function that takes two types at the call site and returns a 2-tuple where the types of the components of the tuple are defined by the two type arguments and the values are specified by the types default values.
proc build2Tuple(type t, type tt) { var x1: t; var x2: tt; return (x1, x2); }This function is instantiated with “normal” function call syntax where the arguments are types:
var t2 = build2Tuple(int, string); t2 = (1, "hello");
A formal type argument can include a formal type (a colon followed by a type). This pattern is sometimes useful to create generic functions accepting type arguments that only apply to a specific group of types.
Example (typeColonArgument.chpl).
Suppose that we’d like to define a function that accepts a type argument and returns 1 represented in that type.
proc getOne(type t:numeric) { return 1:t; }Now calls to this function will resolve to the appropriate version based upon the argument type supplied.
var anInt8 = getOne(int(8)); var aReal = getOne(real);
Formal Parameter Arguments¶
If a formal argument is specified with intent param
, then a
parameter must be passed to the function at the call site. A copy of the
function is instantiated for each unique parameter that is passed to
this function at a call site. The formal argument is a parameter.
Example (fillTuple.chpl).
The following code defines a function that takes an integer parameter
p
at the call site as well as a regular actual argument of integer typex
. The function returns a homogeneous tuple of sizep
where each component in the tuple has the value ofx
.proc fillTuple(param p: int, x: int) { var result: p*int; for i in result.indices do result(i) = x; return result; }The function call
fillTuple(3, 3)
returns a 3-tuple where each component contains the value3
.
Formal Arguments without Types¶
If the type of a formal argument is omitted, the type of the formal argument is taken to be the type of the actual argument passed to the function at the call site. A copy of the function is instantiated for each unique actual type.
Example (fillTuple2.chpl).
The example from the previous section can be extended to be generic on a parameter as well as the actual argument that is passed to it by omitting the type of the formal argument
x
. Additionally the parameter argument can allow any type be passed. The following code defines a function that returns a homogeneous tuple of sizep
where each component in the tuple is initialized tox
:proc fillTuple(param p, x) { var result: p*x.type; for i in result.indices do result(i) = x; return result; }In this function, the type of the tuple is taken to be the type of the actual argument. The call
fillTuple(3, 3.14)
returns a 3-tuple of real values(3.14, 3.14, 3.14)
. The return type is(real, real, real)
.
Formal Arguments with Queried Types¶
If the type of a formal argument is specified as a queried type, the type of the formal argument is taken to be the type of the actual argument passed to the function at the call site. A copy of the function is instantiated for each unique actual type. The queried type has the semantics of a type alias.
Example (fillTuple3.chpl).
The example from the previous section can be rewritten to use a queried type for clarity:
proc fillTuple(param p: int, x: ?t) { var result: p*t; for i in result.indices do result(i) = x; return result; }
Example (query.chpl).
Type queries can also be used to constrain the types of other function arguments and/or the return type. In this example, the type query on the first argument establishes type constraints on the other arguments and also determines the return type.
The code
writeln(sumOfThree(1,2,3)); writeln(sumOfThree(4.0,5.0,3.0)); proc sumOfThree(x: ?t, y:t, z:t):t { var sum: t; sum = x + y + z; return sum; }produces the output
6 12.0
Formal Arguments of Generic Type¶
If the type of a formal argument is a generic type, there must exist an instantiation of that type that the actual argument can be implicitly coerced to (Implicit Conversions). A copy of the function is instantiated for each unique instantiation of the formal’s type.
Example.
The following code defines a function
writeTop
that takes an actual argument that is a generic stack (see Example: A Generic Stack) and outputs the top element of the stack. The function is generic on the type of its argument.proc writeTop(s: Stack) { write(s.top.item); }
Types and parameters may be queried from the types of formal arguments
as well. In the example above, the formal argument’s type could also be
specified as Stack(?t)
in which case the symbol t
is equivalent
to s.itemType
.
Note that generic types which have default values for all of their generic fields, e.g. range, are not generic when simply specified and require a query to mark the argument as generic. For simplicity, the identifier may be omitted.
Example.
The following code defines a class with a type field that has a default value. Function
f
is defined to take an argument of this class type where the type field is instantiated to the default. Functiong
, on the other hand, is generic on its argument because of the use of the question mark.class C { type t = int; } proc f(c: C) { // c.type is always int } proc g(c: C(?)) { // c.type may not be int }
Formal Arguments of Partially Generic Type¶
The generic type for a formal argument may be specified with some queries or generic types and some concrete types or values. Using concrete types or values in this manner makes the argument partially concrete for the purpose of function resolution.
Example (nested-type-queries.chpl).
Given the code:
class C { type elementType; type indexType; type containerType; } class Container { type containedType; } proc f(c: C(real,?t,?u)) { // ... }The function
f
can only apply when thec.elementType==real
.It’s also possible to use a generic type as an argument to
C
. The following function,g
, can only apply whenc.containerType
is an instance ofContainer
:proc g(c: C(?t,?u,Container)) { // ... }
Similarly, a tuple type with query arguments forms a partially concrete argument.
Example.
The function definition
proc f(tuple: (?t,real)) { // body }specifies that
tuple.size == 2 && tuple(2).type == real
.
Homogeneous tuple arguments of generic type are also supported:
Example (partially-concrete-star-tuple.chpl).
record Number { var n; } proc f(tuple: 2*Number) { }specifies that
f
accepts a tuple with 2 elements, where each element has the same type, and that type is instantiation ofNumber
.
Note that specifying a tuple consisting entirely of queried types does create a partially concrete argument because the size of the tuple is constrained.
Example (partially-concrete-tuple-ambiguity.chpl).
The following program results in an ambiguity error:
proc f(tuple: (?,real)) { } proc f(tuple: (?,?)) { } f( (1.0, 2.0) );since the
tuple
arguments in both versions off
are partially concrete.
Formal Arguments of Generic Array Types¶
If the type of a formal argument is an array where either the domain or the element type is queried or omitted, the type of the formal argument is taken to be the type of the actual argument passed to the function at the call site. If the domain is omitted, the domain of the formal argument is taken to be the domain of the actual argument.
A queried domain may not be modified via the name to which it is bound (see Association of Arrays to Domains for rationale).
Function Visibility in Generic Functions¶
When resolving a function call, as defined in Function Resolution, there is an additional source of visible functions when the call is nested within a generic function. The additional source is the functions visible from the call site that the enclosing generic function is invoked from. This call site is referred to as the point of instantiation. If there are multiple enclosing generic functions or the call is nested within a concrete function that is, in turn, nested in generic function(s), the point of instantiation is the call site of the innermost generic function.
If no candidate functions are found during the initial steps of identifying visible and candidate functions, function resolution continues the search for visible and candidate functions at the point of instantiation. If still no candidates are found, the search continues to the point of instantiation of the innermost generic function that contains the previous point of instantiation. Once candidate(s) are found, the search succeeds and function resolution proceeds to selecting the most specific functions. Otherwise the search will reach a point of instantiation that is not within a generic function. For example, it can be at the module level or enclosed in only concrete function(s). If no candidates have been found, the compiler issues a “call cannot be resolved” error.
Example (point-of-instantiation.chpl).
Consider the following code:
module LibraryA { proc callWorkers(arg) { worker1(); worker2(); } } module LibraryB { use LibraryA; proc worker1() { writeln("in LibraryB"); } proc libFun(arg) { callWorkers(arg); } } module Application { use LibraryB; proc worker1() { writeln("in Application"); } proc worker2() { writeln("in Application"); } proc main() { libFun(1); } }When resolving the call to
worker1
incallWorkers()
there are no visible functions at the scope of the call. SincecallWorkers()
is a generic function, resolution looks at its point of instantiation, which is its call withinlibFun()
. There, a single candidate function forworker1
is found, so function resolution determines that this is the target function.Since the search is complete, no further points of instantiation are visited. Therefore
LibraryB
is assured that whenevercallWorkers()
looks to its callers forworker1
, the implementation inLibraryB
will be used. Other overloads, suchworker1()
in moduleApplication
, will not be considered.When resolving the call to
worker2
incallWorkers()
, resolution again looks at its point of instantiation, namely its call withinlibFun()
. No visible functions can be found there. SincelibFun
is also a generic function, the search continues in turn to its point of instantiation, which is its call in moduleApplication
. Since a definition ofworker2
is visible there, it will be considered the candidate for the call toworker2
incallWorkers()
.
If the generic function is only called indirectly through dynamic
dispatch, the point of instantiation is defined as the point at which
the derived type (the type of the implicit this
argument) is defined
or instantiated (if the derived type is generic).
Rationale.
Visible function lookup in Chapel’s generic functions is handled differently than in C++’s template functions in that there is no split between dependent and independent types.
Also, dynamic dispatch and instantiation is handled differently. Chapel supports dynamic dispatch over methods that are generic in some of its formal arguments.
Note that the Chapel lookup mechanism is still under development and discussion. Comments or questions are appreciated.
Generic Types¶
Generic types comprise built-in generic types, generic classes, and generic records.
Built-in Generic Types¶
The types integral
, numeric
and enum
are generic types that
can only be instantiated with, respectively, the signed and unsigned
integral types, all of the numeric types, and all enumerated types. The
type enumerated
is currently available as a synonym for enum
.
The type record
can be instantiated with any record type.
The memory management strategies owned
, shared
, borrowed
,
and unmanaged
(see Class Types) are also generic
types that can be instantiated with any class using that memory
management strategy. These types indicate generic nilability.
The types class
and class?
, on their own or in combination with
memory management strategies, are also generic types. They can be
instantiated as follows:
class
can instantiate with any non-nilable class using any memory management strategyclass?
can instantiate with any class using any memory management strategy but will use the nilable variant of that class in an instantiation. When used as an argument type, a value of non-nilable class type will be implicitly converted to the nilable type on the call. As a result, a formal of typeclass?
can accept an actual of any class type.owned
can instantiate with anyowned
class - taking the nilability from whatever it instantiated from.owned class
can instantiate with any non-nilableowned
class.owned class?
can instantiate from any nilableowned
class. As withclass?
, it can also instantiate from a non-nilableowned
class, in which case a implicit conversion would occur in a call.shared
,shared class
,shared class?
behave similarly to the above but withshared
management strategy.borrowed
,borrowed class
,borrowed class?
behave similarly to the above but withborrowed
management strategy.unmanaged
,unmanaged class
,unmanaged class?
behave similarly to the above but withunmanaged
management strategy.
Generic Classes and Records¶
The remainder of this section Generic Types specifies generic class and record types that are not built-in types (Built-in Generic Types).
A class or record is generic if it contains one or more generic fields. A generic field is one of:
a specified or unspecified type alias,
a parameter field, or
a
var
orconst
field that has no type and no initialization expression.
For each generic field, the class or record is parameterized over:
the type bound to the type alias,
the value of the parameter field, or
the type of the
var
orconst
field, respectively.
Correspondingly, the class or record is instantiated with a set of types and parameter values, one type or value per generic field.
Type Aliases in Generic Types¶
If a class or record defines a type alias, the class or record is generic over the type that is bound to that alias. Such a type alias is accessed as if it were a field from either a class or record instance or from the instantiated class or record type itself. Similar to a parameter field, it cannot be assigned except in its declaration.
The type alias becomes an argument with intent type
to the
compiler-generated initializer
(The Compiler-Generated Generic Initializer) for its class
or record. This makes the compiler-generated initializer generic. The
type alias also becomes an argument with intent type
to the type
constructor (The Type Constructor). If the type alias
declaration binds it to a type, that type becomes the default for these
arguments, otherwise they have no defaults.
The class or record is instantiated by binding the type alias to the actual type passed to the corresponding argument of a user-defined (User-Defined Initializers) or compiler-generated initializer or type constructor. If that argument has a default, the actual type can be omitted, in which case the default will be used instead.
Example (NodeClass.chpl).
The following code defines a class called
Node
that implements a linked list data structure. It is generic over the type of the element contained in the linked list.class Node { type eltType; var data: eltType; var next: unmanaged Node(eltType)?; }The call
new Node(real, 3.14)
creates a node in the linked list that contains the value3.14
. Thenext
field is set to nil. The type specifierNode
is a generic type and cannot be used to define a variable. The type specifierNode(real)
denotes the type of theNode
class instantiated overreal
. Note that the type of thenext
field is specified asNode(eltType)
; the type ofnext
is the same type as the type of the object that it is a field of.
Parameters in Generic Types¶
If a class or record defines a parameter field, the class or record is generic over the value that is bound to that field. The field can be accessed from a class or record instance or from the instantiated class or record type itself.
The parameter becomes an argument with intent param
to the
compiler-generated initializer
(The Compiler-Generated Generic Initializer) for that class
or record. This makes the compiler-generated initializer generic. The
parameter also becomes an argument with intent param
to the type
constructor (The Type Constructor). If the parameter
declaration has an initialization expression, that expression becomes
the default for these arguments, otherwise they have no defaults.
The class or record is instantiated by binding the parameter to the actual value passed to the corresponding argument of a user-defined (User-Defined Initializers) or compiler-generated initializer or type constructor. If that argument has a default, the actual value can be omitted, in which case the default will be used instead.
Example (IntegerTuple.chpl).
The following code defines a class called
IntegerTuple
that is generic over an integer parameter which defines the number of components in the class.class IntegerTuple { param size: int; var data: size*int; }The call
new IntegerTuple(3)
creates an instance of theIntegerTuple
class that is instantiated over parameter3
. The fielddata
becomes a 3-tuple of integers. The type of this class instance isIntegerTuple(3)
. The type specified byIntegerTuple
is a generic type.
Fields without Types¶
If a var
or const
field in a class or record has no specified
type or initialization expression, the class or record is generic over
the type of that field. The field becomes an argument with default
intent to the compiler-generated initializer
(The Compiler-Generated Generic Initializer). That argument
has no specified type and no default value. This makes the
compiler-generated initializer generic. The field also becomes an
argument with type
intent and no default to the type constructor
(The Type Constructor). Correspondingly, an actual value
must always be passed to the default initializer argument and an actual
type to the type constructor argument.
The class or record is instantiated by binding the type of the field to the type of the value passed to the corresponding argument of a user-defined (User-Defined Initializers) or compiler-generated initializer (The Compiler-Generated Generic Initializer). When the type constructor is invoked, the class or record is instantiated by binding the type of the field to the actual type passed to the corresponding argument.
Example (fieldWithoutType.chpl).
The following code defines another class called
Node
that implements a linked list data structure. It is generic over the type of the element contained in the linked list. This code does not specify the element type directly in the class as a type alias but rather omits the type from thedata
field.class Node { var data; var next: unmanaged Node(data.type)? = nil; }A node with integer element type can be defined in the call to the initializer. The call
new Node(1)
defines a node with the value1
. The codevar list = new unmanaged Node(1); list.next = new unmanaged Node(2);defines a two-element list with nodes containing the values
1
and2
. The type of each object could be specified asNode(int)
.
The Type Constructor¶
A type constructor is automatically created for each class or record. A
type constructor is a type function (The Type Return Intent)
that has the same name as the class or record. It takes one argument per
the class’s or record’s generic field, including fields inherited from
the superclasses, if any. The formal argument has intent type
for a
type alias field and is a parameter for a parameter field. It accepts
the type to be bound to the type alias and the value to be bound to the
parameter, respectively. For a generic var
or const
field, the
corresponding formal argument also has intent type
. It accepts the
type of the field, as opposed to a value as is the case for a parameter
field. The formal arguments occur in the same order as the fields are
declared and have the same names as the corresponding fields. Unlike the
compiler-generated initializer, the type constructor has only those
arguments that correspond to generic fields.
A call to a type constructor accepts actual types and parameter values and returns the type of the class or record that is instantiated appropriately for each field (Type Aliases in Generic Types, Parameters in Generic Types, Fields without Types). Such an instantiated type must be used as the type of a variable, array element, non-generic formal argument, and in other cases where uninstantiated generic class or record types are not allowed.
When a generic field declaration has an initialization expression or a
type alias is specified, that initializer becomes the default value for
the corresponding type constructor argument. Uninitialized fields,
including all generic var
and const
fields, and unspecified type
aliases result in arguments with no defaults; actual types or values for
these arguments must always be provided when invoking the type
constructor.
Generic Methods¶
All methods bound to generic classes or records, including initializers,
are generic over the implicit this
argument. This is in addition to
being generic over any other argument that is generic.
The Compiler-Generated Generic Initializer¶
If no user-defined initializers are supplied for a given generic class, the compiler generates one in a manner similar to that for concrete classes (The Compiler-Generated Initializer). However, the compiler-generated initializer for a generic class or record (The Compiler-Generated Initializer) is generic over each argument that corresponds to a generic field, as specified above.
The argument has intent type
for a type alias field and has intent
param
for a parameter field. It accepts the type to be bound to the
type alias and the value to be bound to the parameter, respectively.
This is the same as for the type constructor. For a generic var
or
const
field, the corresponding formal argument has the default
intent and accepts the value for the field to be initialized with. The
type of the field is inferred automatically to be the type of the
initialization value.
The default values for the generic arguments of the compiler-generated
initializer are the same as for the type constructor
(The Type Constructor). For example, the arguments
corresponding to the generic var
and const
fields, if any, never
have defaults, so the corresponding actual values must always be
provided.
User-Defined Initializers¶
If a generic field of a class or record does not have a default value or type alias, each user-defined initializer for that class must explicitly initialize that field. In the event that the initializer is called using an already instantiated type as the receiver, the class or record instance created by the initializer must have that same instantiated type.
Example (initializersForGenericFields.chpl).
In the following code:
class MyGenericClass { type t1; param p1; const c1; var v1; var x1: t1; // this field is not generic type t5 = real; param p5 = "a string"; const c5 = 5.5; var v5 = 555; var x5: t5; // this field is not generic proc init(c1, v1, type t1, param p1) { this.t1 = t1; this.p1 = p1; this.c1 = c1; this.v1 = v1; // compiler inserts initialization for remaining fields } proc init(type t5, param p5, c5, v5, x5, type t1, param p1, c1, v1, x1) { this.t1 = t1; this.p1 = p1; this.c1 = c1; this.v1 = v1; this.x1 = x1; this.t5 = t5; this.p5 = p5; this.c5 = c5; this.v5 = v5; this.x5 = x5; } } // class MyGenericClass var g1 = new MyGenericClass(11, 111, int, 1); var g2 = new MyGenericClass(int, "this is g2", 3.3, 333, 3333, real, 2, 222, 222.2, 22);The initializers are required to initialize fields
t1
,p1
,c1
, andv1
. Otherwise, field initializations may be omitted according to previously-described initializer semantics.
User-Defined Compiler Diagnostics¶
The special compiler diagnostic function calls compilerError
and
compilerWarning
generate compiler diagnostic of the indicated
severity if the function containing these calls may be called when the
program is executed and the function call is not eliminated by parameter
folding.
The compiler diagnostic is defined by the actual arguments which must be
string parameters. The diagnostic points to the spot in the Chapel
program from which the function containing the call is called.
Compilation halts if a compilerError
is encountered whereas it will
continue after encountering a compilerWarning
.
Example (compilerDiagnostics.chpl).
The following code shows an example of using user-defined compiler diagnostics to generate warnings and errors:
proc foo(x, y) { if (x.type != y.type) then compilerError("foo() called with non-matching types: ", x.type:string, " != ", y.type:string); writeln("In 2-argument foo..."); } proc foo(x) { compilerWarning("1-argument version of foo called with type: ", x.type:string); writeln("In generic foo!"); }The first routine generates a compiler error whenever the compiler encounters a call to it where the two arguments have different types. It prints out an error message indicating the types of the arguments. The second routine generates a compiler warning whenever the compiler encounters a call to it.
Thus, if the program foo.chpl contained the following calls:
1foo(3.4); 2foo("hi"); 3foo(1, 2); 4foo(1.2, 3.4); 5foo("hi", "bye"); 6foo(1, 2.3); 7foo("hi", 2.3);compiling the program would generate output like:
foo.chpl:1: warning: 1-argument version of foo called with type: real(64) foo.chpl:2: warning: 1-argument version of foo called with type: string foo.chpl:6: error: foo() called with non-matching types: int(64) != real(64)
Creating General and Specialized Versions of a Function¶
The Chapel language facility supports three mechanisms for using generic functions along with concrete functions. These mechanisms allow users to create a general generic implementation and also a special implementation for specific concrete types.
The first mechanism applies to functions. According to the function resolution rules described in Function Resolution, functions accepting concrete arguments are selected in preference to those with a totally generic argument. So, creating a second version of a generic function that declares a concrete type will cause the concrete function to be used where possible:
Example (specializeGenericFunction.chpl).
proc foo(x) { writeln("in generic foo(x)"); } proc foo(x:int) { writeln("in specific foo(x:int)"); } var myReal:real; foo(myReal); // outputs "in generic foo(x)" var myInt:int; foo(myInt); // outputs "in specific foo(x:int)"
This program will run the generic foo function if the argument is a real, but it runs the specific version for int if the argument is an int.
The second mechanism applies when working with methods on generic types. When declaring a secondary method, the receiver type can be a parenthesized expression. In that case, the compiler will evaluate the parenthesized expression at compile time in order to find the concrete receiver type. Then, the resolution rules described above will cause the concrete method to be selected when applicable. For example:
Example (specializeGenericMethod.chpl).
record MyNode { var field; // since no type is specified here, MyNode is a generic type } proc MyNode.foo() { writeln("in generic MyNode.foo()"); } proc (MyNode(int)).foo() { writeln("in specific MyNode(int).foo()"); } var myRealNode = new MyNode(1.0); myRealNode.foo(); // outputs "in generic MyNode.foo()" var myIntNode = new MyNode(1); myIntNode.foo(); // outputs "in specific MyNode(int).foo()"
The third mechanism is to use a where clause. Where clauses limit a generic method to particular cases. Unlike the previous two cases, a where clause can be used to declare special implementation of a function that works with some set of types - in other words, the special implementation can still be a generic function. See also Where Clauses.
Example: A Generic Stack¶
Example (genericStack.chpl).
class MyNode { type itemType; // type of item var item: itemType; // item in node var next: unmanaged MyNode(itemType)?; // reference to next node (same type) } record Stack { type itemType; // type of items var top: unmanaged MyNode(itemType)?; // top node on stack linked list proc push(item: itemType) { top = new unmanaged MyNode(itemType, item, top); } proc pop() { if isEmpty then halt("attempt to pop an item off an empty stack"); var oldTop = top; var oldItem = top!.item; top = top!.next; delete oldTop; return oldItem; } proc isEmpty return top == nil; }