alias syntax to make every symbol 1st class

[timotheecour]

Symbol aliases

Abstract

This RFC proposes to add more aliasing capabilties to Nim. Every symbol (template, module, const, iterator etc: anything in TSymKind) becomes a 1st class entity, which can be passed to routines (procs, templates, iterators, etc: anything in routineKinds), or used as generic paramter in types. This works even if the symbol is overloaded, or if it's a template/macro (even if all parameters are optional).

In particular, this allows defining 0-cost lambdas and aliases.

See nim-lang/Nim#11992 for the corresponding PR.

Motivation 1: symbol aliasing

• nim doesn't have a way to alias symbols, and the workaround using template foo2(args: varargs[untyped]): untyped = foo(args) falls short in many cases; eg
  • if all parameters are optional, this won't work, see case1
  • this requires different syntax for different symbols and doesn't work for some symbols, see case2
  • it only provides an alternative way to call a routine but doesn't alias the symbol, so for example using introspection (eg to get parameter names) would give different results, see case3

Motivation 2: passing symbols to routines

• nim doesn't allow passing templates or uninstantiated generics (or macros, iterators etc) to routines, so it forces you to either turn the callee into a template/macro, leading to much more complex, hard to debug code code (eg: see zero-functional https://github.com/zero-functional/zero-functional/blob/master/zero_functional.nim, with macros calling macros calling macros...).

Motivation 3: speed benefit

Passing functors via closures is not free, because closure prevents inlining. Instead this RFC allows passing templates directly which is a zero-cost abstraction. eg: see case4.

Motivation 3: lambdas

• this allows defining lambdas, which are more flexible than sugar.=>, and don't incur overhead, see tests/magics/tlambda.nim; eg: case5

Motivation 4: composable iterators

composable iterators, which allows define lazy functional programming primitives (eager toSeq and lazy map/filter/join etc; which can have speed benefit compared to sequtils); the resulting code is quite nice and compact, see tlambda_iterators.nim which uses library lambdaIter that builds on top of lambda; it allows defining primitives that work regardless we're passing a value (@[1,2,3]) or a lazy iterate (eg iota(3))

Motivation 5: this fixes or closes a lot of issues

see a sample here: nim-lang/Nim#11992

alias syntax: alias foo2 = expr

alias foo2 = expr # expr is an expression resolving to a symbol
# eg:
alias echo2 = echo # echo2 is the same symbol as `echo`
echo2() # works
echo2 1, "bar" # works

alias echo2 = system.echo # works with fully qualified names

import strutils
alias toLowerAscii2 = strutils.toLowerAscii # works with overloaded symbols
alias strutils2 = strutils # can alias modules2
var z = 1
alias z2 = z # works with var/let/const

passing alias to a routine / generic parameter

proc fn(a: alias) = discard # fn can be any routine (template etc)
fn(alias echo) # pass symbol `echo` to `fn`
proc fn(a, b: alias) = discard # a, b are bind-many, not bind-once, unlike `seq`; there would be little use for bind-once

• an alias parameter makes a routine implicitly generic
• an alias parameter matches a generic parameter:

proc fn[T](a: T) = discard
fn(12) #ok
fn(alias echo) #ok

alias parameters are resolved early

proc fn(a: alias) =
  # as soon as you refer to symbol `a`, the alias is resolved
  doAssert a is int
  doAssert int is a
fn(alias int)

symbol constraints (not implemented)

proc fn(a: alias[type]) = discard # only match skType
proc fn(a: alias[module]) = discard # only match skModule
proc fn(a: alias[iterator]) = discard # only match skIterator
# more complex examples:
proc fn(a: alias[proc(int)]) = discard
proc fn(a: alias[proc(int): float]) = discard
proc fn[T](a: alias[proc(seq[T])]) = discard

