Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Refal
open-in-new
<p>Refal "is a <a href="/facts/Functional_programming/cdxqPEIM">functional</a> <a href="/facts/Programming_language/cWTYbgWa">programming language</a> oriented toward symbolic computations", including "<a href="/facts/String_processing/ALwbntgo">string processing</a>, <a href="/facts/Translation/2foI82so">language translation</a>, [and] <a href="/facts/Artificial_intelligence/lJGauQwX">artificial intelligence</a>". It is one of the oldest members of this family, first conceived of 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. </p><p>One of the first functional programming languages to do so, and unlike <a href="/facts/Lisp_(programming_language)/xJHA3CrX">Lisp</a> of its time, Refal is based on <a href="/facts/Pattern_matching/CEwptMs9">pattern matching</a>. Its pattern matching works in conjunction with <a href="/facts/Term_rewriting/9PHlnnnJ">term rewriting</a>. </p><p>The basic <a href="/facts/Data_structure/yNsNvL1I">data structure</a> of Lisp and <a href="/facts/Prolog/r5h66Qh1">Prolog</a> is a linear list built by <a href="/facts/Cons/KTYIDGwz">cons operation</a> in a sequential manner, thus with <i>O(n)</i> access to list's <i>n</i>th element. Refal's lists are built and scanned from both ends, with pattern matching working for nested lists as well as the top-level one. In effect, the basic data structure of Refal is a <a href="/facts/Tree_(computer_science)/RcXz9noF">tree</a> rather than a <a href="/facts/List_(computer_science)/9tzhAH6M">list</a>. This gives freedom and convenience in creating data structures while using only mathematically simple control mechanisms of pattern matching and substitution. </p><p>Refal also includes a feature called the <i>freezer</i> to support efficient <a href="/facts/Partial_evaluation/cSBKhRPo">partial evaluation</a>. </p><p>Refal can be applied to the processing and transformation of tree structures, similarly to <a href="/facts/XSLT/0gw4WVyJ">XSLT</a>. </p>