⍝   B r a i n f u c k
⍝
⍝ See: dfns.dws/notes.bf for a description of the language.
⍝
⍝ As Brainfuck is known to be Turing-complete, the ability to
⍝ write it in eval proves that eval is also Turing-complete.
⍝
⍝ Here, the BF machine is a:
⍝   ;-separated 3-tuple of          ⍝ tokens; memory; input/output
⍝       /-separated pairs of        ⍝ upstream/downstream
⍝           :-separated lists.      ⍝ head:tail
⍝
⍝ For the memory tape and token stream, the head items in each left list are
⍝ under BF's read-heads, with tail items in the forward-reading direction.
⍝ Item's in the right lists have already passed under the read-head.
⍝
⍝ This means that, to read forward, we pop the current item from the left list
⍝ and push it onto the right list; and vice-versa for reading backwards.
⍝
⍝ Lists are terminated by '∘'.
⍝
⍝ Here is sample initial BF machine state.  The token read-head is positioned at
⍝ the left-most token, so the second "downstream" token list is empty. Ditto for
⍝ the memory tape.  The input list contains two unread items and the output list
⍝ is empty:
⍝
⍝   ,:>:,:<:[:-:>:+:<:]:>:.:∘ / ∘;    0:0:∘ / ∘;     2:3:∘ / ∘
⍝   └───────────┬───────────┘         └─┬─┘          └─┬─┘  └┬┘
⍝   :-separated token [up]stream      memory         input output
⍝
⍝ The reduction rules are very simple; the only complication arises in skipping
⍝ back and forth along [...] sequences, where inner nested []s must be ignored.
⍝ This is achieved with two sets of four reduction rules for internal infix
⍝ functions ≤ and ≥, which maintain [...] depth as a left argument.

⍝ Functions:

      ↑(+∘1)                    ⍝ primitive successor
      ↓(-∘1)                    ⍝ primitive predecessor

    → :()                       ⍝ item separator (cons)
    → /()                       ⍝ list separator
    → ≤() ≥()                   ⍝ skip left/right
    → ;()                       ⍝ tuple separator
    ← =() ≡()                   ⍝ reduction equivalence

⍝ Variables:

     m  n :: 0 →                ⍝ natural numbers
        p ::   →                ⍝ positive number
        s :: < > + - , .        ⍝ non-[] token
        t :: < > + - , . [ ]    ⍝ any token
    ss tt ::                    ⍝ token stream lists
    mm nn ::                    ⍝ memory tape lists
    ii oo ::                    ⍝ input/output lists

