Reduceron

# Reduceron, an efficient processor for functional programs

## WHAT IS REDUCERON?

Reduceron is a high performance FPGA softcore for running lazy functional
programs, complete with hardware garbage collection.  Reduceron has been
implemented on various FPGAs with clock frequency ranging from 60 to 150
MHz depending on the FPGA.  A high degree of parallelism allows Reduceron
to implement graph evaluation very efficiently.

Reduceron is the work of Matthew Naylor, Colin Runciman and Jason Reich,
who have kindly made their work available for others to use.  Please see
https://mn416.github.io/reduceron-project/ (the original
http://www.cs.york.ac.uk/fp/reduceron no longer works) for supporting
articles, memos, and original distribution.


## OK, WHAT'S THIS THEN?

The present is a fork of the original distribution with the aim of
keeping it running.  Originally there were more lofty
goals, but that's all abandonned.

While Reduceron technically refers to the FPGA implementation, it is
supported by

 - Flite: the F-lite to Red translator.
 - A Red emulator in C
 - Red Lava: Reduceron is a Red Lava program, which generate Verilog
 - Support for Verilog simulation and synthesis for various FPGA boards

As much of the history as was available has been gathered and
Reduceron, Lava, and the Flite distribution have been merged into one
repository.


## HOW DO I USE IT?

The was last tested with Glasgow Haskell Compiler, Version 8.4.4 on
macOS 10.14.3 and Linux, 64-bit.

Optionally: just run make in the toplevel directory and a large
regression run will start. The Verilog simulation part will take weeks to
finish.

To build:

    make

Or run a specific test suite:

    make -C programs $X

where $X is one of `regress-emu`, `regress-flite-sim`, `regress-flite-comp`, or
`regress-red-verilog-sim`.

Note: the code generated by the C backend for Flite (used in the
`regress-flite-comp`) depends on GCC features, such as nested
functions.  To build on macOS, install *real* gcc (say via Mac
Homebrew) and invoke make as `make CC=gcc-7` (assuming you installed
version 7 of gcc).

To build a hardware version of a given test

    cd fpga; make && flite -r ../programs/$P | ./Red -v

where $P is one of the programs (.hs).  Next, build a Reduceron system
for an FPGA board, fx the BeMicroCV A9:

    make -C Reduceron/BeMicroCV-A9

Unfortunately programs can't currently be loaded dynamically but are
baked into the FPGA image.  It's a high priority goal to change that.

## OPEN QUESTIONS, with answers from Matthew:

Q1: Currently there doesn't seem an efficient way to handle toplevel
    variable bindings (CAFs).  What did the York team have in mind there
    or does it require an extension?  (Obviously one can treat them all
    other functional arguments, but that would mean a lot of parameters
    to pass around).

A1: "Some mechanism would be needed to construct graphs at a specified
location on the heap at the beginning of program execution.  The
initial (unevaluated) graphs have constant size so can be linked to at
compile time."


Q2: Why does Flite default to 0 for the MAXREGS parameter?  Eg, why is

      redDefaults = CompileToRed 6 4 2 1 0

A2: (Historical reasons it would appear).


Q3: What happend to Memo 24?

A3: "I'd like to say it was our best kept secret, but in reality it
probably got trashed :)"

[![tip for next commit](http://prime4commit.com/projects/273.svg)](http://prime4commit.com/projects/273)