introduction


Refal (for REcursive Functions Algorithmic Language) is a functional programming language oriented toward symbol manipulation: string processing, translation, artificial intelligence. Functional programming languages enjoy well-deserved popularity nowadays. One of the oldest members of this family (first implemented in 1968 in Russia, where it has been widely used ever since), Refal combines mathematical simplicity with practicality for writing big and sophisticated programs. * Refal-5 is a dialect of Refal developed at the City College of New York. The features included in Refal-5 have been tested by time.

In this guide you will find examples of Refal programs of the following types:

As with any programming language, implementations of Refal-5 may differ in some details. Our examples are written for the implementation of Refal-5 developed by Refal Systems Inc.; it will be referred to simply as ``the Refal system''. This implementation focuses on the essential features of the language, with only a basic system-user interface, yet much attention has been paid to debugging facilities. Reference sections summarize the most important features of our Refal system.

Unlike Lisp, Refal is based on pattern matching. Due to that, a typical program in Refal is two or three times shorter, on the average, than the analogous program in Lisp, and much more readable. When compared with Prolog, Refal is conceptually simpler. Its pattern matching works in the forward direction, not backwards (starting from the goal), as in Prolog. This is a more natural approach to writing algorithms and makes them much easier to test and debug.

Furthermore, there is an important difference between data structures of Refal and most other high-level languages. The basic data structures of Lisp and Prolog are lists which can be read only in one direction. Refal uses more general structures. You can build and read them from left to right and from right to left, and of course, go down and up by parentheses. This is a great relief for the programmer. Refal gives you freedom and convenience in creating data structures while using only mathematically simple control mechanisms - pattern matching and substitution. This is what you need for symbol manipulation and artificial intelligence.

Other features of the language are: simplicity, high modularity, an inherent structuredness of the program (you would not know how to incorporate GO TO in Refal, even if you wished to). The very simple semantics of Refal facilitate tracing and debugging. The Refal system includes a powerful tracer-debugger which can, among other things, catch the moment when the argument of the evaluated function matches any given pattern.

Partial evaluation of function calls has lately become an important type of program transformation. Refal-5 includes a feature (the ``freezer'') which is specially designed for efficient partial evaluation.

Because of its fundamental simplicity, Refal is an excellent choice for introducing students to functional programming languages. It has been taught at the City College of New York for several years with a very positive response from students. Refal is also an excellent choice as a language for research in theory of programming languages and program transformation. For a mathematically oriented person, Refal provides all the power of a practical programming language, yet eliminates the need to learn a lot of small details, for which many other programming languages are notorious.


Footnotes:

  1. See e.g., V. Turchin, The concept of a supercompiler, ACM Transactions on Programming Languages and Systems, vol. 8, pp. 292-325 (1986). This paper also includes a short definition of a simplified version of Refal.