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

~ David McCullough
 

Infinity Plus One

2014年09月21日

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!"

read more...
qed

Data vs Codata

2014年01月12日

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)
read more...
qed

The Halting Problem in Javascript

2013年09月12日

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.

read more...
qed