1. Wanted: a Metalanguage

The last few years witnessed the emergence of a new class of formal languages: markup languages, such as HTML and XML. A text in such a language is a document structured in a certain way according to the rules of the language. The common feature of markup languages is the use of tags, which allows to treat a string of characters as a tree-like structure. The non-algorithmic nature of markup languages calls for a language (a metalanguage with respect to markup languages) for writing programs which would parse, check and, generally, make whatever use of the marked-up document was intended by its author.

We need a high-level programming language, convenient for working with markup languages, but universal in the sense that it is also convenient for general symbol manipulation. Further narrowing of the class of admissible data and algorithms is undesirable, because the software dealing with texts in markup languages will, no doubt, grow in volume, diversity and sophistication.

In addition to being universal, the language must be conceptually simple and easy for an unsophisticated user -- at least, as long as the user wants something relatively simple.

2. Refal

We believe that the language Refal [1] is the best choice for such a metalanguage. Refal (REcursive Functions Algorithmic Language) was conceived by the present author and implemented in the early 1970s in the Soviet Union, where it became widely known and used in the 1970s and 1980s for writing various translators and converters, as well as programs of Artificial Intelligence type. By the 1990s the existing implementations of Refal became obsolete, and no new implementations appeared, mainly because of the general crisis in the countries of the former Soviet Union. But Refal is a simple language, and the methods of its efficient implementation are well researched, so it would not be difficult to make a state of the art Refal System implemented in Java.

Refal is a purely functional language based on pattern matching. This means that:

Computation is always an evaluation of some function call.

A function is defined by a number of sentences (rules, or equations), where in the left side we see a pattern of the argument (i.e. an argument which may be only partially defined), whereas in the right side we see an expression which must be substituted for the function call in one step of computation. Presented in this way the program looks declarative: it is much easier to read and handle than a program presented as a sequence of commands (instructions) which include jumps of the execution point from one place to another.

3. Refal Compared with Other Languages

For some time after its inception, Refal was unique in combining these two features. In the 1980s a number of similar functional languages appeared, such as ML, Haskel, Miranda, etc. Comparing Refal with these languages we note, first of all, that it is the simplest language in the family. One of the design goals of Refal was to minimize the number of basic concepts which the user will have to understand and remember. In particular, variables in Refal can be only of the three basic data types (see below), and you cannot define new types. To distinguish between different classes of values, tags can be used. Thus, if x is a variable whose value defines a dog, then we keep it as (Dog x) throughout the program. In some contexts this is even more convenient than having type declarations as a separate part of the program, because it keeps type names close to values and variables. Then type-related conditions and operations may get their visually clear definitions in terms of patterns.

The most important difference between Refal and all known to us functional languages is the fundamental data type used for manipulation of symbolic information. Refal uses R-expressions (Refal expressions); other languages use lists, or S-expressions.

Lists were first introduced in the language Lisp and became widely used in theoretical computer science. A list is a slightly restricted S-expression, while S-expression is a binary tree. Lisp's lists are not exactly lists as we understand it intuitively. When we speak of a list of three elements A, B, and C, we think of it as a chain A-B-C, which you can read from left to right or right to left. Not so with lists of computer scientists. Here a list is a skew binary tree where the list's elements make up the tree's rightmost path from the root. Symbolically, the list above must be seen as A -> B -> C. You cannot read it from right to left. To locate the last element you must start from the root A and pass the whole list. To sum up, such widely used data structure as string cannot be adequately represented in terms of Lisp's lists.

In Refal we allow a genuine concatenation of elements, which creates strings. This is achieved by representing the data in the computer with references in two directions: A <--> B <--> C. Therefore, the user can see his data as printed on paper or shown on the screen (i.e. ABC in our example), because whatever he can do on paper, he also can do in the computer.

Besides concatenation, Refal allows embracing an expression in parentheses. This creates tree-like structures with an arbitrary number of children of a node. For instance, (A B (C) D) may be understood as a tree where the root has 4 children: A, B, (C), D; (C) is a node with one child C; and A, B, C, D have no children; they are called leaves.

The syntax of Refal expression is very simple. A symbol is a unit which is not decomposed into parts. It is a leaf when an expression is seen as a tree. A term is either a symbol or an expression in parentheses. An expression is a string of symbols and terms, possibly empty. Accordingly, there are three syntax types of variables: symbol variable (it has prefix "s."), term variable (prefix "t."), and expression variable (prefix "e.").

It must be noted that parentheses in a Refal program are not characters, but special symbols that are represented in the computer in such a manner that the location of one parenthesis contains a reference to its pair, so that we can both enter parentheses, and jump over the parenthesized subexpressions. A parenthesis which is a character appears in quotes, as all other characters, so that it cannot be taken for a "genuine" Refal parenthesis.

4. Two small Programs in Refal

As an example of a simple Refal program let us define function Palindrome as a predicate telling us whether a string of letters is a palindrome (i.e. reads the same from left to right and right to left):

