Data Conversion Between APL Versions

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

Many APLers will have had some experience of transferring objects between different versions of APL. The usual technique for user-defined functions (and operators if these are supported) is to transfer the canonical representations (⎕CR forms). For variables, I have seen various approaches used. One method is to include a header with each variable that identifies its name, data type, rank and shape, followed by the ravelled data as though typed in. At the receiving end, the data part may then be executed (with quotes placed around character variables), re-shaped, and assigned to its name. A similar method re-constitutes each variable from an executable string including the name assignment and re-shape expressions. A nested array using this approach can look very complex! In addition, the transferred characters must be converted from one character set to the other if the internal representations of the atomic vectors (⎕AVs) of the two versions of APL differ, which they usually do.

These methods are not very efficient. The processing at each end is quite significant, but more importantly, the amount of data to be transferred for a variable is considerably larger than the space the variable actually consumes in the workspace. For infrequent transfers, this may not matter. However, for regular transfers through a network with constant interaction between remote systems, the priorities change somewhat. Both elapsed time and network transfer volumes must be kept to a balanced minimum.

Table 1 indicates the maximum size overhead per element for each data type if a simplistic transfer technique is employed. For booleans and numerics to be re-assembled by execution, a space character is required between elements, and the requisite number of digits and other paraphernalia must be represented in order to retain accuracy.

† Some APLs also support 1 and 2 byte Integers

Table 1: Maximum element sizes using string execution

Of course, the maximum sizes will often not be required. Integers will realistically require far less than the theoretical 10 digits plus sign and separating space. Trailing zeros can be omitted from floating point numbers. But in most cases, and always for booleans, there is a big overhead compared with workspace storage size. This is especially the case for floating point numbers, which comprise most business data.

Another Approach¶

The idea occurred to me some time ago that a good way of transferring data between APLs might be to convert to one or other of the internal data structures used by the different APL versions. After all, the data storage methods of modern APLs are a reasonably efficient compromise between storage space versus processing costs when functions are applied.

The 8-bit byte is the usual base unit for transport protocols, whether it be TCP/IP, or a file-to-file protocol such as IBM’s IND$FILE facility, or whatever. For a binary transfer, all 256 bit combinations of a byte may be used. Thus, a Real (Floating Point) number that is represented in the workspace by 8 bytes may also be transferred using 8 consecutive bytes. The same applies for other data types, but for Boolean arrays, padding may be required to extend the single bits defining the data up to a byte boundary. We can think of the byte representation of data as a text string, although the text if printed would appear as gibberish. How to convert to and from text string form, and between the representations of those data structures in the different versions of APL, is the principal subject of this article.

A further factor that induced me to experiment with this approach is the availability of a function in some APLs to convert a variable from one data type to another. I believe this concept was first introduced on mainframe APL*PLUS as a "fast function" called CHTYPE (for Change Type). This subsequently became available for the PC version of APL*PLUS (now known as APL+Win) as the ⎕DR system function (for Data Representation), and later in Dyalog APL version 8. The dyadic form of ⎕DR converts the array given as its right argument to the form indicated by a numeric code (or codes) specified by its left argument, providing that the conversion is feasible (otherwise DOMAIN ERROR is reported). In fact, this simply involves altering the data type and shape of the array. For example,

82 ⎕DR REALNRS

converts each item of Real array REALNRS to 8 characters defined by the bit patterns of the consecutive sets of 8 bytes that comprise a Real number; 82 is the code that says convert to a Character array. If REALNRS were a 1-column matrix, the result would be an 8-column Character array. To convert from Character to Real, the length of the last axis must be a multiple of 8, unless the array is an empty vector. The combined bit pattern must also be a valid Real representation (not all bit patterns are). The monadic usage of ⎕DR returns the data type code for a given array, e.g. 82 for a Character array.

This system function or the CHTYPE equivalent is extremely quick, providing the basis for fast algorithms to perform the conversions for the transport process and re-constitution in the receiving workspace. Although the conversions could easily be achieved using native APL functions with quite acceptable performance, the important advantage of rapid conversion at one end of the process is lost.

Development Platforms¶

For the purpose of concrete example, the article will describe the approach based on the actual platforms for which it was developed, although the same approach could be applied between any APL versions using whatever transport protocol is available.

Specifically, transfer of data is required in both directions between applications running under Dyalog APL/W Version 8 on PCs (the clients), and an IBM mainframe running APL*PLUS under CP/CMS (the server). The transport protocol uses IBM’s IND$FILE facility which sends data via a CMS file and a DOS file, to be picked up by the client/server as appropriate. These processes are controlled interactively by APL programs at each end without direct user intervention. However, the transport procedures are not of concern for this article; therein lies another tale. The applications involve frequent interactions between client and server, with sometimes quite large data transfers (up to perhaps 2 Megabytes of workspace storage), mainly from server to client. The critical criterion for a transfer process is the elapsed time that a transfer takes. This is affected by the processing times at each end to perform the conversions, the actual transmission time of the transfer, and the messaging and synchronisation protocols that are required. The described approach impacts on the first two of these.

Data Representations¶

The way in which arrays are stored in the workspace is dependent on the APL vendor, although they will be influenced by the hardware platform for which the version is designed and by convention amongst implementers.

For Intel-based PCs, covering 80386, 80486 and Pentium processors, the storage of numeric data is likely to conform to the IEEE standards, since these are fully supported at the micro-code level. Another standard is that for IBM 360/370 machines. These standards are reviewed below.

