Generic and metaprogramming models: Go, Rust, Swift, D and others

In some areas of programming, it’s normal to want to write a data structure or algorithm that can work with elements of different types. For example, a list of generics or a sorting algorithm that only needs a comparison function. In various languages, various ways of solving this problem are offered: from simply pointing out the appropriate common functions (C, Go) to programmers to such powerful generic systems that they become Turing complete ( Rust , C ++ ). In this article I will talk about generic systems from different languages ​​and their implementation. I'll start by solving the problem in languages ​​without a similar system (like C), and then I will show how the gradual addition of extensions leads to systems from other languages.

I find generics to be an interesting option because they are a simple special case of the general metaprogramming task: writing programs that can generate classes of other programs. As a proof, I will show how three different and completely general metaprogramming methods can be considered multidirectional extensions in the space of generic systems: dynamic languages ​​like Python, procedural macro systems like Template Haskel, and phased compilation like Zig and Terra .

Overview

I drew a block diagram of all the systems described in the article so that you can present its contents and how these systems are interconnected:


')

Main ideas

Suppose we are writing in a language without generic systems, and we want to make a generic stack data structure data structure that works with data of any type. The problem is that each function and type definition will only work with data of the same size and copied in one way, and generally work similarly.

There are two ways to get around this: either make sure that all data types act in the same way in our structure, or make many copies of the data structure with minor changes to work correctly with each data type. These ideas formed the basis of two large groups of solutions with generics: boxing and monomorphization.

Packaging means putting everything in a row into unified “boxes” that work the same way. This is usually done like this: the data is put in a heap, and the pointers to it are placed in the data structure. You can make pointers to all types that will work the same way, so the same code will work with data of any type! However, this leads to increased memory consumption, dynamic search, and cache misses. In C, this means that your data structure stores void* pointers and simply caches data to and from void* (if the data is not on the heap, it places them there).

Monomorphization means copying code repeatedly for the different types of data that we want to store. Then each code instance can directly use the size and data methods that it works with without dynamic search. With this approach, the code runs the fastest, but its size and compilation time increase, because we repeatedly compile the same code with minor changes. In C, this corresponds to the definition of the entire data structure as a macro , followed by its invocation for each data type.

In general, when compiling, the code compiles faster, but its performance may deteriorate during execution, while during monomorphization we generate fast code, but it takes more time to compile and optimize all instances of the code. Another difference is that when packaging extensions allow you to make more dynamic behavior of the executable code, and monomorphization allows you to more flexibly separate different instances of the generic code. It is also worth noting that in some large programs, the benefits of monomorphization can be offset by misses in the cache of additional instructions from the generated code.

Each of the described schemes for working with generics can be expanded in different directions, if you need more features or security, and the authors of various languages ​​have come up with very interesting solutions. For example, both approaches can be used in Rust and C #!

Packaging

Let's start with an example of basic packaging in Go:

 type Stack struct { values []interface{} } func (this *Stack) Push(value interface{}) { this.values = append(this.values, value) } func (this *Stack) Pop() interface{} { x := this.values[len(this.values)-1] this.values = this.values[:len(this.values)-1] return x } 

Also, packaging is used in C ( void* ), Go ( interface{} ), pre-generic Java ( Object ) and pre-generic Objective-C ( id ).

Packed Generics with Mashing Types

The main packaging method has disadvantages:

• Depending on the language, we often have to cast values ​​to or from the correct type each time we read or write to the data structure.
  
• Nothing prevents us from putting elements of different types into the structure, which can provoke bugs that look like crashes during code execution.
  

Both problems can be solved by adding generic types of functionality to the system, while using the main packaging method in the same way as before during code execution. This approach is often called type erasure, because types in the generic system are “overwritten” and become one type under the hood (like Object ).

Java and Objective-C started with the usual packaging, and later acquired language tools for generics with type mashing, for the sake of compatibility, using the same collection types as before, but with the optional parameters of generic types. Consider a Wikipedia example about generics in Java :

 List v = new ArrayList(); v.add("test"); // A String that cannot be cast to an Integer Integer i = (Integer)v.get(0); // Run time error List<String> v = new ArrayList<String>(); v.add("test"); Integer i = v.get(0); // (type error) compilation-time error 

