golog

package module
Version: v0.0.0-...-a28e2a2 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Mar 30, 2017 License: MIT Imports: 14 Imported by: 5

README

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.

Documentation

Overview

Golog aspires to be an ISO Prolog interpreter. It currently supports a small subset of the standard. Any deviations from the standard are bugs. Typical usage looks something like this:

m := NewMachine().Consult(`
    father(john).
    father(jacob).

    mother(sue).

    parent(X) :-
        father(X).
    parent(X) :-
        mother(X).
`)
if m.CanProve(`father(john).`) {
    fmt.Printf("john is a father\n")
}

solutions := m.ProveAll(`parent(X).`)
for _, solution := range solutions {
    fmt.Printf("%s is a parent\n", solution.ByName_("X"))
}

This sample highlights a few key aspects of using Golog. To start, Golog data structures are immutable. NewMachine() creates an empty Golog machine containing just the standard library. Consult() creates another new machine with some extra code loaded. The original, empty machine is untouched. It's common to build a large Golog machine during init() and then add extra rules to it at runtime. Because Golog machines are immutable, multiple goroutines can access, run and "modify" machines in parallel. This design also opens possibilities for and-parallel and or-parallel execution.

Most methods, like Consult(), can accept Prolog code in several forms. The example above shows Prolog as a string. We could have used any io.Reader instead.

Error handling is one oddity. Golog methods follow Go convention by returning an error value to indicate that something went wrong. However, in many cases the caller knows that an error is highly improbable and doesn't want extra code to deal with the common case. For most methods, Golog offers one with a trailing underscore, like ByName_(), which panics on error instead of returning an error value.

See also:

* Golog's architecture: https://github.com/mndrix/golog/blob/master/doc/architecture.md
* Built in and foreign predicates: See func Builtin...
* Standard library: See golog/prelude package

Index

Constants

This section is empty.

Variables

View Source
var CutBarrierFails error = fmt.Errorf("Cut barriers never succeed")
View Source
var EmptyConjunctions = fmt.Errorf("Conjunctions list is empty")

EmptyConjunctions error is returned when trying to pop a conjunction off an empty conjunction stack. This is mostly useful for those hacking on the interpreter.

View Source
var EmptyDisjunctions = fmt.Errorf("Disjunctions list is empty")

EmptyDisjunctions error is returned when trying to pop a disjunction off an empty disjunction stack. This is mostly useful for those hacking on the interpreter.

View Source
var MachineDone = fmt.Errorf("Machine can't step any further")

MachineDone error is returned when a Golog machine has been stepped as far forward as it can go. It's unusual to need this variable.

View Source
var NoBarriers = fmt.Errorf("There are no cut barriers")

NoBarriers error is returned when trying to access a cut barrier that doesn't exist. See MostRecentCutBarrier

Functions

func BarrierId

func BarrierId(cp ChoicePoint) (int64, bool)

If cp is a cut barrier choice point, BarrierId returns an identifier unique to this cut barrier and true. If cp is not a cut barrier, the second return value is false. BarrierId is mostly useful for those hacking on the interpreter or doing strange control constructs with foreign predicates. You probably don't need this. Incidentally, !/0 is implemented in terms of this.

func RegisterHelp

func RegisterHelp(m Machine, h map[string]string)

Types

type ChoicePoint

type ChoicePoint interface {
	// Follow produces a new machine which sets out to explore a
	// choice point.
	Follow() (Machine, error)
}

ChoicePoint represents a place in the execution where we had a choice between multiple alternatives. Following a choice point is like making one of those choices.

The simplest choice point simply tries to prove some goal; usually the body of a clause. We can imagine more complex choice points. Perhaps when the choice point was created, we spawned a goroutine to investigate that portion of the execution tree. If that "clone" finds something interesting, it can send itself down a channel. In this case, the ChoicePoint's Follow() method would just return that speculative, cloned machine. In effect it's saying, "If you want to pursue this execution path, don't bother with the computation. I've already done it"

