Chapter 27. generics

Generics are Nim’s means to parametrize routines or types with type parameters. Depending on the context, the brackets are used either to introduce type parameters or to instantiate a generic routine or type. A generic defines a family of types and routines. If G[T] is a generic depending on type T then multiple occurrences of G[C] where C is a concrete type such as int or string denote the same type. In other words structural type equivalence is used for generics and not name equivalence. The following example shows how a generic binary tree can be modeled: 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: BinaryTree[T] =

result = BinaryTree[T](le: nil, ri: nil, data: data)

proc add*T =

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:
                                                                   177
       if it.ri == nil:
         it.ri = n
         return
       it = it.ri

proc add*T =

# convenience proc:
add(root, newNode(data))

iterator preorder*T: T =

# Preorder traversal of a binary tree.
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)

In G[T] the T is called a generic type parameter or a type variable. 27.1. Is operator The is operator checks for type equivalence. It is therefore very useful for type specialization within generic code: type

Table[Key, Value] = object
   keys: seq[Key]
   values: seq[Value]
  when not (Key is string): # empty value for strings used for

optimization

     deletedKeys: seq[bool]

27.2. 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 178 following built-in type classes: Table 9. 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 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 with the | operator to form more complex type classes: # create a type class that will match all tuple and object types type RecordType = (tuple | object) proc printFieldsT: RecordType =

for key, value in fieldPairs(rec):
  echo key, " = ", value

Type constraints on generic parameters can be grouped with , and propagation stops with ;, similarly to parameters for macros and templates: proc fn1[T; U, V: SomeFloat]() = discard # T is unconstrained template fn2(T; u, v: SomeFloat) = discard # T is unconstrained

Nim allows for type classes and regular types to be specified as type constraints of the generic type parameter: proc onlyIntOrStringT: int|string = discard onlyIntOrString(450, 616) # valid onlyIntOrString(5.0, 0.0) # type mismatch: float is not an int or a string onlyIntOrString("xy", 50) # invalid as 'T' cannot be both at the same time 27.3. Implicit generics A type class can be used directly as the parameter’s type. # create a type class that will match all tuple and object types type RecordType = (tuple | object) proc printFields(rec: RecordType) =

for key, value in fieldPairs(rec):
  echo key, " = ", value

Routines utilizing type classes in such a manner are considered to be implicitly generic. They will be instantiated once for each unique combination of param types used within the program.

         Implicit generics can make the code harder to understand as a



         generic has different symbol binding rules than non-generics.
         Instead of proc p(x, y: tuple) prefer proc p[T: tuple](x, y:
         T).

By default, during overload resolution, each named type class will bind to exactly one concrete type. We call such type classes bind once types. Here is an example taken directly from the system module to illustrate this: 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 180 allow each param matching the type class to bind to a different type. Such type classes are called bind many 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: type Matrix[T, Rows, Columns] = object

...

proc [](m: Matrix, row, col: int): Matrix.T =

m.data[col * high(Matrix.Columns) + row]

Here are more examples that illustrate implicit generics: proc p(t: Table; k: Table.Key): Table.Value # is the same as (except that it also adds Key and Value to the scope): proc pKey, Value: Value proc p(a: Table, b: Table) # is the same as (except that it also adds Key and Value to the scope): proc pKey, Value proc p(a: Table, b: distinct Table) # is the same as (except that it also adds Key and Value to the scope): proc pKey, Value, KeyB, ValueB typedesc used as a parameter type also introduces an implicit generic. typedesc has its own set of rules: proc p(a: typedesc) # is the same as (except that it also adds T to the scope): proc pT

typedesc is a "bind many" type class: proc p(a, b: typedesc) # is roughly the same as: proc pT, T2 A parameter of type typedesc is itself usable as a type. If it is used as a type, it’s the underlying type. (In other words, one level of "typedesc"-ness is stripped off): proc p(a: typedesc; b: a) = discard # is roughly the same as: proc pT = discard # hence this is a valid call: p(int, 4) # as parameter 'a' requires a type, but 'b' requires a value. 27.4. Generic inference restrictions The types var T and typedesc[T] cannot be inferred in a generic instantiation. The following is not allowed: proc gT =

f(x)

proc c(y: int) = echo y proc v(y: var int) =

y += 100

