Nial

The appearance and growing popularity of APL in the 1960s and 1970s generated significant interest among computer scientists and practitioners in the use of arrays as an universal data structure. The so called ‘theory of arrays’ emerged in 1968 as an attempt to put the array programming paradigm on formal ground. More generally, the theory aims at developing a comprehensive ‘logical foundation for the construction of programming languages’ by providing rigorous definitions for data structures and the operations on them.

The theory of arrays combines the set-theoretic concepts of nesting and self-containment with the vectors and multi-axis arrays of APL. It is an axiomatic theory about the definition and manipulation of nested rectangular arrays: data collections arranged along axes, with items that are themselves arrays. Every data object in the theory is an array. A number, character, or other scalar is considered an one-item array of rank 0. Arrays have shape, and ones of the same shape differ according to their virtual items. Simple axioms define certain primitive operations on arrays. Most data operations in programming can then be represented by operations built upon the axioms. Rules are explicitly included for transforming any operation into a new operation that applies to all items in any array. The axioms, and consequently the theorems derived form them, hold for all arrays having a finite number of axes of arbitrary countable ordinal lengths.

One consequence of the theory of arrays is that it influenced the evolution of the array programming languages. This includes APL, but most notably, Nial was created as the implementation of the theory. (The name of the language comes from ‘nested interactive array language’.) An interpreter for Nial, named Q'Nial, was released in 1983 and is still (as of 2009) available. Formerly marketed at a substantial price, it is now offered for free, including the C source. Nial has been applied in various domains, but is considered particularly suitable for prototyping and experimenting with functional programming structures.

The initial version of Nial/Q'Nial was very close to the ideas of array theory, while also providing imperative control and other conventional programming constructs. In a sense, the theory was supplemented by a set of additional theorems developed to support the implementation functionality. Later on, a redesign of Nial and Q'Nial was undertaken which introduced some modifications to the theory of arrays and sacrificed some of its generality.

Arrays and Programming

Like all array languages, Nial bears some similarity to APL. However, it differs from its progenitor by rationalizing some concepts, introducing a number of new ones, and being more generally usable. Among others, Nial, like other array languages, disposed of the special alphabet of APL.

Primitive data, or atoms in Nial include integer and floating-point numbers, truth values, characters, indivisible strings of characters called phrases (a.k.a. symbols elsewhere) and faults. Truth values are symbolically designated in several ways (true, truth, and l, and false and o, respectively) but can also take place in arithmetic computations where they are equivalent to 1 and 0. A fault is a value intended to carry information of an error; it can be generated implicitly or explicitly and contains a text string.

An atom is indistinguishable from an array with that atom as the single member. Data objects of different types may occur in the same array. Any item of any array can itself be an array. Through nesting, arbitrary hierarchies can be built.

Arrays can be specified by enumerating their members delimited by commas within brackets. However, the so called ‘strand notation’ is also used, where inclusion at the same level is expressed by means of juxtaposition. The two notational forms may be mixed, and parentheses can be used for demarcation. For example, the 3×2 array [[1,2],[3,4],[5,6]] may be equivalently written [1 2,3 4,5 6] or [1,2] [3,4] [5,6] or (1 2)(3 4)(5 6).

