Ouros: A Dataflow-Driven Processor for Lazy Functional Programming Languages

Abstract

This paper presents Ouros, a pipelined processor for lazy functional programming languages based on combinator graph reduction. Ouros overcomes the inherent sequentiality of graph reduction through dataflow-driven execution and automatic fine-grained multi-threading. It maintains pipeline utilisation by hiding per-thread latency and interleaving multiple independent threads. Its concurrent garbage collector (GC) addresses the high memory allocation pressure of functional language execution. The correctness of the GC algorithm is verified via model checking. Ouros achieves a higher clock frequency than the single-cycle KappaMutor processor in FPGA implementation, and is faster by 20.9% on average across 10 Haskell benchmarks (up to 118% on richly-threaded programs). GC overhead ranges from 0% to 23% depending on program allocation behaviour.