Documentation for: prolog.r

The Prolog (Like) Inference Engine Documentation

prolog.r is an inference engine which can process prolog like clauses in the form of :

    man [jean]
    woman [mary]
    human [X] [man [X]]
    human [X] [woman [X]]

This quick example illustrates how to load the engine, assert clause in the knowledge base and how to submit a goal and how to retrieve all the possible solution:

    do %prolog.r

    ex-base: assert none [
        man [carl]  
        man [paul]  
        man [marco]
    ]

    print [newline "*** Man list ***"]
    goal ex-base [
        man [X]
        (print ["==>" X "is a man."])
    ]

Contents

1. Specification

1.1 The interface

The engine provide the following interface :

1.1.1 assert

    USAGE:
        ASSERT base clauses

    DESCRIPTION:
        Create or update a KB block with parsed clauses. Return the KB block.
        ASSERT is a function value.

    ARGUMENTS:
        base -- KB block or none for a new base (Type: block none)
        clauses -- Clauses block to be parsed (Type: block)

If you want to create a new knowledge base, give none for the base parameter. If you want to add clauses to a knowledge base, give the base into which the clauses must be added.

NB. The clause are always appended to the knowledge base. Perhaps, it will be usefull to have a /head refinement to insert it instead of append it.

1.1.2 retract

    USAGE:
        RETRACT base predicat /all

    DESCRIPTION:
        Retract a clause from the block
        RETRACT is a function value.

    ARGUMENTS:
        base -- The KB block (Type: block)
        predicat -- The predicate to retract (Type: block)

    REFINEMENTS:
        /all

Retract removes all clauses for which the head of the clause can be matched with the predicate.

NB: This is not very well tested up to now.

1.1.3 goal

    USAGE:
        GOAL base goals

    DESCRIPTION:
        Try a goal and return the number of solution
        GOAL is a function value.

    ARGUMENTS:
        base -- The KB to use (Type: block)
        goals -- The goals to try (Type: block)

1.1.4 for-which

    USAGE:
        FOR-WHICH base 'word goals body

    DESCRIPTION:
        Try a goal and execute the body for each solutions

    ARGUMENTS:
        base -- The KB to use (Type: block)
        word -- The word or block of word to set for each solutions (will be local) (Type: word block)
        goals -- The goals to try (Type: block)
        body -- The block to evaluates for each solutions (Type: block)

    (SPECIAL ATTRIBUTES)
        throw

1.1.5 bench-goal

    USAGE:
        BENCH-GOAL count base goals

    DESCRIPTION:
        Try a goal n times and return the time to do it
        BENCH-GOAL is a function value.

    ARGUMENTS:
        count -- (Type: integer)
        base -- The KB to use (Type: block)
        goals -- The goals to try (Type: block)

1.2 Differences between Prolog syntax and prolog.r dialect

The main difference is that the prolog.r dialect use block [] instead of parenthesis (). An other difference is that the body of the predicates is placed within a block.

For example, the (Turbo) Prolog :

    grandfather (X, Y) :-
        father (X, Z),
        father (Z, Y).

Is in the prolog.r dialect :

    grandfather [X Y] [
        father [X Z]
        father [Z Y]
    ]

This is simply because it's more simple to parse and manipulate block than strings in REBOL and also, because when you load your script, REBOL check missing brackets if any.

An other difference is that you can place REBOL code within your clauses. For example, to print out some information, you can do this :

    grandfather [X Y] [
        father [X Z]
        father [Z Y]
        (print [X "is the grandfather of" Y])
    ]

You can also place REBOL script within the parameters of a predicate. For example the following clauses :

    sum [X Y (X + Y)]
    sum [X (Z - X) Z]
    sum [(Z - Y) Y Z]

Will give back the third parameter when you give only two or check that the first plus the second equal the third when you give the three parameters.

The last difference, is that you can organize your knowledge into many base. To access to the clauses from one base to another, you must use path, for example :

    facts: assert none [
        father [marco paul]
        father [arnaldo marco]
    ]
    rules: assert none [
        grandfather [X Y] [
            facts/father [X Z]
            facts/father [Z Y]
        ]
    ]

