Function Models

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

1. Introduction¶

We have defined a simple descriptive formalism, and used it to define the data domains available in APL. Because functions can be characterised by the data domains of their inputs and outputs, we started to examine 𝔽, the functions domain, and we shall continue with that examination in a little more detail.

The expression defining the domains of a function’s inputs and outputs is known as the function mapping, or model. The terms are used interchangeably.

Wherever the term "function" is used without qualification, this may be taken to mean a "partial function". A function is a mapping from a set of input values to a set of output values. A total function is defined for all elements of the input set; a partial function need not necessarily be defined for all elements of the input set. Thus, the reciprocal function, whose mapping is ℝ↤ℝ, is not defined for zero, and is therefore a partial function, while the signum function, whose mapping is ℤ↤ℝ, is a total function. We shall have little need to identify which functions are total functions.

Unless we wish to add the rule explicitly, there is nothing which automatically restricts an object to being a function or a variable.

There is nothing restricting the arguments or results of a function to data items. A function can take a function definition as an argument, in which case it is often known as a functional or an operator. Examples are the reduction operator in APL, and the differential operator in calculus.

There is nothing requiring the arguments or result(s) of a function to be exclusively functions or data – as witness the use of slash to denote compression or reduction, according to context.

There is nothing restricting a function to a single mapping. The complete mapping for a particular function may consist of the domain sum of other, simpler, mappings.

2. Dyadic Functions¶

The function models so far considered have all been monadic.

A dyadic function could be defined with a mapping over the domain product of its left and right arguments, but there are difficulties. We could, for instance, define a function ADD as having the mapping ℝ↤ℝ⊗ℝ , which is entirely correct, so far as it goes, but suggests that in practice the function is applied to a 2-element numeric right argument. It would be better if we could also indicate the syntax of the call in some way.

This desire becomes a necessity with mixed functions such as reshape, whose mapping (ignoring character right arguments) would be something like

(ℝ*ℕ*ℕ)↤(ℕ*ℕ)⊗ℝ*ℕ*ℕ

which looks OK, but might lead us to interpret (2⍴ 3 4) as defining a 2-by-3 matrix filled with 4s. (Why? Because the mapping requires an integer vector for the new shape, and can accept any simple array (including scalars) as the element list. This must mean that the shape is 2 3, and the element list is the scalar 4.)

It is common practice to construct a logical calculus with 1-place functions only. This can then be extended to n-place functions via a mechanism popularised by Curry, but actually due to Schönfinkel. The process is best illustrated using conventional notation:

the application of a 3-place function f, to arguments a, b and c, conventionally written f(a,b,c), can be conceived to be the following process:

i) construct a 1-place function f ′ which can be applied to a to yield another 1-place function f ″
ii) apply f ″ to b to yield another 1-place function f ‴
iii) apply f ‴ to c, to yield the final value.

As an example of that ready wit for which logicians are everywhere famous, the f ′, f ″, f ‴, etc, are known as Curried functions.

Assuming conformance, the APL function call ADD(THIS;THAT) could be deemed to represent the following sequence:

ADD(THIS;THAT) ≡ (ADD1 THIS) THAT
               =  ADD2 THAT
               =  result

We would expect the result to be an element of ℝ, so that the function ADD2 has the mapping ℝ↤ℝ ; this function is the result of applying ADD1 to THIS, so that the function ADD1 has the mapping (ℝ↤ℝ)↤ℝ . Since the expression ADD(THIS;THAT) is merely a syntactically convenient way of describing the above process, we may say that the mapping for ADD itself is also (ℝ↤ℝ)↤ℝ . This, or something similar, is the notation used in most books on semantics. Or the manuals for functional programming languages, where this sort of stuff is commonplace.

Unfortunately, it gives us no indication of the order of evaluation. The sequence

ADD(THIS;THAT) ≡ (ADD1 THAT) THIS
               =  ADD2 THIS
               =  result

also gives a final mapping of (ℝ↤ℝ)↤ℝ .

To revert to infix notation, observe how the Curried function approach reflects the process in the APL interpreter. In an expression such as

THIS × THAT,

which may be seen as shorthand for

(TIMES_LEFT THIS) THAT,

the left argument is examined, and

if LA null, (TIMES_LEFT THIS) ∊ (ℤ↤ℝ)
if LA non-null, (TIMES_LEFT THIS) ∊ (ℝ↤ℝ)

and the resultant function applied to the right argument THAT . This means that the mapping for TIMES_LEFT is

if LA null, TIMES_LEFT ∊ (ℤ↤ℝ)↤∅
if LA non-null, TIMES_LEFT ∊ (ℝ↤ℝ)↤ℝ

