Refal

Refal — short for REcursive Functions Algorithmic Language — is a functional programming language oriented toward symbolic computation, built from the ground up on pattern matching and term rewriting. Conceived in the Soviet Union in the 1960s, it is one of the oldest functional languages still in use, and it occupies a singular place in computing history: it is the language in and around which supercompilation, one of the most ambitious program-transformation techniques ever devised, was born.

History & Origins

Refal was created by Valentin Turchin (1931–2010), a Soviet and later American physicist, cybernetician, and computer scientist. He first conceived the language in 1966 as a theoretical tool — a metalanguage for describing the semantics of other algorithmic languages and for reasoning about computation — rather than as a practical programming system. The first working implementation followed in 1968, turning Refal from a formalism on paper into a language people could actually run.

The intellectual context matters. Turchin was deeply influenced by Markov’s normal algorithms, a Soviet model of computation based on string-rewriting rules, and Refal can be read as a richer, more structured descendant of that idea. At the same time, Refal was a deliberate contrast to Lisp, the dominant symbolic language of the era: where Lisp built everything from linear lists and cons cells, Refal made pattern matching over tree-structured data the central act of programming.

Through the 1970s, Refal-2 became the most widely used implementation, and Refal grew into a primary language for artificial intelligence and natural-language processing research across the Soviet Union — by many accounts the AI language of choice there. Turchin’s career was disrupted by his dissident activities; he emigrated from the USSR in the late 1970s and continued his work in the United States, where the later Refal-5 dialect was documented.

Design Philosophy

Refal’s design rests on a small number of unusually pure ideas:

• Everything is rewriting. A Refal program is essentially a set of sentences (rewrite rules), each with a left-hand pattern and a right-hand replacement. Computation proceeds by repeatedly matching the current expression against patterns and rewriting it — a direct, executable embodiment of term rewriting.
• Data are trees, not just lists. Refal’s central data structure is the object expression: a sequence that can contain symbols, numbers, and parenthesized sub-expressions nested to any depth. Because data are trees rather than flat lists, patterns can scan and match in both directions and reach into nested structure.
• Pattern matching as the core paradigm. Refal was one of the first languages to elevate pattern matching from a convenience to the primary computational mechanism. Its variables come in kinds — typically an s-variable matching a single symbol, and an e-variable matching an arbitrary sub-expression — which makes patterns expressive while keeping matching well defined.
• A clean abstract machine. Execution is described by the Refal machine, an abstract machine with a “view field” holding the expression being transformed and a “free format” describing the program. This explicit operational model is part of why Refal lends itself so well to formal analysis and transformation.

Key Features

• Pattern-directed function definitions — functions are defined by listing alternative patterns; the first matching sentence fires, much like equational definitions in modern functional languages, but generalized to arbitrary tree patterns.
• Two-directional, nested matching — e-variables can match spans anywhere inside an expression, enabling concise definitions for parsing, searching, and rewriting tasks.
• Strong, dynamic typing — values carry their type at run time, while the structure of object expressions is checked as matching proceeds.
• Symbolic orientation — strings, symbols, and structured terms are first-class, making the language a natural fit for language processing, algebraic manipulation, and metaprogramming.
• Amenability to program transformation — Refal’s simple, uniform semantics is what makes supercompilation possible, which is arguably the language’s most important and lasting feature.

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

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

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

Supercompilation and Metacomputation

Refal’s deepest contribution to computer science grew out of Turchin’s broader philosophy. In his book The Phenomenon of Science (published in English by Columbia University Press in 1977, though reportedly written around 1970), he introduced the metasystem transition — the idea that new levels of control emerge when a system gains the ability to observe and manipulate copies of itself. Applied to computing, this became metacomputation: building a “metamachine” that controls, analyzes, and imitates the work of another machine.

The most celebrated instance is supercompilation (a contraction of supervised compilation), a program-transformation technique Turchin developed beginning in the 1970s. A supercompiler does not merely optimize locally; it traces the possible generalized histories of a program’s computation and builds a new, often radically restructured program with the same behavior but greater efficiency. Supercompilation can perform deep specialization, fuse away intermediate data structures, and even serve as a basis for program verification.

The most advanced supercompiler for the language is SCP4, built by Andrei Nemytykh and Valentin Turchin and made publicly available around 2000. Written in Refal-5 and operating on Refal-5 programs, SCP4 became a key research tool and influenced a generation of work on program specialization — supercompilation has since been explored for functional languages well beyond Refal, including experimental supercompilers for languages such as Haskell.

Evolution

Refal has passed through several dialects over its long life:

The Refal-5 dialect, documented in Turchin’s 1989 manual, remains the canonical reference point, and its companion supercompiler SCP4 anchored much of the research community. More recently, Refal-5λ (Refal-5 Lambda), developed at Bauman Moscow State Technical University by Alexander Konovalov and colleagues, modernizes the language with higher-order functions and unnamed nested functions while staying close to the classic Refal-5 core.

Current Relevance

Refal today is a niche but living language. It no longer competes for mainstream use, but it retains a dedicated community — concentrated in Russia and among program-transformation researchers worldwide — and actively maintained implementations such as Refal-5λ. Its enduring importance is twofold. First, it is a remarkably clean teaching language for pattern matching and term rewriting, paradigms now mainstream in languages like Haskell, Erlang, and Rust. Second, and more profoundly, it remains the home of supercompilation, an idea that continues to inspire research into program specialization, optimization, and verification decades after Turchin first formulated it.

Why It Matters

Refal is a reminder that some of the most influential ideas in programming arrived early and from unexpected places. Built in the Soviet Union in the 1960s on the austere foundation of rewriting rules, it anticipated the pattern-matching style that would become central to functional programming a generation later. But its greatest legacy is conceptual: by treating programs as objects that other programs can analyze and transform, Turchin’s work on metasystem transitions and supercompilation opened a line of inquiry — what can a program learn by watching itself compute? — that the field is still pursuing today. For anyone interested in the roots of functional programming or the theory of program transformation, Refal is essential history.

Sources: Refal — Wikipedia, Valentin Turchin — Wikipedia, Refal — PLDB, The Supercompiler SCP4: General Structure (Springer), and the Refal-5λ project documentation.