Tuesday, March 20, 2012

Optimization is just a side benefit.

A corrolary to our previous definition of type systems as principally ways to prove correctness: many discussions programmers have about type systems seem to focus on the runtime cost of type checking, as if that were the primary issue. Common Lisp has a great answer to that in its optional type declaration system¹ and the powerful inference and inlining done by compilers such as CMU Python.²

To a typeful programmer, runtime optimizations are an interesting side-effect of types, but ultimately beside the point. The correctness-proving features have a much greater impact on how you think about data structure, algorithm, and API design, approaches to testing, etc.

Common Lisp's type declarations are very nice, but they are little help in broadly proving program correctness, which is mostly the point of typeful programming.


① The special form the offers a glimpse into this system.

② See the CMUCL FAQ question on Python for explanation.

Sunday, March 18, 2012

Type systems prove things about your programs.

Typeful programmers don't seem to see types the way Common Lispers or C programmers do. Instead, type systems are how you can partially prove the correctness of your program.

Thinking of types as proof systems offers several useful intuitive analogies. It is not just more rigorous testing; it's in a whole other universe from testing. Scientifically, we don't accept a hypothesis that seemed to work when we tried it with a few different things, we demand proof, which is qualitatively different.

Taking the time to prove your program's correctness may take more time than simply writing the program in many cases. (This is a complex issue I will return to later.) However, even in those cases, the benefit of the rigor of proof may outweigh the cost.

It may be that, when you are writing a program, you can intuitively see that your program is somewhat correct, but you don't know how to prove it. Well, if you can't prove it, should you, or anyone else, really trust your intuition? If you do prove it, no trust is necessary; all you need to do is trust the proving framework, the type system, to disallow nonsense, and the fact that the type system passed the program is enough to satisfy everyone that the proof is sound, so far as it goes.

Finally, type inference is “proof assistance”. Typeful compilers come with both proof checkers and proof assistance, but these, again, deserves separate posts.

Accordingly, I will often use the language of “proof” when talking about using type systems.

A Lisper's perspective on “new hotness” typeful programming languages

A few years ago, I didn't care about functional programming. A year ago, it would have been unthinkable for me to work with a bunch of type system fanatics. I've been a Lisper for a long time, very much disliking anything breaking the Lisp mold, and it was just a little over a year ago that I learned, and came to appreciate, Haskell and the advantages it provides.

This is how I perceive the modern world of typeful programming, as a programmer who most naturally thinks in Lisp, with some experience in that area and a relatively newfound appreciation for it.

I won't discuss the benefits of immutable, persistent data structures, except where it naturally comes up in discussion of types. Clojure demonstrates that you don't need fancy type systems to get many of the advantages of immutable data. Were I to take on a large project in Common Lisp now, I would certainly try to use Funds or some implementation of Okasaki's data structures wherever beneficial, but I don't care to discuss that.

I will be similarly mute on the benefits of Haskell-flavored normal-order evaluation, for similar reasons. They will come up more often in relation to type systems, though.

I've broken up the discussion into simple assertions and discussion of them. You won't find rigorous logical backing of my statements, merely the empirical and anecdotal, because the former has already been done quite well elsewhere, and won't be as fun for me.

Here I keep links to articles already posted. The unlinked articles have been written, but not posted yet, for the sake of cadence.

  1. Type systems prove things about your programs.
  2. Optimization is just a side benefit.
  3. Type systems help with “a class of errors”: factual, but not true.
  4. C and Java do not have good type systems.
  5. With a type system, whether you can write a program depends on whether you can prove its correctness.
  6. “Inference” is “proof assistance”.
  7. Some type systems are much better than others.
  8. More type system features can make proofs harder to write.

Since last time

I'm going to diverge briefly from my usual focus on technical matters. Since my last posting here, several things have changed:
  1. I moved to Fort Lauderdale, FL to work for Velocitude, a company building generalized mobile web support in Clojure, a dialect of Lisp with special support for programming with immutable data structures, concurrency, and other functional programming goodness.
  2. Velocitude was bought by Akamai, and I moved to the Boston area to continue with the same work.
  3. Back in, oh, January or February 2011, I took the time to learn Haskell properly, including how to think in its type system.
  4. I joined S&P Capital IQ a couple months ago, to work with some hardcore type system fans in Scala.

I just wanted to provide some context for what follows, and will dwell no more on such matters.

Friday, September 25, 2009

De Icaza "civil and polite"?

In response to RMS: De Icaza Traitor to Free Software Community:
Kudos to De Icaza for remaining civil and polite despite such a low blow from RMS.
While I certainly think that RMS went a little too far in his comments, it's unfair to overlook the highly personal attack with which De Icaza opens his post:
I want to say that God loves all creatures. From the formidable elephant to the tiniest ant. And that includes Richard Stallman.
I'm not familiar with De Icaza's religion, but it's common knowledge in the Free Software community that RMS is an atheist. Many atheists, especially in the United States, find proselytizing of the "God loves you" sort to be highly insulting. In this situation, especially, it feels like De Icaza is trying to evoke the popular image among the religious of the Bitter Atheist, the sort who really believes in god but hates him so pretends he doesn't exist, vs. the Friendly, Reasonable Theist, who is just trying to get the Bitter Atheist to see the truth.

Furthermore, the widely quoted comments from RMS were made in the setting of a spoken forum. Once the words are out of your mouth, there's no Backspace key to take them back, and we already know that RMS can get quite emotional about issues affecting the Free Software community.

But De Icaza had a chance to consider his response carefully (he was, after all, writing a blog entry), and he opted to publicly, albeit indirectly and with some subtlety, attack RMS's lack of religion. Being polite doesn't make you right, but even if it did, who was really being less "constructive and civil" here?