Typesafe first class templates

[metagn]

This RFC is a pipe dream for me and also a response to a comment by Araq in a relevant PR, though that PR is more general than this RFC. I'm also not expecting this any time soon, the point of 1.0 version releases should be to promote language stability and usage, not for new language concepts altogether.

Abstract

This RFC proposes the addition of first class compile time template variables, to allow functional AST transforms.

Motivation

Many of the issues are addressed already in nim-lang/Nim#11992, but this is a simpler subset of that PR and the problem can be expressed more simply as well.

The distinction between compile time rewriting and function passing in functional programming idioms like sequtils.mapIt and sequtils.map is annoying for newcomers to grasp. The implementation of idioms like sugar.dup have to be implemented in macros and account for things like syntax sugar due to the lack of a simple compile time function-like transform.

Description

First class templates come in 3 parts: a new template type similar to the proc type and iterator type, a way to treat templates as values, and anonymous templates.

1. The template type

This type will not be available as a runtime value, it will be a compile time value similar to typedesc. It will be denoted like template (a: T): S (nkTemplateTy like nkProcTy), a nullary template returning void as template(), and the generic typeclass representing all template types as simply template. Pragmas will not be part of the type information unlike the proc type.

The limitations of the types of the arguments for a template type are tricky, for now I can say they can take concrete types for arguments. auto/untyped might be available, since they don't require implicit generics, but typed/static/type/typedesc all do use implicit generics, so they might not be available.

2. Templates as values

This is again similar to typedesc, they cannot just be stored in constants or compile time variables, but they can work as routine arguments (or even generic arguments). The way to pass them around is simply to refer to them in an identifier, like procvars. This is backwards incompatible for nullary templates: they will be instantiated if used like this. This is not mentioned in the manual, so it's relatively safe to give it a new meaning, though there should still be a backwards compatibility switch for a transition method with either --useVersion or with a define. Here is an example of the current behaviour:

template bar = echo 3

bar # => 3

template foo(x: int) = echo x

foo # Error: expression 'foo' is of type 'template (x: int)' and has to be discarded; for a function call use ()

It acknowledges that foo where foo has a positive arity has the type of a template, so the Nim compiler is in line with how we want it to treat template name identifiers. There are 2 solutions of how to keep the old behaviour while allowing the new behavior:

Inferred template variables

proc foo(templ: template()) = templ # void context, instantiated
proc templateWithValue[T](templ: template: T) =
  echo(templ) # obviously, we can't echo templates, nullary template variables that bind to any T are instantiated
proc baz(x: int) = echo x

template bar = echo "hi"
template nonVoid: int = 3

foo(bar) # inferred to be a template variable and passed to foo
bar # instantiated
baz(bar) # instantiated, fails with "type mismatch"

nonVoid # instantiated, fails with "has to be discarded"
templateWithValue(nonVoid) # passed as template variable, outputs 3
baz(nonVoid) # instantiated, outputs 3

I don't know if Nim has strong enough type inference for something like this, but I don't see it outside of the realm of possibility.

Explicit template reference

This is a last resort in relation to inferred template variables, and there are multiple ways to do this:

1. Proc defined as a magic:

# symbol irrelevant here, can be not an operator, feel free to bikeshed
proc `&`(templ: untyped): template {.magic: ExplicitTemplateVar.}
# if number 1 is implemented:
proc `&`[T: template](templ: T): T = templ

proc foo(templ: template()) = templ
proc templateWithValue[T](templ: template: T) =
echo(templ)
proc baz(x: int) = echo x

template bar = echo "hi"
template nonVoid: int = 3

foo(bar) # fails
foo(&bar) # works
bar # also works
baz(bar) # fails the same as foo(bar)
baz(&bar) # type mismatch

templateWithValue(nonVoid) # fails
templateWithValue(&nonVoid) # works
baz(nonVoid) # works
baz(&nonVoid) # type mismatch

2. Surrounding AST; from Araq, surrounding the identifier with parentheses:

proc foo(templ: template()) = templ
proc templateWithValue[T](templ: template: T) =
echo(templ)
proc baz(x: int) = echo x

template bar = echo "hi"
template nonVoid: int = 3

foo(bar) # fails
foo((bar)) # works
foo (bar) # also works
bar # also works
baz(bar) # fails the same as foo(bar)
baz((bar)) # type mismatch

templateWithValue(nonVoid) # fails
templateWithValue((nonVoid)) # works
baz(nonVoid) # works
baz((nonVoid)) # type mismatch

3. Anonymous templates:

