Max
---
Max extends the Min programming language with:

    - Lists.
    - Local definitions.
    - Polymorphic types.

A  familiarity  with Min is assumed in describing the new language elements that
constitute this extension:

Lists
-----
A _list_ is a collection of items, all of the same type, whose explicit "length"
is  often of little interest. In fact, the single thing of interest about a list
is  whether  or not it's empty, and the only two things of interest about a non-
empty  list  are  the value of its head item, together with anything of interest
about its tail sub-list.

Lists are constructed using:

    - Datum: '[]', pronounced "null"; the empty list.

    - Infix function: ':', pronounced "cons"; the list constructor.

Informally,  cons  returns  its left argument hitched onto the front of its list
right argument. It is similar to the APL function: {(⊂⍺),⍵}.

Cons  binds  to the right with a strength weaker than that of function applicat-
ion.

        a:b:c ≡ a:(b:c)     / cons associates right.
        f a:b ≡ (f a):b     / cons binds weaker than function application.
        a:g b ≡ a:(g b)     /   ..      ..      ..      ..      ..

In  a perhaps uncharacteristic concession to legibility, Max displays lists as a
sequence  of  bracket-enclosed,  comma-separated items; a form which may also be
used for input: [a,b,c] ≡ a:b:c:[].

        1:2:3:[]
    [1,2,3]

        [1,2,3]
    [1,2,3]

        +0 : [+(+0),+2]
    [1,2,3]

Lists may be nested:

        [1,2]:[3,4]:[]
    [[1,2],[3,4]]

··· but must be uniform:

        [2,[3,4]]
    ?

The segments of a compound statement are separated by commas and like APL, eval-
uated  from  left  to right. Output from any of the segments is displayed on the
following line, separated by commas.

        i=1, +i, [i,+i], ~i             / compound statement.
    2, [1,2]

Cons is used in function argument patterns to deconstruct lists:

        f (x:y) = x                     / First item.

        f [2,3,4]
    2
        l (x:[]) = x                    / Last item.
        l (x:y:z) = l (y:z)

        l [[1],[1,2],[1,2,3]]
    [1,2,3]

    ~ f l

Functions  (and their argument patterns) may combine natural number and list ex-
pressions.

        s []     = 0                    / Sum total of list of natural numbers.
        s (0:y)  = s y
        s (+i:y) = +(s(i:y))

        s [2,3,4]
    9
        i 0    (x:y) = x                / I'th item of list.
        i (+j) (x:y) = i j y

        i 1 [2,3,4]
    3

In  common with Min, functions may take function arguments. The following "high-
order" functions correspond to APL's each and reduce operators:

Map  applies its  (function)  first  argument  to each item in its (list) second
argument.

        m f []    = []                  / Map (each)
        m f (x:y) = f x : m f y

        m + [2,3,4]                     / map succ over a list of numbers.
    [3,4,5]

Fold  applies its function first argument between each pair of items in its list
third argument. The second argument is an identity for the null list.

        f g i []    = i                 / Fold (reduce) from the right.
        f g i (x:y) = g x (f g i y)

For example, if 'p' is arithmetic product:

        p 0 j    = 0                    / Product, in terms of
        p (+i) j = s [j, p i j]         / sum (defined above) and product.

then:

        f p 1 [2,3,4]                   / Fold product with identity: 1.
    24

Min's  remove command: ~ has been extended: '~' removes names that appear to its
right,  returning  any  that remain. Thus '~~' (pronounced "retain") removes all
but the specified names. In particular, ~~ in isolation removes all names and is
equivalent  to  APL's )CLEAR. We will retain the definitions of map (m) and fold
(f) to use in some of the examples that follow.

        ~~mf                            / retain only m and f.
    m f

Local Definition
----------------
A  sequence  of  dots (pronounced "where") following an expression, introduces a
definition _local_ to the expression.

        [x,x] . x=4                 / A list of x's where x is 4.
    [4,4]

Dots associate right and have a binding strength weaker than that of '='.

        f a  .  f = +  .  a = 0     / ≡ (f a) . ((f=+) . (a=0))
    1

Sequences  of dots of differing length have the same meaning, except that longer
sequences bind tighter than shorter ones.

        a=bc .  bx=a(ax) .. a=+  .  c=+a .. a=0    ≡
        a=bc . (bx=a(ax) .. a=+) . (c=+a .. a=0)

