Trivium: A Framework For Symbolic Metaprogramming in C++

Metaprogrammed code in C++ can be as simple, clear, reusable, modular and configurable as code that is written in a functional language like Lisp or Haskell.

Template metaprogramming (TMP) code tends to be unfriendly to humans. The code is generally neither easy to read nor easy to write.

The Trivium framework gives a solution to this problem by organising TMP indirectly by the means of Trivium Lisp, a symbolic domain specific language (DSL) for metaprogramming. Metaprograms are not encoded directly in C++, but as symbolic expressions in Trivium-Lisp.

1. 1
Trivium: A Framework For Symbolic
Metaprogramming in C++
https://github.com/andreas-maniotis/trivium

2. 2
Andreas Milton Maniotis
Mathematician and Computer Scientist
Freelance C++-Developer
[email protected]

3. 3

4. 4
Goal Of The Trivium Project
Make metaprogrammed code in C++ can as simple,
clear, reusable, modular and configurable as code that
is written in a functional language like Lisp or Haskell.
Trivium shall serve as a metaprogramming tool for
everyone, not just the small group of template
metaprogramming experts.

5. 5
Outline
●What is Metaprogramming?
●Template Metaprogramming
●Symbolic Programming
●Trivium Lisp ( a symbolic DSL for Template Metaprogramming)
●The Closure (connecting C++ and Trivium Lisp)
●Symbolic Representation of the C++-Type System
●A Full Metaprogramming Example in Trivium
●What next?
●Conclusion

6. 6
What is Metaprogramming?
The Classical Perspective on Computation:
A fixed program p from a programming language
L acts on varying data d from a set of possible
inputs in a set D:
[[p]]: D → D, [[p]](din) = dout

7. 7
The Metaprogramming Perspective
L ⊆ D : Programs are data.
Consequence: A program p may compute a
new program [[p]](q)∈ L from input q . This
program may then act on other data x∈ D :
result = [[ [[p]](q) ]](x).

8. 8
Metaprogramming in Real Life
Example: Printing with format strings.
printf: Convenient but not type-safe
std::print (C++23): a type-safe version of printf.

9. 9
std::print
std::print("{2} {1}{0}!\n", 23, "C++", "Hello");
(1) format string --generates at compile-time-- >
(2) print_function –-acts on runtime-data-- >
(3) side-effect

The format string is data for a metaprogram, which is executed at
compile-time to generate a concrete function for printing.

10. 10
Problem: Metaprograms are not
cleanly representable in C++!
In the abstract introduction we assumed the
simplest embedding of programs in to data:
L ⊂ D
Such an embedding does not exist in C++.

11. 11
Template Metaprogramming
Metaprogramming in C++ is carried out through the template mechanism and thus called
“template metaprogramming” (TMP).
TMP accidentally discovered. It is not a planned feature of the language. Hence TMP is
less supported than rather tolerated by the language,
notwithstanding that tremendeous efforts to improve the support for metaprogramming
have been made a posteriori.
TMP-code tends to be unfriendly to humans. The code is generally neither easy to read nor
easy to write.

12. 12
The Principle Thought Behind
Trivium
Simplify metaprogrammed code through indirection with the help of three components:
(a) a symbolic domain-specific programming language (DSL) for metaprogramming;
(b) a symbolic representation of the C++ type-system;
(c) a closure-mechanism that is capable of connecting the DSL with symbolically represented C++-types.
In the same manner as high-level programming languages provide a layer of abstraction on assembly
language, Trvium shall provide a layer of abstraction to template metaprograms.
A note on the name: Trivium means the junction of three roads in Latin. The three roads are the DSL, the
symbolic representation, and the closure

13. 13
Symbolic Programming
Origin: Lisp
“Recursive Functions of Symbolic Expressions
and Their Computation by Machine”
Communications of the ACM, April 1960

14. 14
Symbolic Expressions
A symbolic expression with symbolic atoms in a set S is a finite tree, whose leaf nodes are labelled with elements from S.
Symbolic expressions are written as nested lists.
Example:
.
/ | \
(x ( y z ( a b ) ) x ) x . x
/ | \
y z .
/ \
a b

15. 15
Symbolic Programming Languages
Symbolic Expressions are the syntactic building blocks of Lisp.
More generally:
A symbolic programming language is a programming language,
whose programs denote transformations on symbolic expressions.

16. 16
Homoiconicity
A symbolic programming language is called homoiconic, when its semantics is a partial map of the form
Eval: Expr ---> Expr,
where Expr is the set of symbolic expressions over symbolic atoms in a fixed set X.
Consider q := Eval[ (p xs... )]:
In (p xs…) p can be considered as a program, the terms xs… can be considered as input values, and q
is the output of p, run on xs.. .. .
All items have the same form: They are symbolic expressions.

