J, a derivative of APL, has arrays (which it calls “boxes”) as its only data structure. In this progress report, the authors propose to add trees as a specialization of arrays. After reviewing previous approaches, which introduced trees as a distinct data type, they proceed by defining facilities for the manipulation and display of trees represented as a subset of arrays. They list 54 functions (called “verbs” in J); for 10 of them, they present annotated J code. They also outline a modification of the J interpreter’s C source to incorporate the functions.
The goal of the paper is not clear. Is it a proposal to introduce tree verbs as primitives into J? For this, the number of functions is too large, and their interactions with the array primitives are not clearly described. Or should the tree facility be provided as a library? Then modification of the interpreter source does not make sense. This fuzzy goal is a symptom of one of J’s major problems: its lack of user-defined abstract data types (or objects). Tree facilities could be encapsulated as objects, for which the implementation could be supplied either in J itself or in C.
Given these language constraints, which the paper makes no mention of, the model of trees as a subset of arrays is still elegant. Therefore, I recommend the paper to those interested in and familiar with J or APL. The J code listings, however, are only readable by experienced J programmers.