Yield Prolog Tutorial

1. Introduction

This tutorial introduces you to Yield Prolog. For this tutorial, you do not need to know Prolog, but hopefully you will learn something about it. The example code is in the distribution directory:

Python (requires Python 2.5): source/python/examples/YieldPrologTutorial/tutorial1.py
C# (requires .NET 2.0): source/csharp/examples/YieldPrologTutorial/Tutorial1.cs
In Visual Studio .NET, you can load YieldPrologTutorial.sln . In the project properties, make sure the Startup Object is Tutorial1.
Javascript (requires yield support such as Firefox 3): source/javascript/examples/YieldPrologTutorial/tutorial1.js .
Open tutorial1.html from the same directory in a browser.

The yield keyword

You can use the yield keyword in a function to return an iterator to use in for...in. For example:

Python

def personWithReturnValue():
    yield "Chelsea"
    yield "Hillary"
    yield "Bill"

def main():
    print("Names using a return value:")
    for p in personWithReturnValue():
        print(p)

using System;
using System.Collections.Generic;
class Tutorial1
{
    static IEnumerable<string> personWithReturnValue() {
        yield return "Chelsea";
        yield return "Hillary";
        yield return "Bill";
    }

    static void Main(string[] args) {
        Console.WriteLine("Names using a return value:");
        foreach (string p in personWithReturnValue())
            Console.WriteLine(p);
    }
}

Because of the yield keyword, when you call personWithReturnValue, it automatically returns an object that for...in uses as an iterator. On each pass, the iterator returns the value given by the yield keyword. So, the main function outputs:

Names using a return value:
Chelsea
Hillary
Bill

Note that, because it is an iterator, a function like personWithReturnValue can yield 0, 1 or more times. In the example above, it yields 3 times.

For more information on the yield keyword, see this for Python (requires Python 2.5) or this for C# (requires .NET 2.0).

Using a simple variable to return values

Instead of getting the result from the yield return value, we can pass an object into the iterator which it will use to return the value. (This is useful when we want to return more than one result at a time.) Here is the simplest way to do it:

class SimpleVariable:
    pass

def personWithSimpleVariable(Person):
    Person._value = "Chelsea"
    yield False
    Person._value = "Hillary"
    yield False
    Person._value = "Bill"
    yield False

def main():
    print("Names using SimpleVariable:")
    P = SimpleVariable()
    for l1 in personWithSimpleVariable(P):
        print(P._value)

using System;
using System.Collections.Generic;

class SimpleVariable
{
    public object _value;
}

class Tutorial1
{
    static IEnumerable<bool> personWithSimpleVariable
	(SimpleVariable Person) {
        Person._value = "Chelsea";
        yield return false;
        Person._value = "Hillary";
        yield return false;
        Person._value = "Bill";
        yield return false;
    }

    static void Main(string[] args) {
        Console.WriteLine("Names using SimpleVariable:");
        SimpleVariable P = new SimpleVariable();
        foreach (bool l1 in personWithSimpleVariable(P))
            Console.WriteLine(P._value);
    }
}

The class SimpleVariable just has a member _value. The iterator function personWithSimpleVariable takes a SimpleVariable argument called Person. (Why spell the argument Person with an upper case letter? This is an old habit from Prolog where variable names start with an upper case letter. But in Yield Prolog, this is not required.)

Each time personWithSimpleVariable needs to return a result, it sets Person._value and yields. The actual value returned by the yield keyword doesn't matter any more, so we always return false. In the main function, we create an instance of SimpleVariable and pass it to personWithSimpleVariable. Then, inside the for...in loop, we print its _value. As before, it prints the three names.

Using UnifyingVariable to return values

We are almost there. We need a better variable class that keeps track of whether _value has an assigned value or not. If it has an assigned value, we say the variable is "bound", otherwise it is "unbound". To handle this, we create a new class UnifyingVariable with the function unify:

class UnifyingVariable:
    def __init__(self):
        self._isBound = False

    def unify(self, arg):
        if not self._isBound:
            self._value = arg
            self._isBound = True
            yield False
            # Remove the binding.
            self._isBound = False
        elif self._value == arg:
            yield False

class UnifyingVariable
{
    public object _value;
    public bool _isBound = false;

    public IEnumerable<bool> unify(object arg) {
        if (!_isBound) {
            _value = arg;
            _isBound = true;
            yield return false;
            // Remove the binding.
            _isBound = false;
        }
        else if (_value.Equals(arg))
            yield return false;
    }
}

