Phrasal Forms
Note: In this paper we use the linguistic terms verb and pronoun interchangeably with the mathematical terms function and variable. Introduction In standard APL [ISO88] certain forms are ungrammatical, and new definitions could be adopted for them without conflict. Such definitions we shall call phrasal forms [AHD76]. For example, if b and c are pronouns, the phrase b c is meaningless, and in APL2 [IBM85] the definition (⊂ b), (⊂ c) , where ⊂ is the APL2 enclose function, is adopted for it. Verb Rank The notion of verb rank, first introduced by Iverson [Iv78], later elaborated by Keenan [Ke79], and further evolved by Whitney [Wh84], has been adopted by Iverson in his Dictionary [Iv87]. It refers to the rank of the subarrays of an argument which are the cells to which the verb aplies. For example, the cells that negate applies to are items, and items are ranlk zero objects, and thus we say the rank of negate is zero. Similarly, the cells to which reverse applies are lists, or rank ome objects, and thus we say the rank of reverse is one. Not only primitive verbs, but also derived and defined verbs have rank. The idea is a powerful one, producing great simplifications, and so we define the ranks of the new constructions we describe herein. Definitions In the following definitions, f , g , and h denote verbs and ⍺ and ⍵ denote pronouns. Hook. A hook is denoted by f g and is defined formally by identities and informally by hook-shaped diagrams as follows: (fg)⍵ ←→ ⍵fg⍵ ; ⍺(fg)⍵ ←→ ⍺fg⍵ f f / \ / \ ⍵ g ⍺ g \ \ ⍵ ⍵ The rank of the hook f g is the maximum of the ranks of f and g . Note that the verb is used monadically. Fork. A fork is denoted by f g h and is defined formally by identities and informally by forking diagrams as follows: (fgh)⍵ ←→ (f⍵)g(h⍵) ; ⍺(fgh)⍵ ←→ (⍺f⍵)g(⍺h⍵) g g / \ / \ f h f h / \ / \ / \ ⍵ ⍵ ⍺ ⍵ ⍺ ⍵ The rank of the fork f g h is the maximum of the ranks of f and g . Note that the central verb is used dyadically or monadically according to whether the fork is applied to two arguments or one. Parenthesis are required around hook and fork forms only to avoid ambiguity. Discussion of Hook and Fork Hook. In combinatory logic one of the most useful primitive combinators is designated by S [Sch24]. Curry defines Sfgx in prefix notation to be fx(gx) [CuFeCr74]. In common mathematical infix notation this would be given by (x)f(g(x)) , which one can write in APL as xfgx , and this is the hook form (fg)x . The combinatory logician appreciates this form because of its great expressiveness: it can be shown that S , along with K , the constancy combinator, suffice to define all other combinators of interest [Ro50]. (The constancy combinator K is defined in infix notation so that cKx has the value c for all x .) Users of APL will appreciate the hook for the same reasons. For example, +÷ adds the reciprocal of the right argument to the left argument, a form used in describing continued fractions. Thus (+÷)\3 7 16 ¯294 gives the first four convergents to pi, which, to nine decimals, are 3, 3.1412857143, 3.14159292, and 3.141592654. Further, =⌊ is a proposition that tests whether its argument is an integer, the number of primes less than positive integer ⍵ is approximately (÷⍟)⍵ ; and to decompose a number ⍵ into numerator and denominator, one can write (÷∨/)⍵, 1 (where ∨ is the greatest common divisor). Fork. The forks f + h and f × h and f ÷ h provide formal treatment of the identical but informal phrases used in mathematics [e.g. Ef89] for the sum and product and quotient, respectively, of two functions. Further, the treatment of sets in terms of propositions p and q defining them may be expressed as the forks p ∨ q and p ∧ q and p ≠ q for the union, intersection, and symmetric difference of sets. The fork form also provides a convenient notation for expressing the notion of function arrays, as in +,-,×,÷ as will be discussed in more detail below. Curry [Cu31] defines a formalizing combinator, Φ , in prefix notation, such that Φfghx means f(gx)(hx) . In common mathematical infix notation this would be designated by (g(x))f(h(x)) . An example of this form is Φ+sin2cos2θ , meaning sin2θ+cos2θ . The fork (f g h)⍵ has the same meaning, namely (f⍵)g(h⍵) . Curry named this the formalizing combinator because of its role in defining formal implication in terms of ordinary implication. Iverson and Whitney have made several earlier suggestions of ways to achieve what the fork form provides: the scalar operators of [Iv78], [Iv79a], [Iv 79b], the til operator of [Iv82], the union and intersection conjunctions of [Iv87], and the yoke adverb of [Iv88]. Benkard [Bk87] has also suggested a way to achieve the meaning of this form, in his proposal for ↑g/(f h)⍺ ⍵ , using the notion of function pair (↑ is APL2’s first function). The present proposal has significant advantages over these earlier ones. As instances of the use of this form, f + h and f - h and f × h yield verbs that are the sum, difference, and product of the verbs f and h . If f and h are propositions defining sets, then f ∨ h and f ∧ h and f > h yield propositions defining the union, intersection, and difference of sets. The dyadic case of f g h handles relations, as in < ∧ = for ≤ , or in the tautology < = (< ∨ =) . The set greater than 0 and less than 100 can be defined by >¨O∨<¨100 . In words this says “greater than zero and less than one hundred”. The corresponding set restricted to integers can be expressed using hook by >¨O∨<¨100∨(=⌊) . (The forms m¨g and f¨n , where m and n are nouns, are from [IV87], and provide a way of obtaining a monadic verb from a dyadic one, by fixing the left or right argument, respectively. Logicians have coined the verb “to Curry” to describe this fixing. They can be read “m with g” and “f with n”, respectively.) The forms (⊢ g ⊢)⍵ and (⊢ g ⊣)⍵ are equivalent to ⍵g⍵ and ⍵g⍺ , respectively, and thus provide the functionality of the duplicate and swap adverbs of [Iv87]. The symbols ⊢ and ⊣ denote the right and left functions of [Iv87], respectively. Backus [Ba78] defines a construction functional form [f1, ,fn] : x to mean < f1 : x, ,fn : x > . For example, [f,g] :x would be written as f(x),g(x) in common mathematical notation. In the specific fork form where the central verb g is catenation, as in f,h, we obtain the equivalent of Backus’s construction form. For example, (-b)(+,-)√((b*2)-4×a×c)÷2×a gives the two roots of the quadratic equation ax2+bx+c . Note that the fork form extends to any odd number of verbs. (If there are an even number of verbs, the leftmost of these is the composite fork defined by the remaining odd number of verbs.) For example, the tautology ≤ = (< ∨ =) may also be written without the parentheses as ≤ = < ∨ = . On the other hand, the expression +,-,x,÷ of seven verbs from [FIS64] can be parenthesized (redundantly) without changing its meaning as (+,(-,(x,÷))) . If we assign f ← +,-,x,÷ , then f 10 yields 10 ¯10 1 0.1 and 9f10 yields 19 ¯1 90. 0.9 . If the central verb g is ⍤< , that is, catenation composed with box, the results of applying the verbs f and h are boxed before being catenated, thus accommodating results which are not uniform in shape. This construction form was used informally in the early years of APL [Fa62, FIS64], preceding its initial implementation, and has in recent years been discussed in APL papers under the heading function arrays: [Bk83, Bk84, Be84, Br84, Bk85a, Bk85b, Bk86, La86, Bk87, La88]. In most of these discussions, the form (f g h)x is taken to mean (f 0{x),(g 1{x),(h 2(x) , and an error would be signalled if x were a vector or higher-rank array with first axis not of length three; and for scalar x the form (f g h)x would mean (fx),(gx),(hx) (where ⍺{⍵ selects element ⍺ from array ⍵) . Experimenting with Hook and Fork The functions defs and def (both listed in ISO APL) can be used to experiment with hook and fork. defs permits entering definitions until an empty line is entered. def permits entering a single definition. They both use the inner function d , which in turn uses the auxiliary functions m , t , and n . Spaces are used to separate the functions, but this a device only required in the model. A sample session is given below: defs whole←= ⌊ whin←3¨> ^ whole ^ 0¨< whole a←.5×⍳7 1 0 1 0 1 0 1 whin a 0 0 1 0 1 0 0 2 whole a 0 0 0 0 1 1 0 def sort←{⊂ ⎕av¨⍋ sort 'I sing of Olaf' IOaffgilnos The definitions of the functions are as follows: defs;b;⎕io →(0=⍴b←⍞)/⎕io←0 →1,0⍴⎕fx d b,' ' def:0 0⍴⎕fx d ⍞,' ',0⍴⎕io←0 r←d b;e;h;i;p;r;u;y i←¯1↓(b∊' ')/⍳⍴b←u\(u←b≠'←')/b h←'z←x ',(i[0]↑y←' y)' r←(e←~2|⍴i)/'yx',m t 0 →u/l,⍴p←' ',(1,~u←2=⍴i)⍴' x' k:r←r,'(',' x',m(t e),y,t e+1 →((⍴i)>1+e←e+2)/k l:r←(m'→0,0⍴z←'),r,p,m(¯1↑i)↓b r←h n('→2+0≠⎕nc''x''')n r,'y' m:⍵,[¯.5]⍵ t:i[⍵]↓i[⍵1]↑b n:((1↓m)↑⍺),[0](m←(0,⍴⍺) ⌈⍴⍵)↑⍵ References
Errata
First appeared in the Proceedings of the APL89 Conference, APL Quote-Quad, Volume 19, Number 4, 1989-08.
|