Lambda the Ultimate

Google's MapReduce Programming Model -- Revisited. Ralf Lämmel.

MapReduce is a programming model (and an associated implementation) used at Google for processing large amounts of input data (such as millions of documents) and generating keyed or indexed query results (such as the indexes used for Google's web search). The programming model is stunningly simple, and it allows the programmer to largely abstract from the parallel and distributed execution of the data-processing computations. Parallel execution is promoted by the assumed skeleton of MapReduce computations. Load balancing, network performance and fault tolerance are taken care of by the MapReduce implementation.

We revisit the MapReduce programming model in an attempt to provide a rigorous description of the model. We focus on the key abstraction for MapReduce computations; this abstraction is parameterized by the problem-specific ingredients for data extraction and reduction. We use Haskell as a lightweight specification language to capture the essence of MapReduce computations in a succinct, executable and strongly typed manner. Our study substantiates that clarity, generality and correctness of designs (or the presentations thereof) are easily improved, if modest functional programming skills are put to work.

This is a fun example of type-directed exploration and prototyping, and pokes some gentle fun of Google's (ab)use of standard terminology. It's neat to get a glimpse into the programming process of a very experienced Haskell programmer.

(From the forums.)

While on the subject of quantum computing, I think some of you might enjoy playing with this Scheme DSEL for quantum computation from André van Tonder.

There've been a couple of threads recently about safety-critical code (Rules for, and in real-time Java). Safety-critical code necessarily includes careful handling of failure situations. Or does it? Here's another take on failure handling, from the opposite direction:

Enhancing Server Availability and Security Through Failure-Oblivious Computing (Rinard et al., 2004) was originally presented at OSDI '04, but hasn't previously been featured here:

We present a new technique, failure-oblivious computing, that enables servers to execute through memory errors without memory corruption. Our safe compiler for C inserts checks that dynamically detect invalid memory accesses. Instead of terminating or throwing an exception, the generated code simply discards invalid writes and manufactures values to return for invalid reads, enabling the server to continue its normal execution path.

We have applied failure-oblivious computing to a set of widely-used servers from the Linux-based open-source computing environment. Our results show that our techniques 1) make these servers invulnerable to known security attacks that exploit memory errors, and 2) enable the servers to continue to operate successfully to service legitimate requests and satisfy the needs of their users even after attacks trigger their memory errors.

The paper includes descriptions of how this technique was applied with good results to servers such as Apache and Sendmail, as well as to client programs such as Pine, Mutt, and Midnight Commander.

The paper also raises concerns about the potential for such techniques to create a bystander effect (although the term moral hazard might be more appropriate here), influencing programmers to be less careful about error handling because they have a safety net.

This work was performed on programs written in C, and there's a temptation to think that the approach is only applicable to memory-unsafe languages. However, there's a connection here to the approach used by some of the classic shell scripting languages and their descendants such as Perl, in which certain kinds of failure are silently tolerated in the interests of keeping the program running. The approach could also have potential applications in other memory-safe languages, providing the potential for higher-availability programs, as noted in the paper's conclusion.

While most language implementors aren't going to rush to incorporate failure-oblivious approaches in their languages, the positive results obtained from this work are thought-provoking, and could inspire other less traditional but effective ways of handling failure.

Registration is now open for the 9th Annual ICFP Programming Contest. The ICFP contest is an event that traditionally raises interest in the LtU community.

A more detailed announcement found in the forum mentions that this year's theme is "computational archaeolinguistics." Intriguing.

The first 10 Prolog Programming Contests took place in Ithaca (1994), Portland (1995), Bonn (1996), Leuven (1997), Manchester (1998), Las Cruces (1999), Paphos (2001), Copenhagen (2002), Mumbay (2003) and Saint-Malo (2004). The contest organisers have written this book, containing the (slightly reworked) questions and an answer (in Prolog of course) for each question... The book is now also freely downloadable on this page.

For your enjoyment...

Microsoft recently announced the Microsoft Robotics Studio, which aims to offer end-to-end robotics development environment customer technical preview for hobbyist, academic, and commercial developers.

This isn't a programming languiage item per se, of course, but I think fun platforms sometimes offer intereseting opportunities (which is why I posted on LEGO Mindstorms before), and I wanted to flush the RSS feed with a new item to test if it's working properly.

The Semicolon Wars
Brian Hayes

A laypeople's introduction to the world of programming languages from American Scientist. Includes some history, a high-level overview of different programming paradigms, some guesses at which differences make a difference, some Dijkstra, and some cheap shots at zealots.

Regular LtU readers won't find anything new here, but it's a good article, and it's always nice to see something like this for the general reading public.

This is the first sentence of this story. This is the second sentence. This is the title of this story, which is also found several times in the story itself. This sentence is questioning the intrinsic value of the first two sentences. This sentence is to inform you, in case you haven't already realized it, that this is a self-referential story, that is, a story containing sentences that refer to their own structure and function. This is a sentence that provides an ending to the first paragraph.


This is the link to the story

foldl.com and foldr.com are two fun websites that may just help you wrap your head around left and right folds. They are the product of Oliver Steele, designer of (Open)Laszlo.

I have characterized myself recently as a recovering typoholic and a convert to Visual Basic and in my various talks I use the paper on type-indexed rows that I wrote together with Mark Shields as the prime example of how deep you can fall as an addict to static typing.

As many of us undoubtedly do every once in a while, I was egosurfing for “typoholic”; vague hoping it would be a Google wack. However, much to my astonishment the first hit is actually our paper on type-indexed rows (alternatively type in typoholic on the Google homepage and hit “I’m feeling lucky”). That page does not contain the word "typoholic" and until now there were no links pointing to it!

If you ask me, this is pure voodoo. Perhaps I should start wrapping myself in aluminum foil to protect me against the Google mind control waves.