|
Extending APL to Infinity
A recent proposal suggested that a positive and negative infinity be added to APL. This paper discusses the effect on APL of adding infinities to APL. There are two principal topics: infinities as elements and arrays having infinitely long axes. The properties of infinite elements and infinitely large arrays are exhibited by describing the behaviour of each primitive function with respect to them. 1. Introduction In a recent paper [Iv1] Iverson proposed that the symbols _ and ¯ be used to denote infinity and negative infinity, respectively. He shows the use of these symbols to denote the limit of a function or its inverse, to separate ordinary numeric arguments of the axis operator, and to denote an alternative fill character for the expand function. In this paper, we explore further the consequences of admitting symbols for infinities. There are two main issues: infinite elements and infinite axes. We discuss these in terms of their effect on the behaviour of each of the primitive functions. 1.1 Why have an infinity? Having a representation for infinity would be advantageous in several ways. For example, it would provide division by zero, directly or indirectly. This would, among other things, simplify the definition of the residue function. Currently, in order to provide a definition which is valid for all numeric arguments, the residue function must be defined by res:⍵-⍺×⌊⍵÷⍺+⍺=0 . The phrase at the end (“+⍺=0”) is included in order to avoid the domain error that would result in evaluating 0|a . Providing the result ¯ or _ for a÷0 would permit the definition for residue to be written more simply as res:⍵-⍺×⌊⍵÷⍺ . 1.2 Undefined versus indeterminate; pole An undefined expression is one for which no numerical result is available. In elementary school we learn that 3÷0 is undefined. Later we learn that ⍟0 is also undefined. If we study analysis we learn that an argument which would cause the result of a function to be infinitely large is said to be a pole of the function; this is a more sophisticated way of dealing with the notion of “undefined”. On the other hand, an indeterminate is an expression for which the rules of mathematics are ambiguous or do not give consistent guidance. Thus, in dealing with the case 0÷0 , one could argue that it should have the value 1 , since a÷a has the value 1 for nonzero a , and as a approaches zero from any direction, the expression maintains the value 1 . But one could also argue that 0÷0 should have the value 0 , since 0÷a has the value zero, and as a approaches zero from any direction the expression maintains the value 0 . Lastly, from a=b×c ←→ b=a÷c that, since 0=b×0 , any number b could be used as the value of 0÷0 . The point is, not what choice is made, but that a choice can be made and defended. To sum up: undefined means “no choice”,
whereas “indeterminate” means
“many choices”.
2. Orthography The symbols chosen by Iverson for infinities, the underbar _ and overbar ¯ , are different from the “lazy 8’ symbol used in conventional mathematics. This is undoubtedly partly because of the present limitations of the APL character set, but there is also both some justice to the choice, and some opportune additional benefits resulting from it. In a tabulation of results, a dash is frequently used to indicate “not available”. With the orthography proposed, we would have, for example: 3 2 1÷2 1 0 1.5 2 _ where the underline, signifies, in a sense, an “unavailable” result. Since the proposed characters are numeric in type, they would be added to the list of characters available for spelling names in APL, and would follow the rules given for the use of the numeric characters—they could appear within a name, but could not be used to begin a name. Thus, names of the form rate_of_pay could be formed which would have greater clarity than, for example, either rateofpay or rate∆of∆pay . There is even some hope that _ and ¯ could replace the characters ∆ and ⍙ as alphabetic extenders, thereby making ∆ available as a function symbol. 2.1 Complex complications There are orthographic complications in describing infinity in the complex plane. In his summary paper [Pe1] Penfield gives two proposals for the representation of a complex constant. In one, the real and imaginary parts are separated by the _ character, for example 3_4 . Penfield prefers the use of the dieresis character ¨ , rather than the underbar, since using the underbar as separator would require writing the complex constant having real and imaginary parts equal to infinity as ___ . On many printing or display devices the three underbars are not distinguished, but run together to form one line. However, we propose that any complex infinity
(one not on the real line) be represented in polar form.
One such polar form might be mpa ,
where m is the magnitude of the number
and a is the angle in degrees.
Thus an infinity at an angle of 30 degrees would
be represented by _p30 .
We propose that in a display of complex values
any non-infinite value be represented in rectangular form
(or as a real number), but that a complex infinity
be represented in polar form.
3. Representation in machine form This discussion is specific to the machine architecture of the IBM System/360 and equivalent machines, such as those made by Amdahl Corporation. Representations for other machine architectures would have to be devised to accord with the possibilities of those machines. In System/360, a long floating-point value has 64 bits. The first of these is the sign bit for the fraction, the next 7 are the (excess 64) exponent, and the remaining 56 are used, four at a time, for 14 hexadecimal fraction digits. A non-zero value is kept in a normalized form, in which the leading fraction digit is non-zero. This is the form in which APL implementations written for System/360 keep numbers with fractional parts as well as integers larger than can be accommodated in the 32-bit fixed point form. System/360 also as a short floating-point form, not used by APL implementations, which uses only 32 bits, and gives only 6 fraction digits. One could use a long unnormalized form, in which the first six fraction digits were zero, and the last eight encoded to have various meanings, to represent the infinities we are discussing. Thus, if such a floating point number were to appear as an argument, a simple test could determine that an infinity is present:
lter x,x test upper 6 digits
bz maybe branch if zero
...
...
maybe ltdr x,x test all 14 digits
bnz yes branch if non-zero
...
...
yes (code for infinite argument)
The sign bit could be used to distinguish
infinity from negative infinity.
The low-order 32 bits provide enough
encodings to represent not only the infinities
we are discussing, but also other special values,
such as indeterminates and infinitestimals.
One could even distinguish “true”
from “machine” infinities.
These matters will not be further discussed
in this paper.
4. Infinite elements as results; as arguments In this section we show which functions can produce arrays having infinite elements, and then discuss for each function the implications of allowing its argument(s) to have infinite elements. Only certain of the primitive functions can give results which are infinite. Before discussing these, however, we have to distinguish two cases. In the first case, the argument is a pole of the function, and the result is properly infinite. For example, 0 is a pole for the reciprocal function, and so ÷0 is properly infinite. In the second case, the argument is not a pole of the function, but the result is not representable in the machine environment. For example, !1000 is a perfectly ordinary, finite number, but since it has 2568 decimal digits it can’t be represented using System/360 architecture. Falkoff and Iverson point out [Fa1]
We propose that this latter class of results be called machine infinity, and that it also be represented by the underbar symbol. We shall distinguish true infinity from machine infinity in the tabulations of the scalar functions given below by “T” and “M”, for “true” and “machine”.
4.1 Infinities as results of monadic scalar functions Table 1 shows the monadic scalar functions which can produce an infinity as a result, indicates whether this is a true or machine infinity, whether this is a positive or negative infinity, or both, and, for a machine infinity, gives the range of values of the argument which produce the machine infinity, using the architecture of System/360, and the implementation of APL given by I.P. Sharp Associates. The functions which give a true infinity are reciprocal, logarithm, factorial and tangent. Except for logarithm, which gives negative infinity at zero, the others are ambiguous in that either infinity or negative infinity could be given as the value at each pole. There does not appear to be a simple rule which could be uniformly applied to decide which infinity should be given. For the tangent function, the ambiguity is resolved because we cannot represent π over two or the other members of its residue class, modulo two π, exactly, and thus any infinite result for the tangent function will be a machine infinity. The argument will always be just below or just above the pole, and therefore we are able to give either infinity or negative infinity, respectively, as the result. With reciprocal, for values of the argument which are sufficiently close to zero, we also can determine, using the sign of the argument, whether the result should be infinity or negative infinity. On the other hand, for the argument zero itself, there is no a priori reason for preferring either of the choices. The rule we propose is that the infinity chosen should [note] have the same sign as the result of applying the function to any number for which the pole is the floor. For example:
×÷0.5
1
⌊.5
0
and therefore,
÷0
_
×_
1
[Note: In EEM’s copy of the proceedings, the text from [Note] to the ×_ example is crossed out, replaced by the hand-written sentence “be positive if the argument is even, and negative if the argument is odd”.] The same rule can be applied to the poles of the factorial function (the negative integers). Thus:
×!¯2.3
1
⌊¯2.3
¯3
!¯3
_
×_
1
but on the other hand
×!¯3.2
¯1
⌊¯3.2
¯4
!¯4
¯
ׯ
¯1
4.2 Infinities as arguments of monadic scalar functions Once we admit the possibility of an infinity as a result of an expression, the question arises, what will be the result if this infinity is used in turn as the argument to a function. Table 3 shows, for each monadic scalar function, the result when it is applied to infinity or negative infinity. As will be seen, it seems useful to say that infinities, like zero, take on all the characterizations of real numbers. They are identically integers and non-integers, divisible by 2, multiples of 2π, and so forth. Reciprocation The value show for ÷_ and ÷¯ is 0 . Knuth [Kn1] makes the point that if infinity is used to represent what we call machine infinity, as well as true infinity, it is incorrect to give 0 as the result of ÷_ , “less inaccurate results be regarded as true answers!” He suggests that an indeterminate value be reserved for such results. In this paper we do not discuss the possibility of an indeterminate result, and give zero as the result of reciprocating infinity. Floor and ceiling These functions show how the infinities can be characterized as integers, since we see no alternative to giving as results the value of the arguments. Roll Statistically, any finite number has zero probability of being chosen out of an infinitude of numbers, and so we give _ as the result of ?_ . Logarithm The result of ⍟¯ is shown as a domain error. In fact, if complex numbers are admitted, it will be possible to give the logarithm of a negative number. In this paper we do not discuss further the implications of complex numbers on the question of infinities. Circular functions The circular
functions Factorial We show ¯ as the result of !¯ . Here we consider negative infinity not only to be an integer, but an even integer, since, as we saw in the discussion of Table 1 the factorial of negative even integers is negative infinity. 4.3 Infinities as results of dyadic scalar functions Table 2 shows the dyadic scalar functions which can produce infinity or negative infinity as a result. The only functions which give true infinities are those derived from the corresponding monadic scalar functions, namely divide and dyadic logarithm (from reciprocal and logarithm).
4.4 Infinities as arguments of dyadic scalar functions Table 4 shows the result of using each dyadic scalar function with negative infinity as one argument, and several kinds of other argument. For the commutative functions, such as addition, only one row is given, which may be read either with negative infinity as the left argument, each each element at the head of the columns as the right argument, or vice-versa. For the non-commutative functions, such as subtraction, there are two entries, the first showing negative infinity as left argument, with the elements at the head of the columns as right argument, and the second with negative infinity as right argument, and the elements at the head of the columns as left argument. Table 5 provides the same information for infinity as left and right argument. For many scalar dyadic functions we show domain error when both arguments are infinite. Although some authorities [Ba1 Bu1 Kn1] give results in some of these cases, we feel that there is enough disagreement among competent judges that at present we ought to beg the question. It is easier to remove a domain error than to put one in. 4.5 Infinities as results of mixed functions The two mixed functions that may give results having infinite elements are decode (⊥) and the two forms of ⌹ : matrix divide and matrix inverse. For decode, the infinities are machine infinities; this follows from the definition of decode in terms of addition and multiplication. Matrix inverse may result in a machine infinity if the matrix is close to singular, however it will also give a true infinity if its argument is a singular matrix, one having a zero determinant. To see why this is so, recall that the inverse of a square matrix is given by
⌹a ←→ (⍉adjoint a)÷det a
and if the determinant of a is zero, then for each non-zero element of the transposed adjoint, the corresponding element of the inverse will be infinite. An application where this would be useful is as follows: currently, it is difficult to determine (under program control) whether a given matrix is singular without error trapping facilities. If we permit division of non-zero by zero to give an infinite result, a test for singularity is given by _∊|⌹a . Similar results exist for dyadic ⌹ . 4.6 Infinities as arguments of mixed functions If a and b are arrays having one or more infinite elements, then expressions of the form ⍴a ⌽a ⍉a k↑a ,a k/a a⍳b ⍋a ⍕a a[k] k⍴a k⌽a k⍉a k↓a a,b k\a a∊b ⍒a k⍕a have obvious definitions in terms of current APL. The expressions a⍴b a↑b a↓b ⍳a can produce infinite arrays as discussed in the next section. For example, ⍳_ is an array such that (⍳_)[k] ←→ k . We see no way by which the deal function ? can be meaningfully defined for infinite arguments. The functions ⊤ , ⊥ ,
and ⌹ are defined in terms of more primitive functions,
and we may retain these definitions with respect
to infinite arguments.
For example, 5. Infinite arrays Expressions such as We say that a is an infinite array if _∊⍴a . The concept of infinite arrays adds significant new capabilities to APL. Consider the problem of evaluating the series for the constant e . This series is infinitely long, and practically speaking, one uses only a finite prefix of it. Suppose we wish to evaluate it until the n-th term is smaller than 1e¯8 . If we know that we don’t have to sum more than 25 terms, we can write
+/÷!⍳(1e¯8>÷!0,⍳25)⍳1 .
If, on the other hand, 1e¯8 is replaced by an arbitrarily small positive number eps , an accurate a priori bound may be difficult to compute. In this case, we might replace 25 by 100 or some larger number. But _ is greater than any number; hence we should be able to write
+/÷!⍳(eps>÷!0,⍳_)⍳1 ,
which gives a solution using the infinite vector ⍳_ . 5.1 Implementing infinite arrays Typically, an APL implementation stores an array with a header containing the number of the array’s axes and the length of each axis. For an infinite array, the length of an infinite axis can be given as a negative integer, for example ¯1 . Furthermore, an infinite array may be stored as a function of its indices. For example, to store the infinite vector v←2+3×⍳_ we need only to store the function vf:2+3×⍵ . Then it easy to see that v[k] ←→ vf k . Any particular element of v may be obtained by using the associated function vf . Since the user can never examine all the elements of v , it does not matter that the entire infinite array is not in fact stored; any portion of it may be computed as needed. A request such as
⎕←v
may be interpreted as continued evaluation and display of the results of vf until the user interrupts the display. Thus, to the user, it appears as if an infinite array is present. This is a generalization of the J-vector introduced by Abrams [Ab1] and implemented in several versions of APL. If v is an infinite vector and a is a scalar, then v⍳a should return the location of the first occurrence of a in v ; if a is not in v the search for it will go on forever. Hence the introduction of infinite arrays leads to simple expressions whose execution never terminates. Note that expressing an infinite array as a function of its coordinates implies that the number of axes of the array is finite; otherwise it is conceivable that we could never compute the value of a given array position. In particular, all infinite arrays have a countable number of elements, meaning that we can pair each element of v with a non-negative integer in a unique fashion. Before discussing in detail which mixed functions may be implemented on infinite arrays, it will be useful to make a few informal definitions concerning a monadic function f . f is totally locally computable (TLC) if there is a well-defined, terminating procedure to compute (f a)[k] for any k , which requires that the procedure need only look at a finite subset of a , and that the procedure need not have access to any global information about a ; f is partially locally computable (PLC) if such a procedure exists for certain a ; f is locally uncomputable (LUC) if such a procedure never exists. For example, f:2*⍺ is TLC since (f v)[k] ←→ 2*v[k] . The function g:⍺⍳1 is PLC, since if 1 is in v the computation v⍳1 will terminate, while if 1 is not in v it won’t. Finally, +/v is LUC since we can never compute the sum of an infinite number of elements by looking only at a finite subset. To compute +/v , “global” information about v is needed. Those functions that are TLC may be conveniently implemented. Those function which are PLC present more formidable difficulties. We can now discuss the implementation of primitive functions and operators with respect to infinite arrays. 5.2 Scalar functions of infinite arrays The scalar functions are easily implemented using the following identities. If a and b are infinite vectors then
(f a)[k] ←→ f a[k]
(a f b)[k] ←→ a[k] f b[k] .
5.3 Mixed functions of infinite arrays For most of the mixed functions it suffices to examine their behaviour for infinite vectors. Extension to higher-order arrays is based on their action on infinite vectors. Functions along finite axes of an infinite array are easily implemented. For example, if
a←_ 2⍴⍳_
then
(+/a)[k] ←→ +/a[k;] ←→ (4×k)-1 .
Since every infinite array is represented as a function of its indices, it suffices for implementation purposes to exhibit such a function. For example, the identity (⍳_)[k] ←→ k indicates how ⍳_ may be implemented. In the discussion that follows, a and b are infinite arrays, v and w are infinite vectors, k is a finite scalar, j is either a finite scalar or _ or ¯ , and c is a finite vector. shape: If a is an infinite array, then _∊⍴a . reshape: Here we must have ~_∊1↓⍴a . To see this, consider the following: an expression like 3 _⍴⍳_ says to fill an array in row-major order with three rows and an infinite number of columns with the numbers from one to infinity. This cannot be done, since it takes an infinite amount of numbers to fill the first row. Thus we have the unpleasant result that there are certain arrays that cannot be created with reshape alone. In particular, the identity
a ←→ (⍴a)⍴a
no longer holds in general, since the expression on the right may not even be defined. As another example, let a←(⍳3)∘.×⍳_ . Then _⍴a effectively takes only the first row of a . Reshape may be implemented using the fact that
(_⍴c)[k] ←→ c[1+(⍴c)|k-1]
ravel: This may be implemented using the identity ,a ←→ (×/⍴a)⍴a . Once again we obtain results that may look peculiar for infinite arrays of rank two or greater, that is,
,(⍳3)∘.×⍳_ ←→ _
reverse: ⌽v is not defined, since the “last” element of v is not defined. rotate: For non-negative, finite k , k⌽v is k↓v . k⌽v is not defined if k is negative or infinite.
transpose (monadic and dyadic): Transposition of infinite arrays (represented as functions of their indices) is facilitated by the use of Iverson’s “from” function [Iv1, p.17]:
i⌷a ←→ (,a)[1+⍉(⍴a)⊥⍉i-1]
(this definition in terms of ⊥ works correctly for ⍴a finite; it must be modified for infinite arrays, but the extension is clear). Then
k⌷j⍉a ←→ k[j]⌷a .
_↓v and ¯↓v are not defined. compress:
indexing: (v[w])[k] ←→ v[w[k]] index generator: (⍳_)[k] ←→ k
upgrade, downgrade: These functions are not in general well-defined. For example, no meaningful result can be assigned to
⍋2*-⍳_
monadic and dyadic format: These are both TLC functions, but no easy algorithm appears possible. decode, enclose, matrix inverse and divide, and execute: are all LUC and hence we propose that they not be implemented. 5.4 Derived functions of infinite arrays inner product, reduction: These generally create LUC functions, and hence cannot be easily implemented [Mo1]. scan: (f\v)[k] ←→ f/v[⍳k] outer product:
i⌷a∘.f b ←→ (((⍴⍴a)↑i)⌷a)f((-⍴⍴b)↑i)⌷b
where ⍴i ←→ (⍴⍴a)+⍴⍴b 5.5 Display of infinite arrays Since APL prints arrays in row-major order, we encounter problems when trying to display arrays a with _∊1↓⍴a . For example, since it takes an infinite amount of time to print the first row of (⍳4)∘.×⍳_ , we never get to see the other rows. However, Breed [Br1] has shown how APL display can be modified so that, instead of displaying a matrix by giving each row it its entirety before starting the next row, one could instead display as much of each row as would fit in the print width before going on with the remainder of each row, continuing in this fashion until the entire matrix has been displayed. To illustrate the effect, compare the way an APL system currently displays the matrix a←2 20⍴⍳40 , with print width set at 40:
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 28 29 30 31 32 33
34 35 36 37 38 39 40
with the way it would be displayed using Breed’s modification:
1 2 3 4 5 6 7 8 9 10 11 12 13
21 22 23 24 25 26 27 28 29 30 31 32 33
14 15 16 17 18 19 20
34 35 36 37 38 39 40
This suggestion applies also to higher rank arrays having only one infinite axis, where the infinite axis is the last axis: successive infixes of all the planes, etc. are displayed to the extent that they can fill the given display width, before the remainder of the planes, etc. are displayed. It cannot be used for displaying an array having more than one infinite axis. 5.6 The functions diag and idiag As we noted before, if a is an infinite array, then ,a may not include all the elements of a . However, a function can be defined which converts an infinite array to an infinite vector without “losing” information. For example, suppose
a←(⍳_)∘.×⍳_
5 5↑a
1 2 3 4 5
2 4 6 8 10
3 6 9 12 15
4 8 12 16 20
5 10 15 20 25
We can convert a to a vector by selecting elements from successive diagonals of the array:
diag a
1 2 2 3 4 3 4 6 6 4 5 8 9 8 5 ...
diag for finite arrays may be defined as follows:
diag:(,⍵)[⍋,+⌿iota⍴⍵]
iota:1+⍵⊤⍵⍴(⍳×/⍵)-1
diag causes a diagonal transformation of its array right argument. The result is a vector. diag allows the user to examine arrays that otherwise could not be printed. For example,
diag (⍳2)∘.+⍳_
2 3 3 4 4 5 5 6 6 7 7 8 ...
diag may be used with finite arrays as well, of course:
diag 3 5⍴⍳15
1 2 6 3 7 11 4 8 12 5 9 13 10 14 15
The inverse to the function diag is the function idiag . For finite arrays we have the following definition:
idiag:⍺⍴⍵[⍋⍋,+⌿iota⍺]
Note that idiag is dyadic; the left argument specifies the shape of the result. We have
a ←→ (⍴a)idiag diag a
This identity holds for all arrays a , while the related identity
a ←→ (⍴a)⍴,a
holds only for finite arrays. Example:
a←_ _ idiag ⍳_
5 5↑a
1 2 4 7 11
3 5 8 12 17
6 9 13 18 24
10 14 19 25 32
15 20 26 33 41
idiag (unlike reshape) allows the creation
of infinite arrays of any shape.
Acknowledgments We should like to thank the following people,
who read an early draft of this paper and
gave us many valuable comments:
Larry Breed of IBM, Paul Penfield of MIT,
Steve Smoller of General Research,
and Arlene Azzarello, Bob Bernecky,
Leigh Clayton, Doug Forkes, Ken Iverson,
Roland Pesch, Joey Tuttle, and Ed Wilts,
of I.P. Sharp Associates.
References
Originally appeared in the APL80 Conference Proceedings, 1980.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||