which may be summarised as

TIMES ∊ ((ℤ↤ℝ)↤∅)⊕(ℝ↤ℝ)↤ℝ .

Problem solved. We shall adopt the convention that, in an expression like (A↤B)↤C , we have the domain of the result (A), the domain of the right argument (B) and the domain of the left argument (C). Or, to put it another way,

A←C f B  iff  f∊(A↤B)↤C .

This convention captures the fact that (i) the "control" argument is conventionally on the left, and (ii) while evaluating from right to left, the interpreter will first check out any left argument, before deciding what to do with the right.

We would also observe that any mapping of the form (D↤∅) is identically equal to D alone, so that the expression could be simplified to

TIMES ∊ (ℤ↤ℝ)⊕(ℝ↤ℝ)↤ℝ

except that we lose any indication of whether the monadic definition takes its argument on the left or the right.

With arithmetic functions, however, there is no obvious "control" variable and most of us would feel probably more comfortable with ADD(THIS;THAT) than (ADD1 THIS) THAT, even given that the expressions are equivalent.

We can avoid such difficulties if we explicitly identify the domain of the left argument and the domain of the right argument separately. For this, we need a sequence or a list of domains.

In keeping with our policy of using distinguishing syntax for the domain definitions, we enclose a domain list with angle brackets. The list elements are domain expressions, separated by semicolons, e.g:

⟨A*ℕ;B⊕C⟩ .

The significant difference between a list of domains and their cross-product lies in the way they are affected by null entries. If we denote the cardinality of domain A by n(A), then (in conventional notation) the cardinality of a cross-product is

n(A⊗B) = n(A) × n(B)

which evaluates to zero, if either domain is empty. The domain list,

⟨∅;ℝ*ℕ*ℕ⟩

on the other hand, still has two separately identifiable elements, albeit one of them is null. If we adopt the convention that all function models require a two-element domain list, then two non-null elements indicates a dyadic function, while monadic functions would be defined with one element null.

Another possible refinement is to include the names (⍺ and ⍵) of the left and right arguments in the domain list. We can now avoid all ambiguity, by defining the mapping of the reshape function on numeric arrays thus:

(ℝ*ℕ*ℕ)↤⟨⍺∊ℕ*ℕ;⍵∊ℝ*ℕ*ℕ⟩

which we can improve by adding in the definition for character arrays, and allowing for scalar left arguments, to give:

((ℍ*ℕ*ℕ)↤⟨⍺∊ℕ⊕ℕ*ℕ;⍵∊ℍ*ℕ*ℕ⟩)⊕
 (ℝ*ℕ*ℕ)↤⟨⍺∊ℕ⊕ℕ*ℕ;⍵∊ℝ*ℕ*ℕ⟩.

An example: addition is a scalar dyadic function, and therefore has the mapping ℝ↤⟨ℝ;ℝ⟩ , while the derived reducing function has the mapping ℝ↤ℝ*ℕ, so that the reduction operator itself has the mapping

(ℝ↤ℝ*ℕ)↤(⍺∊ℝ↤⟨ℝ;ℝ⟩).

This is quite a neat definition. If we dispense with ⍺ and ⍵ , it becomes

(ℝ↤ℝ*ℕ)↤⟨ℝ↤⟨ℝ;ℝ⟩;⟩.

Using the (A↤B)↤C convention defined above, the definition becomes

((ℝ↤ℝ*ℕ)↤∅)↤(ℝ↤ℝ)↤ℝ.

which may be less perspicuous.

That, at least, is the story if the interpreter permits the expression +/ to appear without a right argument. Many interpreters insist that the derived function be applied immediately, in which case the slash looks more like an infix function, with the mapping (for the reduction operation) of

ℝ↤⟨ℝ↤⟨ℝ;ℝ⟩;ℝ*ℕ⟩

and another (for the replication operation) of

(ℝ*ℕ)↤⟨ℕ*ℕ;ℝ*ℕ⟩

giving a combined definition of

((ℝ*ℕ)↤⟨ℕ*ℕ;ℝ*ℕ⟩)⊕ℝ↤⟨ℝ↤⟨ℝ;ℝ⟩;ℝ*ℕ⟩ ,

unless, of course, you prefer

((ℝ*ℕ)↤ℝ*ℕ)↤ℕ*ℕ)⊕(ℝ↤ℝ*ℕ)↤ℝ↤⟨ℝ;ℝ⟩ .

3. Storage and Assignment¶

Even with the foregoing, we still cannot describe the assignment function adequately. For this we need two more primitive domains.