Similar to anonymous procs in syntax. These aren't very hard to explain, except do notation behaviour when accounting for them. If the type of the last argument of a routine being called with do notation is strictly a template, it will turn the do block into an anonymous template. If it has an untyped/auto argument, it will turn it into an anonymous template. If it's anything else, including a generic T that has no bound, or template | proc, it will become a proc.

Examples

Before

import sequtils

let a = @[1, 2, 3, 4, 5]

template increment(x: int): int = x + 1

echo map(a, proc (x: int): int = increment(x))
echo mapIt(a, increment(it))
# 2 separate approaches, one is more efficient but one is typesafe

After

proc map[T, S](s: openarray[T], op: (template (x: T): S) or (proc (x: T): S)): seq[T] =
  newSeq(result, s.len)
  for i in 0 ..< s.len:
    result[i] = op(s[i])

let a = @[1, 2, 3, 4, 5]

template increment(x: int): int = x + 1

echo map(a, increment) # @[2, 3, 4, 5, 6]
echo map(a, template (x: int): int = x * 2) # @[2, 4, 6, 8, 10]
echo map(a, proc (x: int): int = x * 2) # @[2, 4, 6, 8, 10]

# reimplementation of sugar.dup without the sugar
template dup[T](x: T, op: template(it: var T)): T =
  var it = x
  op(it)
  it

