Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!elroy.jpl.nasa.gov!usc!zaphod.mps.ohio-state.edu!wuarchive!psuvax1!rutgers!mcdchg!usenet From: cjoslyn@bingvaxu.cc.binghamton.edu (Cliff Joslyn) Newsgroups: comp.newprod Subject: REFAL-5: REcursive Functional Algorithmic Language Message-ID: <51610@mcdchg.chg.mcd.mot.com> Date: 4 Dec 90 15:03:01 GMT Sender: usenet@mcdchg.chg.mcd.mot.com Followup-To: poster Organization: SUNY Binghamton, NY Lines: 149 Approved: usenet@mcdchg.chg.mcd.mot.com 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 ; (s1 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 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 = '+'; tU'-'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. . . Brought to you by Super Global Mega Corp .com