RFC: Generic generic parameters

[bpr]

Nim doesn't allow parameters of generic to be generic themselves. The lack of this feature has come up a few times, sometimes in the context of implementing something from functional programming like a
flatMap or monadic API, and also as with C++ in parameterizing containers. The usual workaround in the
absence of this feature is to pass in only instantiated types to generics.

This feature exists in C++, D, and Scala, and it is one of the highly desired missing features from Rust, see 'higher kinded types', or HKT, where it's perhaps more necessary than in Nim since Rust uses algebraic data types for errors rather than exceptions. Having this, variadic generics, and working static[T], and concepts will close the gap between Nim and C++ 17.

[vegansk]

👍 for HKT!

[Araq]

Note that higher kinded types are not as required since you can simply underspecify generic constraints in Nim (Nim's generics are close to C++ templates in this regard).

[bpr]

The feature, while not required, is consistent with (my view of) the Nim way, works especially well with concepts, and increases the expresiveness of the type system. That you can get around their omission by specifying less strikes me as making a virtue of a necessity. Let's take the simplest example in pseudo-Nim

type
  Array[T] = concept a
    a.len is Ordinal
    get(a, Ordinal) is T
    for value in a:
      type(value) is T

  Map[K, V, A: Array[T]] = object
    keys: A[K]
    values: A[V]

The meaning is clear, and the variations on this (allowing another generic array param to allow different arrays to back keys and values) are straightforward.

[Xe]

Isn't this already the case?

[vegansk]

@Xe, no. The previous example is written in pseudo-Nim. You can't implement Map like this in real Nim. How I wish to be wrong, but I can't find any solution.

[bpr]

@Xe, the issue is not concepts, but "generic generic parameters", that is, using uninstantiated generics as the parameters of a generic, as A is in Map in the example. If you fix the syntax, the compiler will tell you: 'Error: no generic parameters allowed for A'.

Concepts make this feature much nicer.

[mratsim]

I would love that.

I have a base method declared with a generic type TT (TT is expected to be Container[T])

But in some implementations I need to get access to the T subtype of TT for proc like newSeq[T](foo) to return a new container.

[metagn]

This works:

type
  Array[T] = concept a
    a.len is Ordinal
    #get(a, Ordinal) is T
    for value in a:
      value is T

  Map[K, V] = concept m
    type A = Array
    m.keys is A[K]
    m.values is A[V]

template mapImpl(A: typedesc): auto =
  type MapImpl[Key, Value] = object
    keys: A[Key]
    values: A[Value]
  
  assert MapImpl is Map
  
  MapImpl

proc get[T](arr: openarray[T], idx: Ordinal): T = arr[idx]

type
  SeqMap = mapImpl(seq)

iterator pairs(m: Map): (m.K, m.V) =
  let ks = iterator(keys: type(m.keys)): m.K =
    for k in keys:
      yield k
  let vs = iterator(values: type(m.values)): m.V =
    for v in values:
      yield v
  while true:
    let p = (ks(m.keys), vs(m.values))
    if ks.finished or vs.finished: break
    yield p

proc toSeqMap[K, V](ps: openarray[(K, V)]): SeqMap[K, V] =
  result.keys = newSeq[K](ps.len)
  result.values = newSeq[V](ps.len)
  for i, p in ps.pairs:
    (result.keys[i], result.values[i]) = p

var sm = {"a": 1, "b": 2}.toSeqMap

for k, v in sm:
  echo "key: ", k, ", value: ", v

Comment out the get(a, Ordinal) is T line and it breaks. Change it with a[Ordinal] is T and it breaks again because the system module says T[I] is T for whatever reason

[Kazark]

I believe that as people scorned generic types in the past (Java, Go) and have always ended up conceding in the end (and being rescued by Wadler) so one day languages that have said "we do not need higher-kinded generics" will realize that they ought to be a standard part of modern languages. Nim would do well to add itself to the (currently relatively short) list of (non-toy) languages that have this feature today. It would be a way of giving itself a boost (particularly with the functional community).

[mratsim]

I believe that as people scorned generic types in the past (Java, Go) and have always ended up conceding in the end (and being rescued by Wadler) so one day languages that have said "we do not need higher-kinded generics" will realize that they ought to be a standard part of modern languages. Nim would do well to add itself to the (currently relatively short) list of (non-toy) languages that have this feature today. It would be a way of giving itself a boost (particularly with the functional community).

Since 2016, Nim support for higher-kinded type is actually quite usable. The only limitation being generic generics in the proc signature but you can do

proc foo[T](a: T) =
  type U = T.U # Access the nested generics

instead of having to do

proc foo[T, U](a: T[U]) =
  discard

which is a ergonomic improvement.

I.e. functionality is there, and this RFC improves ergonomics.

[Kazark]

@mratsim thanks for the clarification. Maybe just an ignorance of the syntax here, but type U = T.U looks like an existential type to me, whereas the second one looks like a universal (forall). What I mean is, where is the U bound in the first case? It looks to me like it is only bound within the body, not within the signature.

This is probably just my ignorance. Where's the best place to read up on this? (Searching led me here.)

[mratsim]

@mratsim thanks for the clarification. Maybe just an ignorance of the syntax here, but type U = T.U looks like an existential type to me, whereas the second one looks like a universal (forall). What I mean is, where is the U bound in the first case? It looks to me like it is only bound within the body, not within the signature.

This is probably just my ignorance. Where's the best place to read up on this? (Searching led me here.)

It would come from the type declaration, assuming:

type Foo[U] = object
  field: U

proc foo[T](a: T) =
  type U = T.U # Access the nested generics

The best places to show examples of Nim higher-kinded types in use are probably:

• Emmy: https://github.com/unicredit/emmy#algebraic-structures which uses concepts to model Algebraic Structures
• Constantine: to model towers of extension fields for number theory/cryptography
  • https://github.com/mratsim/constantine/blob/ec76ac5e/constantine/tower_field_extensions/tower_common.nim
  • Quadratic extension field (i.e. modular arithmetic with coordinate a + 𝑖b with 𝑖 a quadratic non-Residue in the base prime field (usually sqrt(-1) depending on the prime): https://github.com/mratsim/constantine/blob/ec76ac5e/constantine/tower_field_extensions/quadratic_extensions.nim
  • Elliptic curves build on top of the base prime field or the extension field with compile-time switch depending on the base field Fp or the extension Field Fp2: https://github.com/mratsim/constantine/blob/ec76ac5e/constantine/elliptic/ec_weierstrass_affine.nim#L16-L57
  • And the base field is build on top of a generic BIgInt type which is generic over the number of bits: https://github.com/mratsim/constantine/blob/ec76ac5e/constantine/config/type_bigint.nim#L16-L28

    func wordsRequired*(bits: int): int {.compileTime.} =
      (bits + WordBitWidth - 1) div WordBitWidth
    
    type
      BigInt*[bits: static int] = object
        limbs*: array[bits.wordsRequired, SecretWord]

    Note that the last part also shows Nim dependent types.
    Also the difference betwen when and if is that when is evaluated and dispatched at compile-time
  • Finally concretizing the nesting of types to implement elliptic curve and pairing-based cryptography in a generic way: https://github.com/mratsim/constantine/blob/ec76ac5e/constantine/towers.nim
    • distinct type: SecretWord (uint32 on 32-bit, uint64 on 64-bit)
    • Limbs: array of SecretWord
    • BigInt[bits]: with limbs derived from the number of bits (dependent types)
    • Finite Field parametrized with a prime which in turn set the number of bits in the BigInt
    • Fp2 constructed on top of of 2 finite field elements
    • Fp6 constructed on top of 3 Fp2 elements
    • Fp12 constructed on top of 2 Fp6 elements and which shares the same code as Fp2 (higher kinded-types
    • Elliptic curve additive group G1 constructed on top of finite field elements
    • Elliptic curve additive group G2 constructed on top of Fp2 elements and which shares the same code as G1
    • Elliptic curve multiplicative group GT (not implemented) constructed on top of Fp12

In short Nim is a practical language to implement math concepts in Number Theory in a generic way combining higher-kinded types and dependent-types like capabilities.
It's also as fast as specialized C libraries (as fast as assembly libraries coming).
And you have very few restrictions to precompute at compile-time. I do BigInt computation at compile-time in Constantine. The compilation time stays fast as well (contrary to C++).

Bonus, you can use unicode if it makes sense: https://github.com/mratsim/constantine/blob/ec76ac5e/constantine/towers.nim#L29

type
  Fp2*[C: static Curve] = object
    c0*, c1*: Fp[C]

  β = NonResidue

type
  Fp6*[C: static Curve] = object
    c0*, c1*, c2*: Fp2[C]

  ξ = NonResidue
    # We call the non-residue ξ on 𝔽p6 to avoid confusion between non-residue
    # of different tower level

type
  Fp12*[C: static Curve] = object
    c0*, c1*: Fp6[C]

  γ = NonResidue
    # We call the non-residue γ (Gamma) on 𝔽p6 to avoid confusion between non-residue
    # of different tower level