The stages in interpreting a statement such as

NAME ← EXPRESSION

are roughly as follows:

— evaluate EXPRESSION, and leave the result somewhere in memory;
— find (or make) an entry in the symbol table for NAME;
— (re)set the pointer associated therewith to point to the result of EXPRESSION.

These operations involve two new domains, whose elements are (i) names, and (ii) something approximating to memory locations.

The following quotation is taken from §2.1 of "The Varieties of Programming Language":

"The domain … Id, is the set of names or identifiers in the programming language. [It] is an elementary domain, and it is also the only domain we shall encounter whose members are elements of the text of the program, and are therefore parts of the programming language itself, and not objects manipulated by it. Id is generally defined by the syntax rules of the programming language. It is a very simple domain whose only basic property is the relation of equality – it is always possible to say if two names are the same or not, but names in general have little internal structure.

The only remarkable thing about Id is the number of different words which have been used to describe its members. The fact that they have been called "names", "identifiers" and "variables" in different languages would not matter so much if these same words had not been also used with quite different meanings."

That which Strachey refers to as "Id" will be denoted herein by the double-struck character 𝕀 .

Strachey then goes on to formalise the idea of "storage" – splendid pioneering work, but flawed.

"The problem with inconsistent formalizations (like Strachey’s potentially was) is that they provide no basis for reliable reasoning", (Gordon, 1979). Point taken: Gordon himself (p.15) defines state (for a tiny language) as follows:

 State  =  Memory × Input × Output
Memory  =  Ide → [ Value + {unbounded} ]
 Input  =  Value*
Output  =  Value*
 Value  =  Num + Bool

We recognise the domain Value as our (implementation dependent) universal domain 𝕌, and since the domain mapping function includes, by definition, all partial functions, we do not need the {unbounded} element Gordon introduces, so we can rewrite the above as follows:

𝕊  =  Memory × Input × Output
   =  (𝕌↤𝕀)⊗(𝕌*ℕ)⊗(𝕌*ℕ) .

Gordon’s formulation allows for just two channels: Input and Output; Unix defines three by default: stdin, stdout and stderr; a realtime rate feed may have half a dozen. We would allow arbitrarily many:

CHANNELS = (𝕌*ℕ)*ℕ.

Precisely what is required to describe the machine’s state at any point in the execution of a program varies from author to author. A useful definition would be for state to include

• all environment information (⎕IO, ⎕CT, … , state of all channels, etc);
• the current symbol table (consisting of pairs of <name, value pointer>, with the most recent name entry being the one deemed to be currently in scope);
• the memory, containing the current value (if any) of all named variables;
• the current stack (only one stack is required in theory).

This would give us a definition of

𝕊  =  Environment × Symbol_Table × Memory × Stack × Channels .

Not that it matters a lot. At this stage, we shall content ourselves with identifying changes to a state whose precise nature we at present leave unspecified.

Each change in state will be an element of 𝕊⊗𝕊, the set of all pairs of "before" and "after" states. The domain of all state changing functions is, of course, 𝕊↤𝕊, which, being the set of partial functions from 𝕊 to 𝕊, admits the existence of states we cannot change out of.

If a function FOO has side-effects, i.e, FOO is a function whose execution produces a change of state, then we say

FOO∊(𝕊↤𝕊) .

Right parenthesis is just such a function, since its action is to place a marker on the stack. Semicolon is another. Left parenthesis is yet another: it delivers the topmost item or items from the stack, down to the most recent right marker, and finally removes the marker itself. Left parenthesis therefore has the mapping

(𝕊↤𝕊)⊗(𝕌*ℕ) .

Assignment is another such a function, and (for the time being) its mapping is

(𝕊↤𝕊)↤⟨𝕀;𝕌⟩.

4. Headers¶

For primitive functions, the obvious repository for all this is the APL standard¹. For user-defined functions, the obvious repository is the function header.

Currently, the function header provides a syntactic template and a list of locals. Our suggestion is that the localisation of names be performed separately, and that the present syntactic template is replaced with a more informative semantic specification.

In many cases, there will be no arguments and no result: in such cases a default header of 𝕊↤𝕊 can be assumed. This tells us that the purpose of the function is to produce a change of state (an externally visible change of state, that is), by reading input, producing output, or assigning a value to an external variable.

Where a header is provided, it will be the function mapping. From this, the interpreter can determine the function’s valence, including any ambivalence, any restrictions on the type or rank of arguments, whether the block has any side-effects, whether the function is actually a user-defined operator, etc.

There will no longer be any need to name the result or the arguments.

