Generics ======== Generics are Nim's means to parametrize procs, iterators or types with `type parameters`:idx:. Depending on context, the brackets are used either to introduce type parameters or to instantiate a generic proc, iterator or type. The following example shows a generic binary tree can be modelled: .. code-block:: nim type BinaryTreeObj[T] = object # BinaryTreeObj is a generic type with # with generic param ``T`` le, ri: BinaryTree[T] # left and right subtrees; may be nil data: T # the data stored in a node BinaryTree[T] = ref BinaryTreeObj[T] # a shorthand for notational convenience proc newNode[T](data: T): BinaryTree[T] = # constructor for a node new(result) result.data = data proc add[T](root: var BinaryTree[T], n: BinaryTree[T]) = if root == nil: root = n else: var it = root while it != nil: var c = cmp(it.data, n.data) # compare the data items; uses # the generic ``cmp`` proc that works for # any type that has a ``==`` and ``<`` # operator if c < 0: if it.le == nil: it.le = n return it = it.le else: if it.ri == nil: it.ri = n return it = it.ri iterator inorder[T](root: BinaryTree[T]): T = # inorder traversal of a binary tree # recursive iterators are not yet implemented, so this does not work in # the current compiler! if root.le != nil: yield inorder(root.le) yield root.data if root.ri != nil: yield inorder(root.ri) var root: BinaryTree[string] # instantiate a BinaryTree with the type string add(root, newNode("hallo")) # instantiates generic procs ``newNode`` and add(root, newNode("world")) # ``add`` for str in inorder(root): writeLine(stdout, str) Is operator ----------- The ``is`` operator checks for type equivalence at compile time. It is therefore very useful for type specialization within generic code: .. code-block:: nim type Table[Key, Value] = object keys: seq[Key] values: seq[Value] when not (Key is string): # nil value for strings used for optimization deletedKeys: seq[bool] Type operator ------------- The ``type`` (in many other languages called `typeof`:idx:) operator can be used to get the type of an expression: .. code-block:: nim var x = 0 var y: type(x) # y has type int If ``type`` is used to determine the result type of a proc/iterator/converter call ``c(X)`` (where ``X`` stands for a possibly empty list of arguments), the interpretation where ``c`` is an iterator is preferred over the other interpretations: .. code-block:: nim import strutils # strutils contains both a ``split`` proc and iterator, but since an # an iterator is the preferred interpretation, `y` has the type ``string``: var y: type("a b c".split) Type Classes ------------ A type class is a special pseudo-type that can be used to match against types in the context of overload resolution or the ``is`` operator. Nim supports the following built-in type classes: ================== =================================================== type class matches ================== =================================================== ``object`` any object type ``tuple`` any tuple type ``enum`` any enumeration ``proc`` any proc type ``ref`` any ``ref`` type ``ptr`` any ``ptr`` type ``var`` any ``var`` type ``distinct`` any distinct type ``array`` any array type ``set`` any set type ``seq`` any seq type ``any`` any type ================== =================================================== Furthermore, every generic type automatically creates a type class of the same name that will match any instantiation of the generic type. Type classes can be combined using the standard boolean operators to form more complex type classes: .. code-block:: nim # create a type class that will match all tuple and object types type RecordType = tuple or object proc printFields(rec: RecordType) = for key, value in fieldPairs(rec): echo key, " = ", value Procedures utilizing type classes in such manner are considered to be `implicitly generic`:idx:. They will be instantiated once for each unique combination of param types used within the program. Nim also allows for type classes and regular types to be specified as `type constraints`:idx: of the generic type parameter: .. code-block:: nim proc onlyIntOrString[T: int|string](x, y: T) = discard onlyIntOrString(450, 616) # valid onlyIntOrString(5.0, 0.0) # type mismatch onlyIntOrString("xy", 50) # invalid as 'T' cannot be both at the same time By default, during overload resolution each named type class will bind to exactly one concrete type. Here is an example taken directly from the system module to illustrate this: .. code-block:: nim proc `==`*(x, y: tuple): bool = ## requires `x` and `y` to be of the same tuple type ## generic ``==`` operator for tuples that is lifted from the components ## of `x` and `y`. result = true for a, b in fields(x, y): if a != b: result = false Alternatively, the ``distinct`` type modifier can be applied to the type class to allow each param matching the type class to bind to a different type. Procs written with the implicitly generic style will often need to refer to the type parameters of the matched generic type. They can be easily accessed using the dot syntax: .. code-block:: nim type Matrix[T, Rows, Columns] = object ... proc `[]`(m: Matrix, row, col: int): Matrix.T = m.data[col * high(Matrix.Columns) + row] Alternatively, the `type` operator can be used over the proc params for similar effect when anonymous or distinct type classes are used. When a generic type is instantiated with a type class instead of a concrete type, this results in another more specific type class: .. code-block:: nim seq[ref object] # Any sequence storing references to any object type type T1 = auto proc foo(s: seq[T1], e: T1) # seq[T1] is the same as just `seq`, but T1 will be allowed to bind # to a single type, while the signature is being matched Matrix[Ordinal] # Any Matrix instantiation using integer values As seen in the previous example, in such instantiations, it's not necessary to supply all type parameters of the generic type, because any missing ones will be inferred to have the equivalent of the `any` type class and thus they will match anything without discrimination. Concepts -------- **Note**: Concepts are still in development. Concepts, also known as "user-defined type classes", are used to specify an arbitrary set of requirements that the matched type must satisfy. Concepts are written in the following form: .. code-block:: nim type Comparable = concept x, y (x < y) is bool Container[T] = concept c c.len is Ordinal items(c) is T for value in c: type(value) is T The concept is a match if: a) all of the expressions within the body can be compiled for the tested type b) all statically evaluatable boolean expressions in the body must be true The identifiers following the ``concept`` keyword represent instances of the currently matched type. These instances can act both as variables of the type, when used in contexts where a value is expected, and as the type itself when used in contexts where a type is expected. Please note that the ``is`` operator allows one to easily verify the precise type signatures of the required operations, but since type inference and default parameters are still applied in the provided block, it's also possible to encode usage protocols that do not reveal implementation details. Much like generics, concepts are instantiated exactly once for each tested type and any static code included within them is also executed once. **Hint**: Since concepts are still very rough at the edges there is a command line switch ``--reportConceptFailures:on`` to make debugging concept related type failures more easy. Symbol lookup in generics ------------------------- The symbol binding rules in generics are slightly subtle: There are "open" and "closed" symbols. A "closed" symbol cannot be re-bound in the instantiation context, an "open" symbol can. Per default overloaded symbols are open and every other symbol is closed. Open symbols are looked up in two different contexts: Both the context at definition and the context at instantiation are considered: .. code-block:: nim type Index = distinct int proc `==` (a, b: Index): bool {.borrow.} var a = (0, 0.Index) var b = (0, 0.Index) echo a == b # works! In the example the generic ``==`` for tuples (as defined in the system module) uses the ``==`` operators of the tuple's components. However, the ``==`` for the ``Index`` type is defined *after* the ``==`` for tuples; yet the example compiles as the instantiation takes the currently defined symbols into account too. A symbol can be forced to be open by a `mixin`:idx: declaration: .. code-block:: nim proc create*[T](): ref T = # there is no overloaded 'init' here, so we need to state that it's an # open symbol explicitly: mixin init new result init result Bind statement -------------- The ``bind`` statement is the counterpart to the ``mixin`` statement. It can be used to explicitly declare identifiers that should be bound early (i.e. the identifiers should be looked up in the scope of the template/generic definition): .. code-block:: nim # Module A var lastId = 0 template genId*: untyped = bind lastId inc(lastId) lastId .. code-block:: nim # Module B import A echo genId() But a ``bind`` is rarely useful because symbol binding from the definition scope is the default.