Lessons learned while coding my first functional type system in constexpr C++ - Daniel Nikpayuk

[00:00:09]Okay. [clears throat] So, my name is Daniel Nikki. Uh, my talk is lessons learned while coding my first functional type system in context for C++. Uh, before I start, I just want to say um I'm actually going to go through a lot of context or content, so I'm going to read very quickly. uh think of it more like a survey. I don't expect you to follow absolutely everything but if you have questions at the end or you know come see me after or I can review it later.

[00:00:42]Uh okay so uh outline for my talk uh there are six parts. So about myself, about this talk, template metaroming, uh context programming, uh my functional type system, and lessons learned.

[00:00:59]So uh about myself, uh who am I? I'm a self-taught coder. I've been programming in C++ since 2005. Uh I don't currently work in the tech industry. I have a bachelor with arts majoring in mathematics, minoring in economics. Uh I'm an in person specifically Inu from Canada's western Arctic and devoted to the continued renewal of my field's language and culture. So why C++? Uh it is a life goal of mine to build a programming language for multimedia production.

[00:01:32]I hope to offer said language as an option for uh telling and retelling my people's stories traditional and new.

[00:01:39]uh such a language will generally require system level performance and so C++ is a good fit for writing its first compiler.

[00:01:48]Okay, about this talk uh what is this talk about? Uh as per the title is primarily about functional type systems and conext for C++.

[00:02:00]Uh so let's start with functional type systems. A brain on terms is often a good idea. So I will say for the purpose of this talk that a functional type system is one which is built on top of the untyped lambda calculus. Uh the types of these systems include atomics such as booleans, characters and integers.

[00:02:19]They also include compound types such as products, co-products and lists. Uh beyond this it is worth noting that in practice the untyped lambda calculus can can in fact be equipped with alternative or alternate theoretical type systems.

[00:02:35]Uh these theoretical type systems are related to each other and those relations are encoded into what's called the lambda cube.

[00:02:45][clears throat] So in practice uh such type systems are built on top of list style programming languages which resonate well with the lambda calculus.

[00:02:54]A type system when implemented can be thought of as a recordkeeping system. In particular though it is not only meant to hold types it is expected to hold values of those types as well. The difference between theory and practice here uh is that real world type systems come with real world constraints.

[00:03:13]Uh in terms of my type system, uh it extends the core types by further including comparison types such as the identity type as well as logical types such as dependent products and dependent pairs.

[00:03:26]Uh I should mention my functional type system has a few additional constraints as well. Uh some which might be unique to it.

[00:03:36]In particular uh is required to be serializable.

[00:03:39]Uh this means as a record keeping system it can be transmitted across mediums of technology. Uh in effect it means it can be saved and reloaded for later use.

[00:03:50]Furthermore the internal representation of function values is required to be a bite code uh in the style of assembly program.

[00:04:00]The bite code representation itself has an additional requirement. Uh its instructions can only request memory from the stack. uh cannot allocate from the heap.

[00:04:11]If these constraints seem arbitrary, uh they're not. Uh we'll go into greater detail uh as to why in the following sections.

[00:04:20]Uh so this brings us to conext for C++.

[00:04:23]Uh rather than starting from there though, is more beneficial for us to instead discuss compile time programming more broadly. Uh in which context for C++ is only one part that makes up a greater hole.

[00:04:35]to continue. Then uh if we were to observe the evolution of programming languages, it could be said that once types were introduced uh to a given language, they then gave us the option to translate programs of that language into two parts. First are those parts that are runtime invariant and so are known completely at compile time. Second are those parts uh that can only be known during runtime execution.

[00:05:02]Given this uh once types are introduced into a programming language uh they allow us to distinguish between time scopes in particular between compile time and runtime.

[00:05:14]Relative to this talk any program evaluation which manipulates runtime invariant data as input and returns runtime invariant data as output is known as compile time programming.

[00:05:26]So this includes static types uh which are known completely at compile time.

[00:05:30]With that said, uh modern languages such as C++ take this further by allowing for the manipulation of runtime invariant value data as well.

[00:05:40]Okay, so two examples are as follows.

[00:05:42]The first is an int x uh we assign it the value five. uh we annotated con expert and then uh within a strct we have a uh unsigned array length three uh and we market constexer and static.

[00:06:02]So uh that's it in terms of constexer C++ for now. So to end this section, I would like to add that this talk is also about design, especially broader ideas of design. Uh which for my part includes cultural design.

