View diagram at https://catecon.net/d/hdole/factorial.
In this video the factorial n! is built using only basic morphisms like add and multiply, and categorical operators. The notion of ‘if’ is not builtin, so there’s work to be done!
Today we’ll show how to build a factorial morphism using basic functions like add and multiply and categorical operators like composition and products and coproducts.
We will generate C++ code for double precision floating point, compile it, and run it.
Next we show a novel diagrammatic way to build morphisms using what are herein referred to as reference morphisms using injections and projections.
To generalize the notion of factorial, we create the definition of factorial in Catecon.
Lastly, we use that factorial definition to generate a 128-bit version of the factorial, and run it as well.
Let’s get morphing.
We’re referencing a pre-existing diagram called CPP that we use for accessing basic functions like subtraction and multiplication and accessing the TTY console.
First off let’s list the basic required pieces.
Use X to change the input mode to ‘morphism’ and double click.
Our first factorial uses double precision floating point, or F64.
Call our morphism ‘fact’.
And of course, the codomain is F64.
To assemble using categorical operators we need the basic bits that we’re assembling and there are four things we need:
Test for zero
The number one for doubles
A decrement by one
And the 64-bit floating point multiply
Our first step then is to copy F64 and create the identity morphism with a double-click.
We know we are going to use the input to test for zero, so we need to make a copy of the input by creating a factor morphism, or delta in this case, from F6 4 to F64 cross F64.
Next select the test-for-zero and the identity and create the product of the two by clicking the P key.
Drag the domain and drop on the codomain to fuse the two together.
Select the codomain and note the appearance of this special button.
Catecon comprises a list of actions, and those actions appear on the toolbar depending on what has been selected.
As it happens we are in a category with distribution, and we have selected something that we can distribute, so click.
We can only right distribute, so click.
Now we need the two morphisms that depend on the result of the test for zero.
We do not have something labeled true and false, but we do have coproducts and a terminal object.
Hence we represent the space of truth values with one plus one, sometimes known as two.
False corresponds to the zero injection from one to two, and true being the one’th injection from one to two.
For the distribution we can also look at its string graph to see how the various factors of the domain and codomain are connected.
Our two new morphisms need a domain of one cross F64, so select a one and F64 and hit the P key to create their product object.
For the morphism corresponding to the true path, we don’t need the F64 so we double-click on the one factor to create a projection to it.
Next make a copy of the floating point one and fuse the domain.
Area-select both morphisms and notice the composition icon appears now that we selected something composable.
Make the composite and we have the first of our two morphisms.
Now make a copy of the one cross F64.
This time we need the F64 so project the F64 and forget the one.
We need again to make two copies of our input, so bring a copy of the delta morphism over and fuse it.
Next up is doing the recursive function call, so take two copies of the decrement and fact morphism, fusing in the proper order.
Select both and compose.
Select the F64 identity and the last morphism, form the product of the two, and fuse appropriately.
Select the multiplier, copy, fuse, and compose.
Now we have our second morphism.
First select the latter morphism and it represents the false path, and then select the former morphism as the true path.
Form the coproduct of the two, and fuse appropriately to where we left off.
Lastly in the composite we need to fold the two paths in the coproduct together.
Select F64 and then the dual of the projection button to create the fold.
Select and compose.
Now we have our main morphism built.
Next select the fact morphism followed by the main morphism.
Our toolbar now shows a new option for recursion since it was detected that the first morphism has the same domain and codomain as the latter, and the latter uses the former somewhere in its construction.
Click it to set the recursor, and we have finished creating the factorial as a morphism.
But does it do anything?
Let’s convert it C++, compare it to our original code, and try it out.
Copy fact and then select its domain and the right hom object icon to see which morphisms have a codomain of F64.
There’s a lot so we filter to find the morphism from standard input.
Similarly click on the left object icon to see morphisms with domain F64, and filter to find the out to standard output.
Arrange and compose.
Click on the question mark icon for info about the element itself.
You will see a C++ option, so click it.
Then click on the download button to get the C++ code for the morphism.
And let us take a look.
The first set of include files comes from the C++ generator, and the subsequent ones are those from the referenced diagrams.
We have a couple of typedefs, the first is one plus one typedef’d as bool, and our F64 typedef’d as a double.
Next up is the internal name of our main morphism.
This big long name is the unique name for the morphism in Catecon’s space of morphisms.
In the emitted code the function is seen as fun underbar it’s signature.
An element’s signature is a key internal feature of how Catecon tracks elements, and it is exposed here.
We see this function calls itself so it is recursive.
It is also seen called from the program’s main function as it is called to read in a double, apply the factorial, and send the result to stdout.
The function has an input of var_2, and there seem to be a lot of variables.
But where did these variables come from as there are no variables in the original diagram itself?
Go back to the diagram and click the G key to see all morphism’s string graph if it has one.
We see the connected string starting from our domain, continuing through the distributor, and down into the true and false cases.
This connected string through all the morphisms is assigned to var_2.
The propagation continues through all morphisms, even fdecr64 defined as a composite in a reference diagram.
In effect, sub-morphisms appearing in the top-level expression are all expanded and do not have corresponding function calls.
The main fact morphism has a function call as it needs to be recursive.
Going back to the code the var_4 holds the result of the test for zero, and it looks like when true that the final result var_3 is set to one.
Otherwise var_2 is decremented by one, sent to the factorial, and the result multiplied.
The remainder is boiler plate to read a number, apply it, and show the result.
Go to the command line and compile the fact64.cpp code. No errors. Good sign.
I have a script to run a.out with inputs up to 200, so run it.
That looks good, though it switches over to floating point.
Keep going, and it looks like it overflows at 170 factorial.
That was a bit of work, though in a pleasing categorical ASMR manner.
Let us try to reduce the amount of work by using some injections and projections as references to guide the morphism assembly process.
We start with the test-for-zero morphism.
Double-click on the left one for false to create an injection to that factor.
Click the R key to turn the morphism into a reference.
Good. What is a reference?
Think of a reference as flowing in the opposite direction of the arrow.
In other words, if the codomain is hit, try to run all the morphisms based on the domain.
Make a corresponding one for one.
Now on the it-is-zero path, take a copy of one64 and fuse the domains.
For the other path take a copy of F64 and click the one key to create a morphism to the terminal object.
Turn it into a reference and fuse the codomain.
Next double-click on the F64 to create an identity, turn it into a reference and fuse.
These two references mean that when both are satisfied, morphisms with domains on the F64 can then be evaluated.
Take our decrement and fact morphisms and put them inline appropriately.
Copy the multiplier and double-click on the first factor to project it, turn it into a reference, and fuse.
Double-click the second factor and act accordingly.
Now we can fold the two paths back together by copying down the F64 fold.
Double-click to create the two injections and fuse.
These are not references as the information flow is down the arrow.
We can now select an object on our blob and the toolbar shows the morphism assembly button.
Clicking the action button then assembles the blob into a morphism.
The resulting composite morphism h as a similar structure to the one we created by hand.
We make two copies of the input, run the test for zero, distribute, have two conditional morphisms, and finally fold the result.
We have a few more factor morphisms in the composite as the general case goes through some sub-cases.
Now look at our fact morphism and remove the hand-built morphism previously set as its recursor.
Set the newly generated morphism as our recursor and now we have the factorial morphism generated from diagrammatic references.
While that was fun, what if I wanted to make a 128-bit version of factorial.
Instead of having to make a similar diagram each time there’s a need to make a new factorial, we instead create a definition of factorial.
With that said, select fact, notice the definition button, and click it.
The definition action scans the fact morphism and determines that the following morphisms are required to build the fact morphism.
At the end we see the morphism that can be generated by the definition.
This is a simple, or lower level, version of a definition as we have not put any constraints on the required morphisms, and such constraints would be declared commutative diagram cells.
Call our definition factorial and create it.
Look at the definition and view its internals.
We see the four required morphisms and fact morphism as before.
Now use the definition to create a 128-bit version of the factorial.
We enter the names of the four corresponding morphisms for F128 and create the morphisms.
With the morphisms selected note that we have a button indicating the presence of user actions.
When we created the factorial definition it creates a user action that looks into the selected elements to see if there’s a match to the definition.
In this case we have something and can see the hdole/factorial action available.
Click it.
Now we have a listing of the original four morphisms as the source and the four selected morphisms as the target.
At the bottom are the morphism templates that can be generated (probably should filter out the decrement).
By clicking the placement button, we get the F128 version of the factorial generated by replacing each occurrence of the source with the corresponding target.
We want to test this new version, so we attach standard input and output to the morphism.
Download the C++ code.
Let’s diff the fact64.cpp and fact128.cpp code.
Basically, the names are different as they at the least have different domain and codomain.
Signatures are of course different.
The new variables are instantiated with 128-bits.
The structural part of the code is the same in both files as those lines don’t show up in the diff.
Let us compile the new version. Yay.
I have a pre-existing script to run a.out from zero to ten thousand by 10.
We run it and see that first floating point number at ten.
And it looks like we overflow just before 1760 factorial.
Quod erat demonstradum: Factorial as morphism.