Where Do Type Systems Come From?
Nice article. I especially liked:<p>&gt; program3 fails because runFunction can only run first-order functions and runFunction is a second-order function – a function that takes a first-order function as a parameter.<p>Here I had no idea that JavaScript implicitly typed `runFunction` that way. That&#x27;s cool.<p>Also, I never thought of &quot;higher-order functions&quot; as breaking into a countable hierarchy of nth-order functions, which is an interesting thought. In Haskell the hierarchy would start off as<p><pre><code>    zerothOrderFunction :: a
    firstOrderFunction :: a -&gt; b
    SecondOrderFunction :: a -&gt; (b -&gt; c)
    SecondOrderFunction&#x27; :: (a -&gt; b) -&gt; c
</code></pre>
In general, an nth-order function is a function which either<p>1. Takes an (n-1)th order function as an input and returns a simple type.<p>2. Takes a simple type as an input and returns an (n-1)th order function as an output.<p>The upshot is that typed programming languages not only catch bugs, but prevent you from legally expressing many non-sensical expressions (analogous to the set theory paradoxes).  For example, consider the expression<p><pre><code>    (\x -&gt; x x) (\x -&gt; x x)
</code></pre>
If you expand this expression, it reduces to itself:<p><pre><code>    (\x -&gt; x x) (\x -&gt; x x) == (\x -&gt; x x) (\x -&gt; x x)
</code></pre>
In a purely untyped language, this expression would be legal. But what would be its meaning? Arguably, it is non-sense, and should be excluded from the set of legally expressible expressions. The way to do this is through a type system. And indeed, if you typed this statement into a Haskell REPL you would get a type error; this statement can actually be proven to be untypable (IIRC).<p>On the other hand, this means that typed systems are in some sense <i>strictly less expressive than their untyped counterparts</i>. It would therefore be interesting if somebody found an expression which was both (i) meaningful and (ii) <i>only</i> expressible in an untyped language. You would then have an argument for untyped languages :-)