[00:06:18]Uh and so before we get into more technical details, I would like to take a short detour regarding cultural design. I would like to center Inuit design using a phrase in intuititut. Uh inipt being the umbrella term for my people's language. Uh as for the phrase to translate is weather is thought is boss.

[00:06:50]So sila is weather is boss.

[00:06:56]Okay. Uh in classical inuit cosmology there's a deep connection between sila and isma.

[00:07:03]Uh so I took this picture uh in Nunovit in 2002. I took it with a disposal cam disposal camera. So it's not the highest quality but um what happened was it was completely clear sky and then within literally like 10 minutes these clouds rode in and covered it completely and the clouds were moving so fast it just like shaped the front of the clouds and like smoothed it out. Uh [clears throat] so weather in the Arctic changes all the time. and it changes quickly. Uh this parallels human thought.

[00:07:37]Uh to take this interpretation further, ideas of weather are connected to air and air is connected to breath.

[00:07:47]When humans breathe, we take air into our lungs, circulates through our bodies and then leaves us.

[00:07:55]Uh what happens when we use such breath to speak?

[00:07:59]uh the air has passed through our brains and so our thoughts have effect on it.

[00:08:04]Meaning when it leaves us as we speak, it conveys our will out into the world.

[00:08:10]It affects the world.

[00:08:14]It is for this reason uh in which traditionally have been very careful with our words since we know the power that they hold.

[00:08:22]Okay. So what does this story have to do with cultural design?

[00:08:27]uh Inwood culture is shaped by thousands of years of Arctic living. Uh the ice and the snow are both water and are malleable.

[00:08:37]In this sense, there's very little permanence in the Arctic. Uh and so in an environment like that, the things that have great meaning are the things that are permanent.

[00:08:47]Uh so what is permanent in Inuit culture? uh isma which is to say thought or rather patterns of thought that persist.

[00:08:57]Uh anthropologists and ethnographers who have studied Inuit society have noted a great many technologies that my ancestors have innovated such as uh Ioit and u but material technology in the Arctic is malleable.

[00:09:15]Uh as for the technology that is permanent in Inuit culture uh isma our ways of thinking are our technologies.

[00:09:25]In any case uh all this is my way of saying uh this talk is much is very much about design especially ways of thinking about design uh that persist.

[00:09:37]Okay. So uh next section uh template meta programming.

[00:09:44]So before we get into constex for C++ and functional type systems I would like to first discuss template meta programming.

[00:09:52]Historically speaking uh template meta programming is a paradigm shift from standard C++.

[00:09:58]Uh it is a different way of thinking about C++ code. Uh to motivate this understanding I would ask how do we use programming languages?

[00:10:08]uh in a general sense that is programming languages uh generally speaking describe types and values for those types. Uh such types can range from simple built-in to complex data structures with corresponding objects as values.

[00:10:24]From there we usually go on to define functions which act on our types and values of interest to return other types and values of interest.

[00:10:33]Uh in a general sense, this is pretty much the core of what programming languages are and do. Uh I say this uh because most other grammatical features added to a language are there to keep types, values, and functions organized.

[00:10:47]Either that uh or they are there to validate and verify type logic under additional constraints.

[00:10:54]So given this uh I would further say that the real focus of a programming language is that of functions.

[00:11:02]Uh how does this apply to template meta programming? Uh template metaroming at its simplest is a way to grammatically hack the C++ compiler.

[00:11:12]Uh compilers for everything they are are also programs.

[00:11:17]In their behavior when compiling they branch and loop based on their input uh just like any other non-trivial program does.

[00:11:25]Uh it is worth pointing out that the input to a compiler is in its simplest terms really just strings of characters which then go on to form our programs.

[00:11:35]Uh template meta programming is a style of such which uses language features in unintended ways to redirect the compiler's behavior.

[00:11:44]Uh when done right uh it ends up executing side programs on top of the main program translation.

[00:11:51]uh a classic example of that or sorry a classic example is that of a conditional operator.

[00:11:58]So here we have a uh conext for rule value called dispatch. Uh we declare a type alias and then we define it using conditional and the dispatch or based on the dispatch it will return double or int. then we can finally uh define a value based on that type.

[00:12:22]Okay, so the higher order idea is that we conceptualize certain C++ grammarss to take types and values as compile time input.

[00:12:32]Uh pretending like those grammarss were regular functions in the language.

[00:12:37]In effect, we end up with a higher order programming language built on top of standard C++, one which evaluates at compile time rather than runtime.

[00:12:49]Uh, conceptualizing grammar this way has been quite useful to C++ programmers in the past. Uh, which is why it has become a full-fledged style of programming on its own.

