Programming in Refal Plus

This chapter gives a step-by-step tutorial introduction to the language Refal Plus and provides a diverse group of program examples demonstrating some of the ways in which Refal Plus can be used to solve problems.

• Your First Refal Plus Program
  To maintain the historically established tradition, we begin by considering a simple program in Refal Plus.
• Data Structures
  Data processed by Refal Plus Programs can be tree-like structures or directed graphs.
• Evaluation and Analysis of Ground Expressions
  The main kind of data dealt with by Refal Plus programs are ground expressions.
• Functions Defined in the Program
  A Refal Plus program is essentially a set of mutually recursive function definitions.
• Logical conditions
  In Refal Plus, the truth values "true" and "false" are represented by empty expressions and failures, respectively, while the logical connectives "and", "or" and "not" can be mimicked by constructs dealing with failures.
• Direct access selectors
  All implementations of Refal Plus enable quick and "cheap" direct access to the top-level terms of a ground expression, which turns out to be useful for solving problem by means of the technique known as "divide and conquer".
• Functions returning several results
  If the output format of a function contains several variables, the function is said to return several results.
• Iteration
  In Refal Plus, recursion is the principal means of representing loops. In many cases, however, this means is too universal, for which reason Refal Plus provides a special search construct $iter.
• Search and backtracking
  The constructs that Refal Plus provides for catching and handling failures can be used for implementing algorithms dealing with search and backtracking.
• Example: a compiler for a small imperative language
  The primary objective of this section is to consider the traditional compiler writing techniques in the framework of Refal Plus. These techniques are applied to a compiler for a small imperative language.