Refal-5

Refal-5 is the canonical reference dialect of Refal — Valentin Turchin’s functional, pattern-matching language for symbolic computation. Documented in Turchin’s 1989 Programming Guide and Reference Manual, Refal-5 is the version most programmers and researchers mean when they say “Refal” today: it is the dialect taught in tutorials, the one most modern implementations track, and the language in which the celebrated SCP4 supercompiler is written.

History & Origins

The Refal family begins with Valentin Turchin (1931–2010), a Soviet and later American physicist and computer scientist who conceived Refal — REcursive Functions Algorithmic Language — in 1966 as a metalanguage for describing the semantics of other algorithmic languages. The first working implementation followed in 1968. Through the 1970s, Refal-2 became the dominant Soviet implementation and Refal grew into a primary language for artificial-intelligence and natural-language research there.

Refal-5 is the dialect Turchin produced after emigrating to the United States. He documented it in the “REFAL-5 Programming Guide and Reference Manual,” published in 1989 by New England Publishing in Holyoke, Massachusetts. That manual — later revised and expanded — gave the Refal community a clear, portable, freely available reference standard at a time when earlier dialects were fragmented across incompatible Soviet implementations. The provided “year” of 1989 reflects this documentation milestone rather than the conception of Refal itself, which dates to the 1960s.

Design Philosophy

Refal-5 inherits the austere, unusually pure ideas at the heart of all Refal dialects:

• Everything is rewriting. A Refal-5 program is a set of sentences (rewrite rules), each pairing a left-hand pattern with a right-hand replacement. Computation repeatedly matches the current expression against patterns and rewrites it.
• Data are trees, not just lists. The central data structure is the object expression: a sequence of symbols, numbers, and parenthesized sub-expressions nested to any depth. Because data are tree-structured, patterns can scan in both directions and reach into nested structure.
• Pattern matching as the core paradigm. Refal elevated pattern matching from a convenience to the primary computational mechanism well before it became mainstream.
• A clean abstract machine. Execution is described by the Refal machine, with a “view field” holding the expression being transformed. This explicit operational model is part of why Refal-5 lends itself so well to formal analysis and program transformation.

A defining constraint of classical Refal-5 is that it deliberately omits nested functions. Turchin held that Refal should be not only the subject but also the object of program transformation, and that valid transformations are those a person could carry out “with pen and paper” — a discipline that keeps the language small enough to reason about mechanically. (Later extensions relax this; see Evolution below.)

Key Features

• Pattern-directed function definitions — functions are written as alternative sentences; the first matching sentence fires.
• Typed variables — Refal-5’s variables come in kinds: an s-variable (s.X) matches a single symbol, an e-variable (e.X) matches an arbitrary sub-expression, and a t-variable (t.X) matches a single term (a symbol or a parenthesized expression).
• Two-directional, nested matching — e-variables can match spans anywhere inside an expression, making parsing, searching, and rewriting concise.
• Strong, dynamic typing — values carry their type at run time while structure is checked as matching proceeds.
• Symbolic orientation — symbols, numbers, and structured terms are first-class, suiting language processing, algebraic manipulation, and metaprogramming.

A flavor of Refal-5’s rewriting style — a function that reverses a sequence by peeling off the last symbol:

Reverse {
  = ;
  e.Init s.Last = s.Last <Reverse e.Init>;
}

The empty pattern (=) handles the base case; e.Init s.Last splits an expression into an arbitrary prefix and a final single symbol, which is moved to the front before recursing.

Supercompilation and SCP4

Refal-5’s most consequential role is as the substrate for supercompilation, the program-transformation technique Turchin developed beginning in the 1970s. A supercompiler traces the generalized histories of a program’s computation and builds a new, often radically restructured program with the same behavior but greater efficiency — performing deep specialization, fusing away intermediate data, and even supporting program verification.

The flagship is SCP4, built by Andrei Nemytykh and Valentin Turchin and made publicly available around 2000. SCP4 is written in Refal-5 and operates on Refal-5 programs, making the dialect both the implementation language and the object language of the most advanced supercompiler in the Refal world. SCP4 influenced a broad line of program-specialization research, and supercompilation has since been explored for functional languages well beyond Refal.

Evolution

Refal-5 sits at the center of a family of dialects:

The most active modern descendant is Refal-5λ (Refal-5 Lambda), developed at Bauman Moscow State Technical University by Alexander Konovalov and colleagues. It is described as an exact superset of Refal-5 — any program that runs on a classical Refal-5 implementation is also a valid Refal-5λ program — adding higher-order functions, unnamed nested functions (inspired by Refal-7), and syntactic sugar such as assignments and blocks. Its implementation is also more open to integration with C++, in contrast to many of the more closed classical implementations.

Current Relevance

Refal-5 today is a niche but living standard. It no longer competes for mainstream use, but it remains the de facto reference point for the Refal community — concentrated in Russia and among program-transformation researchers worldwide — and is kept current through actively maintained, backward-compatible implementations like Refal-5λ. Its enduring importance is twofold: it is a remarkably clean teaching vehicle for pattern matching and term rewriting, paradigms now mainstream in languages such as Haskell, Erlang, and Rust; and it remains the home of supercompilation, an idea that continues to inspire research into program specialization, optimization, and verification.

Why It Matters

Refal-5 is the dialect that turned a fragmented family of Soviet implementations into a single, documented, portable reference — the form in which Refal’s ideas reached the wider world. By giving the language a stable definition, Turchin made it possible for tools like SCP4 to be built, studied, and extended, and for newcomers to learn Refal from one authoritative manual. For anyone interested in the roots of functional programming or in the theory of program transformation, Refal-5 is the natural starting point: small enough to learn quickly, yet deep enough to host one of the most ambitious ideas in computer science.

Sources: Refal — Wikipedia, Valentin Turchin — Wikipedia, REFAL-5 Programming Guide and Reference Manual (Google Books), Refal-5λ project documentation, and The Supercompiler SCP4: General Structure (Springer).