Writing is thinking. To write well is to think clearly. That's why it's so hard.

~ David McCullough

Infinity Plus One


Everyone has, at some point during their childhood, found themselves in a contest to name the largest number. It starts off with perhaps a hundred, or a thousand, then a million, a billion, a trillion. Perhaps the savvy youngsters will know about quadrilions or quintillions.

But at some point, we run out of words for numbers. The argument continues with one-upsmanship. Your friend names a numbers. You tack "plus one" onto the end. They come back with "plus two". Maybe some multiplication gets thrown in there ("a trillion trillion!").

The game gets boring pretty quickly, though. You decide it's time to pull out your trump card: infinity!

Surely, you've won. No one can top infinity. It's bigger than the biggest number, after all. Your friend will have to forfeit.

Or so you think. But they come right back at you: "Infinity plus one!"


Data vs Codata


Infinite lists

OCaml and Haskell are both statically typed functional programming languages. Their type systems are very similar. They both have function types, algebraic data types, higher-order types (list of things, maybe/option types, tuple types). They both support type variants of the Hindley-Milner type inference algorithm.

But in Haskell, one often heralded featured is that data types can be "infinite". Haskellers love to showcase this clever one-linear which produces the fibonacci numbers:

fibs :: [Int]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

The Halting Problem in Javascript


The Specs for Halt

We suppose the existence of a function called Halt. It takes one parameter: a function, we will call f, that takes 0 parameters. Then Halt(f) returns true if the call to f() ever returns a value, and Halt(f) returns false if f() loops infinitely.

An important part of this assumption is that Halt(f) must always return true or false regardless of your choice of f. It must not itself loop.