Mbfi

Mbfi (Matryoshka brainfuck interpreter) is a brainfuck self-interpreter created by Ørjan Johansen to achieve a (calculable) eigenratio (i.e. the slowdown factor in the infinite limit of adding one more self-interpreter to a large stack of them).

Design goals

The main design goals are, in descending order of importance:

1. Existence of eigenratio:
   • To ensure that an eigenratio exists, mbfi uses a different layout of simulated code vs. simulated tape than usual for brainfuck self-interpreters.
   • The code representation is placed inside the tape, next to the simulated current tape cell. <> instructions are implemented by shifting the entire code representation relative to the tape.
   • This is of course ridiculously slow for most normal brainfuck programs, but it is asymptotically better for huge tape sizes, which is what counts in the limit of nesting arbitrarily many self-interpreters. As such this self-interpreter may be considered a galactic algorithm.
2. Practically calculable eigenratio:
   • There should be a practically calculable matrix, ideally small enough to include here, whose dominant eigenvalue is the eigenratio, which can then be found with any decent linear algebra library (actually constructing such a matrix is still remaining work to do).
   • Per Clive Gifford's previous work, this means keeping low the number of essential "instruction variations" with different costs, which correspond to the number of rows/columns in the matrix.
   • An important restriction to achieve this is to avoid moving the tape pointer into "unknown" tape cell territory unnecessarily. This reduces the number of unknown cell values affecting the cost of simulating a particular instruction.
     • As a consequence, the instruction decoding method of dbfi could not be used. Although heavily golfed, it goes deep into unknown cell theory and would in a deep enough stack of interpreters have caused the cost of an instruction to depend on up to 15 different unknown cell values.
3. A "small" eigenratio:
   • Given how the <> instructions are necessarily expensive with this design, lowering the eigenratio involves a balance between golfing the code and reducing the number of expensive code search roundtrips. As such, parts of the code have been taken from Daniel B. Cristofani's dbfi, the shortest brainfuck self-interpreter, while other parts are inspired by the roundtrip-reducing aspects of Clive Gifford's cgbfi, the fastest (for normal programs).

Previous lack of eigenratio

(This section is really discussing most/all(?) previous brainfuck self-interpreters, not mbfi itself.)

Most brainfuck self-interpreters do not have an eigenratio because of how they implement the simulated brainfuck tape: There is at least one cell of padding per value cell, and a simulated access of simulated tape cell $n$ requires accessing at least $2n$ distinct cells between the code representation and the tape cell representation in the inner interpreter.

This forces the cost of accessing tape cell $n$ (1-based) with a stack of $d$ self-interpreters within the outermost program to grow at least as fast as the function

$$f(n,d)={\begin{cases}1,&d=0\\\sum _{i=1}^{2n}f(i,d-1),&d>0.\end{cases}}$$

