Compiling Prolog to Go

append.go

package prolog

/*
%% append(list,list,list)
%% append(+,+,+) is semidet.
%% append(+,+,-) is det.
%% append(+,-,+) is semidet.
%% append(+,-,-) is det.
%% append(-,+,+) is multi.
%% append(-,+,-) is multi.
%% append(-,-,+) is multi.
%% append(-,-,-) is multi.
append(Front,Back,Whole) :- % simplified Prolog only allows variables in clause heads
	unify(Front,[]),  % simplified Prolog does unification with unify/2
	unify(Back,Whole).
append(Front,Back,Whole) :-
	cons(X,RestFront,A),  % simplified Prolog does lists with cons/3
	unify(Front,A),
	cons(X,RestWhole,B),
	unify(Whole,B),
	append(RestFront,Back,RestWhole).
*/

var empty = NewAtom("[]")

type PredicateId int

// a constant for each known predicate
const (
	predAppend3 PredicateId = iota
)

func append3_a(Front, Back, Whole Term) Goal {
	return conjunction(
		unify(Front, empty),
		unify(Back, Whole),
	)
}

func append3_b(Front, Back, Whole Term) Goal {
	var A, B, RestFront, RestWhole, X Variable
	return conjunction(
		cons3(X, RestFront, A),
		unify(Front, A),
		cons3(X, RestWhole, B),
		unify(Whole, B),
		append3(RestFront, Back, RestWhole),
	)
}

func append3(Front, Back, Whole Term) Goal {
	return &PredicateGoal{
		Predicate: predAppend3,
		Args:      []Term{Front, Back, Whole},
	}
}

builtin.go

package prolog

func cons3(X, Y, Z Term) Goal {
	return nil
}

context.go

package prolog

type Context interface {
	Trail() Trail
}

goal.go

package prolog

// Goal describes any computation which produces solutions.
type Goal interface {
	// Next returns true for the first value if it succeeds in producing a solution.
	// On success, returns true for the second value if this goal can produce more
	// solutions.
	Next(Context) (bool, bool)
}

type NeedsCleanup interface {
	// Cleanup instructs this goal to discard any resources it allocated (such as
	// goroutines) because the goal won't be called again.
	Cleanup()
}

goal_conjunction.go

package prolog

type GoalConjunction struct {
	Goals []Goal

	choicepoints []choicepoint
}

type choicepoint struct {
	index   int
	barrier Barrier
}

func conjunction(goals ...Goal) Goal {
	return &GoalConjunction{Goals: goals}
}

func (self *GoalConjunction) Next(c Context) (bool, bool) {
	goalIndex := 0
	if len(self.choicepoints) > 0 {
		p := self.choicepoints[len(self.choicepoints)-1]
		self.choicepoints = self.choicepoints[0 : len(self.choicepoints)-1]
		goalIndex = p.index
		c.Trail().BacktrackTo(p.barrier)
		c.Trail().DropBarrier(p.barrier)
	}

	for goalIndex < len(self.Goals) {
		goal := self.Goals[goalIndex]
		barrier := c.Trail().PushBarrier()
		ok, more := goal.Next(c)
		if ok {
			if more {
				// record a choicepoint
				p := choicepoint{goalIndex, barrier}
				self.choicepoints = append(self.choicepoints, p)
			}
			goalIndex++
			continue
		} else {
			// TODO backtrack to previous choicepoint
		}
	}

	more := len(self.choicepoints) > 0
	if !more {
		for _, goal := range self.Goals {
			if x, ok := goal.(NeedsCleanup); ok {
				x.Cleanup()
			}
		}
	}
	return true, more
}

goal_predicate.go

package prolog

type PredicateGoal struct {
	Predicate PredicateId
	Args      []Term

	clauseIndex int
	clauses     []Goal
}