By convention, all simple APL arrays are defined by a header followed by a data part. The word "tupple" has been coined (tuppence!) to describe this two-part string. It is not a word in the dictionary that I have found, but if Lewis Carroll can invent words, why not?

Taking Dyalog APL as an example, the header contains the following:

The data part contains elements in ravelled order, padded at the end if necessary to align to a 4-byte boundary. If the array is nested (and perhaps if it is heterogeneous, though Apl+Win handles this in a single tupple), each nesting structure is identified as a "pointer" type, and its data part is a set of pointers to other tupples. A nested array is therefore a linked set of tupples. At the end of each path through the structure, there may be several pointer tupples, but ultimately it must end with a tupple for a simple array.

For transfer purposes, exactly how the header part is identified is not important, although the information is required to reconstruct the array correctly. However, APL will look after the header during this process, e.g. when ⎕DR is used to convert the data, and the shape information is used to re-shape the array. I use a similar construct to the above as follows:

Note that for transfer, the base unit size is a byte, as opposed to a 4-byte word in the workspace, so there is no need to pad the header. The Compression Method indicates how the transferred array has been compressed, if at all, to be discussed later.

The conversion process is applied to the data part of the array, which is always a ravelled vector. There are, in fact, two aspects to the conversion, although the actual processes will sensibly be consolidated:

• conversion, if necessary, because the data representation in the workspace differs between the APL versions;
• conversion of this representation to text string form for the transfer.

If there are data representation differences, the conversions both to and from the form required for the other should be undertaken on the same platform, normally where it can be done most quickly. Also, since different code must be developed for the two versions, to, say, convert Real numbers, it is much more reliable and easier for testing to have pack/unpack functions that are reversible. Applying the packing function to an array and then applying the unpack function to its result, i.e. the transfer form, should provide the original array within precision limits. It also means that on the other, presumably slower, platform, the data conversion process is much simpler, and almost trivial if a facility like ⎕DR is available.

For the discussion case, the mainframe APL*PLUS server takes the brunt of the processing task, leaving the Dyalog APL client with a rapid, re-assembly task. The remaining sections discuss conversion issues relating to these specific platforms, although the underlying logical processes may be extrapolated to other platform combinations.

Translation of Binary Data¶

The strategy described here relies on generating the exact bit patterns, represented as bytes for transfer, that will reproduce the data part exactly in one of the APLs (in this case, Dyalog APL). It is therefore very important that the transport protocol passes the data without translation. There are usually options that allow for automatic translation when writing to or reading from a transfer file. The option must be disabled, set to "No Translation".

Specifically for Dyalog APL, writing to and reading from native files, i.e. DOS files, assumes a default translation. The file must be set to "No Translation" by the statement:

((⍳256)-⎕IO)⎕NXLATE tn      ⍝ where tn is the negative file tie number.

Equally important, a similar setting must be made for ⎕DR, otherwise a conversion will be made in converting to and from the byte strings, thus:

((⍳256)-⎕IO)⎕NXLATE 0

Conversion of Character Arrays¶

A re-mapping of characters is required if the ⎕AVs of the respective APLs do not match either in the characters that they represent, or in the bit patterns that describe each character. Neither condition is met in the discussion case.

The re-mapping is achieved by defining a 256-element Character vector in the APL*PLUS workspace in which each element identifies an APL*PLUS character whose position in the vector has the bit pattern that matches the equivalent character in Dyalog APL. The equivalent bit pattern for a given position number is (8⍴2)⊤number. Beware that this position may not be the subscript of the character in Dyalog APL’s ⎕AV. For example, the letter ‘a’ has origin-0 position 38 in APL*PLUS’s ⎕AV; in Dyalog APL, its bit pattern translates to 97 whereas its subscript in ⎕AV is 17. ‘a’ needs to be mapped to the position in the translation vector that has the bit pattern equivalent to 97. As it happens, this is also position 97, since the bit patterns in APL*PLUS’s ⎕AV progress consecutively from 0 to 255, but it must be verified. Characters with no equivalent are mapped arbitrarily to bit pattern 255. In most business uses, this should not occur in practice, but for function transfers, it needs to be handled in some way.

Thus, at the APL*PLUS end, Character data is translated for transfer as follows:

At the Dyalog APL end, no translation is required, either outgoing or incoming.

This is the sole case in which translation is required for ⎕AV differences, in contrast to the string execution approach when all transfers require this translation.

Conversion of Boolean Arrays¶

Both APL*PLUS and Dyalog APL store Boolean data in the same way. For outgoing transfer, the vector must first be extended up to a byte boundary:

shape←⍴bool ⋄ bool←,bool
bool←8×⌈(⍴bool)÷8)↑bool

Recording the shape and ravelling of the object are assumed for all further examples.

Both versions support data type conversion functions, which may therefore be used for rapid conversion to/from text string form:

Conversion of Integer Arrays¶

Both APL*PLUS and Dyalog APL store 4-byte Integer data in a similar, though not identical, way. Dyalog APL also supports 1-byte and 2-byte Integers if each element n of the array is respectively in the range ¯128≤n≤127 or 32767≤n≤32768. It is worthwhile taking advantage of this space optimisation.

In principle, the first bit of the internal storage form of an Integer indicates the sign of the number and the remaining bits identify the value. In Dyalog APL, there may be 7, 15 or 31 value bits, whereas in APL*PLUS there are 31.

