In my down time at work, I was looking at my second 01_ interpreter to see why it was so slow on the 99 bottles of beer. The simplistic built-in Java profiling, enabled with the -Xprof flag, showed that a big chunk of time was spent in pattern matching. Every time a function was called, it would attempt to match the arguments to the patterns, and it would have to reevaluate the argument for the next pattern if the pattern failed to match. Furthermore, recursion would cause giant chains in the delayed function call values that had to be evaluated over and over.

So I changed FuncallValue to memoize its result when evaluated, and the 99 bottles of beer program was fast. However, I then uncovered some hard to diagnose bugs in the interpreter. It still runs all the examples that I've posted so far correctly.

After skimming some of the languages on the Esolang Wiki, I would say that, superficially, 01_, as a lazy, pattern-matching language, is most closely related to pax and Rhotor.

Some more simple example code that runs correctly on my interpreter. Given the definitions:

take 0x 0y = 0 take x y.
take 0x 1y = 1 take x y.
take _ . = _.

drop 0x 0y = drop x y.
drop 0x 1y = drop x y.
drop _ y = y.

concat x y = x y.

reverse 0 x = reverse x 0.
reverse 1 x = reverse x 1.
reverse _ = _.

This reverses the lines of its input:

tac _ = _.
tac in = tac drop-line in first-line in _.

drop-line _ = _.
drop-line 00001010in = in.
drop-line in = drop-line drop 00000000 in.

first-line _ ac = ac.
first-line 00001010in ac = ac 00001010.
first-line in ac = first-line drop 00000000 in concat ac take 00000000 in.

This caesar-encodes its input:

caesar _ = _.
caesar 011x = 011 reverse rotl3 reverse take 00000 x caesar drop 00000 x.
caesar 010x = 010 reverse rotl3 reverse take 00000 x caesar drop 00000 x.
caesar x = take 00000000 x caesar drop 00000000 x.

rotl3 00000 = 00000.
rotl3 11111 = 11111.
rotl3 01111 = 01111.
rotl3 10111 = 10111.
rotl3 00111 = 00111.
rotl3 11011 = 11011.
rotl3 x = rotl rotl rotl rotl rotl rotl rotl rotl rotl rotl rotl rotl rotl x.

rotl 10000 = 01011.
rotl 0x = 1 rotl x.
rotl 1x = 0 x.
rotl _ = _.

Note that the 4th character in rotl3 and rotl is the letter L and is not the number 1.