Derived Packaged Generics with Unified Performance

OCaml further develops the idea of ​​a unified view. There are no primitive types that need additional packaging placement (like an int must turn into Integer to get into an ArrayList in Java), because everything is already packed or represented by an integer value the size of a pointer, that is, everything fits into one machine word. But when the garbage collector looks at the data stored in generic structures, it needs to distinguish pointers from numbers, so numbers are marked with a single bit, placed where correctly aligned pointers do not have one bit, leaving ranges of only 31 or 63 bits.

OCaml also has a type inference system, so you can write a function and the compiler will output the most suitable generic type if you do not annotate it, and so the functions will look like it's a dynamically typed language:

 let first (head :: tail) = head (* inferred type: 'a list -> 'a *) 

The given type can be called “a function from the list of elements of type 'a into something with type 'a ”. This means that the return type will be the same as the list type, and it can be any type.

Interfaces

Another limitation of conventional packaging is that packaged types are completely opaque. This is not a problem for data structures like a stack, but tools like sorting generic functions need additional features, such as type-specific comparison functions. There are many ways to implement this in runtime and reflect in the language, technically these are different directions, and you can implement the same language with several similar approaches . However, the features of different languages ​​affect their implementation, and only then extensions enhance the strengths of the selected implementations. This means that there are two families of languages ​​based on different approaches to runtime: virtual method tables (vtables) and dictionary transfer.

Interface Method Tables

If we want to provide type-specific functions, adhering to the packaging strategy for the sake of unified work with everything, then it is enough to have a unified way to find similar functions that we need to get from the object. This approach is called “virtual method tables” (vtables, virtual method tables), although no one uses the full name. It is implemented as follows: at a zero offset in each generic structure object, there is a pointer to a table of function pointers with a consistent circuit. In these tables, the generic code looks for pointers to type-specific functions by indexing specific pointers at fixed offsets.

This is how interface types are implemented in Go and dyn trait objects in Rust. When you cast a type to an interface type of what it implements, a wrapper is created for the interface that contains a pointer to the source object and a pointer to vtable of type-specific functions. But this requires an additional level of indirect addressing of pointers and another scheme. Therefore, sorting in Go uses the interface for the container with the Swap method , and does not take the slice of the Comparable interface, because this would require placing in memory a completely new slice of interface types that would be sorted instead of the original slice!

Object oriented programming

OOP is a language property that makes good use of the capabilities of virtual type tables. Instead of separate interface objects with vtables, OOP languages ​​like Java simply insert a pointer to a table of virtual types at the beginning of each object. Java-like languages ​​have an inheritance system and interfaces that can be fully implemented using these virtual type object tables.

In addition to providing additional features, embedding vtable in each object solves the problem of the need to construct new interface types with indirect addressing (indirection). Unlike Go, in Java , the sort function can apply the Comparable interface to the types that it implements.

Reflection

If you have tables of virtual types, then it will not be difficult for you to force the compiler to generate tables of other types of information, for example, names of fields, types and locations. This will allow access to all data of this type with the help of a code that can view all data of any other types. This behavior can be used to add “reflection” to the language, which allows serialization and beautiful display of arbitrary types. Reflection, as an extension of the packaging paradigm, has a drawback: for it, only one copy of the code is enough, but you need to perform many dynamic searches, which reduces the speed of serialization.

Languages ​​that use reflection for serialization and other functions: Java, C # and Go.

Dynamically typed languages

Reflection is a very powerful tool that allows you to solve a bunch of different metaprogramming tasks. But it does not allow you to create new types or edit information about the types of existing values. If we add this feature and make the data access and modification syntaxes use reflection by default, we get dynamically typed languages! The incredible flexibility of metaprogramming in languages ​​like Python and Ruby has arisen thanks to the effective, powerful reflection systems that are used to solve any problems.

