Make Refal on the Prolog. Seven Lines Magic

    If the recognizing machine responds to the elephant’s picture with a “mura” signal, the image of a camel is also “mura” and the portrait of a prominent scientist is again “mura”, this does not necessarily mean that it is faulty. She can be just philosophical.
    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. Refal’s fate is complicated, but his language is still alive and developing. For those interested, here are a few links:


    Strongly exaggerating, we can say that Refal is a mixture of Lisp and Prolog. There is one interesting feature in the language syntax - comparison with the so-called pattern. "Direct conclusion."

    That is, for example, a predicate for determining a palindrome on Refal can be written as follows:

     Palindrom {
         = True;
         s.1 = True ;
         s.1 e.2 s.1 =  ;
         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. A function call is recorded in angle brackets. Characters starting with "s" and "e" are variables of a certain kind. The name of the variables is written after the period.
    • A variable of type “s” means that the mapping is true for only one element of the sequence
    • A variable of type “e” means that the match is true for 0 or more elements


    T.O. this definition of a palindrome can be read like this:
    • The expression is true for an empty list. Those. an empty sequence can be called a palindrome.
    • The expression is true for a single-element list. Those. a sequence of one element can be called a palindrome. The type of the s variable tells us that the pattern is valid for only one element.
    • The expression is true for a list of at least 2 items, with the first and last items in the list being equal. The equality of the first and last element is indicated by the same variable names ("1"). The sublist between the first and last element (the variable “e.2”, ie the length of such a sublist can be 0 or more elements) must be recursively checked for a palindrome.
    • If none of the above rule worked, then the argument passed is not a palindrome.


    It is necessary to cancel that in modern implementations of Refal comparison with the model is implemented quite efficiently.

    2. Prologue. The magic begins!



    Refal has a lot of Prolog. We will try to implement the mechanism of refalovskoe comparison with the sample on the Prolog.

    Before we begin, we define the helper predicate “prefix”. The predicate must check whether the first argument is the beginning of the second argument. The remainder of the second argument is indicated 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 determine the predicate of refalval matching with the sample (let us call the predicate “rf”). Here are some examples of using “rf” using the same palindrome as an example (the implementation itself will be a bit 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. The fourth rule in the refalov example we did not need, because The prologue itself will cut off the false branches of the mapping. Note that the “s” and “e” in the example are ordinary Prolog terms.

    Examples of calling our palindrome:

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


    Now let's move on 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([], []).
    


    We comment on our definition line by line:
    • The comparison is true 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 also true for the “s” element in the pattern.
    • If the next element of the sample is an “e” variable, then 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 , on the Prolog. The statement of the problem:

    There are two ASCII lines in the input file, one consists of only large Latin letters, the other can contain large Latin letters and two other special characters - * (asterisk) and? (question mark). Strings can have a length of 1 to 255 characters, be in a file in random order (but there are only two of them, the input data format is correct). A line with only letters is called a word. A line with special characters - a pattern in which "?" and "*" play the role of wildcard characters according to the rules identical to wildcards in file names in DOS or Unix-shell, ie "?" replaces 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 a YES response if the word matches the pattern (match it), or NO otherwise.


    Solution for refal:

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


    We 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 much less effective than the solution from the article “Prolog, introduction” .

    3.2. Second example



    Here is another example of using our predicate. We define a trivial predicate that calculates arithmetic expressions in a string.

    Usage example:

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


    Let the infix predicate “understand” only addition and multiplication operations. 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 leave the implementation of other operators to an independent study.

    Instead of a conclusion



    The above code does not claim to be unique or practical. However, we dare to hope that it will push the reader to become more familiar with such wonderful languages ​​as Prolog and Refal.

    Also popular now: