Wikipedia
Refal (Recursive functions algorithmic language) "is functional programming language oriented toward symbol manipulation", including " string processing, translation, [and] artificial intelligence". It is one of the oldest members of this family, first conceived in 1966 as a theoretical tool with the first implementation appearing in 1968. Refal was intended to combine mathematical simplicity with practicality for writing large and sophisticated programs.
Unlike Lisp, Refal is based on pattern matching. Its pattern matching works in the forward direction rather than backwards (starting from the goal) as in Prolog.
Very important is the difference between data structures and their use in Refal and most other high-level languages. The basic data structure of Lisp and Prolog is a linear list consed up from the beginning. Refal lists are built and scanned from both ends, and pattern matching allows to match against nested lists as well as the top-level one. (In effect, the basic data structure of Refal is a tree rather than a list). According to the authors, this gives freedom and convenience in creating data structures while using only mathematically simple control mechanisms of pattern matching and substitution.
Refal also includes a feature called the freezer to support efficient partial evaluation.
Refal can be applied to the processing and transformation of tree structures, similarly to XSLT.