[00:13:00]At the end of the day though, it is important to remember this is just another programming tool uh which like any other has its trade-offs.

[00:13:08]On the upside, it allows programmers to resolve relevant data at compile time which is good for program performance.

[00:13:16]Uh it can also be used to dispatch type traits and attributes at compile time.

[00:13:21]On the downside, uh because it is a hack, because the compiler doesn't recognize or conceptualizing certain grammarss to be meta functions, uh it ends up shifting some of its type checking to the programmers who are making use of this meta programming style.

[00:13:37]Uh as of C++ 17, variatic templates, alias templates, and class templates can all be conceptualized as meta functions.

[00:13:48]As with standard C++ functions, each have its own grammar for making a function call.

[00:13:55]So standard C++ functions use parenthesis uh in their definitions of functions as well as the function call.

[00:14:06]Variatic templates as meta functions are the variety which most resemble standard functions. As such, we will discuss them first.

[00:14:15]So varied meta functions take a mix of parameters as input and return a value as output.

[00:14:21]If you'd like to use a value as input, I recommend using the auto keyword.

[00:14:27]So here we define the square function uh using auto and then when we call it instead of parenthesis it has the left and right braces and we [clears throat] call it the value 2.0.

[00:14:42]So in effect uh such meta functions are weakly typed because although the auto keyword does restrict input to values it doesn't restrict any further than that meta functions such as these can be strengthened in C++ 20 using concepts.

[00:15:01]So here uh we have the integral concept.

[00:15:06]Uh we reimplement our square function same as before except this time we test its type to see if it's an integral and then when we call it on the quoting number it returns an error because that's not an integral.

[00:15:24]Okay. So continuing on uh an interesting artifact about periodic meta functions is that we can define them using common pattern matching paradigms already known in other languages.

[00:15:36]A classic example is from Haskell.

[00:15:39]So we declare our factorial.

[00:15:42]Uh it also has an integral uh concept except I think they call them type classes.

[00:15:50]uh [clears throat] and then we define our factorial by case. The base case maps 0 to one and the general case maps the variable n to the recursive definition.

[00:16:04]Uh in C++ we do the same thing using specialization.

[00:16:08]So we have a factorial uh it takes auto end input uh but this is the general case and then we specialize to define the base case that map 0 to one.

[00:16:22]Uh so moving on uh let's next observe alias templates. Uh alias templates are somewhere in their input to variable templates but because they are aliases their output is restricted to types.

[00:16:38]So we have a make in enter array meta function. We declare it with using that takes auto end as input and returns a stood array of type int and size n as output.

[00:16:52]Uh so that's it for alias metaf functions except it's worth noting that pattern matching isn't an an available feature.

[00:17:02]Finally we come to class templates as meta functions. They are similar to alias metaf functions but with some important differences.

[00:17:10]Uh class metaf functions always construct classes.

[00:17:14]This is in contrast to aliases which are able to return pre-existing types.

[00:17:20]Uh class meta functions also allow specialization. Uh this means that pattern matching is an available feature.

[00:17:29]So for example we have some meta function uh we mark it with class it takes a type as input but then we can specialize an alternate case where the uh input is known to be a constant type.

[00:17:48]Okay so that's it for the three kinds of meta functions. Uh let's now discuss some of the traits they might share with functions at large. Uh the first kind of function worth mentioning is that of a higher order function.

[00:18:03]In that case uh what does it mean when we speak of higher order meta functions?

[00:18:08]Uh in programming literature higher order functions are ones which take other functions as input or return other functions as output. In template metaroming all three metapunction varieties can take other meta functions as input.

[00:18:24]Unfortunately uh variable meta functions are not supported as input uh to any of the higher order meta functions.

[00:18:32]As for alias and class metaf functions uh they can be passed as template parameters using template template keywords.

[00:18:40]So here we have a higher order meta function. It takes a regular meta function using template template uh syntax and then it also takes a type as its input. Uh and its body it applies that meta function to the type and then does other things.

[00:18:59]So as for returning meta functions from other meta functions uh there is currently no direct support for such a feature.

[00:19:06]uh before moving on to other kinds of meta functions. One higher order meta function worth matching is that of apply.

[00:19:15]So here is apply it's kind of the same as before and if we defined this first we could have refactored the the previous example.

[00:19:27]So the next trait that a functions can have uh is that of recursion.

[00:19:33]Uh in fact, we've already seen an example which implemented the factorial function.

[00:19:38]Uh there's not too much else to say except for a subtlety having to do with how compilers evaluate metaphors.

[00:19:45]Uh let's start with an example to demonstrate.