func (self *PredicateGoal) Next(c Context) (bool, bool) {
	if self.clauses == nil {
		self.clauses = lookupClauses(self.Predicate, self.Args)
	}

	// look for solutions from each clause in turn
	for {
		if self.clauseIndex >= len(self.clauses) {
			// already investigated all clauses
			return false, false
		}

		clause := self.clauses[self.clauseIndex]
		ok, more := clause.Next(c)
		if ok {
			if more {
				return true, true
			}

			if x, ok := clause.(NeedsCleanup); ok {
				x.Cleanup()
			}
			self.clauseIndex++
			return true, self.clauseIndex < len(self.clauses)
		} else {
			if x, ok := clause.(NeedsCleanup); ok {
				x.Cleanup()
			}

			// look for solutions in the next clause
			self.clauseIndex++
		}
	}
}

func lookupClauses(id PredicateId, args []Term) []Goal {
	return nil
}

hello.pl

main :-
    format("Hello, world!~n").

/*
use("amalog.org/std/io", Io);

main(W) {
    Io.printf(W, "Hello, world!\n");
}
*/

scanner.go

package prolog

import (
	"fmt"
	"io"
)

type Class int

const (
	Atom  Class = iota
	Neck  Class = iota
	Num   Class = iota
	Punct Class = iota
	Var   Class = iota
)

const EOF rune = -1

type Position struct {
	Filename string
	Line     int
	Column   int
}

func (pos Position) String() string {
	f := pos.Filename
	if f == "" {
		f = "<input>"
	}
	return fmt.Sprintf("%s:%d:%d", f, pos.Line, pos.Column)
}

type SyntaxError struct {
	Position Position
	Message  string
}

func (err *SyntaxError) Error() string {
	return fmt.Sprintf("%s: %s", err.Position, err.Message)
}

type Token struct {
	Class    Class
	Position Position
	Text     string
}

func (t *Token) String() string {
	switch t.Class {
	case Atom:
		return fmt.Sprintf("atom(%s)", t.Text)
	case Neck:
		return "neck"
	case Num:
		return fmt.Sprintf("num(%s)", t.Text)
	case Punct:
		return fmt.Sprintf("punct(%s)", t.Text)
	case Var:
		return fmt.Sprintf("var(%s)", t.Text)
	default:
		return "<unknown token class>"
	}
}

type Scanner struct {
	r io.RuneScanner

	filename string
	err      *SyntaxError

	line       int
	column     int
	prevLine   int // before calling next()
	prevColumn int // before calling next()
}

func NewScanner(r io.RuneScanner) *Scanner {
	s := &Scanner{
		r:      r,
		line:   1,
		column: 0,
	}
	return s
}

func (s *Scanner) Scan() (*Token, error) {
	var ch rune
	for {
		ch = s.peek()
		if ch == EOF {
			if s.err == nil {
				return nil, io.EOF
			}
			return nil, s.err
		}

		if ch >= 'a' && ch <= 'z' { // atom
			return s.scanAtom()
		} else if ch >= 'A' && ch <= 'Z' { // variable
			return s.scanVariable()
		} else if ch >= '0' && ch <= '9' { // number
			return s.scanNumber()
		} else if ch == ':' { // neck
			return s.scanNeck()
		} else if ch == ' ' || ch == '\n' { // white space
			s.skipSpace()
			continue
		} else {
			break
		}
	}

	_ = s.next() // consume punctuation character
	t := &Token{
		Class:    Punct,
		Position: s.pos(),
		Text:     string([]rune{ch}),
	}
	return t, nil
}

func (s *Scanner) peek() rune {
	ch := s.next()
	if ch == EOF {
		return ch
	}
	s.back()
	return ch
}

func (s *Scanner) back() {
	err := s.r.UnreadRune()
	if err != nil {
		panic(err)
	}

	s.line = s.prevLine
	s.column = s.prevColumn
}