(The sequences $f(1,d)$ and $f(2,d)$ appear to be OEIS A002449 (confirmed in the formula section) and OEIS A098541, while $f(2^{n},d)$ seem to be the suitably shifted columns of OEIS A098539. I couldn't find $f(3,d)$ there, and no discussion of the growth rate.)

Theorem

$$f(n,d)\geq {\frac {n^{d}}{d!}}\cdot 2^{\frac {d(d+1)}{2}}$$

Proof

By induction on $d$. For $d=0$, both sides are 1. Otherwise,

$${\begin{aligned}f(n,d+1)&=\sum _{i=1}^{2n}f(i,d)\geq \sum _{i=1}^{2n}{\frac {i^{d}}{d!}}\cdot 2^{\frac {d(d+1)}{2}}{\text{(by induction assumption)}}\\&\geq \int _{i=0}^{2n}{\frac {i^{d}}{d!}}\cdot 2^{\frac {d(d+1)}{2}}{\text{(because }}i^{d}{\text{ is increasing in }}i{\text{ for }}i\geq 0{\text{)}}\\\\&={\frac {(2n)^{d+1}}{d!(d+1)}}\cdot 2^{\frac {d(d+1)}{2}}={\frac {n^{d+1}}{(d+1)!}}\cdot 2^{{\frac {d(d+1)}{2}}+{\frac {2}{2}}(d+1)}={\frac {n^{d+1}}{(d+1)!}}\cdot 2^{\frac {(d+1)(d+2)}{2}}.\end{aligned}}$$

As a consequence, for fixed $n$, $f(n,d)=\exp(\Omega (d^{2}))$, while a self-interpreter with an eigenratio cannot have faster growth than $\exp(O(d))$.

Code

Version 2 of the interpreter. Testing by Clive Gifford suggests that the slowdown factor from 2 to 3 self-interpreters is around 9500.

Matryoshka Brainfuck Interpreter (mbfi) version 2

Made by Ørjan Johansen 2021

Version 2: Changed from a modified dbfilike dispatch to a nested loop case
match like Clive Gifford's cgbfi

Most of parsing and bracket matching code is from Daniel B Cristofani's dbfi

General tape layout most of the time:
(left simulated tape)000
(simulated code before IP)0?(code after IP)
000(simulated right tape starting with current cell)

>>> Add three more padding cells to the left of simulated code
Parser loop mostly unchanged from dbfi
>>>+[
 [-]>>[-]
 ++>+>+++++++[<++++>>++<-]++>>+>+>+++++[>++>++++++<<-]+>>>,<++[
  [>[->>]<[>>]<<-]
  <[<]<+>>[>]>
  [<+>-
   [[<+>-]>]
   <[
    [[-]<]
    Marker cell is no longer set here
    <-[
     <+++++++++>[<->-]>
     + Set process another character flag here (just 1) instead
     >
    ]>>
   ]
  ]<<
 ]<
]
Just after simulated code
<[<]> Go to first simulated code instruction and enter main interpreter loop
[ At simulated IP (0 0 'i)
 [<<+>+>-] Make two copies of instruction
 +< Set flag and go to second instruction copy (i 'i 1)

 Match instruction with nested decrements/loops
 Instructions are listed in reverse order of dbfi
 -
 [-
  [-
   [-
    [-
     [-
      [-
       [-
        Increment instruction (i '0 1)

        No other instructions left so must match
        >[>]>>> Go to simulated current cell
        + Perform instruction on simulated current cell
        << Go to middle of padding area (0 '0 0)
       ]

       After each match loop there are three possible local configurations:
        (i '0 1) This loop level matched and its instruction will run
        (0 '0 0) An instruction already ran; now in the right side padding
                 In this case the actual simulated IP will be in (i 0 1) form
        (i '0 0) An instruction already ran; now in the simulated IP
                 (This option is first used by the Move Right instruction)

       Input instruction

       > Go to flag
       [ Test flag for whether instruction should run
        [>]>>>,< Otherwise almost identical to increment
       ]
       In padding area regardless of branch taken (0 0 '0)
       < Go to middle of padding area
      ]
      >[[>]>>>-<]< Decrement instruction
     ]
     >[[>]>>>.<]< Output instruction
    ]>
    [ Move left instruction: This is the only one that starts its work
      to the left of the simulated code (i 0 '1)
     <<[<] Go to the left of the simulated code (0 0 '0 j)
     + Set flag to shorten padding
     <<< Go to old simulated left_of_current cell and loop to move its value
     [ At ((ltape) 'o 0 0 1 (code) 0 0 n (rtape))
      - Decrement
      >>>[[>]>]> Go to new simulated current cell (0 0 'n)
      + Increment
      <<<[[<]<]< Go back to old simulated left_of_current cell and loop again
     ]
     >>>- Clear temporary 1 padding to the left of simulated code
     > Go to leftmost end of simulated code and enter loop to shift code
     [[[<+>-]>]>] Shift values one cell leftward until meeting two zeros in a
                  row
    ]< At (0 '0 0) of old or new padding regardless of branch taken
   ]>
   [ Move right instruction
    [>] Go to the right of the simulated code ('0 0 0 c)
    + Set flag to shorten padding
    >>> Go to old current cell and loop to move its value
    [ At ((ltape) n 0 0 (code) 1 0 0 'o (rtape))
     - Decrement
     <<<[[<]<]< Go three cells to the left of the simulated code
     + Increment
     >>>[[>]>]> Go back to old simulated current cell and loop again
    ]
    <<<- Clear temporary 1 padding to the right of simulated code
    < Go to rightmost end of simulated code and enter loop to shift it
    [[[>+<-]<]<] Shift values one cell rightward until meeting two zeros in a
                 row
    >>>[>]>- Go to 1 of simulated IP and clear it (i 0 '0)
   ]<
  ]>
  [ Start loop instruction
   [>]>>+ Go to padding and set flag just before simulated current cell
   > Go to simulated current cell (0 0 1 'c)
   [<-]< If not zero clear flag and go to middle of padding
         If zero go to flag (and enter loop)
   [
    -<<<[<]> Clear flag and go to 1 of simulated IP (1 0 '1)
             reinterpreting this as starting depth for bracket matching
    [-<+>>-[<<+>++>-[<->[<<+>>-]]]<[>+<-]>] Unchanged from dbfi
    < Go to first zero of new simulated IP (j '0 0)
   ]
   > Go to last zero of padding or simulated IP
  ]<
 ]>
 [ End loop instruction
  [>]>>+ Go to padding and set flag just before simulated current cell
  > Go to simulated current cell and enter loop if nonzero (0 0 1 'c)
  [
   <-<<<[<]< Clear flag and go to 1 encoding current right bracket ('1 0 1)
            reinterpreting this as starting depth for bracket matching
            and the 1 of the simulated IP as the moved right bracket
   [+>+<<-[>-->+<<-[>+<[>>+<<-]]]>[<+>-]<] Unchanged from dbfi ('0 0 2)
   ++>>-- Move found left bracket leftwards and go to the second zero
          of simulated IP (2 0 '0)
  ]
  At simulated IP (j 0 '0) or simulated current cell (0 0 1 'c)
  <[-<]> If the latter then clear flag and go to it (0 0 '0 c)
 ]
 At simulated IP (i 0 '0) or in padding (0 0 '0)
 <+< Set flag and enter loop to test ('i 1 0  or  '0 1 0)
 [>-]> Clear flag and go to it if at simulated IP; then go right
 At simulated IP (i 0 '0) or in padding (0 '1 0)
 [
  -<<[<] If in padding clear flag and go to simulated IP (i '0 1)
  >- Go to 1 of simulated IP and clear it converging branches
 ]
 > Go right to next instruction code cell (or 0 beyond end of simulated code)
]