[00:19:49]So uh we have the factorial function again. Uh but this time we find it using the turnary uh operator. Uh does this compile?

[00:20:00]Uh no it does not.

[00:20:03]Both GC both GCC and clang give errors uh saying the template instantiation depth has been exceeded.

[00:20:10]Uh so why does this happen? Because of the turnary operator.

[00:20:16]Uh to explain this uh let's observe the following expression.

[00:20:21]So the function f uh you know applies values g of x and h of y.

[00:20:29]Uh so I ask uh how do we evaluate such an expression? Uh we can first evaluate G and H the order of which doesn't matter here. Uh then we can pass the return values to F. Uh the style of evaluation is called eager evaluation.

[00:20:47]Alternately alternatively uh we can treat G and H as paused expressions and pass them to F. Uh the meaning here is that we only evaluate g and h uh if the return values are actually needed when computing f. Uh this is called lazy evaluation. So the problem with the turnary operator is it evaluates eagerly. Uh this means the expressions n equals 0 factorial of n minus one and one are each evaluated before they're passed to the turnary.

[00:21:17]Uh for any int input n greater than equal to zero. uh this becomes a problem when we reach the assigned value n equals z by trying to evaluate factorial of n minus one uh we're trying to evaluate factorial of minus one uh which keeps decrementing by its definition uh and thus never halts.

[00:21:40]So the compiler is itself forced to halt uh when it exceeds its preset template instantiation depth.

[00:21:48][clears throat] Uh to finish our discussion on recursion, I'd like to show yet another way it can be achieved.

[00:21:54]Uh we've already observed variable metapunction recursion. So here I will demonstrate class metapunction recursion as an alternative.

[00:22:02]Uh it's worth stating though that class metapunction recursion is less performant at compile time. Uh it's worth knowing about because of its historical relevance.

[00:22:11]Uh it's also worth knowing about uh because recursive class meta functions further introduce a class template as compile time tpple pattern.

[00:22:21]It probably has a better name but if it does I don't know what it is. Uh the idea is that C++ classes naturally have member values types and functions. Uh so if we declare member values or functions to be static they become shared between objects of the class. In effect, uh this means static values and functions belong to the class type rather than any given object of that class. Uh this is notable for us because it means we can access static members of a class using the scope resolution operator.

[00:22:54]So here uh we have a metapair definition. Uh it takes the two type input uh assigns them as first and second uh member types.

[00:23:09]Uh and then we can u specify an actual metapair and then um access its first member.

[00:23:19]Uh I should mention uh in this talk I use the class and strct keywords interchangeably. Uh for our purposes the only difference is classes default to private members while strrus default to public. As for recursion uh we can use classes as better containers to reimplement the factorial function.

[00:23:38]So uh now we have a factorial tuple.

[00:23:43]>> [clears throat] >> Uh it has a member value called value uh which defines the general case and then we specialize the base case assigning value one to the member value and then we define the factorial meta function itself uh using uh the factorial tuple accessing its member value.

[00:24:10]Okay. Okay, so to finish this section, uh I would say the final function trait worth mentioning is that of curing. Uh curing is where we apply uh a multi-argument function to a single value uh to get a partially applied function back. Uh with standard functions, it can be implemented in C++ 20 as follows.

[00:24:32][clears throat] I'm not going to explain this one. I'll just leave it up for a second.

[00:24:38]So unfortunately because this requires returning a function from a function it is not directly supported in template meta programming.

[00:24:47]Uh there are multitudes of workarounds but they are beyond the scope of this talk.

[00:24:54]Just going to have some water quickly.

[00:25:04]Okay. So conexture programming [clears throat] uh template meta programming hacks the compiler in effect getting it to act like an interpreter as a side job to its main purpose.

[00:25:16]Another way to say this is that the compiler is taking on extra responsibility uh that it wasn't designed to handle.

[00:25:24]Arguably uh there's nothing technically wrong with this so long as we adhere to the C++ specification.

[00:25:31]Uh but from a design perspective uh it is questionable because it wasn't engineered to be an accountable unified system.

[00:25:39]Uh what's more even if we could logically prove it adheres to a clean scalable design uh the grammatical complexity of template meta programming remains a heavy burden.

[00:25:51]Conext programming aims to fix these problems because it intentionally designs for them. In context for programming, uh we can write standard C++ code, but instead of being translated into assembly, the compiler runs it at compile time. Uh so long as we annotate it with the const expert keyword, uh which we've observed many times at this point.

[00:26:14]Uh there is a caveat. Uh the constexert keyword doesn't promise to run the code at compile time. Generally speaking, uh it does so if it knows it can.

