Refal

Infobox programming language
name = Refal
year = 1966-1968
paradigm = Pattern-matching and Term-rewriting
designer = Valentin Turchin
developer = Valentin Turchin, S. Florentsev, V. Olyunin, et al.
website = http://www.refal.net
typing=strong, dynamic
implementations=Refal-2, Refal-5, Refal-6, Refal+Refal is a pattern matching programming language. The name Refal stands for Recursive functions algorithmic language.

As defined by [http://www.supercompilers.com/html/refal_content.html] , "Refal (for REcursive Functions Algorithmic Language) is a functional programming language oriented toward symbol manipulation: string processing, translation, 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 algorithms 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.

Recently, Refal has been demonstrated to be more powerful in processing and transforming tree structures than XSLT. [http://www.refal.org/english/xmlref_1.htm]

Refal Basics

A Refal Hello World 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)

Other Examples

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 lispy style of operators.

Factorial with loops

Fact { s.n = ; }; 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.

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 bedecomposed into terms in an expression as above.)

If

Defining control structures is easy

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 e2the same for e2.

queeze 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 doubleblanks in its input expression, and replaces it with a single blank.The second clause matches only when the first one did not, and returns theresultant value which is the current expression.

queeze using Explicit Looping

Squeeze { '__'e.1 = ; s.A e.1 = s.A ; = ; };

References

* cite web
last=Turchin
first=Valentin F.
title=REFAL-5 Programming Guide and Reference Manual
url=http://www.supercompilers.com/html/refal_content.html
publisher=The City College of New York, New England Publishing Co., Holyoke
year=1989

External links

* [http://www.refal.net/ Refal homepage]