One can imagine a ChoicePoint implementation which clones the Golog machine onto a separate server in a cluster. Following that choice point waits for the other server to finish evaluating its execution branch.

func NewCutBarrier

func NewCutBarrier(m Machine) ChoicePoint

NewCutBarrier creates a special choice point which acts as a sentinel value in the Golog machine's disjunction stack. Attempting to follow a cut barrier choice point panics.

func NewHeadBodyChoicePoint

func NewHeadBodyChoicePoint(m Machine, g, t term.Term) ChoicePoint

A head-body choice point is one which, when followed, unifies a goal g with the head of a term t. If unification fails, the choice point fails. If unification succeeds, the machine tries to prove t's body.

func NewSimpleChoicePoint

func NewSimpleChoicePoint(m Machine, g term.Term) ChoicePoint

Following a simple choice point makes the machine start proving goal g. If g is true/0, this choice point can be used to revert back to a previous version of a machine. It can be useful for building certain control constructs.

type Database

type Database interface {
	// Asserta adds a term to the database at the start of any existing
	// terms with the same name and arity.
	Asserta(Term) Database

	// Assertz adds a term to the database at the end of any existing
	// terms with the same name and arity.
	Assertz(Term) Database

	// Candidates() returns a list of clauses that might unify with a term.
	// Returns error if no predicate with appropriate
	// name and arity has been defined.
	Candidates(Term) ([]Term, error)

	// Candidates_() is like Candidates() but panics on error.
	Candidates_(Term) []Term

	// ClauseCount returns the number of clauses in the database
	ClauseCount() int

	// String returns a string representation of the entire database
	String() string
}

Database is an immutable Prolog database. All write operations on the database produce a new database without affecting the previous one. A database is a mapping from predicate indicators (foo/3) to clauses. The database may or may not implement indexing. It's unusual to interact with databases directly. One usually calls methods on Machine instead.

func NewDatabase

func NewDatabase() Database

NewDatabase returns a new, empty database

type ForeignPredicate

type ForeignPredicate func(Machine, []Term) ForeignReturn

Golog allows Prolog predicates to be defined in Go. The foreign predicate mechanism is implemented via functions whose type is ForeignPredicate.

type ForeignReturn

type ForeignReturn interface {
	IsaForeignReturn() // useless method to restrict implementations
}

ForeignReturn represents the return type of ForeignPredicate functions. Values of ForeignReturn indicate certain success or failure conditions to the Golog machine. If you're writing a foreign predicate, see functions named Foreign* for possible return values.

func BuiltinAtomCodes2

func BuiltinAtomCodes2(m Machine, args []term.Term) ForeignReturn

atom_codes/2 see ISO §8.16.5

func BuiltinAtomNumber2

func BuiltinAtomNumber2(m Machine, args []term.Term) (ret ForeignReturn)

atom_number/2 as defined in SWI-Prolog

func BuiltinCall

func BuiltinCall(m Machine, args []term.Term) ForeignReturn

