[RFC] template constraint: allows overloading templates with untyped; more powerful than concepts

[timotheecour]

in D, we can overload templates using template constraints:

void myMap(alias lambda, T)(a:T) if isSomeProperty(lambda, T) { }
10.myMap!(a=>a)
# can be overloaded:
void myMap(alias lambda, T)(a:T) if isSomeOtherProperty(lambda, T) { }

in Nim, templates with untyped params can't have constraints attached to these untyped params so these can't be overloaded from these untyped params:

template foo(a:untyped)=discard
template foo(a:untyped)=discard # can't overloaded like that, since no constraint can be expressed on `a`

This also leads to worse error messages and function documentation, since the type checking happens inside the instantiated foo, as opposed to before instantiation is attempted, via a template constraint.

proposal: template constraint

suggested syntax:

template myMap[T](a:T, lambda: untyped) when isSomeProperty1(lambda, T) = discard
template myMap[T](a:T, lambda: untyped) when isSomeProperty2(lambda, T) = discard # overloaded!
10.foo(a=>a)

# more complex example with 2 untyped params:
proc isSomeProperty(lambda1: untyped, lambda2: untyped, T: typedesc): bool =
  makeLambda(lambda1, fun1) # from https://github.com/nim-lang/Nim/pull/8679
  makeLambda(lambda2, fun2)
  # in this example, we make sure the lamdas satisfy given constraint:
  result = compiles(fun1(T.default) < fun2(T.default))

template myMap[T](a:T, lambda1: untyped, lambda2: untyped) when isSomeProperty(lambda1, lambda2, T) = discard

comparison to concepts

• concepts doesn't allow you to specify constraints on untyped param
• concepts can only apply to a single argument, and can't express a template constraint that needs to consider more than 1 argument, eg:

proc foo[T1,T2](a:T1, b: T2) when T1.sizeof < T2.sizeof = discard
proc foo[T1,T2](a:T1, b: T2) when T1.sizeof == T2.sizeof = discard

=> doesn't seem possible in Nim

benefits

