Reproducing Programs implement Lazy Lists

Along the lines of the quine discussion happening in another thread, Manfred von Thun wrote a new page for the Joy site, Reproducing Programs implement Lazy Lists. This connects nicely with Jeremy Gibbons spigot algorithms paper, one example of which is his IOHCC 2004 submission PiSpigot.

JavaScript and domain specific Languages

Interesting sounding projects...

I am busy, but where are all the other editors? Step up to the plate, and post something!

Embedded Interpreters

This is a tutorial on using type-indexed embedding projection pairs when writing interpreters in statically-typed functional languages. The method allows (higher-order) values in the interpreting language to be embedded in the interpreted language and values from the interpreted language may be projected back into the interpreting one. This is particularly useful when adding command-line interfaces or scripting languages to applications written in functional languages. We first describe the basic idea and show how it may be extended to languages with recursive types and applied to elementary meta-programming. We then show how the method combines with Filinski's continuation-based monadic reflection operations to define an extensional version of the call-by-value monadic translation and hence to allow values to be mapped bidirectionally between the levels of an interpreter for a functional language parameterized by an arbitrary monad. Finally, we show how SML functions may be embedded into, and projected from, an interpreter for an asynchronous pi-calculus via an extensional variant of a standard translation from lambda into pi.

Another paper from Nick Benton.

Like the previous one this paper is dense and detailed, but this time there are some useful practical techniques that may come handy next time you build a DSL in a functional language.

Nick Benton: Simple Relational Correctness Proofs for Static Analyses and Program Transformations

We show how some classical static analyses for imperative programs, and the optimizing transformations which they enable, may be expressed and proved correct using elementary logical and denotational techniques. The key ingredients are an interpretation of program properties as relations, rather than predicates, and a realization that although many program analyses are traditionally formulated in very intensional terms, the associated transformations are actually enabled by more liberal extensional properties. We illustrate our approach with formal systems for analysing and transforming while-programs. The first is a simple type system which tracks constancy and dependency information and can be used to perform dead-code elimination, constant propagation and program slicing as well as capturing a form of secure information flow. The second is a relational version of Hoare logic, which significantly generalizes our first type system and can also justify optimizations including hoisting loop invariants. Finally we show how a simple available expression analysis and redundancy elimination transformation may be justified by translation into relational Hoare logic.

Not really exciting as such, but this technical report version of the POPL 2004 paper includes most of the proofs, which some might find helpful.

Python Optimization Surprises

This weekend, I took another crack at trimming microseconds off the common-case path for generic function execution, and succeeded in dropping the excution time from 13.2 microseconds to just over 9.8. (Which is about 9 microseconds overhead added relative to a hand-optimized Python version of the same trivial function.) Along the way, however, I realized a couple of surprising things about Python performance tuning.

An amusing story that tells you something about Python's implementation.

The discussion of closures is of particular interest...

An Introduction to Jython

Getting sick of Python posts by now? Sorry...

A large part of this presentation consists of a series of code examples showing how something is done in pure Java versus a Jython version. A nice illustration of the differences between the languages (did anyone say explicit static typing?) and about their different abstraction facilities and domain specific abstractions (e.g., builtin dictionaries and list comprehensions).

Analyzing these examples may be fun exercise idea for those of us teaching PL courses.

Implementation of FPL

Simon Peyton Jones book on the Implementation of Functional Programming Languages, circa 1987, is available online.

This book is about implementing functional programming languages using lazy graph reduction, and it divides itnto three parts.

The first part describes how to translate a high-level functional language into an intermediate language, called lambda calculus, including detailed coverage of pattern-matching and type checking. The second part begins with a simple implementation of the lambda calculus, based on graph reduction, and then develops a number of refinements and alternatives, such as super-combinators, full laziness and SK combinators. Finally, the third part describes the G-machine, a sophisticated implementation of graph reduction, which provides a dramatic increase in performance...

via the Haskell mailing lists. I've seen lots of references to this work, as it was one of the seminal works in the development of the Haskell programming language. But I can't find where it was directly discussed on LtU before.


A SPARK program has a precise meaning which is unaffected by the choice of Ada compiler and can never be erroneous.

From the examples in the chapter, I thought it looked surprisingly simple to use - comparable to adding contracts in DbC, for example. I guess the analysis requires a little more effort?

This has been mentioned only in passing by Ehud so I hope it's worth a post of its own. And I'm amused by the idea that Ada is a sloppy, ill-defined language... ;o)

Use Continuations to Develop Complex Web Applications

An introductory article from IBM developerWorks on Cocoon, continuation-based (sometimes called "modal") web applications, and such.

If you've ever developed a non-trivial Web application, you know that development complexity is increased by the fact that Web browsers allow users to follow arbitrary navigation paths through the application. No matter where the user navigates, the onus is on you, the developer, to keep track of the possible interactions and ensure that your application works correctly. While the traditional MVC approach does allow you to handle these cases, there are other options available to help resolve application complexity. Developer and frequent developerWorks contributor Abhijit Belapurkar walks you through a continuations-based alternative that could simplify your Web application development efforts.

via comp.lang.scheme

PyPy wins a funding contract with the EU

PyPy aims at producing a simple runtime-system for the Python language,

Our primary Scientific objective is to investigate novel techniques (based on Aspect-Oriented-Programming code generation and abstract interpretation) for the implementation of practical dynamic languages, breaking the compromise between flexibility, simplicity and performance trade-offs and expanding the range (small-to-large) of directly supportable runtime platforms.

XML feed