Prolog interpreter in Go

Overview

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.

Issues
  • Olegs/expose native objects

    Olegs/expose native objects

    The changes roughly fall into these categories:

    • New Prolog type term.Native This required some (very few) modifications in term package to deal with caching of terms (perhaps it would be better to let each kind of term to implement a method which returns something that may be cached?) Another question here: I treated native nil as if it was a non-instantiated Prolog variable. It was useful in some of my code, but I'm not sure it's the correct way to go about it.

    • Serialization and deserialization of Go objects into Prolog objects I'm not entirely confident about correctness of all of my code. (Go reflection is a huge mess...) But for the instances I tried, it seems to work. There are some tests for decoding and encoding, but they don't cover 100% of possible cases. There are also some todos in that general area related to integer overflow that may happen when converting between these types. It wasn't a high priority problem for me, but if need be, I can fix that.

    • help and apropos predicates I found that for interactive use with a large database these are invaluable (I used them with my own code because I couldn't remember the exact names or the number / order of arguments). But, really this is optional feature, however it required one small change in machine struct. I also used a regular hash-table rather than persistent one because these are intended for interactive use, where concurrency isn't an issue. Again, I can redo it using the persistent hash-table to be consistent with the rest of the code.

    • Pretty printing of strings and lists Instead of printing strings like this '.'(23, '.'(24, ...) now it prints it "ab...". This makes the printing a little slower, but I think it's worth the effort. Especially since most printing happens interactively anyways. The printing code doesn't handle recursive terms (I'm not really sure if this is something that's even supported in Golog in general). Anyways, if need be, I can fix it to also avoid looping indefinitely over recursive structures.

    opened by wvxvw 4
  • Use type assertions instead of reflect.

    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.

    opened by ericlagergren 2
  • Typing bug: interface{} instead of ps.Any

    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

    opened by tfgordon 2
  • Tighter code intergration with golang

    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.

    opened by lingnand 2
  • Fix printing list of ints

    Fix printing list of ints

    There is an issue in printing list of ints, because Compound's String method first checks if term is a String and later if it's a List. Unfortunately for list of ints, e.g. [1, 2, 3] the function func IsString(t Term) bool returns true, because it loops over ints unless we get an empty list:

    //...
    		args := c.Arguments()
    		if !IsInteger(args[0]) {
    			return false
    		}
    		if IsCompound(args[1]) {
    			c = args[1].(*Compound)
    		} else if IsEmptyList(args[1]) {
    			break
    		} 
    

    And of course printing the Compound [1,2,3] as a String gives us wrong result. For instance:

    append([65], [66,67], List).
    

    gives [ABC], instead of [65,66,67].

    Anyway, I'm not sure if this is 100% correct fix (maybe there is a more elegant way to do it), but so far it works fine if I replace in func (self *Compound) String() string an order of if-checks. First check if the term is a List and later if it's a String.

    opened by kuba-- 1
  • go get github.com/mndrix/golog/bin fails

    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'.

    opened by mehlon 1
  • implement more ISO Prolog built in predicates

    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.

    opened by mndrix 1
  • implement indexing

    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.

    opened by mndrix 0
  • separate Compound and Atom types

    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.

    opened by mndrix 0
  • Can't create an interpreter with pre-bound variables.

    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?

    opened by tbolsh 1
  • optimize atom representation

    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.

    opened by mndrix 0
  • optimize code representations

    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.

    opened by mndrix 3
  • create benchmarks for Jekejeke test programs

    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.

    opened by mndrix 1
  • support attributed variables

    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.

    opened by mndrix 0
Owner
Michael Hendricks
Michael Hendricks
Scriptable interpreter written in golang

Anko Anko is a scriptable interpreter written in Go. (Picture licensed under CC BY-SA 3.0, photo by Ocdp) Usage Example - Embedded package main impor

mattn 1.2k Jun 20, 2022
A POSIX-compliant AWK interpreter written in Go

GoAWK: an AWK interpreter written in Go AWK is a fascinating text-processing language, and somehow after reading the delightfully-terse The AWK Progra

Ben Hoyt 1.5k Jun 28, 2022
A BASIC interpreter written in golang.

05 PRINT "Index" 10 PRINT "GOBASIC!" 20 PRINT "Limitations" Arrays Line Numbers IF Statement DATA / READ Statements Builtin Functions Types 30 PRINT "

Steve Kemp 277 Jun 24, 2022
A simple virtual machine - compiler & interpreter - written in golang

go.vm Installation Build without Go Modules (Go before 1.11) Build with Go Modules (Go 1.11 or higher) Usage Opcodes Notes The compiler The interprete

Steve Kemp 227 Jun 28, 2022
A JavaScript interpreter in Go (golang)

otto -- import "github.com/robertkrimen/otto" Package otto is a JavaScript parser and interpreter written natively in Go. http://godoc.org/github.com/

Robert Krimen 6.7k Jul 1, 2022
Yaegi is Another Elegant Go Interpreter

Yaegi is Another Elegant Go Interpreter. It powers executable Go scripts and plugins, in embedded interpreters or interactive shells, on top of the Go

Traefik Labs 4.5k Jun 26, 2022
A shell parser, formatter, and interpreter with bash support; includes shfmt

sh A shell parser, formatter, and interpreter. Supports POSIX Shell, Bash, and mksh. Requires Go 1.14 or later. Quick start To parse shell scripts, in

Daniel Martí 4.9k Jun 26, 2022
Lisp Interpreter

golisp Lisp Interpreter Usage $ golisp < foo.lisp Installation $ go get github.com/mattn/golisp/cmd/golisp Features Call Go functions. Print random in

mattn 117 Apr 29, 2022
Mini lisp interpreter written in Go.

Mini Go Lisp Mini lisp interpreter written in Go. It is implemented with reference to the d-tsuji/SDLisp repository written in Java. Support System Fu

Tsuji Daishiro 16 Nov 25, 2020
Toy Lisp 1.5 interpreter

Lisp 1.5 To install: go get robpike.io/lisp. This is an implementation of the language defined, with sublime concision, in the first few pages of the

Rob Pike 863 Jun 24, 2022
Small Clojure interpreter, linter and formatter.

Joker is a small Clojure interpreter, linter and formatter written in Go. Installation On macOS, the easiest way to install Joker is via Homebrew: bre

Roman Bataev 1.4k Jun 22, 2022
Go bindings to QuickJS: a fast, small, and embeddable ES2020 JavaScript interpreter.

quickjs Go bindings to QuickJS: a fast, small, and embeddable ES2020 JavaScript interpreter. These bindings are a WIP and do not match full parity wit

Kenta Iwasaki 125 May 28, 2022
Interactive Go interpreter and debugger with REPL, Eval, generics and Lisp-like macros

gomacro - interactive Go interpreter and debugger with generics and macros gomacro is an almost complete Go interpreter, implemented in pure Go. It of

Massimiliano Ghilardi 1.9k Jun 25, 2022
A interpreter of SweetLang, is writed in Go Programming language.

SweetLang ( Soon ) A interpreter of SweetLang, is writed in Go Programming language. SweetLang is made with clarity and simplicity we try to make its

SweetLang 2 Oct 31, 2021
interpreter for the basic language written in golang

jirachi interpreter for the basic language written in golang The plan supports the following functions: Arithmetic Operations (+, -, *, /, ^) Comparis

菜菜 4 Jun 10, 2022
◻️ A Whitespace interpreter written in Go.

whitespace-go A Whitespace interpreter written in Go. Whitespace is a esoteric programming language made up entirely of spaces, tabs, and newlines. Th

Sam Pratt 4 May 18, 2022
🧠 A Brainfuck interpreter written in Go

brainfuck-go A Brainfuck interpreter written in Go. How Brainfuck works Brainfuck is an esoteric programming language designed to have the simplest co

Sam Pratt 7 May 18, 2022
A little brainfuck interpreter written in Go

Brainfuck_go_interpreter A little brainfuck interpreter written in Go from what I've done in coding game Usage $ go build brainfuck.go $ ./brainfuck P

Axel Vanzaghi 0 Dec 13, 2021
Monkey programming language project from 'Writing An Interpreter In Go'and 'Writing A Compiler In Go' Books

Monkey Monkey programming language ?? project from "Writing An Interpreter In Go

Amr Hesham 1 Dec 16, 2021