Graph reduction is the basic operational model of lazy functional programming. The idea is that the program is represented as a huge λ-term abstract syntax tree, and the program is executed by performing outermost-leftmost β-reductions to this tree, and whenever a subtree must be replaced by another tree (such as, when performing the substitution operation), the root node of the replacee is overwritten by the root node of the replacement (or a redirection node pointing to the replacement) instead of making copies (the body of an abstraction still needs to be copied, of course). The effect is the familiar laziness: when a function refers to its parameter more than once, the argument term is shared between the parameter references instead of making copies, and so any reduction in any one of them is shared by all of them.
For some strange reason, I decided I must write a set of C functions that demonstrate graph reduction. I wrote them, and then in order to test them I expanded them to become a complete implementation of λ-calculus (extended with integers) graph reduction. The program can be found here; it is written in portable ANSI–C. It is able to show the complete trace of reductions. It is intended for demonstrating the technique, and therefore is effectively a stupid interpreter and does not implement any of the sophisticated optimization techniques that industrial-strength functional language implementations routinely use.
$ cat examples/fib TRUE = \t.\f.t FALSE = \t.\f.f IF = \x.x NIL = \x. IF x TRUE NIL ISNIL = \x. x TRUE CONS = \car. \cdr. \x. IF x FALSE (\y. IF y car cdr) CAR = \cell. cell FALSE TRUE CDR = \cell. cell FALSE FALSE MAP = \f. \xs. IF (ISNIL xs) NIL (CONS (f (CAR xs)) (MAP f (CDR xs))) AT = \n. \xs. CAR (DROP n xs) DROP = \n. \xs. IF (n = 0) xs (DROP (n - 1) (CDR xs)) TAKE = \n. \xs. IF (n = 0) NIL (CAR xs (TAKE (n - 1) (CDR xs))) FIBS = CONS (CONS 0 1) (MAP GENFIB FIBS) GENFIB = \pair. CONS (CDR pair) ((CAR pair) + (CDR pair)) FIB = \n. (CDR (AT n FIBS)) $ ./graph-reduction -t -S10K -H1M examples/fib graph-reduction 1.0 by Antti-Juhani Kaijanaho, report bugs to email@example.com [heap_size=1048560,stack_size=2621440] examples/fib> FIB 3 [...] 1 + (1 + (0 + (\f.f) (\y.(\x.x) y 0 1) (\t.\f.f))) 1 + (1 + (0 + (\y.(\x.x) y 0 1) (\t.\f.f))) 1 + (1 + (0 + (\x.x) (\t.\f.f) 0 1)) 1 + (1 + (0 + (\t.\f.f) 0 1)) 1 + (1 + (0 + (\f.f) 1)) 1 + (1 + (0 + 1)) 1 + (1 + 1) 1 + 2 3 examples/fib>
(In the trace output, each bound variable is annotated by a scope identifier that effectively allows me to ignore variable caputure problems.)
I plant to further extend the language to handle algebraic data types and simple pattern matching, to get rid of the noise of simulating these concepts in the traces.
Technically, perhaps the most interesting part of the program is that it contains a fully portable copying garbage collector.