Lambda the Ultimate

Parrot 0.2.2 has been released! Parrot is a versatile virtual machine for dynamic languages. Though originally designed for Perl 6, it's power and flexibility has generated a lot of interest in the language development community. Parrot is distributed with a number of sample compiler implementations at varying stages of completion, including partial compilers for common languages like lisp, scheme, tcl and python.

The latest release features grammar and rule support in PGE, the Parrot Grammar Engine. Parrot also comes with utilties that convert PIR (Parrot Intermediate Representation) and PASM (Parrot Assembly) into PBC (Parrot bytecode).

Those who are interested in learning how to implement languages for Parrot should start with the documentation. You may also be interested in my own (extremely feeble) attempt at implementing PIR generators in Haskell and Ocaml.

A Typed, Compositional Logic for a Stack-Based Abstract Machine. Nick Benton. MSR-TR-2005-84. June 2005.

We define a compositional program logic in the style of Floyd and Hoare for a simple, typed, stack-based abstract machine with unstructured control flow, global variables and mutually recursive procedure calls. Notable features of the logic include a careful treatment of auxiliary variables and quantification and the use of substructural typing to permit local, modular reasoning about program fragments. Semantic soundness is established using an interpretation of types and assertions defined by orthogonality with respect to sets of contexts.

Also related to PCC, TAL etc.

The results are in for the 2005 Glasgow Haskell Compiler user survey, with a summary and all the raw data. The comments were the highlight for me; see for instance Applications I use GHC for.

(Previous LtU mention)

Accurate step counting. Catherine Hope and Graham Hutton.

Starting with an evaluator for a language, an abstract machine for the same language can be mechanically derived using successive program transformations. This has relevance to studying both the space and time properties of programs because these can be estimated by counting transitions of the abstract machine and measuring the size of the additional data structures needed, such as environments and stacks. In this article we use this process to derive a function that accurately counts the number of steps required to evaluate expressions in a simple language.

Somewhat related to a recent discussion (in which I mentioned EOPL1's scetion on deriving a compiler and machine from an interpreter).

The paper is, of course, worth checking out regardless.

Dynamic optimization refers to the runtime optimization of a native program binary. This paper describes the design and implementation of Dynamo, a prototype dynamic optimizer that is capable of optimizing a native program binary at runtime... Contrary to intuition, we demonstrate that it is possible to use a piece of software to improve the performance of a native, statically optimized program binary, while it is executing. Dynamo not only speeds up real application programs, its performance improvement is often quite significant. For example, the performance of many +O2 optimized SPECint95 binaries running under Dynamo is comparable to the performance of their +O4 optimized version running without Dynamo.

I think Dynamo is pretty well known, but in the light of the Apple switch to x86, it offers perspective on the possibility of using JIT compilation to translate binaries.

The application to programming languages is also straightforward.

A Judy tree is generally faster than and uses less memory than contemporary forms of trees such as binary (AVL) trees, b-trees, and skip-lists. When used in the "Judy Scalable Hashing" configuration, Judy is generally faster then a hashing method at all populations.

Some of the reasons Judy outperforms binary trees, b-trees, and skip-lists:

• Judy rarely compromises speed/space performance for simplicity (Judy will never be called simple except at the API).
• Judy is designed to avoid cache-line fills wherever possible.
• A b-tree requires a search of each node (branch), resulting in more cache-line fills.
• A binary-tree has many more levels (about 8X), resulting in more cache-line fills.
• A skip-list is roughly equivalent to a degree-4 (4-ary) tree, resulting in more cache-line fills.
• An "expanse"-based digital tree (of which Judy is a variation) never needs balancing as it grows.
• A portion (8 bits) of the key is used to subdivide an expanse into sub-trees. Only the remainder of the key need exist in the sub-trees, if at all, resulting in key compression.

The Achilles heel of a simple digital tree is very poor memory utilization, especially when the N in N-ary (the degree or fanout of each branch) increases. The Judy tree design was able to solve this problem. In fact a Judy tree is more memory-efficient than almost any other competitive structure (including a simple linked list). A highly populated linear array[] is the notable exception.

Worth a look, considering the open-source LGPL license and range of applications. HP released this library in 2004. From the PDF manual,

Judy arrays are remarkably fast, space-efficient, and simple to use. No initialization, configuration, or tuning is required or even possible, yet Judy works well over a wide dynamic range from zero to billions of indexes, over a wide variety of types of data sets -- sequential, clustered, periodic, random.

Speed is often used as an excuse for bad programming (premature optimization is the root of all evil and all that). Yet understanding the causes of poor performance of the language system, as opposed to user code, isn't all that easy.

If you are using an open source language implementation, and have access to something clever like dtrace, it might be easier than you think.

PMAT analyzes IBM verbose GC traces by parsing the traces and building pattern models. PMAT recommends key configurations by executing a diagnosis engine and pattern modeling algorithm. If there are any errors related with Java heap exhaustion or fragmentation in the verbose GC trace, PMAT can diagnose the root cause of failures. PMAT provides rich chart features that graphically display Java heap usage.

Sounds useful. If anyone has the time to download and check this out, it would be interesting to hear what you think.

The Fortress Language Spec v0.618

We've already discussed the Fortress project at Sun's Programming Language Research lab. The project seems to be progressing well: they have now released a preliminary version of the language spec as a tech report. This should help assuage the folks who were grumbling about the hype and market-speak of Sun's promotional article. Their PL research team includes some real Smarty McSmartpants, so I expect really good things from them.

From a cursory glance at the spec, there seem to be many interesting features, including:

• an advanced component and linking architecture
• objects and traits (which look similar to Moby and Scala)
• multiple dispatch
• type inference
• parameterized types
• extensible syntax (with a conspicuous reference to Growing a Language)
• first-class functions
• proper tail calls
• labelled jumps, exceptions
• contracts
• some interesting parallelism features (including futures, parallel loops, atomicity primitives, transactions)
• matrices
• comprehensions
• bignums, fixnums (signed and unsigned), floating-point, imaginary and complex numbers
• dimensions

Future work includes proving type soundness, apparently. :)

It is so much fun when the luminaries start working on new languages. History in the making!

jhc is a haskell compiler which aims to produce the most efficient programs possible via whole program analysis and other optimizations.

This seems like an interesting project, for example: Region Inferencing, Compilation by transformation with 2 general intermediate languages, very modern design, using rank-n polymorphism, monad transformers, generic programing, and existential types.

Note, howver, that there are quite a few problems (scaling, memory leaks, etc.)

Maybe some of you might want to offer a helping hand...