For a positive number, with a sign bit of 0, the expression 2⊥value_bits gives the numerical value.

For a negative number, with a sign bit of 1, a form known as "twos-complement" is used. Here, the value bits are reversed, and the expression -1+2⊥~value_bits gives the numerical value.

Intel-based machines, on which the Windows version of Dyalog APL is installed, have a further twist. All numeric values that take more than one byte are stored in reverse byte order. For example, the number 1234 is stored as a 2-byte Integer which conceptually may be thought of as:

0 0 0 0 0 1 0 0   1 1 0 1 0 0 1 0
↑     1st byte        2nd byte
sign bit

but is actually stored as:

1 1 0 1 0 0 1 0   0 0 0 0 0 1 0 0
    2nd byte      ↑     1st byte
                  sign bit

This is sometimes known as a "low-endian", as opposed to a "high-endian", method of storage. The same principle also applies to the storage of Real numbers.

At the APL*PLUS end, for fast conversion:

⍝ Outgoing:
S←S+3=S←+/1,(127 32767<⌈/int)∨¯128 ¯32768>⌊/int
str←,⌽(¯2 F 3 2 0[1 2 4⍳S])↑'CI'CHTYPE((⍴int),1)⍴int

⍝ Incoming:
T←'BC'CHTYPE⌽(⌽S,⌈(⍴str)÷S)⍴str
int←'IB'CHTYPE ((1+8×3 2 0[1 2 4⍳S])/T[;,⎕IO]),0 1↓T
int←shape⍴int

At the Dyalog APL end:

⍝ Outgoing:
str←82 ⎕DR int
⍝ Incoming:
int←83 163 323[1 2 4⍳S]⎕DR str

Conversion of Real (or Floating Point) Arrays¶

A Real number is an abstract mathematical concept. Its value may lie in the range between +∞ (plus infinity) and -∞, and between any two Real numbers there lie an infinite number of Real numbers. Any digital representation of a Real number is therefore usually an approximation. Strictly speaking, a Floating Point number is an approximation of a Real number, though the terms are often used as though synonymous. We normally work using decimal values. A binary representation of a decimal value again is usually not exact, so rounding is required when a conversion is made from decimal to binary and vice versa. Also, even if numbers are represented in binary form, there are varying methods of storage, and again rounding may be required when numbers are converted from one platform to another.

A Floating Point number is stored in three parts, being its sign, an exponent and a mantissa. The mantissa identifies a number of significant digits up to the limit of the storage method. The exponent is a power to which a base value will be raised. The represented number is conceptually calculated from:

(¯1*sign) × mantissa × base*exponent

For computer storage, the first (logical) bit represents the sign (0 for positive, 1 for negative), followed by a number of bits that represent the exponent, and the remaining bits in the allocated storage size represents the mantissa. Normally, the base is 2, but the IBM 360/370 convention has a base of 16.

In order to give the exponent a range from negative to positive without using an explicit sign bit, a bias is added to the actual exponent for storage, normally at the centre of the range.

To make comparison and arithmetic simpler, the mantissa is normalised. With a base 2 exponent, this means that the bits in the mantissa are shifted such that the left-most bit (i.e. the most significant bit) is a 1.

Consider an example with decimal numbers. There are many ways of representing the value 10.34 using scientific E notation, such as 1034E-2, 0.01034E3, 10.34E0 etc. The normalised form is 1.034E1. That is, the decimal is shifted so that just one non-zero figure occurs to its left. The number of places to shift is ⌊10⍟number and this becomes the exponent value.

In storage form, the adjustment is slightly more complicated as we have to consider the precision, i.e. the maximum number of digits that can be stored. Let us consider this number 10.34 represented in base-10, a 2-digit exponent with a bias of 50, and 6 digits of precision in the mantissa:

• The mantissa takes the number 103400 (i.e. 6 digits)
• Its normalised value is 1.03400, i.e. 103400÷10*5 (1 digit before the decimal)
• The mantissa calculation is ⌊0.5+10.34×10*(5-⌊10⍟10.34)
• The corresponding exponent, before applying bias, must then be ⌊10⍟10.34, i.e. 1
• The biased exponent is 50+1, i.e. 51
• The sign is 0 for positive (it would be 1 for negative)
• The number would be represented in sign-exponent-mantissa notation (spaces shown for clarity) as 0 51 103400

The same principle is applied to the digital representation. Table 2 identifies pertinent characteristics for IEEE and IBM 360/370 Standards for 8 byte Real numbers.

Table 2: Standards for 8-byte Real Numbers

For IEEE representation, a little trick is applied to the mantissa. Although 52 bits are stored, since the normalised form adjusts the mantissa such that there is a 1 in its leftmost bit, it can be assumed. This is known as the implicit bit. It effectively gives 53 bits of precision. This trick cannot be pulled off for the IBM 360/370 standard, because the exponent base is 16, i.e. 2⁴. The condition for a normalised number is therefore that there must be a 1 in any of the first 4 bits, as shift adjustments may only be made in powers of 16.

As previously mentioned, Intel storage is low-endian whereas IBM 360/370 storage is high-endian. The 8-bytes of an Intel Real number must be rotated to place the bits in notional order for the sign-exponent-mantissa convention.

