Graph reduction machine explained

A graph reduction machine is a special-purpose computer built to perform combinator calculations by graph reduction.

Examples include the SKIM ("S-K-I machine") computer, built at the University of Cambridge Computer Laboratory,^[1] the multiprocessor GRIP ("Graph Reduction In Parallel") computer, built at University College London,^{[2] [3]} and the Reduceron, which was implemented on an FPGA with the single purpose of executing Haskell.^{[4] [5]}

See also

• SECD machine

Further reading

• T. J. W. Clarke, P. Gladstone, C. MacLean, A. C. Norman: SKIM — The S, K, I Reduction Machine. LISP Conference, 1980: 128–135

External links

• Reduction Machines, Parallel Functional Programming: An Introduction, Kevin Hammond

Notes and References

1. Book: Clarke . T. J.W. . Gladstone . P. J.S. . MacLean . C. D. . Norman . A. C. . Proceedings of the 1980 ACM conference on LISP and functional programming - LFP '80 . SKIM - the S, K, I reduction machine . 1980-08-25 . https://dl.acm.org/doi/10.1145/800087.802798 . LFP '80 . New York, NY, USA . Association for Computing Machinery . 128–135 . 10.1145/800087.802798 . 978-1-4503-7396-8. 10189254 .
2. Web site: 2002-07-31 . Reduction Machines . 2023-07-01 . https://web.archive.org/web/20020731111557/http://www-fp.dcs.st-and.ac.uk/~kh/papers/pasco94/subsubsectionstar3_2_1_1.html . 31 July 2002 .
3. Book: Jones . Simon L. Peyton . Clack . Chris . Salkild . Jon . Hardie . Mark . Functional Programming Languages and Computer Architecture . GRIP — a high-performance architecture for parallel graph reduction . 1987 . Kahn . Gilles . Lecture Notes in Computer Science . 274 . en . Berlin, Heidelberg . Springer . 98–112 . 10.1007/3-540-18317-5_7 . 978-3-540-47879-9. free .
4. Naylor . Matthew . Runciman . Colin . 2012 . The Reduceron reconfigured and re-evaluated . Journal of Functional Programming . en . 22 . 4–5 . 574–613 . 10.1017/S0956796812000214 . 1310090 . 1469-7653. free .
5. Book: Naylor . Matthew . Runciman . Colin . Implementation and Application of Functional Languages . The Reduceron: Widening the von Neumann Bottleneck for Graph Reduction Using an FPGA . 2008 . Chitil . Olaf . Horváth . Zoltán . Zsók . Viktória . https://link.springer.com/chapter/10.1007/978-3-540-85373-2_8 . Lecture Notes in Computer Science . 5083 . en . Berlin, Heidelberg . Springer . 129–146 . 10.1007/978-3-540-85373-2_8 . 978-3-540-85373-2.