As mentioned above, the major difference between Refal and Lisp, as well as other languages working with lists, is the data domain. Refal expressions are strings of terms which can be processed both left to right, and right to left. They are trees with an arbitrary and unfixed arity. Lisp's list is a special kind of a Refal expression. There are several reasons why I stubbornly use Refal in metacomputation (beyond the main reason, which I am trying to conceal: I invented it).
1. I hope that sooner or later the methods of metacomputation will be used on the
industrial scale for automatic development of big and fast programs. The efficiency of
algorithms is, as we very well know, tightly bound to data structure. I cannot imagine
that practical programmers will agree to abandon such an important data structure as
string. Limiting ourselves to lists, we throw overboard a huge set of efficient
algorithms.
2. As we saw in Section 2.2, Refal expressions allow generalizations that are
inexpressible with lists. This makes supercompilation easier and more efficient. Data
structures we use are, essentially, models of reality. More sophisticated data structures
allow us to express more subtle features of the medium. A language based on graphs would
have the same advantage over Refal as Refal has over a pure list-processing language.
3. When we create a metamachine for examining and controlling the operation of the
object machine, we often want to trace its steps in both forward and backward directions.
Histories of computation are naturally represented by strings of states. In Sec.3.1 I show how supercompilation can be enhanced by switching
from configurations of the computing machine to histories of computation by it. Moreover,
backward movement is part of the concept of supercompilation. It can be avoided, but not
without paying some price - in conceptual simplicity, if not in anything else. Languages
we use not only help express something we are doing; they suggest what we might do
further. It is not an accident that the concept of supercompilation first appeared in the
context of such a language as Refal.
4. Pure list-processing languages are good for programming in recursive style, but
poor when the algorithms are iterative. Meanwhile, we often face the situation where a
recursive algorithm is clear and elegant, but inefficient, so that we have to transform it
into an iterative form. In Lisp even a simple traversal without inverting the list is
impossible when we do it iteratively. Refal is equally at ease with both recursive and
iterative programming. 
The use of lists, though, is not without its own advantages. As a data structure for
analysis and manipulation, lists are simpler than Refal expressions, though in my view,
the difference is not significant. Another advantage is the simple fact that people in
computer science research have accustomed to this domain, and the languages based on it
are widely used. One balances these two sets of advantages according to one's priorities.
Contents
Next