Introduction

Hof is a new language based on the SKI calculus named after Douglas Hofstadter.

Syntax:   Semantics:        Meaning:
T -> I    λx.x              I combinator from SKI calculus
T -> K    λx.λy.x           K combinator from SKI calculus
T -> S    λx.λy.λz.xz(yz)   S combinator from SKI calculus
T -> P    λx.x              Print x to stdout

T -> R    λx.λy.(x|y)       Randomly return either x or y with Bernoulli
                            probability distribution

T -> A    (T₁T₂)            Form a new term out of the application of
                            terms T₁ and T₂

The interpreter for the language is written in C++ and features lazy evaluations implemented with memoized thunks. The optimizations found in D. A. Turner's paper, "Another Algorithm for Bracket Abstraction" including B, C, S′, B′, C′ combinators are included.

The interpreter also contains a full Lambda Calculus lexer/parser which transcompiles the untyped Lambda Calclulus into the SKI calculus, including η-reduction simplification, which is then transcompiled into Hof.

Another feature is verbose mode which shows the full evaluation cycle in colorized terminal output. Combined with a good debugger, verbose mode can reveal the entire combinator application execution by stepping through with breakpoints in the eval/apply cycle.