⍝ Reduction rules:
⍝
⍝     tokens    memory     i/o  →    tokens     memory    i/o
⍝     ------    ------     ---       ------     ------    ---
    +:ss/tt;  m:mm/nn;   ii/oo  =  ss/+:tt;  ↑m:mm/nn;  ii/oo       ⍝ + incr
    -:ss/tt;  m:mm/nn;   ii/oo  =  ss/-:tt;  ↓m:mm/nn;  ii/oo       ⍝ - decr
    >:ss/tt;  m:mm/nn;   ii/oo  =  ss/>:tt;   mm/m:nn;  ii/oo       ⍝ > right
    <:ss/tt;  mm/n:nn;   ii/oo  =  ss/<:tt;   n:mm/nn;  ii/oo       ⍝ < left
    ,:ss/tt;  m:mm/nn; n:ii/oo  =  ss/,:tt;   n:mm/nn;  ii/oo       ⍝ , input
    .:ss/tt;  m:mm/nn;   ii/oo  =  ss/.:tt;   m:mm/nn;  ii/m:oo     ⍝ . output

    [:ss/tt;  0:mm/nn;   ii/oo  =  1≥   ss/[:tt;  0:mm/nn;  ii/oo   ⍝ 0[ skip →
    [:ss/tt;  p:mm/nn;   ii/oo  =       ss/[:tt;  p:mm/nn;  ii/oo   ⍝ p[ cont
  ]:ss/t:tt;  p:mm/nn;   ii/oo  =  1≤ t:]:ss/tt;  p:mm/nn;  ii/oo   ⍝ p] skip ←
    ]:ss/tt;  0:mm/nn;   ii/oo  =       ss/]:tt;  0:mm/nn;  ii/oo   ⍝ 0] cont

    ⍝ [...] processing:                 ⍝  0[...[...]...]t...  skip right:
                                        ⍝  └──────→──────┘
      0 ≥   ss/tt  =       ss/tt        ⍝ matching ]: done
      p ≥ [:ss/tt  =  ↑p ≥ ss/[:tt      ⍝ skip over inner [] pair
      p ≥ ]:ss/tt  =  ↓p ≥ ss/]:tt      ⍝ end of [] pair
      p ≥ s:ss/tt  =   p ≥ ss/s:tt      ⍝ skip right over token

                                        ⍝  [t...[...]...p]...  skip left:
                                        ⍝   └─────←─────┘
    1 ≤   [:ss/tt  =         ss/[:tt    ⍝ matching [: done
    p ≤ ]:ss/t:tt  =  ↑p ≤ t:]:ss/tt    ⍝ skip over inner [] pair
    p ≤ [:ss/t:tt  =  ↓p ≤ t:[:ss/tt    ⍝ end of [] pair
    p ≤ s:ss/t:tt  =   p ≤ t:s:ss/tt    ⍝ skip left over token

⍝ Test cases:
⍝
⍝   +:∘/∘; 0:∘/∘;    ∘/∘  ->  ∘/+:∘;1:∘/∘;∘/∘       ⍝ +
⍝   -:∘/∘; 1:∘/∘;    ∘/∘  ->  ∘/-:∘;0:∘/∘;∘/∘       ⍝ -
⍝   >:∘/∘; 0:∘/∘;    ∘/∘  ->  ∘/>:∘;∘/0:∘;∘/∘       ⍝ >
⍝   <:∘/∘;   ∘/0:∘;  ∘/∘  ->  ∘/<:∘;0:∘/∘;∘/∘       ⍝ <
⍝   .:∘/∘; 0:∘/∘;    ∘/∘  ->  ∘/.:∘;0:∘/∘;∘/0:∘     ⍝ .
⍝   ,:∘/∘; 1:∘/∘;  0:∘/∘  ->  ∘/,:∘;0:∘/∘;∘/∘       ⍝ ,
⍝  [:+:]:∘/∘; 0:∘/∘; ∘/∘  ->  ∘/]:+:[:∘;0:∘/∘;∘/∘   ⍝ skip fwd
⍝  [:-:]:∘/∘; 5:∘/∘; ∘/∘  ->  ∘/]:-:[:∘;0:∘/∘;∘/∘   ⍝ clear memory
⍝
⍝ Output of sum of two numbers from input stream: 2+3 → 5:
⍝           ¯¯¯
⍝ ,:>:,:<:[:-:>:+:<:]:>:.:∘/∘; 0:0:∘/∘; 2:3:∘/∘ -> ∘/.:>:]:<:+:>:-:[:<:,:>:,:∘;5:∘/0:∘;∘/5:∘
⍝ , > , < [ - > + < ] > .      └──┬──┘  └──┬──┘      . > ] < + > - [ < , > ,   └──┬──┘ └─┬─┘
⍝            initial memory ──────┘        │                    final memory ─────┘      │
⍝       input/output stream ───────────────┘             input/output stream ────────────┘
⍝
⍝ Output of product of two numbers from input stream 2×3 → 6:
⍝           ¯¯¯¯¯¯¯
⍝ ,:>:,:<:[:>:[:>:+:>:+:<:<:-:]:>:>:[:<:<:+:>:>:-:]:<:<:<:-:]:>:>:.:∘/∘; 0:0:0:0:∘/∘; 2:3:∘/∘ -> ∘/.:>:>:]:-:<:<:<:]:-:>:>:+:<:<:[:>:>:]:-:<:<:+:>:+:>:[:>:[:<:,:>:,:∘;6:0:∘/3:0:∘;∘/6:∘
⍝ , > , < [ > [ > + > + < < - ] > > [ < < + > > - ] < < < - ] > > .      └────┬────┘  └──┬──┘      . > > ] - < < < ] - > > + < < [ > > ] - < < + > + > [ > [ < , > ,   └────┬────┘ └─┬─┘
⍝                                                        initial memory ──────┘          │                                                               final memory ──────┘        │
⍝                                                   input/output stream ─────────────────┘                                                        input/output stream ───────────────┘
⍝
⍝ This program, transliterated from Böhm's P" language, a precursor to BF,
⍝ returns the predecessor of a number represented in 2-adic number system:
⍝ ⍬ 1 2 11 12 21 22 111 112 121 ...
⍝
⍝   pred(8) → 7:
⍝
⍝ >:[:>:]:<:[:-:[:<:[:<:]:]:-:<:]:>:+:∘/∘; 1:1:2:0:∘/∘; ∘/∘ -> <:]:]:-:<:]:>:+:∘/[:<:[:-:[:<:]:>:[:>:∘;1:1:1:0:∘/∘;∘/∘
⍝   
⍝   Back to: Contents