Generic Read & Replace in IPSA

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 128

Introduction¶

This paper presents a simple design for numeric APL data bases. The design is quite general. Filing and retrieving from any such data base is handled by a very small module. The design is practical for applications which deal with several data bases.

Unfortunately, one cannot write about the APL file system but rather an APL file system. Files, or lack of, were an early divergence node for APL implementations. Each vendor has done it differently, and IBM has not done it at all. Allowing that a fair number of readers are only familiar with the IBM flavours of APL, we begin with a brief exposition of APL files. Since there is no standard, I’ll present the one that I’m most familiar with, the SHARP APL file system.

A primer on (SHARP) APL files¶

The great convenience of APL files is that one can work with them directly (no auxiliary processor) and programmatically (without system commands). The problem of data storage and shared access is thus brought within the APL environment. All the tools for working with the file system are present in every workspace as system functions.

While not all applications require files, nearly all business applications do. If several different workspaces deal with the same data base, there is a logistical problem of collecting (filing) and distributing (reading). One solution is to use )COPY and )SAVE, which is quite awkward to implement smoothly even if all users are from one account. IBM’s solution is to have non-APL programs perform the file I/O, and to employ shared variables and auxiliary processors to interface with APL. This isn’t at all a ‘bad’ solution, but it takes one out of the APL environment and requires expertise in the non-APL world.

The usefulness of APL files as a third alternative was apparent enough to vendors such as STSC, SHARP, XEROX, and DEC, all of whom had APL file systems in the early 70’s. Today nearly all except IBM have file systems. Some file systems closely resemble others, as SHARP’s resembles STSC’s, but no two are entirely alike.

The simplest way to describe an APL file is a place to store variables. Any variable in any workspace can be put anywhere on any file. File records are called file components. A file is a string of components. Each component has a file index (also called component number) which is used for direct access to the component.

For example, a file of sales data for 80 sales locations might be organized:

And each component of the file might be a matrix of unit sales figures for 54 products and 12 months.

Each APL account has a file library. Suppose that the sales data is in account 123’s library under the name ‘SALES’. To use the data base, one would share tie (open) the file and read (retrieve) from it. If we wanted the New York data for all products for the first three months:

'123 SALES' ⎕STIE 1
←(⎕READ 1 2)[;1 2 3]

Several files may be share tied at the same time. The right argument to quadSTIE established a distinct file tie number. The tie number is used to qualify which file to quadREAD from. The argument to quadREAD is tie number (1), file index (2). Most of the systems functions that pertain to files take tie numbers as one or part of one argument.

If there’s a new sales location to be added to the file from a variable, X, in the workspace,

X ⎕APPEND 1

would append it to the end of the file that’s tied to 1. If we have updated sales data for London in variable Y,

Y ⎕REPLACE 1 1

Would do the job. When we’re all done with ‘123 SALES’, we close it by

⎕UNTIE 1

There are some subtleties. If 1 was already in use as a tie number for a different file, a different tie number would have to be chosen. If ‘123 SALES’ was already open, we’d need to know by which tie number. These things matter but are not important enough to dwell on.

There are quite a few system functions involved, quadCREATE, quadSIZE, quadRDAC, quadERASE, quadDROP….. The one that we’re most concerned with is quadREAD for the moment.

The Design¶

‘123 SALES’ has 80 components, each 54 × 12. The file can be thought of as an 80 × 54 × 12 array, partitioned on the first dimension. That is the essence of the design. The problem is to relate a physical file structure to a logical view of it as a simple array.

If we think of the file as an 80 × 54 × 12 array, London would be the first plane, New York the second, and so forth. If we wanted to subscript the logical array, A, as follows:

A[2 4;5 6 7;1 2 3]

we would take

(⎕READ 1 2)[5 6 7;1 2 3]
(⎕READ 1 4)[5 6 7;1 2 3]

We could write the following program to handle any combination of components (planes), rows, and columns:

