Reduction#
Bruijn supports several reducers that can be chosen using its
--reducer flag.
HigherOrder (source)#
HigherOrder reduction is one of the simplest reducers. By translating the entire expression to a higher-order representation, we can abuse Haskell's internal reduction implementation in our favour. Aside from conversion from/to the higher-order encoding, this reducer does basically nothing special.
RKNL (source)#
RKNL1 is an abstract machine for reducing lambda calculus. It uses the call-by-need reduction strategy, similar to Haskell and other functional programming languages. For you this means that you have efficient support for laziness with generally less redundant reductions.
ION (source)#
The ION machine was created by Benn Lynn as a reducer for a hypothetical functional stack machine computer. We convert the lambda calculus term to combinatory logic using Kiselyov translation, set up a "virtual" machine with the combinators, and let it run until the stack has reached its end.
Most of the work was done by John Tromp in his nf.c. The translation to Haskell and its integration into bruijn was mainly done as an experiment on performance.