Refal(ID:595/ref001)

Recursive functional algorithms 

Recursive Functions Algorithmic Language. V. Turchin, Moscow ca 1972 (now at CUNY?).
Related languages
Refal => Sample   Influence
References:
  • S.A. Romanenko, V.F. Turchin: "REFAL compiler"; view details
          in Second Soviet All Union Computing Conference 1970 view details
  • Turchin, V. "Supercompiler System Based on the Language Refal" view details
          in SIGPLAN Notices 14(02) Feb 1979 view details
  • Basic REFAL and its implementation on computers CNIPIASS, Moscow, 1977, (in Russian). view details
          in SIGPLAN Notices 14(02) Feb 1979 view details
  • Turchin, Valentin F. "REFAL-5 programming guide and reference manual" New England Publishing Co., Holyoke 1989 view details Extract: Introduction
    Introduction

    Refal (for 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 (first implemented in 1968 in Russia, where it has been widely used ever since), Refal combines mathematical simplicity with practicality for writing big and sophisticated programs. * Refal-5 is a dialect of Refal developed at the City College of New York. The features included in Refal-5 have been tested by time.

    In this guide you will find examples of Refal programs of the following types:

    Simple string manipulation: editing text lines, translating words, etc.
    Work with trees and graphs.
    Familiar sorting algorithms.
    Problem solving, artificial intelligence ("Missionaries and Cannibals'', a problem used in many texts on AI).
    Translation of an arithmetic expression into a program for a one-address machine.
    As with any programming language, implementations of Refal-5 may differ in some details. Our examples are written for the implementation of Refal-5 developed by Refal Systems Inc.; it will be referred to simply as "the Refal system''. This implementation focuses on the essential features of the language, with only a basic system-user interface, yet much attention has been paid to debugging facilities. Reference sections summarize the most important features of our Refal system.

    Unlike Lisp, Refal is based on pattern matching. Due to that, a typical program in Refal is two or three times shorter, on the average, than the analogous program in Lisp, and much more readable. 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 and makes them much easier to test and debug.

    Furthermore, 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 what you need for symbol manipulation and artificial intelligence.

    Other features of the language are: simplicity, high modularity, an inherent structuredness of the program (you would not know how to incorporate GO TO in Refal, even if you wished to). The very simple semantics of Refal facilitate tracing and debugging. The Refal system includes a powerful tracer-debugger which can, among other things, catch the moment when the argument of the evaluated function matches any given pattern.

    Partial evaluation of function calls has lately become an important type of program transformation. Refal-5 includes a feature (the "freezer'') which is specially designed for efficient partial evaluation.

    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 a language for research in theory of programming languages and program transformation. For a mathematically oriented person, Refal provides all the power of a practical programming language, yet eliminates the need to learn a lot of small details, for which many other programming languages are notorious. External link: online copy
          in SIGPLAN Notices 14(02) Feb 1979 view details