Game development

In my fifth year of high school, I had to choose between taking two hours of applied sciences or two hours of mathematics and programming on top of the regular science curriculum. The programming part was about the basics of Java (through BlueJ¹). At that time, my father had already taught me some things about programming and had shown me some of the projects he had made in Delphi (an Object Pascal dialect). However, now it was my turn to play with the real deal. It took a bit before I started enjoying it, but once I was able to play around with the possibilities, I quickly learned how amazing programming can be.

My first personal project was developing a game. In the fifth year of primary school, i.e. six years earlier, during the last week of the school year, our teacher introduced us to the wonderful world of Age of Empires (AoE I to be specific). No wonder my own first game had to be something like it: a real-time strategy game. I started implementing unit and building classes, resource systems, graphics and an AI (clearly at that time this did not consist of much, but it worked!) I quickly got the support of two class mates and we worked on this project together for a while (adding a multiplayer mode amongst other things). However, due to holiday breaks and, more importantly, at the end of the last year of high school, the change to university, this project fell apart.

However, over the years, I often returned to it. At some point, I tried to salvage the code I could recover from my high school days, but, sadly, this was to no avail. I had to (re)start from scratch. This blog post will cover the latest iteration, which covers a few years (be it with lengthy breaks). When I started learning Java, version (1.)7 was in use. At the time of writing, version (1.)25 was the latest one. Many things have changed and many improvements have been added to the language. This means that, after obtaining a PhD in statistics, which implies working with Python for 4 years (and more), I had to relearn a lot and I also learned new things along the way. I selected a handful of topics that I want to cover in more detail, give my opinion about their use, and explain some relations to formal mathematics.

---

The following practice is common in Java code (and in general):

    public void someMethod(ClassA obj) {
        if(obj != null)
            obj.doSomething();
    }

Although this is straightforward to understand and very clear from the perspective of readability, it is slightly verbose. As soon as there are multiple objects in use, the amount of brackets that need to be inserted quickly increases and readibility suffers. For example, assume that we want to perform a chain of operations. If we want to foolproof the following method call obj.getSomeAttribute().doSomething(), we would have to write

    public void someMethod(ClassA obj) {
        if(obj != null && obj.getSomeAttribute() != null)
            obj.getSomeAttribute().doSomething();
    }

which requires calling getSomeAttribute() twice, something that should be avoided in general whenever possible (especially for costly methods), or

    public void someMethod(ClassA obj) {
        if(obj != null) {
            ClassB attr = obj.getSomeAttribute();
            if(attr != null)
                attr.doSomething();
        }
    }

The situation gets even worse if null values need to be handled explicitly. This introduces even more braces and control statements. Moreover, without inspection of a method’s implementation, it is a priori not clear whether it can return null or not (except when its return type is void). Accordingly, in general, we would need to check for null every time we use a method that is not void or returns a primitive type.

To this end, Java 8 introduced a new (generic) class: Optional<T>, which solves both issues at once. When using a method whose return type is of this form, it is immediately clear that the value could correspond to null (of course, it should not exactly be null as this would defeat the whole purpose). The way Optional<T> is implemented also allows for easier program flow. The situation considered above will now look as follows:

    public void someMethod(Optional<SomeClass> obj) {
        obj.ifPresent(ClassA::getSomeAttribute).ifPresent(ClassB::doSomething);
    }

As in the Stream API, methods can easily be chained. (We will come back to this in a section further below.) Now, given an instance Optional<T> opt, how do we handle null values? This is covered by the orElse() construction.² The code opt.orElse(alternative) will either

• return the instance of class T contained in opt if it is not null, or
• return alternative otherwise.

---

In the preceding section, we saw how we can handle null values in a safe and controlled manner. The only piece that remains is how to instantiate Java’s Optional<T>s. The most general method to obtain an Optional<T> reads as Optional<T> ofNullable(T obj). If obj == null, it will represent an ‘empty’ Optional<T>, otherwise it will simply be a wrapper of obj. Let us introduce the notations ‘Nothing’ and ‘Just obj’, depending on whether obj == null or not.

Combined with the functionality presented in the preceding section, it follows that Java’s Optional API gives a common example of a monad (see my previous post on diagrammatic calculus for more information). In particular, it constitutes the Maybe monad. Formally, this monad is characterized by the following natural deduction rules:

• Formation: $A:\mathrm{Type}\vdash\mathrm{Maybe}\,A:\mathrm{Type}$,
• Introduction: $a:A\vdash\mathrm{Just}\,a:\mathrm{Maybe}\,A\qquad \mid\qquad \mathrm{Nothing}:\mathrm{Maybe}\,A$,
• Elimination: $o:\mathrm{Maybe}\,A,f:A\rightarrow B\vdash f(o):\mathrm{Maybe}\,B$,
• Computation:
  • $f(\mathrm{Nothing}) \equiv \mathrm{Nothing}$, and
  • $f(\mathrm{Just}\,a) \equiv \mathrm{Just}\,f(a)$.

Let us unpack these rules (in Java):

• The formation rule says that, for every class A, there exists a class Optional<A>.
• The introduction rule says that there are two ways to obtain an instance of Optional<A>. Either by wrapping an instance of A or the empty Optional<A>.
• The elimination rule says that, if we have a method public B f(A obj), we can map any Optional<A> to an Optional<B>, i.e. we obtain a method public Optional<B> f(Optional<A> opt).³
• The implementation of this elimination rule goes as follows:
  • If obj == null, we are working with $\mathrm{Nothing}$, and $\mathrm{Nothing}$ is always mapped to $\mathrm{Nothing}$. Once we start with null, it remains null until the end of time.
  • For nonnull objects, we are working with an instance of the form $\mathrm{Just}\,a$ and applying $f$ is straightforward. $\mathrm{Just}\,a$ is simply a wrapper of $a$, so we can unwrap it, apply $f$ and then wrap it again.

Now, computer science is of course not the only place monads turn up. (For examples in quantum mechanics and logic, see this post and this post.) For 4 years, I worked on uncertainty quantification (UQ) and machine learning. While uncertainty quantification is an important part of every machine learning application (or, at least, it should be), sometimes it is impossible or morally unjust to try to put a number on it. UQ serves as a means to handle uncertain predictions and determine whether predictions coming from approximate models are reliable. However, UQ methods also suffer from “approximation” errors on their own (although these are of a different kind⁴).

When there is a strong lack of confidence, i.e. when the uncertainty is so high it is not meaningful anymore to give any prediction, pointwise or uncertaintywise, we can could adopt a different approach. (Which in mine opinion is a very fair one!) Even with robust frameworks like conformal prediction, the distinction between a lack of confidence of the model and a confident estimate of high uncertainty can be unclear. Does predicting the entire target space correspond to the former or to the latter? Consider the standard case of prediction regions. If we know that the ground truth distribution is, for example, the uniform distribution on 5 elements, and we are asked to produce a 90% prediction region, we are forced to predict all 5 elements. However, the same would hold if our model genuinely did not know what to predict and we had to make sure the statistical guarantees hold. So, how about we let the model signal this distinction to us. This is the idea behind prediction with reject option (see, for example, this review). We let the model abstain from making actual predictions when it is too uncertain.

Well, enhancing a given model by the ability to reject a prediction, is exactly the same as turning a classic prediction model $f:X\rightarrow Y$ into a prediction model $\overline{f}:X\rightarrow\text{Maybe }Y$. The Kleisli composition of such predictors also preserves the meaning of abstention. If we compose two such predictors and the first one abstains, the result of the second one will also be abstention (practically, this can of course be shortcircuited/hardcoded).

---

Above, I referred to the Stream API also introduced in Java 8. This API allows to handle Collections more easily, the most common features being filtering and mapping. Let us start from the beginning and consider a collection like an ArrayList<T> (which is just a particular implementation of a sequential list). Now, we would like to apply the method public S transform(T obj) to every element of the list to obtain an instance of ArrayList<T>.

The standard approach would be a simple loop:

    ArrayList<B> listB = new ArrayList<>();
    for(A obj : listA)
        listB.add(transform(obj));

But what if we do not have one method to apply, but two? Well, two possibilities exist. Either we chain methods:

    ArrayList<C> listC = new ArrayList<>();
    for(A obj : listA)
        listC.add(transform2(transform1(obj)));

Or we run two loops:

    ArrayList<B> listB = new ArrayList<>();
    ArrayList<C> listC = new ArrayList<>();
    for(A obj : listA)
        listB.add(transform1(obj));
    for(B obj : listB)
        listC.add(transform2(obj));

The former is more concise and only requires us to iterate over the collection once, vastly improving the complexity (both time and space). However, what if we also need to filter the results of transform1(A obj)? The best we could do is storing intermediate values:

    ArrayList<C> listC = new ArrayList<>();
    for(A obj : listA) {
        B temp = transform1(obj)
        if(predicate.test(temp))
            listC.add(transform2(temp));
    }

