DEV Community: Niklas Gruhn

Avoiding "catch-all" else branches with type trickery

Niklas Gruhn — Wed, 11 Oct 2023 20:51:28 +0000

"Catch-all" else branches can lead to unintended behavior when extra cases are silently introduced. We can leverage the type checker to catch such issues before going to production.

For example, here we have a TShirt type and a function, that returns the length of a TShirt in centimeters:

type TShirt = {
  size: 'small' | 'medium' | 'large'
}

function lengthCM(tshirt : TShirt) : number {
  if (tshirt.size === 'small') {
    return 70
  } else if (tshirt.size === 'medium') {
    return 72
  } else {
    return 74
  }
}

The final else branch is such a "catch-all" else branch. It handles the remaining case where size is "large". If we later add the size "xlarge" and forget to update the function, then we return the same length for both "large" and "xlarge".

It's better to handle each case explicitly:

//                                   vvvvvv  type error here
function lengthCM(tshirt : TShirt) : number {
  if (tshirt.size === 'small') {
    return 70
  } else if (tshirt.size === 'medium') {
    return 72
  } else if (tshirt.size === 'large') {
    return 74
  }

  // implicit:
  // return undefined
}

However, without any else branch we get an implicit return undefined at the end of our function. This causes a type error because the effective return type is now number | undefined instead of number.

The implicit return undefined should actually be unreachable because we exhaustively checked all T-shirt sizes. So a simple fix would be to throw an error:

function lengthCM(tshirt : TShirt) : number {
  if (tshirt.size === 'small') {
    return 70
  } else if (tshirt.size === 'medium') {
    return 72
  } else if (tshirt.size === 'large') {
    return 74
  }

  throw new Error('this should be unreachable')
}

Remember, when we introduce the size "xlarge", the throw statement becomes reachable. And because this is a runtime error it might be overlooked until the code is already in production. If possible it's always better to raise a type error, because type errors are detected during development.

To do that we introduce this weird little helper function:

function unreachable(witness : never) : never {
  return witness
}

It's actually impossible to call this function without shushing the type checker, because to call it, you have to provide an argument of type never. never is "the empty type". There is no value that has type never. Except in the middle of unreachable code:

function lengthCM(tshirt : TShirt) : number {
  if (tshirt.size === 'small') {
    return 70
  } else if (tshirt.size === 'medium') {
    return 72
  } else if (tshirt.size === 'large') {
    return 74
  }

  unreachable(tshirt.size)
}

Here tshirt.size has type never because there is no value left that it could have at this point. The fact that we have access to a variable of type never is evidence that we are in the middle of unreachable code. So calling unreachable type-checks. BUT if the code ever becomes reachable (when we introduce "xlarge") we get a type error that reminds us to fix lengthCM before deploying to production:

function lengthCM(tshirt : TShirt) : number {
  if (tshirt.size === 'small') {
    return 70
  } else if (tshirt.size === 'medium') {
    return 72
  } else if (tshirt.size === 'large') {
    return 74
  } else if (tshirt.size === 'xlarge') {
    return 76
  }

  unreachable(tshirt.size)
}

Technically it is possible to always call unreachable by maliciously type casting to never:

unreachable("totally a string" as never)

So in practice (and also for readability) I suggest this final implementation:

function unreachable(witness : never) : never {
  throw new Error('this should be unreachable')
}

The Most Unusual Programming Language

Niklas Gruhn — Sun, 20 Mar 2022 18:10:51 +0000

There are many different programming languages and paradigms out there. But I would argue no programming language is so different and unusual as Prolog. It really bends your intuitions for what programming even means. Prolog is a so called logic programming language. There are no loops, no if-else, no variable assignment (at least not in the way you think).

If you had any Prolog exposure so far, then probably through a university course. And I also predict you didn't like it. Prolog is such an unusual approach to programming, that it takes a while to overcome the initial confusion and frustration. In my opinion it's worth it though. Mainly just to broaden your horizon. But you'll find that Prolog is exceptionally well suited for solving certain hard problems, to the point that they become trivial.

Now, instead of doing a standard introduction to the language by explaining all the syntax and all the jargon, I just want to showcase one unique Prolog property: A single piece of code can often serve many different functions.

If you want to run the following Prolog snippets, you don't have to install anything. There is a great online IDE you can use:

Ok. In pretty much any programming language you have a way to append (aka. concatenate) two lists (aka. arrays). Maybe you have a function append that accepts the two lists as arguments...

append([1,2,2], [3,6]).

...and then returns the result list:

[1,2,2,3,6]