You can say: “But dynamic languages ​​do not work like that, they just implement everything using hash tables!” Hash tables are just a good data structure for creating editable tables with type information. In addition, some interpreters, such as CPython, work this way. In a high-performance JIT, say V8, there are a lot of virtual type tables and reflection information. In V8, hidden classes (vtables and reflection information) and the structure of objects are similar to what you can see in the Java VM, with the ability to replace objects with new virtual type tables at runtime. This is not a coincidence, because there are no coincidences: the creator of V8 used to work on high-performance Java VM .

Dictionary Transfer

Another way to implement dynamic interfaces is to transfer a table with the required function pointers to the generic function that needs them. This is somewhat similar to constructing Go-shaped interface objects at the place of call, only in our case the table is passed as a hidden argument, and not packed into a bundle as one of the existing arguments.

This approach is used in type classes in Haskell , although GHC allows you to perform some kind of monomorphization using inlining and specialization. OCaml uses dictionary transfer with an explicit argument in the form of first-class modules , but it has already been proposed to add the ability to make the parameter implicit .

Witness tables in Swift

The Swift authors applied an interesting solution: transferring the dictionary, as well as putting data on the type sizes and how to move, copy and release them into the table, allows you to provide all the necessary information for unified work with any types without packing them. Thus, Swift can implement generics without monomorphization and placement in memory in a unified representation of all entities! Yes, you have to pay for dynamic searches, as is characteristic of the entire family that uses packaging, but resources for memory, memory consumption and cache inconsistency are saved. Using the functions annotated as @inlinable , the Swift compiler is also able to specialize (monomorphize) and inline generics inside a module or between modules to avoid the mentioned expenses. Probably a heuristic evaluation of the effect on the code size is used.

It also explains how Swift can implement ABI stability , while still allowing you to add and redistribute fields in the structure, although the authors provide the @frozen attribute to refuse dynamic searches for better performance.

Intensional Type Analysis

There is another way to implement interfaces for packaged types. We add a type identifier to a certain part of the object, following the example of a pointer to vtable, and then generate functions for each interface method that has a large switch expression for all types that implement this method, and pass it to the correct type-specific method.

I don’t warn against using languages ​​that use this approach, but C ++ compilers and Java virtual machines act in a similar way, when they use profile-based optimization to find out that a certain place of calling generics mostly works with objects of certain types. Compilers and VMs replace call locations with checks for each ordinary type, and then statically dispatch these types, as a fallback, using regular dynamic dispatch. Therefore, the branch prediction algorithm can predict which branch the code will go on and continue to dispatch instructions using static calls.

Monomorphization

This is an alternative to packaging. With monomorphization, we need to find a way to generate multiple versions of the code for each type that we want to use. Compilers have several presentation phases through which code passes, and, theoretically, can be copied to any of these stages.

Source code generation

The easiest way to monomorphize is to copy at the first presentation stage: copy the source code! Then the compiler does not even have to support generics, and this is sometimes done by users of the C and Go languages, in whose compilers there is no such support.

In C, you can use a preprocessor and define the data structure in a macro or header by repeatedly inserting it with different #define . Go has scripts like genny that make code generation easier.

The disadvantage of duplicating the source code is that, depending on the language, it may be necessary to deal with numerous problems and edge cases, moreover, the compiler parses and checks types for many times for virtually the same code. Again, depending on the language and tools, these generics of methods can be difficult to write and use, as if inside a C-macro each line ends with a backslash and all types and names of functions must be manually glued into their identifiers to avoid collisions.

String mixins in D

However, code generation has its advantages, such as the fact that you can generate code using a full-fledged programming language, as well as use a view familiar to users.

Some languages ​​in which generics are implemented differently also allow code to be generated for more general metaprogramming cases not considered in their generic systems, for example, for serialization. The most understandable example is string mixins in D , which allow compiling D-code in the form of string values ​​in the middle of compilation, using all the features of the language.

Rust procedural macros

