🍩 The Functional Donut 🍩
Tags: c, elm, javascript, webdev
Published: 2021-11-28 01:54:24

---
title: 🍩 The Functional Donut 🍩
published: true
description: A conversion of the C donut in a functional language
tags: c, elm, javascript, webdev
cover_image: https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7fxfo3iyy8va2ne5ctpz.png
---
*Demo: [https://donut.guupa.com/](https://donut.guupa.com/)*

-----

It was about time to create a functional version of the [Obfuscated C Donut](https://www.a1k0n.net/2006/09/15/obfuscated-c-donut.html). 

The C Donut is a 15-year-old creation by [Andy Sloane](https://twitter.com/a1k0n/) that renders a rotating three-dimensional donut in a terminal using characters.

I rewrote it using [Elm](https://elm-lang.org/).

Elm is a [purely functional language](https://en.wikipedia.org/wiki/Purely_functional_programming) 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](https://ellie-app.com/fXPnBZMFhqQa1) 🍩

![The donut code in donut shape](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8wql1xjb5pg5mqy58cj8.png "The donut code in donut shape")



In the rest of the post, I will refer to the **un-obfuscated** version of the code ([Source](https://github.com/lucamug/elm-donut/blob/master/src/Main.elm), [Demo](https://donut.guupa.com/), [Ellie](https://ellie-app.com/fXPxrfTBfsfa1)) 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

![Animated donut](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dod4won8h8hz088tuee5.gif "Animated donut")

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](https://www.a1k0n.net/2011/07/20/donut-math.html) 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](https://guide.elm-lang.org/).

# Starting from JavaScript

I created the Elm version converting the [JavaScript version](https://github.com/lucamug/elm-donut/blob/master/docs/a1k0n-originals/donut.js) 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](http://blog.jenkster.com/2015/12/what-is-functional-programming.html).

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:

```javascript
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`](https://package.elm-lang.org/packages/elm/core/latest/List#map) or [`fold`](https://package.elm-lang.org/packages/elm/core/latest/List#foldl) can be helpful. In other cases, we reach for [**recursion**](https://functional-programming-in-elm.netlify.app/recursion/).

![Baking powder can](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/un07qf4thl48c1sgt6ss.png "Baking powder can")
*The label of this baking powder can, an important ingredient in donuts, is an example of recursion. [Photo](https://en.wikipedia.org/wiki/File:Royal_Baking_Powder.jpg) by [Joe Mabel](https://commons.wikimedia.org/wiki/User:Jmabel).*


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:

```elm
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:

```elm
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:

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

We can write it in Elm like this:

```elm
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](https://jfmengels.net/tail-call-optimization/)).

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

From Elm:

```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):

```javascript
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](https://functional-programming-in-elm.netlify.app/recursion/tail-call-elimination.html).

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:

```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:

```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 

```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:

```elm
 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:

```elm
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).

![Cache performance](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bya2pigv7ny45tf8rc9k.png "Cache performance")

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.

❤️