Notes

These are very refreshing:

From Hudak et al., “A History of Haskell” [1]:

The fact that Haskell has, thus far, managed the tension between these two strands of development [as a mature language, and as a laboratory in which to explore advanced language design ideas] is perhaps due to an accidental virtue: Haskell has not become too successful. The trouble with runaway success, such as that of Java, is that you get too many users, and the language becomes bogged down in standards, user groups, and legacy issues. In contrast, the Haskell community is small enough, and agile enough, that it usually not only absorbs language changes but positively welcomes them: it’s like throwing red meat to hyenas.

And Alan Perlis [2]:

“I think that it’s extraordinarily important that we in computer science keep fun in computing. When it started out, it was an awful lot of fun. Of course, the paying customers got shafted every now and then, and after a while we began to take their complaints seriously. We began to feel as if we really were responsible for the successful, error-free perfect use of these machines. I don’t think we are. I think we’re responsible for stretching them, setting them off in new directions, and keeping fun in the house. I hope the field of computer science never loses its sense of fun. Above all, I hope we don’t become missionaries. Don’t feel as if you’re Bible salesmen. The world has too many of those already. What you know about computing other people will learn. Don’t feel as if the key to successful computing is only in your hands. What’s in your hands, I think and hope, is intelligence: the ability to see the machine as more than when you were first led up to it, that you can make it more.”

Thanks to Benjamin Russell for pointing these out on the Haskell-cafe list.

[1] Hudak, Paul, Hughes, John, Peyton Jones, Simon, and Wadler, Philip. “A History of Haskell: Being Lazy With Class.” San Diego, California: The Third ACM SIGPLAN History of Programming Languages Conference (HOPL-III) (2007): 12-1 - 12-55, 2007. http://research.microsoft.com/en-us/um/people/simonpj/papers/history-of-haskell/history.pdf

[2] Abelson, Harold and Sussman, Gerald Jay with Sussman, Julie. Structure and Interpretation of Computer Programs, Second Edition. Cambridge, MA: The MIT Press and New York: McGraw-Hill, 1996. http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-3.html

If you assume fixed word length, integers can be sorted in linear time using radix sort. This paper gives a stunningly elegant generalization of this to essentially arbitrary data structures, including lists, sets, bags, etc.:

Henglein, F. (2008). “Generic Discrimination: Sorting and Partitioning Unshared Data in Linear Time”.

Wow. The most interesting aspect of this to me is that it provides some extra hope about the practicality of functional containers. Right now everyone is using hash tables, which are fast but extremely lacking in functionality (e.g., they’re not sorted). In many languages they’re also nondeterministic across multiple program runs for security reasons, which is horrible for debugging. Maybe some future abstraction along the lines of this paper (generalized tries?) will make ordering-based containers competitive with hash tables.

Unfortunately, Henglein notes that efficient implementations of these techniques are heavily imperative, which is fine for sorting but bad for use in flexible containers. I’ll keep hoping.

Note: Containers and tries are mentioned as future work in the paper. There are lots of challenges in the way, but Henglein seems optimistic. I expect that some fairly serious compiler support would be required to make an implementation of these ideas both clean and fast.

Lyre birds are spectacular:

http://www.youtube.com/watch?v=VjE0Kdfos4Y

Thanks for Jiayi for the link. I wasn’t sure it was real at first, so here’s independent confirmation (PBS probably isn’t lying):

http://www.pbs.org/lifeofbirds/songs/lyre.ram

We wish to show that for small $x$, $$\sqrt{1+x}\approx 1+\frac{x}{2}$$ To derive this formula, we use the well known fact that $$(1+x{)}^{\alpha }=\sum _{n=0}^{\mathrm{\infty }}\frac{x^n}{n!}\prod _{k=0}^{n-1}(\alpha -k)$$ The result follows by substituting $\alpha =1/2$ and truncating the series after two terms.

I gave a talk a USF a while back for the Special Lecture Series in Computer Science. The goal was to try to give a flavor for the intuition behind simulation algorithms. I’m not sure I succeeded in doing this coherently, but good practice for the next time.

Here are the slides, in pdf and keynote form. Caution: they are not very self-contained.