🍩 The Functional Donut 🍩

Demo: https://donut.guupa.com/

---

It was about time to create a functional version of the Obfuscated C Donut.

The C Donut is a 15-year-old creation by Andy Sloane that renders a rotating three-dimensional donut in a terminal using characters.

I rewrote it using Elm.

Elm is a purely functional language to create web applications. It compiles into JavaScript.

As per tradition, I also made an obfuscated version shaped like a donut.

You can see it in action here 🍩

In the rest of the post, I will refer to the un-obfuscated version of the code (Source, Demo, Ellie) that doesn't have the donut shape but use the same logic.

The un-obfuscated version has some extra features:

• Start/Stop
• Cache system
• FPS setting (60 ~ 6)
• Speed setting
• Position settings

In this post, I will explain how I converted this script to Elm. If you are interested instead in the math of the script, refer to Donut math: how donut.c works by the original author, where these concepts are explained very well.

This is not going to be by any means an introduction to functional programming. If you want to learn more about functional programming and the Elm language, I suggest starting with the Elm Official Guide.

Starting from JavaScript

I created the Elm version converting the JavaScript version of the donut.

The script itself is not that complicated, but it is very imperative. It uses mutability and loops.

How can we convert it into a purely functional language? But foremost...

What is a purely functional language?

A purely functional language, like Elm, is a language that supports and motivates programming with controlled side effects.

Usually, this comes with immutable data and pure functions. Pure functions return the same output for the same input and cannot have any side effects.

If the data is immutable, how can we have for-loops, where typically the counter i mutate at each iteration?

With recursion!

Loop = Recursion

The JavaScript code contains three loops:

for (var i = 0; i < 6.28; i += 0.02) {...}
for (var j = 0; j < 6.28; j += 0.07) {...}
for (var k = 0; k < 1760; k += 1   ) {...}

Imperative loops can be converted to functional code in several ways, depending on the type of the loop. If the loop involves the items of an array, for example, functions like map or fold can be helpful. In other cases, we reach for recursion.

The label of this baking powder can, an important ingredient in donuts, is an example of recursion. Photo by Joe Mabel.

Because there are several loops in the original code, let's build a declarative function that is implementing the loop logic. After that, every time we need a loop, it will be enough to call this function with the proper details.

A generic loop in this script needs:

• a counter, that holds the present value of the counter (that increments at each iteration)
• a max limit, so that the loop can be terminated when the counter reach this limit
• an increment value, to be added to the counter at each iteration
• some data, to keep around for the function below
• a donut (the result)
• a helper function that, given the counter, the data, and the previous donut, generate a new donut

And will return a donut.

Let's translate this into a type annotation:

loop :
    { counter : number
    , max : number
    , increment : number
    , data : data
    , donut : donut
    , helper :
        { counter : number
        , data : data
        , donut : donut
        }
        -> donut
    }
    -> donut

..and this is its implementation, the heart of our script that will take care of all our loops:

loop args =
    if args.counter >= args.max then
        -- We reached the limit, we simply return
        -- the current donut
        args.donut

    else
        -- Otherwise we call `loop` recursively...
        loop
            -- ..after incrementing the counter...
            { counter = args.counter + args.increment

            -- ..and calculating a new donut...
            , donut =
                args.helper
                    { counter = args.counter
                    , data = args.data
                    , donut = args.donut
                    }

            -- ...while the rest of the data
            --    remain as it is.
            , max = args.max
            , increment = args.increment
            , data = args.data
            , helper = args.helper
            }

Now that we have this utility function we can convert the JavaScript. Let's start, for example, with this one:

for (var i = 0; i < 6.28; i += 0.02) {...}

We can write it in Elm like this:

loop
    { counter = 0
    , max = 6.28
    , increment = 0.02
    , data = ... -- some data
    , donut = donut
    , helper = i_loopHelper
    }

It may seem that we created some unnecessary boilerplate compared to the JavaScript loop, but at the same time this form is more declarative and we don't need to write the logic of the loop over and over, we just pass the details about how the loop should be.

Tail-call optimization

Ok, this is all nice and well, but what happens if we iterate too many times, don't we risk a stack overflow error?

Yes, we do, but the Elm compiler is smart enough to convert a recursive call to a function back to a simple loop. (Note that this may not happen if certain requirements are not met).

