mndrix / golog

Prolog interpreter in Go

golog

Prolog interpreter in Go with aspirations to be ISO compatible. See the full package documentation for usage details.

Install with

go get github.com/mndrix/golog

Status

The long term goal is to make Golog fully compliant with ISO Prolog. It currently supports a subset of ISO Prolog. Any deviations from the standard are bugs. Please report issues to help Golog improve.

Golog is used in production systems, but should be considered experimental software. It has bugs and sharp edges.

Development is sponsored by PriceCharting.

golog's Issues

support tabling

I don't have any clear ideas about implementation, but it's a cool idea which should help performance in some use cases.

Tighter code intergration with golang

The idea of having a Prolog-like reference engine in go is brilliant, however I feel that the balance is tilted too much towards the Prolog end. Since the package mainly serves programs in Go, it would actually make more sense to design the interface and APIs more in the way of Go rather than that of Prolog.

Currently I'm building up callables in ways like this:

func NewRule(fact t.Term, conditions ...t.Term) t.Callable {
    // build the comma separated callable list
    cond := conditions[0]
    if len(conditions) > 1 {
        for _, c := range conditions[1:] {
            cond = t.NewCallable(",", cond, c)
        }
    }
    return t.NewCallable(":-", fact, cond)
}

As you can see this is really awkward. I understand the package is intended to be used by feeding in straight strings written in Prolog, but there is no reason why the underlying API couldn't be restructured to fit a more programmatic approach - that will not only allow the Go language to be used more to its advantage, but also saves the cost of parsing. This would be especially meaningful if one is to build a reference engine of relatively big size.

Some problems will lend themselves to easier solutions if this consideration is taken into account. For example, on the issues of atom representation #14, one can simply allow the user to define custom inherit types of Atom that doesn't contain anything if the user wants to save space. One can even imagine the whole system being opened up for more complicated unification processes - the user can define more custom variables and terms and tailor the unification process however they want.

The implementation of relating different functors to their respective functions inside Go feels a bit awkward to me as well. Currently one has to call registerForeign, and throws away a first class function instead to use a token identity for its representation. If we de-couple parsing from reference-working completely, we can just use the function value inside the engine - the user will then use the same function inside Assertz. This is more reader-friendly, and again, more efficient.

All in all, what I'm suggesting is to separate the syntax and logic of Prolog - the logic (mainly unification) should open itself up to suit more programming needs of Go programmers, while the syntax can be any form one would like - be it Go, or Prolog.

support attributed variables

Review each of the major Prolog implementations to see which primitives they have for attributed variables. Support those primitives in Golog. Build similar libraries (or reuse existing ones) on top of these primitives.

optimize atom representation

Atoms (especially those used as functor names), are really just fancy integers with a human-readable form. I suspect that about 85% of all atoms can be mapped to a 64-bit integer. For those that can't be, fall back to the current string representation.

• create a CodedAtom type which implements the Atom interface
• have NewAtom try to create a coded atom then fall back to a string atom
• unification of two compressed atoms is just integer comparison

The simplest coding that could possibly work is:

• treat an atom string as a base-27 (lowercase letters + underscore) integer
• add and multiply our way through the string
• if an unknown letter is encountered or we run out of numeric precision, fall back to a string representation.

Optimize that by extending the base-27 alphabet to a base-64 alphabet where the extra 37 symbols are the 37 most common bigrams in English text. A base-32 alphabet with only 5 bigrams might work better.

Optimize that with Huffman coding or arithmetic encoding to fit more symbols into a 64 bit integer (or float).

The real goal here is not to achieve the highest possible compression ratio (encoding long atoms into small integers). Rather, we want to encode the highest percentage of atoms into a fixed space.

If I've correctly understood Go's internal string representation, a single-character string occupies 17 bytes on a 64-bit machine.

Use type assertions instead of reflect.

This line can be simplified down to:

if r, ok := src.(io.Reader); {
    return r, nil
}

Testing it locally, this change added a 2x speedup (4.91671ms -> 2.944214ms) for creating a NewMachine. Additionally, this drops the need to include the reflection library.

support or-parallelism

Create a new ChoicePoint implementation which, in a separate goroutine, steps a machine until it fails or finds an answer. It then sends itself down a channel where the original machine can extract its "future self" if it follows that disjunction.

We'll need some timing information to know which predicates are worth spawning. Once we have that, we can choose which choice points want parallel execution and which don't.