17. 17
Trivium Lisp
Trivium Lisp is a homoiconic symbolic
language. It is a DSL for template
metaprogramming.

18. 18
Symbolic Atoms of Trivium Lisp
1. Keywords
apply and C++ cons drop_first eval eq first if irreducible not or quote requires
symbolic xor true false == != < <= > >= + - * / %
2. C++-types
3. Identifiers (ascii-stsrings that denote variables)
4. The empty list ();
5. A symbol Y*, which we shall call the "recursion symbol" that helps implementing recursive functions.

19. 19
Representations of Trivium Lisp
Expressions in C++
template< typename… Xs > struct s {}; // represents lists ( xs… )
template< char… Identifier > using text = ...; // represents identifiers
struct K; // represent combinatory logic entities...
struct S; // … needed to implement functions
struct Y; // a type needed to implement recursion

20. 20
Abstract and Concrete Syntax
We have presented symbolic expressions as abstract
syntax-trees, that is, we have abstracted away questions of
their representations as text.
The framework contains a class template s_expr, which
takes a compile-time string as its non-type parameter and
parses it. It returns a representation of the string as an
abstract symbolic expression.

21. 21
Example of s_expr
s_expr<”(abc (d e f))”>
evaluates to the C++-representation T of
(abc (d e f)), which is the type
T = s< text<’a’,’b’,’c’>, s< text<’d’,’e’,’f’> > >

22. 22
Functions as Symbolic Expressions
Combinatory Logic:
S = ( λxyz. xz (yz)) and K = ( λxy. x) can be used to give a semantically
equivalent expression to every other λ-expression.
Combinatory logic can be viewed as a variable-free model of computable functions.
Example: The identity function id = (λ x. x) can be described by the
expresssion
j = S K K : j t = S K K t = K t (K t) = t.

23. 23
Elimination of Function Variables in
Symbolic Expressions
We can extend symbolic expressions to contain the expressions
f := [x]p := ( x.p)
λ
.
●They shall mean an expression, such that the semantic meaning
of (ft) becomes “replace x with t in p and then evaluate the
expression that originates form the replacement”. We write
λ-Εxpr for this extension of Expr.

24. 24
Retracting λ-Expressions
When S = (λxyz. xz(yz)) and K = (λxy.x) are
contained in the symbolic atoms, then we can replace
every expression p in λ-Expr by a semantically
equivalent expression p
∗
in Expr.
This can be carried out by an algorithm in linear time.
Example: For p = ( λxyz. xz(yz)) we can pick p
∗

= S (KS) K .

25. 25
Notation for λ-expressions
In Trivium Lisp we write [x]f for the expression (λx.f) . Furthermore,
we let
[x1 ... xn]f := [x1][x2]...[xn]f .
Real-world example in Trivium-Lisp:
using T = lt::s_expr<”[x y]( / y x )”>;
The type T contains the metaprogram: “Divide the second input
variable by the first input variable”.

26. 26
Syntactic Sugar is Necessary
λ-expressions are mere syntactical sugar in
Trivium Lisp. But they are an indispensable
sweetener, because without them, the life of a
Trivium Lisp programmer would become
semantically “bitter” to such an extent that no
human programmer would use it.

27. 27
Some Trivium Lisp Examples
●The Factorial map
●Nested Definitions
●Stein’s gcd

28. 28

29. 29

30. 30

31. 31
A closure Mechanism for the
Connection of C++ and Trivium Lisp
The closure is realized with the help of a compile-time dictionary
template< typename... > struct map;
An instantiation lt::map< Entry... > must have the following properties:
1. There are types Entry::key and Entry::value for every parameter Entry
2. The list ( Entry::key... ) has no duplicates.

32. 32
Symbol Lookup
Eval[ ( map<Entry...> p )] = typename E::value
if and only if
● X = Eval[p] is defined;
● X is a C++ type;
● There is a (necessarily unique) parameter E in the parameter pack
Entry... such that E::key coincides with X.

33. 33
The Closure by Example
using T = s_expr< “(a ( b 2))”
, map{ assign<”b”, double> }
>;
evaluates to a C++-representation of the abstract symbolic expression
(a ( double 2)),
which is an alias of the type
s< text<’a’>, s< double, value<2> > >;
(The C++-type double is printed in italics).

34. 34
A Full Metaprogramming Example
TASK:
We have a class template called my_alloc and
that we want to replace every occurrence of
std::allocator by my_alloc in an arbitrary type X.

