Make Refal on Prolog. Seven line magic

If the discriminating machine responds to the drawing of an elephant with a “mura” signal, the images of a camel are also “mura” and the portrait of a prominent scientist is again “mura”, this does not necessarily mean that it is faulty. She may just be philosophically tuned.
Vladimir Savchenko, "Opening yourself"

1. Love Refal. Immediately!

Everyone knows that there is such a programming language - Refal. Refal was developed in 1966 by our compatriot Valentin Turchin. The fate of Refal is complicated, but the language is still alive and developing. For those interested, here are some links:

• Independent study Refal-5. Student look
• The journal "Practice of Functional Programming", issue number 7 (bright memory to him!). The articles "REFAL Language - a view from the side" and "Supercompilation: ideas and methods"

')
Strongly exaggerating, we can say that Refal is a mixture of Lisp and Prolog. In the syntax of the language there is one interesting feature - the comparison with the so-called sample. "Direct conclusion".

Ie, for example, the predicate for defining a palindrome on Refal can be written as:

Palindrom { = True; s.1 = True ; s.1 e.2 s.1 = <Palindrom e.2> ; e.1 = False ; } 

Each line in braces is a pattern matching rule. The body of each rule is separated by the symbol "=". Sample elements are separated by a space. The function call is written in angle brackets. Symbols beginning with “s” and “e” are variables of a certain type. The variable name is written after the full stop.

• A variable of type "s" means that the match is true only for one element of the sequence.
• A variable of type "e" means that the mapping is true for 0 or more elements.

So This definition of a palindrome can be read as follows:

• The expression is valid for an empty list. Those. an empty sequence can be called a palindrome.
• The expression is valid for a list of one item. Those. a sequence of one element can be called a palindrome. The type of the variable “s” tells us that the pattern is valid only for one element.
• The expression is true for a list consisting of at least 2 elements, the first and the last element of the list must be equal. The equality of the first and last element is indicated by the same variable names (“1”). The sublist between the first and the last element (the “e.2” variable, i.e. the length of such a sublist may be 0 or more) must be recursively checked on the palindrome.
• If none of the above defined rules worked, then the passed argument is not a palindrome.

It is necessary to cancel that in modern implementations of Refal the pattern matching is implemented quite effectively.

2. Prologue. The magic begins!

In Refal there is a lot of Prolog language. We will try to implement the mechanism of refal pattern matching on the Prolog.

Before we begin, we define the auxiliary predicate “prefix”. The predicate must check whether the first argument is the beginning of the second argument. The remainder of the second argument is specified in the third argument.

 prefix([], [X|Xs], [X|Xs]). prefix([X|Prefix], [X|List], Rest) :- prefix(Prefix, List, Rest). 

Call examples:

 ?- prefix([1,2], [1,2,3,4], [3,4]). true. ?- prefix([], [1,2,3,4], X). X = [1, 2, 3, 4]. 

Now everything is ready for us to define the predicate of the reference match with the sample (let's call the predicate “rf”). Let us give examples of using “rf” using the example of the same palindrome (the implementation itself will be a little later):

 palindrom([]). palindrom([_]). palindrom(List) :- rf([s(X1), e(Y), s(X1)], List), palindrom(Y). 

As you can see, this definition is similar to what we wrote earlier on Refal. We did not need the fourth rule in the Refalian example, since The prologue itself will cut off the false branches of the collation. Note that the “s” and “e” in the example are the usual terms of Prologue.

Examples of calling our palindrome:

 ?- palindrom("abc"). false. ?- palindrom("abcba"). true . ?- palindrom("aa"). true . 

We now turn, in fact, to the definition of the predicate “rf”:

 rf([X | Pattern], [X|Xs]) :- rf(Pattern, Xs). rf([s(X) | Pattern], [X|Xs]) :- rf(Pattern, Xs). rf([e(X) | Pattern], Xs) :- prefix(X, Xs, Rest), rf(Pattern, Rest). rf([e(X)], X). rf([], []). 

Let's comment on our definition line by line:

• The comparison is correct if, at a minimum, both the sample and the list begin with the same element (variable X). Next, check the rest of the arguments.
• The rule is true for the "s" element in the sample
• If the next element of the sample is an “e” variable, then we check whether the variable X is a prefix for the second argument (recall that the empty list can also be a prefix). Next, check the rest of the arguments.
• The remaining 2 rules describe trivial matching cases.

3. Examples

3.1. First example

The wonderful article “Prolog, Introduction” provides a solution to the problem proposed in the Refal community in Prolog. Task statement:

There are two ASCII strings in the input file, one consists only of capital Latin letters, the other can contain large Latin letters and two more special characters - * (asterisk) and? (question mark). Lines can be from 1 to 255 characters long, be in a file in any order (but there are only two of them, the format of the input data is correct). A string with only letters is called a word. A string with special characters - a pattern in which the "?" and "*" play the role of wildcard characters according to the rules identical to wildcards in DOS or Unix-shell file names, i.e. "?" substitutes for itself exactly one arbitrary character, and "*" replaces any number of arbitrary characters — 0 or more (that is, it can replace an empty string). The program should give the answer YES, if the word falls under the pattern (match it), or NO otherwise.

Solution to the refal:

 Match { s.1 e.2 (s.1 e.3) = <Match e.2 (e.3)>; s.1 e.2 ('?' e.3) = <Match e.2 (e.3)>; e.1 ('*' e.3) = { e.1 : e.11 e.12, <Match e.12 (e.3)>; }; /*empty*/ () = /*yes*/; }; 

Rewrite the Refal predicate on Prolog using the approach described above:

 ischar(H, [H]). match([],[]) :- !. match("*",_) :- !. match(Pattern, Word) :- rf([s(T1), e(E1)], Pattern), rf([s(T1), e(E2)],Word), match(E1, E2),!. match(Pattern, Word) :- rf([s(T1), e(E1)], Pattern), ischar(T1, "?"), rf([s(_T2), e(E2)], Word), match(E1,E2),!. match(Pattern, Word) :- rf([s(T1), e(E1)], Pattern), ischar(T1, "*"), rf([e(_E21), e(E22)], Word), match(E1,E22),!. check:- match("ASDFAASDASDAAASDASDASD", "ASDFAASDASDAAASDASDASD"), match("*", "ASDFAASDASDAAASDASDASD"), match("A?DF?A*ASD*ASDA?DASD", "ASDFAASDASDAAASDASDASD"), \+ match("ASDFAASDADAAASDASDASD", "ASDFAASASDAAASDASDASD"). 

Note that, of course, our definition is significantly less efficient than the solution from the article “Prolog, introduction” .

3.2. Second example

Let's give one more example of using our predicate. We define a trivial predicate that calculates arithmetic expressions in a string.

Example of use:

 ?- infix("2+2*2", R). R = 6. ?- infix("1+1+1+1", R). R = 4. 

Let the infix predicate "understand" only operations of addition and multiplication. Then the solution might look like this:

 ischar(H, [H]). infix(A,R) :- rf([e(X), OpPlus, e(Y)], A), ischar(OpPlus, "+"), infix(X,R1), infix(Y,R2), R is R1 + R2,!. infix(A,R) :- rf([e(X), OpMul, e(Y)], A), ischar(OpMul, "*"), infix(X,R1), infix(Y,R2), R is R1 * R2, !. infix(A,R) :- rf([e(X)], A), number_codes(R, X),!. 

We reserve the implementation of other operators for independent study.

Instead of conclusion

The code above does not claim to be unique or practical. However, we dare to hope, will push the reader to get closer to such wonderful languages ​​as Prolog and Refal.