~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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