Graph reduction machine

{{Short description|Special-purpose computer}}

{{Use dmy dates|date=April 2022}}

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,{{Cite book |last1=Clarke |first1=T. J.W. |last2=Gladstone |first2=P. J.S. |last3=MacLean |first3=C. D. |last4=Norman |first4=A. C. |title=Proceedings of the 1980 ACM conference on LISP and functional programming - LFP '80 |chapter=SKIM - the S, K, I reduction machine |date=1980-08-25 |chapter-url=https://dl.acm.org/doi/10.1145/800087.802798 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=128–135 |doi=10.1145/800087.802798 |isbn=978-1-4503-7396-8|s2cid=10189254 }} the multiprocessor GRIP ("Graph Reduction In Parallel") computer, built at University College London,{{Cite web |date=2002-07-31 |title=Reduction Machines |url=http://www-fp.dcs.st-and.ac.uk/~kh/papers/pasco94/subsubsectionstar3_2_1_1.html |access-date=2023-07-01 |archive-url=https://web.archive.org/web/20020731111557/http://www-fp.dcs.st-and.ac.uk/~kh/papers/pasco94/subsubsectionstar3_2_1_1.html |archive-date=31 July 2002 }}{{Cite book |last1=Jones |first1=Simon L. Peyton |last2=Clack |first2=Chris |last3=Salkild |first3=Jon |last4=Hardie |first4=Mark |title=Functional Programming Languages and Computer Architecture |chapter=GRIP — a high-performance architecture for parallel graph reduction |date=1987 |editor-last=Kahn |editor-first=Gilles |series=Lecture Notes in Computer Science |volume=274 |language=en |location=Berlin, Heidelberg |publisher=Springer |pages=98–112 |doi=10.1007/3-540-18317-5_7 |isbn=978-3-540-47879-9|doi-access=free }} and the Reduceron, which was implemented on an FPGA with the single purpose of executing Haskell.{{Cite journal |last1=Naylor |first1=Matthew |last2=Runciman |first2=Colin |date=2012 |title=The Reduceron reconfigured and re-evaluated |journal=Journal of Functional Programming |language=en |volume=22 |issue=4–5 |pages=574–613 |doi=10.1017/S0956796812000214 |s2cid=1310090 |issn=1469-7653|doi-access=free }}{{Cite book |last1=Naylor |first1=Matthew |last2=Runciman |first2=Colin |title=Implementation and Application of Functional Languages |chapter=The Reduceron: Widening the von Neumann Bottleneck for Graph Reduction Using an FPGA |date=2008 |editor-last=Chitil |editor-first=Olaf |editor2-last=Horváth |editor2-first=Zoltán |editor3-last=Zsók |editor3-first=Viktória |chapter-url=https://link.springer.com/chapter/10.1007/978-3-540-85373-2_8 |series=Lecture Notes in Computer Science |volume=5083 |language=en |location=Berlin, Heidelberg |publisher=Springer |pages=129–146 |doi=10.1007/978-3-540-85373-2_8 |isbn=978-3-540-85373-2}}