In Prolog you do it like this:

append([1,2,2], [3,6], X).

Syntactically, this still looks like a function call but it isn't. This thing does not have a return value. Instead it will use, what looks like a third argument X here, to provide the output. If we run this, Prolog outputs:

X = [1,2,2,3,6]

If you now think: "Oh, that's like in C, where you pass a memory reference as an argument and ..." NO!

append describes a logical relation between three things: the start of a list, the end of a list and the list as a whole. We can put a capital X somewhere and ask Prolog: "What would X have to be to make this true?". For example we could also do this:

append([1,2,2], X, [1,2,2,3,6]).

and Prolog outputs

X = [3,6]

Now we can already use append for two seemingly very different purposes. Concatenating two lists; and also removing a chunk from the beginning of a list. In other programming languages you usually have a separate implementation for this (sometimes called stripPrefix). We can take it further:

append(X, [3,6], [1,2,2,3,6]).

gives

X = [1,2,2]

We can pretty much put the X anywhere we want:

append([1,2,2], [X,6], [1,2,2,3,6]).

X = 3

We don't have to use X at all actually:

append([1,2,2], [3,6], [1,2,2,3,6]).

true

So we can also use append to simply check that the third list is in fact the concatenation of the first two lists. Also something that would usually require a separate function (isAppend maybe?).

We can also use X multiple times:

append([1,2,2], [3,6], [1,X,X,3,6]).

X = 2

Here we ask: "What is this item that appears twice in the result list?". Of course, this kind of query doesn't have an answer in all situations. If we rephrase the question like this:

append([1,2,2], [3,6], [1,X,2,X,6]).

false

then there is no answer and the query fails. Again, don't think of false here as the "boolean return value" of this. It's just how Prolog denotes that this query has no solution.

However, if we do this:

append([1,2,2], [3,6], [1,X,2,Y,6]).

We get an answer again:

X = 2,
Y = 3

X and Y are called variables. Think of them as holes that can be filled in different ways. It's Prologs job to figure out what these different ways are.

In general, everything that starts with a capital letter is a variable. Instead of X and Y we could also use more expressive names:

append(Prefix, [3,6], [1,2,2,3,6]).

Prefix = [1,2,2]

Now, at this point Prolog might look more like an equation solver than a general purpose programming language. Let me get back to more obviously useful applications. What other typical list operations can we implement with this?

JavaScript has pop() to remove the last element of a list; and push() to add a new element at the end of a list. In Prolog they are the same. The Only difference is, where you put the variables:

append(ListPopped, [ToRemove], [1,2,2,3,6]).

ToRemove = 6,
ListPopped = [1, 2, 2, 3]

and

append([1,2,2,3], [6], ListPushed).

ListPushed = [1, 2, 2, 3, 6]

JavaScript also has shift() to remove the first element of a list; and unshift() to add a new element at the beginning of a list. Again, in Prolog it's all the same:

append([ToRemove], ListShifted, [1,2,2,3,6]),

ToRemove = 1,
ListShifted = [2, 2, 3, 6],

and

append([1], [2,2,3,6], ListUnshifted).

ListUnshifted = [1, 2, 2, 3, 6]

Let's go deeper.

What do you think happens, if we run following program?

append(X, Y, [1,2,2,3,6]).

We're essentially asking: "What are the two lists I have to append to get [1,2,2,3,6]?". Well, there are multiple ways to do it, right? Initially, Prolog gives the slightly un-insightful answer:

X = [],
Y = [1,2,2,3,6]

but if you run this query in the web IDE that I mentioned earlier, you'll notice that Prolog allows you to generate more answers:

Eventually, Prolog generates all possible ways to split a list. At the end Prolog outputs false because there are no more possible answers.

In some programming languages you have a function maybe called splitAt to split a list at a specific index. How can we achieve that? Say we want to split the list at index 3. We would expect the answer:

X = [1,2,2],
Y = [3,6]

At the moment we split the list at every possible index. We get multiple answers because we pose a very general question. If we can make the question more specific, we get a more specific answer. One way to do it, is to insist that the prefix list X has length 3. In Prolog, we can relate a list to it's length via length:

length([1,2,2], Len).

Len = 3

We can utilise length together with append as follows:

length(X, 3), 
append(X, Y, [1,2,2,3,6]).

Here we ask: "What is the list X of length 3 and the other list Y that together form [1,2,2,3,6]?".

(I know I'm glossing over a lot of details here. I hope it's still enough to get a feel for logic programming.)

Running this, we get the intended (single) answer:

X = [1,2,2],
Y = [3,6]

