<< Tutorial 2 ^^Contents Tutorial 4 >>

Yield Prolog Tutorial

3. ListPair

In Tutorial 3, we work with the ListPair class to make lists.

Making a list with ListPair

A ListPair has a "head" and a "tail". The head is the first element in the list and the tail is the rest of the list. Usually the tail points to another ListPair object or to and empty list if there are no more elements in the list. In this way, you chain together ListPair objects to make a list of any length.

Here we define a function makeList which sets List to a list from the two arguments First and Second:

Python
 C#
 
import sys
# Hack sys.path for the examples.
sys.path.append("../..")
from YP import *
from Variable import *
from ListPair import *

def makeList(First, Second, List):
    list1 = ListPair(Second, Atom.NIL)
    result = ListPair(First, list1)
    for l1 in YP.unify(List, result):
        yield False

def main():
    print("Return a list of 2 elements:")
    List = Variable()
    for l1 in makeList("a", "b", List):
        print("List = " + str(List.getValue()))

 
using System;
using System.Collections.Generic;
using YieldProlog;
class Tutorial3
{
    static IEnumerable<bool> makeList
               (object First, object Second, object List) {
        ListPair list1 = new ListPair(Second, Atom.NIL);
        ListPair result = new ListPair(First, list1);
        foreach (bool l1 in YP.unify(List, result))
            yield return false;
    }

    static void Main(string[] args) {
        Console.WriteLine("Return a list of 2 elements:");
        Variable List = new Variable();
        foreach (bool l1 in makeList("a", "b", List))
            Console.WriteLine("List = " + List.getValue());
    }
}

It is easier to build lists starting from the end and working backwards, so makeList first sets list1 to a ListPair where the head is Second and the tail is the emtpy list Atom.NIL. (Nil is defined as "[]" which looks like an empty list.) On its own, list1 is now a valid list with one element which is the Second argument. Then it sets result to a ListPair where the head is First and the tail is the list1 list we just made. Finally it unifies the result with the List argument. (As we'll see, you don't have to use temporary variables like list1 and result, but we do it here for clarity.)

The main function calls makeList with arguments "a" and "b" and the third argument receives the result List.  [1] This prints:
Return a list of 2 elements:
List = [a, b]
This shows the result [a, b] in the standard Prolog way where the list elements are between brackets [] and separated by a comma.

Unifying two lists

As always, since makeList uses unify it can be used in many ways. Consider this:

import sys
# Hack sys.path for the examples.
sys.path.append("../..")
from YP import *
from Variable import *
from ListPair import *

def makeList(First, Second, List):
    list1 = ListPair(Second, Atom.NIL)
    result = ListPair(First, list1)
    for l1 in YP.unify(List, result):
        yield False

def main():
    print("Unify two lists:")
    Second = Variable()
    for l1 in makeList("x", Second,
          ListPair("x", ListPair("y", Atom.NIL))):
        print("The second element is " + Second.getValue())

 
using System;
using System.Collections.Generic;
using YieldProlog;
class Tutorial3
{
    static IEnumerable<bool> makeList
               (object First, object Second, object List) {
        ListPair list1 = new ListPair(Second, Atom.NIL);
        ListPair result = new ListPair(First, list1);
        foreach (bool l1 in YP.unify(List, result))
            yield return false;
    }

    static void Main(string[] args) {
        Console.WriteLine("Unify two lists:");
        Variable Second = new Variable();
        foreach (bool l1 in makeList("x", Second, 
              new ListPair("x", new ListPair("y", Atom.NIL))))
            Console.WriteLine("The second element is " + 
                              Second.getValue());
    }
}

(The code for makeList is the same as before.) When the main function calls makeList, the First and Second arguments are "x" and an unbound variable. And, instead of returning a list in the List argument, it constructs and passes in the list [x, y]. (Notice that we can construct a list by chaining together many ListPair.)

As before, makeList sets result to a list of the arguments First and Second, then unifies this with the List argument. When Prolog unifies two lists, it unifies the first element of both lists, then the second element of both lists, etc. In this case, because result is a list of First and Second, makeList unifies First with the first element of List and Second with the second element of List. What happens in this case? Since First is "x" and the first element of List is also "x", this succeeds. And since Second is an unbound variable, unify binds it to the second element of List which is "y". [2] So, the main function prints the value of Second:
Unify two lists:
The second element is y
We went through this in agonizing detail, but the idea is simple. When Prolog unifies two lists, it unifies each of the matching elements of both lists. (Both lists must have the same number of elements for unify to succeed.) If all of the elements are bound values, this checks that both lists are equal. But if an element of one of the lists is an unbound variable, this binds the variable to "extract" the value of the matching element from the other list.

In Tutorial 4, we do more advanced work with the parser, compiler and module system.


1. The equivalent Prolog code for this example is:
makeList(First, Second, List) :-
  List = [First, Second].
:- makeList(a, b, List).
Of course, you can also write the more compact:
makeList(First, Second, [First, Second]).
2. The equivalent Prolog code for this example is:
makeList(First, Second, List) :-
  List = [First, Second].
:- makeList(x, Second, [x, y]).