[00:26:23]Otherwise, it considers the code as standard to be compiled the usual way.

[00:26:29]Uh strictly speaking, uh it's not as simple as that though. C++ support for constax experies based on the exact specification being used. Uh to keep things simple, uh we'll put aside such caveats for now and say there are primarily two ways to run conext for programs. uh with functions and with classes.

[00:26:52]So [clears throat] constructor functions are defined in the same way as standard functions. Uh a C++ 20 example being just a plus two function which takes a value and adds two to it. Uh furthermore, we call construct for functions the same way as standard ones.

[00:27:08]Unfortunately, uh there are some restrictions in their use.

[00:27:13]uh one of the most notable is when we pass compile time values as arguments uh to anthropomorphize uh from the perspective of a function it has no way of knowing if the value it's been given is compile time or not. So it treats the value as if it's runtime.

[00:27:33]Uh this restricts the way we can interact with arguments inside a function body. So for example, arguments cannot be passed as template parameters.

[00:27:44]So here we have a square + one uh function uh takes an auto value x and then tries to pass it as a template parameter to our previous square function.

[00:27:59][clears throat] So when we define an actual constex for uh auto value x and apply the square + one function to it, we get an error.

[00:28:12]uh and yet uh there is a relevant but narrow C++ 17 workound uh which I call the type name autoc correspondence.

[00:28:21]The idea is we can convert a type to a value [clears throat] and convert it back again.

[00:28:33]Uh as for how it's implemented we start by defining a void function template. uh I've named it store. Uh it takes a single generic value as input and does nothing with it.

[00:28:48]We then define our meta function. Uh so you store T which so the base case uh takes a type and embeds the type of ex with an added pointer uh into store. [clears throat] So the single reference case uh just preserves the single reference and embeds it into store and then the double reference also preserves the double reference into store.

[00:29:23]So the reference type cases encode themselves into store. Uh but the default case where we add a pointer uh does not.

[00:29:33]The only reason for this special case is due to the void type.

[00:29:38]uh C++ does not allow functions with void input.

[00:29:42]So uh this would not compile.

[00:29:46]On the other hand, uh C++ does allow functions with void pointer input. Uh the trick then is to add a pointer to every non-reference type in the conversion.

[00:29:57]As for converting back, we simply pattern match the cases and remove the extra pointer.

[00:30:04]Okay, so [clears throat] uh in the double reference case uh it just preserves it directly.

[00:30:11]Single reference case uh same thing and then the type with pointer we just remove the pointer and return back the type.

[00:30:21]Uh so to which we can assign to which we can then restore our original type. Uh so we have instead of uh u store t we now have t store u uh it takes an auto input called u uh gets the type from it using decel type and then calls uh t restore t where t restore t uh takes a type as input uh normalizes it as a const reference that's actually just an optimization to simplify various cases uh and then applies or pattern matches using store match to get the result back.

[00:31:03]So note in the previous slide the use of t resto uh which takes the type of the store function and returns the original type of interest.

[00:31:15]So this is our workaround for the constex argument prop.

[00:31:20]uh we pass a compile time function pointer as argument uh which we then convert back to a guaranteed constra value.

[00:31:28]Uh we do so by first restoring its type and then converting back to a value. Uh it is an artifact of function pointers that we can do this.

[00:31:39]Uh as for an example application so here we have a function called our different. takes two types as input.

[00:31:50]Uh [clears throat] it res it uses those types, restores them and then applies the restoration or applies the same to those restorations and then negates.

[00:32:04]So if you were to use it in practice, you could uh convert an int to a value.

[00:32:11]Uh you can convert a character to a value and then apply as arguments um apply those as arguments to are different and it compiles under a static assert.

[00:32:25]So that's the trick. Uh it should be said in C++ 26 all this can be achieved directly with reflection.

[00:32:33]Uh as for the history of this type name model correspondence uh it wasn't the constexert argument problem that originally motivated this technique. Uh it was the need for uniform meta function parameters.

[00:32:47]So here we have our apply function or higher order metaf function uh takes regular metaf function and type as input and then applies. But we have a second version.

[00:33:01]Uh it again takes a meta function but it instead takes a value this time and applies that.

[00:33:09]Uh so the point of these versions of apply uh is to show that distinct parameter kinds uh lead to other to otherwise duplicate meta functions and often duplicate algorithms.

[00:33:20]Uh the way to mitigate this uh is to convert all auto parameters to type name parameters or to convert all type name parameters to auto ones. Uh I will mention in my code in my own code library I've chosen a type name to auto conversion policy because it allows us to pass values as template parameters uh as well as function arguments.

