Introduction

Refal Plus is a dialect of the programming language Refal.

Refal (Recursive Function Algorithmic Language) was designed by V.F.Turchin as a tool for describing the semantics of other algorithmic languages [Tur1986]. Later, when reasonably efficient Refal implementations had been created [BsR1977], [Rom1987a], Refal was used as a symbol manipulation language in such fields as computer algebra, compiler and interpreter writing, artificial intelligence, etc.

The principal data type in Refal are arbitrary trees, referred to as ground expressions. In programs and text files ground expressions are represented by linear sequences of symbols and parentheses, with parentheses being properly paired. Symbols represent such elementary data objects as characters, words, numbers and references to objects).

The principal means of analyzing and accessing ground expressions is pattern matching. Refal patterns may contain symbols, parentheses, and variables. If matching a ground expression against a pattern succeeds, the pattern's variables are bound to the corresponding components of the ground expression, which can be used later for building new ground expressions.

A Refal program may contain function definitions. Each function takes as argument a ground expression and returns as its result a ground expression. Functions can call each other. In particular, a function can call itself (directly as well as indirectly, through other functions), in which case the function is said to be recursive. And it is recursion that is the princi- pal way of structuring the control in Refal programs.

Refal Plus has been developed to take into account the experience gained from the design, implementation and use of such languages as Basic Refal [BsR1977], Refal-2 [Rom1987a], Refal-4 [Rom1987b], Refal-5 [Tur1989], and RL [Rom1988].

As compared to the other Refal dialects, Refal Plus provides the following features.

More advanced modules

Each module is divided into two components: the interface of the module and the implementation of the module. The interface contains the parts of the module that may be visible in other modules, whereas the implementation contains the parts of the module that are invisible in other modules.

The interface of a module may contain any declarations, which means that not only function declarations may be exported, but also declarations of constants and objects (such as boxes and i/o channels). When a function declaration is exported, not only the function name becomes visible, but also the formats of the function's arguments and results, which enables the calls to the function to be checked for correctness at compile time, rather than at run time.

For a module to be compiled, there must be known the interfaces of other modules, rather than other module's implementa- tions. Thus, a module can be compiled even if the implementations of other modules have not been created. Besides, the fact that a module's implementation has been modified does not necessitate recompiling the modules importing that module. Thus arbitrary intermodule dependencies are allowed (including the cyclic ones).

Static declarations of dynamic objects

All objects that can be created dynamically at run time (such as i/o channels, boxes, vectors, and tables) can also be declared statically, in which case they are given symbolic names to be used in the program text for referencing the objects.

Function declarations

Each Refal Plus function is declared as either failing or unfailing one. The evaluation of a call to a failing function can result in returning a special "failure" value. For example, all predicate functions return either an empty ground expression or a "failure". On the other hand, an unfailing function never returns a "failure".

It should be noted that earlier Refal dialects enabled the programmer to define only unfailing functions.

One more feature of Refal Plus is the possibility of defining functions accepting several arguments and returning several results. The number and type of a function's arguments is said to be the function's arity, whereas the number and type of the function's results is said to be the function's co-arity.

The arity and co-arity of a function are specified by declaring the function's input and output formats, which are patterns containing symbols, parentheses, and variables. The input format imposes syntax restrictions on the form of the calls to the function, whereas the output format imposes restrictions on the contexts in which the calls to the function may appear. By stripping the input format of all the symbols and parentheses, we get the variable sequence describing the function's arity. By stripping the output format, we get the description of the function's co-arity.

The explicit function format declarations allow many errors to be detected at compile time, and also reduce the costs of evaluating the function calls.

It should be noted that earlier Refal dialects assumed each function to accept a single argument and to return a single result.

Failure and error trapping

If evaluating a Refal Plus construct terminates, it either succeeds, fails, or produces an error.

If the evaluation succeeds, the result returned by the construct is a ground expressions. (The format of the returned expression is always known in advance, which permits Refal Plus implementations to represent the result by a tuple of ground expressions.)

If the evaluation fails, the result returned is a "failure".

If the evaluation produces an error, the result returned is an "error" value containing a ground expressions (which, usually, is an error message).

Refal Plus provides several constructs enabling failures and errors to be caught and analyzed.

Input/output of ground expressions

Refal Plus provides functions that enable programs to input and output character strings as well as character representations of ground expressions, the conversion of ground expressions into character sequences and vice versa being done automatically.

Operations on boxes, vectors, and tables

Refal Plus provides a way to deal with dynamically created objects such as boxes, vectors, strings, and tables. Boxes are treated in the same way as in Refal-2, whereas vectors, strings, and tables are a feature of Refal Plus.

A box is an object containing a ground expression.

A vector is an object containing a finite sequence of ground expressions.

A string is an object containing a finite sequence of characters.

Boxes, vectors, and strings can be accessed via reference symbols pointing to these objects. Refal Plus provides functions for creating, accessing and updating boxes, vectors, and strings, including accessing and updating individual components of vectors and strings.

A table is an object containing a finite set of keys, each key associated with its value. The keys as well as values are ground expressions. A table can be accessed via reference symbols pointing to the table. Refal Plus provides functions for creating and copying tables, for getting the value associated with a key in a table, and getting all the keys contained in a table. Essentially, a table is a representation of a function with the finite domain.

"Vector" representation of ground expressions

The present implementations of Refal Plus are based on the "vector" representations of ground expressions [AbR1988], which allows the copying of ground expressions to be reduced to copying a pair of pointers to the expression's representation.

The cheapness of the copying operation permits Refal programs to be written in functional style, whereas the earlier Refal implementations forced the programmer to be careful with copying, thereby inducing him/her to stick to the imperative style.

The objects that have become inaccessible to the program are automatically destroyed by the garbage collector provided by the Refal Plus implementations.