[1] ⎕UNTIE ⎕NUMS ⍝ CLOSE ALL FILES
[2] '123 SALES' ⎕STIE 1
[3] DATA←((⍴COMPONENTS),(⍴ROWS),⍴COLUMNS)⍴0
[4] I←1
[5] LOOP:DATA[I;;]←(⎕READ 1,COMPONENTS[I])[ROWS;COLUMNS]
[6] I←I+1
[7] →LOOP IF I≤⍴COMPONENTS
[8] ⎕UNTIE 1

Not too difficult. We can make ‘DATA’ the explicit result of the function and ‘I’ a local variable. We’re left with ‘COMPONENTS’ ‘ROWS’, and ‘COLUMNS’ to pass to the function as an argument. The most direct way is to pass them as a three element enclosed vector and unpack them within the function:

[.3] COMPONENTS←>ARGUMENT[1]
[.4] ROWS←>ARGUMENT[2]
[.5] COLUMNS←>ARGUMENT[3]

We might also make the file name the left argument of the function and rewrite [2] with the file name as the left argument of quadSTIE. We would then have a read function that would work on other files with the same structure as ‘123 SALES’.

While we have a more general program, we’re still restricted to matrix components and a simple file layout. Suppose, for example, that there were 6 years of data on ‘123 SALES’. The conceptual array would be 6 × 80 × 54 × 12, or some permutation thereof. We’d either have three-dimensional components or a two-dimensional file layout. Either way the program would no longer work. Our goal is to modify the program so that it will work regardless of the rank of the components or the rank of the file layout. In the next section we proceed toward this goal in two steps. We first modify the program to work regardless of the file layout, then to work regardless of component rank.

Generalization¶

Suppose again that there are 6 years of data on ‘123 SALES’, in sets of 80 components:

(The location columns are headed together “LOCATION”.)

This table shows the file index for each combination of year and location. If we were after 1981, 1982 for Paris, London we would read from components 164,161 (1981) and 244,241 (1982).

In the logical array, we are subscripting by rows 3, 4 and columns 4, 1.

Translation from logical subscripts to file indices is an application of base value. For example:

      1+6 80⊥2 3
164
      1+6 80⊥3 0
241

More generally,

FILEINDEX←1+FILELAYOUT⊥SUBSCRIPT-1

If the file layout is 6 80 and we want to find the file index for 1983, Madrid, we plug 5 3 into SUBSCRIPT and 6 80 into FILELAYOUT to get 323.

Let’s look at a revised program that would handle the hashing of file indices from logical subscripts:

[1] SUBSCRIPTS←>ARGUMENT[1]
[2] LAYOUT←>ARGUMENT[2]
[3] SHAPE←SHAPEOF SUBSCRIPTS
[4] COMPONENTS←LAYOUT HASH(⍴LAYOUT)↑SUBSCRIPTS
[5] SUBSCRIPTS←¯2↑SUBSCRIPTS
[6] ROWS←>SUBSCRIPTS[1]
[7] COLUMNS←>SUBSCRIPTS[2]
[8] ⎕UNTIE ⎕NUMS
[9] FILENAME ⎕STIE 1
[10] I←1
[11] DATA←((⍴COMPONENTS),(⍴ROWS),⍴COLUMNS)⍴0
[12] LOOP:DATA[I;;]←(⎕READ 1,COMPONENTS[I])[ROWS;COLUMNS]
[13] I←I+1
[14] →LOOP IF I≤⍴COMPONENTS
[15] DATA←SHAPE⍴DATA

We’re still assuming that all files have two-dimensional components, and that the filename is given as a left argument. There are 3 new twists. There is a subroutine, SHAPEOF, that tells us what the ultimate shape of the data ([15]) should be. ‘SUBSCRIPTS’ is an enclosed vector of subscripts for the logical array. SHAPEOF just returns the shape of each element of the enclosed vector.

On line [3] we store the shape, on line [15] we reshape. All that hash does is to calculate a vector of file indices for cells of the logical array. The base value algorithm is used as above. The remaining trick is to produce the right argument to base value, which is always a matrix with as many rows as elements in LAYOUT.

