Snowball: A language for stemming algorithms

Snowball is a small string processing language designed for creating stemming algorithms for use in Information Retrieval.

And here's a sample program.

I am not sure just how exciting this language is, but it has been a while since we discussed a DSL.

Crash-Only Software

(via Val Henson's weblog)

This paper (from HotOS IX) describes a software design approach which seems very close to the design techniques erlang tries to encourage.

ll-discuss's new home

For all those (like me) who didn't get the memo, I just found out that the seemingly defunct ll1-discuss mailing list has in fact found a new home at:

An Interview with Donald Knuth

A very pleasant 1996 interview with Donald Knuth by Jack Woehr of Dr. Dobb's Journal.

Theoretical Pearl: Church numerals, twice!

Ralf Hinze. Theoretical Pearl: Church numerals, twice! Journal of Functional Programming, 2004. To appear.

This pearl explains Church numerals, twice. The first explanation links Church numerals to Peano numerals via the well-known encoding of data types in the polymorphic LC. This view suggests that Church numerals are folds in disguise. The second explanation, which is more elaborate, but also more insightful, derives Church numerals from first principles, that is, from an algebraic specification of addition and multiplication. Additionally, we illustrate the use of the parametricity theorem by proving exponentiation as reverse application correct.

A simple concept is used to demonstrate several interesting and useful techniques.

Functional programming in Java


Vadim Nasardinov pointed out this article, which although pitched at an introductory level, provides a reasonably thorough overview of functional programming possibilities in Java. It focuses on the use of closures and higher-order functions, via Java's anonymous inner classes, and works its way up to "using closures to implement business rules" as one of its concrete examples.

Perhaps a little too introductory for LtU, but articles like this can be a useful starting point when talking to Java programmers who've had little or no previous exposure to FP, or who need some hints about useful ways to apply FP concepts in Java. Using anonymous inner classes to implement e.g. GUI event listeners in Java is common practice, but often, more advanced and useful possibilities are overlooked.

OCaml Release 3.08.0

Objective Caml release 3.08.0 is official and incorporates many improvements. A big thank-you to the OCaml team for this stable release. Those on the bleeding edge of post-3.08 CVS work can follow Xavier's advice.

Reflections on reflection - Henk Barendregt


Here's something to exercise both brain hemispheres. Henk Barendregt needs no introduction for many LtU readers - he literally wrote "the book" on the lambda calculus, and that only hints at the profound impact his work has had on lambda calculus and type theory.

The page linked above lists two overlapping papers, both about reflection:

Reflection plays in several ways a fundamental role for our existence. Among other places the phenomenon occurs in life, in language, in computing and in mathematical reasoning. A fifth place in which reflection occurs is our spiritual development. In all of these cases the effects of reflection are powerful, even downright dramatic. We should be aware of these effects and use them in a responsible way.

A prototype situation where reflection occurs is in the so called lambda calculus. This is a formal theory that is capable of describing algorithms, logical and mathematical proofs, but also itself.

As the first paragraph quoted above implies, the scope of these two papers extends far beyond the lambda calculus, into fields such as biology and meditation. Between the two papers, there's something for everyone:

"Reflection and its use, from science to meditation" is wide-ranging, covering reflection related to living cells, formal languages, mathematics, art, computers, and the human mind.

"Reflection and its use, with an emphasis on languages and lambda calculus", focuses specifically on reflection in formal languages, including combinatory logic and lambda calculus.

Two books

While downtown doing something else entirely I managed to find myself in a bookshop. One of the few bookshops not belonging to a chain; in fact one that was established in 1908. They had some used books, and I managed to find two that were both interesting and cheap (around $6 each): Pascal User Manual and Report by Jensen and Wirth, 1974 Springer (alas only the 3rd edition from 1985) and Performance and Evaluation of Lisp Systems by Richard Gabriel (1985, MIT).

Here's a taste from both.

Wirth and Jensen:

Upon first contact with Pascal, some programmers tend to bemoan the absence of certain "favorite features." Examples include an exponentiation operator, concatenation of strings, dynamic arrays, arithmetiac operations on Boolean values, automatic type conversions and default declerations. These were not oversights, but deliberate omissions. In some cases their presence would be primarily an invitation to inefficient programming solutions; in others it was felt that they would be contrary to the aim of clarity and reliability and "good programming style."


Benchmarking is a black art at best. Stating the results of a particular benchmark on two Lisp systems usually causes people to believe that a blanket statement ranking the systems in question is being made. The proper role of benchmarking is to measure various dimensions if Lisp system performance and to order these systems along each of these dimensions.

Gabriel includes a pertinent quote from Vuaghan Pratt: Seems to me benchmarking generates more debate than information. How true...

I enjoyed the discussion of the various Lisp implementations in chapters 1 and 2. The Tak, Stak, Ctak, Takl and Takr series of benchmarks is enlightening. It shows how easy it is for benchmarks to measure "overheads" you haven't intended to measure, and how to engineer benchmarks to overcome this fundamental problem.

alt.lang.jre @ IBM developerWorks

Welcome to the new series alt.lang.jre. While most readers of this series are familiar with the Java language and how it runs on a cross-platform virtual machine (part of the JRE), fewer may know that the JRE can host languages besides the Java language. In its support for multiple languages (including some that pre-exist the Java platform) the JRE provides a comfortable entry point for developers coming to the Java platform from other backgrounds. It also gives developers who have rarely, if ever, strayed from the Java language the opportunity to explore the potential of other languages without sacrificing the familiarity of the home environment.

This series may become an amusing resource.

The first installment is about Jython.