The Stream API allows us to streamline this code (what’s in a name):

    ArrayList<C> listC = listA.stream().map(a -> transform1(a))
                                        .filter(b -> predicate.test(b))
                                        .map(b -> transform2(b))
                                        .toList();

No need to write if-statements, no need to actually story intermediate values. Everything is done under the hood. What is even better: as long as the final method toList() is not called, nothing is actually performed. This is a beautiful example of lazy evaluation. We can initialize our stream pipeline at any point in time (or further modify it throughout the code), but only ‘consume’ it when we actually need it, minimizing memory load.

The method Stream<B> map(Function<? super A, ? extends B> mapper) is actually another example of a monad law: the List monad. $\mathrm{List}$ sends a set (or type) $A$ to the set (or type) $\mathrm{List}(A)$ of lists with elements in $A$. The action on functions $A\rightarrow B$ is exactly given by $\mathrm{map}$ (which is also well known under its alias $\mathrm{fapply}$):

\[\mathrm{List}\,f\bigl([a_1,\ldots,a_n]\bigr) := [f(a_1),\ldots,f(a_n)]\,.\]

Many more examples could be given, but I wanted to stick to the main novelties (for me) in the Java ecosystem. For those that want more, I highly recommend Bartosz’s site: https://bartoszmilewski.com/. Other beautiful examples of monads are exception handling and console output. In general, monads are the key structure required for stateful programming, i.e.~programming with side effects. (Again, see Bartosz’s site for more information.)

---

As sketched above, the categorical semantics of filtering are not as straightforward as those of function application. However, the underlying structure was too interesting (in my opinion) not to write an additional section on it! Besides the approach through the maybe monad, there is also an approach that makes use of so-called catamorphisms.

Consider a class $A$, interpreted as a set, and the associated polynomial functor $L_A(X) := 1+A\times X$. It is not hard to convince oneself that $L_A(\mathrm{List}(A))$ is equivalent to $\mathrm{List}(A)$, the unique element $\ast$ being sent to the empty list $[]$. This can be rephrased in the language of $F_A$-algebras. An algebra over an endofunctor $F:\mathbf{C}\rightarrow\mathbf{C}$ is a morphism $F(X)\rightarrow X$ (where $X$ is called the carrier).⁵ The equivalence $L_A(\mathrm{List}(A))\cong\mathrm{List}(A)$ is then a consequence of Lambek’s theorem, since $\mathrm{List}(A)$ is the initial algebra for $F_A$. So let us first see what $F$-algebra morphisms are.

A morphism $\varphi:(A,\alpha_A)\rightarrow(B,\alpha_B)$ of $F$-algebras is a commutative square as shown below.

The algebra $(A,\alpha_A)$ is said to be initial if there exists a unique such diagram for every other algebra $(B,\alpha_B)$. Lambek’s theorem then says that $\alpha_A$ is an isomorphism whenever it is initial. Now, since $\alpha_A$ is an iso, it has an inverse $\alpha^{-1}_A$ which makes the following diagram commute.

It follows that the algebra morphism admits the following recursive expression:

\begin{gather} \label{cata} \varphi = \alpha_B\circ F(\varphi)\circ \alpha^{-1}_A\,. \end{gather}

Such morphisms out of an initial algebra are also called catamorphisms. Now, we can return to how filtering of lists with respect to a given predicate can be incorporated. Every predicate $p:A\rightarrow\mathbf{2}$ gives rise to an $F_A$-algebra structure on $\mathrm{List}(A)$ as follows:

\[\pi_p: \begin{cases} \ast\mapsto []&\\ (a_0,[a_1,\ldots,a_n])\mapsto[a_0,a_1,\ldots,a_n]&\text{ if }p(a_0)\\ (a_0,[a_1,\ldots,a_n])\mapsto[a_1,\ldots,a_n]&\text{ otherwise} \end{cases}\]

The catamorphism associated to $\pi_p$ can be (recursively) obtained through Eq. \eqref{cata}.⁶ The first step is to see how it acts on the empty list (try to have a guess before you read on).

Now, what about a singleton list?

By recursion, this gives us exactly what we want: filtering out all elements that do not satsify the predicate $p$.

---

• https://learnyouahaskell.github.io/
  
  
• https://bartoszmilewski.com/2017/02/28/f-algebras/
  (Bartosz’ site is an absolute goldmine for everything related to computer science and category theory.)
  
  
• Awodey, S. (2010). Category theory. OUP Oxford.

---