// consumes the next character in the stream. stores errors in s.err
func (s *Scanner) next() rune {
	s.prevLine = s.line
	s.prevColumn = s.column

	ch, _, err := s.r.ReadRune()
	if err == io.EOF {
		return EOF
	}
	if err != nil {
		panic(err)
	}

	// handle prohibited characters
	if ch == '\t' || ch == '\r' {
		s.err = s.prohibitedCharacter(ch)
		return EOF
	}

	// update position information
	if ch == '\n' {
		s.line++
		s.column = 0
	} else {
		s.column++
	}

	return ch
}

func (s *Scanner) prohibitedCharacter(ch rune) *SyntaxError {
	var name string
	switch ch {
	case '\t':
		name = "tab"
	case '\r':
		name = "carriage return"
	}
	return &SyntaxError{
		Position: s.pos(),
		Message:  fmt.Sprintf("The %s character is prohibited", name),
	}
}

func (s *Scanner) pos() Position {
	return Position{
		Filename: s.filename,
		Line:     s.line,
		Column:   s.column,
	}
}

func (s *Scanner) skipSpace() {
	for {
		ch := s.next()
		if ch == ' ' || ch == '\n' {
			continue
		}
		s.back()
		break
	}
}

func (s *Scanner) scanAtom() (*Token, error) {
	chars := make([]rune, 0)

	ch := s.next()
	pos := s.pos()
CH:
	for {
		switch {
		case ch >= 'a' && ch <= 'z', ch == '_':
			chars = append(chars, ch)
		case ch == '(', ch == ')', ch == ',', ch == '.', ch == ' ':
			s.back()
			break CH
		case ch == EOF:
			break CH
		default:
			err := &SyntaxError{
				Position: s.pos(),
				Message:  fmt.Sprintf("Unexpected atom character: %c", ch),
			}
			return nil, err
		}

		ch = s.next()
	}

	t := &Token{
		Class:    Atom,
		Position: pos,
		Text:     string(chars),
	}
	return t, nil
}

func (s *Scanner) scanNeck() (*Token, error) {
	pos := s.pos()
	ch := s.next()
	if ch == ':' {
		ch = s.next()
		if ch == '-' {
			t := &Token{
				Class:    Neck,
				Position: pos,
				Text:     ":-",
			}
			return t, nil
		}
	}

	err := &SyntaxError{
		Position: pos,
		Message:  "Expected neck (:-)",
	}
	return nil, err
}

func (s *Scanner) scanVariable() (*Token, error) {
	chars := make([]rune, 0)

	ch := s.next()
	pos := s.pos()
CH:
	for {
		switch {
		case ch >= 'A' && ch <= 'Z':
			if len(chars) > 0 {
				prev := chars[len(chars)-1]
				if prev < 'a' || prev > 'z' {
					err := &SyntaxError{
						Position: s.pos(),
						Message:  fmt.Sprintf("variable names may not have consecutive uppercase letters, got %c", ch),
					}
					return nil, err
				}
			}
			chars = append(chars, ch)
		case ch >= 'a' && ch <= 'z':
			if len(chars) == 0 {
				panic("called scanVariable without upper case letter next in stream")
			}
			chars = append(chars, ch)
		case ch == '(', ch == ')', ch == ',', ch == '.':
			s.back()
			break CH
		case ch == EOF:
			break CH
		default:
			err := &SyntaxError{
				Position: s.pos(),
				Message:  fmt.Sprintf("Unexpected variable character: %c", ch),
			}
			return nil, err
		}

		ch = s.next()
	}

	t := &Token{
		Class:    Var,
		Position: pos,
		Text:     string(chars),
	}
	return t, nil
}

func (s *Scanner) scanNumber() (*Token, error) {
	x, err := s.scanInteger()
	if err != nil {
		return nil, err
	}

	switch ch := s.next(); ch {
	case '.':
		y, err := s.scanInteger()
		if err != nil {
			return nil, err
		}
		t := &Token{
			Class:    Num,
			Position: x.Position,
			Text:     x.Text + "." + y.Text,
		}
		return t, nil
	default:
		t := &Token{
			Class:    Num,
			Position: x.Position,
			Text:     x.Text,
		}
		return t, nil
	}
}

