Graph reduction

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.

Example usage:

$ 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 antkaij@mit.jyu.fi
[heap_size=1048560,stack_size=2621440]
examples/fib> FIB 3
[...]
1 + (1 + (0 + (\f[4].f[4]) (\y[11].(\x[5].x[5]) y[11] 0 1) (\t[3].\f[4].f[4])))
1 + (1 + (0 + (\y[11].(\x[5].x[5]) y[11] 0 1) (\t[3].\f[4].f[4])))
1 + (1 + (0 + (\x[5].x[5]) (\t[3].\f[4].f[4]) 0 1))
1 + (1 + (0 + (\t[3].\f[4].f[4]) 0 1))
1 + (1 + (0 + (\f[4].f[4]) 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.

3 thoughts on “Graph reduction

  1. Why writing such a tool in C?
    No, really, why?

    The only reason I can imagine is that you wanted to play writing a garbage collector. Please, tell me, this is the reason 🙂

    Otherwise there are tons of languages (haskell, ocaml, freshml, even … whatever lisp) more suitable to write symbolic processing programs, and implementing functional languages is the typical example of such programs.

    Cheers.

  2. No, that is not the reason.

    I know these languages, and have even implemented a similar one myself (in Haskell). I have done a graph reduction system in Haskell at least twice.

    Yes, I have a reason for this. No, I will not tell you what it is. Yet.

    (BTW, the extreme portability of ANSI C is always very appealing. None of the languages you cited, except perhaps Lisp, rivals it in portability. And no, this was not the primary reason.)

    (Plus I enjoy writing C. And no, this was not the primary reason either.)

  3. Kommentoinpa tännekin tuota arkistoviilausta:

    Tekstin lukeminen kuukauden ryppäässä tuntuu kyllä helpommalta noin…

    Tulipa vain mieleen, että koska tapa kuitenkin poikkeaa hieman totutusta, tarvitseeko arkistossa ilmoittaa, että järjestyksen olevan käänteinen verrattuna etusivuun?

    “Archived posts presented in chronological order” tai jotain…

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.