What is interesting though, the fastest interpreters for lambda calculus (such as yours uni.c) work by translating the term to combinatory logic (although with a bigger base than S,K) and calculating with it.
My uni.c was based on Ben Lynn's combinatory logic VM to which he compiled a large subset of Haskell [1] in a winning IOCCC entry. Lennart Augustsson made an even more comprehensive Haskell implementation with a combinator based runtime [2].
Thanks for the pointer to MicroHS, looks interesting.
BTW, this is probably obvious to you, there are also 5 combinators to which you can directly translate (with proper parentheses) the bits of BLC expression and it sort of self-evaluates in combinatory logic.
The self-evaluation works with the stack of de Bruijn terms as the second argument. One combinator represents lambda abstraction which puts a term to the stack, another is S which represents application, two combinators are used to drop/select the de Bruijn term from the stack and there needs to be another combinator to mark the end of input.
Yes; that's sort of how the lambda calculus self-interpreter works.
There's another connection too, where a lambda term is obtained from its binary code by successive applying an initial term to true or false [1].