[00:33:44]Uh it also tends to have better compile time performance uh but that is case by case.

[00:33:50]Okay, moving on. Uh, another restriction of context expert functions worth mentioning uh is called the conextert allocation problem.

[00:34:00]Basically uh the problem is that objects with heap allocated memory uh cannot currently be returned from constexert functions.

[00:34:09]Uh in practice uh this policy is strict enough that class objects with internal pointers also uh cannot be returned from concepts and functions.

[00:34:19]assuming they're saved as constant expert values. U [clears throat] so note uh that allocating heap memory within the compile time scope of a function body is often supported.

[00:34:32]Also uh it's worth saying that to varying degrees uh there are proposals to solve this problem.

[00:34:39]At the very least, uh, more recent versions of C++ offer greater support for standard lever containers, uh, beyond that of stood array and stood vector.

[00:34:50]In any case, uh, that's it for const functions. Right now, uh, so on to constex for classes.

[00:34:59]Uh, defining them is a bit more involved than for functions. uh independent of their variations, we at least always start by annotating the constructors of a class.

[00:35:11]So here we have a class called opacity.

[00:35:13]Uh here's a constructor for it and we mark it as constexer and then independently of that uh we can mark member functions as constexer as well. Uh so note uh that when we instantiate a conextra object of the given class type, it is first created under the rules of its constructor as if it were a runtime object.

[00:35:36]Once the object finishes its construction, it is assumed to be an immutable compile time object. Uh it's worth mentioning the same pattern occurs with the uh constra functions as well.

[00:35:49]When a constexer function is called, it is executed as if during runtime. But when the value is returned and assigned as a conext variable, uh it effectively crystallizes as an immutable compile time object.

[00:36:04]Uh the prevalence of this pattern merits some terminology to help us conceptualize and navigate its subtleties.

[00:36:10]Uh notably that of time scopes in particular meta compile time uh and meta runtime.

[00:36:18]So here we have a program lifespan uh that can be split into compile time and runtime and then the compile time can be decomposed into scopes of meta compile time and meta runtime.

[00:36:32]So I have introduced this terminology in previous talks. Uh I stand by it. Uh it has helped me sort out designs that would otherwise have been too confusing to implement and I know of no standard terminology which does the same.

[00:36:47]uh ultimately uh this pattern in ter terminology leads to an idea I'm calling the compile time monet uh it just means in practice compile time programming works by alternating between scopes of metar runtime and metacmpile time uh so that's it for con 6 for classes so continuing on [clears throat] excuse me sorry one moment Okay. [clears throat] Uh since context per code is largely just regular C++ with the added context per keyword, uh there's not too much else to say about it. Uh as such, uh the remainder of this section will focus on building a theory of functions within this context.

[00:37:37]uh to start given the nature of context for compiling and being able to run programs at compile time uh it is natural to search for ways to automate the construction and manipulation of functions.

[00:37:50]Uh in particular we focus on the idea of composition.

[00:37:55]So for this exposition I will use simplified function notation uh or pseudo code.

[00:38:02]So manual composition is simple. This is just your standard math definition of compose.

[00:38:09]Uh to translate this into automated composition, uh we first switch to an alternative form known as continuation passing.

[00:38:19]So we take a regular function f and lift it to become a continu or to become continuation passing uh as a CPS function. We then evaluate it. Uh notice the right hand side is nearly identical to regular compose just uh the functions inverted.

[00:38:37]Uh one of the reasons uh continuation passing functions are interesting is because they have their own composition operator.

[00:38:45]Uh if f and g are cps functions uh then their composition is defined as follows.

[00:38:54]Just leave that up for a second.

[00:38:59]Okay, so for those interested uh I have a compiler explorer link implementing CPS compose.

[00:39:10]Okay, so now for the purpose of my functional type system uh we will want to generalize TPS composition in a way that lets us abstract out a controller.

[00:39:21]Uh think of it like this. uh if we want to compose a chain of functions uh f0 f_sub_1 f_sub_1 through fn uh we can instead of specifying a sequence of actual functions uh index them numerically uh then we would only need specify the corresponding numbers. So now a sequence of uh indices k0 k1 through kn uh to create our controller.

[00:39:50]So using C++ pseudo code uh to keep the details relatively simple uh we could implement our abstract CPS functions as follows.

[00:40:01]So we have our function uh as a template parameter. It takes a controller value uh uses that controller and a get next function to create our continuation and then it uses returns a call of that continuation to an intermediate value.

