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