This can be usefull to organize your knowledge base, frequently one base for the rules (your logic) one base for the facts (the knowleddge base) and one base for the case (the deduction donefor the applied case).

Except these differences, the Prolog syntax is respected. Variables are word that begins with an uppercase letter or an underscore (_). Others words are considered as symbol. The CUT is available (CUT or !) and also the FAIL. CUT and FAIL are the only programed predicates. All others predifefined predicates are standard predicates.

1.3 Predifined predicates

prolog.r offers a set of predefined predicates:

prolog.r offer also another facility which is very simple but quiet difficult to explain. An example is much more simple:

    mother [anne cathy]
    mother [cathy cindy]

    display-all-mother [][
        mother? [X _]
        (print [X "is a mother])
    ]

In this example you can see that I didn't define the mother? predicates. I can do this because prolog.r defines it automaticaly in the following manner :

    mother? [X Y] [
        mother [X Y] !
    ]

With this, the predicate succeeds (only one time due to the cut) if the predicate whitout the question mark (?) succeeds. This prevents you to define this kind of predicate.

2. Examples

Here under, you will find a set of example that I use to test the engine

2.1 Father, mother and so on ...

Here, the facts and the predicates

    ex-base: assert none [

    ; The facts
    ; ---------
        man [jean]  
        man [pierre]  
        man [jacques]
        man [albert]  
        man [yvan]  
        man [marco]

        woman [jeanne]
        woman [anne]

        father [jacques pierre]
        father [jean jacques]
        father [jacques anne]

        mother [jeanne anne]
        mother [jeanne jean]
        mother [anne pierre]

    ; The predicates
    ; --------------
    ; A person is a man or a woman
        person [X] [
            man [X]
        ]
        person [X] [
            woman [X]
        ]

    ; A father is a man and is the father of at least one child
        father [X] [
            man [X]
            father? [X _]
        ]

    ; A mother is a woman and mother of at least one child
        mother [X] [
            woman [X]
            mother? [X _]
        ]

    ; A parent is a father or a mother
        parent [X Y] [
            father [X Y]
        ]
        parent [X Y] [
            mother [X Y]
        ]

        ; A parent is a person which is at least one time parent
        parent [X] [
            person [X]
            parent? [X _]
        ]

    ]

How to print who is a man

    print [newline "*** List of man ***"]
    goal ex-base [
        man [X]
        (print ["==>" X "is a man"])
    ]

How to print who is a person (a man or a woman)

    print [newline "*** List of persons ***"]
    goal ex-base [
        person [X]
        (print ["==>" X "is a person"])
    ]

How to print who is a father

    print [newline "*** List of father ***"]
    goal ex-base [
        father [X]
        (print ["==>" x "is a father"])
    ]

How to print who is a parent (a father or a mother)

    print [newline "*** List of parents ***"]
    goal ex-base [
        parent [X]
        (print ["==>" X "is a parent"])
    ]

How to print all the couples mother daughter

    print [newline "*** List of mother/daughter couple (use of for-which) ***"]
    for-which ex-base [
        Y Z
    ][
        mother [Y Z]
        woman [Z]
    ][
        print [Y "is the mother of" Z]
    ]

The following examples cannot be done with many Prolog (Turbo Prolog and his successor Visual Prolog for example)

How to print all the relationship with anne.

    print [newline "*** List of anne's relationship ***"]
    goal ex-base [
        X [Y anne]
        (print ["==>" Y "is the" X "of anne"])
    ]

How to print all the couple mother daughter

    print [newline "*** List of relationship between anne and pierre ***"]
    goal ex-base [
        X [anne pierre]
        (print ["==> anne"  "is the" X "of pierre"])
    ]

How to print all relationship two by two

    print [newline "*** List of all relationship two by two ***"]
    goal ex-base [
        X [Y Z]
        (print ["==>" mold Y "is the" X "of" mold Z])
    ]

How to print all the relationship

    print [newline "*** List of all relationship ***"]
    goal ex-base [
        X Y
        (print ["==>" X mold Y])
    ]

2.2 Reverse and concat of list

Here are three example of list manipulation

    ex-base: assert none [

    ; Invert of a list
        invert [[|X] [|Y]] [
            invert [X [] Y]
        ]
        invert [[] X X] [!]
        invert [[X | Y] Z W] [
            invert [Y [X | Z] W]
        ]

    ; Concat of two lists
        concat [[] L L] [!]
        concat [[X | L1] L2 [X | L3]] [
            concat [L1 L2 L3]
        ]

    ; Reverse known as naive reverse of a list
        nrev [[] []] [!]
        nrev [[X | Y] L] [
            nrev [Y Z]
            concat [Z [X] L]
        ]
    ]

    print [newline "*** Invert of [0 1 2 3 4 5 6 7 8 9] ***"]
    goal ex-base [
        invert [[0 1 2 3 4 5 6 7 8 9] [] X]
        (print ["==> Invert of [0 1 2 3 4 5 6 7 8 9] is" mold X])
    ]

    print [newline "*** Concat of [0 1 2 3 4] ans [5 6 7 8 9] ***"]
    goal ex-base [
        concat [[0 1 2 3 4] [5 6 7 8 9] X]
        (print ["==> Concat of [0 1 2 3 4] [5 6 7 8 9] is" mold X])
    ]

    print [newline "*** Naive reverse call from outside (for which) ***"]
    for-which ex-base [
        Y
    ][
        nrev [[1 2 3] Y]
    ][
        print ["Naive reverse of [1 2 3] is" mold Y]
    ]

2.3 How to optimize the cutting of a bar in many pieces

I create this example when Guy (a guy which name is Guy) asked on the french forum how to resolve this problem in REBOL.

The predicate "combine" receive in input the length, the element list and return the remainder and the solution.

    ex-base: assert none [

    ; If the first element is smaller or equal to the length, it's a solution
        combine [L [X1 | _] (L - X1) [X1]][
            if [(L >= X1)]
        ]

    ; If the first element is smaller or equal to the length,
    ; we try for the rest of the length

        combine [L [X1 | X] R [X1 | Y]] [
            if [(L >= X1)]
            combine [(L - X1) [X1 | X] R Y]
        ]

    ; If the length is greater than 0
    ; we try with the rest of the element

        combine [L [_ | X] R Y] [
            if [(L > 0)]
            combine [L X R Y]
        ]
    ]

    print [newline "*** Optimization of the cutting of a bar of 25 meters in element of 10 4 and 3 ***"]
    result: copy []
    for-which ex-base [RB C] [
        combine [25 [10 4 3] RB C]
    ][
        append result reduce [RB C]
    ]
    sort/skip result 2
    foreach [R C] result [
        print ["The remainder is" R "for the combination" mold C]
    ]

2.4 Resolving a murder

Here are the deducting rules

    rule: assert none [

    ; R1
    ; Someone (X) could have killed a person (Y) one day (Z) if :
    ;    X have a weapon
    ;    X can wish to kill Y
    ;    X does not have an alibi for day Z

        can-have-killed [X Y Z] [
            fact/has-a-weapon [X]
            wish-to-kill [X Y]
            day [Z]
            does-not-have-an-alibi-for-day [X Z]
        ]

    ; R2
    ; Someone (X) has not an alibi for the day (Y) if :
    ;    either he does not have an alibi for the day
    ;    either the alibi is given by a doubtful person

        does-not-have-an-alibi-for-day [X Y] [
            not [fact/has-an-alibi [X Y _]]
        ]
        does-not-have-an-alibi-for-day [X Y][
            fact/has-an-alibi [X Y Z]
            fact/is-doubtful [Z] 
        ]

    ; R3
    ; Someone (X) can wish to kill a person (Y) if
    ;   maybe if he wishes to be avenged of Y
    ;   maybe if he is the heir of Y
    ;   maybe if he has seen committing a crime by Y
    ;   maybe if he must give back money to Y

        wish-to-kill [X Y][
            fact/wish-to-be-avenged [X Y] !
        ]
        wish-to-kill [X Y][
            fact/is-the-heir [X Y] !
        ]
        wish-to-kill [X Y][
            fact/has-seen-committing-a-crime [Y X] !
        ]
        wish-to-kill [X Y][
            fact/must-give-back-money [X Y] !
        ]

    ; List of the day of the week
        day [ monday ]
        day [ tuesday ]
        day [ wednesday ]
        day [ thursday ]
        day [ friday ]
        day [ saturday ]
        day [ sunday ]
    ]

Here the result of the investigation

    fact: assert none [
    ; The alibis
        has-an-alibi [luc tuesday bernard]
        has-an-alibi [paul tuesday bernard]
        has-an-alibi [louis tuesday luc]
        has-an-alibi [alain thursday luc]

    ; The doubtful person
        is-doubtful [alain]

    ; Who wish to be avenged
        wish-to-be-avenged [paul jean]
        wish-to-be-avenged [luc jean]

    ; Who is the heir of who
        is-the-heir [bernard jean]
        is-the-heir [jean louis]

    ; Who must give back money to who
        must-give-back-money  [louis jean]
        must-give-back-money  [luc jean]

    ; Who has seen committing a crime
        has-seen-committing-a-crime [jean alain]

    ; Who has a weapon
        has-a-weapon [luc]
        has-a-weapon [louis]
        has-a-weapon [alain]
    ]

Here we call the goals

    print [newline "*** Who killed jean Tuesday ***"]
    goal rule [
        can-have-killed [X jean tuesday]
        (print ["==>" X "can have done it"])
    ]

    print [newline "*** Who could be a murder ***"]
    goal rule [
        fact/has-a-weapon [X]
        can-have-killed? [X _ _]
        (print ["==>" X "could be a murder"])
    ]

    print [newline "*** Who could be a victim ***"]
    goal rule [
        can-have-killed? [_ Y _]
        (print ["==>" Y "could be killed"])
    ]

    print [newline "*** When a crime could take place?***"]
    goal rule [
        day [Z]
        can-have-killed? [_ _ Z]
        (print ["==> A crime could take place" Z])
    ]

3. Performance

On my PC, the performance of prolog.r is around 650 LIPS (Logical Inference Per Second). It's quiet few but this is mesured on predicate that you will never implement in prolog dialect. The usual bench to mesure LIPS is the NREV predicate (naive reverse of a list) :

    do %engine.r
    print ""
    print "****************************"
    print "**** Start of benchmark ****"
    ex-base: assert none probe [
        concat [[] L L] [!]
        concat [[X | L1] L2 [X | L3]] [
            concat [L1 L2 L3]
        ]
        nrev [[] []] [!]
        nrev [[X | Y] L] [
            nrev [Y Z]
            concat [Z [X] L]
        ]
    ]
    i: 100
    j: 0
    t: bench-goal i ex-base [
        nrev [[1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30] L]
        (print ["Boucle :" j: j + 1])
    ]

    print ["Length" t]
    print ["Performance (LIPS)" (i * (30 + 1) * (30 + 2) / 2) / to-decimal t]

    print ""
    print "**** End of benchmark ****"
    print "**************************"

First of all, I am not a specialist of programming langage. I have no particular competence to build things like that and I make it with my own logic just for fun. Certainly a guy with all the necessary competences will make it much more faster and smaller.

You should also take prolog.r as an add-on to REBOL and use it only for non-deterministic logic. If you want to reverse a list, use the reverse REBOL function. It's why it was very important to be able to embed REBOL code within the clauses in a simple manner, as it was also important to invoke the goals easyly.

So I hope that the obtained performances are good enough for small part of a program where it's much more easy to specify the logic with clauses. And for the remaining part of the programm, we should write it with standard REBOL script.

Perhaps Carl will implement a native unify function which will be usefull for prolog.r but also for other REBOL script. In the same manner, if the find/match rafinement functioned on the blocks, prolog.r would be much faster. But this it's another story.

4. Conclusion

When I was programming in Turbo Prolog, I found very tedious to write all the deterministic part of the program with clauses that you force to be deterministic with a lot of CUT.

I believe prolog.r, which allows the mix of REBOL and Prolog within the same script and with a syntax continuity, is a good base to write funny script with Logic Programming.

I hope you will have fun with it, Marco.