call/*

func BuiltinComma

func BuiltinComma(m Machine, args []term.Term) ForeignReturn

,/2

func BuiltinCut

func BuiltinCut(m Machine, args []term.Term) ForeignReturn

!/0

func BuiltinCutTo

func BuiltinCutTo(m Machine, args []term.Term) ForeignReturn

$cut_to/1

An internal system predicate which might be removed at any time in the future. It cuts all disjunctions on top of a specific cut barrier.

func BuiltinDowncaseAtom2

func BuiltinDowncaseAtom2(m Machine, args []term.Term) ForeignReturn

downcase_atom(+AnyCase, -LowerCase)

Converts the characters of AnyCase into lowercase and unifies the lowercase atom with LowerCase.

func BuiltinFail

func BuiltinFail(m Machine, args []term.Term) ForeignReturn

fail/0

func BuiltinFindall3

func BuiltinFindall3(m Machine, args []term.Term) ForeignReturn

findall/3

func BuiltinGround

func BuiltinGround(m Machine, args []term.Term) ForeignReturn

ground/1

func BuiltinIfThen

func BuiltinIfThen(m Machine, args []term.Term) ForeignReturn

->/2

func BuiltinIs

func BuiltinIs(m Machine, args []term.Term) ForeignReturn

is/2

func BuiltinListing0

func BuiltinListing0(m Machine, args []term.Term) ForeignReturn

listing/0 This should be implemented in pure Prolog, but for debugging purposes, I'm doing it for now as a foreign predicate. This will go away.

func BuiltinMsort2

func BuiltinMsort2(m Machine, args []term.Term) ForeignReturn

msort(+Unsorted:list, -Sorted:list) is det.

True if Sorted is a sorted version of Unsorted. Duplicates are not removed.

This is currently implemented using Go's sort.Sort. The exact implementation is subject to change. I make no guarantees about sort stability.

func BuiltinNot

func BuiltinNot(m Machine, args []term.Term) ForeignReturn

(\+)/1

func BuiltinNumericEquals

func BuiltinNumericEquals(m Machine, args []term.Term) ForeignReturn

=:=/2

func BuiltinPrintf

func BuiltinPrintf(m Machine, args []term.Term) ForeignReturn

A temporary hack for debugging. This will disappear once Golog has proper support for format/2

func BuiltinSemicolon

func BuiltinSemicolon(m Machine, args []term.Term) ForeignReturn

;/2

Implements disjunction and if-then-else.

func BuiltinSucc2

func BuiltinSucc2(m Machine, args []term.Term) ForeignReturn

succ(?A:integer, ?B:integer) is det.

True if B is one greater than A and A >= 0.

func BuiltinTermEquals

func BuiltinTermEquals(m Machine, args []term.Term) ForeignReturn

==/2

func BuiltinTermGreater

func BuiltinTermGreater(m Machine, args []term.Term) ForeignReturn

@>/2

func BuiltinTermGreaterEquals

func BuiltinTermGreaterEquals(m Machine, args []term.Term) ForeignReturn

@>=/2

func BuiltinTermLess

func BuiltinTermLess(m Machine, args []term.Term) ForeignReturn

@</2

func BuiltinTermLessEquals

func BuiltinTermLessEquals(m Machine, args []term.Term) ForeignReturn

@=</2

func BuiltinTermNotEquals

func BuiltinTermNotEquals(m Machine, args []term.Term) ForeignReturn

\==/2

func BuiltinUnify

func BuiltinUnify(m Machine, args []term.Term) ForeignReturn

=/2

func BuiltinVar1

func BuiltinVar1(m Machine, args []term.Term) ForeignReturn

var(?X) is semidet.

True if X is a variable.

func ForeignFail

func ForeignFail() ForeignReturn

ForeignFail indicates a foreign predicate that failed

func ForeignTrue

func ForeignTrue() ForeignReturn

ForeignTrue indicates a foreign predicate that succeeds deterministically

func ForeignUnify

func ForeignUnify(ts ...term.Term) ForeignReturn

ForeignUnify indicates a predicate that succeeds or fails depending on the results of a unification. The list of arguments must have an even number of elements. Each pair is unified in turn. Variables bound during unification become part of the Golog machines's bindings.

func InteractiveApropos1

func InteractiveApropos1(m Machine, args []term.Term) ForeignReturn

func InteractiveHelp0

func InteractiveHelp0(m Machine, args []term.Term) ForeignReturn

func InteractiveHelp1

func InteractiveHelp1(m Machine, args []term.Term) ForeignReturn

type Machine

type Machine interface {
	// A Machine is an acceptable return value from a foreign predicate
	// definition.  In other words, a foreign predicate can perform low-level
	// manipulations on a Golog machine and return the result as the new
	// machine on which future execution occurs.  It's unlikely that you'll
	// need to do this.
	ForeignReturn

	// Temporary.  These will eventually become functions rather than methods.
	// All three accept Prolog terms as strings or as io.Reader objects from
	// which Prolog terms can be read.
	CanProve(interface{}) bool
	Consult(interface{}) Machine
	ProveAll(interface{}) []Bindings

	String() string

	// Bindings returns the machine's most current variable bindings.
	//
	// This method is typically only used by ChoicePoint implementations
	Bindings() Bindings

	// SetBindings returns a new machine like this one but with the given
	// bindings
	SetBindings(Bindings) Machine

	// PushConj returns a machine like this one but with an extra term
	// on front of the conjunction stack
	PushConj(Callable) Machine

	// PopConj returns a machine with one less item on the conjunction stack
	// along with the term removed.  Returns err = EmptyConjunctions if there
	// are no more conjunctions on that stack
	PopConj() (Callable, Machine, error)

	// ClearConjs replaces the conjunction stack with an empty one
	ClearConjs() Machine

	// ClearDisjs replaces the disjunction stack with an empty one
	ClearDisjs() Machine

	// DemandCutBarrier makes sure the disjunction stack has a cut barrier
	// on top.  If not, one is pushed.
	// This marker can be used to locate which disjunctions came immediately
	// before the marker existed.
	DemandCutBarrier() Machine

	// MostRecentCutBarrier returns an opaque value which uniquely
	// identifies the most recent cut barrier on the disjunction stack.
	// Used with CutTo to remove several disjunctions at once.
	// Returns NoBarriers if there are no cut barriers on the disjunctions
	// stack.
	MostRecentCutBarrier() (int64, error)

	// CutTo removes all disjunctions stacked on top of a specific cut barrier.
	// It does not remove the cut barrier itself.
	// A barrier ID is obtained from MostRecentCutBarrier.
	CutTo(int64) Machine

	// PushDisj returns a machine like this one but with an extra ChoicePoint
	// on the disjunctions stack.
	PushDisj(ChoicePoint) Machine

	// PopDisj returns a machine with one fewer choice points on the
	// disjunction stack and the choice point that was removed.  Returns
	// err = EmptyDisjunctions if there are no more disjunctions on
	// that stack
	PopDisj() (ChoicePoint, Machine, error)

	// RegisterForeign registers Go functions to implement Golog predicates.
	// When Golog tries to prove a predicate with one of these predicate
	// indicators, it executes the given function instead.
	// Calling RegisterForeign with a predicate indicator that's already
	// been registered replaces the predicate implementation.
	RegisterForeign(map[string]ForeignPredicate) Machine

	// Step advances the machine one "step" (implementation dependent).
	// It produces a new machine which can take the next step.  It might
	// produce a proof by giving some variable bindings.  When the machine
	// has done as much work as it can do, it returns err=MachineDone
	Step() (Machine, Bindings, error)
}

Golog users interact almost exclusively with a Machine value. Specifically, by calling one of the three methods Consult, CanProve and ProveAll. All others methods are for those hacking on the interpreter or doing low-level operations in foreign predicates.

func NewBlankMachine

func NewBlankMachine() Machine

NewBlankMachine creates a new Golog machine without loading the standard library (prelude)

func NewInteractiveMachine

func NewInteractiveMachine() Machine

func NewMachine

func NewMachine() Machine

NewMachine creates a new Golog machine. This machine has the standard library already loaded and is typically the way one obtains a machine.

Directories

Path Synopsis
cmd
golog
A primitive Prolog top level for Golog.
A primitive Prolog top level for Golog.
Tokenize UTF-8-encoded Prolog text.
Tokenize UTF-8-encoded Prolog text.
Defines the Prolog standard library.
Defines the Prolog standard library.
Read Prolog terms.
Read Prolog terms.
Represent and unify Prolog terms.
Represent and unify Prolog terms.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL