Lambda the Ultimate

via Jeff Newbern in the discussion forum comes the writeup from the winning entry in the MEMOCODE 2007 contest:

This year, the first MEMOCODE hardware/software codesign contest posed the following problem: optimize matrix-matrix multiplication in such a way that it is split between the FPGA and PowerPC on a Xilinx Virtex IIPro 30. In this paper we discuss our solution, which we implemented on a Xilinx XUP development board with 256 MB of DRAM. The design was done by the five authors over a span of approximately 3 weeks, though of the 15 possible man-weeks, about 9 were actually spent working on this problem. All hardware design was done using Bluespec SystemVerilog (BSV), with the exception of an imported Verilog multiplication unit, necessary only due to the limitations of the Xilinx FPGA toolflow optimizations.

Wow! This is much cooler than the kinds of programs I write :-)

This MIT/Bluespec team won the first contest at MEMOCODE 2007 and the second in MEMOCODE 2008. The results for 2008 are very interesting: The Bluespec team had the highest performance by an order of magnitude, the next fastest program was written by one guy in straight C without using the FPGA, and the rest were mostly in a hybrid of C and (V?)HDL.

Does this make Bluespec the programming tool of choice for discriminating hardware hackers?

Non-Deterministic Recursive Ascent Parsing, Renee Leermakers. 1991 conference on European chapter of the Association for Computational Linguistics.

A purely functional implementation of LR-parsers is given, together with a simple correctness proof. It is presented as a generalization of the recursive descent parser. For non-LR grammars the time-complexity of our parser is cubic if the functions that constitute the parser are implemented as memo-functions, i.e. functions that memorize the results of previous invocations. Memo-functions also facilitate a simple way to construct a very compact representation of the parse forest. For LR(0) grammars, our algorithm is closely related to the recursive ascent parsers recently discovered by Kruseman Aretz [1] and Roberts [2]. Extended CF grammars (grammars with regular expressions at the right hand side) can be parsed with a simple modification of the LR-parser for normal CF grammars.

How LR parsers worked always confused me until I learned about their presentation in terms of recursive ascent.