Refal: the Language for Processing XML Documents

Valentin F. Turchin

abstract

Refal (for Recursive Functions Algorithmic Language) is a programming language for manipulation of symbolic information. We argue that Refal is the best language for processing documents in XML, HTLM, and similar formats, because it has the following unique combination of features:

Refal is a functional language. A program in Refal defines an algorithm, but looks as (and is, indeed) a declaration of certain relations between function calls.

Computation is directed by pattern matching, which is very convenient visually, and allows to distinguish easily between different cases of arguments.

Unlike other known to us functional languages, Refal has R-expression as its basic data structure. An R-expression can represent both tree-like structures, and strings of symbols or terms which can be processed both from left to right, and from right to left. The basic data structure of XML is, essentially, a special case of R-expressions. R-expressions are convenient and familiar to everybody who remembers expressions of high school algebra.

Refal has a short list of basic concepts and a simple syntax. Hence it is fast to learn.

Refal is universal as a language for processing symbolic information. It can stay as the only needed language of programming at all stages of the work with XML documents: from simplest one-to-one substitutions to sophisticated Artificial Intelligence systems.

A supercompiler for Refal is available. It implements a powerful method of program optimization.

In this paper we provide a brief informal description of Refal with simple examples of programs. Then we define the mapping of XML texts on R-expressions and vice versa. One can see how simple it is. Then we pick up a specific text in XML with a program in XSL which translates it into HTML. We show how an equivalent program in Refal can be, step by step, written. The Refal program is shorter than that in XSL and presents the algorithm in a clearer form, provided, of course, that one knows the basic Refal notation.