Semantic Class and Arrays of Functions

by D. B. Piper

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

Abstract¶

Many papers have already been published which discuss arrays of functions in APL. Some of the most significant are listed in the references at the end of this paper. Landaeta (LA86, LA88) and Bernecky (BE84) have made fairly rigorous proposals for APL2 and Sharp APL type interpreters respectively.

The basic concepts behind arrays of functions are discussed first. Landaeta’s proposal (LA86) is re-presented and criticised. Finally, the concept of semantic class is introduced, with an appropriate mechanism for the manipulation of arrays of functions.

Introduction¶

APL supports operations on arrays of data:

      1 2 3 × 4 5 6
4 10 18

Scalar extension allows a constant to be specified as a scalar:

      2 × 4 5 6
8 10 12

An implementation that supports strand notation allows an expression of the sort:

      2 3 4 + 5 6 7                   ..(1)
7 9 11

to be re-written as:

      (2+5)(3+6)(4+7)                 ..(2)

At first glance, the expression

      (2=5)(3-6)(4×7)                 ..(3)

is very similar, but has no “in-stranded” version such as (1) above. An APL supporting arrays of functions would allow such a short form:

      2 3 4 (+ - ×) 5 6 7             ..(4)

The sub-expression (+ - ×) in (4) above is a vector of functions

Operations on Arrays of Functions¶

If a vector of functions can be created in a way analogous to a vector of data, it should be possible to manipulate function arrays in similar ways. For assignment:

      F ← + - ×                       ..(5)

we can then write

      2 3 4 F 5 6 7                   ..(6)

As Brown (BR84) points out, function assignment of this sort is a conforming extension of the syntax of APL2, since it currently produces a SYNTAX ERROR.

Once the concepts of functional arrays and assignment are adopted, it is a short step to manipulating arrays of functions. It is at this point that difficulties begin to arise.

Syntax Class.

APL embodies the concept of syntax class for each object (primitive or defined) in a workspace. Variables, functions and operators are each given a different class. Name class (as returned by the ⎕NC system function) is a concept similar to that of syntax class. Variables are given syntax class 0, functions class 1, and operators class 2.

An object of a given syntax class operates on objects only of a lower syntax class. Functions operate on variables, creating new variables. Operators operate on functions (or variables) and return derived functions as a result.

This restriction on the syntax class of arguments and operands is the basis of the problem. For example, if we wish to alter the shape of a function array, the re-shape function cannot be used since a function array has syntax class 1.
Possible Solutions.

The concept of a whole new set of operators to manipulate function arrays is impractical (BR84). Presumably it would also be desirable to manipulate arrays of operators, requiring objects of a new syntax class (called Transforms (BK84)). Arrays of transforms then come into question, and so on in an infinite regression.

Landaeta (LA86, LA88) proposes the concept of an elevator object with a new syntax class. The elevator takes an object of syntax class N and returns a derived object of syntax class N + 1. Landaeta (LA86) uses the symbol $:
```
⍴$
```
returns an operator which can be used to manipulate a function array. Repeated use of the elevator can produce an object of arbitrary syntax class, to operate on objects of the correct associated syntax class.
Problems with the elevator.

A number of problems can be identified with the use of the elevator. Firstly what is the syntax class of the elevator itself? Since it can produce an object of arbitrary syntax class, it can only be assigned an “infinite” syntax class. The problem of an infinite regression of syntax classes still exists.

The derived object:
```
⍴$                                ..(7)
```
is an operator (with syntax class 2), but obeys the syntactic rules of a function. Landaeta argued that since (7) is an ambivalent operator, which does not exist in APL2, a modified syntax was acceptable. This argument seems somewhat contrived and rather violates the idea of keeping APL syntax as simple as possible.

Semantic Class¶

The approach of changing the syntax class of an object gives rise to the problem mentioned above. Note, however, the concern is not with the syntax class of the operation in question, but rather with the syntax class of the arguments. The concept of changing the syntax class of an object without changing its syntactic properties is fundamentally flawed. Since the syntactic properties are not being changed, the syntax class should not be changed. Instead the semantic properties of the operation should be modified.

In order to define the semantic properties of an object, a three-item vector is defined for each object in the workspace. This defines the maximum syntax class of the left and right arguments and explicit result. Each item can take values 0, 1 or 2. The semantic property vector for a variable is empty. By default the semantic property vector for a function is 0 0 0, for an operator it is 1 1 1.

