The gulava.Cons type represents a list and has a few simple predicates associated with it. This page takes a look at Cons and the append predicate. After reading this, you should be able to write your own predicates and values, similar to what you would find in an Prolog course.

Cons is a singly-linked list. It has a car and a cdr field. The car field represents the first item in the list. The cdr field is another list which contains the rest of the elements. Cons.of can be used to create a new list from the car and cdr values. A null reference represents the empty list. For instance:

Object list = Cons.of("foo", Cons.of("bar", null))

represents a list with two items, and calling toString on that list will return [foo, bar].

An easier way to create a list with multiple elements is to use Cons.s, which automatically creates the nested Cons cells:

Object list = Cons.s("foo", "bar")

A list where only the first item is known but the rest of the list is not would be represented with a gulava.Var in the cdr position:

Var rest = new Var();
Object list = Cons.of("foo", rest);

Below is a snippet of Cons.java.

@gulava.annotation.MakeLogicValue
public abstract class Cons<CAR, CDR> {
  Cons() {}

  public abstract CAR car();
  public abstract CDR cdr();

  public static <CAR, CDR> Cons<CAR, CDR> of(CAR car, CDR cdr) {
    return new MakeLogicValue_Cons<>(car, cdr);
  }
}

MakeLogicValue causes a subclass to be created called MakeLogicValue_${original_class_name}. This class implements the accessors, constructor, toString, equals, hashCode, and the methods in gulava.LogicValue. You can make a working logic value without MakeLogicValue, but it requires a lot of boilerplate that is rarely necessary to customize.

public abstract class Cons<CAR, CDR> {

Because the fields in a logic value can be anything (e.g. a String, a Var, or another logic value), each field is assigned a separate generic template argument.

Cons() {}

The constructor is explicitly declared here to make it package protected and to make it hard to create an implementation separate from the automatically-created one.

public abstract CAR car();
public abstract CDR cdr();

Each field has its own accessor. There is no setter and the getter doesn't have get prepended to the name.

public static <CAR, CDR> Cons<CAR, CDR> of(CAR car, CDR cdr) {
  return new MakeLogicValue_Cons<>(car, cdr);
}

A logic value must have a static factory method called of which allows specifying each field in the same order as the accessors. This is important for the readability of your own code, but also because Gulava will generate code that uses this method.

Below is more code from Cons.java which defines a predicate.

import static gulava.Goals.UNIT;
import static gulava.Goals.conj;
import static gulava.Goals.same;

...

  public static final Goals O = new MakePredicates_Cons_Goals();

  @gulava.annotation.MakePredicates
  public static abstract class Goals {
    public abstract gulava.Goal append(Object a, Object b, Object ab);

    final gulava.Goal append_baseCase(Void a, Object b, Object ab) {
      return same(b, ab);
    }

    final gulava.Goal append_iterate(Cons<?, ?> a, Object b, Cons<?, ?> ab) {
      return new DelayedGoal(
          conj(
              same(a.car(), ab.car()),
              append(a.cdr(), b, ab.cdr())));
    }
  }

As you can see, this also uses an annotation to create a class: MakePredicates, which generates an implementation of the Goals inner class. The O static field is intended as a shorthand for external callers to get a working instance of Goals.

public abstract gulava.Goal append(Object a, Object b, Object ab);

Each predicate is declared with a public abstract method which returns Goal and accepts an Object for each predicate argument. To attach documentation to a predicate, attach it to this method. In this example, append is a predicate that indicates the list ab is a concatenation of a and b.

A predicate is true if any of its clauses is true. Each clause is a final, package-protected method with the same number of arguments as the public method. It has a name of the form ${predicate_name}_${clause_description}. The clause description can be anything and is like a comment - it is not referred to by any code you write. append is comprised of the following two clauses:

final Goal append_baseCase(Void a, Object b, Object ab) { ... }
final Goal append_iterate(Cons<?, ?> a, Object b, Cons<?, ?> ab) { ... }

Each predicate has different types for the arguments. A ? or Object indicates the argument or field at that position can be bound to anything. Void indicates the argument or field must be null. A logic value, such as Cons<?, ?> indicates that the argument must be bound to a value of that type. You can nest types as deep as necessary inside the generic type arguments. For instance, a two-element list would be represented by:

Cons<?, Cons<?, Void>>

You cannot use any other types besides other LogicValue implementations. For instance, String and Integer are not allowed.

The automatically-implemented abstract method will qualify the Goals returned by the clauses to ensure that values of the correct type are bound to each argument.

final gulava.Goal append_baseCase(Void a, Object b, Object ab) {
  return same(b, ab);
}

The baseCase clause indicates that if a is an empty list, then b and ab are equivalent. It uses the Goal factory method gulava.Goals.same to indicate the equivalency relation.

final Goal append_iterate(Cons<?, ?> a, Object b, Cons<?, ?> ab) {
  return new DelayedGoal(
      conj(
          same(a.car(), ab.car()),
          append(a.cdr(), b, ab.cdr())));
}

The iterate clause is recursive and works to transform (not exactly, but in a sense) a to a shorter list until it is empty, so that baseCase can be used. We'll read the code in an inside-out order:

same(a.car(), ab.car())

The first element (car) of a and ab must be the same.

append(a.cdr(), b, ab.cdr())

a.cdr() appended to b is ab.cdr()

conj(..., ...);

The previous two Goals must both succeed (conj is short for conjoin and can be read as "and"). You can also create "or" goals with gulava.Goals.disj.

new DelayedGoal(...)

Creates a new Goal that is equivalent to the one passed, but causes it to be lowered in priority if it is or'd with other Goals. This is hard to reason about and hard to know when to use. Generally, I don't use it at all until I start to see StackOverflowErrors or some other Goal is not returning results.

You can see the results of some append invocations by adding them to "java/gulava/Demo.java" and then running bazel run //java/gulava:Demo from inside the Gulava repository. For instance, try pasting this code into Demo.main():

System.out.println("\nTry append");
Goal append = Cons.O.append(a, b, Cons.s(1, 2, 3, 4));
print(append.run(Subst.EMPTY), 10, dump, a, b);

The output will be something like:

Try append
{_.1=[1,2,3,4], _.0=null}
{_.1=[2,3,4], _.0=[1]}
{_.1=[3,4], _.0=[1,2]}
{_.1=[4], _.0=[1,2,3]}
{_.1=null, _.0=[1,2,3,4]}
()

The empty parenthesis at the end indicates all the results have been shown. As you can see, there are five possible solutions to append(a, b, [1, 2, 3, 4]), where the original lists are of varying sizes.