let a = @[1, 2, 3, 4, 5, 6, 7, 8, 9]
doAssert(a.dup(template (it: var seq[int]) = # would benefit from type inference here
  it.add(10)
  it.sort()) == @[1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
doAssert a == @[1, 2, 3, 4, 5, 6, 7, 8, 9]

proc get[T](x: Option[T], otherwise: template(): T): T =
  if x.isSome:
    result = unsafeGet(x)
  else:
    result = otherwise()

iterator filter[T](s: openarray[T], op: (template (x: T): bool) or (proc (x: T): bool)): T =
  for it in s:
    if op(it): yield it

let a = @[1, 2, 3, 4, 5]

import sugar

# => here is valid, template(it) is actually template(it: untyped): void and nkTemplateTy
# another operator is fine though like ~>
for n in a.filter(template(it) => bool(it and 1)):
  echo n
  if n == 3: break
# 1
# 3

Backwards incompatibility

As mentioned before, identifiers with template names where the template is nullary will have different behaviour, but not necessarily backwards incompatible. (plus this feature isn't documented well, see nim-lang/Nim#7803)

[Araq]

Thank you, I'm beginning to love it. We can keep the backwards compatibility by the following rules:

• Non-overloaded nullary templates are always invoked immediately (I care about this rule because it allows for template myAlias: untyped = someLocation[i][j].
• Non-overloaded nullary templates can be passed around via parenthesis (mytempl). (And in general parenthesis can be used for this case.) Of course, instead of () other new notations/builtins are possible.

[metagn]

For forcing a template reference, I considered unary & in consistency with Ruby/Crystal and D defined as a magic in system, I think no one uses that. If they do, you can invoke it like system.`&`(templ) or use import as.

[Araq]

Unary & is already Nim's format operator and it doesn't fit Nim for an "address of"-like mechanism.

[zah]

The tyTemplate type would be a nice addition to the language, but you have to be careful about the semantics. One of the defining feature of templates is that they use call-by-name (a.k.a lazy) parameters.

These are easy to reason about when you create abstractions that lead to inlined code (i.e. templates calling other templates), but things quickly get complicated when you pass the template to a regular function and you need a run-time representation of the template (a closure or a C++ functor object).

If you imagine that the template would work as a C++ functor objects (which is the more reasonable choice; in other words the template-taking function gets a separate compiled copy for each unique template passed to it, also known as monomorphisation), you'll be tempted to claim that you are adding the last missing piece of the puzzle for function-like parameters, but then the lazy nature of templates will bite you back, because some things are very difficult to express in this model (templates have to be carefully written to avoid double evaluation of the input expressions that may have side-effects). You'll end up needing yet another piece of the puzzle anyway (a proc type that's treated with monomorphisation).

---

proc map[T, S](s: openarray[T], op: (template (x: T): S) or (proc (x: T): S)): seq[T] =
  newSeq(result, s.len)
  for i in 0 ..< s.len:
    result[i] = op(s[i])

The holy grail for type-safe map definitions is one that doesn't allocate memory. You need support for higher-order iterators to achieve this.

[metagn]

things quickly get complicated when you pass the template to a regular function and you need a run-time representation of the template

We don't need a runtime representation. The tyTemplate I'm imagining is erased like tyTypedesc and monomorphized, but the template passed to it is concrete, generics/typed/typedesc/static aren't allowed. As I see it, untyped being allowed doesn't lead to complications here, if it does then it could be disallowed as well.

the lazy nature of templates will bite you back, because some things are very difficult to express in this model (templates have to be carefully written to avoid double evaluation of the input expressions that may have side-effects).

Well yeah, but you already have to account for these with untyped transform idioms, people should already know how to do let it = s[i]. The only improvement here is giving the op AST structure and type safety.

You'll end up needing yet another piece of the puzzle anyway (a proc type that's treated with monomorphisation).

Yes, that's the trickiest part.

The holy grail for type-safe map definitions is one that doesn't allocate memory. You need support for higher-order iterators to achieve this.

I don't know how a map that doesn't allocate memory works, does the function produce T -> T (I don't know what the functional programming word for this kind of function is)? If so that's not hard.

[metagn]

I hacked this together: https://github.com/hlaaftana/applicates

This library creates the template when it's called (using a cache which I'm not proud of. are macro caches good practice?), not where it's defined. I'm not sure if I thought it would be possible for the templates to "capture" local symbols here (because I know my library can't), but it probably should in case this is in the language to not confuse people. Anyway if you don't need that kind of "capturing" (like instead of proc map you use template map, or you just don't care about local symbols) than that library should be good enough. Don't know if I should release on nimble because I don't feel like it's quality nor could I think of good tests for it

Edit: Never mind, completely revamping this library now, it is possible to capture local symbols if you register a typed template definition. I've expanded the library for all routine definitions (might do any possible nodes but it might broaden the scope of the library too much), though only templates and macros are really able to take advantage of being typed.

[metagn]

While writing tests for my package I came up with something that would be translated into the syntax in this proposal like:

template iter(iter: untyped): untyped =
  template(agg: template): untyped =
    for x in iter:
      agg(x)

template filter(iter: template, f: template): untyped =
  template(agg: template): untyped =
    iter(template(x): untyped =
      let x1 = x
      if f(x1):
        agg(x1))

template map(iter: template, f: template): untyped =
  template(agg: template): untyped =
    iter(template(x): untyped = agg(f(x)))

template apply(iter: template, f: template): untyped =
  iter(template(x): untyped = f(x))

template collect(iter: template): untyped =
  # weird hack to figure out type, this actually works in my tests
  var elemType {.compileTime.}: NimNode
  macro storeElemType(ty: typed) {.gensym.} =
    result = newEmptyNode()
    elemType = ty
  if false:
    iter(template(x): untyped = storeElemType(typeof(x)))
  macro getElemType(): untyped {.gensym.} =
    result = elemType
  var s: seq[getElemType()]
  iter.apply(template(x): untyped = s.add(x))
  s

# UFCS might not be able to work here but that can be solved with macro,
# only using dot notation for show
doAssert iter(-7..11)
  .filter(template(x): untyped = x mod 3 == 0)
  .map(template(x): untyped = x + 2)
  .filter(template(x): untyped = x > 0)
  .map(template(x): untyped = $x)
  .collect() == @["2", "5", "8", "11"]

I didn't use the name apply in my test because apply is what you use to instantiate the templates. enumerate and fold should also be possible. I did not bother to add generics/types to this because it would be extremely long and types of iterators are ugly. Ignoring that and the 27 template keywords I think this is a good addition to the examples in this RFC.

[Araq]

Related to your experiments, here are my thoughts: We need to get into a state where Nim's macros compose. The way the usual control flow structures if/case/while do this is:

• sem'check the children. (Symbol lookups and type checks happen in the sem'check phase.)
• Then check more constraints like: a while's condition must be of type bool.

In generic proc bodies we still lack the precise types, but we still want to perform symbol lookups. And as precisely as possible. The let, proc etc keywords allow us to know which constructs introduce new symbols. The problem with e.g. sequtils.mapIt is that we don't know that it introduces an it symbol in the following expression. This is not a problem for typed expressions which can be resolved before the macro expansion (but even then macro overloading is problematic), but for untyped it's problematic (and the current Nim compiler uses an undocumented mechanism to resolve it, iirc).

We need to be able to say something like:

template mapIt[T](a: Iterable[T]; x: untyped[it: T])) 
  ## document in the header that we will inject an ``it`` of type ``T`` to ``x``.

We also need something like:

template `:=`(varname: InjectingSymbol[`var`]; value: typed) =
  # InjectingSymbol means that afterwards the identifier passed to `varname` will be in the scope.
  var varname = value

[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.