35. 35
template< typename Type
, template< typename > class Old_Alloc
, template< typename > class New_Alloc
, auto closure =
map{ lt::assign< "from"
, lt::class_template< Old_Alloc > >
, lt::assign< "to"
, lt::class_template< New_Alloc > >
, lt::assign< "term"
, Type >}
>
using replace = … (next slide)

36. 36
using replace =
lt::eval< R"({
( def subst [ from to term ]
( if ( eq term from )
target
( if ( irreducible term )
term
( cons ( subst from to (first term) )
( subst from to (drop_first term) )
)
)
)
(@'C++ ( subst ( @'Symbolic @'term )
( @'Symbolic @'from )
( @'Symbolic @'to ) ) )
})"
, closure // connect type parameters to the metaprogram
>;

37. 37
For using T = std::vector<int> (X::*)(double, std::vector<double>) &&
we witness
replace< T, std::allocator, my_alloc > :=:
std::vector<int, my_alloc<int>> (X::*)(
double, std::vector<double,
my_alloc<double>) &&.
( :=: denotes the equality of types here).

38. 38
The Role of @’Symbolic and @’C++
(@’Symbolic X) instructs the interpreter to create
a symbolic representation of a C++-type X.
(@’C++ x) instructs the interpreter to transform a
symbolically represented type x into the C++-type
that it represents.

39. 39
A DSL for Symbolic Type
Representation
Trivium contains a DSL for symbolic
representations of C++ types (accessed with
@’Symbolic and @’C++).

40. 40
Decompositions of C++-Types
●Any type T that is not identical with std::decay_t<T>
decomposes into subtypes
●Functions decompose into subtypes with further
decompositions of the function arguments and the return
type
●noexcept specifications cv-qualifier, member functions
qualified with &, &&, const, const volatile etc have these
qualifiers represented.

41. 41
●Types of the form W (X::*) decompose.
●Class templates of the form
template< typename… Xs > class F
decompose, with the parameters accessible in
the decomposition.

42. 42
Limitations of The Symbolic Type
Representation
Class Templates with non-type parameters and with template template
parameters cannot be decomposed automatically. (This may change with
C++26(?))
Examples: template< int x > struct f;
template< template< typename… > class > struct z;
Instantiations of these types will be treated as atomics unless hand-
crafted code is added for a decomposition. (Some improvements are
under construction for support of hand-crafted code).

43. 43
Complete Separation of
Metaprogramming And C++
Metaprogramming is carried out in Trivium Lisp and completely
separated from C++
Consequence: Metaprogramming libraries are simple to establish and
easy to use, because they are merely libraries in a high-level
homoiconic programming language.
(No details of the template mechanism, sfinae, instantiation rules,
boxing etc needed).

44. 44
When To Use Trivium
●Complex Scenarios like Parsers for DSLs
●Metaprograms that have a complex algorithmic
component

45. 45
When Not To Use Trivium
●Simple situations when 1-2 lines of
contemporary C++ are not beautiful, but self-
explaining
●Existing TMP code is known to work fine. Then
this code can be used inside Trivium by binding
it to a symbol in a map. (Do not reinvent the
wheel!)

46. 46
What Next?
●Minor adjustments and simplifications in the
parser and the Trivium Lisp interpreter
●The provision of a complete Trivium Lisp library
containing higher-order functions and the
comon algorithms (folds, map-accumulate, sort
etc)

47. 47
What Next?
Addition of a command defined to the interpreter
with the intended semantics:
Eval[ (defined expr) ] = true (false) when the
expression Eval[expr] is a symbol that is (not)
defined
Eval[ (defined expr) ] undefined if Eval[expr] is not
defined.

48. 48
What Next?
●Provide pool of complex and simple examples,
where higher-order Trivium Lisp functions are
used.
●Extend the documentation. Currently only the
exact syntax and semantics of Trivium Lisp are
specified (approximately 25 pages, most of them
unneeded in daily work).

49. 49
Conclusion
●We have proved that metaprogramming can be
clean an simple in C++ if one makes the effort to
use and indirection via a DSL.
●We have given a framework that can deal with
complex metaprogramming tasks elegantly once
the necessary infrastructure is in place (Trivium
Lisp library functions and documentation).

50. 50
●Non-Intrusiveness: Trivium can cooperate with
existing TMP-code with the help of closures
●No Dependence on other libraries. (A stand-
alone header-only library that can be used in an
embedded context).

51. 51
Advantages that are “imported”
from Lisp / Haskell:
0) code simplicity
1) Reusable code
2) Readability (although some people hate Lisp)
3) Good maintainability

52. 52
Trivium Lisp Metaprograms are simpler to read,
to understand and to maintain.
They have a higher-level of abstraction and
fewer semantic and syntactic “surprises” (like
unexpected template instantiations etc), because
the DSL Trivium Lisp was planned for
metaprogramming.