Notice that unify is also an iterator function. If the value is unbound, it sets it to the arg argument, sets _isBound true and yields as we did in personWithSimpleVariable. After the yield, we remove the binding by setting _isBound false. Also notice that if the value is already bound, it checks if the bound value equals the arg argument. We will discuss this shortly.

Here is how we use UnifyingVariable to return the three person names:

def personWithUnify(Person):
    for l1 in Person.unify("Chelsea"):
        yield False
    for l1 in Person.unify("Hillary"):
        yield False
    for l1 in Person.unify("Bill"):
        yield False

def main():
    print("Names using UnifyingVariable:")
    Person = UnifyingVariable()
    for l1 in personWithUnify(Person):
        print(Person._value)

using System;
using System.Collections.Generic;
class Tutorial1
{
    static IEnumerable<bool> personWithUnify
	(UnifyingVariable Person) {
        foreach (bool l1 in Person.unify("Chelsea"))
            yield return false;
        foreach (bool l1 in Person.unify("Hillary"))
            yield return false;
        foreach (bool l1 in Person.unify("Bill"))
            yield return false;
    }

    static void Main(string[] args) {
        Console.WriteLine("Names using UnifyingVariable:");
        UnifyingVariable Person = new UnifyingVariable();
        foreach (bool l1 in personWithUnify(Person))
            Console.WriteLine(Person._value);
    }
}

Believe it or not, this is a Prolog program [1]. This UnifyingVariable class can be used for most Prolog programs. (However, Yield Prolog uses an enhanced Variable class that improves efficiency and addresses a few issues that we discuss in Tutorial 2.) In the rest of this tutorial, we experiement with UnifyingVariable and add a few helper functions.

How does personWithUnify work? For each of the 3 values, it unifies Person with the value and yields. Person.unify is used in a for...in loop, but the loop only goes through one iteration, so why use a loop? Why not just call unify once? It is true that unify only yields once, but remember that after it yields, it removes the binding before the for...in loop quits. This is important because Person needs to be unbound before we do the next for...in loop which binds it to a new value.

The main function passes the Person variable to personWithUnify in a for...in loop which prints each name by calling Person._value.

How unify works

The unify function in UnifyingVariable actually performs two tasks:

If the value is unbound, it binds it to the argument.
If the value is bound, it compares the value to the argument. If the values are equal, unify yields once. (It "succeeds.") If the values are not equal, unify does not yield. (It "fails.") In this way, if the value is bound, unify acts more like an if statement. If the values are equal, the code in the for...in block executes once, otherwise it is not executed.

Using unify to check values

We can use unify to check a bound value like this:

def personWithUnify(Person):
    for l1 in Person.unify("Chelsea"):
        yield False
    for l1 in Person.unify("Hillary"):
        yield False
    for l1 in Person.unify("Bill"):
        yield False

def main():
    print("Use unify to check a person:")
    Person = UnifyingVariable()
    for l1 in Person.unify("Hillary"):
        for l2 in personWithUnify(Person):
            print("Hillary is a person.")
    for l1 in Person.unify("Buddy"):
        for l2 in personWithUnify(Person):
            # This won't print.
            print("Buddy is a person.")

using System;
using System.Collections.Generic;
class Tutorial1
{
    static IEnumerable<bool> personWithUnify
	(UnifyingVariable Person) {
        foreach (bool l1 in Person.unify("Chelsea"))
            yield return false;
        foreach (bool l1 in Person.unify("Hillary"))
            yield return false;
        foreach (bool l1 in Person.unify("Bill"))
            yield return false;
    }

    static void Main(string[] args) {
        Console.WriteLine("Use unify to check a person:");
        UnifyingVariable Person = new UnifyingVariable();
        foreach (bool l1 in Person.unify("Hillary")) {
            foreach (bool l2 in personWithUnify(Person))
                Console.WriteLine("Hillary is a person.");
        }
        foreach (bool l1 in Person.unify("Buddy")) {
            foreach (bool l2 in personWithUnify(Person))
                // This won't print.
                Console.WriteLine("Buddy is a person.");
        }
    }
}

(The code for personWithUnify is the same as before.) In the main function, we bind Person to "Hillary" and call personWithUnify. So, when personWithUnify calls Person.unify("Chelsea"), Person is already bound, so unify does not yield because the values are not equal. But, personWithUnify next calls Person.unify("Hillary"). The values are equal, so unify yields once which causes personWithUnify to yield once and we print "Hillary is a person". Next, "Hillary" and "Bill" are not equal, so it doesn't yield for "Bill".