Zero is considered to be a special case for the IEEE standard. This is because of the implicit bit, so an exponent of 0 is reserved and outside the range for normalised numbers. Actually, the standard supports positive and negative zero, and so does Dyalog APL from a translated bit pattern. The conversion algorithms must treat zeros separately, mainly to avoid DOMAIN ERROR when taking the logarithm.

The standard also uses a 0 exponent to handle sub-normal numbers. These are numbers between 0 and the smallest absolute number that can be represented as a normal number. The calculation for a sub-normal number is:

(¯1*s) × (2*¯1022) × (2⊥m)÷2*52

This extension provides for "gradual underflow", important in high-precision calculations when, for example, two small numbers are subtracted. Sub-normal numbers are supported by Dyalog APL, but not by APL*PLUS on the mainframe (where the result from underflow is 0).

The IEEE standard also makes use of the highest exponent value 2047 for special purposes, but these are not supported by Dyalog APL. Out of interest, if the mantissa is 0, this signifies ∞, either + or - depending on the sign bit. Any other mantissa value is termed NaN (for Not a Number). Dyalog APL reports a DOMAIN ERROR for these cases, so it is not a good idea to translate arbitrary bit strings.

Another point to notice when converting is that the largest absolute number that can be represented is very much greater in Dyalog APL than in mainframe APL*PLUS. It is therefore necessary to prevent a calculation when converting from Dyalog APL to APL*PLUS that would exceed this number otherwise DOMAIN ERROR raises its head again.

Because Real number conversion is the most complex of the conversions, and most critical in terms of processing costs, three different variants are presented in order to discuss the problems that occurred during its evolution to the final version. Each function handles the packing and unpacking tasks in the mainframe APL*PLUS workspace, converting from IBM360 form to IEEE form. I have excluded full header comments from the first two but not the last to reduce space.

The task at the Dyalog APL end is trivial, amounting to:

This is the first mainframe APL*PLUS variant. I have marked the lines that differ by the bar character against the comments.

    ∇ R←A PKREAL1 B;⎕CT;E;I;M;S;Z
[1]   ⍝∇ Pack/Unpack Real numbers...Mainframe APL*PLUS version
[2]   ⍝  Variant 1: uses ⊥ and ⊤
[3]
[4]    ⎕CT←0 ⋄ →A↑L1
[5]   ⍝ Pack object from IBM360 form to Intel IEEE form
[6]    R←(Z←R≠0)/R←,B ⍝                  compress zeros
[7]    S←R<0 ⋄ R←|R ⍝                    extract sign, make +ve
[8]    R←⌊0.5+R×2*52-E←⌊2⍟R ⍝            | normalised mantissa
[9]    E←E+1023 ⍝                        | add bias
[10]   R←⍉1=(52⍴2)⊤R ⍝                   | mantissa bits
[11]   E←⍉1=(11⍴2)⊤E ⍝                   | exponent bits
[12]   R←S,E,R ⋄ S←E←0 ⍝                 put together with sign bit
[13]   R←⌽'CB'CHTYPE R ⍝                 character equivs, 8 per Real
[14]   R←Z⍀R ⋄ R[(~Z)/⍳⍴Z;]←⊃⎕AV ⋄ R←,R ⍝ expand to restore zeros
[15]   →EXIT
[16]
[17]  ⍝ Unpack object from Intel IEEE form to IBM360 form
[18]  L1:R←⌽((⌊(+/⊃⍴R)÷8),8)⍴R←,B ⍝     group by Real nr
[19]   R←'BC'CHTYPE R ⍝                  convert to bits
[20]   I←∨/0 1↓R ⍝                       note zeros
[21]   R←⍉R ⍝                            | transpose now
[22]   S←R[1;] ⋄ E←1 0↓¯52 0↓R ⋄ R←12 0↓R ⍝| sign, expont,mantissa
[23]   E←¯1023+2⊥E ⍝                     | base 2 exponent
[24]   E←E×~M←E>251 ⍝                    | adjust if maximum number exceeded
[25]   R←1+(2⊥R)×2*¯52 ⍝                 | value represented by mantissa
[26]   R←I×R×2*E ⋄ E←I←0 ⍝               | non-zero × mantissa × 2* exponent
[27]   →(1∊M)↓L2 ⋄ R[M/⍳⍴M]←⌊/⍳0 ⍝       maximum nr adjustments
[28]  L2:→(1∊S)↓EXIT ⋄ R[S/⍳⍴S]←-S/R ⍝   apply sign
[29]
[30]  EXIT:
    ∇

This variant works on the Real values themselves, performing the arithmatic to work out the mantissa and exponent values for the IEEE representation. It does not explicitly use any of the parameters for IBM 360/370 format, although certain relationships are implied. Firstly, in line [8], the normalised mantissa is generated. This requires an exact integral representation to work, but as just 53 bits are required for this calculation, whereas an IBM360 Real number allows 56, there is no problem.

Also, since the largest absolute number and the smallest absolute numbers are well within the range supported by IEEE, there is no need to check for these conditions. This is not the case when unpacking IEEE numbers. A check must be made to ensure that the largest number is not exceeded before re-calculating from the mantissa and exponent (otherwise a DOMAIN ERROR will occur); in this case, the algorithm sets the unsigned value to ⌊/⍳0, i.e. the largest representable number. However, there is no need to check for underflow, as APL*PLUS simply sets the number to 0.

