After a day that included a 3 hour meeting to make estimates on some ambiguously specified work that might be done weeks or months in the future and would probably change a bunch of times before then, I went home and got my 01_ interpreter to work. The meeting was long and boring, but having work lined up for the future is a good thing.

When I removed the memoizing from the interpreter, it worked correctly, though slowly. I eventually figured out that the problem had something to do with list concatenation of delayed values and pared down the code that reproduced the problem to

print _ = _.
print 0x = 00110000 print x.

== This should never be reached unless there is a bug in the interpreter.
print _ = 00101000 01100010 01110101 01100111 00101001.

concat x y = x y.

nil = _.

bug = print concat concat 0 nil 0_ 00001010.

which would print out 00 if the interpreter were working correctly. It printed out 0(bug) because the argument to print was a delayed value when forced the first time evaluated correctly to 0, so the first print _ = _. didn't match. However, when it was forced again, it evaluated to nil, so the print 0x = ... didn't match either, so it got to the second print _ = ....

Finally, I traced the problem to the assumption that the first list in a list concatenation was never nil, and the only way it could be forced to nil is when the list concatenation itself was forced. However, with memoization, the first list could be forced to nil outside of the list concatenation, and then the bug was that the list concatenation evaluated to nil instead of the second list. Once I figured that out, it was easy to fix.

Now the interpreter was fast enough and worked well enough to run a brainfuck interpreter

== brainfuck interpreter 
== with 8-bit cells and an infinite array in both directions
brainfuck input code = bf compress code _ zeros zeros input.

== Infinite list of 0
zeros = 0 zeros.

== Compress instructions into 3 bits
compress _ = _.
compress 00111110code = 000 compress code. == >
compress 00111100code = 001 compress code. == <
compress 00101101code = 010 compress code. == -
compress 00101011code = 011 compress code. == +
compress 00101110code = 100 compress code. == .
compress 00101100code = 101 compress code. == ,
compress 01011011code = 110 compress code. == [
compress 01011101code = 111 compress code. == ]
compress code = compress tail code.

== End of code
bf _ . . . . = _.

== >
bf 000instructions previous-instructions data previous-data input =
    bf instructions concat 000 previous-instructions
        tail data concat head data previous-data input.

== <
bf 001instructions previous-instructions data previous-data input =
    bf instructions concat 001 previous-instructions
        concat head previous-data data tail previous-data input.

== -
bf 010instructions previous-instructions data previous-data input =
    bf instructions concat 010 previous-instructions
        concat head - data tail data previous-data input.

== +
bf 011instructions previous-instructions data previous-data input =
    bf instructions concat 011 previous-instructions
        concat head + data tail data previous-data input.

== .
bf 100instructions previous-instructions data previous-data input =
    reverse head data
    bf instructions concat 100 previous-instructions data previous-data input.

== ,
== Read EOF
bf 101instructions previous-instructions data previous-data _ =
    bf instructions concat 101 previous-instructions
        concat 00000000 tail data previous-data _.
== Read 8 bits
bf 101instructions previous-instructions data previous-data input =
    bf instructions concat 101 previous-instructions
        concat reverse head input tail data previous-data tail input.

== [
== Exit loop
bf 110instructions previous-instructions 00000000data previous-data input =
    jump-forward _ instructions concat 110 previous-instructions
        concat 00000000 data previous-data input.
== Enter loop
bf 110instructions previous-instructions data previous-data input =
    bf instructions concat 110 previous-instructions data previous-data input.

== ]
== Exit loop
bf 111instructions previous-instructions 00000000data previous-data input =
    bf instructions concat 111 previous-instructions
        concat 00000000 data previous-data input.
== Continue loop
bf 111instructions previous-instructions data previous-data input =
    jump-backward _ concat 111 instructions previous-instructions
        data previous-data input.

== Reverse bits
reverse _ = _.
reverse 0bits = reverse bits 0.
reverse 1bits = reverse bits 1.

== First 8/3 bits
head bits = take 00000000 bits.
head3 bits = take 000 bits.
take 0counter 0bits = 0 take counter bits.
take 0counter 1bits = 1 take counter bits.
take . . = _.

== Drop first 8/3 bits
tail _ = _.
tail bits = drop 00000000 bits.
tail3 bits = drop 000 bits.
drop 0counter 0bits = drop counter bits.
drop 0counter 1bits = drop counter bits.
drop . bits = bits.

== Concatenate 2 lists
concat a b = a b.

== Skip out of loop
jump-forward _ 111instructions previous-instructions data previous-data input =
    bf instructions concat 111 previous-instructions data previous-data input.
jump-forward 0nesting 111instructions previous-instructions
  data previous-data input =
    jump-forward nesting instructions concat 111 previous-instructions
        data previous-data input.
jump-forward nesting 110instructions previous-instructions
  data previous-data input =
    jump-forward concat 0 nesting instructions
        concat 110 previous-instructions data previous-data input.
jump-forward . _ . . . . = _.
jump-forward nesting instructions previous-instructions
  data previous-data input =
    jump-forward nesting
        tail3 instructions concat head3 instructions previous-instructions
        data previous-data input.

== Jump back to the start of loop
jump-backward _ instructions 110previous-instructions
  data previous-data input =
    bf instructions concat 110 previous-instructions data previous-data input.
jump-backward 0nesting instructions 110previous-instructions
  data previous-data input =
    jump-backward nesting concat 110 instructions previous-instructions
        data previous-data input.
jump-backward nesting instructions 111previous-instructions
  data previous-data input =
    jump-backward concat 0 nesting
        concat 111 instructions previous-instructions data previous-data input.
jump-backward . . _ . . . = _.
jump-backward nesting instructions previous-instructions
  data previous-data input =
    jump-backward nesting
        concat head3 previous-instructions instructions
        tail3 previous-instructions
        data previous-data input.

== Increment
+ 0bits = 1 bits.
+ 1bits = 0 + bits.
+ _ = 1.

== Decrement
- 0bits = 1 - bits.
- 1bits = 0 bits.
- _ = _. == An infinite list of 1 would be more correct