Lambda the Ultimate

A regular user of groklaw, the legal blog that discusses the SCO vs IBM litigation and related matters (including some generic aspects of computer science and intellectual property law), has written a paper entitled Explanation of Computer Theory for Lawyers, designed to educate legal practitioners on the subject of computability theory, and how it might apply to IP law. The paper was written as a reaction to the oral arguments conducted Monday before the Supreme Court of the United States in the Bilski case, which many observers expect to eliminate so-called "business method patents" from patentable subject matter in the US, and may have an effect on software patents as well.

While it does contain some legalese, it's actually quite useful as an introduction to the topic for other laypersons or students in CS or mathematics. It provides a high overview of the topic--eschewing many details that a praticing computer scientist would need to know, but it's an interesting read nonetheless.

Available here.

Go is a new programming language to come out of google and this thread on Google discouraging python internally for new projects seems more than just coincidence.

Go is an attempt to combine the ease of programming of an interpreted, dynamically typed language with the efficiency and safety of a statically typed, compiled language.

By combining dynamic features, safety, garbage collection and efficiency in a single language and environment, Go claims to remove the reasons why programmers end up building systems using multiple languages. A brief look at Go shows strong C origins with nice support for "goroutines" - essential sequential processes communicating using channels. I don't quite get the "safety" claim of the language since you can take the address of an uninitialized variable in Go. It could qualify as a "C with concurrency" language I think.

Go already has a great set of packages that should make it immediately usable as a pragmatic language. (The terse package names are very reminiscent of Erlang's package structure.) It even has a package for interfacing with Google Native Client (NaCl) for audio/video access.

(minor edits)

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.

Atomic Install from Bracha's blog.

I'm happy to see people talking about this, mostly because it's a pet topic of mine. I think too much ink has been spilled trying to shoehorn "dynamic languages" (by which I mean the usual suspects: Smalltalk-esque, mostly, and Python, PHP, etc.) into the vocabulary and mindset of type theory. Meanwhile, the operational model of these languages is really fundamentally different, and they are mostly quite similar: the semantics defines some run-time data model for programs, and then the program updates that model, usually in a fairly straightforward procedural way. In this sense, most of these languages can really be viewed as data description languages in disguise. Ruby is a great example of this: all of it's OO constructs are best viewed as syntactic sugar (semantic sugar?) over a fairly simple set of hashtable updates.

(Of course, the runtime data model may be abstract, as in JIT compiled code, and the runtime may not need to actually build and maintain it in a naive way, but that's hidden from the programmer.)

Anyway, given the above, it has for a long time struck me that a better direction for providing safety and static checking in such languages may be to borrow techniques from transaction processing. One might define suitable notions of data consistency and then insist that at particular semantic checkpoints, those consistency properties are guaranteed to hold. Atomic install is exactly what one such a mechanism might look like.

Is there work in the PL literature on this topic?

I'm reading Bolingbroke and Peyton Jones' excellent paper Types Are Calling Conventions, and following along by building a quick-and-dirty interpreter for their proposed intermediate language.

There are a couple of options for how to structure the branching construct in such an intermediate language, and I'm curious if anyone has explored the advantages and disadvantages. Bolingbroke and Peyton Jones' have a case expression (branching on values only, since the whole language is in ANF and the idea is to make strictness/laziness explicit) and a very simple pattern language (a wildcard, literals, and unwrapping a single layer of data constructor binding it's arguments), along with an operational semantics that (if I'm reading it correctly) requires evaluating the list of alternatives in order.

Is this easier to work with than an if/then/else expression? Is it to be preferred simply because it doesn't require distinguishing a Boolean type in the intermediate language?

It's clearly equivalent and easy to understand either way, but I'm wondering if one or the other makes it easier to express common optimizations/transformations. Are there other sensible options besides these two?

William Cook gave an interesting speech at ECOOP 2009. When discussing his career path, he touches on PLT research,

One thing I learned is that programming languages is a very small research area. As a grad student I thought we were big, because everyone in knew did it. But I found out that we are small, smaller perhaps than database research. We are also very fragmented, into functional, OO, typed and untyped, etc. This tends to lead dilute our influence on the community, I think.

differences between academia and industry

Academia is like page-rank: your value is defined by what everybody else thinks of you. And what you think of everybody else contributes to (or subtracts from!) their net academic worth. It is a closed hermetic self-referential system. The commercial value system is obviously different: it's all about money. In a way this is similar to page-rank as well. The difference is that the money comes from outside the community, from customers.

and a few other PLT morsels that might interest LtUers.

William Cook was the prinicpal lead for creating AppleScript. His HOPL paper was discussed on LtU before but I can't currently find the reference.

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?

Suppose a small language with a few primitive types (number, boolean, string) and first-class procedures from and to these types with arbitrary but fixed arity, and the usual syntax (if, let, top-level definitions), but without type declarations. And suppose that the types of all primitive procedures (which are monomorphic) are given, and so is the type of the top-level procedure ("main", a procedure that is not invoked by any procedure, also monomorphic). The language is strict, if it matters.

What I'd like to have is an algorithm that can find the unique monomorphic type of all other procedures in a closed program, or prove that there is none. For example, in main = λ() f0; f = λ(x) gx; g = λ(x) fx, the procedures f and g have no unique monomorphic type, despite being Hindley-Milner typeable. So far I have figured out how to type a fair number of special cases, but I have no clue when to stop looking, or what to do when I run out of heuristics. It's definitely important that procedures can have procedure-valued arguments whose exact types (not merely the fact of being a procedure) must be reconstructed; without those, the problem is easily solved.

Can anyone help?

(Update: Actually, I'm wrong; that example is typeable. As I said, it's procedure-valued arguments that create problems.)