var i: int # allowed: infers 'T' to be of type 'int' g(c, 42) # not valid: 'T' is not inferred to be of type 'var int' g(v, i) # also not allowed: explicit instantiation via 'var int' gvar int 182 27.5. Symbol lookup in generics The symbol binding rules in generics are slightly subtle: There are “open” and “closed” symbols. 27.5.1. Open and Closed symbols A “closed” symbol cannot be re-bound in the instantiation context, an “open” symbol can. Per default, symbols that are overloaded in the scope of the generic definition are open and all other symbols are closed. Open symbols are looked up in two different contexts: Both the context at definition and the context at instantiation are considered: 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. 27.6. Mixin statement A symbol can be forced to be open by a mixin declaration: 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

mixin statements are only available in templates and generics.

27.7. 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): # Module A var

lastId = 0

template genId*: untyped =

bind lastId
inc(lastId)
lastId

# Module B import A echo genId() But a bind is rarely useful because symbol binding from the definition scope is the default. bind statements are only available in templates and generics. 27.8. Delegating bind statements The following example outlines a problem that can arise when generic instantiations cross multiple different modules: # module A proc genericA*T =

mixin init
init(x)

# module C type O = object proc init(x: var O) = discard import C 184 # module B proc genericBT =

# Without the `bind init` statement C's init proc is
# not available when `genericB` is instantiated:
bind init
genericA(x)

# module main import B, C genericB O() Module B has an init proc from module C in its scope that is not taken into account when genericB is instantiated which leads to the instantiation of genericA. The solution is to forward these symbols by a bind statement inside genericB. 27.9. Templates A template is a simple form of a macro: It is a simple substitution mechanism that operates on Nim’s abstract syntax trees. The syntax to invoke a template is the same as calling any other kind of routine. Example: template != (a, b: untyped): untyped =

# this definition exists in the system module
not (a == b)

assert(5 != 6) # transformed into: assert(not (5 == 6)) The !=, >, >=, in, notin, isnot operators are in fact templates: a > b is transformed into b < a. a in b is transformed into contains(b, a). notin and isnot have the obvious meanings. The “types” of template parameters can be the symbols untyped, typed or typedesc. These are “meta types”, they can only be used in certain contexts. Regular types can be used too; this implies that typed expressions are

expected. 27.10. Typed vs untyped parameters For an untyped parameter symbol lookups and type resolution is not performed before the expression is passed to the template. This means that semantic checking of the argument that is passed to an untyped parameter is lazily done. The implications of this mechanism are important to understand. For example, it means that undeclared identifiers can be passed to the template: template declareInt(x: untyped) =

var x: int

declareInt(x) # valid x = 3 template declareInt(x: typed) =

var x: int

declareInt(x) # invalid, because x has not been declared and so it has no type A template where every parameter is untyped is called an immediate template. For historical reasons, templates can be explicitly annotated with an immediate pragma and then these templates do not take part in overloading resolution and the parameters' types are ignored by the compiler. Explicit immediate templates are deprecated. 27.11. Passing a code block to a template One can pass a block of statements as the last argument to a template following the special : syntax: template withFile(f, fn, mode, actions: untyped): untyped =

var f: File
if open(f, fn, mode):
  try:
    actions
  finally:
    close(f)
else:

186

   quit("cannot open: " & fn)

withFile(txt, "ttempl3.txt", fmWrite): # special colon

 txt.writeLine("line 1")
 txt.writeLine("line 2")

In the example, the two writeLine statements are bound to the actions parameter. Usually, to pass a block of code to a template, the parameter that accepts the block needs to be of type untyped. Because symbol lookups are then delayed until template instantiation time: template t(body: typed) =

 proc p = echo "p"
 block:
   body

 p()  # fails with 'undeclared identifier: p'