During this process, keep an eye open for ways to support and-parallelism too.

separate Compound and Atom types

Atoms are currently implemented as 0-arity compound terms. There are quite a few optimizations that can be made with atoms once their implementation is separated. The first step is just to separate the implementations.

Typing bug: interface{} instead of ps.Any

When trying to build with version go1.5 linux/amd64, I get the following error:

../../mndrix/golog/term/term.go:195: cannot use func literal (type func(string, interface {})) as type func(string, ps.Any) in argument to innerNames.ForEach

make Unify() a method on Term

Each Term implementation can apply substantial unification optimizations because it knows it's own type and implementation details.

profile and improve performance for each benchmark

There are several benchmarks in the repository. Profile each one to see what's slow. Fix the major ones.

create benchmarks for Jekejeke test programs

Jekejeke Prolog has several sample programs which seem to benchmark useful aspects of a Prolog implementation. Create Go Benchmark functions for each one.

implement indexing

Golog has no indexing at the moment. I've sketched one indexing technique that might work. Try implementing it.

Make sure that I can implement different indexing techniques for different predicates. Some predicates may have only a couple, shallow heads. Others may have many heads or very deep heads. I suspect that no single indexing algorithm can perform well on them all.

Can't create an interpreter with pre-bound variables.

Sorry - it might be a rookie error.
I am trying to create an interpreter with some variables bound to values. I want this variables to have a name, for example:

	mId := golog.NewMachine().Consult(`test_unify(X, X).`)
	t, v := term.NewAtom("atom"), term.NewVar("W")
	b, _ := term.NewBindings().WithNames(psm.Set("W", v)).Bind(v, t)
	mId = mId.SetBindings(b)
	solutions := mId.ProveAll(`test_unify(P, W).`)
	for _, solution := range solutions {
		fmt.Printf("pattern: variable is %s\n", solution.ByName_("P"))
	}

I get

panic: Can't set names when names have already been set
goroutine 1 [running]:
github.com/mndrix/golog/term.(*envMap).WithNames(0xc420368560, 0x5ca2e0, 0xc4202a7a40, 0x5ca100, 0xc420368560)
/home/diguser/projects/Watson/Engine/apicache/src/github.com/mndrix/golog/term/bindings.go:135 +0x140
github.com/mndrix/golog.(*machine).ProveAll(0xc4200928c0, 0x506540, 0x54a550, 0x1, 0x1, 0x253)
/home/diguser/projects/Watson/Engine/apicache/src/github.com/mndrix/golog/machine.go:341 +0x218

If I do not use .WithNames(psm.Set("W", v)). then there is no effect of binding variable to value, because it cannot be found by name (ByName_).

I checked the code and understand why it is happening, but how can I get around it other then creating a text representation of my long list of atoms? Is that possible?

remove most Term methods

Term has a bunch of methods which should really be functions. Make it happen.

steal ideas from Krall

"Implementation of a high-speed Prolog interpreter" by Krall. The abstract claims an interpreter that's as fast as compiled code. I haven't read the paper, but there must be some good ideas in there worth implementing.

experiment with other unification algorithms

Try a more efficient unification algorithm such as those described in "An Efficient Unification Algorithm" by Martelli, "A practically efficient and almost linear unification algorithm" by Escalada-Imaz, "A Practically Linear Unification Algorithm" by Baxter.

go get github.com/mndrix/golog/bin fails

Executing go get github.com/mndrix/golog/bin gives: imported and not used: "github.com/mndrix/ps".

Also, it should probably be moved to github.com/mndrix/golog/cmd/golog so that the binary would be called 'golog', not 'bin'.

optimize code representations

Codes and lists of codes are both common Prolog data structures. Create internal representations which optimize for this use case. These representations will occupy less memory (the bottleneck in most benchmarks).

Make a Code type which implements the Number interface. It should just be a rune under the hood. The current implementation for integers requires a pointer to a struct which wraps a bool and a slice. A Code type would also be helpful for representing small integers, which are very common in real world code.

Make a CodeList which implements the Callable interface. It should just be a []rune under the hood. Unification with other list terms returns a slice where possible. The current implementation for code lists requires a linked list of terms which adds substantial memory overhead.

implement more ISO Prolog built in predicates

I've only implemented a handfull. Review the spec and add as many as possible, starting with the most commonly used ones. It should be easy enough to scan some popular Prolog projects to see which predicates are the most common.