The Reduceron

Matthew Naylor and Colin Runciman

Between October 2008 and December 2009, we are working on the EPSRC-funded project

The Reduceron: High-Level Symbolic Computing on FPGA,

continuing work that began in Matthew's thesis. This web-page makes available the work-in-progress results of the project.

Technical report

Coming soon...

Implementation

The implementation of the Reduceron comprises three pieces.

York Lava The Haskell library used to describe the Reduceron
F-lite A compiler for the language that runs on the Reduceron
Reduceron The reduction machine itself

F-lite and York Lava are discussed in memos 9 and 23 respectively.

Memos

The following series of memos are just notes, mainly for our own benifit.

1 Widening function bodies
2 Widening function bodies revisited
3 Head reduction, arity raising and shared subexpressions
4 Chunky lists
5 Recursive nested-case function bodies and in-lining
6 Case factorisation and special treatment of constructors
7 Memory layout
8 Speculative evaluation of primitive redexes
9 F-lite: a core subset of Haskell
10 Experminents in inlining, arity-raising, and indirection-avoidance
11 Enabling arity-raising by sharing analysis
12 An algorithm for arity-reduction
13 Compiling case expressions
14 First quarterly review
15 Towards a spineless Reduceron
16 Configuring the XUPV5
18 Spineless versus Spinefull
19 HFL Talk: Three improvements to the Reduceron
20 Brimingham Talk: The Reduceron
21 Second quarterly review
22 Compiling F-lite to C
23 York Lava, by example
25 Bounded template instantiation
26 Rotation and one-hot addition
27 Design of the Octostack
28 Mark-Compact in O(survivors) time
30 Reduceron performance, just before ICFP'09
31 Design proposal for speculative evaluation of primitive redexes
32 Thoughts about Reducera -- a Plural Reduceron
33 Fourth quarterly review
34 Expected clock-tick run-times for flite-reduceron programs
35 Order of compilation passes
36 Case of known construction -- at compile-time and run-time
37 Counting the clock cycles needed to instantiate a combinator body
38 Benefits of a primitive-value stack
39 The Force-and-Rebind transformation
40 Forcing arguments to primitive functions, revisited

Previous work

The Reduceron was first developed as part of Matthew's thesis, circa 2007. Here are some of the materials that arose from the thesis work.

Thesis Matthew's thesis, see Chapter 2
Paper Published at IFL'07
Source code Of the thesis implementation