I just finished coding a between/3 with steps: between/4

General
1

One really rapidly hits an enormous amount of questions just by doing such exercises, which somehow always take about 20h more than expected. I will have to ask later.

Definitely seems to work, all units tests passed (UPDATED after bug fix)

Interesting things:

  • Getting it to be semi-deterministic.
  • The advantage of tagged integers (i.e. use pos(X) instead of X if X is a positive integer to take advantage of pattern matching) becomes evident.
    • Then rearranging arguments to get the most out of matching.
    • The compiler should help in flagging unnecessary cuts (I just left them in, deal with it Mr Compiler).
    • …and that would actually help in deciding whether clause indexing is at it should be (maybe?)
  • Some unit testing features could be added (testing semi/determinism & a size-limited “all”)
  • Standard exception terms as defined by ISO are sadly inflexible and non-regular (varying between compound terms of arity 3,2,1 and an atom?). What happened here?
  • must_be/2 needs a third arg to indicate which variable actually failed. But there is nowhere in the ISO exception term where you can actually put that third arg. Suboptimal.
  • Passing an options list to a predicate to cover a few cases that might be of interest to the programmer (e.g. throw vs. fail on empty sequence) feels like an excellent and simple idea.
  • Binding arguments that no caller needs just for documentation/debugging purposes doesn’t seem like a bad idea either as long as one does not need to change the program structure just for those (they can “tag along”).
  • I haven’t done this in this code, but sometimes one wants to add an argument just to take up the information destroyed by the predicate (e.g. list items removed by the predicate) instead of throwing the information into the heat sink. Then the predicate can run properly backwards too (“reversible computing” in Prolog, right?)
2 Likes
2

Hi, this is very interesting. I understand that the questions you raise are far beyond the problem at hand (how to do a between with a step) but I hope you find my comments at least partly relevant.

If we leave out the “checking” part only for a moment and only think about the sequence, how does this compare to the command-line tool seq? With it you can do:

$ seq 3
1
2
3
$ seq 2 4
2
3
4
$ seq 1 0.3 2
1.0
1.3
1.6
1.9
$ seq 1 -1 -3
1
0
-1
-2
-3

So obviously this only generates sequences but at least it gives us a good starting point for an interface to a between/4 that extends the classical between/3.

I once had other more important things to do, so instead I tried to reproduce the behavior of seq in Prolog. The conclusion I got to was that it was easiest to take the following approach:

Calculate (using arithmetic) the total number of elements n in your sequence; then use between/3 to generate 1, 2, ..., n and use arithmetic to get the corresponding element in your own sequence.

This approach gives you both argument checking and backtracking for free (the arithmetic and between/3 will do the error throwing and backtracking, you can maybe catch and rethrow if you want to add info to the exception).

At some point of time I purposefully deleted a lot of code that didn’t serve any particular purpose and my seq/2, seq/3, seq/4 must have gotten lost. From memory, it went something like this:

seq(Upper, X) :-
    seq(1, Upper, X).

seq(Lower, Upper, X) :-
    seq(Lower, 1, Upper, X).

seq(Lower, Step, Upper, X) :-
    N is floor((Upper - Lower) / Step),
    between(0, N, Y),
    X is Lower + Y * Step.

This code already works pretty well for most modes that I tested now in a hurry. For example:

?- seq(1, -0.3, -0.2, X).
X = 1.0 ;
X = 0.7 ;
X = 0.4 ;
X = 0.10000000000000009 ;
X = -0.19999999999999996.

?- seq(1, 10).
false.

?- seq(10, 1).
true ;
false.

?- seq(1, 10, 1).
true ;
false.

?- seq(3, 10, 1).
false.

?- seq(3, -1, 1).
false.

?- seq(3, -1, 1, 1).
true.

?- seq(3, -1, 0, 1).
true ;
false.

?- seq(3, -1, 0, -1).
false.

?- seq(3, -1, -2, -1).
true ;
false.

There are some dangling choice points obviously, but they seem easy to handle.

I don’t want to show all errors, but all errors I could come up with were caught by either is/2 or between/3.

2 Likes
3

Btw, if you are using #= instead of is then you get relational behavior for integers as well, overcoming the limitation of the is predicate.

4

The biggest problem with integers is that you sometimes want floats or rationals. BTW, can you demonstrate the problems with non-relational behavior due to is/2 in the code above? I am sure there are problems but I am too lazy to think about it carefully right now.

Here the code above with a rational:

?- seq(1, -2r3, -1, X).
X = 1 ;
X = 1r3 ;
X = -1r3 ;
X = -1.
5

Yes, linear transforms came to mind too, although a bit late. I was already “nearly done”

It turns out that a lot of work has to go into what could be called paintjob & metalwork of the predicate (in this case, handling the infinities and doing various checks, throwing exceptions etc.). The engine is then just a few lines that could be subject to changes of approach.

N is floor((Upper - Lower) / Step),

Here lies a question I am always struggling with. If the division yield 1.99999999 steps … what to do? Should one “correct upwards to within some small error”?

6

In the case of floats, it is what it is. You either forbid them explicitly or handle the representation somehow.