• would fix: Exporting a toSeq overload messes up iterator visibility #7322
• this would allow for eg writing lambdas (see [TODO] Nim now supports true lambdas; eg allows map(a~>a*localVar) (wo limitations of sugar.nim =>) Nim#8679) with type constraints and allow overloading
• would allow providing better error messages when attempting to call a proc/template/macro gives a compiler error, especially dealing with untyped params (early type checking); eg: would fix error message given here [1]
• would allow specifying an isIterator constraint, and restricting / overloading a template that takes an untyped argument representing an iterator (eg use case: toSeq(walkPattern("...")) ; note that toSeq(foo: iterator) doesn't work for that: it requires untyped);
• [very minor point] simpler to use than concepts for one-off cases where a template constraint is just used in 1 location
• [EDIT] (need to double check this point) we wouldn't need openArray[T] with template constraints, avoiding issues associated with openArray eg https://github.com/nim-lang/Nim/issues/9001 or converter gives inconsistent ambiguous call error with openarray Nim#10019)

notes

• template constraints would work in all other "function" contexts too (eg: func, proc, macro, iterator)
• probably low and localized implementation complexity (IMO, I could be wrong)
• would work well in combination with concepts: a template constraint could itself use concepts

discussion on syntax:

• option 1: using when

template myMap[T](a:T, lambda: untyped) when isSomeProperty1(lambda, T) = discard
# with a return type specified:
template myMap[T](a:T, lambda: untyped) : Bar when isSomeProperty2(lambda, T, Bar) = discard

• option 2: via a pragma when (or maybe constraint):

template myMap[T](a:T, lambda: untyped) : Bar {.when: isSomeProperty1(lambda, T, Bar) .} = discard

links

[1] Confusing error message when calling toSeq using a non-iterator #7182
EDIT: implemented via nim-lang/Nim#12048 (need to check whether nim-lang/Nim#12048 100% covers this)

[Araq]

concepts doesn't allow you to specify constraints on untyped param

untyped parameters are hard and their restrictions make any proposal like yours equally hard to implement.

concepts can only apply to a single argument, and can't express a template constraint that needs to consider more than 1 argument, eg:

Yeah, whatever. So move your when sizeof check into the generic. "But, but, but... that's not extensible then!" -- Yeah, but it means the selected overload can't depend on freaking sizeof computations!

[mratsim]

It feels like unnecessary complexity you can already do that today:

template myMapImpl1() {.dirty.} =
  discard

template myMapImpl2() {.dirty.} =
  discard

template myMap[T](a:T, lambda: untyped) =
  when isSomeProperty1(lambda, T):
    myImpl1()
  elif isSomeProperty2(lambda, T, Bar)
    myImpl2()
  else:
    discard

Edit: but yes that wouldn't help if we want a consistent toSeq across all libraries. But maybe toSeq should use the Iterable concept of https://github.com/nim-lang/Nim/issues/7996

[zah]

In Nim, it's legal to say:

template foo[T](x: T, y: SomeConcept[T]) 

... which can be used to encode arbitrary inter-argument dependencies for well-typed arguments. Generic templates do have implementation issues right now though, so I'm not sure if the above works at the moment.

What kind of constraint would you put on an untyped parameter in D? untyped means that you only care about the AST structure, so any constraint must take into account only the AST. I've actually considered adding procedural AST constraints in the past. Just like you can now say untyped{nnkSym}, you may be able to say untyped{someAstPredicateFunc}, but is this what you're after?

[timotheecour]

@zah

Just like you can now say untyped{nnkSym}

are you sure?
template foo2(fun: untyped{nnkSym}, a: int): auto = 123 gives Error: illformed AST: nnkSym (and untyped[nnkSym] gives Error: type expected)

untyped means that you only care about the AST structure, so any constraint must take into account only the AST.

that's not true under this proposal, see below examples based on compiles; it allows arbitrary type-checking or AST-checking constraints

What kind of constraint would you put on an untyped parameter

Many use cases:

• for my lambda PR [TODO] Nim now supports true lambdas; eg allows map(a~>a*localVar) (wo limitations of sugar.nim =>) Nim#8679, allowing type constraints (or other constraints) on untyped lambda param:

# this checks that fun is a lambda
template map[T](s: T, fun:untyped) : auto when isLambda(fun) = ...

# more strict test: this checks that fun is a lambda that can be applied on `ElementType(s)`
template map[T](s: T, fun:untyped) : auto when isLambda(fun, ElementType(s)) = ...
# with:
template isLambda(fun:untyped, typedesc T): bool = compiles(lambdaEval(fun, T))

[1,2].map(a~>a*2) #ok: selects above map overload

# now, map can be overloaded (including in other modules!), eg:
template map[T, S](s: T, fun: proc (x: T)) : auto = ...

[1,2].map(a=>a*2) #ok: selects 2nd overload

# for mapIt afficionados (ie, with `it` shortform of lambdas); again, can be placed in a different module from other overloads!
template map[T](s: T, fun: untyped) : auto when isLambdaIt(fun, s) = ...
[1,2].map(it*2) #ok: selects 3nd overload

• for toSeq:

template toSeq(s:untyped) : auto when isIterable(s) = ...

Note: isIterable here is more general than Iterable from https://github.com/nim-lang/Nim/issues/7996 as it allows passing in myIter(5) (which has no type when myIter is an inline iterator), as used toSeq; That would fix issues like https://github.com/nim-lang/Nim/issues/7322

@mratsim

you can already do that today

I know that (that's what I'm exploting in my universal toSeq PR nim-lang/Nim#8711); but that prevents having overloads in different modules, eg having a user defined imported toSeq in presence of import sequtils (see https://github.com/nim-lang/Nim/issues/7322)

But maybe toSeq should use the Iterable concept of #7996

no, that cannot work:

iterator myIter(a:int):auto = yield a
template toSeq2(s:Iterable)=discard # or even template toSeq2(s:typed)=discard
toSeq(myIter(3)) #works because toSeq accepts untyped (and this use case is used a lot)
toSeq2(myIter(3)) # Error: attempting to call undeclared routine: 'myIter'

[zah]

@timotheecour, I was trying to explain how the existing features of Nim fit into the picture, how the language can be extended in a logical way to reach your goals. Admittedly, I don't have a working solution for you now, only a possible alternative to what is being suggested here.

Just like you can now say untyped{nnkSym}

The {nnkSym} constraints in particular are explained here:

https://nim-lang.org/docs/manual.html#term-rewriting-macros-parameter-constraints

The reasoning why by untyped we mean "only AST", is explained here:

https://stackoverflow.com/questions/31367313/typed-vs-untyped-vs-expr-vs-stmt-in-templates-and-macros

So, if you want a new syntactic construct such as a ~> a * 2, this is something that an AST constraint can detect without looking at specific types.

If you are after eliminating the indirect calls introduced by regular closures, Nim can also emulate C++-style functor objects through generic functions executed with types overloading the () operator. You can then have a Callable concept that generalizes functor objects and closures. A reasonable suggestion would be to ask for a closure-like signature that acts like a generic type, compiling the function with statically dispatched code for each unique closure being given (in other words, a syntax sugar over the aforementioned functor objects).

Finally, if you want to deal with the current problem of iterators not being properly typed (and the lack of support for higher-order iterators), let's write an RFC for that. I've been planning to write one myself. I do share the view that the best possible way to define map is as an iterator, because this allows you to avoid allocating memory for the result (and actually allows you to select the container type of the result, if any).

[Araq]

untyped is what it is, toSeq cannot use typed (but should!) because Nim allows iterators and procs of the same name. That seems to be the root cause here, too much overloading, not too little of it.

[timotheecour]

/cc @zah

In Nim, it's legal to say:

template foo[T](x: T, y: SomeConcept[T]) 

which can be used to encode arbitrary inter-argument dependencies for well-typed arguments

this has limitations that my RFC doesn't have, eg, arguments must be given in a specific order, see below:

when defined(case1):
  # ok
  type SomeConcept[T] = concept a
    var y:T
    type(y[0]) is type(a)

  proc foo[T](x: T, y: SomeConcept[T])=
    echo (x,y)
  foo([1], 2)

when defined(case2):
  # Error: type mismatch
  import timn/util/util_traits
  type SomeConcept[T] = concept a
    var y:T
    type(y[0]) is type(a)

  proc foo[T](x: SomeConcept[T], y: T) =
    echo (x,y)
  foo(2, [1])

in more complex cases, this workaround would become impossible.

[zah]

@timotheecour, do you have an example case where it's not possible to re-order the arguments to solve the problem? It seems to me that re-ordering won't be possible only if there are cyclic requirements between the types, but this sounds a bit ill-constructed at first glance.

The problem can also be solved with a fixed-point binding process (or just by delaying the evaluation of the concepts), although this is not something I would like to add to the compiler.

[timotheecour]

it's not always desirable to re-order elements, eg when overloading, or in case of UFCS where a variable makes more sense to be in 1st position, etc; and yes, cyclic requirements make this approach based on concepts impossible.
Here's another example that I just filed, where using the proposed template constraint would alleviate other limitations I'm running into with concepts, see nim-lang/Nim#9071

The problem can also be solved with a fixed-point binding process (or just by delaying the evaluation of the concepts), although this is not something I would like to add to the compiler.

indeed, this would be lot more complicated than proposed template constraint

[github-actions]

This RFC is stale because it has been open for 1095 days with no activity. Contribute a fix or comment on the issue, or it will be closed in 30 days.