A new operator is defined to allow the semantic property vector to be manipulated. The CONTEXT operator is represented by $ (to maintain consistency with (LA86)). The left operand of CONTEXT is the object whose semantic properties are to be changed. The right operand is the new semantic property vector. The only unusual characteristic of the CONTEXT operator is its default semantic property vector - 2 1 2. The value of 2 for the left operand and explicit result semantic classes allows operators to be manipulated and returned.

Use of CONTEXT.

To reshape a function array:
```
F ← + - ×
G ← 2 2(⍴$ 0 1 1)F                ..(8)
```
In (8) above, the CONTEXT operator is used to change the semantic properties of the re-shape function, so that:

The left argument is a variable.
The right argument is a function.
The result is a function.

The array G will be a 2-by-2 function array.

Catenation of function arrays:
```
F ← + -
G ← × ÷
H ← F(,$ 1 1 1)G
```
The derived catenate function has semantic class 1 for both arguments and its explicit result. A function vector is passed for both arguments. A new function vector is returned as the explicit result.

Other Functions

      F ← × ÷ ⍴ ∨ ∧
      G ← + ⍴ ∊
      G(∊$ 1 1 0)F
0 1 0

Membership is being used with both arguments of syntax class 1. The explicit result is of syntax class 0. Note that the symbols in a function vector are not the same as the equivalent symbols in a character vector.

      F ← × ÷ ⍴ ∨ ∧
      G ← '+⍴∊'
      G(∊$ 0 1 0)F
0 0 0

Missing Syntax Classes

The use of the CONTEXT operator allows objects of mixed syntax class to be created. These have special properties, which will be illustrated below:
```
F ← + - ÷
V ← 1 2 3
X ← F(,$ 1 0 0)V
```
X is a vector containing objects of both variable and function syntax class. An object of mixed syntax class inherits the highest syntax class of any of its constituents. The object X is therefore a function; it is a niladic function since a right argument is already present (and no function takes a left argument only). These properties can be illustrated:
```
      X                                ...(9)
¯1 ¯.5 ¯.33333
```
Note that X is evaluated as if the expression
```
      + - ÷ 1 2 3
```
had been typed, rather than:
```
      (+ - ÷) 1 2 3                    ...(10)
1 ¯2 .33333
```
Other properties:
```
      ⍴X                               ⍝ SHAPE OF RESULT OF X
3

      (⍴$ 0 1 0)X                      ⍝ SHAPE OF VECTOR X
6
```
Since X is evaluated, a problem arises over displaying the contents of X. In APL2, this can be achieved using the disclose function:
```
      (⊃$ 0 1 0)X
+ - ÷ 1 2 3
```

Other mixed syntax-class objects

The niladic function X is not very useful, however if a single argument is supplied on the left, a named monadic function can be created:

      INCREMENT←1 (,$ 0 1 1) +
      INCREMENT 3
4
      INCREMENT INCREMENT 4 5 6
6 7 8
      ⍴INCREMENT
SYNTAX ERROR
      ⍴INCREMENT
      ^^
      (⍴$ 0 1 0) INCREMENT
2
      (⊃$ 0 1 0) INCREMENT
1+

Properties of mixed syntax-class objects

From the above examples, (especially (9) and (10)), it is easy to see that a reference to an object containing mixed syntax classes causes an attempt at evaluation. In other words, many variables, functions or operators can be stranded together without any evaluation taking place. As soon as an attempt is made to mix syntax classes via stranding, evaluation is triggered. Objects of mixed syntax class have to be created by the use of catenation or some other function.

User Defined Functions¶

The creation of arrays of functions is not limited to primitive functions. Defined functions may also be used, with beneficial effects on several “traditional” APL problems. For example, in a menu-driven system, one technique for executing a function selected from a menu is to pick the function name from an array and then execute it. The problems associated with the use of execute are discussed elsewhere (PI86,PI88); its use should be avoided.

If function arrays are permitted, execute can be avoided:

      OPTS←OPT_1 OPT_2 OPT_3 OPT_4

      RC←(OPT_NO(⊃$ 0 1 1)OPTS) PARMS

The option number (OPT_NO) is used to pick the correct function from the list. The reference to this function with the argument PARMS causes its evaluation.

