Refal
Encyclopedia
Refal "is a 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 combines mathematical simplicity with practicality for writing large and sophisticated programs.
Unlike Lisp, Refal is based on pattern matching
. Due to that, a typical program in Refal is on average two or three times shorter and more readable than a Lisp analog. Compared to Prolog
, Refal is conceptually simpler. Its pattern matching works in the forward
direction rather than backwards
(starting from the goal) as in Prolog. This is a more natural approach to writing algorithm
s which also makes them easier to test and debug.
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). 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 more succinct in processing and transforming tree structures than XSLT.
example is shown below.
$ENTRY Go { =;}
Hello {
=;
}
The program above includes two functions named Go and Hello. A function is written as the name of the function followed by the function body in curly braces. The Go function is marked as the entry point of the program using the $ENTRY directive.
One could think of expressions in the function bodies as function "calls" in Lisp
-like syntax. For example, the Hello function appears to call the built-in Prout function with the string 'Hello world' as the argument. The meaning and the mechanism of the call, however, is quite different. To illustrate the difference, let us consider the following function that determines whether a string is a palindrome
.
Pal { = True;
s.1 = True;
s.1 e.2 s.1 =;
e.1 = False; }
This example shows a function with a more complex body, consisting of four sentences. A sentence begins with a pattern followed by an equal sign followed by a general expression on the right hand side. A sentence is terminated with a semicolon. For example, the pattern of the second sentence of the function is "s.1" and the expression is "True".
As the example shows, patterns include pattern variables that have the form of a character identifying the type of the variable (what the variable matches) followed by the variable identifier. The variables that begin with an "s" match a single symbol, those that begin with an "e" match an arbitrary expression. The variable identifier can be an arbitrary alphanumeric sequence optionally separated from the type identifier by a dot.
A function executes by comparing its argument with the patterns of its sentences in the order they appear in the definition, until the first pattern that matches. The function then replaces the argument with the expression on the left hand side of the matched sentence.
If the result of a function application includes a subexpression in angle brackets (as it will after the third sentence of our example is applied), the result is further processed by Refal by invoking the function identified by the first symbol in the brackets. Execution stops when the result has no more angle brackets to expand in this way.
The function Pal can thus be read informally as: "If the expression is empty, replace it with True. Otherwise if the expression is a single symbol, replace it with True. Otherwise if the expression is a symbol followed by an arbitrary expression e.2 followed by the same symbol, replace it with the expression. (In other words, throw away the two identical symbols at the beginning and the end and recurse). Otherwise replace the expression with False. (The pattern e.1 always matches)."
The following are three step-by-step execution traces annotated with the sentence numbers applied at each step to produce the next
(#3)
(#3)
(#1)
True
(#3)
(#2)
True
(#3)
(#3)
(#3)
(#4)
False
We can now see that the Hello World example in fact executes as the sequence of the following expression transformations:
Seed the machine with the initial expression marked by $ENTRY:
(apply the sentence in Go)
(apply the sentence in Hello)
(Prout is a built-in that prints and expands to nothing)
(nothing to apply; stop)
s.N = <* s.N>>; }
Here 0 matches 0 the number and produces 1. On any other symbol which is a number, multiply it with the result of (Fact (- s.N 1))
Note the prefix style of operators.
; };
Loop {
0 s.f = s.f;
s.n s.f = <* s.n s.f>>; }
As can be seen s.n acts as the loop counter.
(e.1)(e.1) = T;
(e.1)(e.2) = F; }
Here the function is defined as, if given two terms, and the terms are same then the first clause matches and produces True.
else the second clause matches and produces False.
An important property of Refal is that all functions in refal are single argument. (But may be
decomposed into terms in an expression as above.)
If {
T Then (e.1) Else (e.2) = e.1;
F Then (e.1) Else (e.2) = e.2; }
Here the e1 is evaluated only when the expression entered matches 'True' Then e1 Else e2
the same for e2.
e.1'__'e.2 =;
e.1 = e.1; }
(Using '_' in place of space char so as to make the function call clear.)
The first clause matches whenever the function Squeeze encounters double
blanks in its input expression, and replaces it with a single blank.
The second clause matches only when the first one did not, and returns the
resultant value which is the current expression.
'__'e.1 =;
s.A e.1 = s.A;
= ; };
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
oriented toward symbol manipulation", including "string processing, translation
Translation
Translation is the communication of the meaning of a source-language text by means of an equivalent target-language text. Whereas interpreting undoubtedly antedates writing, translation began only after the appearance of written literature; there exist partial translations of the Sumerian Epic of...
, [and] artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
". 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 combines mathematical simplicity with practicality for writing large and sophisticated programs.
Unlike Lisp, Refal is based on pattern matching
Pattern matching
In computer science, pattern matching is the act of checking some sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually has to be exact. The patterns generally have the form of either sequences or tree structures...
. Due to that, a typical program in Refal is on average two or three times shorter and more readable than a Lisp analog. Compared to Prolog
Prolog
Prolog is a general purpose logic programming language associated with artificial intelligence and computational linguistics.Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is declarative: the program logic is expressed in terms of...
, Refal is conceptually simpler. Its pattern matching works in the forward
Forward chaining
Forward chaining is one of the two main methods of reasoning when using inference rules and can be described logically as repeated application of modus ponens. Forward chaining is a popular implementation strategy for expert systems, business and production rule systems...
direction rather than backwards
Backward chaining
Backward chaining is an inference method that can be described as working backward from the goal...
(starting from the goal) as in Prolog. This is a more natural approach to writing algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s which also makes them easier to test and debug.
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
Cons
In computer programming, cons is a fundamental function in most dialects of the Lisp programming language. cons constructs memory objects which hold two values or pointers to values. These objects are referred to as cells, conses, non-atomic s-expressions , or pairs...
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). 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
Partial evaluation
In computing, partial evaluation is a technique for several different types of program optimization by specialization. The most straightforward application is to produce new programs which run faster than the originals while being guaranteed to behave in the same way...
.
Refal can be more succinct in processing and transforming tree structures than XSLT.
Refal Basics
A Refal Hello WorldHello world program
A "Hello world" program is a computer program that outputs "Hello world" on a display device. Because it is typically one of the simplest programs possible in most programming languages, it is by tradition often used to illustrate to beginners the most basic syntax of a programming language, or to...
example is shown below.
$ENTRY Go { =
Hello {
=
}
The program above includes two functions named Go and Hello. A function is written as the name of the function followed by the function body in curly braces. The Go function is marked as the entry point of the program using the $ENTRY directive.
One could think of expressions in the function bodies as function "calls" in Lisp
Lisp
A lisp is a speech impediment, historically also known as sigmatism. Stereotypically, people with a lisp are unable to pronounce sibilants , and replace them with interdentals , though there are actually several kinds of lisp...
-like syntax. For example, the Hello function appears to call the built-in Prout function with the string 'Hello world' as the argument. The meaning and the mechanism of the call, however, is quite different. To illustrate the difference, let us consider the following function that determines whether a string is a palindrome
Palindrome
A palindrome is a word, phrase, number, or other sequence of units that can be read the same way in either direction, with general allowances for adjustments to punctuation and word dividers....
.
Pal { = True;
s.1 = True;
s.1 e.2 s.1 =
e.1 = False; }
This example shows a function with a more complex body, consisting of four sentences. A sentence begins with a pattern followed by an equal sign followed by a general expression on the right hand side. A sentence is terminated with a semicolon. For example, the pattern of the second sentence of the function is "s.1" and the expression is "True".
As the example shows, patterns include pattern variables that have the form of a character identifying the type of the variable (what the variable matches) followed by the variable identifier. The variables that begin with an "s" match a single symbol, those that begin with an "e" match an arbitrary expression. The variable identifier can be an arbitrary alphanumeric sequence optionally separated from the type identifier by a dot.
A function executes by comparing its argument with the patterns of its sentences in the order they appear in the definition, until the first pattern that matches. The function then replaces the argument with the expression on the left hand side of the matched sentence.
If the result of a function application includes a subexpression in angle brackets (as it will after the third sentence of our example is applied), the result is further processed by Refal by invoking the function identified by the first symbol in the brackets. Execution stops when the result has no more angle brackets to expand in this way.
The function Pal can thus be read informally as: "If the expression is empty, replace it with True. Otherwise if the expression is a single symbol, replace it with True. Otherwise if the expression is a symbol followed by an arbitrary expression e.2 followed by the same symbol, replace it with the expression
The following are three step-by-step execution traces annotated with the sentence numbers applied at each step to produce the next
True
True
False
We can now see that the Hello World example in fact executes as the sequence of the following expression transformations:
Seed the machine with the initial expression marked by $ENTRY:
(nothing to apply; stop)
Factorial
Fact { 0 = 1;s.N = <* s.N
Here 0 matches 0 the number and produces 1. On any other symbol which is a number, multiply it with the result of (Fact (- s.N 1))
Note the prefix style of operators.
Factorial with loops
Fact { s.n =Loop {
0 s.f = s.f;
s.n s.f =
As can be seen s.n acts as the loop counter.
Equality
Equal {(e.1)(e.1) = T;
(e.1)(e.2) = F; }
Here the function is defined as, if given two terms, and the terms are same then the first clause matches and produces True.
else the second clause matches and produces False.
An important property of Refal is that all functions in refal are single argument. (But may be
decomposed into terms in an expression as above.)
If
Defining control structures is easyIf {
T Then (e.1) Else (e.2) = e.1;
F Then (e.1) Else (e.2) = e.2; }
Here the e1 is evaluated only when the expression entered matches 'True' Then e1 Else e2
the same for e2.
Squeeze blanks
Squeeze {e.1'__'e.2 =
e.1 = e.1; }
(Using '_' in place of space char so as to make the function call clear.)
The first clause matches whenever the function Squeeze encounters double
blanks in its input expression, and replaces it with a single blank.
The second clause matches only when the first one did not, and returns the
resultant value which is the current expression.
Squeeze using Explicit Looping
Squeeze {'__'e.1 =
s.A e.1 = s.A
= ; };