[00:40:22]Uh this is a template pattern. Sorry, I shouldn't use the word template. Um it's a general pattern. Yeah. Okay.

[00:40:31]>> [clears throat] >> Uh the idea is uh we can in practice implement a controller as a compile time bite array. We can then use that bite array uh to get the next CPS function in the composition.

[00:40:45]Uh we then call that next function making sure to pass the byte array along its compile time trajectory.

[00:40:52]Uh so it can continue the process until a function is constructed.

[00:40:57]With this uh we now have a powerful technique for automating the composition of functions and yet uh we can take this technique further. Uh I won't go into the details here uh but we can generalize our abstract CPS functions to act as if they were register machines.

[00:41:16]Uh in turn the controllers [clears throat] for these more powerful CPS register machines uh would be encoded as tables instead of arrays.

[00:41:26]Uh this would then give the appearance of a bite code assembly language.

[00:41:31]Uh this is the topic of my 2024 talk C++'s meta compiler. Uh given this I'll skip the finer details here.

[00:41:40]I will add uh the main grammatical feature we need uh to make this idea work is that of variatic packs.

[00:41:48]Uh a C++ 20 example would be uh nothing fancy here. It's just some function with a auto pack of arguments. Uh the reason for needing variatics is that we are simulating an arbitrary number of registers as CPS function arguments.

[00:42:05]In particular, uh we will need to read from and write to any given register in the pack. Uh in other words, uh we need variatic indexing.

[00:42:16]Uh C++ 26. This is simple uh since there is direct language support an example being so here we have a autopack and we want the fifth value and so with 26 you have a array like indic indexing but for a pack you know very simple uh in my own library I'm using C++ 17 uh so it requires a number of carefully crafted tricks uh outside the scope of this talk uh finally uh to finish the section I thought I'd give an example of what CPS register assembly actually looks like.

[00:42:55]Uh there's no zoom. I'm not going to explain it. I'll leave it up for a second.

[00:43:18]I apologize. Uh audio was okay.

[00:43:22]Bit of static.

[00:43:23]Okay.

[00:43:26]Okay. Next section. Uh my functional type system. [clears throat] Uh we're finally ready to discuss the type system that makes up this talk. I previously mentioned uh that I'd restricted my functional type system in ways that might be it.

[00:44:12]Oh yeah, >> that's good.

[00:44:17]>> Sorry [clears throat] guys, that's broken.

[00:44:59]Okay.

[00:45:01]Okay.

[00:45:04]Okay. Uh so right. So my functional type system notably my type system requires serialization meta assembly for the internal representation of functions stack allocated memory only.

[00:45:23]The motivation for these restrictions have entirely been due to my specialized continuation passing paradigm.

[00:45:30]The reality is I came up with the CPS paradigm first. uh the type system only came after.

[00:45:38]With that said, when I initially achieved my CTS paradigm, I did so using a proof of concept learning.

[00:45:46]Not only that, but the but truth be told, uh it was also meant to be a vehicle for me to learn about compiler theory.

[00:45:56]There's a lot of original research on my part having to do with CPS abstract machines.

[00:46:02]As for lexers and parsers, known technologies but it was my first time building those as well.

[00:46:09]As such the version 1.0 of my proof concept code was a mess.

[00:46:15]I did spend time cleaning up that code in a version 2.0 proof of concept library. Uh but even with that effort it was still a mess.

[00:46:25]Uh my meta compiler uh used an a wide range of conextur and temp sorry my meta compiler used a wide range of conextur and template metaroming tricks uh all all the while upholding a generic style of design choice uh to clean up the code further uh it wasn't a matter of incrementally improving the architectural design uh the design had simply reached its limits uh this is why I switched to rebuilding my met a compiler using a C++ constexer functional type system.

[00:46:59]Uh truth be told, uh there's not a whole lot of design discuss here, uh nor code to show at this point. Uh the small amount we're showing starts with an example of the type system internal representation.

[00:47:17]Uh to be clear uh no one is expected to know how to read this uh in order to use my library.

[00:47:24]Uh I'll explain it reading anyway uh to demonstrate the major design.

[00:47:30]Okay. So to start uh the very first record in a type system is always metadata.

[00:47:37]The 104 is the length of the flat array.

[00:47:40]The 28 is the current length.

[00:47:43]The initial zero is an error code. uh in CA in this case no error. Uh the other zero tells us whether or not the second record is a table of contents.

[00:47:56]Okay. Uh so for the next record uh next every other record is of this form.

[00:48:04]Records grow forward from left to right.

[00:48:08]So there's a left side.

