Contents

2.5. Refal Advantages

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. img32.gif (102 bytes)


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