Phrasal Forms

    K. E. Iverson
   
Toronto
          E. E. McDonnell
I. P. Sharp Associates
Palo Alto


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 andanddenote 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 integeris approximately (÷⍟)⍵ ; and to decompose a numberinto numerator and denominator, one can write (÷∨/)⍵, 1 (whereis 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 symbolsanddenote 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

[AHD76]  American Heritage Dictionary, Second College Edition, Houghton-Mifflin Company, Boston (1976). See page 51: “A phrasal verb is an idiomatic expression … with a unitary meaning that is equal to more than the sum of the separate meanings of its elements.”
[Ba78]  Backus, John, “Can Programming Be Liberated from the von Neumann Style? A Functional Style and its Algebra of Programs”, CACM 21, 8, (August 1978).
[Bk83]  Benkard, J. P., “Valence and Precedence in APL Extensions”, APL Quote-Quad 13, 3 (March, 1983).
[Bk84]  Benkard, J. P., “Syntactic Experiments with Arrays of Functions and Operators”, APL Quote-Quad 14, 4 (June, 1984).
[Bk85a]  Benkard, J. P., “Control of Structure and Evaluation”, APL Quote-Quad 15, 4 (June, 1985).
[Bk85b]  Benkard, J. P., “Structural Experiments with Arrays of Functions”, ibid.
[Bk86]  Benkard, J. P., “Analysis of Function Application in Deep Arrays”, APL Quote-Quad 16, 4 (July, 1985).
[Bk87]  Benkard, J. P., “Implications of APL2 Grammar”, APL Quote-Quad 17, 4 (May, 1987).
[Be84]  Bernecky, Robert, “Function Arrays”, APL Quote-Quad 14, 4 (June, 1984).
[Br84]  Brown, James A., “Function Assignment and Arrays of Functions”, APL Quote-Quad 14, 4 (June, 1984).
[Cu31]  Curry, Haskell B., “The universal quantifier in combinatory logic”, Ann. of Math. (2) 32, (1931).
[CuFeCr74]  Curry, Haskell B., and Robert Feys, with William Craig, Combinatory Logic, North-Holland Publishing Company, Amsterdam (1974).
[Ef89]  Effros, Edward G., “Why the circle is connected”, The Mathematical Intelligencer 11, 1, Springer-Verlag (Winter 1989).
[Fa62]  Falkoff, Adin D., “Algorithms for Parallel-Search Memories”, JACM 9, 4 (October, 1962).
[FIS64],  Falkoff, Adin D., Kenneth E. Iverson, and Edward D. Sussenguth, “A Formal Description of System/360”, IBM Systems Journal 3, 3 (1964).
[IBM85]  APL2 Programming: Language Reference, SH20-9227-1, IBM Corporation, San Jose, CA (1985).
[ISO88]  Morrow, L. A., ed., Programming Language APL, International Standards Organization, Geneva (to appear).
[Iv78]  Iverson, K. E., “Operators and Functions”, IBM Research Report RC7091, April 1978.
[Iv79a]  Iverson, K. E., “The Derivative Operator”, APL Quote-Quad 9, 4, part 1 (June, 1979).
[Iv79b]  Iverson, K. E., “Operators”, ACM Transactions on Programming Languages and Systems 1, 2, October 1979.
[Iv82]  Iverson, K. E., and Arthur T. Whitney, “Practical Uses of a Model of APL”, APL Quote-Quad 13, 1 (1982).
[Iv87]  Iverson, K. E., “A Dictionary of APL”, APL Quote-Quad 18, 1 (1987).
[Iv88]  Iverson, K. E., “A Commentary on APL Development”, APL Quote-Quad 19, 1 (September, 1988).
[Ke79]  Keenan, Douglas J., “Operators and Uniform Forms”, APL Quote-Quad 9,4, part 1 (June, 1979).
[La86]  Landaeta, David J., “A Notation for Manipulating Arrays of Operations”, APL Quote-Quad 16, 4 (July, 1986).
[La88]  Landaeta, David J., “The Theory of Function Arrays”, APL Quote-Quad 18, 2 (December, 1987).
[Mo73]  More, Trenchard, Notes on the development of a theory of arrays, IBM Philadelphia Scientific Center Technical Report Number 320-3016, May 1973.
[Ro50]  Rosenbloom, Paul C., The Elements of Mathematical Logic, Dover (1950).
[Sch24]  Schönfinkel, M., “Über die Bausteine der mathematischen Logik”, Math. Ann. 92 (1924).
[Wh84]  Whitney, A. T., informal communication, Heidelberg, 1984.



Errata

  In the Verb Rank section, it should say “applies” instead of “aplies”; “rank zero objects” instead of “ranlk zero objects”; and “rank one objects” instead of “rank ome objects”.
  In the definition of hook, it should say “the verb g is used monadically” instead of “the verb is used monadically”.
  In the definition of fork, it should say that the rank of f g h is the maximum of the ranks of f and h instead of the maximum of the ranks of f and g . Moreover, it should say “Note that the verbs f and h are used dyadically or monadically …” instead of “Note that the central verb is used dyadically or monadically …”.
  In the discussion of fork, it should say [Iv79b] instead of [Iv 79b].
  In the discussion of fork,is equivalent to the fork <∨= and not to <^= .
  In the discussion of fork, the set greater than 0 and less than 100 is defined by >¨0^<¨100 and not >¨0∨<¨100 . The corresponding set restricted to integers is expressed as >¨0^<¨100^(=⌊) and not >¨0∨<¨100∨(=⌊) .
  In the discussion of fork, the label for the 1987 Iverson paper should be [Iv87] rather than [IV87].
  In the discussion of fork, the quadratic formula
    (-b)(+,-)√((b*2)-4×a×c)÷2×a
should be
    ((-b)(+,-)√(b*2)-4×a×c)÷2×a .
  In the discussion of fork, in the next-to-last paragraph, the verb “catenation composed with box” is ,⍤> (the , is missing in the text).
  In the Experimenting with Hook and Fork section, the first line in the sample session should be indented by 6 spaces instead of 12.
  The model of hook and fork does not work. It has multiple errors: for example, line 2 of function d has an unmatched left parenthesis, and function t has the illegal construct ⍵1 It is not apparent how to fix the model without rewriting it in its entirety.
  Reference [Bk86] was published in July 1986 instead of July 1985.
  In the References, it should say “[FIS64]” instead of “[FIS64],”.
  The label for the 1982 Iverson and Whitney paper should be [IW82] instead of [Iv82].
  [Mo73] is not referenced.



First appeared in the Proceedings of the APL89 Conference, APL Quote-Quad, Volume 19, Number 4, 1989-08.

created:  2009-10-10 21:20
updated:2014-01-06 12:20