Lambda the Ultimate

Gabriel Dos Reis and Bjarne Stroustrup. Specifying C++ Concepts. POPL06. January 2006.

We discussed work on improving the C++ template facility before. The basic notion in this paper is concepts, a type system for templates, which will increase the expressiveness of template parameters, and improve compile time error messages. Separate compilation is also an important concern.

I am happy to report that Ada is mentioned, which is a good sign. However, I think there's room for a more detailed discussion and comparison. Other LtU readers will be glad to see that Haskell mentioned as well...

Jeremy Gibbons (2006). Fission for Program Comprehension. Submitted for publication.

Fusion is a program transformation that combines adjacent computations, flattening structure and improving efficiency at the cost of clarity. Fission is the same transformation, in reverse: creating structure, ex nihilo. We explore the use of fission for program comprehension, that is, for reconstructing the design of a program from its implementation. We illustrate through rational reconstructions of the designs for three different C programs that count the words in a text file.

The paper works through the examples meticulously and highlights their recursion schemes. The claim is that the three different wordcount programs might all have arisen from the same high-level design, namely the composition length o words.

The more audacious claim is that [i]f one accepts the claim that design patterns in object-oriented programming correspond to recursion patterns in generic functional programming, then this is further support for Johnson’s slogan that ‘patterns document architectures’.

This is an incomplete draft of a guide on PLT Scheme contracts. Apparently it changes daily, but you might still want to take a look.

(via PLNews)
Thoughts on Language Design

Computers with multiple processors are becoming more and more common. We need programming languages that support the use of multiple threads of control. [...] In such a context, the organizing principles of structured programming may not always be appropriate. I'm not talking about avoiding goto. (Java has no goto statement.) I'm talking about sequencing, if-then-else, and loops.

OS and web search vendors are merging desktop search into their offerings. Vendor solutions vaguely worry me. They seem too focused on the home PC and not on business needs, while needlessly bypassing RDF. There's also vendor lock, bad EULAs, privacy negligence, and lost boundaries between OS, applications, and data - proprietary black boxes tempting us into dependence.

That thinking led me to the open-source Mind Raider program. It's one of the few that makes RDF useful for normal people. It compares to Chandler but focuses less on email and calendars. As far as I know, Chandler doesn't expose RDF or even use it, necessarily. However the Mind Raider Big Picture shows similarity to Chandler's vision.

So why should this stuff matter to LtU. Well, compare formal organization between data that only computers inspect and data that people use daily. Many database systems exist to store data in the former category. Employee and customer address data serves little purpose beyond printing paychecks and shipping labels. A human will not care about values except that they not be empty. Granted that people do use databases to track sales figures and other aggregates. Still even those folks use data in the latter category: stray thoughts and reminders, sticky notes, social and business correlations, restaurant napkin sketches, collaborative data, recorded conversations, news clippings. A large cloud of miscellany doesn't rise to the level of application documents or the formality of enterprise systems.

Few systems exist to aggregate and organize that stuff. If your brain suffices, then good for you. The rest of us need a crutch. Some people use spreadsheets to store lists simply because there's little else available. I've used software which imitates sticky notes on screen. It leaves much to be desired. There are dozens of little programs for narrow data types - address books, internet bookmark apps, password managers, photo albums, etc. How do you tell the address book that the photo album has pictures of the guy, and that his web link lives in the bookmark manager? Right now, you don't. And programs never organize data just the way you want. Besides, exceptions to the common format always arise. So the problem is not just searching documents and email, nice as that is, but organizing human details in useful ways. Moleskin notebooks and Dictaphones have been around a long while. It's time for cool software.

Somehow RDF seems primed for the role, but it needs less abstract public relations. Raw RDF may not be the ideal presentation but still seems a likely candidate for the underlying data model. Each individual develops a personal ontology (aka "working style" if you will) over years of time. RDF can capture that, but it will take friendly programs like Mind Raider. What do you think?