Each column of the matrix is a combination of indices for each file layout dimension.

For example, if the file layout is 6 × 80, years × locations, and we want years 2 and 3, locations 3,4 and 5, the matrix would have 2 rows (row 1 = years, row 2 = locations) and 6 columns. The columns would be, respectively, 2 3,2 4,2 5,3 3,3 4, and 3 5. Not coincidentally, the columns preserve row major order. The result of hash would be a six-element vector of file indices — 83 84 85 163 164 165.

The number of rows of the matrix is always equal to the shape of LAYOUT, and each row corresponds to a dimension of the file layout (years and locations in our example). The number of columns in the matrix is always equal to

×/(⍴LAYOUT)↑SHAPE

as defined in the program. Here is one way of writing the hash program.

    ∇ COMPONENTS←LAYOUT HASH SUBSCRIPTS
[1]   SUBSCRIPTS←CROSSCATENATE SUBSCRIPTS
[2]   COMPONENTS←1+LAYOUT⊥SUBSCRIPTS-1
    ∇

    ∇ NTUPLES←CROSSCATENATE VECTOR;SHAPE;RESHAPE;REPLICAS;INDEX;⎕IO
[1]   ⎕IO←1
[2]   SHAPE←SHAPEOF VECTOR
[3]   RESHAPE←×/SHAPE
[4]   NTUPLES←((⍴VECTOR),RESHAPE)⍴0
[5]   REPLICAS←⌽1,×\⌽1↓SHAPE
[6]   INDEX←1
[7]  LOOP:NTUPLES[INDEX;]←RESHAPE⍴REPLICAS[INDEX]/>VECTOR[INDEX]
[8]   INDEX←INDEX+1
[9]   →LOOP IF INDEX≤⍴VECTOR
    ∇

Perhaps I should have made some mention that the examples assumed quadIO of 1. In the Appendix is a full listing of the final program in origin independent form.

We now have a program that can work regardless of file layout, but is restricted to two-dimensional components. The generalization to components of arbitrary rank could be done in much the same way as file layout was, e.g.

[ ] LOOP:∆←⎕READ 1,COMPONENTS[I]
[ ] ∆←,∆
[ ] DATA[I;]←∆[SUBSCRIPTS]

With ‘SUBSCRIPTS’ derived appropriately. The program can now handle any rank file layout, and rank component.

The key principles are row major order and properties of reshape. The process is certainly easier to write with enclosed arrays. Usage of enclosed arrays needn’t be more than enclosing and disclosing to pass and unpack arguments. There are quite a few ways to write the program, depending on how much one wants to use enclosed arrays. The full listing here uses them minimally for the sake of simplicity. Any motivated APLer should be able to find bigger and better ways to do the same thing.

Practicality and extensions¶

There are two constraints posed by this design: all components must be identically shaped, and the program retrieves monolithically. If the logical array is sparse, the storage cost might not be worth it. If the idea is to return a single number as a function of each component, the program might pose workspace full problems by returning subsets of each component instead of single numbers.

The sparseness problem is rather black and white. Either it is or it isn’t. The latter problem can be dealt with by modifying the program. The code does not take up very much space. There could be several different versions of the program to handle different situations.

In practice I have found that the fundamental idea is robust enough that it can be extended in many different directions, some of which are:

1) Multiple-file data bases.

2) A ‘data origin’ parameter, as in

```
COMPONENTS←ORIGIN+LAYOUT⊥SUBSCRIPTS-⎕IO
```

This allows one to use the first (origin-1) component for things like dictionaries.

3) Filing of data, which is nothing more than a transposition of the left and right of the assignment.

4) Creating data bases.

5) Integrating file operations with macros.

It is not very hard to integrate the file I/O module with equally generic modules for dictionary maintenance and other data base chores. I have sort of followed my own nose in building a multiple-data base management system upon a file I/O module. The system is conversational and oriented somewhere between an application generator for programmers and a multiple data base spreadsheet (of sorts) for end users. To my surprise it has become popular with both, primarily because it reduces file I/O to a handful of simple parameters.

