Xref: utzoo comp.ai:5125 comp.theory:84 comp.lang.prolog:2191 comp.lang.lisp:2488 comp.misc:7513 comp.lang.scheme:940 comp.edu:2711 comp.lang.misc:3707 Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!uwm.edu!rpi!leah!bingvaxu!cjoslyn From: cjoslyn@bingvaxu.cc.binghamton.edu (Cliff Joslyn) Newsgroups: comp.ai,comp.theory,comp.lang.prolog,comp.lang.lisp,comp.misc,comp.lang.scheme,comp.edu,comp.lang.misc Subject: Announcing REFAL (REcursive Functions ALgorithmic language) Keywords: programming languages, artificial intelligence, functional programming Message-ID: <2680@bingvaxu.cc.binghamton.edu> Date: 29 Nov 89 22:02:43 GMT Organization: SUNY Binghamton, NY Lines: 148 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 ; (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 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 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, 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. . . Brought to you by Super Global Mega Corp .com