Together with length we can also implement other common JavaScript functions like indexOf, lastIndexOf, slice, splice. I would have to explain a tiny bit more syntax though, which, I fear, is a more confusing than helpful for now (but if you're interested: there you go).

To wrap it up, I'm going to show you how append is implemented. I don't expect you to understand it. Especially because it's recursive, which already is kind of mind bender on its own. I just want you to appreciate how ridiculously short this implementation is:

append([], Suffix, Suffix).
append([First|Rest], Suffix, [First|List]) :-
    append(Rest, Suffix, List).

3 lines of code! This implementation barely exists and yet it can be used for many different purposes.

I hope I could get across some of the appeal of logic programming. If you are interested in actually learning the language, I recommend the Power of Prolog.

What makes a programming language Turing complete?

Niklas Gruhn — Sat, 25 Jan 2020 14:47:05 +0000

Turing completeness is a concept from theoretical computer science. It tells you how powerful a programming language is. Not in terms of performance or maintainability or how rich its ecosystem is. A programming language is Turing complete if you can implement any possible algorithm with it.

Think for example of pure HTML. You simply can not implement merge sort with HTML (add CSS and you can, haha!). Thus, HTML is not Turing complete.

Now you might think you have to get clever to design a programming language capable of running any possible algorithm. Especially because most introductions to Turing completeness are pretty math heavy. However, most programming languages out there are Turing complete and if you were to create your own programming language you would probably make it Turing complete by accident.

In fact a lot of stuff that's not even a programming language later on turned out to be Turing complete. For example

Yes, that means you can entirely implement Googles search algorithm with PowerPoint animations.

That sounds crazy, right? How am I supposed to even... you know... make HTTP requests and so on. But that misses the point. Turing completeness is about something much deeper. Whether or not you can make HTTP requests or access the file system is not a property of the programming language itself. It's a question about the APIs that are provided with it.

Think of JavaScript. In the browser you don't have direct access to the file system. In Node.js you have. Same programming language; Different APIs.

Let's dive a little bit deeper into what really distinguishes Turing complete and non-Turing complete programming languages.

Consider the following programming language with only these syntax features:

n = 1 + 1

loop n:
    # do something n times

We can use addition, variable assignment and a simple loop. That's it! Also no Strings no other data types; Only positive integers. For the loop the number of iterations is fixed in the beginning; No matter what happens inside! So even this:

n = 10

loop n:
    n = n + 1

runs exactly 10 times. Not more not less.

With this programming language we can already implement nearly everything.
We literally don't need anything else. Not even the other arithmetic operators (-, *, /). We can emulate them all with just loops and addition.

An if-else-block like this:

if n > 0:
    # ...   
else:
    # ...

can be emulated like this:

n_if = 0
n_else = 1

loop n:
    n_if = 1
    n_else = 0

loop n_if:
    # ...

loop n_else:
    # ...

Try to digest what’s happening here. If n = 0 the first loop runs 0 times. Thus n_if stays 0 and n_else stays 1. Now we also skip the second loop (which represents the if-case) and run the third loop once (which represents the else-case). Do you see what happens when n > 0?

But how on earth can you do subtraction using addition?

x = x - 1

The trick is to increment another variable until you reach x but stop one incrementation earlier:

y = 0

loop x:
    x = y
    y = y + 1

If you want to subtract 10 instead of 1, you have to do this whole process 10 times.

Of course it's ridiculous to program like this but remember that we don't care about performance or readability. We are just interested in what's possible in principle.

Our programming language is very capable but notice that it's impossible to make infinite loops. We can use multiple loops, we can use nested loops but each loop will always have a fixed and finite number of iterations. Thus, it's completely impossible to make an infinite loop.

That's why this language is not Turing complete.

Let's introduce a new kind of loop to our programming language:

for i until n:
    # ...

i is incremented after each iteration and the loop continues as long as i < n.

Now, we can make infinite loops. Just keep reseting i so it never reaches n:

i = 0

for i until 2:
    i = 0

Our programming language just became Turing complete! Even if we are restricted to only use the for-loop once in an entire program, the language is still Turing complete.

Infinite loops are not very impressive. Most of the time we probably want to avoid them. What really makes the for-loop powerful is that we can control how long a loop runs from within the loop itself.

A program somewhat controlling it's own flow. That's the key feature that makes a programming language Turing complete. By the way, we don't necessarily need loops for that. The same thing can be achieved with recursion, GOTO-statements or a thing called the Y combinator, which is maybe the most primitive concept that can still deliver Turing completeness.