func (s *Scanner) scanInteger() (*Token, error) {
	chars := make([]rune, 0)

	ch := s.next()
	pos := s.pos()
CH:
	for {
		switch {
		case ch >= '0' && ch <= '9', ch == '_':
			chars = append(chars, ch)
		case ch == '(', ch == ')', ch == ',', ch == '.', ch == ' ':
			s.back()
			break CH
		case ch == EOF:
			break CH
		default:
			err := &SyntaxError{
				Position: s.pos(),
				Message:  fmt.Sprintf("Unexpected number character: '%c'", ch),
			}
			return nil, err
		}

		ch = s.next()
	}

	t := &Token{
		Class:    Num, // not really
		Position: pos,
		Text:     string(chars),
	}
	return t, nil
}

scanner_test.go

package prolog

import (
	"fmt"
	"io"
	"strings"
	"testing"
)

func TestScanner(t *testing.T) {
	tests := map[string]string{
		`hello.`: `[atom(hello) punct(.)]`,
		`3.141.`: `[num(3.141) punct(.)]`,
		`X`:      `[var(X)]`,
		`FooBar`: `[var(FooBar)]`,

		"main :-\n    hello.": `[atom(main) neck atom(hello) punct(.)]`,
		"123 hi":              `[num(123) atom(hi)]`,
		"123.4 bye":           `[num(123.4) atom(bye)]`,
		"9_876":               `[num(9_876)]`,
	}
	for prolog, expected := range tests {
		ts, err := tokens(prolog)
		if err != nil {
			t.Errorf("oops: %s", err)
			return
		}
		got := fmt.Sprintf("%s", ts)
		if got != expected {
			t.Errorf("got : %s\nwant: %s\n", got, expected)
		}
	}
}

func tokens(text string) ([]*Token, error) {
	ts := make([]*Token, 0)

	s := NewScanner(strings.NewReader(text))
	for {
		t, err := s.Scan()
		if err == io.EOF {
			return ts, nil
		}
		if err != nil {
			return nil, err
		}
		ts = append(ts, t)
	}

	return nil, nil
}

succ.go

package prolog

/*
%% succ(num,num).
%% succ(+,+) is semidet.
%% succ(+,-) is det.
%% succ(-,+) is det.
succ(X,Y) :-
	Y #= X + 1.
*/

import (
	"math/big"
)

var one = big.NewRat(1, 1)

// succ/2 is a built-in predicate
type Succ2 struct {
	X, Y Term
}

func succ2(X, Y Term) Goal {
	return &Succ2{X, Y}
}

func (self *Succ2) Next(c Context) (bool, bool) {
	if IsGround(self.X) {
		if x, ok := self.X.(Number); ok {
			y := new(big.Rat).Add(x.AsBigRat(), one)
			return Unify(c, self.Y, TermFromBigRat(y))
		} else {
			panic("type error: X is not a number")
		}
	} else if IsGround(self.Y) {
		if y, ok := self.Y.(Number); ok {
			x := new(big.Rat).Sub(y.AsBigRat(), one)
			return Unify(c, self.X, TermFromBigRat(x))
		} else {
			panic("type error: Y is not a number")
		}
	} else {
		panic("mode error: X or Y should have been ground")
	}
}

term.go

package prolog

import "math/big"

type Term interface {
}

type Variable interface {
}

type Number interface {
	AsBigRat() *big.Rat
}

func NewAtom(s string) Term {
	return nil
}

func IsGround(t Term) bool {
	return false
}

func TermFromBigRat(x *big.Rat) Term {
	return nil
}

trail.go

package prolog

type Barrier int

type Trail interface {
	BacktrackTo(Barrier)
	DropBarrier(Barrier)
	PushBarrier() Barrier
}

func unify(X, Y Term) Goal {
	return nil
}

func Unify(c Context, x, y Term) (bool, bool) {
	return false, false
}