In the main function, after we check "Hillary", we bind Person to "Buddy" and call personWithUnify. Since this doesn't match any of the person names, personWithUnify never yields, and so we never execute the code in the loop to print "Buddy is a person".

generalGetValue and generalUnify

In the previous example, we have to bind Person to "Hillary", before we call personWithUnify(Person). We have to do this first step because personWithUnify takes an argument of type UnifyingVariable. But life would be easier if we could just call personWithUnify("Hillary"). To do this, we create separate general functions:

def generalGetValue(value):
    if isinstance(value, UnifyingVariable):
        if not value._isBound:
            return value
        else:
            return value._value
    else:
        return value

def generalUnify(arg1, arg2):
    arg1Value = generalGetValue(arg1)
    arg2Value = generalGetValue(arg2)
    if isinstance(arg1Value, UnifyingVariable):
        for l1 in arg1Value.unify(arg2Value):
            yield False
    elif isinstance(arg2Value, UnifyingVariable):
        for l1 in arg2Value.unify(arg1Value):
            yield False
    else:
        # Arguments are "normal" types.
        if arg1Value == arg2Value:
            yield False

using System;
using System.Collections.Generic;
class Tutorial1
{
    static object generalGetValue(object value) {
        if (value is UnifyingVariable) {
            if (!((UnifyingVariable)value)._isBound)
                return value;
            else
                return ((UnifyingVariable)value)._value;
        }
        else
            return value;
    }

    static IEnumerable<bool> generalUnify(object arg1, object arg2)
    {
        object arg1Value = generalGetValue(arg1);
        object arg2Value = generalGetValue(arg2);
        if (arg1Value is UnifyingVariable) {
            foreach (bool l1 in 
                 ((UnifyingVariable)arg1Value).unify(arg2Value))
                yield return false;
        }
        else if (arg2Value is UnifyingVariable) {
            foreach (bool l1 in 
                 ((UnifyingVariable)arg2Value).unify(arg1Value))
                yield return false;
        }
        else {
            // Arguments are "normal" types.
            if (arg1Value.Equals(arg2Value))
                yield return false;
        }
    }
}

