1Generics 2======== 3 4implementing generics Go 5------------------------ 6 7The branch generics-v1 is an experiment to add generics to gomacro. 8 9This file contains observations, choices, difficulties and solutions found 10during such work. 11 12Due to the author's personal taste and his familiarity with C++, generics are 13named 'templates' in this document. 14 15### Parser ### 16 17#### Declaring templates #### 18 19Adding a new syntax to declare template types, function and methods is easy: 20it's just a matter of inventing the syntax and choosing a representation in 21terms of `go/ast.Node`s 22 23Current syntax is: 24``` 25template [T1, T2...] type ... 26template [T1, T2...] func ... 27``` 28 29Template type declarations are represented with `*ast.TypeSpec` as usual, 30with the difference that `TypeSpec.Type` now contains 31`&ast.CompositeLit{Type: <type declaration>, Elts: [T1, T2 ...]}` 32 33Template function and method declarations are represented with `*ast.FuncDecl` 34as usual, with the difference that `FuncDecl.Recv.List` now has two elements: 35the first element is nil for functions and non-nil for methods, 36the second element is `&ast.Field{Names: nil, Type: &ast.CompositeLit{Elts: [T1, T2 ...]}}` 37 38#### Using templates #### 39 40The main idea is that template functions and methods will be used mostly 41in the same ways non-template ones, i.e. `Func(args)` and `obj.Method(args)` 42exploiting appropriate type inference (exact inference rules need to be defined). 43 44In some cases, using template functions and methods will need to specify 45the exact template arguments. Template types will need such explicit 46qualification most of (or maybe all) the time. 47 48For example, after a declaration 49``` 50template [T1, T2] type Pair struct { First T1; Second T2 } 51``` 52it is tempting to say that the syntax to specify the template arguments 53(= to qualify the template name) is 54``` 55Pair[int, string] 56``` 57i.e. the template name is immediately followed by '[' and the comma-separated 58list of template arguments. 59 60Alas, such syntax is too ambiguous for current Go parser. Take for example the 61code fragment 62``` 63func Nop(Pair[int, int]) { } 64``` 65By manual inspection, it's clear that `Pair` is a type name, not a parameter 66name. But compare the fragment above with this: 67``` 68func Nop(Pair []int) { } 69``` 70where `Pair` is a parameter name with type `[]int`. 71 72In both cases, the parser will encounter `Pair` followed by `[` and must 73decide how to parse them without further look-ahead. 74 75The current parser algorithm for this case assumes that `Pair` is an 76identifier and that `[` starts a type expression to be parsed. 77 78To avoid breaking lots of existing code, the current parser algorithm for 79this case must be preserved. So we need a different, less ambiguous syntax to 80qualify template names. 81 82One of the suggestions in latest Ian Lance Taylor 83[Type parameters (December 2013)](https://github.com/golang/proposal/blob/master/design/15292/2013-12-type-params.md) 84proposal is "using double square brackets, as in `Vector[[int]]`, or perhaps 85some other character(s)." 86 87The authors' current decision - but it's trivial to change it - is to write 88`Pair#[int, string]` and similarly `Vector#[int]`. The reason is twofold: 89 901. double square brackets look too "magical" 912. the hash character `#` is currently not used in Go syntax, and usually does not have 92 strong connotations in programmers' minds. The alternatives are the other 93 ASCII characters currently not used in Go syntax: `?` `@` `$` `~` 94 * the question mark `?` is better suited for conditionals, as for example 95 the C ternary operator `?:` 96 * the at sign `@` already has several common meanings (at, email...). 97 * the dollar sign `$` seems inappropriate, in the author's opinion, for 98 this usage. 99 * the tilde sign `~` is already used by gomacro for quasiquote and friends. 100 101Implementation choice: `Pair#[int, string]` is represented as 102``` 103&ast.IndexExpr{X: Pair, Index: &ast.CompositeLit{Elts: [T1, T2...]} } 104``` 105The simpler `&ast.CompositeLit{Type: Pair, Elts: [T1, T2...]} }` would suffice 106for the parser, but compiling it is much more ambiguous, since it could be 107interpreted as the composite literal `Pair{T1, T2}` 108 109#### Composite Literals #### 110 111The parser had to be extended to recognize things like `Pair#[T1,T2] {}` 112as a valid composite literal. 113 114In practice, `isTypeName()` and `isLiteralType()` now return true for `*ast.IndexExpr`. 115 116This solution should be better examined to understand whether the increased 117syntax ambiguity is a problem, but an official implementation will surely create 118new ast.Node types to hold template declarations and template uses, bypassing 119this potential problem. 120 121### Declaration ### 122 123The declaration of template types and functions is straightforward. 124 125For each template declaration found, the compiler now collects it in the same 126`map[string]*Bind` used for const, var and func declarations. 127 128Such declarations store in the *Bind their **source code** as an ast.Node, in order to 129retrieve and compile it on-demand when the template type or function needs to be 130instantiated. 131 132This is easy for an interpreter, but more tricky for a compiler: 133since a package A may use a template B.C declared in package B, 134the compiler may need to instantiate B.C while compiling A. 135 136There are at least two solutions: 1371. for each compiled package, store in the compiled archive packagename.a 138 the **source code** of each template, alongside with binary code. 139 140 This may not play well with commercial, binary-only libraries since, 141 with a little effort, the source code of templates could be extracted. 142 1432. for each compiled package, require its source code to be available 144 in order to instantiate its templates. 145 146 This has the same problem as above, only in stronger form: 147 the **full** source code of B must be available when compiling A. 148 149Another question is: where to store the B.C instantiated while compiling A ? 150 151For templates declared in the standard library and instantiated by non-root users, 152$GOROOT may not be writeable, so it should probably be stored in 153$GOPATH/pkg/$GOOS_$GOARCH/path/to/package, using a name like B.somehash.a 154 155### Instantiation ### 156 157Instantiantion is a regular compile, with some careful setup. 158 159Since a template may access global symbols in the scope where it was declared, 160it must be compiled in that **same** scope. Better yet, it can be compiled 161in a new inner scope, that defines the template arguments to use for instantiation. 162 163An example can help to understand the abstract sentence above: 164suppose package B contains 165``` 166package B 167 168const N = 10 169 170template[T] type Array [N]T 171``` 172 173and is later used by package A as 174``` 175package A 176 177import "B" 178 179var arr B.Array#[int] 180``` 181 182the technique described abstractly above means: to compile `B.Array#[int]`, 183pretend that package B contains the following (pseudo-code, it's not valid Go): 184``` 185{ // open new scope 186 187 type T = int // inject the template argument 188 189 // inject the template declaration literally - no replacements needed 190 type Array#[T] [N]T // finds T immediately above, and N in outer scope 191} 192``` 193 194There is a peculiarity in this approach that must be handled carefully: 195`type Array#[T]` should not be taken too literally. It conveys the 196intention, but the exact mechanics are more subtle: 197 1981. the name `Array` is a template type. It must have an associated cache 199 that keeps track of already-instantiated types based on it, otherwise 200 each `Array#[Foo]` will trigger an instantiation (= a compile) even 201 if it exists already. 2022. such cache has the same role as the list of existing (non-template) 203 types, functions, constants and variables: looks up identifiers and 204 resolves them. 2053. Go supports (non-template) recursive functions and types, 206 and we want to also support recursive template functions and types, 207 as for example `template[T] List { First T; Rest *List#[T] }` 208 See the next paragraph for details. 209 210### Recursive templates ### 211 212Let's start with a non-template example for concreteness: 213``` 214type IntList struct { First int; Rest *IntList } 215``` 216Compiling it in Go is conceptually three-step process: 2171. forward-declare `IntList`, i.e. create a new named type `IntList` 218 with no underlying type (i.e. it's incomplete) and add it to the current 219 scope. 2202. compile the underlying type `struct { First int; Rest *IntList }`. 221 It will find the **incomplete** type `IntList` in the current scope, 222 but that's ok because it uses a **pointer** to `IntList`, 223 not an `IntList` - Go, as C/C++/Java and many other languages, 224 allow and can implement pointers to incomplete types because at the 225 assembler level they are all implemented in the same way: a machine word 226 (`void *`, `unsafe.Pointer`, etc.) with pointer semantics. 227 For completeness: also slices, maps, channels and functions signatures 228 of incomplete types are accepted in Go. 2293. complete the forward-declared `IntList` by setting its underlying type to 230 the result of step 2. 231 232Recursive template types and functions can be implemented very similarly: 233instantiating 234``` 235template[T] List struct { First T; Rest *List#[T] } 236``` 237as for example `List#[string]`, is almost the same process: it starts 238with the technique described in the paragraph [Instantiation](#instantiation) 239above: 240``` 241{ // open new scope 242 243 type T = string // inject the template argument 244 245 // inject the template declaration literally - no replacements needed 246 // except for conceptually replacing List -> List#[T] in the declaration 247 // (not in the body) 248 type List#[T] struct { First T; Rest *List#[T] } 249} 250``` 251and it continues with the analogous of the three-step process described above: 2521. forward-declare `List#[string]` i.e. add to the cache of instantiated types 253 a new named type `List#[string]` with no underlying type (i.e. it's 254 incomplete) 2552. compile the underlying type `struct { First T; Rest *List#[T] }` in the scope 256 just prepared above for the instantiation. 257 It will find the **incomplete** type `List#[string]` in the cache of 258 instantiated types, but that's ok because its uses a **pointer** to 259 `List#[string]`, not a `List#[string]`. As we said, pointers to incomplete 260 types are accepted. 2613. complete the forward-declared `List#[string]` by setting its underlying type 262 to the result of step 2. 263 264### Partial and full specialization ### 265 266This is a desirable feature of C++ templates. 267Although not overly difficult to implement, it introduces a lot of complexity: 268C++ templates are Turing-complete because of it. 269 270In extreme summary it means that, in addition to the general declaration of a template, 271one can also declare special cases. 272 273Example 1: given the template function declaration 274``` 275template[T] func nonzero(a, b T) T { if a != 0 { return a }; return b } 276``` 277one can declare the special case "T is a map of something" as: 278``` 279template[K,V] for[map[K]V] func nonzero(a, b map[K]V) map[K]V { if a != nil { return a }; return b } 280``` 281and the special case "T is struct{}" as: 282``` 283template[] for[struct{}] func nonzero(a, b struct{}) struct{} { return struct{}{} } 284``` 285Note that the number of template arguments **can** be different in each specialized declaration. 286 287A specialized declaration with zero template arguments is named "full specialization" 288or "fully specialized"; all other specialized declarations are named "partial 289specialization" or "partially specialized". 290 291The compiler is expected to automatically decide which specialization to use, 292based on the criteria "use the most specialized declaration that is applicable". 293 294In case there is no single "most specialized declaration", the compiler 295is expected to produce a (hopefully descriptive) error. 296 297Implementation note: choosing the "most specialized declaration" requires the 298following steps: 2991. keep a list of candidates, initially containing only the general declaration. 3002. for each specialization, pattern-match it against the code to compile 301 (for example `nonzero#[map[int]string]`). 302 If it does not match, ignore it and repeat step 2. with the next specialization. 303 It it matches, name it "new candidate" and continue to step 3. 3043. compute the types and constants required to match the new candidate against the 305 code to compile. For example, the candidate `template[K,V] for[map[K]V] func nonzero(...) ...` 306 matches the code `nonzero#[map[int]string]` if `K = int` and `V = string` 3074. perform a loop, comparing the new candidate selected at step 2. against each candidate 308 currently in the list. If the new candidate is more is more specialized than a current one, 309 the latter is removed from the candidate list. 3105. add the new candidate to the candidate list, storing also the types and constants 311 computed at step 3. 3126. if there are more specializations, return to step 2. with the next specialization. 313 314The comparison at step 4. "candidate A is more specialized than candidate B" 315can be implemented as: B pattern-matches A, but A does not pattern-match B. 316 317Pattern-matching compares the ast.Node tree structure and the contents 318of each *ast.Ident and *ast.BasicList, but it should also expand type aliases 319and compute the value of constant expressions before comparing them. 320 321It is not yet clear whether it is feasible for pattern-matching to also expand 322template types in case they are type aliases too. 323 324### Turing completeness ### 325 326If one has some familiarity with C++ templates, it is easy to see that 327the partial and full specialization rules described above are Turing complete 328at compile-time, just like C++ templates. 329 330The reason is: 331* partial and full specializations are a compile-time `if` 332* instantiating a template from inside another one is a compile-time `while` 333* compile-time computation on integers can be implemented with normal arithmetics 334* intermediate results can be stored in the number of elements of an array type, 335 and extracted with `len()` 336 337For example, this is a compile-time computation of fibonacci numbers 338using the rules proposed above: 339 340``` 341template[N] type Fib [len((*Fib#[N-1])(nil)) + len((*Fib#[N-2])(nil))] int 342template[] for[1] type Fib [1]int 343template[] for[0] type Fib [0]int 344const Fib10 = len((*Fib#[10])(nil)) 345``` 346arguably, the Go code above is even **less** readable than the already convoluted 347C++ equivalent: 348``` 349template<int N> struct Fib { enum { value = Fib<N-1>::value + Fib<N-1>::value }; }; 350template<> struct Fib<1> { enum { value = 1 }; }; 351template<> struct Fib<0> { enum { value = 0 }; }; 352enum { Fib10 = Fib<10>::value }; 353``` 354 355This seems to present a conundrum: 3561. allow partial template specialization and, as a consequence, compile-time 357 Turing-completeness, with the **extremely** unreadable syntax required to use it 3582. or forbid partial template specialization, preserving readability as much 359 as possible, but severely limiting the usefulness of templates? 360 361If Go adds compile-time Turing-completeness, whatever its syntax, 362it is such an enticing feature that many programmers will certainly use it. 363Some programmers may **heavily** use it, and the result could be something 364resembling the well-known C++ libraries STL and Boost: 365 366professional code, that heavily uses templates, very useful and very used, 367but written in a dialect very different from the basic language (C++ in this case), 368almost unreadable for average programmers skilled mostly on non-template code, 369and difficult to read even for experts. 370 371In my opinion, there is only one solution to the conundrum: 372<b>add another, readable syntax to perform compile-time computation.</b> 373 374As minimum, such syntax would be used in most cases for compile-time 375Turing-completeness **instead** of the extremely unreadable template 376specializations, simply because it has the same features 377(compile-time Turing-completeness) but is more readable. 378 379Ideally, such syntax could also be used to simplify writing complex 380template code. 381 382To give some context, Go is not foreign to compile-time computation: 383`//go:generate` allows to execute arbitrary commands at compile-time, 384and Go code generation tools and techniques are accepted and 385quite in widespread use (at least compared to many other languages). 386 387### Compile-time function evaluation ### 388 389Following the suggestion of the previous chapter, a very simple syntax 390to perform compile-time computation could be `const EXPRESSION`, 391as for example: 392``` 393func fib(n int) int { if n <= 1 { return n }; return fib(n-1)+fib(n-2) } 394const fib30 = const fib(30) 395``` 396This is readable, and the programmer's intention is clear too: 397invoke `fib(30)` and treat the result as a constant - which implies 398`fib(30)` must be invoked at compile time. 399 400Question: which functions can be invoked at compile time? 401Answer: a minimal set could be: all functions in current package, 402provided they do not use imported packages, print() or println(), 403or invoke other functions that (transitively) use them. 404 405Question: global variables should be accessible by functions 406invoked at compile time? 407Answer: tentatively no, because if such variables are modified at 408compile-time, their value at program startup becomes difficult to 409define unambiguously, and difficult to store in the compiled code. 410 411So, a tentative definition of whether a function can be invoked 412at compile time is: 4131. is defined in the current package (so source code 414 is available in order to check points 1. and 2. below) 4152. does not use global variables, imported packages, print() 416 or println() 4173. calls only functions that (transitively) respect 1. and 2. 4184. as a consequence, calls to closures are allowed, provided 419 that the function creating the closure respects 1, 2 and 3. 420 421An alternative, wider definition could be: only pure functions 422can be invoked at compile time. A function is pure if: 4231. does not use global variables, print() or println(), or assembler 4242. either does not call other functions, or only calls pure functions 425As a special case, all builtin functions except `print()` and `println()` 426are considered pure. 427This alternative definition allows calling function in other 428packages at compile-time, provided they are pure. 429Thus it requires storing in compiled packages a flag for each function, 430indicating whether it is pure or not. 431