⎕CR and ⎕FX Redefined

The system functions ⎕CR and ⎕FX are often criticised. ⎕FX is particularly criticised since the function is created as a side effect, it is not the explicit result of the function. ⎕FX could be redefined to use function assignment. The semantic vector of the new function is 0 0 2, that is it takes two data arguments and returns a function:
```
MYFN←⎕FX ARRAY
```
The right argument contains the code of the function (or defined operator). Note the function is assigned as the explicit result of the system function. The ⎕CR function is defined as the inverse of ⎕FX, its semantic property vector is 0 2 0.
```
ARRAY←⎕CR MYFN
```
Note the function is passed explicitly as the right argument (rather than simply being named as the right argument). The explicit result is the character representation of the function.
The DEL Editor

In the same way that ⎕FX was redefined, the DEL editor can be defined as a primitive function with semantic property vector 0 2 2:
```
NEWFN← ∇OLDFN
```
The facilities provided by DEL are of course implementation dependent. For editing a new function, the jot can be used to represent a null function:
```
NEWFN← ∇ ∘
```
The left argument of ∇ could be implemented either to specify the execution properties of the defined object (as with ⎕FX in APL2) or to pass an opening command to the editor (as a character vector).

Function Headers¶

Since the function is being named as the explicit result of both ⎕FX and the DEL editor, a question can be raised about the meaning of the function name specified in the function header line. The function assignment capability allows the meaning of names in the header to be rationalised.

Currently, all names in the header of a defined function are local, except for the function name. By explicitly assigning the function to a name, the function name specified in the header can be considered the local function name. This is particularly useful for recursive functions - consider the following definition of a recursive factorial function:

      CODE

R← ∆FACT NUM
⍝ RECURSIVE FACTORIAL FN.
R←1
→(NUM≤1)/0
R←NUM×∆FACT NUM-1

      FACTORIAL←⎕FX CODE
      FACTORIAL 4
24
      ∆FACT 4
VALUE ERROR
      ∆FACT 4
      ^

The benefit of this approach to recursive functions is that the interpreter “knows” it is re-invoking the same function all the time. Because of this knowledge, the local copy of the function re-invoked each time can be a “pre-parsed” version - all the work involving syntactic analysis is performed only once. The impact on performance of recursive code could be considerable.

Conclusions¶

The inclusion of arrays of functions into APL syntax seems at first glance to be a natural extension, relatively simple to implement. The number of papers written on the subject is mute testament to the difficulties that are encountered in practice.

The distinction drawn between syntactic and semantic properties appears to solve many of the problems. Functions remain functions but are semantically transformed to operate on arrays of functions rather than data. Contrast this to the approach of Landaeta where functions are transformed into operators, but retain the syntactic properties of functions.

The three-item semantic property vector allows the semantic properties of the left and right arguments and the explicit result to be specified independently.This independence can be used to rationalise the definitions of ⎕CR and ⎕FX as well as the DEL editor.

The assignment of functions as the explicit result of the editor or ⎕FX clarifies the meaning of the function name in the function header. This development presents the opportunity for a considerable improvement in the performance of recursive functions by removing one of the major performance overheads - the continual re-invocation of the same unit of code (note that some implementations have already by-passed this problem in other ways).

The introduction of arrays of functions to APL is probably the next major enhancement to the language following nested arrays. The implications for the power, flexibility and usability of the language are probably as great as they have been with nested arrays.

References¶

LA86 Landaeta D.J. A Notation for Manipulating Arrays of Operations
APL86 proceedings APL Quote Quad Vol.16 No.4

LA88 Landaeta D.J. The Theory of Function Arrays
APL88 proceedings APL Quote Quad Vol.18

BE84 Bernecky R. Function Arrays
APL84 proceedings APL Quote Quad Vol.14 No.4

BR84 Brown J.A. Function Assignment and Array of Functions
APL84 proceedings APL Quote Quad Vol.14 No.4

BK84 Benkard J.P. Syntactic Experiments with Arrays of Functions and Operators
APL84 proceedings APL Quote Quad Vol.14 No.4

PI86 Piper D.B. Using Quad-FX to Facilitate the use of Auxiliary Processors
Technical Articles Section Vector Vol.3 No.2

PI88 Piper D.B. APL88 Code Quality
Letter in Technical Correspondence Section. Vector Vol.4 No.4