Some precision may be lost in the conversion as the IBM360 standard has up to 3 extra bits representing the mantissa. (Recall IEEE’s implicit bit, and the fact that there may be up to three leading 0 bits in the IBM 360/370 mantissa).

Notice that the CHTYPE fast function is used only to convert from Boolean to Character form, and vice versa.

Although the most straightforward of the variants, it suffers from a considerable drawback. This is caused by the way the Encode function works (the one with the bar on top ⊤ - hands up all those who have to try it out at the desktop), and it may well be common to all versions of APL; certainly it is to those I am using. Lines [10-11] perform an encode to convert the integral representations, but actually Real numbers, to Boolean with an encoding base of 2’s. The result of this function has the same type as its right argument. Thus, until forced Boolean, but too late, the temporary result to obtain the mantissa bits amounts to 416 bytes per item. With 10,000 Real numbers, that would require 4,160,000 bytes. The algorithm needs to handle 100,000 Real numbers in about 4 Megabytes of free workspace. Amen to that idea.

The second variant follows another approach:

    ∇ R←A PKREAL2 B;⎕CT;E;I;L;M;S;U;Z
[1]   ⍝∇ Pack/Unpack Real numbers...Mainframe APL*PLUS version
[2]   ⍝ Variant 2: Conversion by bit manipulation
[3]
[4]    ⎕CT←0 ⋄ →A↑L1
[5]   ⍝ Pack object from IBM360 form to Intel IEEE form
[6]    R←(Z←R≠0)/R←,B ⍝                  compress zeros
[7]    S←R<0 ⋄ R←|R ⍝                    extract sign, make +ve
[8]    R←'BR'CHTYPE((⍴R),1)⍴R ⍝          | convert to real to boolean
[9]    S←R[;1] ⋄ E←0 1↓0 ¯56↓R ⋄ R←0 8↓R ⍝| sign,exponent,mantissa
[10]   L←+/∧\0=((⊃⍴R),3)↑R ⍝             | rotate to place 1 in leftmost posn
[11]   E←4ׯ64+2⊥⍉E ⍝                    | IBM360 exponent
[12]   E←⍉1=(11⍴2)⊤E+1023-L ⍝            | IEEE exponent
[13]   R←0 ¯4↓(L+1)⌽R ⍝                  | rotate inc 1st bit/keep 52 bits
[14]   R←S,E,R ⋄ S←E←L←0 ⍝               put together with sign bit
[15]   R←⌽'CB'CHTYPE R ⍝                 character equivs, 8 per Real
[16]   R←Z⍀R ⋄ R[(~Z)/⍳⍴Z;]←⎕AV[1] ⋄ R←,R ⍝ expand to restore zeros
[17]   →EXIT
[18]
[19]  ⍝ Unpack object from Intel IEEE form to IBM360 form
[20]  L1:R←⌽((⌊(+/⊃⍴R)÷8),8)⍴R←,B ⍝     group by Real nr
[21]   R←'BC'CHTYPE R ⍝                  convert to bits
[22]   I←∨/0 1↓R ⍝                       note zeros
[23]   S←R[;1] ⋄ E←0 1↓0 ¯52↓R ⋄ R←0 12↓R ⍝| sign, expont,mantissa
[24]   E←¯1023+2⊥⍉E ⍝                    | IEEE exponent
[25]   E←64+⌊E←(E←E-L←-4|E)÷4 ⍝          | IBM360 exponent to base 16
[26]   M←E>127 ⋄ U←E<0 ⍝                 | >maximum number/Underflow ?
[27]   E←⍉1=(7⍴2)⊤E×~M∨U ⍝               | exponent bit pattern
[28]   R←L⌽((⊃⍴R),56)↑(1=1),R ⍝          | extend mantissa inc implicit bit
[29]   R←S,E,R ⋄ S←E←0 ⍝                 | put together, 64 bits/real
[30]   R←,'RB'CHTYPE R ⍝                 | convert boolean to real
[31]   →(1∊U)↓L2 ⋄ R[U/⍳⍴U]←0 ⍝          | underflow adjustments
[32]  L2:→(1∊M)↓L3 ⋄ R[M/⍳⍴M]←⌊/⍳0 ⍝     maximum nr adjustments
[33]  L3:→(1∊S)↓EXIT ⋄ R[S/⍳⍴S]←-S/R ⍝   apply sign
[34]
[35]  EXIT:
    ∇

In this version, the conversion process is done by bit manipulation, an intellectually appealing approach. Boolean solutions to problems are well-understood by APLers, often providing new insights, and performing very highly.

Firstly, the bit representation of the Real numbers is obtained using CHTYPE, and the sign, exponent, and mantissa matrices are extracted.

The IBM360 mantissa has up to three leading 0-bits, so these are counted, L say. The mantissa matrix is then rotated by (L+1) bytes, to also include the first 1-bit, and the last 4 bytes are then dropped. This leaves a 52-bit mantissa, the IEEE form with the first bit being an implicit 1.

The exponent is complicated by the bias, so it is enumerated, bias-adjusted and multiplied by 4. Adding the IEEE bias of 1023 almost gets us there. It is also necessary to compensate for the mantissa rotation by deducting L, since the rotation is equivalent to mutiplying the mantissa by 2*L. The revised exponents are then converted back to binary equivalents.

Finally, the sign, exponent and mantissa matrices are joined together, giving the logical IEEE representation. Convert to byte form, rotate, and there we have the transport form, ready for instant conversion in Dyalog APL.

