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