note: this can be achieved without alias[T] via {.enableif.} (nim-lang/Nim#12048)
which is also more flexible:

proc fn(a, b: alias) = discard {.enabelif: isFoo(a, b).}

symbol parameters typed as a symbol type alias parameter (not implemented)

proc fn(t: alias, b: t) = discard
fn(alias int, 12) # type(b) is `t` where `t` is an alias for a type

proc fn(t: alias): t = t.default
doAssert fn(int) == 0 # type(result) is `t` where `t` is an alias for a type

Description: lambda

library solution on top of alias

alias prod = (a,b) ~> a*b # no type needed
alias square = a ~> a*a # side effect safe, unlike template fn(a): untyped = a*a
alias hello = () ~> echo "hello" # can take 0 args and return void

Differences with nim-lang/Nim#11992

currently:

• const foo2 = alias2 foo is used instead of alias foo2 = foo
• fn(alias2 echo) is used instead of fn(alias2 echo)
• a: aliassym is used instead of a: alias

complexity

this introduces a new tyAliasSym type, which has to be dealt with.

Examples

• see tests/magics/tlambda.nim
• see tests/magics/tlambda_iterators.nim

Backward incompatibility

No backward incompatibility is introduced.
In particular, the parser accepts this even if nimHasAliassym is not defined.

when defined nimHasAliassym:
  alias echo2 = echo

snippets referenced in this RFC

when defined case1:
  iterator bar(n = 2): int = yield n
  template bar2(args: varargs[untyped]): untyped = bar(args)
  for i in bar2(3): discard
  for i in bar2(): discard

when defined case2:
  import strutils
  template strutils2: untyped = strutils
  echo strutils2.strip("asdf") # Error: expression 'strutils' has no type 

when defined case3:
  import macros
  proc bar[T](a: T) = a*a
  template bar2(args: varargs[untyped]): untyped = bar(args)
  macro deb(a: typed): untyped = newLit a.getImpl.repr
  echo deb bar
  echo deb bar2 # different from `echo deb bar`

when defined case4:
  func isSorted2*[T, Fun](a: openArray[T], cmp: Fun): bool =
    result = true
    for i in 0..<len(a)-1:
      if not cmp(a[i],a[i+1]):
        return false

  # benchmark code:
  let n = 1_000
  let m = 100000
  var s = newSeq[int](n)
  for i in 0..<n: s[i] = i*2
  benchmarkDisp("isSorted2", m): doAssert isSorted2(s, (a,b)~>a<b)
  benchmarkDisp("isSorted", m): doAssert isSorted(s, cmp)

when defined case5:
  proc mapSum[T, Fun](a: T, fun: Fun): auto =
    result = default elementType(a)
    for ai in a: result += fun(ai)
  doAssert mapSum(@[1,2,3], x~>x*10) == 10 + 20 + 30

[Araq]

Note: Sorry for the deletions but it seemed the best way so that the RFC's author remains Timotheecour.

[Araq]

I think as a next step you should outline the wording we have to add to the manual.

[timotheecour]

@Araq done => nim-lang/Nim#14747

[Araq]

this introduces a new tyAliasSym type, which has to be dealt with.

We already have tyAlias, what's the difference between tyAlias and tyAliasSym?

[planetis-m]

What is proc fn(a: symbol), is it like typed? An implicit generic... Is these two new constructs really needed, can't templates fixed/ improved to provide the same features?

[Araq]

There is considerable overlap with my unwritten RFC "nullary non-overloaded templates should be resolved early and allow for aliasing of the template body". Can we unify aliases and nullary templates?

[timotheecour]

@Araq

We already have tyAlias, what's the difference between tyAlias and tyAliasSym?

• I can only infer tyAlias from reading code since it's undocumented, nor was it documented or explained when introduced in e6c5622aa74c1014b022071d9d525a0e13805246, but I'm fairly certain it's entirely unrelated to tyAliasSym. tyAlias is for type aliases (only created in semTypeClass, maybeAliasType, fixupTypeOf), while tyAliasSym is for symbol aliases. Conflating tyAlias and tyAliasSym would not make sense.
• Furthermore, tyAlias survives codegen, whereas tyAliasSym only exists during semantic phase, since aliases are resolved upon use; so code generators are not aware of it; on a related note, tyAlias is a "leaky" abstraction and many parts of compiler must be aware of it (146 ocurrences), vs only 30 for tyAliasSym

I'd like to rename tyAlias to tyAliasType and tyAliasSym to tyAlias in future work though, but it's low priority.

There is considerable overlap with my unwritten RFC "nullary non-overloaded templates should be resolved early and allow for aliasing of the template body". Can we unify aliases and nullary templates?

hard to comment on something that hasn't been written, please point me to a draft, but from your description I don't see how these could be unified. Nullary templates don't help with passing symbols to routines, in particular wouldn't help with most of the test suite I added in the PR (eg, lambdas ~>, passing un-instantiated generics or iterators/templates to other routines etc).

@B3liever
typed is explained in the manual; alias is explained in nim-lang/Nim#14747; after PR, typed would be a strict superset since it can match arguments that are not symbol aliases; eg: fn(10) would match proc fn[T](a: T) or template fn(a: typed) but not template fn(a: alias); note that typed can't be used as a proc/iterator param (it can only be used as a template/macro param)

Is these two new constructs really needed, can't templates fixed/ improved to provide the same features?

there is no way to pass symbols to routines before this PR. alias declarations (alias a = b) and alias parameters (proc fn(a: alias)) is what allows this. This has little to do with templates.

[Clyybber]

I would prefer to reuse the template mechanism as a means to alias symbols, so looking forwards to Araqs RFC there.
Afaict the other thing that alias enables is passing uninstantiated generics and templates around, but I think this should ideally be solved differently without an entirely new language mechanism (which may work similar to alias internally).
Regarding generics, this could be made to work:

proc a(p: proc) =
  discard p[int]()

proc p[T]() =
  echo "hey"

a(p)

which would enable us to pass uninstantiated generics to other generics (I faintly remember an RFC/issue about this, but can't find it, searching for "lazy generics").
Additionally we could enable this syntax to work:

proc a(p: proc[T](arg: T)) = ...

Regarding templates I think making proc a(t: template) and proc a(t: template()) and so on work should be the solution.

[Varriount]

@Araq

There is considerable overlap with my unwritten RFC "nullary non-overloaded templates should be resolved early and allow for aliasing of the template body". Can we unify aliases and nullary templates?

Would this change semantics such that nullary templates could not be used in places that non-nullary would work (or exhibit different behavior)?

Or to phrase it another way, would nullary templates become a semantic superset of non-nullary templates, or would they diverge in shared behaviors?

[Araq]

Ok, let me phrase it differently: Everything your alias does should be achievable with a nullary template with hopefully only minor additions to nullary templates.

[timotheecour]

@Araq

unwritten RFC "nullary non-overloaded templates should be resolved early and allow for aliasing of the template body". Can we unify aliases and nullary templates?
Ok, let me phrase it differently: Everything your alias does should be achievable with a nullary template with hopefully only minor additions to nullary templates.

I don't see how nullary templates as a replacement for alias/aliassym would work.

I've gone through the trouble to write the implementation for the proposed alias that passes a large test suite (nim-lang/Nim#11992, first working version was 1 year ago), an RFC (this one #232), and a PR to update the manual accordingly (nim-lang/Nim#14747); it's a sound design that solves real problems and doesn't introduce any ambiguities or breaking changes, and yes, it does add a new feature to the language. The change in compiler is relatively small in comparison to the features it offer, in particular it has 0 footprint on backend code, and tyAliasSym appears in only 31 instances (contrast this with tyOut from the recent out PR).

If you still think nullary templates is a viable and preferable alternative, please write an RFC with sufficient details otherwise it's impossible to comment on this alternative.

I'm not even sure what syntax you're suggesting since there's no RFC; is it:

• template echo2 = echo ?
• template echo2: untyped = echo ? (that syntax is more verbose than alias echo2 = echo)
• are there restrictions on the body of the template?
• are there restrictions on pragmas, eg: template echo2: untyped {.foo.} = echo ?
• what about {.dirty.}?
• what about generic params?

Here are just some of the problems with nullary templates:

nullary templates are already very common

eg around 220 definitions just in nim repo itself; any change of meaning would have an large impact.

major breaking change: nullary templates are not resolved early

a lot of code would break under this proposal, eg:

• tableimpl.nim:

template checkIfInitialized() =
  when compiles(defaultInitialSize): (if t.dataLen == 0: initImpl(t, defaultInitialSize))

it'd conflate 2 unrelated concepts

despite appearances, the 2 concepts are unrelated. templates is a substitution mechanism that operates on AST (PNode); alias operates on symbols (PSym).
Both can interoperate to yield useful features such as lambdas (see ~> in lambdas.nim), but conflating those doesn't make sense.

this introduces a weird special case for templates

all those rules would be violated, introducing weird special cases and bugs:

• templates are not resolved early
• their behavior is unchanged when overloads are added (module existing bugs) for unambiguous sigmatches
• templates can be redefined (template a: untyped=1; template a: untyped=2 is legal)

non-overloaded templates rule is fragile

suppose you have: import pkg/foo; template bar: untyped = baz and later foo.nim adds an overload, suddenly bar would change its meaning, leading to CT errors at best, silent behavior change at worst

nullary templates already have a different, incompatible meaning:

• asyncfutures: template fut: untyped = Future[T](future)
• cgen: template onExit() = close(m.ndi, m.config)
• os.nim: template getCommandLine(): untyped = getCommandLineW()

there would be an inherent ambiguity

template foo2 = foo already has a meaning today, so I don't see how you could reconcile it with the new meaning:

when true:
  template foo(x = 1) = echo ("foo", x)
  template foo2 =
    static: echo "in foo2 CT" # currently called each time
    echo "in foo2 RT" # currently called each time
    foo
  foo2 # currently calls echo ("foo", 1)
  foo2() # ditto
  # foo2(2) # Error: type mismatch: got <int literal(2)>

last but not least:

this wouldn't help at all with passing iterators/macros/other symbols to other routines / types

[ghost]

has any decision been made regarding this yet? this looks like a good addition, a PR is already there, and the nullary templates rfc is nowhere to be seen...

[Araq]

Plenty of Nim developers think that there is considerable overlap with template and/or const and we should really figure out their limitations first. Sorry for the delay but we have to be careful with new core language additions.

[timotheecour]

Plenty of Nim developers think that there is considerable overlap with template and/or const

nim-lang/Nim#11992 has the +1's amongst all PR's to date, and I haven't seen any explanation of how it would overlap.

Everything your alias does should be achievable with a nullary template with hopefully only minor additions to nullary templates.

as was already mentioned, template can't be forwarded to a proc, likewise with iterator, macros, un-instantiated generics etc.
The overlap you mention is only for defining aliases, which is a small fraction of what nim-lang/Nim#11992 is about, which is making every symbols first class. D has had this feature from day 1 via alias and it's an essential feature.

You've proposed nullary templates a while ago but there is still no embryo of an RFC so it's impossible to debate on it, but my understanding is it wouldn't help a bit with symbol forwarding, defining lambdas that you can pass to procs, etc.

[nc-x]

Plenty of Nim developers think that there is considerable overlap with template and/or const and we should really figure out their limitations first.

I personally don't think there is much overlap with templates. Just because templates can be used as a "workaround" for alias, does not mean we should go around adding more stuff on top of templates just to increase support for that use case.

I mean I can use macros to do whatever templates do, but I don't do I? So, why should I be using templates to define alias, when there could be a better alternative that is easy to use, is less likely to cause confusion (esp. to newcomers) and most importantly, conveys its intentions well (the keyword 'alias' describes 'creating an alias for a symbol' much better than the keyword 'template').

If there are downsides/annoyances to using templates that are fixed by nullary templates, I am all for it as well. However, I am against complicating templates just because some people want to avoid having a new keyword 'alias'.

In any case, I am not against comparing alias with template to figure out the downsides and upsides, I just don't want this feature to be merged with templates if it increases its complexity.

[Araq]

D has had this feature from day 1 via alias and it's an essential feature.

This is rather meaningless, C# still lacks it and nobody complained. In fact, the programming language theory knows no such
"alias" construct that is required for "lambdas" or "un-instantiated generics".

[metagn]

As overly simple as it sounds, the limitations of nullary templates outlined above could be cleared up with an explicit .alias annotation (#466). Unsure about the degree of overlap though.