cjoslyn@bingvaxu.cc.binghamton.edu (Cliff Joslyn) (11/30/89)
NEW PRODUCT ANNOUNCEMENT
REFAL-5 is a new implementation of the programming language Refal
released by Refal Systems Inc. The available package combines a
compiler, executor, and tracer-debugger with an introductory text and
manual.
REFAL (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 is REFAL. It was first implemented in
1968 in Russia, where it is now a dominant Artificial Intelligence
programming language. REFAL combines mathematical simplicity with
practicality for writing large, sophisticated programs. For example,
the `supercompiler' (a program optimizer/transformer) described in [1]
was written in REFAL. That paper also includes a concise definition of
REFAL. The features included into REFAL-5 have been tested by time.
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. Working with trees and graphs.
3. Familiar sorting algorithms.
4. AI type problem solving (such as `Missionaries and Cannibals').
5. Translation of an arithmetic expression into a program for
a one-address machine.
REFAL compares very favorably 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 set1 set2)
(cond ((null set1) nil)
((member (car set1) set2) (cons (car set1)
(isect (cdr set1) set2)))
(T (isect (cdr set1) set2)) ))
(define (member 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 to create 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 says 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 be quite
satisfied with Prolog. But this is not so 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. Take another
textbook example: that of 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, and then we interpret the list of relations as a procedure.
This doing and undoing is absolutely unnecessary. One of the results is
the introduction of auxiliary variables, of 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
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 exactly what you
need for symbol manipulation and Artificial Intelligence.
Other features of REFAL are a high modularity and an inherent
`structuredness' of the program (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 REFAL-5 system includes a
powerful tracer-debugger, which, among other things, can catch the
moment when the argument of the evaluated function matches any given
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 an excellent choice as
the language for research in theory of programming languages and program
transformation.
You can order REFAL-5 by mail. Write to:
REFAL SYSTEMS Inc
188 Hiawatha Blvd.
Oakland, N.J. 07436
At present it is available at the price of $20 (check or money order),
just enough to cover our production and mailing costs. The package
includes a textbook-manual and a system diskette for IBM/XT-AT or
Macintosh (command interface only); indicate which one you want.
Reference
[1] V.Turchin, The concept of a supercompiler, ACM Transactions
on Programming Languages and Systems, vol. 8, pp. 292-325 (1986).
--
O------------------------------------------------------------------------->
| Cliff Joslyn, Cybernetician at Large, cjoslyn@bingvaxu.cc.binghamton.edu
| Systems Science, SUNY Binghamton, Binghamton NY 13901
V All the world is biscuit shaped. . .