The Recursive Functions Algorithmic Language, a programming language designed by Dr. Valentin Turchin when he was at the Keldysh Institute for Applied Mathematics in Moscow during the late 1960's, based somewhat on the theory of Markov Normal Algorithms. The first good virtual machine for it was completed around 1968. It was very popular in the Soviet Union for artificial intelligence programming, symbolic processing, and the theory of computation, making it something of the USSR's answer to LISP.
In the taxonomy of programming languages REFAL is a functional language which uses call by value semantics and static binding. Input data are automatically grouped into symbols, making most parsing jobs superfluous. The language itself is based almost entirely on pattern matching. An example of REFAL code to recognize a palindrome is this:
Palindrome {
= True;
s.1 = True;
s.1 e.2 s.1 = <Palindrome e.2>
e.1 = False;
}
Function application is given by angle brackets: <...>. The first line of the function (= True;) states that an empty argument is a palindrome. The second line (s.1 = True;) says that a single symbol by itself is considered a palindrome. The third line (s.1 e.2 s.1 = <Palindrome e.2>) says that two identical symbols s.1 between an arbitrary expression e.2 is a palindrome only if e.2 is a palindrome. The last line says that any expression that doesn't match any of the previous rules is not a palindrome. It's no mistake that this looks very similar to a context-free grammar that recognizes palindromes.
Recently, it had been pointed out that XML actually represents data in ways very similar to the way functional programs do. Interestingly enough, REFAL's approach to data representation is closer to XML than any other, making it a fairly convenient means of manipulating XML documents, which is probably easier to do this way than XSLT.
One of the things REFAL was used for in the beginning was metaprogramming, the writing of programs by other programs. Using REFAL Turchin developed the fundamental concepts of a globally optimizing program transformation technique he calls 'supercompilation', that's able to dramatically increase the speed and efficiency of programs. The same concepts applied to Java became the foundation for a company he co-founded in 1999 at the height of the Internet boom: Supercompilers LLC.
There are a few dialects of REFAL floating around, all of which based either directly or indirectly on Turchin's original code. The last version Turchin himself was directly involved with was REFAL-5, which he produced when he was professor at the City College of New York. Source code and precompiled versions of a REFAL-5 system for Win32 and Linux are available at:
http://botik.ru/pub/local/scp/refal5/refal5.html
A dialect created by a colleague of Turchin's from his days at Keldysh, Andrei Klimov, is REFAL-6, which can be obtained at:
http://gh218.keldysh.ru/refal6/
Yet another version is REFAL+, whose origin I'm unable to ascertain as the only pages describing it are written in Russian. Anyone who can read Russian is welcome to check it out, and hopefully tell me more about who wrote it and what makes it different from the other dialects. Its home page is:
http://refal.msu.ru/