In the generalGetValue function, if the argument is an unbound UnifyingVariable, then return it. (We'll see why shortly.). If the argument is a bound UnifyingVariable, then return its _value. Otherwise, if the argument is some other type (such as a string), just return the argument.

The generalUnify function takes two arguments which we try to unify. Note that we first call generalGetValue for each of the arguments. For example, if arg1 is a UnifyingArgument which is bound to the string "Hillary", then arg1Value is just the string "Hillary". If arg1 is an unbound UnifyingVariable, then generalGetValue just returns it and we continue to treat it as a variable. This is why it returns the argument itself (instead of null) if the argument is an unbound UnifyingVariable.

So in generalUnify, if either argument is an unbound UnifyingVariable, just call its unify to bind it to the other argument. Otherwise, if both arguments have "normal" types, or are bound to "normal" types (such as a string), then just check if they are equal.

It's a little work to create these general functions, but now we can use them to make our code simpler:

def person(Person):
    for l1 in generalUnify(Person, "Chelsea"):
        yield False
    for l1 in generalUnify(Person, "Hillary"):
        yield False
    for l1 in generalUnify(Person, "Bill"):
        yield False

def main():
    print("Use generalUnify to check a person:")
    for l1 in person("Hillary"):
        print("Hillary is a person.")
    for l1 in person("Buddy"):
        # This won't print.
        print ("Buddy is a person.")

using System;
using System.Collections.Generic;
class Tutorial1
{
    static IEnumerable<bool> person(object Person) {
        foreach (bool l1 in generalUnify(Person, "Chelsea"))
            yield return false;
        foreach (bool l1 in generalUnify(Person, "Hillary"))
            yield return false;
        foreach (bool l1 in generalUnify(Person, "Bill"))
            yield return false;
    }

    static void Main(string[] args) {
        Console.WriteLine
	     ("Use generalUnify to check a person:");
        foreach (bool l1 in person("Hillary"))
            Console.WriteLine("Hillary is a person.");
        foreach (bool l1 in person("Buddy"))
            // This won't print.
            Console.WriteLine("Buddy is a person.");
    }
}

The function person takes a general object instead of a UnifyingVariable, so it calls generalUnify. In the main function, as we wanted, we can simply call person("Hillary") to check if "Hillary" is a person. We don't have to create an extra UnifyingVariable. Isn't that better!

The meaning of unify

Because unify can either bind values or check values, it enforces a logical relation. This is why programming languages that use it (like Prolog) are called "logic languages." If you are inside a loop defined by a call to person(Person), you can be sure that the loop will explore all the ways that Person is a person. If Person is unbound at the start of the loop, person will bind it to all known persons. Or if Person is bound at the start of the loop, person will ensure that it matches one of the possible person values.

Next, we will see an example of a function brother that takes two arguments, Person and Brother, but the meaning is the same: brother makes sure that the loop explores all possible ways that the arguments are logically related so that Brother is the brother of Person.

Finding relations

Here is a function with two arguments called brother:

def brother(Person, Brother):    
    for l1 in generalUnify(Person, "Hillary"):
        for l2 in generalUnify(Brother, "Tony"):
            yield False
        for l2 in generalUnify(Brother, "Hugh"):
            yield False
    for l1 in generalUnify(Person, "Bill"):
        for l2 in generalUnify(Brother, "Roger"):
            yield False

def main():
    print("Find relations:")
    Brother = UnifyingVariable()
    for l1 in brother("Hillary", Brother):
        print("Hillary has brother " + 
	  Brother._value + ".")

using System;
using System.Collections.Generic;
class Tutorial1
{
    static IEnumerable<bool> brother
	(object Person, object Brother) {
        foreach (bool l1 in generalUnify(Person, "Hillary")) {
            foreach (bool l2 in generalUnify(Brother, "Tony"))
                yield return false;
            foreach (bool l2 in generalUnify(Brother, "Hugh"))
                yield return false;
        }
        foreach (bool l1 in generalUnify(Person, "Bill")) {
            foreach (bool l2 in generalUnify(Brother, "Roger"))
                yield return false;
        }
    }

    static void Main(string[] args) {
        Console.WriteLine("Find relations:");
        UnifyingVariable Brother = new UnifyingVariable();
        foreach (bool l1 in brother("Hillary", Brother))
            Console.WriteLine("Hillary has brother " +
                Brother._value + ".");
    }
}

The brother function unifies Person and Brother with pairs that mean "Hillary" has brother "Tony", "Hillary" has brother "Hugh", and "Bill" has brother "Roger".

The main function calls brother where the Person argument is "Hillary" and Brother is an unbound variable. brother binds Brother to each of the values that match when Person is "Hillary". (Since brother uses generalUnify, we can pass the string "Hillary" without first binding it to a UnifyingVariable.) So, the main function prints:

Find relations:
Hillary has brother Tony.
Hillary has brother Hugh.

Again, the logical meaning is that brother loops with all matches where Brother is the brother of Person. In this way, brother is actually 4 different functions:

If Person and Brother are unbound variables, loop where these are bound to each of the person/brother pairs.
If Person is bound, loop where Brother is bound to each brother of Person (as in the example above).
If Brother is bound, loop where Person is bound to each person who has brother Brother.
If both are bound, loop once if Brother is the brother of Person. If not, then don't loop.

In this way, because unify does "double duty" on each argument, with 2 arguments we really get 4 functions, with 3 arguments we really get 8 functions, etc.

Joining functions

We have a function for brother. If we define a function for parent, then we can combine them to infer whether a person has an uncle. (A person has an uncle if the person has a parent and that parent has a brother.)

def brother(Person, Brother):    
    for l1 in generalUnify(Person, "Hillary"):
        for l2 in generalUnify(Brother, "Tony"):
            yield False
        for l2 in generalUnify(Brother, "Hugh"):
            yield False
    for l1 in generalUnify(Person, "Bill"):
        for l2 in generalUnify(Brother, "Roger"):
            yield False

def parent(Person, Parent):
    for l1 in generalUnify(Person, "Chelsea"):
        for l2 in generalUnify(Parent, "Hillary"):
            yield False
    for l1 in generalUnify(Person, "Chelsea"):
        for l2 in generalUnify(Parent, "Bill"):
            yield False

def uncle(Person, Uncle):
    Parent = UnifyingVariable()
    for l1 in parent(Person, Parent):
        for l2 in brother(Parent, Uncle):
            yield False

def main():
    print("Joining functions:")
    Person = UnifyingVariable()
    Uncle = UnifyingVariable()
    for l1 in uncle(Person, Uncle):
        print(Person._value + 
	  " has uncle " + Uncle._value + ".")

using System;
using System.Collections.Generic;
class Tutorial1
{
    static IEnumerable<bool> brother
	(object Person, object Brother) {
        foreach (bool l1 in generalUnify(Person, "Hillary")) {
            foreach (bool l2 in generalUnify(Brother, "Tony"))
                yield return false;
            foreach (bool l2 in generalUnify(Brother, "Hugh"))
                yield return false;
        }
        foreach (bool l1 in generalUnify(Person, "Bill")) {
            foreach (bool l2 in generalUnify(Brother, "Roger"))
                yield return false;
        }
    }

    static IEnumerable<bool> parent
	(object Person, object Parent) {
        foreach (bool l1 in generalUnify(Person, "Chelsea")) {
            foreach (bool l2 in generalUnify(Parent, "Hillary"))
                yield return false;
        }
        foreach (bool l1 in generalUnify(Person, "Chelsea")) {
            foreach (bool l2 in generalUnify(Parent, "Bill"))
                yield return false;
        }
    }

    static IEnumerable<bool> uncle
	(object Person, object Uncle) {
        UnifyingVariable Parent = new UnifyingVariable();
        foreach (bool l1 in parent(Person, Parent)) {
            foreach (bool l2 in brother(Parent, Uncle))
                yield return false;
        }
    }

    static void Main(string[] args) {
        Console.WriteLine("Joining functions:");
        UnifyingVariable Person = new UnifyingVariable();
        UnifyingVariable Uncle = new UnifyingVariable();
        foreach (bool l1 in uncle(Person, Uncle))
            Console.WriteLine(Person._value +
                " has uncle " + Uncle._value + ".");
    }
}

(The code for brother is the same as before.) We add function parent which unifies Person and Parent with the following pairs: ("Chelsea", "Hillary") and ("Chelsea", "Bill"). The function uncle(Person, Uncle) has a local variable Parent and unifies with parent(Person, Parent). Then, for each parent of the Person it unifies with brother(Parent, Uncle) to match the uncle of Person. When the main function calls uncle, Person and Uncle are unbound, so it prints all person/uncle pairs:

Joining functions:
Chelsea has uncle Tony
Chelsea has uncle Hugh
Chelsea has uncle Roger

The "uncle" function is a classic example of inference using Prolog [2]. We only have data for who is a parent and who is a brother, and yet we can infer who is an uncle. Again, because of unify, uncle is really 4 different functions and we can use it to find all person/uncle pairs, to find the uncles of a person, to find the persons who have a certain uncle, or to check whether someone is the uncle of another person.

In Tutorial 2, we improve UnifyingVariable to create the full Variable class which Yield Prolog actually uses.

1. The equivalent Prolog code for this example is:

personWithUnify(Person) :-
  Person = 'Chelsea' ; Person = 'Hillary' ; Person = 'Bill'.
:- personWithUnify(Person), write(Person), nl.

Yes, the Prolog code is much more compact, but wait until you see the speed and convenience of using Prolog functionality right inside your program.

2. The equivalent Prolog code for this example is:

brother(Person, Brother) :-
  Person = 'Hillary', (Brother = 'Tony' ; Brother = 'Hugh') ;
  Person = 'Bill', Brother = 'Roger'.
parent(Person, Parent) :-
  Person = 'Chelsea', Parent = 'Hillary' ;
  Person = 'Chelsea', Parent = 'Bill'.
uncle(Person, Uncle) :-
  parent(Person, Parent),
  brother(Parent, Uncle).
:- uncle(Person, Uncle), write(hasUncle(Person, Uncle)), nl.

Chaining together parent and brother is also an example of a join in a relational database. Here is the SQL code:

SELECT parent.Person AS Person, brother.Brother AS Uncle
FROM parent JOIN brother ON parent.Parent = brother.Person

But SQL doesn't use unify. This query returns all Person/Uncle pairs. But if we want to find who has a particular uncle, we have to write a new query:

SELECT parent.Person AS Person, brother.Brother AS Uncle
FROM parent JOIN brother ON parent.Parent = brother.Person
WHERE brother.Brother = 'Hugh'

In Yield Prolog, we can use the same uncle function and just change the main function to:

def main():
    Person = UnifyingVariable()
    for l1 in uncle(Person, "Hugh"):
        print(Person._value + 
	  " has uncle Hugh."

    static void Main(string[] args) {
        UnifyingVariable Person = new UnifyingVariable();
        foreach (bool l1 in uncle(Person, "Hugh"))
            Console.WriteLine(Person._value +
                " has uncle Hugh.");
    }

As expected, this prints:

Chelsea has uncle Hugh