~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a:: #→#→# / Ackermann's function.
a 0 n = +n
a (+m) 0 = a m 1
a (+m) (+n) = a m (a (+m) n)
a 2 2
7
b:: #→#→# / Ackermann's function (tail-recursive)
b m n = a[n,m]
. a ( 0: []) = 0
. a ( 0: 0:s) = a(1:s)
. a ( 0:+m:s) = a(1:m:s)
. a (+n: []) = +n
. a (+n: 0:s) = a(+(+n):s)
. a (+n:+m:s) = a(n:+m:m:s)
b 2 2
7
c:: #→#→#→# / Ackermann's other function:
c 0 m 0 = m / sum
c 0 m (+n) = +(c 0 m n)
c 1 m 0 = 0 / product
c 1 m (+n) = c 0 m (c 1 m n )
c (+(+k)) m 0 = 1 / exponent and beyond ···
c (+(+k)) m (+n) = c (+k) m (c (+(+k)) m n)
/ Then, using partial application (currying):
s = c 0 / sum
p = c 1 / product
e = c 2 / exponent
/ ... / ... and beyond.
s 3 2 / sum 3+2 1(+⍣⍵)⍺
5
p 3 2 / product 3×2 \ ⍺(+⍣⍵)0
6
e 3 2 / exponent 3*2 \ ⍺(×⍣⍵)1
9
c 3 2 2 / and beyond ... \ ⍺(*⍣⍵)1
4
// For more on these functions, search for "Ackermann" in min.dws/Background.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/ This is a Brainfuck interpreter,
/ written in a max interpreter,
/ written in an APL interpreter.
/ written in C.
/
/ Consequently, it is a little slow.
/
/ See: dfns.dws/notes.bf for a description of the language.
/
/ As Brainfuck is known to be Turing-complete, the ability to write Brainfuck
/ in max proves that max is also Turing-complete.
/
/ As max deals only in numbers, we translate BF opcodes into tokens 0-7:
/
/ [ ] < > + - . ,
/ 0 1 2 3 4 5 6 7
/
/ The token-stream and memory-tape are each implemented as a pair of lists,
/ with the current token or memory-cell being the head item of the right-
/ most of the pair.
/
/ To move along the token-stream or memory-tape to the right (say) we simply
/ pop an item from its right list and push it onto its left list, thus making
/ current the original cell's right neighbour.
/
/ .. a b [c] d e .. → .. b c [d] e f .. / moving along stream to right
/ ≡≡≡ / is equivalent to transferring
/ (b:a:..)(c:d:e:..) → (c:b:..)(d:e:f:..) / current item (c) to left.
/
/ Ditto moving left, mutatis mutandis.
/
/ The memory-tape is extended rightwards on demand by consing a 0 to an empty
/ right-list (substituting [0] for []).
/
/ a x(3:y) p(r:[]) i = a (3:x)y (r:p)[0] i / > extend tape.
/
/ This Brainfuck interpreter takes a list of number-tokens, translated as above,
/ and a second list from which input numbers are drawn. It returns a list of
/ output numbers. Therefore, b:: [#]→[#]→[#]
/
/ Inner function "a", where most of the action takes place, is of type:
/
/ a:: [#][#] [#][#] [#] → [#]
/ ├──┘ ├──┘ │ └── output list.
/ │ │ └──────── input list.
/ │ └─────────────── memory-tape lists.
/ └────────────────────── token-stream lists.
/
/ Local subfuctions of "a":
/
/ r skip Right from [ to find matching ].
/ l skip Left to find matching [ from ].
/
/ l and r ignore inner nested [] pairs by maintaining a depth parameter "d".
b t i = a []t [][0] i / brainfuck
. a x[] pq i = [] / no more toks:
. a x(0:y) p(+q:r) i = a (0:x)y p(+q:r) i / +p [ cont
. a x(0:y) p( 0:q) i = r (0:x)y 0 p( 0:q) i / 0 [ skip fwd
. . r x( 1 :y) 0 pq i = a ( 1 :x)y pq i / ] ≡
. . r x( 0 :y) d pq i = r ( 0 :x)y (+d) pq i / [[ →
. . r x( 1 :y) (+d) pq i = r ( 1 :x)y d pq i / ]] →
. . r x(+(+t):y) d pq i = r (+(+t):x)y d pq i / * →
. a x(1:y) p( 0:q) i = a (1:x)y p( 0:q) i / 0 ] cont
. a x(1:y) p(+q:r) i = l x(1:y) 0 p(+q:r) i / +p ] skip back
. . l (x:y)(0:z) 1 pq i = a (0:x:y)z pq i / [ ≡
. . l (x:y)(0:z) (+(+d)) pq i = l y(x:0:z) (+d) pq i / [[ ←
. . l (x:y)(1:z) d pq i = l y(x:1:z) (+d) pq i / ]] ←
. . l (x:y)(+(+t):z) d pq i = l y(x:+(+t):z) d pq i / * ←
. a x(2:y) (p:q)r i = a (2:x)y q(p:r) i / < tape left.
. a x(3:y) p(r:[] ) i = a (3:x)y (r:p)[0] i / > extend tape.
. a x(3:y) p(r:s:t) i = a (3:x)y (r:p)(s:t) i / > tape right.
. a x(4:y) p( q:r) i = a (4:x)y p(+q:r) i / + incr.
. a x(5:y) p(+q:r) i = a (5:x)y p( q:r) i / - decr.
. a x(6:y) p( q:r) i = q:a (6:x)y p( q:r) i / . output.
. a x(7:y) p( q:r) (i:j) = a (7:x)y p(i:r) j / , input,
b::
[#]→[#]→[#]
/ Standard bf code is shown commented to the right of the following examples:
b [4,6, 4,6, 4,6] [] / +. +. +.
[1,2,3]
b [7,3,7, 6,2,6] [8,9] / ,>, .<. reverse of 2-item input list.
[9,8]
s = b [ / sum of two input digits
7, / , 0: input m
3,7, / >, 1: input n
0, / [ 1: n ×
2,4, / <+ 0: incr m
3,5, / >- 1: decr n
1,2,6 / ]<. 0: output m+n
], s:: / display type of sum function:
[#]→[#]
s [5,8] / sum: 5+8 → 13
[13]
t = b [ / total of 0-terminated input list
3,7, / >, 1: first input
0, / [ 1: loop until 0 input
0, / [ 1: next value
2,4, / <+ 0: incr total
3,5, / >- 1: decr input
1, / ] 1: 0
7, / , 1: next input
1, / ] 1: 0
2,6 / <. 0: output total
], t:: / type of total function.
[#]→[#]
t [1,2,3,4,0] / +/1 2 3 4
[10]
t [0] / +/⍬
[0]
p = b [ / product of two input digits (Wikipedia).
7, / , 0: input m
3,7, / >, 1: input n
2,0, / <[ 0: m ×
3,0, / >[ 1: n ×
3,4, / >+ 2: incr total
3,4, / >+ 3: incr copy
2,2,5, / <<- 1: decr loop n
1, / ] 1: 0
3,3,0, / >>[ 3: copy ×
2,2,4, / <<+ 1: copy to n
3,3,5, / >>- 3: decr loop
1, / ] 3: 0
2,2,2,5, / <<<- 0: decr loop m
1, / ] 0: 0
3,3,6 / >>. 2: output m×n
]
p [2,3] / product: 2×3 → 6
[6]
b [6,4, 0, 6,4, 1] [] / .+ [ .+ ] infinite sequence
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,2
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
r:: #→[#]→# / radix-decode:
r n = d / auxiliary decode function.
. d [ 0] = 0 / decode [0] → 0.
. d [+i] = +i / decode [i] → i.
. d ( 0:j:k) = d (j:k) / ignore leading 0.
. d (+i:j:k) = c n (i:j:k) / carry base to next column.
. . c 0 (i:j:k) = d (i:j:k) / carry 0: done.
. . c (+m) (i:j:k) = c m (i:+j:k) / carry 1 → next col + base.
// examples:
r 1 [1,0,1,0,1,0] / unary decode (tally)
3
r 2 [1,0,1,0,1,0] / binary decode
42
r (+9) [1,2,3] / decimal decode
123
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
r:: (⍺→⍵→⍵)→⍵→[⍺]→⍵ / fold (reduce) right:
r f i [] = i
r f i (x:y) = f x (r f i y)
l:: (⍺→⍵→⍺)→⍺→[⍵]→⍺ / fold (reduce) left:
l f i [] = i
l f i (x:y) = l f (f i x) y
// examples:
r s 0 [1,2,3] / sum-reduce
. s 0 j = j
. s (+i) j = +(s i j)
6
l d 0 [1,2,3] / decimal-decode
. d 0 u = u
. d (+t) u = d t (+(+(+(+(+(+(+(+(+(+u))))))))))
123
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
g:: #→#→# / greatest-common-divisor:
g m n = h m n m n
. h 0 0 i j = 0
. h 0 (+n) i j = +n
. h (+m) 0 i j = +m
. h (+m) (+n) 0 0 = +m
. h (+m) (+n) 0 (+j) = h (+m) (+j) m j
. h (+m) (+n) (+i) 0 = h (+i) (+n) i n
. h (+m) (+n) (+i) (+j) = h (+m) (+n) i j
// examples:
[
g 6 9, / → 3
g 3 5, / → 1
g 0 3, / → 3
g 3 0, / → 3
g 3 3 / → 3
]
[3,1,3,3,3]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
m:: (⍺→⍵)→[⍺]→[⍵] / map (each):
m f [] = []
m f (x:y) = f x : m f y
// examples:
m + [0,1,2] / map successor
[1,2,3]
m (m+) [ / map map ..
[], / → []
[0], / → [1]
[1,2], / → [2,3]
[3,4,5] / → [4,5,6]
]
[[],[1],[2,3],[4,5,6]]
m r [ / map reverse
[], / → []
[0], / → [0]
[1,2], / → [2,1]
[3,4,5] / → [5,4,3]
]
. r = f []
. . f x [] = x
. . f x (y:z) = f (y:x) z
[[],[0],[2,1],[5,4,3]]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
p:: [#] / prime numbers:
p = s (i 2) / sieve primes from [2,3,4, ...
. s (0:y) = s y / skip multiple of prime.
. s (+i:y) = +i : s (z i y) / prime with zeros for multiples.
. . z 0 (x:y) = 0 : z i y / multiple: zero for head.
. . z (+j) (x:y) = x : z j y / otherwise: prime for head.
. i j = j : i (+j) / nums [j, +j, +(+j), ...
// example:
t p . t(a:b:c:x) = [a,b,c] / first three prime numbers.
[2,3,5]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
r:: #→#→# / residue (modulus):
r 0 0 = 0
r (+m) 0 = 0
r 0 (+n) = +n
r (+m) (+n) = s (+m) (+n) m n
. s m n 0 0 = 0
. s m n (+i) 0 = n
. s m n 0 (+j) = s m (+j) m (+j)
. s m n (+i) (+j) = s m n i j
// examples:
[
r 0 0, / → 0
r 0 3, / → 3
r 3 0, / → 0
r 3 6, / → 0
r 3 7, / → 1
r 3 8 / → 2
]
[0,3,0,0,1,2]
)
Back to: contents