diff options
Diffstat (limited to 'doc/manual/generics.txt')
| -rw-r--r-- | doc/manual/generics.txt | 711 |
1 files changed, 0 insertions, 711 deletions
diff --git a/doc/manual/generics.txt b/doc/manual/generics.txt deleted file mode 100644 index 1ba62bb5c..000000000 --- a/doc/manual/generics.txt +++ /dev/null @@ -1,711 +0,0 @@ -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 - BinaryTree*[T] = ref object # BinaryTree is a generic type with - # generic param ``T`` - le, ri: BinaryTree[T] # left and right subtrees; may be nil - data: T # the data stored in a node - - 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]) = - # insert a node into the tree - if root == nil: - root = n - else: - var it = root - while it != nil: - # compare the data items; uses the generic ``cmp`` proc - # that works for any type that has a ``==`` and ``<`` operator - var c = cmp(it.data, n.data) - 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 - - proc add*[T](root: var BinaryTree[T], data: T) = - # convenience proc: - add(root, newNode(data)) - - iterator preorder*[T](root: BinaryTree[T]): T = - # Preorder traversal of a binary tree. - # Since recursive iterators are not yet implemented, - # this uses an explicit stack (which is more efficient anyway): - var stack: seq[BinaryTree[T]] = @[root] - while stack.len > 0: - var n = stack.pop() - while n != nil: - yield n.data - add(stack, n.ri) # push right subtree onto the stack - n = n.le # and follow the left pointer - - var - root: BinaryTree[string] # instantiate a BinaryTree with ``string`` - add(root, newNode("hello")) # instantiates ``newNode`` and ``add`` - add(root, "world") # instantiates the second ``add`` proc - for str in preorder(root): - stdout.writeLine(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 -``auto`` any type -``any`` distinct auto (see below) -================== =================================================== - -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. We call such type classes `bind once`:idx: types. -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. Such -type classes are called `bind many`:idx: types. - -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 - - Stack[T] = concept s, var v - s.pop() is T - v.push(T) - - s.len is Ordinal - - for value in s: - 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 evaluable boolean expressions in the body must be true - -The identifiers following the ``concept`` keyword represent instances of the -currently matched type. You can apply any of the standard type modifiers such -as ``var``, ``ref``, ``ptr`` and ``static`` to denote a more specific type of -instance. You can also apply the `type` modifier to create a named instance of -the type itself: - -.. code-block:: nim - type - MyConcept = concept x, var v, ref r, ptr p, static s, type T - ... - -Within the concept body, types can appear in positions where ordinary values -and parameters are expected. This provides a more convenient way to check for -the presence of callable symbols with specific signatures: - -.. code-block:: nim - type - OutputStream = concept var s - s.write(string) - -In order to check for symbols accepting ``typedesc`` params, you must prefix -the type with an explicit ``type`` modifier. The named instance of the type, -following the ``concept`` keyword is also considered an explicit ``typedesc`` -value that will be matched only as a type. - -.. code-block:: nim - type - # Let's imagine a user-defined casting framework with operators - # such as `val.to(string)` and `val.to(JSonValue)`. We can test - # for these with the following concept: - MyCastables = concept x - x.to(type string) - x.to(type JSonValue) - - # Let's define a couple of concepts, known from Algebra: - AdditiveMonoid* = concept x, y, type T - x + y is T - T.zero is T # require a proc such as `int.zero` or 'Position.zero' - - AdditiveGroup* = concept x, y, type T - x is AdditiveMonoid - -x is T - x - y is T - -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 concept body, it's also possible -to describe 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 the body is executed only once. - - -Concept diagnostics -------------------- - -By default, the compiler will report the matching errors in concepts only when -no other overload can be selected and a normal compilation error is produced. -When you need to understand why the compiler is not matching a particular -concept and, as a result, a wrong overload is selected, you can apply the -``explain`` pragma to either the concept body or a particular call-site. - -.. code-block:: nim - type - MyConcept {.explain.} = concept ... - - overloadedProc(x, y, z) {.explain.} - -This will provide Hints in the compiler output either every time the concept is -not matched or only on the particular call-site. - - -Generic concepts and type binding rules ---------------------------------------- - -The concept types can be parametric just like the regular generic types: - -.. code-block:: nim - ### matrixalgo.nim - - import typetraits - - type - AnyMatrix*[R, C: static[int]; T] = concept m, var mvar, type M - M.ValueType is T - M.Rows == R - M.Cols == C - - m[int, int] is T - mvar[int, int] = T - - type TransposedType = stripGenericParams(M)[C, R, T] - - AnySquareMatrix*[N: static[int], T] = AnyMatrix[N, N, T] - - AnyTransform3D* = AnyMatrix[4, 4, float] - - proc transposed*(m: AnyMatrix): m.TransposedType = - for r in 0 .. <m.R: - for c in 0 .. <m.C: - result[r, c] = m[c, r] - - proc determinant*(m: AnySquareMatrix): int = - ... - - proc setPerspectiveProjection*(m: AnyTransform3D) = - ... - - -------------- - ### matrix.nim - - type - Matrix*[M, N: static[int]; T] = object - data: array[M*N, T] - - proc `[]`*(M: Matrix; m, n: int): M.T = - M.data[m * M.N + n] - - proc `[]=`*(M: var Matrix; m, n: int; v: M.T) = - M.data[m * M.N + n] = v - - # Adapt the Matrix type to the concept's requirements - template Rows*(M: type Matrix): expr = M.M - template Cols*(M: type Matrix): expr = M.N - template ValueType*(M: type Matrix): typedesc = M.T - - ------------- - ### usage.nim - - import matrix, matrixalgo - - var - m: Matrix[3, 3, int] - projectionMatrix: Matrix[4, 4, float] - - echo m.transposed.determinant - setPerspectiveProjection projectionMatrix - -When the concept type is matched against a concrete type, the unbound type -parameters are inferred from the body of the concept in a way that closely -resembles the way generic parameters of callable symbols are inferred on -call sites. - -Unbound types can appear both as params to calls such as `s.push(T)` and -on the right-hand side of the ``is`` operator in cases such as `x.pop is T` -and `x.data is seq[T]`. - -Unbound static params will be inferred from expressions involving the `==` -operator and also when types dependent on them are being matched: - -.. code-block:: nim - type - MatrixReducer[M, N: static[int]; T] = concept x - x.reduce(SquareMatrix[N, T]) is array[M, int] - -The Nim compiler includes a simple linear equation solver, allowing it to -infer static params in some situations where integer arithmetic is involved. - -Just like in regular type classes, Nim discriminates between ``bind once`` -and ``bind many`` types when matching the concept. You can add the ``distinct`` -modifier to any of the otherwise inferable types to get a type that will be -matched without permanently inferring it. This may be useful when you need -to match several procs accepting the same wide class of types: - -.. code-block:: nim - type - Enumerable[T] = concept e - for v in e: - v is T - - type - MyConcept = concept o - # this could be inferred to a type such as Enumerable[int] - o.foo is distinct Enumerable - - # this could be inferred to a different type such as Enumerable[float] - o.bar is distinct Enumerable - - # it's also possible to give an alias name to a `bind many` type class - type Enum = distinct Enumerable - o.baz is Enum - -On the other hand, using ``bind once`` types allows you to test for equivalent -types used in multiple signatures, without actually requiring any concrete -types, thus allowing you to encode implementation-defined types: - -.. code-block:: nim - type - MyConcept = concept x - type T1 = auto - x.foo(T1) - x.bar(T1) # both procs must accept the same type - - type T2 = seq[SomeNumber] - x.alpha(T2) - x.omega(T2) # both procs must accept the same type - # and it must be a numeric sequence - -As seen in the previous examples, you can refer to generic concepts such as -`Enumerable[T]` just by their short name. Much like the regular generic types, -the concept will be automatically instantiated with the bind once auto type -in the place of each missing generic param. - -Please note that generic concepts such as `Enumerable[T]` can be matched -against concrete types such as `string`. Nim doesn't require the concept -type to have the same number of parameters as the type being matched. -If you wish to express a requirement towards the generic parameters of -the matched type, you can use a type mapping operator such as `genericHead` -or `stripGenericParams` within the body of the concept to obtain the -uninstantiated version of the type, which you can then try to instantiate -in any required way. For example, here is how one might define the classic -`Functor` concept from Haskell and then demonstrate that Nim's `Option[T]` -type is an instance of it: - -.. code-block:: nim - import future, typetraits - - type - Functor[A] = concept f - type MatchedGenericType = genericHead(f.type) - # `f` will be a value of a type such as `Option[T]` - # `MatchedGenericType` will become the `Option` type - - f.val is A - # The Functor should provide a way to obtain - # a value stored inside it - - type T = auto - map(f, A -> T) is MatchedGenericType[T] - # And it should provide a way to map one instance of - # the Functor to a instance of a different type, given - # a suitable `map` operation for the enclosed values - - import options - echo Option[int] is Functor # prints true - - -Concept derived values ----------------------- - -All top level constants or types appearing within the concept body are -accessible through the dot operator in procs where the concept was successfully -matched to a concrete type: - -.. code-block:: nim - type - DateTime = concept t1, t2, type T - const Min = T.MinDate - T.Now is T - - t1 < t2 is bool - - type TimeSpan = type(t1 - t2) - TimeSpan * int is TimeSpan - TimeSpan + TimeSpan is TimeSpan - - t1 + TimeSpan is T - - proc eventsJitter(events: Enumerable[DateTime]): float = - var - # this variable will have the inferred TimeSpan type for - # the concrete Date-like value the proc was called with: - averageInterval: DateTime.TimeSpan - - deviation: float - ... - - -Concept refinement ------------------- - -When the matched type within a concept is directly tested against a different -concept, we say that the outer concept is a refinement of the inner concept and -thus it is more-specific. When both concepts are matched in a call during -overload resolution, Nim will assign a higher precedence to the most specific -one. As an alternative way of defining concept refinements, you can use the -object inheritance syntax involving the ``of`` keyword: - -.. code-block:: nim - type - Graph = concept g, type G of EqualyComparable, Copyable - type - VertexType = G.VertexType - EdgeType = G.EdgeType - - VertexType is Copyable - EdgeType is Copyable - - var - v: VertexType - e: EdgeType - - IncidendeGraph = concept of Graph - # symbols such as variables and types from the refined - # concept are automatically in scope: - - g.source(e) is VertexType - g.target(e) is VertexType - - g.outgoingEdges(v) is Enumerable[EdgeType] - - BidirectionalGraph = concept g, type G - # The following will also turn the concept into a refinement when it - # comes to overload resolution, but it doesn't provide the convenient - # symbol inheritance - g is IncidendeGraph - - g.incomingEdges(G.VertexType) is Enumerable[G.EdgeType] - - proc f(g: IncidendeGraph) - proc f(g: BidirectionalGraph) # this one will be preferred if we pass a type - # matching the BidirectionalGraph concept - - -Converter type classes ----------------------- - -Concepts can also be used to convert a whole range of types to a single type or -a small set of simpler types. This is achieved with a `return` statement within -the concept body: - -.. code-block:: nim - type - Stringable = concept x - $x is string - return $x - - StringRefValue[CharType] = object - base: ptr CharType - len: int - - StringRef = concept x - # the following would be an overloaded proc for cstring, string, seq and - # other user-defined types, returning either a StringRefValue[char] or - # StringRefValue[wchar] - return makeStringRefValue(x) - - # the varargs param will here be converted to an array of StringRefValues - # the proc will have only two instantiations for the two character types - proc log(format: static[string], varargs[StringRef]) - - # this proc will allow char and wchar values to be mixed in - # the same call at the cost of additional instantiations - # the varargs param will be converted to a tuple - proc log(format: static[string], varargs[distinct StringRef]) - - -VTable types ------------- - -Concepts allow Nim to define a great number of algorithms, using only -static polymorphism and without erasing any type information or sacrificing -any execution speed. But when polymorphic collections of objects are required, -the user must use one of the provided type erasure techniques - either common -base types or VTable types. - -VTable types are represented as "fat pointers" storing a reference to an -object together with a reference to a table of procs implementing a set of -required operations (the so called vtable). - -In contrast to other programming languages, the vtable in Nim is stored -externally to the object, allowing you to create multiple different vtable -views for the same object. Thus, the polymorphism in Nim is unbounded - -any type can implement an unlimited number of protocols or interfaces not -originally envisioned by the type's author. - -Any concept type can be turned into a VTable type by using the ``vtref`` -or the ``vtptr`` compiler magics. Under the hood, these magics generate -a converter type class, which converts the regular instances of the matching -types to the corresponding VTable type. - -.. code-block:: nim - type - IntEnumerable = vtref Enumerable[int] - - MyObject = object - enumerables: seq[IntEnumerable] - streams: seq[OutputStream.vtref] - - proc addEnumerable(o: var MyObject, e: IntEnumerable) = - o.enumerables.add e - - proc addStream(o: var MyObject, e: OutputStream.vtref) = - o.streams.add e - -The procs that will be included in the vtable are derived from the concept -body and include all proc calls for which all param types were specified as -concrete types. All such calls should include exactly one param of the type -matched against the concept (not necessarily in the first position), which -will be considered the value bound to the vtable. - -Overloads will be created for all captured procs, accepting the vtable type -in the position of the captured underlying object. - -Under these rules, it's possible to obtain a vtable type for a concept with -unbound type parameters or one instantiated with metatypes (type classes), -but it will include a smaller number of captured procs. A completely empty -vtable will be reported as an error. - -The ``vtref`` magic produces types which can be bound to ``ref`` types and -the ``vtptr`` magic produced types bound to ``ptr`` types. - - -Symbol lookup in generics -------------------------- - -Open and Closed symbols -~~~~~~~~~~~~~~~~~~~~~~~ - -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. - -Mixin statement ---------------- - -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. |