Out of curiosity, this is an approximation of how Elm compiles the recursive loop function described above into JavaScript.

From Elm:

loop args =
    if args.counter >= args.max then
        args.donut
    else
        loop
            { counter = args.counter + args.increment
            , donut =
                args.helper
                    { counter = args.counter
                    , data = args.data
                    , donut = args.donut
                    }
            , max = args.max
            , increment = args.increment
            , data = args.data
            , helper = args.helper
            }

To JavaScript (by the Elm compiler):

var loop = function (args) {
    while (true) {
        if (args.counter >= args.max) {
            return args.donut;
        } else {
            args = {
                counter: args.counter + args.increment,
                donut: args.helper({
                    counter: args.counter, 
                    data: args.data, 
                    donut: args.donut
                }),
                data: args.data,
                helper: args.helper,
                increment: args.increment,
                max: args.max
            };
        }
    }
};

At the end of the day, we are going back to a code that is similar to the original JavaScript, without recursion, and with mutability.

This technique is called Tail-call optimization.

Elm is like a level of abstraction above JavaScript where all functions are pure, data is immutable, types are correct, and runtime exceptions don’t exist. Pretty neat!

Trivial conversion

The rest of the conversion is trivial at this point. Just one to one coversion. For example, from Javascript:

var sp=Math.sin(i),cp=Math.cos(i),
    h=ct+2,
    D=1/(sp*h*sA+st*cA+5),
    t=sp*h*cA-st*sA;

var x=0|(40+30*D*(cp*h*cB-t*sB)),
    y=0|(12+15*D*(cp*h*sB+t*cB)),
    o=x+80*y,
    N=0|(8*((st*sA-sp*ct*cA)*cB-sp*ct*sA-st*cA-cp*ct*sB));

To Elm:

sp = sin i
cp = cos i
h  = ct+2
d  = 1/(sp*h*sA+st*cA+5)
t  = sp*h*cA-st*sA
x  = round(40+30*d*(cp*h*cB-t*sB))
y  = round(12+15*d*(cp*h*sB+t*cB))
o  = x+80*y
n  = round(8*((st*sA-sp*ct*cA)*cB-sp*ct*sA-st*cA-cp*ct*sB))

Other places requires small changes, for example this construct in JavaScript

if( y<22 && y>=0 && x>=0 && x<79 && D>z[o] ) {
    z[o]=D;
    b[o]=".,-~:;=!*#$@"[N>0?N:0];
}

Is changing both z and b arrays in place. This mutability is not allowed in Elm. Moreover Elm always requires an else block, so this will be converted into:

 if y < 22 && y >= 0 && x >= 0 && x < 79 && d > zValue then
    { z = set o d z
    , b = set o (filler n) b
    }

 else
    { z = z
    , b = b
    }

Note how we return a new record here without changing the old one, also in the else case, where we return a new record that is the same as the previous one.

Almost there

The main function that create a donut frame is now reduced to:

donutBuilder : J_loopData -> String
donutBuilder data =
    j_loop data
        |> .b
        |> Array.toList
        |> String.join ""

Note that there are type annotations throughout the code, but in Elm these are optional. The compiler is able to infer correctly all the types without annotations. The reason we add them is for better readability of the code, and also to help the compiler to give more meaningful error messages.

Cache system

In the Elm version I added a cache system, so after a few seconds, once all the 200 initial donut positions are calculated, the animation proceeds with a smaller usage of resources (see the graph below).

While the cache is generated, each frame is rendered well under 16 milliseconds, assuring a smooth animation at 60 frames per second on most recent devices.

After the cache is generated, the CPU is mainly used to update the DOM 60 times per second.

Conclusions

We converted a highly dynamic, imperative code into pure and immutable code. And then we got it converted back to a highly dynamic, imperative code by the Elm compiler 🤯

I tried to follow as closely as possible the original JavaScript code, I am sure that there are better ways to convert this script.

For such a small piece of code, it was just a style exercise. But also in this small example, I think it is interesting to see how a safe environment where all functions are pure and all data is immutable makes the code different, more explicit if you want.

This has an impact on maintainability and expandability in the long run, especially on larger projects.

I hope you enjoyed the post. Let me know your thoughts and if you have a more functional way to convert the script, add it in the comments below.

❤️