All  becomes  clear  if we arrange the expression over several lines and use the
dots  to  indent  local  definitions. The indentation shows the lexical scope of
each defined name. The example above then becomes:

        a = b c                     / a global
        .   b x = a ( a x )         / b local to global a
        .   .   a = +               / a local to local b
        .   c = + a                 / c local to global a
        .   .   a = 0               / a local to local c

The  following  definition of arithmetic product uses a local auXiliary function
with a third argument to "remember" the multiplier.

        p = x 0
        .   x 0    0    k = 0
        .   x 0    (+j) k = x k j k
        .   x (+i) j    k = +(x i j k)

        p 4 5
    20

        ~ a p                       / remove both global definitions.
    m f

Note how we can embed transient local definitions within larger expressions:

        (t . t f x = f(fx)) + 0     / twice succ 0.
    2
        ~                           / Notice, no residual definition of t.
    m f

Max's full binding strength and associativity table is:

                         Strength Binds
                         -------- -----
         Function application   6 Left
                         Cons : 5 Right
           Lambda abstraction \ 4 Right *
                   Definition = 3 Right
                        Where . 2 Right
               Item separator , 1 Right
          Statement separator , 0 Left

* "Raw"  lambda  abstractions are not part of the Max language, but happen to be
  admitted as an extension by this particular implementation.

Continuation lines
------------------
A  Max expression can extend over a number of lines. If the current line ends in
an  incomplete way, or in the case of input from a script, the following one be-
gins  in an incomplete way, then the lines are concatenated prior to evaluation.
This process is repeated for any number of following lines.

The current line is deemed incomplete if, disregarding comments:

- There are more opening than closing brackets or parentheses.
- Disregarding  white space, it ends with a dot.

The following line is deemed incomplete if, disregarding white space:

- It starts with a dot.

As  an example, the following (single) expression applies a function picked from
a list of functions, to its list argument.

        p 2 [                       / Pick 2th function from list.
            f . f x = h x,          / head,
            f . f x = h (t x),      / head of tail,
            f . f x = h (t(t x)),   / head of tail of tail,
        ] [
            2, 3, 4, 5,             / list of
            6, 7, 8, 9              / numbers.
        ]
        .   p 0      = h            / Pick: 0th item is head.
        .   p (+i) y = p i (t y)    /       +ith item is ith item of tail.
        .   h (x:y)  = x            / head
        .   t (x:y)  = y            / tail
    4

When input is from the keyboard, the prompt during an incomplete expression con-
tains  "white dots",  invisible to the interpreter: one to indicate that the ex-
pression is incomplete, and an extra one for each level of nesting.

        [
    ·   ·   [1,2],
    ·   ·   [
    ·   ·   ·   3,
    ·   ·   ·   4
    ·   ·   ],
    ·   ·   [5,6]
    ·   ]
    [[1,2],[3,4],[5,6]]

Note  that when a line input from the keyboard is to be followed by a local def-
inition,  the  "where dot" must follow the initial line to delay its evaluation.
Otherwise,  names  referenced  in  the line will be satisfied from the preceding
global, rather than the following local, environment.

        f 0 .
    ·   ·   f = +
    1

Alternatively, the multi-line input can be "captured" in enclosing parentheses.

    (
·   ·   r = x []
·       .   x a [] = a
·       .   x a (b:c) = x (b:a) c
·   )
    r[1,2,3]
[3,2,1]

Type
----
We indicate the type of an expression using the following notation:

        ::      "is of type:", or informally: "is a".
        ⍺..⍵    Greek letters stand for arbitrary types.
        #       Natural number (pronounced "num").
        [⍺]     List of type ⍺.
        ⍺→⍵     Function from type ⍺ to type ⍵.