A similar example, only with representation in the compiler at only one stage. Rust procedural macros use token streams as input and output, providing utilities for converting these streams to string and vice versa. The advantage of this approach is that token streams can store location information from source code. The code written by the user, the macro can be inserted as tokens directly from the input to the weekend. And if this code leads to a compilation error in the output of the macos, the compiler will display a message and accurately point to the file, line and column of the broken part of the code. But if the macro generates the broken code, then the error message will indicate a macro call. For example, if you use a macro that wraps a function in logging calls and makes a mistake in implementing a wrapped function, then the error message will point directly to the error in the file, and not to the code generated by the macro.

Syntax Tree Macros

Some languages ​​go even further and offer tools for using and creating different types of abstract syntax trees in macros (Abstract Syntax Tree, AST). Examples include Template Haskell , Nim macros , OCaml PPX, and almost all Lisp .

The disadvantage of AST macros is that you don’t want to force users to learn a bunch of functions to build AST types, as well as basic languages. In the Lisp family of languages, this is solved with the help of a strong simplification and maximum correspondence between the syntax and structure of AST, however, creating structures is not always easy.

Thus, in all the languages ​​I mentioned, there is one way or another primitive "quote" to which you give a piece of code in the language, and that returns a syntax tree. These primitives can merge the values ​​of the syntax tree using the similarity of string interpolation. Here is an example on Template Haskell:

 -- using AST construction functions genFn :: Name -> Q Exp genFn f = do x <- newName "x" lamE [varP x] (appE (varE f) (varE x)) -- using quotation with $() for splicing genFn' :: Name -> Q Exp genFn' f = [| \x -> $(varE f) x |] 

, , , . . , PPX OCaml / , . Rust , parsing quotation , , . Rust , , !

Patterns

— . ++ D , « ». , , , , .

 template <class T> T myMax(T a, T b) { return (a>b?a:b); } template <class T> struct Pair { T values[2]; }; int main() { myMax(5, 6); Pair<int> p { {5,6} }; // This would give us a compile error inside myMax // about Pair being an invalid operand to `>`: // myMax(p, p); } 

, , . , , . D , , : , , . D; if ( ! ):

 // We're going to use the isNumeric function in std.traits import std.traits; // The `if` is optional (without it you'll get an error inside like C++) // The `if` is also included in docs and participates in overloading! T myMax(T)(T a, T b) if(isNumeric!T) { return (a>b?a:b); } struct Pair(T) { T[2] values; } void main() { myMax(5, 6); Pair!int p = {[5,6]}; // This would give a compile error saying that `(Pair!int, Pair!int)` // doesn't match the available instance `myMax(T a, T b) if(isNumeric!T)`: // myMax(p, p); } 

C++20 «» , , .

D , (compile time function evaluation) static if , , , , - runtime-. , , , ++ , .

, « ». , Zig:

 fn Stack(comptime T: type) type { return struct { items: []T, len: usize, const Self = @This(); pub fn push(self: Self, item: T) { // ... } }; } 

Zig , , comptime . Terra , . Terra — Lua, - , Lua API , quoting splicing:

 function MakeStack(T) local struct Stack { items : &T; -- &T is a pointer to T len : int; } terra Stack:push(item : T) -- ... end return Stack end 

Terra - (domain specific) , Java Go . Terra runtime , .

Rust

, . , , ++, . , , , , . , . Rust, — Swift Haskell.

Rust « » (trait bounds). Trait — , , . Rust , - , , , . - Rust . , -.

 fn my_max<T: PartialOrd>(a: T, b: T) -> T { if a > b { a } else { b } } struct Pair<T> { values: [T; 2], } fn main() { my_max(5,6); let p: Pair<i32> = Pair { values: [5,6] }; // Would give a compile error saying that // PartialOrd is not implemented for Pair<i32>: // my_max(p,p); } 

, . Rust . Rust 2018 , v: &impl SomeTrait , v: &dyn SomeTrait . GHC Swift Haskell , .

— , . , (placeholders) -, , . memcpy , ! , . . JIT, , .

, , , , , , ! , , , . , , .