Appendix — Function Listings¶

    ∇ DATA←TIE RETRIEVE ARGUMENT;SUBSCRIPTS;LAYOUT;SPLIT;ORIGIN;SHAPE;COMPONENTS;STOP;INDEX
[1]    UNPACK
[2]   ⍝ INSTEAD OF PASSING THE FILE NAME, THE FILE IS ALREADY TIED
[3]   ⍝ AND THE FILE TIE NUMBER IS PASSED AS THE LEFT ARGUMENT
[4]   ⍝
[5]    SHAPE←SHAPEOF SUBSCRIPTS
[6]   ⍝
[7]    HASH
[8]   ⍝
[9]    STOP←⎕IO+⍴COMPONENTS
[10]   DATA←((⍴COMPONENTS),(⍴SUBSCRIPTS))⍴0
[11]   INDEX←⎕IO
[12]  LOOP:
[13]   DATA[INDEX;]←(,⎕READ TIE,COMPONENTS[INDEX])[SUBSCRIPTS]
[14]   INDEX←INDEX+1
[15]   →LOOP IF INDEX<STOP
[16]   DATA←SHAPE⍴DATA
    ∇

    ∇ UNPACK;⎕IO
[1]    ⎕IO←1
[2]    SUBSCRIPTS←>ARGUMENT[1] ⍝ AS BEFORE
[3]    LAYOUT←>ARGUMENT[2] ⍝ EXTENDED TO INCLUDE COMPONENT SHAPE
[4]    SPLIT←>ARGUMENT[3] ⍝ THE RANK OF THE FILE LAYOUT
[5]    ORIGIN←>ARGUMENT[4] ⍝ FILE INDEX ORIGIN FOR DATA
[6]   ⍝
[7]   ⍝ IN TERMS OF THE EXAMPLE, <LAYOUT> WOULD BE 6 80 54 12.
[8]   ⍝ <SPLIT> WOULD BE 2 (FILE LAYOUT OF 6 80).
[9]   ⍝ AND <ORIGIN> WOULD BE 1 (FIRST FILE INDEX FOR DATA).
    ∇

    ∇ HASH
[1]   ⍝
[2]    COMPONENTS←ORIGIN+(SPLIT↑LAYOUT)⊥(CROSSCATENATE SPLIT↑SUBSCRIPTS)-⎕IO
[3]   ⍝
[4]    SUBSCRIPTS←⎕IO+(SPLIT↓LAYOUT)⊥(CROSSCATENATE SPLIT↓SUBSCRIPTS)-⎕IO
[5]   ⍝
    ∇

    ∇ TUPLES←CROSSCATENATE VECTOR;SHAPE;RESHAPE;REPLICAS;INDEX;⎕IO
[1]   ⍝ JUST SOME SIMPLE REPLICATION
[2]    ⎕IO←1
[3]    SHAPE←SHAPEOF,¨>VECTOR
[4]    RESHAPE←×/SHAPE
[5]    TUPLES←((⍴VECTOR),RESHAPE)⍴0
[6]    REPLICAS←⌽1,×\⌽1↓SHAPE
[7]    INDEX←1
[8]   LOOP:TUPLES[INDEX;]←RESHAPE⍴REPLICAS[INDEX]/>VECTOR[INDEX]
[9]    INDEX←INDEX+1
[10]   →(INDEX≤⍴VECTOR)/LOOP
    ∇

    ∇ SHAPE←SHAPEOF VECTOR
[1]   ⍝ RETURNS THE LENGTH OF EACH ELEMENT OF A VECTOR OF VECTORS
[2]    SHAPE←,>1↑¨>⍴¨>VECTOR
[3]    SHAPE←(SHAPE≠0)/SHAPE ⍝ COMPRESS OUT DEGENERATE CASES
    ∇

    ∇ R←L IF C
[1]    R←C/L
    ∇