Lambda the Ultimate

LtU will be taken offline for some time tomorrow (Tuesday 9th) due to a data center move. The downtime could range from a few minutes to a few hours. The exact time this will occur is unknown, but you'll be able to tell because LtU will be unreachable. :-)

A survey about state of the art C compiler optimization tricks, Felix von Leitner, Linux Kongress 2009.

The introduction and the conclusion is quite well put:

• Optimizing == important.
• But often: Readable code == more important

• Learn what your compiler does

  Then let the compiler do it.

• If you do an optimization, test it on real world data.
• If it’s not drastically faster but makes the code less readable: undo it.

That's certainly something that I agree with 110%. And really, that's why a good compilers course is so important, even if the vast majority of students never write a compiler outside of class.

John Hughes talks about his experience with Erlang vs. Haskell in an InfoQ Interview. While the discussions about strict vs lazy, pure vs side effecting, and dynamic vs static typing are interesting he raises a good question for the LtU crowd at the end:

I think functional programming is a very interesting concept for the future and for the present indeed. One of the things I do wonder about though, is when I got interested in the field, the mainstream was probably Fortran and COBOL and even C was fairly new at that time. The functional programming pioneers spoke of an order of magnitude improvement in productivity and I think functional programming has delivered that.

If you compare Haskell programs to C code or even C++ often, they are about an order of magnitude smaller and simpler. The same is for Erlang, those results are being validated in the industry. Where is the next order of magnitude coming from? I wish I had an answer to that question because it's hard to see almost. When you look at a beautiful Haskell program, how could this be 10 times shorter? But I think we need to be asking ourselves that kind of question. If I had a good idea there, I would spend the rest of my career working on it.

So, LtU, where is the next order of magnitude coming from?

Since other posters at LtU have taken an interest in the Fortress programming language in the past, I thought I'd mention that the Fortress team at Sun Labs has started a blog, to post a series of announcements and news items about Fortress. Our goal is to let people know about ongoing technical discussions and decisions, as well as the current status of the implementation. We will also post interesting examples of Fortress code. We hope to put up new posts at least weekly.

So far we have four posts. The first and fourth posts discuss the new wiki markup for tables and images for use in Fortress comments; the second post discusses some changes to the typing rules for conditional expressions that will help them to interact better with coercion. The third post is Jan-Willem Maessen's report on a pure (functional) implementation of the "treap" data structure in Fortress, and the fact that the nascent Fortress compiler can now compile it. Visit

http://projectfortress.sun.com/Projects/Community/blog

or click on the "Blog" item at the right-hand end of the menu bar on the main Wiki page.

1974 talk show style interview with the original developers of APL; complete with plaid jackets and a smoking host.

The Origins of APL Video

I've never used APL but I found the talk to be very interesting. They talk about how APL come about, its evolution and the character set. Worth watching.

The popular Glasgow Haskell Compiler extends the Haskell 98 type system with several powerful features, leading to an expressive language of type terms. In contrast, constraints over types have received much less attention, creating an imbalance in the expressivity of the type system.

In this paper, we rectify the imbalance, transferring familiar type-level constructs, synonyms and families, to the language of constraints, providing a symmetrical set of features at the type-level and constraint-level. We introduce constraint synonyms and constraint families, and illustrate their increased expressivity for improving the utility of polymorphic EDSLs in Haskell.

One of the themes of Barbara Liskov's Turing Award lectue ("CS History 101") was that nobody has invented a better programming concept than abstract data types. William Cook wrote a paper for OOPSLA '09 that looks at how well PLT'ers understand their own vocabulary, in particular abstract data types and concepts that on the syntactical surface blend to all seem like ADTs. The paper is On Understanding Data Abstraction, Revisited.

In 1985 Luca Cardelli and Peter Wegner, my advisor, published an ACM Computing Surveys paper called “On understanding types, data abstraction, and polymorphism”. Their work kicked off a flood of research on semantics and type theory for object-oriented programming, which continues to this day. Despite 25 years of research, there is still widespread confusion about the two forms of data abstraction, abstract data types and objects. This essay attempts to explain the differences and also why the differences matter.

The Introduction goes on to say:

What is the relationship between objects and abstract data types (ADTs)? I have asked this question to many groups of computer scientists over the last 20 years. I usually ask it at dinner, or over drinks. The typical response is a variant of “objects are a kind of abstract data type”. This response is consistent with most programming language textbooks.

[...]

So what is the point of asking this question? Everyone knows the answer. It’s in the textbooks.

[...]

My point is that the textbooks mentioned above are wrong! Objects and abstract data types are not the same thing, and neither one is a variation of the other.

Ergo, if the textbooks are wrong, then your Dinner Answer to (the) Cook is wrong! The rest of the paper explains how Cook makes computer scientists sing for their supper ;-)

When I’m inciting discussion of this topic over drinks, I don’t tell the the full story up front. It is more fun to keep asking questions as the group explores the topic. It is a lively discussion, because most of these ideas are documented in the literature and all the basic facts are known. What is interesting is that the conclusions to be drawn from the facts are not as widely known.

Ralph Johnson posted the list of papers that Liskov mentioned as having influence her.

A good place to start as any, I'd say.

A short comparison (plus some links) of Erlang and Clojure solutions to the simple problem of running a counter in a separate thread.

LP has been mentioned a number of times on LtU but never featured as a topic of discussion in its own right. On the face of it, it seems like an eminently sensible way to program. Why hasn't it taken the whole world by storm? Knuth puts forward Jon Bentley's observation as one possible answer: "a small percentage of the world's population is good at programming, and a small percentage is good at writing; apparently [Knuth is] asking everybody to be in both subsets."

To discuss this and other theories on their merits, a quick refresher on the basics of LP is in order. As usual, the relevant Wikipedia article is informative but bland. As Knuth pointed out, original sources are often best. Here are two good ones:

1. Programming Pearls: Literate Programming by Jon Bentley and Don Knuth; CACM, Vol. 29, No. 5, May 1986. (A bootleg copy available here.)
2. Programming Pearls: a Literate Program, by Jon Bentley, Don Knuth, and Doug McIlroy; CACM, Vol. 29, No. 6, June 1986. (Bootleg copies available here and here.)

The second paper is the more interesting of the two. It contains a literate program by Knuth and a review of the same by McIlroy:

Knuth has shown us here how to program intelligibly, but not wisely. I buy the discipline. I do not buy the result. He has fashioned a sort of industrial-strength Fabergé egg -- intricate, wonderfully worked, refined beyond all ordinary desires, a museum piece from the start.

I, too, buy the discipline for programming in the small but can't really see how CWEB-like systems can be adapted to and adopted by multi-hacker teams working on very large code bases written in a mixture of different languages. Ramsey's Literate Programming on a Team Project enumerates some of the problems.

Can LP be used for anything other than small-to-medium programs written by a single person in a single language?