The unpacking process is almost the reverse process, except that checks must be made both for numbers exceeding the maximum absolute value and for underflow. This is done by checking the IBM 360/370 exponent values before conversion to binary, which must be in the range 0 to 127. Exponents outside this range are arbitrarily set to 0, and then the recomposed Real numbers are adjusted later.

This algorithm works quite well. It is fast. It will handle 50,000 Real numbers with 4 Megabytes of free workspace, but it runs out of steam before reaching 100,000 numbers, predictably giving WS FULL on line [10] when packing, and on line [27] when unpacking

The third, and final, variant, which I have left fully-commented, is:

    ∇ R←A PKREAL3 B;⎕CT;E;I;M;S;Z
[1]   ⍝∇ Pack/Unpack Real numbers...Mainframe APL*PLUS version
[2]   ⍝ Variant 3: Avoids ⊥ and ⊤, alternate code using CHTYPE
[3]   ⍝ A ↔ LS  0:pack, 1:unpack
[4]   ⍝ B ↔ VIV A=0 Pick element to read/replace in global
[5]   ⍝ B ↔ TV  A=1 Text string to be re-constituted
[6]   ⍝ R ↔ A   A=1 Re-composed Real object
[7]
[8]   ⍝  Character form of Real vector B converted from IBM360 form
[9]   ⍝  to IEEE storage form
[10]  ⍝               IBM360 form                IEEE form
[11]  ⍝               (¯1*s)×(2⊥m)×16*(2⊥e)-64   (¯1*s)×(2⊥m)×2*(2⊥e)-1023
[12]  ⍝  s:sign bit   63      (1)                63      (1)
[13]  ⍝  m:mantissa   62-56   (7)                62-52   (11)
[14]  ⍝  e:exponent   55-0    (56)               51-0    (52+1 implicit bit)
[15]  ⍝  Order        As described               Intel storage, i.e.
[16]  ⍝                                          8 storage bytes reversed
[17]   ⎕CT←0 ⋄ →A↑L1
[18]  ⍝ Pack object from IBM360 form to Intel IEEE form
[19]   R←(Z←R≠0)/R←,B ⍝                  compress zeros
[20]   S←R<0 ⋄ R←|R ⍝                    extract sign, make +ve
[21]   R←⌊0.5+R×2*52-E←⌊2⍟R ⍝            | normalised mantissa
[22]   E←E+1023 ⍝                        | add bias
[23]   R←(2⍴2*26)⊤R ⍝                    | mantissa as 2 integers
[24]   R←⍉R←⌊R ⍝                         | force Integer
[25]   R←((⍴E),52)⍴0 6↓'BI'CHTYPE((2×⍴E),1)⍴R ⍝| mantissa bits
[26]   E←0 21↓'BI'CHTYPE((⍴E),1)⍴E ⍝     | exponent bits
[27]   R←S,E,R ⋄ S←E←0 ⍝                 put together with sign bit
[28]   R←⌽'CB'CHTYPE R ⍝                 character equivs, 8 per Real
[29]   R←Z⍀R ⋄ R[(~Z)/⍳⍴Z;]←⎕AV[1] ⋄ R←,R ⍝ expand to restore zeros
[30]   →EXIT
[31]
[32]  ⍝ Unpack object from Intel IEEE form to IBM360 form
[33]  L1:R←⌽((⌊(+/⊃⍴R)÷8),8)⍴R←,B ⍝     group by Real nr
[34]   R←'BC'CHTYPE R ⍝                  convert to bits
[35]   I←∨/0 1↓R ⍝                       note zeros
[36]   S←R[;1] ⋄ E←0 1↓0 ¯52↓R ⋄ R←0 12↓R ⍝| sign, expont,mantissa
[37]   R←((2×⍴S),26)⍴R ⍝                 | split bits
[38]   R←((⊃⍴R),¯32)↑R ⍝                 | adjust bits as 2 integers
[39]   R←⍉((⍴S),2)⍴'IB'CHTYPE R ⍝        | convert to Integers
[40]   R←(2*26)⊥R ⍝                      | convert to mantissa values
[41]   R←1+R×2*¯52 ⍝                     | decimal mantissa
[42]   E←¯1023+,'IB'CHTYPE((⍴S),¯32)↑E ⍝ | exponent to Integer, less bias
[43]   E←E×~M←E>251 ⍝                    | adjust if maximum nr exceeded
[44]   R←I×R×2*E ⋄ E←I←0 ⍝               | non-zero × mantissa × 2* exponent
[45]   →(1∊M)↓L2 ⋄ R[M/⍳⍴M]←⌊/⍳0 ⍝       maximum nr adjustments
[46]  L2:→(1∊S)↓EXIT ⋄ R[S/⍳⍴S]←-S/R ⍝   apply sign
[47]
[48]  EXIT:
    ∇

This, in fact, is a speeded-up version of the first variant. Use of Encode and Decode is reduced by making use of CHTYPE, and also build-up of temporary storage is avoided by continuous re-assignment. For example, in line [24] R←⍉R←⌊R, if the middle assignment were to be omitted, there would be the temporary storage of the intermediate result of ⌊R whilst the transpose took place. Care is taken to make lines restartable.