[00:48:11]Uh the left side is the record entry.

[00:48:14]Here the initial five is the entire record length and then there's the right side. The right side is metadata. It points to the next related record. Uh the indexing is relative meaning it references records going backwards.

[00:48:33]Note uh in my library such record systems are called concords and I will use that terminology interchangeably with type systems.

[00:48:43]Uh so why create a tight system this way? Uh surely C++ has the maturity to make tight system implementations easier than this.

[00:48:53]Uh yes and no. Conexper is on its way with C++ 26 uh but not as much with 17.

[00:49:02]Uh so why concords?

[00:49:05]First uh a type system implemented as a flat array negates the conext for allocation problem.

[00:49:12]uh concord objects are always pre-allocated on the program stack and as class definitions they hold no internal pointer members.

[00:49:20]Second, as flat arrays uh which are readily serializable uh they mitigate against slow compile times. Uh consider the following string literal.

[00:49:33]uh I I won't explain that but uh it represents uh an important contextf free grammar in my library uh and as a string literal it can be marked conexture in turn a compile time parser generator in my library then translates it into the parser transition table for a specific meta compiler.

[00:49:57]Uh, as for compile times, uh, my original proof of concept meta compiler, uh, didn't scale, uh, but it was still reasonably performant. Uh, it took about 6 seconds on average, uh, to translate this contextfree grammar at compile time.

[00:50:16]Uh, my current library is a bit slower.

[00:50:19]Uh the initial step in translating the context for grammar uh is to lex the string into a list of words and tokens.

[00:50:27]Uh this currently takes about 9 seconds.

[00:50:31]Uh also I'm averaging between uh GCC and clang. So it works for both. Uh if instead uh I write that list out to file then read it back in during the next compilation round rather than starting from scratch each time. uh it takes under one second.

[00:50:51]Uh with C++ 26 and the embed feature, uh it might be even faster.

[00:50:58]Third, in terms of flat arrays, uh compile time concords are naturally compatible with meta-sembly bite code.

[00:51:06]Uh I previously implemented a proof of concept virtual machine to evaluate meta assembly bite code directly. Uh I'm researching how best to add it to my library.

[00:51:16]Uh if nothing else though uh these concord objects can be used to model all variety of compile time programs in C++ uh with many practical coding applications down the road and any meta assembly um within those concords uh they can be used to generate functions at compile time.

[00:51:39]So one major [clears throat] possible application is embedded domain specific languages uh making it easy to build a variety of C++ functions. Another example is an alternative to C++ concepts.

[00:51:53]The theory of functional types includes the ability to represent mathematical claims and their proofs.

[00:52:01]uh a simple example of a claim being uh this [clears throat] which reads uh for all rational a and b there is a rational number between them.

[00:52:12]Uh so I gave a talk in 2025 on this topic uh titled a universal data structure for compile time use uh as a potential alternative to concepts. uh proof theory has trade-offs that might make it relevant in certain contexts uh where concepts aren't uh but such is beyond the scope of this talk.

[00:52:35]As for other applications uh to end this section uh I myself intend to use the techniques of this talk along with my library uh to build the required compiler tools for my multimedia programming language.

[00:52:50]So as for lessons learned, uh the research presented in this talk uh is the culmination of 10 years of trial and error coding.

[00:52:59]Uh in a longer talk, uh I could give I could have discussed so much more uh in-depth examples.

[00:53:08]In any case, uh after all said and done, uh what lessons have I learned?

[00:53:14]one uh modern C++ is a multiaradigm language. It has great potential to express and solve many computational problems. Uh but this also means it has a complexity of interoperable features.

[00:53:28]Two, uh compiler tricks are fun and yet uh it's still better to use standard language features when possible.

[00:53:38]uh for example I didn't even mention the const keyword and how it generally provides better type safety feature support as well as performance uh for compile time only functions three uh compiler tricks are worth learning uh don't forget constexert functions and classes can and do take template parameters uh the roll out of conextra has been slow having started with minimal features in C++ 11. Uh each new C++ specification is doing its best to add more standard grammar to the world of constexert. Uh but as of yet uh there's no specification which supports all C++ features and so there are still situations where TMP tricks are required.

[00:54:28]Uh even then I've learned it helps to organize one's repertoire of tricks around narratives and theories.

[00:54:36]uh this is to say standard ways of thinking.

[00:54:41]In our case, uh we chose the theory of functions as our technology of mind.

[00:54:48]And maybe just maybe the final lesson here is that technologies of mind are the ones which might in fact persist in an everchanging world.

[00:55:02]So this is the end.