For example:

        i :: #          / i is of type: num.
        v :: [#]        / v is a list of nums.
        m :: [[#]]      / m is a list of lists of nums.
        s :: #→#        / s is a function from num to num.
        l :: [⍺]→#      / l is a function from a list of anything to num.

Following an expression with ::, displays its type rather than its value.

        +3 ::               / num
    #
        [[1,2],[]] ::       / list of lists of nums.
    [[#]]
        f . f x = 0 ::      / function from anything to num.
    ⍺→#
        [f.fx=+(+n)] ::     / list of functions from num to num.
    [#→#]

Remember that a function given fewer than its defined number of arguments yields
a function of the remaining ones. For example, if "s" sums its two arguments:

        s 2 3
    5

This expression is interpreted as:

        (s 2) 3                 / function (s 2) is applied to 3.
    5

The type of such a function is therefore:

        s :: #→(#→#)            / s takes a num and returns a function.

In  this case, as the function type constructor '→' associates right, the paren-
theses are superfluous.

        s ::                        / type of sum
    #→#→#
        s 2 ::                      / type of sum 2
    #→#
        s 2 3 ::                    / type of sum 2 3
    #

        m ::                        / type of map
    (⍺→⍵)→[⍺]→[⍵]
        m + ::                      / type of map succ
    [#]→[#]
        m (i.ix=x) [] ::            / type of map id over null
    [⍺]

        f ::                        / type of fold right (foldr)
    (⍺→⍵→⍵)→⍵→[⍺]→⍵
        f (c.cxy=x:y) ::            / type of fold cons
    [⍺]→[⍺]→[⍺]

        g f i [] = i                / defn of fold left (foldl)
        g f i (x:y) = g f (fix) y
        g::                         / type of foldl
    (⍺→⍵→⍺)→⍺→[⍵]→⍺

Type Declaration
----------------
Although  explicit  type declarations need not be given, Max is a strongly typed
language.  Each  expression is type-checked prior to evaluation and an error re-
ported if there is an inconsistency.

        +[1,2,3]                    / succ of list?
    ?

However,  types  may  be specified explictly as a cross-check and to enhance the
legibility of a script.

        s :: #→#→#                  / Sum of two nums, producing a num.

        s 0    j = j                / definition ···
        s (+i) j = +(s i j)         / ··· of sum.

Notice how a more general type is refined by subsequent definition.

        ~s                          / remove Sum.
    m f
        s :: ⍺→⍵                    / declare an over-general type.

        s 0 j = j                   / partial definition,
        s::                         / refines type.
    #→⍺→⍺

        s (+i) j = +(s i j)         / complementary definition,
        s::                         / refines type still further.
    #→#→#

A definition or type declaration that conflicts with Max's current notion of its
type is rejected:

        ~s                          / remove s
    m f
        s :: ⍺→[⍺]→[⍺]              / erroneous declaration for Sum.

        s 0 j = j                   / partial definition refines type.
        s::
    #→[#]→[#]

        s (+i) j = +(s i j)         / conflicting definition rejected.
    ?

The only way out of this, is to remove the definition and start again.

        ~~mf
    m f

Arrays
------
Vectors  can  be  represented  by  lists; matrices by lists of lists; and so on.
However,  arrays  which  are  empty  along  an axis other than the last, cause a
problem.  [[],[],[]]  represents  a  matrix  of  3  rows and 0 columns, but this
simple  representation  can't  cope  with a matrix of 0 rows and 3 columns. This
restriction  apart,  we can code all of our familiar array functions and operat-
ors.

    x :: (⍺→⍵→∊)→[⍺]→[⍵]→[[∊]]              / Cross (outer) product

        x f []    c = []                    / cross product of first axes.
        x f (a:b) c = m (f a) c : x f b c   / (using map)

        a = x s [0,3] [1,2,3]               / sum-cross product of vectors.
        .   s 0    j = j                    / sum :: #→#→#
        .   s (+i) j = +(s i j)

        a                                   / a :: [[#]]
    [[1,2,3],[4,5,6]]


    r :: [[⍺]]→[⍺]                          / Ravel first two axes ,[2↑⍴⍵]⍵

        r []        = []
        r ([]:z)    = r z
        r ((x:y):z) = x : r (y:z)

        r a
    [1,2,3,4,5,6]


    o :: [[⍺]]→[[⍺]]                        / TranspÔse (⍉) first 2 axes.

        o ([]:z)    = []                    / no cols: no rows.
        o ((x:y):z) = m h a : o (m t a)     / firsts cons transpose lasts.
        .   a = (x:y):z                     / matrix arg.
        .   h (x:y) = x                     / head
        .   t (x:y) = y                     / tail

        o a
    [[1,4],[2,5],[3,6]]


    d :: (⍺→⍺→⍺)→(⍺→⍺→⍺)→[[⍺]]→[[⍺]]→[[⍺]]      / Inner (Dot) product.

        d s p a b = m (m (f s)) (x g a (o b))   / Dot product using map and
        .   g a b = m (f p) (o[a,b])            / cross product.
        .   f g (x:[])  = x                     / Fold1 :: (⍺→⍺→⍺)→[⍺]→[⍺]
        .   f g (x:y:z) = g x (f g (y:z))       / undefined for null list.

        d s p a (o a)                           / (APL: a+.×⍉a)
        .   p 0    j = 0                        / product :: #→#→#
        .   p (+i) j = s (p i j) j              /   in terms of sum.
        .   s 0    j = j                        / sum :: #→#→#
        .   s (+i) j = s i (+j)                 /   in terms of succ.
    [[14 32],[32 77]]

Infinite Lists
--------------
Lists can be of infinite length:

        q n = n : q (+n)                / infinite seQuence.
        q 0
    [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,2

        c l = x l l                     / infinite cyCle.
        .   x []    l = x l l           / exhausted: reuse list.
        .   x (a:b) l = a : x b l

        c [1,2,3,4]
    [1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,,4,1,


Max's  evaluation  is lazy; values are computed as needed, so infinite lists may
be passed as arguments to functions.

        c (c [1,0])                     / infinite cycle of infinite cycle.
    [0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1

        t 0    z     = []               / Take :: #→[⍺]→[⍺]
        t (+i) (x:y) = x : t i y

        t 5 z . z = 0:z                 / first items of infinite list.
    [0,0,0,0,0]

        t 4 (q 3)                       / first items of infinite sequence.
    [3,4,5,6]

Using map (m), take (t) and sequence (q) defined above:

        m x (q 1) . x n = t n (q 1)     / infinite sequence of sequences.
    [[1],[1,2],[1,2,3],[1,2,3,4],[1,2,3,4,5],[1,2,3,4,5,6],[1,2,3,4,5,6,7],[1,2,

Naïve implementations of lazy functional languages are notoriously sluggish. Al-
though the following examples are formally correct, you might want to take a cup
of coffee while waiting for the first few terms to appear.

Fibonacci sequence:

        f 0 1 0 1                           / Fibonacci     :: [#]
        .   f a b 0    d = a : f b d b d
        .   f a b (+c) d =     f a b c (+d)
    [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,

(All of the) prime numbers using the "Sieve of Eratosthenes."

        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), ...
    [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,

Extended Max
------------
Max  (like Min)  comes in both a pure and extended form. The pure form is as de-
scribed above, whereas the extended form might expose elements of the underlying
implementation  and may differ from one implementation to another. Specifically,
this  particular  implementation which uses lambda calculus and combinators, ex-
poses both of these devices.

In addition to Max's two primitive functions: succ (+) and cons (:), this imple-
mentation  admits raw lambda and combinator expressions, together with seven ex-
tra "internal" primitive functions. The full  set, each with its approximate APL
equivalent (in ⎕ml≥2, so that ↑ means first) is:

    Natural number functions:

        + Succ      ~ {⍵+1}                     / successor.
        - Pred      ~ {⍵-1}                     / predecessor.
        ! Nil?      ~ {n t f←⍵ ⋄ 0=n:t⋄f}       / test for zero.

    List Functions:

        : Cons      ~ {(⊂⍺),⍵}                  / infix list construction.
        ⊂ Link      ~ {h t←⍵ ⋄ (⊂h),t}          / prefix list construction.
        ↑ Head      ~ {↑⍵}                      / head of list.
        ↓ Tail      ~ {1↓⍵}                     / tail of list.
        ∘ Null?     ~ {l t f←⍵ ⋄ 0=⍴l:t⋄f}      / test for empty list.

    Self Reference:

        ∇ FixPoint  ~ ⍺⍺∘∇  ~ ∇f ≡ f(∇f)        / iterate.

Character '\' is used to represent lambda.

For example:

        (\fx.f(fx))(\fx.f(fx))+0                / Twice twice succ 0
    4
        ∇(\nx.∘x0(+(n(↓x))))[1,1,1]             / Length of list
    3

If the compiler/optimiser is working correctly, the lambda equivalent of each of
the supported combinators, should reduce to the combinator itself.

    \x.x
I
    \cx.c
K
    \fgx.fx(gx)
S
    \fgx.f(gx)
B
    \fgx.fxg
C
    \cfgx.c(fx)(gx)
Ⓢ
    \cfgx.c(fx)g
Ⓒ
    \cfgx.c(f(gx))
Ⓑ

Max can infer the type of a lambda abstraction:

    \fgx.fx(gx) ::      / distributor: S.
(⍺→⍵→∊)→(⍺→⍵)→⍺→∊

Experimenting  with  arbitrary  lambda  abstractions gives some insight into the
workings of combinator expressions.

    \abcd.a
ⒷKKK
    \abcd.b
K(BKK)
    \abcd.c
K(KK)
    \abcd.d
K(K(KI))

As with Min, we can work directly with raw combinator expressions.

        Y(B(S(C∘0))(C(Ⓑ+)↓))[1,1,1]             / Length of list
    3

The above combinator coding is not quite the intellectual feat it might at first
appear. To produce it, we just have Max display the value of the length function
compiled  from  the preceding lambda definition. The function as compiled is not
quite  in normal form and displaying its value directly, would cause a reduction
of ∇, the fixpoint function ∇f → f(∇f). To suppress this, we apply a K combinat-
or,  which  as it requires two arguments, renders the expression as a whole, ir-
reducible.

        ∇(\nx.∘x0(+(n(↓x))))                    / Reduce Length function.
    S(C∘0)(C(Ⓑ+)↓(Y(B(S(C∘0))(C(Ⓑ+)↓))))

        K (∇(\nx.∘x0(+(n(↓x)))))                / Reduction suppressed by K.
    K(∇(B(S(C∘0))(C(Ⓑ+)↓)))

The  required expression is now apparent inside K(···) if we take into consider-
ation that the FixPoint function ∇ and the Y combinator are synonymous.

It is this ability to reinput generated combinator expressions that dictates the
conversion  of the infix form (:) to the prefix form (⊂) of cons. Otherwise, the
following sequence would not work:

    z=0:z       / infite list of zeros.

    z           / display infite list.
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

    Kz          / suppress reduction.
K(Y(⊂0))

    Y(⊂0)       / evaluate raw combinator expression.
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

Playing with Types
------------------
We can show the type of an arbitrary (though well-typed) combinator expression:

      max''

    KISSY::
(((⍺→⍵)→⍺→⍵)→⍺)→((⍺→⍵)→⍺→⍵)→⍵

    B::
(⍺→⍵)→(∊→⍺)→∊→⍵
    BB::
(⍺→⍵→∊)→⍺→(⍳→⍵)→⍳→∊
    BBB::
(⍺→⍵)→(∊→⍳→⍺)→∊→⍳→⍵
    BBBB::
(⍺→⍵→∊→⍳)→⍺→⍵→(⍴→∊)→⍴→⍳
    BBBBB::
(⍺→⍵)→(∊→⍺)→(⍳→∊)→⍳→⍵
    BBBBBB::                    / [1]
(⍺→⍵→∊)→(⍳→⍺)→⍳→(⍴→⍵)→⍴→∊
    BBBBBBB::                   / [2]
(⍺→⍵→∊)→⍺→(⍳→⍴→⍵)→⍳→⍴→∊
    BBBBBBBB::
(⍺→⍵)→(∊→⍳→⍴→⍺)→∊→⍳→⍴→⍵
    BBBBBBBBB::
(⍺→⍵→∊→⍳→⍴)→⍺→⍵→∊→(∆→⍳)→∆→⍴
    BBBBBBBBBB::
(⍺→⍵→∊)→(⍳→⍺)→⍳→(⍴→⍵)→⍴→∊       / same as [1]
    BBBBBBBBBBB::
(⍺→⍵→∊)→⍺→(⍳→⍴→⍵)→⍳→⍴→∊         / same as [2]
    BBBBBBBBBBBB::
(⍺→⍵)→(∊→⍳→⍴→⍺)→∊→⍳→⍴→⍵         / ... etc.
    BBBBBBBBBBBBB::
(⍺→⍵→∊→⍳→⍴)→⍺→⍵→∊→(∆→⍳)→∆→⍴

    SICK::                      / ill-typed expression.
?
    )

Environment
-----------
In  common  with  Min, a Max session returns its current set of definitions as a
shy  result. This result may then be reinput via Max's left argument as an init-
ial environment to a subsequent session.

          ListFns←max''                 ⍝ Make new environment.

        n = q 0 . q n = n : q (+n)      / Natural numbers :: [#]

        t 0    z     = []               / Take :: #→[⍺]→[⍺]
        t (+i) (x:y) = x : t i y

        t 4 n                           / test functions.
    [0,1,2,3]
        )                               / quit Max session.

    ⍝ Workspace variable ListFns now contains a definition for take, and the
    ⍝ _infinite_ set of natural numbers!

          ListFns max←''                ⍝ Revise ListFns environment.
        ~                               / definitions.
    n t
        d 0    z     = z                / Drop :: #→[⍺]→[⍺]
        d (+i) (x:y) = d i y

        t 4 (d 3 n)                     / test functions.
    [3,4,5,6]
        )                               / quit.

Back to: contents