Lines [23-25] obtain the same functional result as line [10] R←⍉1=(52⍴2)⊤R of the first variant. The technique is to encode a mantissa number (integral, but Real) into two Integers, temporarily returned as Real numbers and doubling the space taken until the Floor is applied, but somewhat better than 52 Real numbers that resul tin the first variant. What we actually need is the lowest 52 bits of the 53 bits that fully define the number. The implicit bit is not required. So the encoding base is 2⍴2*26. Using the CHTYPE function, the conversion of each Integer to binary form is extremely rapid with no workspace overload. Drop off the first 6 bytes of each representation, join the 26 bits for consecutive pairs of Integers, and the result is the mantissa that is required.

A similar technique is used for the exponent, but here just a single Integer is sufficient, of which the last 11 bits are what is required.

The same techniques are used in reverse for the unpacking process.

This variant will handle 100,000 Real numbers, and is always faster than the other methods.

Table 3 below summarises timing tests. These were actually done under Dyalog APL v 8.1 where the prototypes were developed, simulating CHTYPE, so an adjustment has been made for the extra overhead by comparison with the time ⎕DR takes for a similar conversion. The PC was a 266MHz Pentium II with 64 MB RAM. The available workspace allowed for each evaluation was 4 Megabytes. Where WS FULL is indicated, the function line of the variant where it occurred is noted.

The actual time for the full 100,000 number test under mainframe APL*PLUS is about 2 seconds, which makes the PC results look impressive. In fact, the PCs in the target working environment are rated at lower clock speeds.

Table 2: Timing tests showing Variants v. Number of Reals

It is clear that variant 3 not only has greater capacity but is significantly faster. Although, variant 2 could be made faster using similar techniques, investigation of time tests on individual lines suggests that the binary algorithm is not as fast per se.

Nested Arrays¶

The functions PACK and UNPACK below illustrate a technique for putting together the transfer string, and re-constructing the original structure when dealing with a nested array.

The PACK function takes the object to be converted. In fact, this is not a good idea, but I shall come back to that. As you will notice, this function is recursive.

    ∇ R←PACK X;J
[1]   ⍝∇ Pack array X
[2]    →LC LB LI LR LH LP['CBIRHN'⍳DTYPE X]
[3]   LC:R←0 PKCHAR X ⋄ →EXIT
[4]   LB:R←0 PKBOOL X ⋄ →EXIT
[5]   LI:R←0 PKINT X ⋄ →EXIT
[6]   LR:R←0 PKREAL X ⋄ →EXIT
[7]   LH:R←0 PKHET X ⋄ →EXIT
[8]   LP:R←0 PKCTRL 0 7 0,(⍴J),J←⍴X
      ⍝ data length,data type,pack,rank,shape
[9]   LP1:→LP3 LP2[1+0∊J]
[10]  LP2:X←1↑,X ⍝ to get correct prototype
[11]  LP3:R←R,⊃,/PACK¨,X
[12]  EXIT:
    ∇

Firstly, the function determines the data type of the object it is dealing with. If it is a simple object, it calls the appropriate conversion function and returns the packed result. I am assuming here that the conversion function places a header in the form discussed earlier before the data part. This code is not included in the test versions for the PKREAL functions discussed earlier. A 0 left argument indicates pack, and 1 indicates unpack.

How the DTYPE function is written is platform dependent, or of course it could be written in standard APL. I leave that as an exercise.

If the array is nested, the header for the tupple is determined. There is no data part for a pointer tupple; it simply identifies the structure. The tupples that define its elements are then converted to string form by a recursive call for each element of the structure. The individual results are catenated to the header and returned. Note that if the pointer structure is empty, we still need to build its prototype which is achieved by a recursive call on the 1↑ of the structure.

The UNPACK function makes use of a global BUFFER which will initially contain the transfer string to be re-constructed into an APL array. This is a string of consecutive tupples, each made up of a header and, usually, a data part, as discussed. Again, this is a recursively called function.

    ∇ R←UNPACK DUMMY;C;X
[1]   ⍝∇ Unpack transfer string from global BUFFER.
[2]    R←''
[3]    →(0∊⍴X←PKNEXT) EXIT
[4]    C←1 PKCTRL X ⍝ hdr length,data type,pack method,rank,shape
[5]    →LC LB LI LI LI LR LH LP[1+2⊃C]
[6]   LC:R←1 PKCHAR X ⋄ →EXIT
[7]   LB:R←1 PKBOOL X ⋄ →EXIT
[8]   LI:R←1 PKINT X ⋄ →EXIT
[9]   LR:R←1 PKREAL X ⋄ →EXIT
[10]  LH:R←1 PKHET X ⋄ →EXIT
[11]  LP:R←(4↓C)⍴UNPACK¨(1⌈,×/4↓C)⍴0
[12]  EXIT:
    ∇

Its first action, through function PKNEXT, is to get the next tupple from the buffer whose length is in the first 4 bytes of the header for each tupple, and then to drop those bytes from the buffer.

Function 1 PKCTRL X translates the header information as commented.

The data type then identifies how to unpack the string. If it is a simple data type, the appropriate function is called with the full tupple including header. Each function returns the re-constructed and re-shaped array which in turn is returned by UNPACK.

If the data type is nested, function UNPACK is called recursively for each element at this level of the nested structure determined from the shape, but at least once to generate the correct prototype. The dummy argument to UNPACK is there simply to obtain the required number of calls. The result is reshaped and returned. On completion, the original array should be returned, and the buffer should be empty.

So what is wrong with the PACK function ? The problem is that it passes down at each recursive call a part of the structure that is also taking up storage space at each calling level. If the object is large, a lot of workspace can disappear very quickly.