With an explicit header, side-effects will be permitted only if they have been included in the header. If side-effects have not been implicitly or explicitly allowed for, then any attempt to assign a new value to an external variable, for instance, will be reported as a DOMAIN ERROR.

The polyglot reader will already have noticed that specifying the domain(s) of the parameter(s) and the domain of any result is very close to the idea of pre- and post-conditions of abstract data types.

By way of introduction to the subject, the following quote from Rachel Harrison may be useful:

In Guttag (1977) the term abstract data type is used to refer to "a class of objects defined by a representation-independent specification".

• A data type (or type) is a means by which we can classify objects which have identical properties. A data type can be either intrinsic (built-in) or user-defined.

When using data abstraction, we are more concerned with what we can do with the data types than in how it is implemented. This leads to the definition shown below:

• An abstract data type (or ADT) consists of a data type together with a set of operations, called access functions, which define how the data type may be manipulated.

These two definitions imply the use of a strongly typed language.

Well, maybe, but not necessarily . . .

5. Parameters¶

As already noted, any left argument is denoted by ⍺ , any right argument is denoted by ⍵ .

If these two names are excluded from the domain 𝕀 , they cannot appear on the left-hand side of an assignment. Thus the slightly dodgy habit of updating actual parameters is prevented, and all functions without side effects can be rerun from the top — a useful thing to have when debugging.

When the function is applied, the actual arguments are evaluated, and, where applicable, type and rank checked against that specified by the mapping. In the event of a mismatch, the function will report a DOMAIN ERROR without proceeding further. This is known as strong typing.

"Strong typing", said the sage, "is for weak minds". What this mechanism provides, however, is optional strong typing. The parameter checking can always be rendered ineffective by specifying a header like:

(∅⊕𝕌)↤⟨∅⊕𝕌;𝕌⟩

which may or may not return a result, may or may not take a left argument, but certainly takes a right argument, which may be of any arbitrary type, shape, size, colour or creed.

6. Results¶

The actual domain of the result will also be checked for type and rank against that specified in the function mapping. In the event of a mismatch, the function will report a DOMAIN ERROR.

This, of course, begs the question of how we identify the result of a function. There has not, heretofore, been any reserved name for the result of a function, and ⍵ , the most poetically apposite name, has already been appropriated.

We could make some rule about using the value of the last expression executed before exiting, or maybe the last uncommitted value before exit. C coders use

return expression

which identifies the value to be returned, and then exits the function. This is bad design. The two actions should be separated, thus:

result expression
return

which would permit post-processing (restoring the environment, for instance) after the result has been obtained.

We do not need the return function, since APL is already adequately equipped in that respect, but the addition of a result function would be really useful.

Each use of the result function would trigger a check that the value of expression fell within the domain prescribed in the function header. In the event that it did not, the interpreter would report a DOMAIN ERROR within the function.

As a particular case of the above, any attempt to use a result statement with a non-null argument, when the function header specified a null result, would also trigger DOMAIN ERROR within the function.

Exiting a function without having declared a result, when one was expected, would trigger a RESULT ERROR outside the function.

7. Caveats¶

The complete model for a function, which may consist of more than one simple mapping, should enable us to identify unambiguously which mapping to apply, knowing only the type and rank of the arguments. This may not be easy.

Conformance requirements are not addressed. They would require a rather more elaborate apparatus than that being developed here, which would hide the essential elements of this discussion.

"Shy" results too could be accommodated with more syntax.

If the function header is redesigned as suggested, we need to address the question of how local variables are identified. We shall tackle this in due course.

Those deliberations will also generate a requirement for user-defined named domains, and that will in turn with suggest other uses for named domains.

8. References¶

8.1 H B Curry, R Feys, Combinatory Logic, Vol I, North Holland, Amsterdam [1968]

This is the standard text, which appears to have been a major influence on the design of J, although the device now known as "Currying" first appeared in —

M Schönfinkel, Uber die Bausteine der mathematischen Logik (in) Mathematische Annalen, 92 [1924]

8.2 Christopher Strachey, The Varieties of Programming Language (in) Proc. International Computing Symposium, Cini Foundation, Venice [1972]

It is highly likely that this is the paper which has been reprinted in —

Peter O’Hearn, Robert D Tennent, Algol-like Languages, Vol 1, Springer-Verlag [1996]

8.3 Michael J C Gordon, The Denotational Description of Programming Languages Springer-Verlag, New York [1979]

8.4 Rachel Harrison, Abstract Data Types in standard ML Wiley, Chichester [1993]

Harrison herself references —

J V Guttag, Abstract Data Types and the development of data structures CACM 20 [1977]