I suspect that my floor(...) can also lead to errors but I know that my understanding of floats is rudimentary at best.

7

I actually had two errors in the code:

  • One due to not checking bounds in “verify” mode. A Value could be “on-sequence” but still be “out-of-bounds”. The second condition was not check, and too many Value were accepted. My bad for not writing the test code. Thanks to jburse for spotting that.
  • One due to the fact that I hadn’t put parenthesis around (if -> then ; else). As ; is highest priority in a clause body, this leads to unexpected logic. Not spotted in the unit tests (I think because a cut of no necessity precluded generation of wrong results). But fixed with the help of the existing unit tests: You know you are staying in the “state space funnel of acceptable behaviour”. Lesson learned: don’t trust Prolog code w/o unit tests. Coding in imperative/functio nal languages is hard, but here it’s harder because you miss execution paths. OTOH, ignoring execution paths may be ok, if you plan on not using them or coming back later.

Updating post to the working version now!

8

The keyword that is your gateway into how this has been studied and means to handle these problems is Numerical analysis.

The link goes way beyond the specifics of what you asked but you asked one of the most basic questions covered in this area and upon further investigation you will no doubtfully ask more of the related questions. While I know the link is not a direct answer to your question, I know you like to do research and learn, there is enough ideas in Numerical Analysis that many make careers of it.

A while back in a post I noted Runge–Kutta methods which if you use differential equations is quite useful.

1 Like
9

Absolutely. I still have Walter Gander’s “Computermathematik” somewhere. That was a good lecture, even though computers were weak.

Reflecting some more on this, I’m pointing out the danger of taking a binary decision (sequence membership) based on a float calculation. Float sequences really have to be represented in a symbolic fashion: N must not be computed from the float Step as the problem becomes ill-defined. N must be a given.

(Edit: LOL at being too old to remember the Prof’s name correctly)

10

You got me interested now :slight_smile:

First, I did a “simple” check to get rid of choice points. Now seq/4 looks like this:

seq(Lower, Step, Upper, X) :-
    N is floor((Upper - Lower) / Step),
    between(0, N, Y),
    (   var(X)
    ->  X is Lower + Y * Step
    ;   X =:= Lower + Y * Step,
        !
    ).

This is still not too efficient but I need to dig much deeper to figure out how to do this properly. This is what I mean:

?- time( seq(1, 0.2, 200, 198.4) ).
% 1,977 inferences, 0.001 CPU in 0.001 seconds (99% CPU, 2210060 Lips)
true.

However: is there a query with seq/4 that is wrong? I tried the usual things I could not find problems. I wish I had the time to apply your unit tests to this solution somehow, but today doesn’t look good.

When I say wrong I mean that it does not throw when it should, or gives results that are not mathematically correct. Again, I am sure there are problems but I lack the expertese to look for them.

EDIT: found one already:

?- seq(1, 0.000000001, 1.000000005, X).
X = 1.0 ;
X = 1.000000001 ;
X = 1.000000002 ;
X = 1.000000003 ;
X = 1.000000004.

?- seq(1, 0.000000001, 1.000000005, 1.000000005).
false.

Time to take a break for the day.

Another idea altogether would be to first use rationalize on any float arguments, but there might be pitfals there as well.

1 Like
11

You really don’t need to cover the var/nonvar case differently. Unless the cut is important (?).

The Obi-Wan Error comes from the fact that you one has Upper-Lower/Step deltas, thus Upper-Lower/Step + 1 boundary points to generate

seq(Lower, Step, Upper, X) :-
    N is floor((Upper - Lower) / Step) + 1,
    between(0, N, Y),
    X is Lower + Y * Step.

the above is just fine, within limits

?- seq(1, 0.000000001, 1.000000005, 1.000000005).
true.

But now things become ugly as you are starting to perform equality tests on floating point values, and even worse, equality tests on floating points values generated from the decimal representations given in the query.

The “verify” needs a “acceptable relative delta”. Then (just going blindly here, not sure I’m doing the right thing but it’s in the general direction):

seq(Lower, Step, Upper, X, RelDelta) :-
    N is floor((Upper - Lower) / Step) + 1,  % The relative delta will be involved here too, but how?
    between(0, N, Y), 
    (   var(X)
    ->  
    X is Lower + Y * Step       % Generate freely, seq/5 behave like a politician saying "so-so" things
    ;
    abs(X / (Lower + Y * Step) - 1.0) < RelDelta,  % Checking must be lenient!
    ! )
1 Like
12

Yes, it is important (well…) so that you don’t get the dangling choice point.

13

You were of course perfectly correct about this.

For my own piece of mind, I went ahead and looked at how seq is implemented. I was looking at the code here:

https://git.savannah.gnu.org/cgit/coreutils.git/tree/src/seq.c

If I am reading this correctly, there are no float inputs, only decimal fractions. If I understand correctly, this is fine because the input is strictly text. For my half-baked seq/4 idea this would probably mean that only decimal fraction literals are allowed, or floating point numbers are first rationalized.

Either way, your post gave me a nice brain-shake, so thank you! :slight_smile:

1 Like
14

The link seems to be broken…
Cheers/JCR

1 Like
15

Thanks … time to update.

1 Like