cjoslyn@bingvaxu.cc.binghamton.edu (Cliff Joslyn) (12/04/90)
Refal Systems Inc. has released a new implementation of
the programming language REFAL. The REFAL-5 package includes
a textbook on Refal and the software for IBMATXT, or
Macintosh (program interface only). A powerful tracer-debugger
is also included.
REFAL (for REcursive Functions Algorithmic Language) is a
functional programming language oriented towards symbol manipulation:
string processing, translation, artificial intelligence.
Refal combines mathematical simplicity with practicality
for writing big and sophisticated programs. For example,
the 'supercompiler' described in [V.Turchin, The concept of a
supercompiler, ACM Transactions on Programming Languages and
Systems, vol. 8, pp. 292-325 (1986)] was written in Refal;
that paper also includes a concise definition of Refal.
Refal is one of the oldest members of the family of functional
programming languages. It was first implemented in 1968 in Russia,
where it has become a language of choice for work in artificial
intelligence; in a recent review of Soviet systems of algebraic
manipulation eight systems were written in Refal
and only one in Lisp.
In the textbook on Refal you will find examples of Refal programs
of the following types:
1. Simple string manipulation: editing text lines,
translating words, etc.
2. Work with trees and graphs.
3. Familiar sorting algorithms.
4. Problem solving, artificial intelligence ('Missionaries and Cannibals',
a problem used in many texts on AI).
5. Translation of an arithmetic expression into a program for
a one-address machine.
How does Refal compare to the more familiar Lisp and Prolog?
Consider the textbook example of a function which computes the
intersection of two sets represented by lists of symbols (Lisp's atoms).
Written in Lisp (in its pure form, i.e. without assuming that somebody
wrote for you all necessary built-in functions) it is:
(define isect (lambda (set1 set2)
(cond ((null set1) nil)
((member (car set1) set2) (cons (car set1)
(isect (cdr set1) set2)))
(T (isect (cdr set1) set2)) )))
(define member (lambda (atom set)
(cond ((null set) nil)
((equal atom (car set)) T)
(T (member atom (cdr set))) )))
The same program written in Refal:
Isect { ()(e1) = ;
(s1 e2)(e3 s1 e4) = s1 <Isect (e2)(e3 e4)> ;
(s1 e2)(e3) = <Isect (e2)(e3)> }
Refal is extremely simple. You can, probably, read the above
definition without having ever heard about Refal. You only need to
know that angular brackets enclose function calls, while parentheses,
are used in their usual role, creating structured objects (expressions).
In particular, function arguments are separated using parentheses.
Unlike Lisp, Refal is based on pattern-matching. There are three
sentences in the above definition of Isect, each defining one case
of the argument in the form of a pattern. The first sentence states that
if the first argument is empty and the second is anything
(the free variable e1, some expression), then the result is empty.
The second sentence picks up the first symbol in the first argument
(the variable s1, some symbol) and finds the same symbol somewhere
in the second argument. The third sentence will be used if the preceding
two do not apply.
Prolog, of course, also has built-in pattern-matching. If what you want
is to get answers to simple questions from a data base, you may, probably,
be quite satisfied with Prolog. This is not so, however, if you have to
program, i.e. to write procedures. 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; it makes them easier to test
and debug. Consider another textbook example: a program for formal
differentiation. In Refal we define the function <D e.Expr s.Var>
to take the derivative of e.Expr over s.Var by simply listing
the possible forms of the argument and writing the answers,
as in a calculus textbook:
D {sX sX = 1;
sC sX = 0;
tU'+'tV sX = <D tU sX>'+'<D tV sX>;
tU'-'tV sX = <D tU sX>'-'<D tV sX>;
... etc. }
Compare it with the analogous program in Prolog:
d(X,X,1)
d(C,X,0) :- atomic(C).
d(U + V,X,A + B) :- d(U,X,A), d(V,X,B).
d(U - V,X,A - B) :- d(U,X,A), d(V,X,B).
... etc
We think about differentiation as a procedure. But with Prolog
we have to make two additional steps to write the program.
First we translate the procedure of differentiation into a relation
between input and output. Then we interpret the list of relations
as a procedure. This doing and undoing is absolutely unnecessary.
One of its results is the introduction of auxiliary variables,
in which we have no need when programming in Refal.
In addition to the these differences, 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 a 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 Refal are a high modularity and an inherent
'structuredness' of programs (you would not know how to incorporate
GOTO in Refal even if you wished). The very simple semantics of Refal
facilitates tracing and debugging. The tracer-debugger of REFAL-5
can catch the moment when the argument of the evaluated function
matches any specified pattern.
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 excellent
as a language for research in theory of programming languages
and program transformation.
To order REFAL-5 by mail, write to:
REFAL SYSTEMS Inc
188 Hiawatha Blvd.
Oakland, N.J. 07436
At present it is available at the low price of $25 (check or
money order) if within the country, and $30 (in USA$ please)
to mail abroad. The package includes a textbook-manual and a system
diskette for IBM/XT-AT or Macintosh (command interface only);
indicate which one you want.
--
O------------------------------------------------------------------------->
| Cliff Joslyn, Cybernetician at Large, cjoslyn@bingvaxu.cc.binghamton.edu
| Systems Science, SUNY Binghamton, Box 1070, Binghamton NY 13901, USA
V All the world is biscuit shaped. . .