Palindrome {

       s.1 e.x s.1 = <Palindrome e.x>;

       s.1 = True;

             = True;

}

A call of function F with the argument Arg is written as <F Arg>. The pattern of the argument in the first sentence, if put in words, is: the argument starts and ends with the same symbol. Note that this pattern is not translatable into Lisp or any language based on lists. To define this function in Lisp, the argument must be first reversed and then compared with the original list. This is clearly much less efficient than our program (which may give answer in one step).

The second and the third sentences tell us that a string consisting of one symbol and an empty string (it is allowed in Refal) are palindromes. The sentences are tried in the order in which they are listed: this transforms a declaration into an algorithm. Hence the last sentence in the definition of Palindrom must be read: If none of the above sentences is applicable, then the answer is False. The last sentence here is always applicable, because e.x stands for an arbitrary argument.

Consider a simple example of a text editing problem. We want a function Fab which changes every 'a' to `b':

Fab {

      'a' e.x = 'b' <Fab e.x>;

       s.1 e.x = s.1 <Fab e.x>;

       (e.y)  e.x = ( <Fab e.y> ) <Fab e.x>;

       = ;

}

5. Mapping XML on R-expressions

The first markup language, HTML (HyperText Markup Language) emerged in the context of the Internet, and it has been used in this capacity ever since. In a modified and generalized form it gave birth to XML (eXtensible Markup Language), and it is believed to become soon, if not have already become, the universal standard for representing structured documents of any kind. So, we concentrate on XML.

To separate a substructure from the rest, XML uses two markers: <TAG...> on its left end and </TAG> on the right side. Here TAG is a string of characters referred to as tag. The dots indicate that some optional information about the substructure may be put there. Substructures may be nested or concatenated like characters in a string.

The Refal programmer immediately recognizes (and welcomes!) the familiar structure of a Refal expression, where <TAG...> plays the role of a left parenthesis, and </TAG> that of the right one. To use Refal on XML, we first convert the input text into a Refal expression. This is a simple one-pass procedure, an important part of which is transformation of tags into Refal parentheses paired according to the well-known simple rules. This makes a tree from a string. Thus, the input transformation also plays the role of parsing and may give out error messages. The details of the input transformation may vary, depending on the preferences of the user. The general principle is:

organize semantically significant substructures by using parentheses.

Listing 1. An XML document

After transformation into a Refal form it becomes:

Listing 2. The document from Listing 1 formatted as an R-expression

We have used the following rules of transformation (presented rather informally and incompletely).

An XML term of the form <Tag properties-list> content </Tag> becomes the Refal term ((Tag[properties-list]) [content]), where square brackets indicate that the inside is subject to further transformation. Symbolic names, like Tag, are distinguished in Refal by starting with a capital letter. Strings are delimited by single or double quotes.

Properties-list in XML is a list of properties, each of the form: property-name = "property-value" where property-name is a symbolic name, and property-value is a string of characters. In Refal it becomes: Property-name Is ("property-value"). We enclose the property-value in parentheses for easier parsing. Properties-list may be empty.

Strings in XML enter documents in their "natural form", without quotes. In R-expressions we enclose them in quotes. Blanks may be freely used for better readability.

One can see that the result of the input transformation, which will be dealt with by Refal programs, is very close to the original XML text, and is no less readable. The inverse transformation of a qualifying R-expression into an XML document is as simple and fast as the direct transformation.

As an example of processing XML in Refal consider this task: Compile the list of the tags in a given document for which a certain property named Property has the value True. Let the name of the function which does the job be Taglist. Here is the program for it:

На начало

6. Comparison with XSL

but an input for some interpreter. It is presented in Listing 4. The Refal text is a program ready for execution; see it In Listing 5.

The next two terms are tagged as Name and Description. They show the strings associated with these tags:

((Description) "My grandma's favorite (may she rest in peace).")

In Listing 5 we generalize this as

((Name)e.name) ((Description) e.descr)

Now it is time to start the construction of the right side. We consult the desired output in Listing 3 for the standard beginning of the HTML format, and abstract from specific values of variables:

e.descr

<Xh e.on>

'</HTML>' ;

The left side of the second sentence has the already familiar structure:

((Ingredients) e.table) e.on =

But before including in the right side the four lines we are required to include the printout 'Ingredients' and the HTML element TABLE which contains the record of the names of the columns in the table:

Now we take out the creation of the table as a job for a new function

Table, and do not forget to close the TABLE element:

<Table e.table>

'</Table>'

The definition of Table proceeds along the same lines as with Xh. Inspect the first line in the input (Listing 2):

((Item) 'lime gelatin')

Generalize it by replacing parameters "box", 1, and 'lime gelatin' by e.unit, e.qty and e.item, respectively, and do not forget to put e.on for further lines -- you have the left side of the first sentence of function Table.

((Item e.option) e.item) ) e.on =

На начало

На начало

На начало