⍝ 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