```~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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 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
```