Kontakt

No Sugar, please

by on

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 Kata routine with a new language that I just picked up. It’s a good exercise on the path of getting literate in a new programming language to solve the same (simple) problem over and over again. 

Kata

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 different solutions may be easy. But coming to your 80th solution will be interesting. You might end up using TensorFlow since you are out of real ideas.

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 on your coding skills. Furthermore that is an excellent space to discus patterns and language idiomatics.

Desugaring

I lately tried a new approach in Katas. Instead of solving the problems in a different way, I take previous solutions and desugar them. Desugaring is the process of removing syntactic sugar your language provides.

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 even more intuitive and easy to understand. It helps me to understand the monadic computation and binding from getLine to name to the call of putStrLn. But we can drive this further.

Infix notation is also syntactic sugar. Haskell is a functional language. That means everything is a function. And functions are just data. So let’s desugar “Hello, World!” further, to have a look at that:

-- 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!”. 

nth 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."

Ok, let's do this.  A solution to the nth-prime-Kata could look like the following:

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 wirst 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 function is always a mapping from a -> b, we can see that this is actually a composed function. Desugaring that will give a clear understanding on how the type signature works:

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

This is not pretty. It's really 'bitter', you might even say. 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