The above code fails with the error message that p is not declared. The reason for this is that the p() body is type-checked before getting passed to the body parameter and type checking implies symbol lookups. The same code works with untyped as the passed body is not required to be type-checked: template t(body: untyped) =

 proc p = echo "p"
 block:
   body

 p()  # compiles
          untyped parameters cause problems with overloading:
            template t(body: untyped) =   1
               proc p = echo "p"
              body
            proc t(a: int) = discard 2
            t:
               p()  3
                                                                       187
          1 A template that takes an untyped code snippet.
          2 A proc that overloads the symbol t.
          3 The code snippet p() needs to be checked for semantics
             before it can be decided which overloaded routine t to
             invoke. This conflicts with `t’s requirements.
         In theory the compiler could resolve the call to t without
         problem. In practice, at the time of this writing, the compiler is
         not able to do that. In the long run we hope to phase out
         untyped parameters; what they enable can be accomplished by
         other means that compose better.

27.12. Varargs of untyped In addition to the untyped meta-type that delays type checking, there is also varargs[untyped] so that not even the number of parameters is fixed: template hideIdentifiers(x: varargs[untyped]) = discard hideIdentifiers(undeclared1, undeclared2) However, since a template cannot iterate over varargs, this feature is generally much more useful for macros. 27.13. Symbol binding in templates A template is a hygienic macro and so opens a new scope. The distinction between open and closed symbols applies to templates as it does apply to generics: # Module A var lastId = 0 template genId*: untyped = inc(lastId) lastId 188 # Module B import A echo genId() # Works as 'lastId' is bound in 'genId's defining scope As in generics, symbol binding can be influenced via mixin or bind statements. 27.14. Identifier construction In templates, identifiers can be constructed with the backticks notation: template typedef(name: untyped, typ: typedesc) =

type
   `T name`* {.inject.} = typ
   `P name`* {.inject.} = ref `T name`

typedef(myint, int) var x: PMyInt In the example, name is instantiated with myint, so T name becomes Tmyint. 27.15. Template parameter lookup rules A parameter p in a template is even substituted in the expression x.p. Thus, template arguments can be used as field names and a global symbol can be shadowed by the same argument name even when fully qualified: # module 'm' type

Lev = enum
   levA, levB

var abclev = levB template tstLev(abclev: Lev) =

echo abclev, " ", m.abclev

tstLev(levA) # produces: 'levA levA'

But the global symbol can be captured by a bind statement: # module 'm' type

Lev = enum
   levA, levB

var abclev = levB template tstLev(abclev: Lev) =

bind m.abclev
echo abclev, " ", m.abclev

tstLev(levA) # produces: 'levA levB' 

          Instead of relying on this subtle rule, name your parameters so
          that they do not conflict with other names.

27.16. Hygiene in templates Per default, templates are hygienic: Local identifiers declared in a template cannot be accessed in the instantiation context. template ||(a, b: untyped): untyped =

let aa = a 1
if aa.len > 0: aa else: b

var a = "" var b = "abc" echo a || b || "def" 2 1 The variable aa is introduced so that the expression a is evaluated only

once.

2 The output of the program is "abc". Every expansion causes a “fresh” set of local variables to be created. These local variables do not interfere with each other. A template is thus very similar to an .inline proc or func. 190 27.16.1. Inject and gensym Whether a symbol that is declared in a template is exposed to the instantiation scope is controlled by the inject and gensym pragmas: gensym'ed symbols are not exposed but inject'ed symbols are. The default for symbols of entity type, var, let and const is gensym and for a routine it is inject. However, if the name of the entity is passed as a template parameter, it is an inject'ed symbol: template withFile(f, fn, mode: untyped, actions: untyped): untyped =

block:
  var f: File   # since 'f' is a template param, it's injected implicitly
   ...

withFile(txt, "ttempl3.txt", fmWrite):

txt.writeLine("line 1")
txt.writeLine("line 2")

The inject and gensym pragmas are second class annotations; they have no semantics outside of a template definition and cannot be abstracted over: {.pragma myInject: inject.} template t() =

var x {.myInject.}: int # does NOT work

To get rid of hygiene in templates, one can use the dirty pragma for a template. inject and gensym have no effect in dirty templates. gensym'ed symbols cannot be used as field in the x.field syntax. Nor can they be used in the ObjectConstruction(field: value) and namedParameterCall(field = value) syntactic constructs. The reason for this is that code like type

T = object
   f: int

template tmp(x: T) =

let f = 34
echo x.f, T(f: 4)
                                                                         191

should work as expected. However, this means that the method call syntax is not available for gensym'ed symbols: template tmp(x) = type

 T {.gensym.} = int

echo x.T # invalid: instead use: 'echo T(x)'. tmp(12) 27.17. Method call syntax limitations The expression x in x.f needs to be checked for semantics (that means symbol lookup and type checking have to be performed) before it can be decided that it needs to be rewritten to f(x). Therefore the dot syntax has some limitations when it is used to invoke templates/macros: template declareVar(name: untyped) = const name {.inject.} = 45 # Doesn't compile: unknownIdentifier.declareVar

ch27.md 19 KB 文件歷史 原始文件

Chapter 27. generics

ch27.md 19 KB

文件歷史原始文件