Background ---------- Min is a tiny functional language whose complete reference manual is: ┌──────────────────────────────────────────────────────────────────────────────┐ │ stmt := expr | temp = expr / Statement. │ │ temp := name | name args / Template. │ │ args := patn | patn args / Function arguments. │ │ patn := name | numb | (pfun patn) / Pattern argument. │ │ expr := prim | expr expr | (expr) / Expression. │ │ prim := name | numb | pfun / Primitive object. │ │ name := a-z / Single character name. │ │ numb := 0-9 / Single digit number. │ │ pfun := + / Primitive function. │ │ │ │ Min's only data type is the non-negative "natural number": 0, 1, 2, ··· │ │ Only single digits 0-9 may be entered, but larger numbers may result. │ │ A name must be a single lower-case letter: a, b, ··· z. │ │ Min's sole primitive function: '+', denotes its argument's successor. │ │ Functions are defined thus: name arg arg ··· = expression. │ │ Arguments may be numbers: 0, 1, 2, ··· or patterns: i, (+i), (+(+i)), ··· │ │ A function given too few arguments, yields a function of remaining ones. │ │ Unlike APL, function application associates left, E.g.: a b c ≡ (a b) c. │ │ Blanks are ignored as is the character '/' and anything to its right. │ │ Appending ';' to an expression causes its evaluation to be traced. │ │ │ │ System command: ~ Removes definitions and displays remaining ones. │ │ ) Exits from Min with current definitions as shy rslt. │ └──────────────────────────────────────────────────────────────────────────────┘ Well established techniques exist for implementing functional languages. Min uses SK combinator reduction, in which definitions are translated first into lambda calculus, and then into expressions using a small set of function combin- ators: Ix = x / Identity Kcx = c / Cancellator Sfgx = fx(gx) / Distributor Bfgx = f(gx) / Compositor Cfgx = fxg / Permutator $cfgx = c(fx)(gx) / S' ¢cfgx = c(fx)g / C' &cfgx = c(f(gx)) / B* Yx = x(Yx) / Fixpoint To avoid a separate lexical pass, each combinator is written as a single char- acter, which also serves as a token in the compiled code. For this reason, comb- inators S', C' and B* are represented by the (arguably) visually suggestive $, ¢ and &, respectively. A combinator is simply a function that makes no external reference. Its result is therefore merely a re-arrangement of (some of) its arguments and possibly, as in the case of the Y combinator, a recursive reference to itself. Combinators originated in the field of Combinatorial Logic in the 1920-30's, the symbols I, K, S standing for Identitätsfunktion, Konstanzfunktion and Ver- Schmelzungsfunktion respectively. See function "combo" to investigate and extend Min's set of combinators. Com- menting out lines from the 'opt' optimisation section of combo, would cause Min to fire on fewer cylinders, so to speak. In the limit, only combinators: S, K and Y would be employed, resulting in a dramatic loss of performance. For example, the definition of "sum" given in the Example script: s 0 j = j / Sum: is defined recursively s i j ≡≡ i+j s (+i) j = +(s i j) / in terms of successor and sum. compiles to the following optimised code: Y(B(S(C!I))(¢B(B(B+))-)) whereas, removing all optimisation yields the following functionally equivalent but slower version: Y(S(S(KS)(S(S(KS)(S(S(KS)(S(KK)(K!)))(S(S(KS)(KK))(KK))))(S(S(KS)(S(S(KS)(S(KK)( KS)))(S(KK)(KK))))(S(KK)(KK)))))(S(S(KS)(S(S(KS)(S(S(KS)(S(KK)(KS)))(S(S(KS)(S(S (KS)(S(KK)(KS)))(S(S(KS)(S(KK)(KK)))(S(KK)(KS)))))(S(S(KS)(S(S(KS)(S(KK)(KS)))(S (S(KS)(S(KK)(KK)))(S(KK)(KK)))))(S(S(KS)(S(KK)(KK)))(S(KK)(K+)))))))(S(S(KS)(S(S (KS)(S(KK)(KS)))(S(S(KS)(S(S(KS)(S(KK)(KS)))(S(S(KS)(S(KK)(KK)))(S(KK)(KS)))))(S (S(KS)(S(S(KS)(S(KK)(KS)))(S(S(KS)(S(S(KS)(S(KK)(KS)))(S(S(KS)(S(KK)(KK)))(S(KK) (KS)))))(S(S(KS)(S(S(KS)(S(KK)(KS)))(S(S(KS)(S(KK)(KK)))(S(KK)(KK)))))(S(S(KS)(S (KK)(KK)))(S(KK)(SKK)))))))(S(S(KS)(S(S(KS)(S(KK)(KS)))(S(S(KS)(S(KK)(KK)))(S(KK )(KK)))))(S(S(KS)(S(S(KS)(S(KK)(KS)))(S(KK)(KK))))(S(KK)(KK))))))))(S(S(KS)(S(S( KS)(S(KK)(KS)))(S(S(KS)(S(S(KS)(S(KK)(KS)))(S(S(KS)(S(KK)(KK)))(S(KK)(KS)))))(S( S(KS)(S(KK)(KK)))(S(KK)(KK))))))(S(S(KS)(S(KK)(KK)))(S(KK)(KK)))))))(S(S(KS)(S(K K)(K-)))(S(S(KS)(KK))(KK))))) The lack of Curry's optimisation: S(Kp)(Kq) => K(pq), accounts for much of the bloat in the above result. Reenabling just this line in combo:opt, produces a much leaner combinator expression, which still employs only S, K and Y. Y(S(K(S(S(S(K!)(SKK))(K(SKK)))))(S(S(KS)(S(KK)(S(K(S(K(S(K+)))))(S(S(KS)(S(K(S(K S)))(S(K(S(KK)))(S(S(KS)(S(KK)(SKK)))(K(SKK))))))(K(K(SKK)))))))(K(S(K-)(SKK)))) ) Introducing the I combinator Ix => x and optimisations SKK => I and S(Kp)I => p, shortens the object code still further: Y(S(K(S(S!(KI))))(S(S(KS)(S(KK)(S(K(S(K+))))))(K-))) ... and so on. Incidentally, the Y combinator may itself be replaced with an S, K expression: Y = SSK(S(K(SS(S(SSK))))K) / John Tromp in: Li and Vitanyi [1997]. Min's performance could be improved significantly by extending the set of com- binators (see Turner 1981). Possibilities include: tab: Wfx = fxx opt: SpI → Wp / Warbler Txf = fx SI(Kp) → Tp / Thrush Although not strictly part of the Min language, this implementation accepts and evaluates expressions containing raw combinators, together with two additional "internal" primitive functions. - n → n-1 / pred[ecessor] ! n t f → n=0:t⋄f / nil? A lambda expression is represented as a 3-item nested array. The first item at each level in this tree is the node type: either '@' for an apply node or '\' for a lambda node. The type is followed by: function and argument for an apply node, and bound variable and body for a lambda node. Compilation from lambda expression into combinator expression removes all lambda nodes, leaving only apply nodes. The resulting simplification in the reduction process is the main advantage of the combinator approach. The following D-functions implement Min: Min accumulation of definitions and evaluation of expressions. Defn environment extended with new definitions. Parse expression tree from source character vector. Compile combinator expression from lambda expression. Combo combinator definitions and optimisations. Reduce reduction of combinator expression to (weak head) normal form. Trace traced reduction of combinator expression. Format linear representation of lambda expressions. Trees tree representation of expressions. We can experiment with these functions using "trees" and by tracing their evalu- ation: trees parse'tfx=f(fx)' ⍝ Parse tree for equation. ┌─=─┐ ┌─@┐ ┌@─┐ ┌@┐ x f ┌@┐ t f f x Min maintains its environment (symbol table) as a 3-vector of vectors of: names, lambda-definitions and combinator-definitions. Lambda representations of suc- cessive equations in a function definition are merged into the lambda-definition which is then compiled into its combinator equivalent. For example, make a new environment with a definition for function "t". The dis- play (see dfns.dws/notes.disp) shows the resulting environment. etab ← disp∘trees ⍝ display of environment table. etab env←defn parse'tfx=f(fx)' ┌→┬─────────┬─────┐ ↓ │┌\─┐ │ │ │ │f ┌\─┐ │ ┌─@┐│ │t│ x ┌@─┐ │┌@┐ I│ │ │ f ┌@┐│S B │ │ │ f x↓ ↓ └─┴────────→┴────→┘ Now extend this environment with the first equation for sum: "s". Note the pre- ence of the error token ? in both the lambda and combinator representations of s. This represents a missing case: etab env←env defn parse's0j=j' ┌→┬─────────┬───────┐ ↓ │┌\─┐ │ │ │ │f ┌\─┐ │ ┌─@┐ │ │t│ x ┌@─┐ │ ┌@┐ I │ │ │ f ┌@┐│ S B │ │ │ f x↓ ↓ ├─┼────────→┼──────→┤ │ │ ┌\───┐ │ ┌───@┐│ │ │ ∆ ┌──@┐ │┌@──┐ ?│ │s│ ┌─@─┐ ? │C ┌─@┐ │ │ │┌@┐ ┌\┐ │ ┌@┐ I │ │ │! ∆ j j ↓ C ! ↓ └─┴────────→┴──────→┘ Lastly, extend the definition of "sum" with a complementary second equation. Note how the lambda definition is enlarged by replacing its "?" node with the second part of the definition. Note also, how the corresponding combinator (compiled) definition is also enlarged. etab env←env defn parse's(+i)j=si(+j)' ┌→┬───────────────────┬─────────────────────┐ ↓ │ ┌\─┐ │ │ │ │ f ┌\─┐ │ ┌─@┐ │ │t│ x ┌@─┐ │ ┌@┐ I │ │ │ f ┌@┐ │ S B │ │ │ f x ↓ ↓ ├─┼──────────────────→┼────────────────────→┤ │ │ ┌\────┐ │┌@───────┐ │ │ │ ∆ ┌───@───────┐ │Y ┌──────@─────────┐ │ │ │ ┌─@─┐ ┌─────@─┐ │ ┌@─┐ ┌─────@┐│ │s│┌@┐ ┌\┐ ┌\─┐ ┌@┐│ B ┌@──┐ ┌─@────┐ -│ │ │! ∆ j j i ┌\──┐ - ∆│ S ┌─@┐ ┌@┐ ┌──@┐ │ │ │ j ┌─@─┐ │ ┌@┐ I ¢ B ┌@─┐ + │ │ │ ┌@┐ ┌@┐ │ C ! C ┌@┐ │ │ │ s i + j ↓ ¢ B ↓ └─┴──────────────────→┴────────────────────→┘ Or, displayed in linear form: disp format env ┌→┬─────────────────────────────┬─────────────────────────┐ ↓t│ \fx.f(fx) │ SBI │ ├─┼────────────────────────────→┼────────────────────────→┤ │s│\∆.!∆(\j.j)((\ij.si(+j))(-∆))│Y(B(S(C!I))(¢B(C(¢B)+)-))│ └─┴────────────────────────────→┴────────────────────────→┘ Use this environment to compile an expression: trees exp←env compile parse'tt+0' ┌─@┐ ┌────@┐ 0 ┌─@───┐ + ┌─@┐ ┌─@┐ ┌@┐ I ┌@┐ I S B S B Or in linear form: format exp SBI(SBI)+0 Trace the reduction of the expression: trace exp SBI(SBI)+0 ¯¯¯¯¯¯¯¯ B(SBI)(I(SBI))+0 ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ SBI(I(SBI)+)0 ¯¯¯¯¯¯¯¯¯¯¯¯ B(I(SBI)+)(I(I(SBI)+))0 ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ I(SBI)+(I(I(SBI)+)0) ¯¯¯¯¯¯ SBI+(I(I(SBI)+)0) ¯¯¯¯ B+(I+)(I(I(SBI)+)0) ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ +(I+(I(I(SBI)+)0)) ¯¯ +(+(I(I(SBI)+)0)) ¯¯¯¯¯¯¯¯¯¯ +(+(I(SBI)+0)) ¯¯¯¯¯¯ +(+(SBI+0)) ¯¯¯¯ +(+(B+(I+)0)) ¯¯¯¯¯¯¯ +(+(+(I+0))) ¯¯ +(+(+(+0))) ¯¯ +(+(+1)) ¯¯ +(+2) ¯¯ +3 ¯¯ 4 On exit, Min's current environment is returned as a shy result which can be re- input via the left argument, as an initial environment for a later session. math←min'' ⍝ Define math functions. s i 0 = i / Sum: is defined recursively s i (+j) = +(s i j) / in terms of successor and sum. p 0 j = 0 / Product: is defined recursively p (+i) j = s j (p i j) / in terms of sum and product. ) / Quit, returning environment. Dyalog's modified assignment syntax provides a convenient idiom for editing en- vironments. In the following, the definition of sum is revised: math min←'' ⍝ Edit 'math' functions. ~s / Remove definition of sum. p s 0 j = j / Sum: is defined recursively s (+i) j = s i (+j) / in terms of successor and sum. ) disp format math ┌→┬──────────────────────────────┬────────────────────────────────────────────── ↓p│\∆.!∆(\j.0)((\ij.sj(pij))(-∆))│Y(B(S(C!(K0)))(¢B(B(S(Y(B($S(C!))(¢C(&B(B+))-) ├─┼─────────────────────────────→┼────────────────────────────────────────────── │s│\∆.!∆(\j.j)((\ij.si(+j))(-∆)) │ Y(B(S(C!I))(¢B(C(¢B)+)-)) └─┴─────────────────────────────→┴────────────────────────────────────────────── Typing the name of a function displays its combinator definition. This imple- mentation of Min accepts and evaluates such "raw" combinator expressions. min'' tfx=f(fx) / definition of twice. t / value of twice. SBI SBI+ / t+ B+(I+) B+(I+)0 / t+0 2 Functions are not evaluated at definition time. Tracing the evaluation of funct- ion "s" shows that it takes two steps to reduce it to a normal form. s 0 j = j / definition of sum. s (+i) j = s i (+j) s; Y(B(S(C!I))(¢B(C(¢B)+)-)) ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ B(S(C!I))(¢B(C(¢B)+)-)(Y(B(S(C!I))(¢B(C(¢B)+)-))) ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ S(C!I)(¢B(C(¢B)+)-(Y(B(S(C!I))(¢B(C(¢B)+)-)))) We can work with any of the above 3 equivalent values of sum. Choosing the first one (just because it's shortest): Y(B(S(C!I))(¢B(C(¢B)+)-)) 2 / sum 2 B(Y(B(S(C!I))(¢B(C(¢B)+)-))(-2))+ B(Y(B(S(C!I))(¢B(C(¢B)+)-))(-2))+ 3 / sum 2 3 5 Incidentally, using the terms "successor" and "predecessor" as opposed to "increment" and "decrement" stems from having a _denotational_ rather than _operational_ view of a function. In other words, a function is seen as denoting the mapping between the sets that comprise its domain and range, rather than as a prescription for the operation that converts one into the other. To take a specific example: Min's '+' doesn't increment its argument; it leaves it alone and denotes its successor as result. Given this view, words from the subset of nouns that can be used as determiners (first of, reverse of, ···), seem more appropriate than transitive verbs as names for functions. For example: sum, difference, product and quotient appear preferable to: add, subtract, multiply and divide. (muse: choosing symbol '@' (pronounced "at") for explicit function application reinforces the denotational view: f@n = "the value of function f at n". ) ¯¯ Playing with Combinators ------------------------ We can experiment with Min's primitive combinators I K S B C $ ¢ & Y by tracing the reduction of combinator strings. Remember: Ix = x / Identity Kcx = c / Cancellator Sfgx = fx(gx) / Distributor Bfgx = f(gx) / Compositor Cfgx = fxg / Permutator $cfgx = c(fx)(gx) / S' ¢cfgx = c(fx)g / C' &cfgx = c(f(gx)) / B* Yx = x(Yx) / Fixpoint min'' BICKY 2; / Trace reduction of arbitrary combinator string. BICKY2 ¯¯¯¯ I(CK)Y2 ¯¯¯¯¯ CKY2 ¯¯¯¯ K2Y ¯¯¯ 2 ISSY BICK; / Some expressions reduce to an irreducible expression. ISSYBICK ¯¯ SSYBICK ¯¯¯¯ SB(YB)ICK ¯¯¯¯¯¯¯ BI(YBI)CK ¯¯¯¯¯¯¯¯ I(YBIC)K ¯¯¯¯¯¯¯ YBICK ¯¯ B(YB)ICK ¯¯¯¯¯¯¯ YB(IC)K ¯¯ B(YB)(IC)K ¯¯¯¯¯¯¯¯¯¯ YB(ICK) ¯¯ B(YB)(ICK) ← too few args for B: reduction suspends. KISSY KISSY; / Some reductions may not terminate. KISSYKISSY ¯¯¯ ISYKISSY ¯¯ SYKISSY ¯¯¯¯ YI(KI)SSY ← [1] ¯¯ I(YI)(KI)SSY ← [2] ¯¯¯¯¯ YI(KI)SSY ← same as [1] ¯¯ I(YI)(KI)SSY ← same as [2] ¯¯¯¯¯ YI(KI)SSY ← same as [1] ¯¯ I(YI)(KI)SSY ← same as [2] ¯¯¯¯¯ ... ← ... interrupt SII(SII); SII(SII) ← [1] fun = SII, arg = SII ¯¯¯¯¯¯¯¯ I(SII)(I(SII)) ¯¯¯¯¯¯ SII(I(SII)) ← [2] as [1] but with: arg' = I arg ¯¯¯¯¯¯¯¯¯¯¯ I(I(SII))(I(I(SII))) ¯¯¯¯¯¯¯¯¯ I(SII)(I(I(SII))) ¯¯¯¯¯¯ SII(I(I(SII))) ← [3] as [2] but with: arg' = I arg ¯¯¯¯¯¯¯¯¯¯¯¯¯¯ I(I(I(SII)))(I(I(I(SII)))) ¯¯¯¯¯¯¯¯¯¯¯¯ I(I(SII))(I(I(I(SII)))) ¯¯¯¯¯¯¯¯¯ I(SII)(I(I(I(SII)))) ¯¯¯¯¯¯ SII(I(I(I(SII)))) ← [4] as [3] but with: arg' = I arg ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ I(I(I(I(SII))))(I(I(I(I(SII))))) ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ I(I(I(SII)))(I(I(I(I(SII))))) ¯¯¯¯¯¯¯¯¯¯¯¯ I(I(SII))(I(I(I(I(SII))))) ¯¯¯¯¯¯¯¯¯ I(SII)(I(I(I(I(SII))))) ¯¯¯¯¯¯ SII(I(I(I(I(SII))))) ← as above with: arg' = I arg ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ... ← ... interrupt ) Unbound names ------------- Unbound (undefined) names are parsed as infinite-arity functions (they expect an unlimited number of arguments). Primitive combinators consume such functions in the normal way but an unbound name at the left of an expression binds (curries) with everything to its right, completing the reduction. min'' z / unbound z z Ix / I: Identity x Kcx / K: Cancellator c Sfgx / S: Distributor fx(gx) Bfgx / B: f-atop-(monadic)g / Compositor f(gx) BBB fgxy; / BBB: f-atop-(dyadic)g - trace BBBfgxy ¯¯¯¯ B(Bf)gxy ¯¯¯¯¯¯¯ Bf(gx)y ¯¯¯¯¯¯¯ f(gxy) $ gfhx / S': monadic fork: (f g h)⍵ → (f ⍵)g(h ⍵) g(fx)(hx) B$$ gfhxy; / B S'S': dyadic fork: ⍺(f g h)⍵ → (⍺ f ⍵)g(⍺ h ⍵) (trace) B$$gfhxy ¯¯¯¯ $($g)fhxy ¯¯¯¯¯¯¯¯ $g(fx)(hx)y ¯¯¯¯¯¯¯¯¯¯¯ g(fxy)(hxy) hello world / too few arguments for function h helloworld BBCradio2; / partial reduction BBCradio2 ¯¯¯¯ B(Cr)adio2 ¯¯¯¯¯¯¯ Cr(ad)io2 ¯¯¯¯¯¯¯ ri(ad)o2 r abcd = dcba / reversal of arguments r efgh; ¢(¢C)(¢C(CI))efgh ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¢C(¢C(CI)f)egh ¯¯¯¯¯¯¯¯¯¯¯¯¯ C(¢C(CI)fg)eh ¯¯¯¯¯¯¯¯¯¯¯¯¯ ¢C(CI)fghe ¯¯¯¯¯¯¯¯ C(CIg)fhe ¯¯¯¯¯¯¯¯ CIghfe ¯¯¯¯ Ihgfe ¯¯ hgfe ) Max, Min's strongly-typed sibling, allows only functions of finite type - in Max an unbound name is an error, so the above examples will not work. Min Coding Example ------------------ In 1928, W.Ackermann published a function that generalises the sequence: enumeration → sum → product → exponent → ··· For example: ack 0 2 3 → 5 ⍝ 2+3 ack 1 2 3 → 6 ⍝ 2×3 ack 2 2 3 → 8 ⍝ 2*3 ack 3 ··· ··· In APL, we might code this as an operator like this: ack←{ ⍺⍺=0:⍺+⍵ ⍝ sum, ⍺⍺=1:⍺×⍵ ⍝ product, (⍺⍺-1)∇∇/⍵/⍺ ⍝ ... and beyond. } then: 2(0 ack)3 ⍝ 2+3 5 2(1 ack)3 ⍝ 2×3 6 2(2 ack)3 ⍝ 2*3 8 2(3 ack)3 ⍝ ... 16 2(4 ack)3 ⍝ ... 65536 ··· and: sum ← 0 ack ⍝ 2 sum 3 → 5 prod ← 1 ack ⍝ 2 prod 3 → 6 exp ← 2 ack ⍝ 2 exp 3 → 8 ··· In Min, this function becomes: a 0 m 0 = m / sum a 0 m (+n) = +(a 0 m n) a 1 m 0 = 0 / product a 1 m (+n) = a 0 m (a 1 m n ) a (+(+k)) m 0 = 1 / exponent and beyond ··· a (+(+k)) m (+n) = a (+k) m (a (+(+k)) m n) Then, using partial application (currying): s = a 0 / sum p = a 1 / product e = a 2 / exponent ··· More usually associated with Ackermann, is a simpler function which, in common with the previous example, is computable but not primitive-recursive: a 0 n = +n / Ackermann's function. a (+m) 0 = a m 1 a (+m) (+n) = a m (a (+m) n) a 3 3 / (takes a while) 61 It is clear that this function terminates for _any_ (natural number) values of m and n, as m's _predecessor_ is used for each recursive call, resulting in the inevitable selection of the first equation and termination. A similar condition holds for the second argument in the third equation, where n's predecessor is used. However, it is not possible to state even the order O(···) of the number of red- uction steps required in terms of m and n, using elementary functions such as exponentiation. For example, evaluation of (a 3 3) takes 2,432 reduction steps, starting: a 3 3 ¯¯¯¯¯ → a 2 (a 3 2) ¯¯¯¯¯ → a 2 (a 2 (a 3 1)) ¯¯¯¯¯ → a 2 (a 2 (a 2 (a 3 0))) ¯¯¯¯¯ → a 2 (a 2 (a 2 (a 2 1))) ¯¯¯¯¯ → a 2 (a 2 (a 2 (a 1 (a 2 0)))) ¯¯¯¯¯ → a 2 (a 2 (a 2 (a 1 (a 1 1)))) ¯¯¯¯¯ → a 2 (a 2 (a 2 (a 1 (a 0 (a 1 0))))) ¯¯¯¯¯ → a 2 (a 2 (a 2 (a 1 (a 0 (a 0 1))))) ¯¯¯¯¯ → a 2 (a 2 (a 2 (a 1 (a 0 2)))) ¯¯¯¯¯ → a 2 (a 2 (a 2 (a 1 3))) ¯¯¯¯¯ ··· A table of the first few values of Ackermann's function shows how they increase very rapidly: n=0 n=1 n=2 n=3 a m ⍵ ≡≡ (APL) ─┼─────┼─────┼─────┼─────┼── ───── ───── m=0 │ 1│ 2│ 3│ 4│ ··· a 0 ⍵ ≡≡ ⍵+1 ─┼─────┼─────┼─────┼─────┼── m=1 │ 2│ 3│ 4│ 5│ ··· a 1 ⍵ ≡≡ ⍵+2 ─┼─────┼─────┼─────┼─────┼── m=2 │ 3│ 5│ 7│ 9│ ··· a 2 ⍵ ≡≡ ¯3++/(⍵+3)⍴2 ─┼─────┼─────┼─────┼─────┼── ¯ m=3 │ 5│ 13│ 29│ 61│ ··· a 3 ⍵ ≡≡ ¯3+×/(⍵+3)⍴2 ─┼─────┼─────┼─────┼─────┼── ¯ m=4 │ 13│65533│ *│ ···│ ··· a 4 ⍵ ≡≡ ¯3+*/(⍵+3)⍴2 ─┼─────┼─────┼────│┼─────┼── ¯ │ └─ (a 4 2) is the following large number: 20035299304068464649790723515602557504478254755697514192650169737108940595563114 53089506130880933348101038234342907263181822949382118812668869506364761547029165 04187191635158796634721944293092798208430910485599057015931895963952486337236720 30029169695921561087649488892540908059114570376752085002066715637023661263597471 44807111774815880914135742720967190151836282560618091458852699826141425030123391 10827360384376787644904320596037912449090570756031403507616256247603186379312648 47037437829549756137709816046144133086921181024859591523801953310302921628001605 68670105651646750568038741529463842244845292537361442533614373729088303794601274 72495841486491593064725201515569392262818069165079638106413227530726714399815850 88112926289011342377827055674210800700652839633221550778312142885516755540733451 07213112427399562982719769150054883905223804357045848197956393157853510018992000 02414196370681355984046403947219401606951769015611972698233789001764151719005113 34663068981402193834814354263873065395529696913880241581618595611006403621197961 01859534802787167200122604642492385111393400464351623867567078745259464670903886 54774348321789701276445552940909202195958575162297333357615955239488529757995402 84719435299135437637059869289137571537400019863943324648900525431066296691652434 19174691389632476560289415199775477703138064781342309596190960654591300890188887 58808473362595606544488850144733570605881709016210849971452956834406197969056546 98136311620535793697914032363284962330464210661362002201757878518574091620504897 11781820400187282939943446186224328009837323764931814789848119452713007440220765 68091037620399920349202390662626449190916798546151577883906039772075927937885224 12943010174580868622633692847258514030396155585643303854506886522131148136384083 84778263790459607186876728509763471271988890680478243230394718650525660978150729 86114143030581692792497140916105941718535227588750447759221830115878070197553572 22414000195481020056617735897814995323252085897534635470077866904064290167638081 61740550405117670093673202804549339027992491867306539931640720492238474815280619 16690093380573212081635070763435166986962502096902316285935007187419057916124153 68975148082619048479465717366010058924766554458408383347905441448176842553272073 15586349347605137419779525190365032198020108764738368682531025183377533908861426 18480037400808223810407646887847164755294532694766170042446106331123802113458869 45322001165640763270230742924260515828110703870183453245676356259514300320374327 40780879056283663406965030844225855967039271869461158513793386475699748568670079 82396060439347885086164926030494506174341236582835214480672667684180708375486221 14082365798029612000274413244384324023312574035450193524287764308802328508558860 89962774458164680857875115807014743763867976955049991643998284357290415378143438 84730348426190338884149403136613985425763557710533558020662218557706008255128889 33322264362819848386132395706761914096385338323743437588308592337222846442879962 45605476932428998432652677378373173288063210753211238680604674708428051166488709 08477029120816110491255559832236624486855665140268464120969498259056551921618810 43412268389962830716548685255369148502995396755039549383718534059000961874894739 92880432496373165753803673586710175783994818471798498246948060532081996066183434 01247609663951977802144119975254670408060849934417825628509272652370989865153946 21930046073645079262129759176982938923670151709920915315678144397912484757062378 04600009918293321306880570046591458387208088016887445835557926258465124763087148 56631352893416611749061752667149267217612833084527393646924458289257138887783905 63004824837998396920292222154861459023734782226825216399574408017271441461795592 26175083889020074169926238300282286249284182671243405751424188569994272331606998 71298688277182061721445314257494401506613946316919762918150657974552623619122484 80638900336690743659892263495641146655030629659601997206362026035219177767406687 77463549375318899587866282125469797102065747232721372918144666659421872003474508 94283091153518927111428710837615922238027660532782335166155514936937577846667014 57179719012271178127804502400263847587883393968179629506907988171216906869295382 48529830023476068454114178139110648560236549754227497231007615131870024053910510 91381784372179142252858743209852495787803468370333781842144401713868812424998441 86181292711985333153825673218704215306311977485352146709553346263366108646673322 92409879849256691109516143618601548909740241913509623043612196128165950518666022 03071561368473236466086890501426391390651506390819937885231836505989729912540447 94434251667742996598118492331515552728832740283526884424087528112832899806259126 73699546247341543333500147231430612750390307397135252069338173843322950701049061 86753943313078479801565513038475815568523621801041965025559618193498631591323303 60964619059902361126811960234418433633345949276319461017166529138237171823942992 16272538461776065694542297877071383198817036964588689811863210976900355735884624 46483570629145305275710127887202796536447972402540544813274839179412882642383517 19491972097971459368875371987291308317380339110161285474153773777159517280841116 27597186384924222802373441925469991983672192131287035585307966942713416391033882 75431861364349010094319740904733101447629986172542442335561223743571582593338280 49862438924982227807159517627578471094751190334822414120251826887137281931042534 78196128440176479531505057110722974314569915223451643121848657575786528197564843 50895838472292353455946452121583165775147129870822590929265563883665112068194383 69041162526687100445602437042006637090019411855571604720446436969328500600469281 40507119069261393993902735534545567470314903886022024639948260501762431969305640 66636662609020704888743889890749815286544438186291738290105182086993638266186830 39152732645812867828066013375000965933646251460917231803129303478774212346791184 54791311109897794648216922505629399956793483801699157439700537542134485874586856 04728675106542334189383909911058646559511364606105515683854121745980180713316361 25730796111683438637676673073545834947897883163301292408008363568259391571131309 78030516441716682518346573675934198084958947940983292500086389778563494693212473 42610306271374507728615692259662857385790553324064184901845132828463270926975383 08673084091422476594744399733481308109863994173797896570106870267341619671965915 99588537834822988270125605842365589539690306474965584147981310997157542043256395 77607048510088157829140825077773855979012912940730946278594450585941227319481275 32251523248015034665190482289614066468903051025109162377704484862302294889667113 80555607956620732449373374027836767300203011615227008921843515652121379215748206 85935692079021450227713309998772945959695281704458218195608096581170279806266989 12050615607423256868422713062950098644218534708104071289176469065508361299166947 78023822502789667843489199409657361704586786242554006942516693979292624714524945 40885842272615375526007190433632919637577750217600519580069384763578958687848953 68721228985578068265181927036320994801558744555751753127364714212955364940843855 86615208012115079075068553344489258693283859653013272046970694571546959353658571 78889486233329246520273585318853337094845540333656535698817258252891805663548836 37437933484118455801683318276768346462919956055134700391478768086403226296166415 60667508153710646723108461964247537490553744805318226002710216400980584497526023 03564003808347205314994117296573678506642140084269649710324191918212121320693976 91439233683747092282677387081322366800869247034915868409911530983154120635661231 87504305467536983230827966457417620806593177265685841681837966106144963432544111 70694170022265781735835125982108076910196105222926387974504901925431190062056190 65774524161919131875339840493439768233102984658933183730158095925228292068208622 30332585280119266496314441316442773003237792274712330696417149945532261035475145 63129066885434542686978844774298177749371011761465162418361668025481529633530849 08499430067636548061029400946937506098455885580439704859144495844450799784970455 83550685408745163316464118083123079704389849190506587586425810738422420591191941 67418249045270028826398305795005734171148703118714283418449915345670291528010448 51451760553069714417613685823841027876593246626899784183196203122624211773914772 08004883578333569204533935953254564897028558589735505751235129536540502842081022 78524877660357424636667314868027948605244578267362623085297826505711462484659591 42102781227889414481639949738818846227682448516220518170767221698632657016543169 19742651230041757329904473537672536845792754365412826553581858046840069367718605 02007054724754840080553042495185449526724726134731817474218007857469346544713603 69758841180294080396167469462885406791721386012254195038197045384172680063988206 56328792839582708510919958839448297775647152026132871089526163417707151642899487 95356485455355314875497813400996485449863582484769059003311696130376612792346432 31297066284113074270462020320133683503854253603136367635752126047074253112092334 02837482949453104727418969287275572027615272268283376741393425652653283068469997 59709775000556088993268502504921288406827413988163154045649035077587168007405568 57240217586854390532281337707074158307562696283169556874240605277264858530506113 56384851965918968649596335568216975437621430778665934730450164822432964891270709 89807667662567151726906205881554966638257382927418208227896068448822298339481667 09840390242835143068137672534601260072692629694686727507943461904399966189796119 28750519442356402644303271737341591281496056168353988188569484045342311424613559 92527233006488162746672352375123431189344211888508507935816384899448754475633168 92138696755743027379537852625423290248810471819390372206668947022042588368958409 39998453560948869946833852579675161882159410981624918741813364726965123980677561 94791255795744647142786862405375057610420426714936608498023827468057598259133100 69199419046519065311719089260779491192179464073551296338645230356733455880333131 97080365457184791550432654899559705862888286866606618021882248602144999973122164 13817065348017551043840662441282280361664890425737764095632648282525840766904560 84394903252905263375323165090876813366142423983095308065496618793819491200339194 89494065132398816642080088395554942237096734840072642705701165089075196155370186 26479745638118785617545711340047381076276301495330973517418065547911266093803431 13785325328835333520249343659791293412848549709468263290758301930726653377825593 14331110963848053940859283988907796210479847919686876539987477095912788727475874 43980677982496827827220092644994455938041460877064194181044075826980568803894965 46165879839046605876453418102899071942930217745199761044950431968415034555140448 20928933378657363052830619990077748726922998608279053171691876578860908941817057 99340489021844155979109267686279659758395248392673488363474565168701616624064242 42412289611180106156823425393921800524834547237792199112285959141918774917938233 40010078128326506710281781396029120914720100947878752551263372884222353869490067 92766451163475810119387531965724212147603828477477457170457861041738574791130190 85838778901523343430130052827970385803598151829296003056826120919509437373254541 71056383887047528950563961029843641360935641632589408137981511693338619797339821 67076100460798009601602482309694304380695662012321365014054958625061528258803302 29083858124784693157203232336018994694376477267218793768264318283826035645206994 68630216048874528424363593558622333506235945002890558581611275341783750455936126 13085264082805121387317749020024955273873458595640516083058305377073253397155262 04447054295735383611136775231699727402929416742044232481138750756313190782721888 64053374694213842169928862940479635305150560788126366206497231257579019598873041 19562622734372890051656111109411174527796548279047125058199907749806382155937688 55464988229389854082913251290764783863224947810167534916934892881042030156102833 86143827378160946341335383578340765314321417150655877547820252454780657301342277 47061674424196895261316427410469547462148375628829977180418678508454696561915090 86958742511844358373065909514609804512474094113738999278224929833677960110153870 96129749705566301637307202750734759922943792393824427421186158236161317886392553 09511718842129850830723825972914414225157940388301135908333165185823496722125962 18125070581137594955250227472746743698871319266707692991990844671612287388584575 84622726573330753735572823951616964175198675012681745429323738294143824814377139 86190671665757294580780482055951188168718807521297183263644215533678775127476694 07901170575098195750845635652173895441798750745238544552001335720333323798950743 93905312918212255259833790909463630202185353848854825062897715616963860712382771 72562131346054940177041358173193176337013633225281912754719144345092071184883836 68181742633429496118700915030491653394647637177664391207983474946273978221715020 90670190302469762151278521956142070806461631373236517853976292092025500288962012 97014137964003805573494926907353514596120867479654773369295877362863566014376796 40384307968641385634478013282612845891848985280480488441808216394239740143629034 81665458114454366460032490618763039502356402044530748210241366895196644221339200 75747912868380517515063466256939193774028351207566626082989049187728783385217852 27920457718469658552787904475621926639920084093020756739253637356283908298175779 02153202106409617373283598494066652141198183810884515459772895164572131897797907 49194101314836854463961690460703010759681893374121757598816512700076126278916951 04063158576375347874200702220510708912576123616580268068158584998526314658780866 16800733264676830206391697203064894405628195406190685242003053463156621891327309 06968735318164109451428803660599522024824888671155442910472192913424834643870536 85086487490991788126705656653871910497218200423714927401644609434598453925367061 32210616533085662021188968234005752675486101476993688738209584552211571923479686 88816085363161586288015039594941852948922707441082820716930338781808493620401825 52222710109856534448172074707560192459155994310729495781978785905789400525401228 67517142511184356437184053563024181225473266093302710397968091064939272722683035 41046763259135527968383770501985523462122285841055711992173171796980433931770775 07556270560478317798444476375602546370333692471142208155199736913719751632413027 48712199863404548248524570118553342675264715978310731245663429805221455494156252 72402891533335434934121786203700726031527987077187249123449447714790952073476138 54254853115527733010303424768358654960937223240071545181297326920810584240905577 25645803681462234493189708138897143299831347617799679712453782310703739151473878 69211918756670031932128189680332269659445928621060743882741691946516226763254066 50708810710303941788605648937698167341590259251946118236429456526693722031555047 00213598846292758012527715422016629954863130324912311029627923723899766416803497 14122652793190763632613681414551637665655983978848938173308266877990196288693229 65973799519316211872154552873941702436698855938887933167445333631195415184040882 83815193421234122820030950313341050704760159987985472529190665222479319715440331 79483683737322082188577334162385644138070054191353024594391350255453188645479625 22602517629283743304651023610575835145507394433396102162296754614157811271970017 38611494279501411253280621254775810512972088465263158094806633687670147310733540 71771087661593585681409821296773075919738297344144525668877085532457088895832099 38234321027182241147637327913575686154212528496579033350931527769255058456440105 52192644505312073756287744998163646332835816140330175813967359427327690448920361 88038675495575180689005853292720149392350052584514670698262854825788326739873522 04572282392902071448222198855871028969919358730742778151597576207640239512438602 02032596596250212578349957710085626386118233813318509014686577064010676278617583 77277289589274603940393033727187385053691295712671506689668849388088514294360996 20129667590792250822753138128498515269029317002631363289420957975779593276355311 62066753488651317323872438748063513314512644889967589828812925480076425186586490 24111112730135719718138160258317850693224400799865663537154408845486639318170839 57357807990597308390948818040609359591909074739609044101505163217496814121007657 19177483767355751000733616922386537429079457803200042337452807566153042929014495 78062963413838355178359976470885134900485697369796523869584599459559209070905895 68914511414126845054621179450266117501669282602509507707782119504326173832235624 37601776799362796099368975191394965033358507155418436456852616674243688920371037 49532842592713161053783498074073915863381796765842525803673720646935124865223848 13416638080615057048290598906964519364400185971204257230073164100099169875242603 77362177763430621616744884930810929901009517974541564251204822086714586849255132 44426677712786372821133153622430109182439124338021404624222334915355951689081628 84879899882736304453724321742802157557779670216663170479697281724833928410156422 74507271779269399929740308072770395013581545142494049026536105825409373114653104 94338248437971860693721444460082679800247122948940576185389220342560830269705287 66213773735943942241147070740729027254613073585417456914194464876243576823970657 03184168467540733466346293673983620004041400714054277632480132742202685393698869 78760700959004868465062677136307097982100655728510130660101078063374334477307347 86538817426812307437660666433127753564665786037151929227684404582732832438082128 41218776132042460464900801054731426749260826922155637405486241717031027919996942 64562095561981645454766204502241144940474934983220680719135276798674781345820385 95704134661779372285349400316315995440936840895725334387029867178297703733328068 01764639502090023941931499115009105276821119510999063166150311585582835582607179 41005252858361136996130344279017381178741206128818206202326384986151565645123004 77929675636183457681050433417695430675380411139285537925292413473394810505320257 08728186307291158911335942014761872664291564036371927602306283840650425441742335 46454998705531872688792642410214736369862546374715974435494344389973005174252511 08773578863909468120966734281525859199248576404880550713298142993599114632399191 13959926752576359007446572810191805841807342227734721397723218231771716916400108 82611254909336118678057572239101818616854910850088527227437421208652485237245624 86976622453848192986711294529455154970305859193071984971054141816369689761311267 44027009648667545934567059936995464500558921628047976365686133316563907395703272 03438917541526750091501119885687270884819553167693168127289214303137681801644547 73675183534978579242764633541624336011259602521095016122641103460834656482355979 34274056868849224458745493776752120324703803035491157544831295275891939893680876 32768543876955769488142284431199859570072752139317683783177033913042306095899913 73146845690104220951619670705064202567338734461156552761759927271518776600102389 44760539789516945708802728736225121076224091810066700883474737605156285533943565 84375627124124445765166306408593950794755092046393224520253546363444479175566172 59621871992791865754908578529500128402290350615149373101070094461510116137124237 61426722541732055959202782129325725947146417224977321316381845326555279604270541 87149623658525245864893325414506264233788565146467060429856478196846159366328895 42997807225422647904006160197519750074605451500602918066382714970161109879513366 33771378434416194053121445291855180136575558667615019373029691932076120009255065 08158327550849934076879725236998702356793102680413674571895664143185267905471716 99629903630155456450900448027890557019683283136307189976991531666792089587685722 90600915472919636381673596673959975710326015571920237348580521128117458610065152 59888384311451189488055212914577569914657753004138471712457796504817585639507289 5337539755822087777506072339445587895905719156733 ( This number (¯3+*/5/2) is too big to represent in IEEE 64-bit floating point format, so it generates a DOMAIN ERROR in Dyalog APL. We can check the numb- er using the "nats" operator from the dfns workspace: )copy dfns nats saved ... (↑*nats/5/2)-nats 3 ⍝ See: dfns.dws/notes.nats ) Buck (1963) defines a function, using essentially the same recurrence relation but returning "cleaner" results at the expense of slightly more complex boundary conditions: b 0 0 = 1 / Buck's function b 0 (+n) = +(+n) / b 0 ⍵ → 1+⍵ b 1 0 = 2 b 1 (+n) = +(+(+n)) / b 1 ⍵ → 2+⍵ b 2 0 = 0 b 2 (+n) = +(+(b 2 n)) / b 2 ⍵ → 2×⍵ b (+(+(+m))) 0 = 1 b (+(+(+m))) (+n) = b (+(+m)) (b (+(+(+m))) n) ... with the following table: n=0 n=1 n=2 n=3 n=4 ··· b m ⍵ ≡≡ APL ≡≡ APL ──┼─────┼─────┼─────┼─────┼─────┼── ───── ─── ─── m=0 │ 1│ 2│ 3│ 4│ 5│ ··· b 0 ⍵ ≡≡ 1+⍵ ───┼─────┼─────┼─────┼─────┼─────┼── m=1 │ 2│ 3│ 4│ 5│ 6│ ··· b 1 ⍵ ≡≡ 2+⍵ ───┼─────┼─────┼─────┼─────┼─────┼── ¯ m=2 │ 0│ 2│ 4│ 6│ 8│ ··· b 2 ⍵ ≡≡ 2×⍵ ≡≡ +/⍵/2 ───┼─────┼─────┼─────┼─────┼─────┼── ¯ ¯ m=3 │ 1│ 2│ 4│ 8│ 16│ ··· b 3 ⍵ ≡≡ 2*⍵ ≡≡ ×/⍵/2 ───┼─────┼─────┼─────┼─────┼─────┼── ¯ ¯ m=4 │ 1│ 2│ 4│ 16│65536│ ··· b 4 ⍵ ≡≡ */⍵/2 ───┼─────┼─────┼─────┼─────┼─────┼── ¯ │ ···│ ···│ ···│ ···│ ···│ ··· Apart from the first three columns, Buck's function may be derived directly from Ackermann's function in Min by: b m (+(+(+n))) = +(+(+(a m n))) / undefined for n∊0 1 2 Notice the correspondence between (b 4 ⍵) and compositions of the simple "twice" function: t f x = f(f x) + 0 ≡≡ b 4 0 ≡≡ 1 t + 0 ≡≡ b 4 1 ≡≡ 2 t t + 0 ≡≡ b 4 2 ≡≡ 4 t t t + 0 ≡≡ b 4 3 ≡≡ 16 t t t t + 0 ≡≡ b 4 4 ≡≡ 65536 ··· ·· t ... t + 0 ≡≡ b 4 ⍵ └──⍵──┘ ( We APLers, accustomed to right-to-left evaluation, are sometimes perplexed by the rapidity of the growth of the result of repeated applications of function t. If we introduce T as a new primitive combinator in function "combo": combo←{ ·· tab:·· ·· ⍵,⊂' Tfx ' ' f(fx) '}{ ⍝ T Twice ·· } we avoid compilation into lower-level combinators and so can observe its re- duction directly: min'' TTT+0; / trace reduction TTT+0 ¯¯¯ T(TT)+0 ¯¯¯¯¯¯ TT(TT+)0 ¯¯¯¯¯¯¯ T(T(TT+))0 ¯¯¯¯¯¯¯¯¯¯ T(TT+)(T(TT+)0) ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ TT+(TT+(T(TT+)0)) ¯¯¯ T(T+)(TT+(T(TT+)0)) ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ T+(T+(TT+(T(TT+)0))) ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ +(+(T+(TT+(T(TT+)0)))) ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ +(+(+(+(TT+(T(TT+)0))))) ¯¯¯ +(+(+(+(T(T+)(T(TT+)0))))) ¯¯¯¯¯¯¯¯¯¯¯¯¯¯ +(+(+(+(T+(T+(T(TT+)0)))))) ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ +(+(+(+(+(+(T+(T(TT+)0))))))) ¯¯¯¯¯¯¯¯¯¯¯ +(+(+(+(+(+(+(+(T(TT+)0)))))))) ¯¯¯¯¯¯¯ +(+(+(+(+(+(+(+(TT+(TT+0))))))))) ¯¯¯ +(+(+(+(+(+(+(+(T(T+)(TT+0))))))))) ¯¯¯¯¯¯¯¯¯¯¯ +(+(+(+(+(+(+(+(T+(T+(TT+0)))))))))) ¯¯¯¯¯¯¯¯¯¯¯¯ +(+(+(+(+(+(+(+(+(+(T+(TT+0))))))))))) ¯¯¯¯¯¯¯¯ +(+(+(+(+(+(+(+(+(+(+(+(TT+0)))))))))))) ¯¯¯ +(+(+(+(+(+(+(+(+(+(+(+(T(T+)0)))))))))))) ¯¯¯¯¯¯ +(+(+(+(+(+(+(+(+(+(+(+(T+(T+0))))))))))))) ¯¯¯¯¯¯¯ +(+(+(+(+(+(+(+(+(+(+(+(+(+(T+0)))))))))))))) ¯¯¯ +(+(+(+(+(+(+(+(+(+(+(+(+(+(+(+0))))))))))))))) ¯¯ +(+(+(+(+(+(+(+(+(+(+(+(+(+(+1)))))))))))))) ¯¯ +(+(+(+(+(+(+(+(+(+(+(+(+(+2))))))))))))) ¯¯ +(+(+(+(+(+(+(+(+(+(+(+(+3)))))))))))) ¯¯ +(+(+(+(+(+(+(+(+(+(+(+4))))))))))) ¯¯ +(+(+(+(+(+(+(+(+(+(+5)))))))))) ¯¯ +(+(+(+(+(+(+(+(+(+6))))))))) ¯¯ +(+(+(+(+(+(+(+(+7)))))))) ¯¯ +(+(+(+(+(+(+(+8))))))) ¯¯ +(+(+(+(+(+(+9)))))) ¯¯ +(+(+(+(+(+10))))) ¯¯¯ +(+(+(+(+11)))) ¯¯¯ +(+(+(+12))) ¯¯¯ +(+(+13)) ¯¯¯ +(+14) ¯¯¯ +15 ¯¯¯ 16 As a spectacle, you might like to try this for TTTT+0; ) The first published non-primitive-recursive function was discovered by Romanian mathematician Gabriel Sudan in 1927. sudan←{ x y←⍵ ⍺=0:x+y y=0:x (⍺-1)∇(0 1×⍵)+⍺ ∇ ⍵-0 1 } 1 sudan¨⍳10 10 0 1 4 11 26 57 120 247 502 1013 1 3 8 19 42 89 184 375 758 1525 2 5 12 27 58 121 248 503 1014 2037 3 7 16 35 74 153 312 631 1270 2549 4 9 20 43 90 185 376 759 1526 3061 5 11 24 51 106 217 440 887 1782 3573 6 13 28 59 122 249 504 1015 2038 4085 7 15 32 67 138 281 568 1143 2294 4597 8 17 36 75 154 313 632 1271 2550 5109 9 19 40 83 170 345 696 1399 2806 5621 2 sudan¨⍳4 3 0 1 19 1 8 10228 2 27 1.556925642E10 3 74 5.742397643E24 See: http://en.wikipedia.org/wiki/Gabriel_Sudan Another Example --------------- The sequence sum, product, exponent is coded in the example script like so: s i 0 = i / Sum: is defined recursively s i j ≡≡ i+j s i (+j) = +(s i j) / in terms of successor and sum. p i 0 = 0 / Product: is defined recursively p i j ≡≡ i×j p i (+j) = s (p i j) i / in terms of sum and product. e i 0 = 1 / Exponent is defined recursively e i j ≡≡ i*j e i (+j) = p (e i j) i / in terms of product and exponent. This progression may be abstracted into a single high level function, often called "foldn", which generalises structural recursion over the natural numbers: f h c 0 = c / foldn 0: constant. f h c (+i) = h (f h c i) / +i: function of i. then: s i = f + i / sum p i = f (s i) 0 / product e i = f (p i) 1 / exponent s 2 3 / sum 5 p 2 3 / product 6 e 2 3 / exponent 8 If we introduce combinators B and C: b f g h = f (g h) / compositor B c f g h = f h g / permutator C we can express sum, product and exponent directly as applicative expressions: s = f + / sum p = c (b f s) 0 / product e = c (b f p) 1 / exponent (muse: it seems puzzling (to JMS), given the uniform nature of the above defin- itions, that sum and product are both commutative and associative, while power is neither commutative nor associative.) Even Ackermann's function, which is normally written as three equations: a 0 n = +n / Ackermann's function. a (+m) 0 = a m 1 a (+m) (+n) = a m (a (+m) n) may be coded directly in this style: a = f (c (f p q)) + / Ackermann's function where: p x y = y (x y) q x = x 1 again, if we introduce combinators: i x = x / identificator I s f g x = f x (g x) / distributor S we can replace equations p and q above to express Ackermann's function as an applicative expression. That is, if: p = s i q = c i 1 then: a = f(c(f(s i)(c i 1)))+ / Ackermann's function f(c(f(s i)(c i 1)))+ 2 2 / Ack 2 2 7 Sadly, with this implementation of Min, the above functions are rather slow. ( Notice that foldn is closely related to primitive power operator ⍣. The following expressions are equivalent: f h c n / Min. (h⍣n)c ⍝ Dyalog. ) More abstraction ---------------- Standard definitions of Boolean functions "and" and "or" are: a x 0 = 0 / and a x 1 = x o x 0 = x / or o x 1 = 1 an alternative might be to define a higher level conditional function: c t f 1 = t / condition c t f 0 = f together with three auxiliary functions: i x = x / identity t x = 1 / true f x = 0 / false then we can redefine "and" and "or" as: a = c i f / and o = c t i / or Order of arguments and performance ---------------------------------- The performance of a Min function may be very sensitive to the order of its arg- uments: given the following definition of sum: s i 0 = i s i (+j) = +(s i j) then (s 9 1) would be reduced to 10 in two steps, while (s 1 9) would take ten. However, if we redefine sum: t 0 j = j t (+i) j = +(t i j) then (t 9 1) is "slow" and (t 1 9), "fast". To capture this concept, we can imagine a high level function R, which returns the number of reduction steps required to reduce its argument expression. Then R s 9 1 = 2 R s 1 9 = 10 R t 9 1 = 10 R t 1 9 = 2 Here are lambda expression trees for s and t: s i 0 = i t 0 j = j s i (+j) = +(s i j) t (+i) j = +(t i j) ┌→─────────────────┐ ┌→─────────────────┐ │┌\─┐ │ │ ┌\────┐ │ │i ┌\──┐ │ │ ∆ ┌───@──────┐ │ │ ∆ ┌─@───────┐ │ │ ┌─@─┐ ┌────@─┐ │ │ ┌─@┐ ┌─────@─┐ │ │┌@┐ ┌\┐ ┌\─┐ ┌@┐│ │ ┌@┐ i ┌\─┐ ┌@┐│ │! ∆ j j i ┌\─┐ - ∆│ │ ! ∆ j ┌@──┐ - ∆│ │ j ┌@──┐ │ │ + ┌─@┐ │ │ + ┌─@┐│ │ ┌@┐ j │ │ ┌@┐ j│ │ s i ↓ │ t i ↓ └─────────────────→┘ └─────────────────→┘ Surprisingly, a "tail-recursive" coding of either s or t does not lead to an im- provement in performance. Perhaps this is because the combinator reduction eng- ine is already inherently tail-recursive. s i 0 = i t 0 j = j s i (+j) = s (+i) j t (+i) j = t i (+j) ┌→─────────────────┐ ┌→──────────────────┐ │┌\─┐ │ │ ┌\────┐ │ │i ┌\──┐ │ │ ∆ ┌───@───────┐ │ │ ∆ ┌─@───────┐ │ │ ┌─@─┐ ┌─────@─┐ │ │ ┌─@┐ ┌─────@─┐ │ │┌@┐ ┌\┐ ┌\─┐ ┌@┐│ │ ┌@┐ i ┌\───┐ ┌@┐│ │! ∆ j j i ┌\──┐ - ∆│ │ ! ∆ j ┌──@┐ - ∆│ │ j ┌─@─┐ │ │ ┌@─┐ j │ │ ┌@┐ ┌@┐ │ │ s ┌@┐ │ │ t i + j ↓ │ + i ↓ └──────────────────→┘ └─────────────────→┘ The effect is amplified if we consider product defined in terms of one of the above sum functions. We have eight permutations: p i 0 = 0 / R p 9 9 = 343 / C p 4 4 = 72374 p i (+j) = s i (p i j) ¯¯ ¯ ¯ q i 0 = 0 / R q 9 9 = 100 / C q 4 4 = 866 q i (+j) = s (q i j) i ¯¯ ¯ ¯ x i 0 = 0 / R x 9 9 = 100 / C x 4 4 = 690 x i (+j) = t i (x i j) ¯¯ ¯ ¯ y i 0 = 0 / R y 9 9 = 343 / C y 4 4 = 69134 y i (+j) = t (y i j) i ¯¯ ¯ ¯ a 0 j = 0 / R a 9 9 = 343 / C a 4 4 = 66061 a (+i) j = s j (a i j) ¯¯ ¯ ¯ b 0 j = 0 / R b 9 9 = 100 / C b 4 4 = 837 b (+i) j = s (b i j) j ¯¯ ¯ ¯ c 0 j = 0 / R c 9 9 = 100 / C c 4 4 = 657 c (+i) j = t j (c i j) ¯¯ ¯ ¯ d 0 j = 0 / R d 9 9 = 343 / C d 4 4 = 63537 d (+i) j = t (d i j) j ¯¯ ¯ ¯ The number of permutations is quadrupled if we consider exponent (power), where there are 32 choices. A working rule for optimal performance seems to be to decide which argument to keep small and then to accumulate into the other one. Further, the combinator engine in this particular implementation of Min seems to favour testing the first argument of a function. Function C in the comments above shows the number of _combinator_ applications per case, making product "c" the best buy. Despite this, the marginally slower product "q" was chosen for the examples as this leads to a coding of (non-commutative) exponent in which the arguments are in the conventional order. (muse: JMS finds it astonishing that the evaluation of (p 4 4 → 16) requires as many as 72,374 distinct function applications. If we restrict ourselves to just S and K combinators by removing all optimisation and coding the Y combinator as SSK(S(K(SS(S(SSK))))K), this figure rises to 3,380,823. It is astonishing both that so many unique reductions are produced and also that, having "gone around the loop" three million or so times, it finally terminates. ) Reduction count for e 2 3 ------------------------- The following table shows the reduction counts for 2-to-the-power-3 for each of three codings: 1. Direct symbolic manipulation of the equations. 2. Optimised combinator reduction using I K S B C S' C' B* and Y combinators. 3. Unoptimised combinator reduction using only S and K combinators. The results are in the form of a 2×4×4 array of 3-vectors, whose axes are: Sum: s i 0 = i / sum[0] / The annotation of each definition s i (+j) = +(sij) / indicates whether argument 0 or 1 / is static. s 0 j = j / sum[1] s (+i) j = +(sij) Product: p i 0 = 0 / prod[00] p i (+j) = s i (p i j) p i 0 = 0 / prod[01] p i (+j) = s (p i j) i p 0 j = 0 / prod[10] p (+i) j = s j (p i j) p 0 j = 0 / prod[11] p (+i) j = s (p i j) j Exponent: e i 0 = 1 / exp[00] e i (+j) = p i (e i j) e i 0 = 1 / exp[01] e i (+j) = p (e i j) i e 0 j = 1 / exp[10] / NB: exp[10] and exp[11] e (+i) j = p j (e i j) / reverse the order of args. e 0 j = 1 / exp[11] e (+i) j = p (e i j) j sum[0] exp[00] exp[01] exp[10] exp[11] ┌──────────────┬──────────────┬──────────────┬──────────────┐ prod[00]│ 35│ 35│ 35│ 35│ │ 358,749│ 10,776│ 339,007│ 10,487│ │ 14,361,544│ 436,589│ 12,460,139│ 411,058│ ├──────────────┼──────────────┼──────────────┼──────────────┤ prod[01]│ 26│ 33│ 33│ 26│ │ 5,494│ 23,150│ 5,296│ 22,413│ │ 215,920│ 927,997│ 203,433│ 824,126│ ├──────────────┼──────────────┼──────────────┼──────────────┤ prod[10]│ 26│ 33│ 33│ 26│ │ 9,592│ 343,697│ 9,272│ 325,980│ │ 397,799│ 13,270,907│ 372,268│ 11,369,502│ ├──────────────┼──────────────┼──────────────┼──────────────┤ prod[11]│ 35│ 35│ 35│ 35│ │ 21,588│ 5,441│ 20,780│ 5,264│ │ 892,499│ 209,003│ 788,628│ 196,516│ └──────────────┴──────────────┴──────────────┴──────────────┘ sum[1] exp[00] exp[01] exp[10] exp[11] ┌──────────────┬──────────────┬──────────────┬──────────────┐ prod[00]│ 35│ 35│ 35│ 35│ │ 4,740│ 20,502│ 4,542│ 19,765│ │ 197,563│ 873,367│ 185,076│ 769,496│ ├──────────────┼──────────────┼──────────────┼──────────────┤ prod[01]│ 26│ 33│ 33│ 26│ │ 359,731│ 10,660│ 339,989│ 10,371│ │ 13,867,821│ 415,447│ 11,966,416│ 389,916│ ├──────────────┼──────────────┼──────────────┼──────────────┤ prod[10]│ 26│ 33│ 33│ 26│ │ 18,798│ 4,658│ 17,990│ 4,481│ │ 837,869│ 190,646│ 733,998│ 178,159│ ├──────────────┼──────────────┼──────────────┼──────────────┤ prod[11]│ 35│ 35│ 35│ 35│ │ 9,578│ 347,610│ 9,258│ 329,893│ │ 376,657│ 12,777,184│ 351,126│ 10,875,779│ └──────────────┴──────────────┴──────────────┴──────────────┘ References ---------- An amusing introduction to Combinatory Logic can be found in: - To Mock a Mockingbird, Raymond Smullyan. Oxford University Press (1990) ISBN 0-19-286095-X Original work in this area, much of which pre-dates computers, includes: - Church, A., 1941. The Calculi of Lambda Conversion. Princeton University Press. - Curry, H.B., Feys, R., 1958. Combinatory Logic, North-Holland. - Schönfinkel, M., 1924. Über die Bausteine der mathematischen Logik. Mathematische Annalen, Vol 92, pp.305-316. - Turner, D.A., 1981. Aspects of the Implementation of Programming Languages. PhD thesis University of Oxford. - M. Li and P. M. B. Vitanyi. An Introduction to Kolmogorov Complexity and its Applications. Springer-Verlag, New York, second edition, 1997. Work relating to Ackermann's function includes: - Ackermann, W., 1928. Zum Hilbertschen Aufbau der reellen Zahlen. Mathematische Annalen, Vol 99, pp.119-133. - Buck, R. C., 1963. Mathematical Induction and Recursive Definitions. Amer. Math. Monthly 70, 128-135. - Dötzel, G., 1991. A Function to End All Functions. Algorithm: Recreational Programming 2.4, 16-17. An introduction to the implementation of functional programming languages in- cluding discussion of the lambda calculus and combinator reduction: - The Implementation of Functional Programming Languages, Simon L.Peyton Jones. Prentice Hall (1987) ISBN 0-13-453325-9. - Functional Programming, A.J.Field, P.G.Harrison. Addison Wesley (1988) ISBN 0-201-19249-7. We can refer to Min as a compiler rather than an interpreter if we take combin- ators as machine instructions for a hardware "reduction engine": - Richards, H., 1985. An overview of Burroughs NORMA. Technical report, Austin Research Centre, Burroughs Corp, January 1985. - Scheevel, M., 1986. Norma: a graph reduction processor. In Proceedings of the ACM Conference on Lisp and Functional Programming, Cambridge, Mass., pp. 212- 19. August. - Stoye, W.R., 1985. The Implementation of Functional Languages using Custom Hardware. PhD thesis, Computer Lab., University of Cambridge. Peano's Axioms (Giuseppe Peano 1858-1932) -------------- If N is the set of natural numbers: - 0 ∊ N. // 0 is a natural number. - m ∊ N implies +m ∊ N. // every m has a successor. - There is no m ∊ N for which +m = 0. // 0 has no predecessor. - +m = +n implies m = n. // predecessors are unique. - If M⊂N and 0∊M and (m∊M implies +m∊M), then M≡N. // axiom of induction. ¯ The last axiom provides us with proof by induction. A proposition P(n) about natural number n defines a subset of N for which P is true. If we can prove that P(0) holds and also that P(m) implies P(+m), then P holds for all natural numb- ers. For example, prove that (in origin 0): +/⍳⍵ ←→ 0.5×⍵×⍵-1 ⍝ (Gauss, aged 7). Proof by Induction: ⍝ Check P(0): +/⍳0 ←→ 0 ←→ 0.5×0×0-1 ⍝ by evaluation of +/⍳0 and 0.5×0×0-1 [0] ⍝ Check that P(m) implies P(+m): +/⍳⍵+1 ⍝ P(⍵+1), ¯¯¯¯ → ⍵++/⍳⍵ ⍝ defn of (origin 0) ⍳: ⍳⍵+1 ←→ (⍳⍵),⍵ ¯¯¯¯ → ⍵+0.5×⍵×⍵-1 ⍝ from P(⍵), [1] ¯ → (0.5×⍵×2)+0.5×⍵×⍵-1 ⍝ expand ⍵ → 0.5×⍵×2 ¯¯¯¯¯¯ ¯¯¯¯¯¯ → 0.5×⍵×2+⍵-1 ⍝ factor out 0.5×⍵× ¯¯¯¯¯ → 0.5×⍵×⍵+1 ⍝ resolve 2+⍵-1 → ⍵+1 ¯¯¯¯¯ → 0.5×(⍵+1)×⍵ ⍝ commute ⍵×⍵+1 → (⍵+1)×⍵ ¯ → 0.5×(⍵+1)×(⍵+1)-1 ⍝ expand ⍵ → (⍵+1)-1 ¯¯¯ ¯¯¯ → P(⍵+1) ⍝ therefore, P(⍵+1) holds. [2] Therefore, from [0], [1], [2] and Peano's axiom of induction, P holds for all natural numbers. (The young Carl Friedrich Gauss actually proved the equivalent assertion for origin-1 ⍳: +/⍳⍵ ←→ 0.5×⍵×⍵+1, which has a similar, though marginally messier, inductive proof.) And, finally ... ---------------- "There may, indeed, be other applications of the system than its use as a logic." - Alonzo Church (1903-1995). Church's lambda calculus provides the implementation framework for many modern functional languages. "Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk" (Dear God created the whole numbers, all else is the work of man.) - Leopold Kronecker (1823-1891). This quotation is often "improved" in translation. We wish Kronecker had excluded negative numbers by saying "natural numbers" or "non-negative integers", but he didn't. "There are no boring natural numbers, because if there were, one of them would be the lowest such number, which would make it interesting." - Anon. Back to: contents