Object Oriented Extensions to APL and J
Vector 9:2, page 116
Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 116
Introduction¶
This paper is a preliminary investigation, motivated by a series of simple examples rather than theory, into how object-oriented (OO) extensions can be made to APL in a parsimonious manner, i.e. in a way which maintains compatibility with the existing language, which introduces few new language constructs and which, most importantly, does not change those characteristics which make APL unique.
The first section contains a brief introduction to OO programming concepts. This is followed by a two-stage description of our proposed extensions. The paper next gives a short critique and suggestions for future research. It concludes with several examples where OO capability yields simpler and more robust designs than are possible in APL. The work here is preliminary, but we have tried to be as complete as possible in the development of our ideas.
Object-Oriented Programming and System Design¶
Software modularity and reusability have proven to be elusive goals in computer programming. By modularity we mean software elements which: correspond to syntactic units in the language, have explicit interfaces and provide a high degree of information hiding. A modular language allows us to decompose complex problems into subproblems which can then be solved separately. Because such modules tend to be relatively simple and focus on the solution of a single functional requirement, modularity makes software more understandable and encourages the construction of new software elements by combining existing ones in new ways. Finally, modularity restricts the scope of both design changes and execution side-effects to one (or at least a few) modules [Meyer 88].
Reusability imposes certain requirements on modules. First, modules should have a measure of generality: e.g. if we implement a linked list module, then linked lists composed of different types of elements should not require different versions of the module. Second, similar types of module should behave in similar ways: e.g. ordered lists and unordered lists should have many common aspects of behaviour. Third, related functions and data must be grouped together. Fourth, users of a module must be able to use it without knowing how it is implemented. And fifth, related groups of modules should be able to share common parts of their implementations [Meyer 88].
Object-oriented programming languages seek to achieve modularity and reusability through four characteristics: abstraction, encapsulation, inheritance and polymorphism. Abstraction means that the user only needs to know what a module does, not how it does it. Encapsulation means that the details of both the interface and implementation are grouped together into a unit. In fact, objects are encapsulations of abstractions [Pinson 88]. Abstraction and encapsulation focus on achieving the goal of modularity.
Inheritance and polymorphism on the other hand provide mechanisms for managing objects in ways which enhance their reusability. Inheritance refers to the ability of one object (the child) to inherit some of its behaviour from another (the parent). If a child can inherit from more than one parent, then this is said to be multiple inheritance [Meyer 88].
Polymorphism is the ability to take on more than one form. This is manifested in two ways. First, the same name may mean different things depending upon the type of object being referenced. Thus, if we have a list of polygons, then asking a "square" what its area is calls a different routine than the same request of a "circle". Second, in strongly typed languages it represents a relaxation of type checking to the extent that if a routine calls for an instance of a particular type, then it is also valid to use a type which is a child of it [Meyer 88].
Although the details vary from language to language, objects are typically referenced by an <object><message><arguments> triple. The message generates a call to one of the methods located in object with the arguments given.
The form is often object.message(arguments) as it is in Eiffel, C++, Objective-C and Turbo Pascal. This notation is an extension of structure or record field referencing. For more information readers are encouraged to consult the many good introductions to OO programming such as [Cox 87], [Meyer 88], [Pinson 88] and [Stroustrup 86] in the bibliography.
Extending a Non-OO Language¶
While there exist languages which were envisioned from the start to be OO, e.g. Smalltalk and Eiffel, many OO languages have been developed by extending an existing language to directly support an object paradigm. Turbo Pascal, LISP, Objective-C and, the best known, C++ are all examples. In fact, the oldest and still one of the best is SIMULA which grew from ALGOL [Meyer 88].
Many of the features of OO design can be used in a non-OO language by establishing a disciplined approach to object definition using a metaphor native to the language at hand. For example, we can bind data and functions together in C by building structures which contain pointers to functions. In C++ this programming-discipline-plus-object metaphor has been replaced by extensions to the language itself. Nevertheless, the motivating metaphor remains: C++ objects look very much like structures. Structures are themselves just the simplest objects, ones containing only data [Stroustrup 86].
We want to extend APL to support an OO paradigm in a way which both preserves the character of the language and still provides abstraction, encapsulation, inheritance and polymorphism. Given those objectives, we must begin with some native metaphor which gives us most of the capabilities of OO programming in the language as it is now. There are many ways support of OO programming can be added to APL, but most of the obvious ones are precluded by these requirements. For example, adding some form of typing or fixed object definition would change the language in ways we would find unacceptable. Alternatively, binding of data and functions by permitting functions to exist as array elements (or gerunds in J) is extremely cumbersome: arrays do not permit us to reference their elements by name.
What structure exists in APL which can be exploited in this way? APL contains variables, functions and operators (in J, nouns, verbs, adverbs and conjunctions) bound together in a workspace. Elements in a workspace are defined through assignment augmented by a collection of structure functions, such as reshape and transpose. Thus, in APL the most natural mechanism for binding together disparate elements into groups within which they can be referenced by name is the workspace itself.
We propose that the creation of objects in APL be accomplished by binding together variables, functions and operators into a subspace — a local workspace in which all name references are strictly internal and in which communication with the "outside" is accomplished primarily by passing arguments to and receiving results from a set of public functions. Such a metaphor is parsimonious; yet, allows us to introduce a full complement of OO features into the language.
Subspaces will be described in two parts. The first will introduce a single new notational convention into APL. In this preliminary form subspaces provide a facility somewhat more powerful than, say, packages in APL2 or modules in Modula-2, but somewhat less than true classes in a full OO language such as Smalltalk. We have chosen the J dialect of APL [Iverson 91] as the basis for our exposition because it is relatively new and perhaps more amendable, because it appears to be extremely portable, and because its developers have generously released its source code.
Extending J — The In-Object Paradigm¶
By way of an example, we define an association list subspace. The list. subspace (the period is significant) uses a global noun .data, which is a two-column table of boxed elements. Each row (TAG; ITEM) of .data contains the association tag and data for the list. The noun .data is global only within the list. subspace, and as is true for all objects within a subspace it cannot be referenced directly outside the subspace.
Names can be referenced by identifying the subspace, using the form subspace.name. In the case of .data the "." prefix precludes this form of reference, forcing private usage of the pronoun. Note the conventions introduced so far:
subspace. |
subspace reference |
subspace.name |
reference to name within subspace |
.name |
strict internalization of name within subspace |
Obviously, subspace names must contain at least two characters; otherwise, there would be conflicts with existing J primitives (such as i. or e.). We assume the session manager has been extended so that the subspace context can be set and that all definitions immediately below occur within the context of the list. subspace.
We will need the following proverbs. Unless otherwise noted they return the final value of .data; this is for purposes of exposition only and is represented schematically by LISTDATA. The non-J character "←" (left arrow) is used below to indicate the type of value returned. The first is a dyadic proverb which creates or re-initializes the list.
The next is a monadic proverb which tests for the presence of a tag in the list, returning a 1 if found and a 0 otherwise, represented schematically by BOOLEAN.
This monadic proverb returns the item from the list given its associated tag.
The last is a slightly more complex example. The dyadic proverb list.insert will add a new item or update an existing one. It uses two private (i.e. private to list. not private to list.insert) proverbs, .add and .replace. Note that the reference is to contains and not list.contains because list.insert executes within the context of the list. subspace.
usage: LISTDATA ← TAG list.insert ITEM
definitions:
.add =. '' : ' .data=: .data, x.;y.'
.replace =. '' : '.data=:(x.;y.)((0{"1 .data)i.<x.)} .data'
insert =. '' : 'x. ((.add' .replace)@.contains x.) y.'
Here is a sample session using the list. subspace:
'abc' list.create 10 20 30
┌───┬────────┐
│abc│10 20 30│
└───┴────────┘
'def' list.insert 100 200
┌───┬────────┐
│abc│10 20 30│
├───┼────────┤
│def│100 200 │
└───┴────────┘
list.contains 'abc'
1
list.fetch 'abc'
10 20 30
'abc' list.insert 50 1000 2 10 3 5
┌───┬────────────────┐
│abc│50 1000 2 10 3 5│
├───┼────────────────┤
│def│100 200 │
└───┴────────────────┘
list.contains 'yz'
0
'yz' list.insert 1 1 2 3 5 8
┌───┬────────────────┐
│abc│50 1000 2 10 3 5│
├───┼────────────────┤
│def│100 200 │
├───┼────────────────┤
│yz │1 1 2 3 5 8 │
└───┴────────────────┘
list.contains 'yz'
1
Note that .data is not directly accessible outside the subspace, although later we will provide a general mechanism for by-passing the interface to reference private names. Users of list. do not need to concern themselves with implementation, only usage. If we wanted to give a user read only access to .data we could define a proverb:
We can assign one subspace to another; "inheritance" for subspaces is handled as inheritance for other elements in J, by "assignment" suitably augmented by "structure functions":
This sentence would duplicate the elements of one subspace in the other. If we executed anotherlist.create, the create proverb would execute in the context of the subspace from within which it was called. Thus, the .data pronoun that was re-initialized would be the copy in anotherlist. while the copy in list. would remain unchanged.
As it does in J normally, a simple assignment of one subspace to another results in inheritance by reference for verbs. Invoking a proverb in anotherlist. causes the associated proverbs in the original list. subspace to be called, but that execution would occur in the context of the anotherlist. subspace. If we wished to accomplish inheritance by value, then we would apply the fix adverb f. as follows:
This would result in an actual copy of verb values from one subspace to another.
The difference is important. In the first case changes in list. would be reflected in anotherlist. and in the second the two subspaces would have independent existences. The precise mechanisms of inheritance would be different for different dialects of APL, but we would certainly always want to be able to control which sort of inheritance, by reference or by value, we were applying. This allows us to set up subspace prototypes without introducing strict typing into the language. Multiple inheritance could be supported by having the "methods" of a particular subspace refer back to more than one prototype.
Subspaces in their current form give us a capability somewhat more than simple modules as in Modula-2, Ada and some Pascals because they function as more than simple libraries of procedures and functions with a well-defined interface. Each subspace is an independent context, and one would anticipate that multiple instantiations would be the rule. Also, real inheritance is provided for in this scheme.
As a matter of fact, subspaces alone add a number of capabilities to APL and J that are extremely useful. For example, we can have verbs with static nouns (nouns with values that persist between calls), record structures (subspaces consisting only of nouns), program modules and libraries and simple objects such as our list. subspace above. All this goes a long way towards satisfying our original goals of modularity and reusability even if it falls short of full OO capability.
Extending J — The On-Object Paradigm¶
To see where subspaces fail to give us full OO capability, we’ll return to our simple example. Assume we have two lists, alist. and blist., which we wish to merge and assign the result to the alist. list. A natural expectation would be to define a monadic proverb merge in the alist. subspace which is used:
This is a more general use of subspaces because it involves an operation on a subspace rather than in one. To accomplish this extension we introduce one new conjunction ::, which returns the entire subspace upon completion. There are also two prospaces, L. for the left subspace argument and R. for the right. And we must have a conjunction s. to force a reference in one subspace to execute in the context of a specified subspace. Then merge can be defined:
Definitions made with the : conjunction use the "in" paradigm and definitions made with the :: conjunction use the "on" paradigm. It is through the s. conjunction that inheritance from prototypes is accomplished. Thus, in our original example if the anotherlist. subspace inherits from the prototype-parent subspace, then a verb method in the child becomes:
… in the child.
We must also be able to treat subspaces as we would any other first-class object. For example, if we have a subspace employee_record. containing only the pronouns name, id_number and address, then
… would insert that subspace as an element in the list. subspace. Note that what is stored is not a reference to employee_record. but its value. If we subsequently deleted the named subspace then the list would still contain those values. Thus, subspaces do not need to be named explicitly, any more than, say, the elements of a numeric array need to be individually named.
It is clear that unless we can use subspaces as software elements in their own right, and not simply as a way for grouping references, we do not have a true OO programming language.
Review and Critique¶
Have we achieved the four capabilities required for OO programming: abstraction, encapsulation, inheritance and polymorphism?
Subspaces are true abstract data types. Users need only concern themselves with the interface and not the implementation. We could change our list. subspace in some very fundamental ways, e.g. making it file-based rather than using an in-memory array, and, as long as we did not change its interface, not a single line of user code would need to be changed.
Encapsulation is achieved by clearly separating public and private names. The interface between a subspace and the outside world is clearly defined. A limited form of access to private references is granted via the new s. conjunction.
Inheritance for subspaces is handled as it is for any other object in APL or J: by assignment augmented by appropriate structural operators. We further assume the session manager is extended so that a user can "enter" and "leave" a subspace so that the construction of a subspace can also proceed in the same way a user creates a workspace now. Multiple inheritance is supported.
Finally polymorphism, it turns out, is easy. APL and J are naturally polymorphic. Because they are not statically typed, there is no need to employ special mechanisms which allow for type generalization.
One concern one may have is that subspaces encourage the use of side-effects. Clearly, if one’s ideal of programming is to use tacit programming in J to produce pure functions, this will be of some concern. However, properly constructed subspaces will encapsulate their state in private names and, hence, will not have side-effects.
Anyone who has worked on large APL-based systems has had the experience of seeing a clear and coherent design become obscured in implementation by the large number of global variables and low-level support functions that inevitably seem to clog up the workspace. It is little comfort that we have avoided side-effects in our functions when our workspaces are littered with them.
The ability to group variables and functions into packages, as is possible in some APLs, is a major advance, but falls short of providing all the capabilities we need to begin to build modular and reusable software in a disciplined manner. Packages do not go far enough and are too difficult to use. They are not really part of language.
Another issue is that of efficiency and complexity. As the depth and size of the inheritance tree grows, there is a real possibility that the overhead required to call functions, and the difficulty of understanding the system in toto, will become too great to be tolerated. Experience with Smalltalk, however, has shown this not to be the case. It should be possible to design an OO-extended APL or J interpreter which both performs well and is adequately supported by tracing and browsing tools. In fact, because many operations will occur using ordinary APL and J primitives (unlike Smalltalk where everything is an object including integers, characters, etc.) it should be possible to produce interpreters which have significantly better performance than found in Smalltalk.
Some Applications¶
Here are some possible applications. Consider static nouns in verbs: there are many instances where some notion of state must be encoded in one or more global variables. For example, in a pseudo-random number generator, the next number in the sequence is calculated by applying some function to the previous one.
Subspaces consisting only of nouns are record-like objects which nevertheless do not impose static typing on the language and maintain APL’s characteristic flexibility. A vector, each element of which is a boxed subspace of "employee records", is a much easier thing to work with than a matrix in which we must know the convention that column 1 is the name, column 2 the address, etc.
Standard libraries or software modules can be implemented with subspaces. For example, a time series "library" subspace can be designed so that it expects input in the form of some "record" subspaces which have "fields" describing the start and end dates, the frequency (daily, monthly, etc.) and the time series data themselves. It would be easy then to define a library function that could add together two time series, producing as a result a new time series containing the sums at their intersecting dates.
Another example where software modules would be useful would be as interfaces to external processes or devices. Graphics is a good example in which a module interface which hid global variables and low-level functions would be welcome. A database interface is another.
OO languages are inherently extensible. SIMULA, although it is often characterized as a simulation language, is actually an OO language which has been extended using its native facilities to support discrete event simulation [Meyer 88]. The same could be done for an OO-APL. Artificial intelligence is another area in which language extensibility could be exploited.
Conclusion¶
Subspaces are a simple and parsimonious way to introduce many useful extensions into APL; the most significant of which is to support a full object-oriented model. As experience with Smalltalk has shown, efficient and usable interpreters and environments can be implemented, and there is every reason to expect that an OO-extended APL or J could implemented even more efficiently.
APL is extremely powerful, but it is not particularly extensible and does not adequately support information hiding. These shortcomings can make it unnecessarily difficult to design, implement and manage medium to large systems. It is time we rectified these deficiencies.
Robert J. Frey, Ph.D
Renaissance Technologies Corporation
100 North Country Road
Setauket, NY 11733, U.S.A.
Bibliography¶
[Cox 87] Brad J. Cox, Object Oriented Programming: An Evolutionary Approach, Addison-Wesley Publishing Company, Reading, Massachusetts, 1987.
[Iverson 91] Kenneth E. Iverson, ISI Dictionary of J (Version 4), Iverson Software, Toronto, 1991.
[Meyer 88] Bertrand Meyer, Object-oriented Software Construction, Prentice-Hall, New York, 1988.
[Pinson 88] Lewis J. Pinson and Richard S. Wiener, An Introduction to Object Oriented Programming and Smalltalk, Addison-Wesley Publishing Company, Reading, Massachusetts, 1988.
[Stroustrup 86] Bjarne Stroustrup, The C++ Programming Language, Addison-Wesley Publishing Company, Reading, Massachusetts, 1986.