Lock -Free Data Structures using STMs in Haskell. Anthony Discolo, Tim Harris, Simon Marlow, Simon Peyton Jones, and Satnam Singh. Submitted to FLOPS'06.

This paper explores the feasibility of re-expressing concurrent algorithms with explicit locks in terms of lock free code written using Haskell's implementation of Software Transactional Memory (STM). Preliminary experimental results are presented which show that for multi-processor systems the simpler lock free implementations offer competitive or superior performance when compared to their corresponding the lock based implementations.

The ArrayBlockingQueue class from JSR-166 is the basis for this experiment. A selection of representative methods from the three interfaces supported by this class is reimplemented in Haskell. Two implementations are provided: one using mutexes and semaphores from the IO monad and one based on STMs.

The performance of the two versions is compared and discussed.

Due to recent discussions here on LtU and on the Haskell mailing lists I've compiled a list of links to implementations of monads in various languages. If you know of any that aren't listed here, please submit them in a comment.

• Clean
• Haskell
• Java
• Joy
• OCaml
• Perl
• Prolog
• Python
• Ruby
• Scheme

A longer article with side by side comparisons of the implementations would be interesting, and may help students understand monads by separating them from any one syntax or implementation.

Generalized Algebraic Data Types and Object-Oriented Programming. Andrew Kennedy and Claudio Russo. OOPSLA, October 2005, San Diego, California.

Generalized algebraic data types (GADTs) have received much attention recently in the functional programming community. They generalize the type-parameterized datatypes of ML and Haskell by permitting constructors to produce different type-instantiations of the same datatype. GADTs have a number of applications, including strongly-typed evaluators, generic pretty-printing, generic traversals and queries, and typed LR parsing. We show that existing object-oriented programming languages such as Java and C# can express GADT definitions, and a large class of GADT-manipulating programs, through the use of generics, subclassing, and virtual dispatch. However, some programs can be written only through the use of redundant run-time casts. We propose a generalization of the type constraint mechanisms of C# and Java to avoid the need for such casts, present a Visitor pattern for GADTs, and describe a switch construct as an alternative to virtual dispatch on datatypes. We formalize both extensions and prove a type soundness result.

I've been waiting for awhile for this paper to be available online.

This paper is, of course, related to the other items posted here about GADTs. The examples in the introduction might be somewhat relevant to the recent discussion about the static versus dynamic features of Java, and its type system.

What kind of task is Ragel good for?

• Lexing programming languages.
• Parsing file formats.
• Creating robust custom protocols.
• Checking your "Theory of Computation" homework.

Features

• Describe arbitrary state machines using regular language operators and/or state tables.
• NFA to DFA conversion.
• Hopcroft's state minimization.
• Embed any number of actions into machines at arbitrary places.
• Control non-determinism using priorities on transitions.
• Visualize output with Graphviz.
• Use byte, double byte or word sized alphabets.
• Generate C/C++/Objective-C code with no dependencies.
• Choose from table or control flow driven output.

From this Wired article:

In 1976, computer pioneer Edsger W. Dijstra made an observation that would prove uncanny: "Program testing can be quite effective for showing the presence of bugs," he wrote in an essay, "but is hopelessly inadequate for showing their absence."

Thirty tears later, Dijsta's words have the ring of prophecy. Companies like Microsoft and Oracle, along with open-source projects like Mozilla and Linux, have all instituted rigorous and extensive testing programs, but bugs just keep slipping through. Last month, Microsoft's monthly drop of bug patches included fixes for 14 security holes that escaped prerelease testing, four of them rated "critical."

There's a bit to chew on here, including the by-now-de rigeur misidentification of Java, Python, and Perl as "type-safe languages." But I think the article is valuable in spite of that for its frank admission that even intense testing regimes aren't doing well at addressing serious quality issues. Daniel Jackson, leader of the Alloy project at MIT, is quoted.