Arrays of characters are called strings and receive a special treatment, including a special notation; e.g. 'abc' is a shortcut for the array `a `b `c.

In order to make nested structure visually more apparent, the Nial interpreter uses yet another notation – box diagrams – possibly combining it with the strand notation at the lowest level. The two-element array [1 2 'ab',3 4] would be displayed thus:

+--------+---+
|+-+-+--+|3 4|
||1|2|ab|| |
|+-+-+--+| |
+--------+---+

Differently from APL, J, and K, all operations are monadic, and expressions are evaluated left-to-right. A particular difference from the said languages that follows from there being no dyadic operations in Nial is the absence of operator ambivalence. E.g. subtraction is denoted - or minus, while negation is opposite or opp.

Operations that would be dyadic in other languages, in Nial take a pair (i.e., a two-element array) as an argument. Infix use is possible as syntactic convenience: an expression of the form x f y, where f is any operation, is equivalent to f x y; e.g. 3 / 5 is the same as /[3,5] or / 3 5.

Most operations are pervasive, in that they seek to apply at the deepest level of nesting possible; e.g. +[1 2 3,4 5 6](10 20) is the same as [1 2 3 + 10,4 5 6 + 20], which in turn is [[1+10,2+10,3+10],[4+20,5+20,6+20]], i.e. [11 12 13,24 25 26].

Some operations are reductive, others are not. + 7 4 12 8 yields 31 – the sum of all the elements of the array – while - 7 4 12 8 is an incorrect expression: minus expects an array of exactly two elements.

There is a large number of built-in operations in Nial, many of them for array generation, extraction, restructuring etc. A special class of functions called transformers serve to modify ordinary operations and thus produce new ones. New operations and transformers can be defined.

An operation can be defined as if it has many arguments – in fact that means that it expects an array of precisely that many elements. It follows that an operation defined to have a single argument is applicable to an array of arbitrary shape. For instance, f is op x (5*x) defines an operation f of one argument (x), therefore valid applications, among others, are f 13, f 3 18 7, and f 3 4 [5,6 7]. On the other hand, if g is op x y z (x+(y*z)), then g requires a 3-element array (of arrays of whatever shape). Note that it also follows that f admits infix notation, while g does not.

Nial has introspection abilities at several levels. The type of a value can be inquired, including whether it is atomic or not, whether it is a fault etc. An internal representation of an expression, namely its parse tree, can be accessed, generated anew, manipulated, evaluated, or turned back into a token sequence (another internal form of representation) or a string of Nial source. Token sequences and parse trees are nothing but arrays, and correspondingly can be processed using the ordinary array operations available in the language.

Functional Programming

Programming in Nial is mostly in a functional style. Imperative features are available but not much used. Working with bulk data, namely arrays – as contrasted to processing it one piece at a time – encourages a stateless, applicative view on programming rather than one oriented to explicit state manipulation.

However, Nial's approach to functional programming is different from that of most other languages. Data and functions are strictly separate program entities. Moreover, there is a clear distinction between first- and second-order functions, called operations and transformers, respectively. The former operate on data to produce data (arrays), and the latter take operations and produce operations. These are the only two kinds of functions in the language.

As functions are not data objects, they cannot be stored in arrays or otherwise treated as data. For instance, an operation cannot return an operation or have one as an argument. The closest to treating an operation or a transformer as data is to obtain its internal representation, or ‘cast’. Like any other value, a cast can be passed around between operations, and a cast of a function can be used to call that function. But a cast cannot capture a lexical context (does not represent a closure), so function casts bring small benefit.

The above mentioned limitations do not hinder functional programming as much as it may seem. Composition, partial application, transformation, λ-abstraction, and atlas formation are being employed in constructing operation expressions. Such expressions denote ‘computed’, anonymous operations just as ordinary expressions denote computed, anonymous data values, and it is always possible to use an operation expression in place of referring to an operation by name. Operations can be defined locally to each other as necessary to achieve better program structuring. Built-in and user-defined operations are treated the same way in all respects of syntax and semantics.

For example, sqrt (10-) is the composition of the operations 10- and sqrt, the latter over the former. 10- is a partial application of - and can be read ‘the operation that subtracts from 10’. If needed, the above operation can be given a name, say f, through defining f is sqrt (10-). Valid expressions then are sqrt (10-) n (provided n is a numeric value), f 5 8 etc.

Had we needed an expression for ‘the operation that subtracts 10’ rather than the above, we might have written 10 converse -. Converse is an operation transformer that can be thought of as flipping the arguments of an operation, so that, e.g., converse - 5 3 yields -2. Another example of using converse is 2 converse power (‘square’), so 2 converse power + is ‘square a sum’, while + 2 converse power is ‘sum squares’, and therefore sqrt + (2 converse power) is ‘Euclidean length’. Note that, since + is reductive, the latter three operations involve summation of vectors of arbitrary length; e.g. sqrt + (2 converse power) 3 -9 4 yields 10.2956.

An atlas is a sequence of operation expressions written in square brackets. The result of applying an atlas is the list of results from applying the operations in the atlas on the same argument. For instance, *[+,-] composes * (multiplication) onto the atlas [+,-] (producing sum and difference), so e.g. 5 (*[+,-]) 3 yields (5+3)⋅(5-3)=16. Like other operation expressions, an atlas can be given a name, e.g. pm is [+,-].

For cases where an explicitly parametrized operation is needed, one can use an ‘operation form’ – another name for a λ-expression. The following

peval is op cs x (reduce (op c v (v*x+c)) reverse cs)

is a definition of an operation, peval, that computes the value of a polynomial for some argument, given its list of coefficients. The operation expression beginning with op (short for operation) is the operation form that specifies the operation. The array of coefficients and the point at which the polynomial is evaluated are represented as parameters cs and x, respectively. The evaluation follows the Horner's rule through applying an anonymous operation specified as another operation form, op c v (v*x+c), along cs. Repetition is achieved through transforming this operation by means of reduce. Since reduce processes the array backwards, cs is reversed to compensate for that.

Having defined peval as above, the expressions peval (2 3 -5 1) 2 and (2 3 -5 1) peval 2, corresponding to 2x³+3x²–5x+1 at 2, both yield 19. A partial application of peval may be used to obtain a specific operation that evaluates a particular polynomial, so that e.g. defining pe is (2 3 -5 1 peval), the expression pe 2 yields 19.

A number of operation transformers predefined in Nial provide patterns of control structuring, array traversal, operation distribution across arrays, and other meta-operation utilities. This brings a strong point-free (combinatory) programming flavour to the language. Two distributional transformers are eachleft and eachright which modify a ‘dyadic’ operation to act on each of the items of its left or right argument, rather than on the whole argument. For example, 3 5 8 eachleft + 10 20 yields [13 23,15 25,18 28], and 3 5 8 eachright + 10 20 yields [13 15 18,23 25 28].

For an example of user-defined operation transformers, consider the following definitions imitating J's monadic and dyadic ‘hooks’:

mhook is tr f g op x (x f (g x))

dhook is tr f g op x y (x f (g y))

(A transformer is defined by a transformer expression starting with tr (or transformer in full) and having an operation expression as a body. Each of the expressions is parametrized: here, f and g are the operations on which the transformer acts, and x and y are the values to which those operations eventually apply.)

With these definitions, assuming that length is an operation computing the Euclidean length of a vector as defined above, mhook[/,length] is an operation that from a numeric vector returns an unit vector of the same direction; and dhook[+,x*] is an operation doing the basic computation in evaluating a polynomial, so the above definition of peval can be expressed using this operation in place of the (explicitly parametrized) λ-expression:

peval is op cs x (reduce dhook[+,x*] reverse cs)

Nial

Array Theory and Nial

Arrays and Programming

Functional Programming

Links of Relevance