NIAL(ID:1242/nia001)for Nested Interactive Array Language Mike Jenkins, Queen's University, Canada. A multi-paradigm language that combines aspects of both functional and procedural languages. Nial is a hybrid language combining a functional array language based on Trenchard More's mathematical treatment of nested arrays, with a procedural language with a familiar control structures. It has a rich set of language primitives that make it easy to rapidly develop loop-free data-driven algorithms. Structures: Related languages
Samples: References: NIAL is a fascinating new computer language that deserves the attention of serious programmers. The name NIAL is an acronym for Nested Interactive Array Language. It is based on the nested-array data model of Dr. Trenchard More Jr. of the IBM Cambridge Research Center, Cambridge, Mass., who has designed a language that both increases programmer productivity by combining the strengths and overcoming the deficiencies of languages such as APL, LISP, and PROLOG and facilitates rigorous proofs of the correctness of programs. NIAL has only one kind of data object: the multidimensional rectangular array of arbitrary length and dimension, each element of which may be any of several data types or another nested array. The size, dimension, and depth of nested arrays are limited only by the bounds of hardware. Q'NIAL is an interpreter for NIAL developed at Queen's University, Kingston, Ont., by a team headed by Dr. Michael Jenkins, with the participation of Dr. More. NIAL has a rich set of predefined nested-array operations. Some of them act like the operations of APL when the arguments are non-nested arrays of elements of the same data type or like the operations of LISP when the arguments are lists. However, one of the main contributions of the nested-array model is to extend such operations to general tree structures with data elements of different types in a way that is both elegant and powerful. A recent extension to APL called APL2 implements nested arrays, but because APL2 and its operations were not designed around the nested-array model from the outset, they lack the elegance and comprehensiveness of NIAL. Within the IBM community there is a growing interest in NIAL as a replacement for APL and LISP. NIAL does not use a special character set the way APL does or require special terminals to enter or display it. NIAL notation consists of strings of printable ASCII characters separated by white space, making it much more readable. Q'NIAL has both an interactive mode, in which statements execute immediately when the return key is hit, and an indirect mode, in which programs are written using any editor and loaded from a text file. As in APL, the Q'NIAL prompt is five blanks, so that in the examples that follow, the user's input begins at the sixth column, and the Q'NIAL response begins at the first column of the line below. In NIAL, there are only three kinds of syntactic construct: the expression and array definition, the operation and operation definition, and the transformation and transformer definition. An expression is a sequence of operations and arrays which evaluates to an array. Q'NIAL is like APL in permitting both an infix and prefix syntax for operations and their arguments. 23 + 78 infix 101 + 23 78 prefix 101 sum 15 89 73 32 209 prefix, more than two arguments Notice, for example, how sum is a synonym for the " + " operation. One has to be careful with infix expressions, however, because of the way Q'NIAL will try to interpret arguments as arrays. 2 3 sum 4 5 68 t adds corresponding elements to each other 2 sum 3 4 5 567 adds 2 to each of the elements of the array An array name is assigned thus: Agets5 67eachsum 1 2 3 186 A 186 can also use for' 'gets" An operation name is defined using either a simple binding: such as: sec IS first rest sec 4 5 6 7 5 which is similar to car cdr in LISP. Or, a lambda-calculus syntax: where the expression uses only the parameters in the preceding list, which stand for nested arrays, and operations that have been previously defined. Thus we might have: double IS OP x {2 *x} double 3 6 OPERATION can be abbreviated NIAL is an extensible language. J Writing a program consists of successively defining operations, the final operation being the program. In this respect, NIAL is much like Forth. A transformer operates on an operation to yield a new operation. Thus the predefined transformer EACH causes the operation to act on the elements of the array arguments rather than on the arrays: sum(2 3)(4 5) 6 8 adds corresponding elements of each array eachsum(2 3)(4 5) 59 adds elements of each array A transformer is defined much like an operation, either binding a name to a composition of previously defined transformers: EACH2 IS EACH EACH or using a lambda form: < transformer name> IS TRANSFORMER < list of parameters > ( where the parameters stand for transformers or operations previously defined, and the composite is a juxtaposition of those parameters which represents the composition of the transformers and oper-ationsthey stand for. But note that the composite is enclosed in parentheses, not braces. Thus we have: TWICE IS TRf(ff) TWICErest5367 67 TRANSFORMER can be abbreviated And a more interesting example in Listing 1. In this example, operation CART on two arrays returns an array composed of pairs of elements from each array argument. Thus: 2 3cart'abc' 2a 2b 2c 3a 3b 3 c As in APL, Q'NIAL reserves for the user an area of memory called the work space, which holds the currently defined array variables, operations, and transformers. The size of this work space is fixed when the user boots up Q'NIAL, but that size is only bounded by hardware. The user can save the contents of this work space using the command: save " where filename must be preceded by a double quote. This saves it as a compressed, encoded file named < filename > . nws. To load this file into the current work space, the command is: load " and the environment that existed when the work space was saved is restored. This is an especially convenient feature for persons who use the language in a development mode on a variety of concurrent projects. Beginning programmers can start using NIAL easily. It has been used with great success both to teach elementary programming concepts and to do advanced research in programming theory. APL is also easy for beginners, but they often bog down as they get into APL's more advanced features. The APL character set, a convenience to those who know what they are doing, contributes to that. Newcomers to NIAL are likely to find themselves progressing to advanced features more rapidly than they would in most other computer languages. Even advanced APL programmers often find . themselves unable to understand their own code a few days after they have written it. NIAL code, if written using reasonably self-documenting names, makes the structure of a program much easier to discern. An unstructured program, as that term is applied to other languages, is practically impossible in NIAL. The main area of potential trouble arises from array elements that reference other array elements since NIAL supports trees but not general graph data structures. This kind of trouble can be avoided by appropriate programming techniques. The operations used for logic programming in PROLOG, such as substitution, unification, and resolution, are simple functions in release 1 of Q'NIAL. These logic operations are being implemented as primitives in release 2 to improve performance, and a compiler companion to the present interpreter should be available shortly after this article appears. Although NIAL is a fairly new language, it is rapidly gaining acceptance for a variety of applications, especially those for which the nested array is the preferred model for representing data. These include applications like games and theorem-proving that involve deep-nested decision trees, data base management where the data does not fit the first normal form restriction of the relational model, numerical analysis and simulation, statistical analysis, CAD/CAM, graphics, and CAT. It has been used for VLSI tool development, and I have used it to simulate global weather and explore the nuclear winter scenario. I have found it to be an excellent choice for rapid prototyping of complex programs, including those which I may later want to rewrite in C, in whole or in part. NIAL can be used like a procedural, record-oriented relational data base language by restricting oneself to the use of non-nested arrays, but its operation in this mode is more like a spreadsheet than like SQL/DS or dBASE III. In current release 1, an array element of type phrase is limited to 255 characters, but future releases will relax that restriction, permitting array elements to consist of text of great length. Since NIAL can use almost any editor, supports graphics, and can make use of other programs on the system, it can be used as a kind of sophisticated integrated package of the kind that are increasingly popular. I use it that way on a daily basis, in preference to most other spreadsheet programs. It does not yet, however, provide a scrolling display that permits the user to browse around an array using the cursor keys or edit array elements on which the cursor falls. A group at IBM is working on an extension to NIAL to permit this. They are writing this extension in Q'NIAL. The traditional AI language has been LISP. However, increasing dissatisfaction with that language has led some AI workers, like those with the Japanese Fifth Generation Project, to turn toward alternatives such as PROLOG, which provides several logical operations as primitives and facilities for manipulating large amounts of data. Unfortunately, PROLOG is an awkward language, requiring programmers to be constantly aware of the complex search and backtracking logic used by PROLOG when they write code. In NIAL, the control component of the logic system is built around and-or tree goal reduction. The generation of these trees is performed using a heuristic search strategy which permits a mix of depth-first and breadth-first search techniques. Since this method considers all possible paths using disjunction, backtracking is not necessary in describing control structures. The result is a much more powerful and easily understood logic program. NIAL also provides much more powerful facilities for handling large quantities of data. This is best appreciated on a system that supports virtual memory with demand paging, such as UNIX System V.tm Another problem with LISP is its lack of portability. It is usually implemented as an interpreter and suffers from the usual performance limitations of interpreters and a proliferation of dialects.. Some vendors have, of course, implemented it as a compiler on special hardware designed to optimize its performance and equipped it with an extensive environment of libraries and utilities that supports AI development. Against this, Q'NIAL offers congenial environments like UNIX and fairly easy translation of existing libraries of LISP code. For those who like the LISP environment, an implementation on a LISP machine is contemplated. Q'NIAL itself has been designed to be easily ported and interfaced to a variety of front-ends. There is a graphics package for the IBM PC. One of the problems on which I am working using Q' NIAL is data base management of fuzzy data?that is, data that is not either valid or invalid but which is imprecise or uncertain to some degree. Many workers in AI have recognized this problem as essential to the development of expert systems. Such fuzzy data does not fit the relational model, and efforts to do queries and manipulation of fuzzy data in ways similar to those used in conventional data base management systems often result in undesirable behavior. Q'NIAL offers tools that facilitate solutions in this area. Some misunderstanding has arisen concerning whether NIAL uses dynamic scoping, in which the value of a function is defined when it is called, or lexical scoping, in which the value and the scope of the function are defined when the function is defined. The first method is easier to implement, and is used in APL and older versions of LISP, like Franz LISP. Dynamic scoping can be simulated using lexical scoping but not the other way around. Newer versions of LISP, like Scheme, , use lexical scoping, and so does Q'NIAL. This can be seen by putting a definition inside a block. That definition can see variables global to that block, but those names are not visible to a routine called by that block if it is not in the same scope. There is a growing consensus for lexical scoping. NIAL supports recursion, and a Q'NIAL program?or for that matter a program in any other language that can be loaded from a text file?can itself be treated as a nested array for manipulation by a NIAL program. A Q'NIAL program can modify itself and execute a modification of itself. It thus lends itself to applications like natural language analysis and automatic programming. Selfmodifying code has to be written carefully, however. Moving code containing local variables will conflict with lexical scoping. For this, the programmer should either make all variables global or use a lambda-free functional style. Q'NIAL is written in C and is being ported to a variety of machines. So far it has been ported to the IBM PC running PC-DOS, the IBM-PC/370, the IBM 4341 and 3031 running VM/CMS, and to several machines running versions of UNIX, including the IBM PC/Sritek 68000 board combination, the IBM-PC/AT, Spectrix, Fortune 32:16, AT&T 3B2, Plexus, Apollo, Cadmus, Masscomp, Sun, Pyramid, HP 9000, Perkin-Elmer, and the VAX/ 730/750/780 series. I have done the port to the Fortune 32:16 and plan to port to the Macintosh, Atari 520ST, and Commodore Amiga, among other systems. The size of the main program file of Q'NIAL version 3.04 is about 209K, and a minimally comfortable work space size is 128K, so a system running UNIX should have at least 512K of RAM. Some applications written in Q'NIAL may, of course, require a larger work space. Help files, which do not need to be resident in RAM, total more than 900K. For a further demonstration of NIAL's coding structure as implemented in the Sieve of Eratosthenes and the Quicksort program, see Listings 2 and 3. How much does Q'NIAL enhance programmer productivity? I do not find the unextended language as productive as a data base language like Progress"" for business applications since it does not come with all the predefined functions that Progress does. But NIAL can easily be extended into a language that would be superior in this area, and I do find it superior in its unextended state to most other languages for other applications. Object-oriented languages are potentially more productive if provided with an extensive library of predefined methods and classes. The extension of Q'NIAL into an object-oriented language would be fairly straightforward, in much the way Forth has been extended (and modified) into an object-oriented language called Neon,tm which is functionally similar to Smalltalk-80. In its present implementation, Q'NIAL is reentrant but not multiuser, and it has no facility for sharing data in a work space. Serious consideration is being given to providing Q'NIAL with external data files that would permit sharing. Also being considered is a signal interface that would permit messaging and use of Q'NIAL in an actor-oriented mode on an open system. One of the major design goals for Q'NIAL has been for use on parallel architectures. UNIX would probably not, however, serve as the operating system for such a machine. The allocation of processors among concurrent operations and subarrays would require tight coupling with whatever operating system was used. Q 'NIAL is a trademark of Queen's University, Kingston, Ont. NIAL Systems Ltd. has been formed to license Q'NIAL. Its addresses are 20 Hatter St., Kingston, Ont., CanadaK7M2L5, (613)549-1432, and P. O. Box 280, Alexandria Bay, N. Y. 13607-0280, (800) 267-0660. Starwood Corp., P.O. Box 160849, San Antonio, Texas 78280-3049, (512) 496-8037, is a distributor for versions ofQ 'NIAL on several machines on which it has done or will do the ports, including the Fortune 32:16, Macintosh, Atari ST, and Commodore Amiga. The company can furnish other versions or do special ports. in IEEE Software 3(01) January 1986 (Multiparadigm language projects) view details in SIGPLAN Notices 23(06) June 1988 view details in Computer Languages 14(1) view details in Restifo Mullin, Lenore M. et. al., (eds) "Arrays, functional languages and parallel systems" Kluwer Academic Publishers, Boston, MA, 1991 view details in [ACM] Proceedings of the 1993 ACM Conference on Computer Science March 1993 view details in [ACM] ACM Computing Surveys (CSUR) 30(2) June 1998 view details |