NOTICE to those who wish for a greater challenge:

If you want a greater challenge, don’t read any further: just try to understand the program via the source.

If you get stuck, come back and read below for additional hints and information.

Obfuscation

The program implements a so called Krivine machine, enhanced with a basic input/output system and a reference counting garbage collector. The Krivine machine is a stepwise transformer of a global state consisting of the current term, the current environment (a list of closures), and a stack of continuations (see the 3rd reference for details).

The term space holds lambda calculus terms in the following format. 0 denotes some form of I/O; the only four occurrences are at:

    C=13: recognizes end of a byte
    C=20: recognize output of 0 bit
    C=21: recognize output of 1 bit
    C=end: input list, expanded lazily

1 denotes a variable, with the next entry its de Bruijn index.

2 denotes application with the next entry the size of the term being applied.

3 denotes lambda abstraction.

A closure consists of the following items:

0. pointer to the next closure (as part of an environment), or next record on free list.
1. reference count.
2. pointer to environment.
3. lambda term (index in term space).

Here’s what each variable does:

    L   Lambda term space
    m   mode: 0 for bits and 7 for bytes
    b   bits remaining unread in I, -1 on EOF
    D   Desirable temporary
    c   continuation context
    a   active environment pointer
    C   Current term index
    U   Ultimate term pointer
    u   utility entry
    B   Born to be free-list of closures
    I   Input character
    O   Output character
    e   entry of current term

Here’s what each of the 6 auxiliary functions do:

    s   variable lookup in active environment with de Bruijn index u
    S   gets one bit of input, setting b to -1 on EOF or to remaining number of bits in current byte
    k   copy fragment from string literal holding lambda terms xor 46 into current end of term space
    x   expand input, adding 11 (resp. 99) entries to term space for bit (resp. byte) mode
    p   parses BLC-encoded lambda term using S(), stores results in term space and returns length
    d   decrease reference counter, add record to free list on reaching zero

Jump to: top