No Sugar, please

As a software developer I always strive to get better. I try to learn at least one new language per year. I found it a good second step to get into some kind of daily routine with a new language that I just picked up. On that path of getting literate I found it a good exercise on the path of getting literate in a new programming language to solve the same (simple) problem over and over again.

Katas

In reference to Japanese culture that is often called a Kata. I have made it a habit to start my day doing at least one Kata. The trick is to try to find a different solution every time. The first ten to fifteen variants may be done with ease. But coming to your 80th solution might be interesting. You might end up using TensorFlow since you are out of ideas otherwise.

Exercism

If you have not yet discovered exercism.io I highly recommend having a look! It provides multiple dozens of Katas for every language you might be interested in. It also provides a mentored track for each language that allows a mentor to nit pick our solution and thus provides another layer of improvement onto your coding skills. Furthermore I found that to be an excellent space to discuss patterns and language idiomatics.

Desugaring

I recently tried a new approach in Katas. Instead of solving the problems in a different way, I take prior solutions and desugar them. Desugaring is the process of removing syntactic sugar from your language of choice.
Side note: I will use Haskell for the examples in this post. If you haven’t had the pleasure of seeing Haskell code before I hope this might also be an introduction that sparks your interest in the language.

Hello, World

Let’s have the simplest example and desugar “Hello, World!”:

-- sort of hello world
-- with added reading of user input to make it simple instead of trivial
main = IO ()
main = do
  name <- getLine
  putStrLn $ “Hello, “ <> name <> “!”

Desugared:

-- sort of hello world desugared
main = IO ()
main =
  getLine >>= (\name ->
    putStrLn (“Hello, “ <> name <> “!”))

I personally find the desugared example more intuitive and easy to understand. I can see the monadic computation and binding from getLine to name to the call of putStrLn. But we can drive this further. Infix notation is also just syntactic sugar. Haskell is a functional language. That means everything is a function. So let’s desugar “Hello, World!” furthermore and have a look at those functions:

-- sort of hello world desugared infixes
main = IO ()
main =
  ((>>=) 
    getLine 
    (\name -> putStrLn ((<>) “Hello, “ ((<>) name “!”))))

Oh, look! Haskell is a LISP! Now things fall into places I have not seen them, yet.
Let’s try desugaring another Kata that might not be as trivial as “Hello, World!”.

n-th Prime

Taken directly from exercism.io: Given a number n, determine what the nth prime is. By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. If your language provides methods in the standard library to deal with prime numbers, pretend they don’t exist and implement them yourself.

Okay, let’s do this! A solution to the nth-prime-Kata could look like the following code snippet:

nth :: Int -> Maybe Integer
nth n
    | n < 1     = Nothing
    | otherwise = Just (nth’ [] n 2)

nth’ :: [Integer] -> Int -> Integer -> Integer
nth’ primes it nextCandidate
    | it == 0 = head primes
    | otherwise = if (isPrime nextCandidate)
        then nth’ (nextCandidate:primes) (it-1) (nextCandidate+1)
        else nth’ primes it (nextCandidate+1)
    where
        isPrime c = (length [x | x<-primes, x `mod` c == 0] == 0)

Let’s desugar that bit by bit and see, what we might learn. I start with the nth’ function since it might be where the meat is. nth is merely an interface.
At first let’s have a look at the signature.

nth’ :: [Integer] -> Int -> Integer -> Integer
nth’ primes it nextCandidate

Since Haskell is a purely functional language and a language is always a mapping from a -> b, we can see that these are composed functions. Desugaring that will give a clear understanding how Haskell’s type signatures work:

nth’ :: [Integer] -> Int -> Integer -> Integer
nth’ =
  (\primes ->
    (\it ->
      (\nextCandidate ->
        -- ...
      )))

Oh, wow! The type signature makes sense now!
Next to the guards; that are those pipe characters. They are indeed a shorthand for if-then-else what itself is sugar on case. So

| it == 0 = head primes
| otherwise = -- ...

becomes

case it == 0 of
  True  -> head primes
  False -> -- ...

Following that we see an if-block. We know, what to do with that!

if (isPrime nextCandidate)
then nth’ (nextCandidate:primes) (it-1) (nextCandidate+1)
else nth’ primes it (nextCandidate+1)

becomes

case (isPrime nextCandidate) of
  True  -> nth’ ((:) nextCandidate primes) ((-) it 1) ((+) nextCandidate 1)
  False -> nth’ primes it ((+) nextCandidate 1)

Pretty neat! We learned that case is the foundation of all branching operations in Haskell. Good to know!
The next interesting thing is where. This is not that interesting, since it is only a search and replace operation. But we have something in the following clause that catches our attention while doing that: We have a list comprehension:

[x | x<-primes, x `mod` c == 0]

We read this as “make a list from all x of primes that are natural dividers of c”. That clearly is a nice bit of syntactic sugar. Let’s try to desugar that in two steps:

-- fist step: discover the monad
do x <- primes
  case ((==) (mod c x) 0) of
    True  -> return x
    False -> []

-- second step: desugar the do block
primes >>= (\x ->
  case ((==) (mod c x) 0) of
    True  -> return x
    False -> [])

That is very interesting. We learned that list comprehension has a monadic structure.
Bringing it all together we get this desugared version of our nth’:

nth’ :: [Integer] -> Int -> Integer -> Integer
nth’ =
  (\primes ->
    (\it ->
      (\nextCandidate ->
        case (primes >>= (\x -> 
          case ((==) (mod nextCandidate x) 0) of
            True  -> return x
            False -> []
        ) of
          True  -> nth’ ((:) nextCandidate primes) ((-) it 1) ((+) nextCandidate 1)
          False -> nth’ primes it ((+) nextCandidate 1)
      )))

Not pretty, but we learned a lot about the language. Haskell is in its very core a purely functional language with very little actual vocabulary to it. As we dive deeper in desugaring the syntax we will manifest the principles on which the language is built upon.

Call to Action

The motivation to this article is to get you interested in the fundamentals and principles of your own language of choice. Try desugaring short programs in your language and watch the principles blossom. Try to understand, why things are that way and then slowly reapply the sugar one bit at a time.

Resources

Go to exercism.io if you haven’t done that, yet.

You can find some of my exercism.io - solutions for the Haskell track on GitHub: https://github.com/felbit/exercise-haskell