length/2 loops for cases of finite failure

[UWN]

#3:

?-  length([_|L],0). 
   loops. % unexpected

It may be helpful to go through all cases.

[UWN]

Consider to use an implementation similar to Scryer which is based on an internal built-in '$skip_max_list'/4 using Brent's cycle detection algorithm which is perfect for term representations based on a directed graph. Many systems use this approach. SICStus, YAP, SWI, Scryer, Trealla.

Test cases.

[UWN]

Going through the test cases:

#19 that's syntax,
#21 could be a resource error - with Brent it's trivial,
#22,
#26 unexpected failure. Produce rather a resource error (since you have Brent).

It seems you have implemented everything in Go. Instead, consider to implement '$skip_max_list'/4 and the implementation in Scryer which has its actual logic in Prolog. Without constraints, it is even a bit simpler.

[ichiban]

I've been thinking this over. Most of my questions are already answered in mthom/scryer-prolog#1023.

21 and 22 should be resource_error(Resource)- what will be the Resource in this library? It's not resource_error(finite_memory) since Go has a GC.

Still having trouble at 26. The list is not finite. p.p.3.1.a says "If List is neither a partial list nor a list, then the goal fails."
Maybe this is the case only if the length of the cycle exceeded Max? In that case, we can't tell if the list is finite or not.

To understand more about 26, I'll implement $skip_max_list/4.

I'm writing most of the predicates in Go because I want to make this library easy to sandbox. If I write length/2 in Prolog, it'll be hard to cherry-pick length/2 for a sandboxed interpreter:

// Good
p := new(prolog.Interpreter)         // An interpreter without any predicates
p.Register2(`length`, prolog.Length) // An interpreter with `length/2`

// Bad
p := new(prolog.Interpreter)                              // An interpreter without any predicates
p.Register4(`$skip_max_list`, prolog.SkipMaxList)         // An interpreter with `$skip_max_list/4`
p.Exec(`length(L, N) :- ..., $skip_max_list(...), ... .`) // An interpreter with `$skip_max_list/4` and `length/2`

[UWN]

21 and 22 should be resource_error(Resource)- what will be the Resource in this library? It's not resource_error(finite_memory) since Go has a GC.

From the standards viewpoint the name of a resource is just an implementation dependent atom. But it makes sense to somewhat indicate what this resource is about. Regardless of the presence of GC, Go's memory will be finite for the general case, like representing a list of arbitrary length. Therefore, it is helpful and resource-saving in 21 and 22 to produce the resource error immediately (strictly speaking, provided there is no constraint on the list), see Scryer for details.

By stating that the resource is finite_memory we say: no matter what size your memory is, it will be always insufficient to represent the list.

Still having trouble at 26. The list is not finite. p.p.3.1.a says "If List is neither a partial list nor a list, then the goal fails."

The prologue as much as the entire standard always talks about finite terms. A unification like the one in #26 is STO (subject to occurs check , 7.3.3) and thus undefined. So any conclusion from something normative (which always assumes NSTO unification) to this undefined part does not hold. This includes your conclusion.

So for you, as you have rational trees, the question is: what would happen if you let this goal just run. Assuming your implementation with bounded integers, you would run into an evaluation_error(int_overflow) (after some time). But Brent could detect this immediately without wasting so much resources. So producing this error just after detection of the cyclic list might be the best for you. (Or, rather consider to use unbounded integers).

[UWN]

As for implementing things in Go vs Prolog. You might certainly also use the functionality of '$skip_max_list/4` in Go. Alternatively, you could either use a real module system, or at least implement system code in Prolog but inaccessibly to the the remaining code.

The Edinburgh Prologs do this (to varying degree): System code in those Prologs starts with a $, and after the system has loaded all those predicates (and established their relation between each other), these names are removed (interned).

[UWN]

A helpful perspective is the one from the actual user: The more complex the errors generated, the more burden to the user. With unbounded integers there is one error case less.

[ichiban]

@UWN, thank you for elaboration!

I wasn't able to allocate enough time to work on this project since I was busy on my day job, but I managed to re-implemented length/2 .
The underlying engine.SkipMaxList() is exposed as skip_max_list/4 in 1pl as well:

Top level for ichiban/prolog (devel)
This is for testing purposes only!
See https://github.com/ichiban/prolog for more details.
Type Ctrl-C or 'halt.' to exit.
?- skip_max_list(N, 2, [a, b, c, d], S).
N = 2,
S = [c, d];
?- skip_max_list(N, _, [a, b, c, d], S). 
N = 4,
S = [];

[ichiban]

I've been thinking how I can make it support unbounded integers. The current implementation of terms are simple and easy to work with because most of them are backed by Go's primitive types:

• engine.Term
  • engine.Variable -- backed by string (may change to support attributes)
  • engine.Atom -- backed by string
  • engine.Integer -- backed by int64
  • engine.Float -- backed by float64
  • *engine.Compound -- backed by struct

One thing we can do is to change the underlying type of engine.Integer from int64 to *big.Int. It won't affect the complexity of the code so much but it'll make it harder to work with.

Another option is to add engine.BigInteger backed by *big.Int. That way, we can keep engine.Integer easy to work with but it'll be complex to type check.

[UWN]

For you it seems the objective is to get the system working with as few irregularities as possible. Offering two internal types is something many high performance systems do, but it seems your objective is less to squeeze out the very tiny last bits of performance.

[UWN]

BTW, is the new length/2 part of main?

[ichiban]

Not yet. It's still in fix-length:

$ git checkout fix-length
Switched to branch 'fix-length'
Your branch is up to date with 'origin/fix-length'.
$ git pull
Already up to date.
$ go install github.com/ichiban/prolog/cmd/1pl
$ $(go env GOPATH)/bin/1pl
Top level for ichiban/prolog (devel)
This is for testing purposes only!
See https://github.com/ichiban/prolog for more details.
Type Ctrl-C or 'halt.' to exit.
?- skip_max_list(N, 2, [a, b, c, d], S).
N = 2,
S = [c, d].
?- L = [a|L], length(L,N).
2022/05/23 21:08:32 error(resource_error(finite_memory), length/2)

[ichiban]

@UWN I fixed conflicts and now length/2 is in the main branch! It passes the test cases 1~28 from http://www.complang.tuwien.ac.at/ulrich/iso-prolog/length on my end.

$ git checkout main
Already on 'main'
Your branch is up to date with 'origin/main'.
$ go install github.com/ichiban/prolog/cmd/1pl
$ $(go env GOPATH)/bin/1pl
Top level for ichiban/prolog (devel)
This is for testing purposes only!
See https://github.com/ichiban/prolog for more details.
Type Ctrl-C or 'halt.' to exit.
?- length([_|L],0). 
false.

[UWN]

When I say go install github.com/ichiban/prolog/cmd/1pl@latest I get v0.9.1 without the improvements. Only when I say go install github.com/ichiban/prolog/cmd/1pl I get devel with the improvements.

[ichiban]

@UWN I finally released v0.10.0 with all the recent improvements.

$ go install github.com/ichiban/prolog/cmd/1pl@latest
$ $(go env GOPATH)/bin/1pl
Top level for ichiban/prolog v0.10.0
This is for testing purposes only!
See https://github.com/ichiban/prolog for more details.
Type Ctrl-C or 'halt.' to exit.
?- length([_|L],0). 
false.

[UWN]

Added. Please check the table.