The technique I actually use is to assign the object to be packed to a global named, say OBJECT, and pass the Pick index as the argument to function PACK, not the object itself. For the first call, this Pick index is (⍳0), since (⍳0)⊃OBJECT is itself. Thereafter, at each recursive call for a nested object, its Pick index is extended so that it selects the item at the next level. A further refinement is to ravel the item from OBJECT that is currently being processed before the recursive call (its shape has already been recorded in the header), so that the Pick index is always a simple vector - a nested Pick index takes considerably more space. Pick assignment in Dyalog APL makes it straightforward to ravel the element, but the process is slightly more complicated otherwise, e.g. for Pick index I:

(I⊃OBJECT)←,I⊃OBJECT

Finally, when an element of the structure has been dealt with, it is set to 0:

(I⊃OBJECT)←0

This is done as soon as the object is read for processing in the individual conversion functions, or after the recursive call for a pointer structure. Thus, the space in the object is freed up and replaced by the generated transfer string. On completion, the global object has the scalar value 0.

Compression Methods¶

There are many ways to attempt to compress data. The ubiquitous PKZIP product does it extremely well and quickly. In APL, the interpretive overhead rules out many algorithms from practical consideration. I have found only three that are worth implementing from the viewpoint of the trade-off between processing cost and transfer volume.

Zero compression¶

Numeric data often contains a lot of zeros. A well-known method of reducing such data uses a Boolean expansion vector, where 0 marks a zero data item, and the compressed numeric data. It is simple to test for zeros, indeed the Real data conversion already requires it, and it is simple to expand, all at very little extra processing overhead. The criterion as to whether it is worth doing may be expressed as:

((⍴bool)÷8)<bytes×+/~bool

where bool is the boolean vector and bytes is the element size of the numeric data (1, 2, 4 or 8 bytes). In other words, is the extra space required for the boolean vector less than the space saved. The header protocol that I use allows each of the 8-bits of the Compression Method byte to identify up to 8 different packing methods. This is one of them.

Vector of Text Vectors (VTV)¶

This is such a commonly-used structure for holding lists of items that I find it worthwhile making it a special case. The APL internal structure is not efficient for large lists, though it can still sometimes improve on a Text Matrix with many trailing blanks. This case is handled by converting the VTV to a linelist† using any of the ⎕TC characters that do not occur in the enlisted text as delimiters (if they all do, it is treated as a nested array). Both APLs provide external functions to make the conversion to and from a linelist very rapid. As a linelist, it can then be treated as a simple Character vector, but with its packing method noted.

† A linelist is a character vector representing a list whose items are separated by an arbitrary character that does not occur in the list items. Its advantage is that unnecessary blanks may be omitted.

Heterogeneous Arrays¶

A heterogeneous array is something of an oddball. It contains a mix of scalar Character and Numeric items, at least one of each type. Although notionally a simple array, it is usually stored as a nested structure with the top-level tupple pointing to, sometimes many, scalar tupples. This is horribly expensive in storage terms, requiring at least 12 bytes per item. Uniquely, to my knowledge, Apl+Win has a special data type for heterogeneous arrays that does away with the pointer tupple.

The approach I have adopted for transfer is to split the data part of a heterogeneous array into three vectors, being:

• a boolean vector that identifies Numeric items by 1 and Character items by 0
• a vector of just the Numeric items
• a vector of just the Character items

The converted form of a heterogeneous array has a header identifying heterogeneous type and shape whose total tupple length includes the converted forms for each of the three vectors. Since the numeric part is handled by one of the normal conversion functions, zero compression will be employed if worthwhile.

More in hope...¶

I am always a little disappointed when I have to find an alternative to a pure APL approach to a problem. Faster machines have had a big impact on making an APL solution, previously untenable, more than just acceptable, even when performance is an issue. The implementers, and with all due credit, are aware of many speed issues, and indeed improvements and new facilities are constantly being added to APL. But there remain overlooked corners.

This exercise has firmly placed the focus on Encode. My work often involves use of this primitive in the efficient handling of large-scale, multi-dimensional data. Its converse, Decode, and also Index Of and Membership, are heavily overworked in this context. The latter two functions have long benefited from clever algorithms that improve performance. I make the same plea for Encode when results should be Integer or Boolean. The workspace overload in the latter case is particularly excessive, a case that is straightforward algorithmically when dealing with data that is exactly integer (including Real representations). After all, it is represented in binary form. I also have my doubts about the processing for Decode, which can give unexpected WS FULLs.

By the bye, when is a Boolean not a Boolean? Try bool_matrix,0 in Dyalog APL. The result has 1-byte Integer type (each item takes 1 byte). The reason is because scalar 0 is actually stored as a 1-byte Integer since this is a common use, and there are small performance gains to be made in general. But if bool_matrix is very large, the 1-byte Integer result may have a substantial workspace impact. There are a number of ways to avoid this, and some that might be expected to that do not. Thus, bool_matrix,0=1 does not work, but bool_matrix,⊖⍴0 does. Life has it little surprises. Workspace compaction, explicitly caused by ⎕WA reduces all arrays to their most compact form, as does ⎕SIZE'array' on that specific array. For this reason, in my DTYPE function, I apply ⎕SIZE on the argument before using ⎕DR to obtain its data type.

So maybe my anticipation will be fulfilled?