From trees into boxes

Reviewer: Martin C. Gfeller

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,<__?__Pub Caret> 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.