Lambda the Ultimate

This whole book by Ulrich Breymann is online (I don't think I've seen this mentioned here before).

Brendan Eich, JavaScript 2 and the Future of the Web, XTech 2006

Motivation:

• Fix problems in JS1 that bug people daily
• A type system to enforce invariants
• Programming in the large
• Support bootstrapping and metaprogramming

Brendan Eich presented these slides recently at a conference on the future of web technology.

Good stuff here, especially if you want to learn more about Ada 2005.

Robert Dewar's talk on Ada 2005 & high integrity systems should be of general interest. The main argument is that quality depends at least as much, if not more, on the language culture than it does on specific language features. Dewar presents some of the elements that contribute to Ada's success in the mission critical world which demands high quality software. Among them: emphasis on readability, static typing, the package construct and the ability to subset the language (e.g., SPARK and RAVENSCAR). The talk isn't about the technical aspects of these features, but on how they influence the way programmers approach their tasks.

Alan Burns discusses the Real time issues in Ada 2005. This revision of the language adds many important features (such as CPU monitoring and accounting, budgeting for the execution time of groups of tasks, and new scheduling polices including non-premeption, round robin, and Earliest Deadline First) to an already rich concurrency model. The non surprising conclusion is that Ada is the best language for RT programming not only on earth, but in the entire universe...

Some of you might be interested to learn that Oz got a basic macro facility.

A bit more information can be found in the mailing list.

Benjamin C. Pierce. The Weird World of Bi-Directional Programming, March 2006. ETAPS invited talk.

This nice set of slides (related to Harmony) begins with a detailed exploration of the design space for lenses (the bi-directional constructs), which is quite fun even if you aren't interested in the the rest of the presentation.

It's hard to convey to people what language design is about. I think these slides are a nice example. The process includes exploring various use cases, trying to come up with reasonable semantics, and specifying these decisions formally.

Don't worry: Types are part of the story, as well...

I was going to post this to the front page, but it's already a Forum Topic. So go there to read about a preprocessor that adds continuations to JavaScript by transforming to CPS (I think).

The subject of type inference for dynamically-checked languages came up in the Buried Treasure thread. A question was raised in that thread having to do with why static type inference in these languages is difficult. Since there's a nascent body of literature which addresses that question, here are a few links to articles and papers about type inference for Python.

A nice overview can be found in Localized Type Inference of Atomic Types in Python, a Master's thesis by Brett Cannon. The whole thesis is relevant, but for an overview of the issues, see Chapter 3, "Challenges of Inferring Types in Python". Chapter 4 summarizes previous attempts involving static inference in Python, including Psyco (previously on LtU) and Starkiller. The limitations of these attempts are briefly addressed.

Type inference solutions for Python invariably involve restrictions to make the problem tractable. The above paper focuses on "inferring atomic types in the local namespace". Another approach is described in Aggressive Type Inference, by John Aycock. Aycock makes an important observation:

Giving people a dynamically-typed language does not mean that they write dynamically-typed programs.

The article offers a type inference approach which exploits this observation. (If the meaning of the above quote isn't clear, I recommend reviewing our mammoth three-part thread on the subject, "Why type systems are interesting", part I, part II, and part III.)

The PyPy implementation of Python in Python (previously on LtU) uses a restricted subset of Python, called RPython, to implement parts of the language. RPython is sufficiently static to be able to support full-program type inference. It is not a "soft" inference approach, and is not designed to be used with ordinary Python programs. The paper Compiling dynamic language implementations covers the approach used for static analysis of RPython. The PyPy Coding Guide, starting at section 1.4 may also be useful.

(It may be interesting to note that the PyPy approach is very similar to that used previously for Scheme 48. The core of Scheme 48 is implemented in PreScheme, a subset of Scheme that supports full-program type inference.)

Finally, Guido van Rossum has a number of blog entries on the subject of adding optional static typing to Python:

• Adding Optional Static Typing to Python
• Adding Optional Static Typing to Python -- Part II
• Optional Static Typing -- Stop the Flames!
• Python Optional Typechecking Redux

If anyone knows of any other good treatments of type inference in Python or similar languages, please post links here.

I have been reading a bit of late on Constraint Programming and thought I'd dump some of the links that have helped me along the way. One problem I find with learning Constraint Programming is that I easily get bogged down in the details of implementation and theory. In basic terms, CP consists of a three stage process: (1) Declare the domain (range) of the variables; (2) Declare the constraints on those variables; and (3) Search for solutions. The 1st and 2nd stages can be combined without too much loss, but there seems to be a general consensus that search should be kept separate as much as possible, since it usually is the most expensive and the least declarative. Most of the resources concentrate on the details about how to go about defining programs in these three stages, as well as giving hints about limiting the combinatorial explosion of the search.

The best tutorial I've found is Finite Domain Constraint Programming in Oz which gives a pretty good practical introduction to the subject. Constraint Programming in Alice is a related work in progress that follows the same general outline. For those who like slide presentations, the lecture notes of Christian Schulte and Guido Tack are good resources. Both Christian and Guido are working on the implementation of Gecode, which is a set of libraries (in C++) that seek to take the model of computation spaces, as first realized in Oz, and extend their reach into other programming languages (Christian uses Java, while Guido uses Alice). For a more detailed look, Christian Schulte's PhD thesis on Programming Constraint Services is an in depth treatise on the use of computation spaces for CP.

One book I've been eyeing is Constraint Based Local Search which uses COMET as the PL. My only hesitation is that I don't quite grok the concept of Local Search - a search method that is supposed to be quite efficient but not guaranteed to find a solution. Anyone care to hit me with a clue-by-four on Local Search?

This just came up in the discussion group,

The OS team at Linspire, Inc. (formerly Lindows) would like to announce that we are standardizing on Haskell as our preferred language for core OS development

Interesting!

A slide presentation on Software ideals and history given in a lecture by Stroustrup and fellow Aggies, turned up in google references to my PL People page. Whatever one thinks of C++ as a language, Stroustrup views on the history of PLs is always an interesting read (I recommend his book the Design and Evolution of C++ for the serious PL enthusiast).