Answer depends on a clause position - is that acceptable?

[Kapelianovych]

Hello. While trying to parse numbers I found out that answers are different when default clause of a number_tail predicate has different positions. Given the following code:

:- use_module(library(dcgs)).
:- use_module(library(clpz)).

digit(0) --> "0".
digit(1) --> "1".
digit(2) --> "2".
digit(3) --> "3".
digit(4) --> "4".
digit(5) --> "5".
digit(6) --> "6".
digit(7) --> "7".
digit(8) --> "8".
digit(9) --> "9".

number(Number) -->
 digit(FirstDigit),
 number_tail(Digits, DigitsCount),
 {
   Number #= FirstDigit * 10 ^ DigitsCount + Digits
 }.

number_tail(0, 0) --> [].
number_tail(Number, DigitsCount) -->
  ("," | ""),
  digit(Digit),
  number_tail(Digits, RestDigitsCount),
  {
    DigitsCount #= RestDigitsCount + 1,
    Number #= Digit * 10 ^ RestDigitsCount + Digits
  }.

repeated([]) --> [].
repeated([Expression | Expressions]) -->
  separator,
  number(Expression),
  separator,
  repeated(Expressions).

separator --> " " | [].

run(I, A) :-
  once(phrase(repeated(A), I)).

When I run it, I see the following

?- run("10,000", O).
     O = [1,0,0,0]

I understand that one 0 is missing because 0,0 is parsed as a single number.

But when I move number_tail(0, 0) --> []. down to be the second defined clause, then answer is different and correct.

?- run("10,000", O).
     O = [10000]

I am wondering if this is okay to rely on clause definition position, or I have done something very wrong somewhere.

[hurufu]

In a pure Prolog program order of clause can only influence termination properties or order of solutions. Generally it is a bad idea to rely on it. Also you are using once/1 that means that your grammar is ambiguous and you just limiting yourself to the first solution which may or may not be what you want. Try to define unambiguous grammar.

[UWN]

order of clause can only influence termination properties

This depends on your definition of termination. There is universal termination and (much rarer) existential termination.

In a pure, monotonic program, order of clauses does not even influence universal termination. That is, a goal G_0, false will terminate in the very same way regardless of the clause order. (For a goal G_0, false both universal and existential termination are the same.)

[hurufu]

I was thinking about this example:

l([_|T]) :- l(T).
l([]).

It doesn't terminate using default search strategy and using tabling. It only terminates using co-induction library(coinduction) (not available in Scryer) where it doesn't need l([]). clause at all. But if you will swap clauses then it will perfectly enumerate all lists.

[UWN]

And in this example, all goals with any L will terminate for ?- l(L), false. in exactly the same way regardless of the clause order.

(Coinduction is something entirely different.)

[hurufu]

It will terminate only when L is sufficiently instantiated, eg:

?- L=[1|_], l(L).

I get that l/1 describes correct solution (which is any list), but it is "unreachable" using any search strategy (SLD or SLG). But maybe I don't understand termination correctly. I don't fully grasp difference between "existential" and "universal" termination...

[UWN]

Note that I did not claim anything about what solutions are found. What we can say for sure is that the termination property remains the same for a goal G_0, false regardless of the clause order. So in your case L=[1|_], l(L), false does not terminate for both orders.

but it is "unreachable" using any search strategy

With iterative deepening all solutions are found:

nat(0).
nat(s(X)) :-
   nat(X).

l([_|T], s(X)) :- l(T,X).
l([], _).

?- nat(X), l(L,X).
   X = 0, L = []
;  X = s(0), L = [_A]
;  X = s(0), L = []
;  X = s(s(0)), L = [_A,_B]
;  X = s(s(0)), L = [_A]
;  X = s(s(0)), L = []
;  X = s(s(s(0))), L = [_A,_B,_C]
;  X = s(s(s(0))), L = [_A,_B]
;  X = s(s(s(0))), L = [_A]
;  X = s(s(s(0))), L = []
;  X = s(s(s(s(0)))), L = [_A,_B,_C,_D]
;  ... .

(We could have avoided all the de facto redundant answers by using a difference instead, but for the sake of "finding all solutions" this one is good enough.)

Iterative deepening holds for the pure, monotonic subset of Prolog. With, e.g. negation things get much more complex. But since most termination problems already occur without negation, it makes sense to first consider that subset only.

difference between "existential" and "universal" termination...

Existential termination: One ("the first") answer is found.

Universal termination: All answers are found.

And they are both the same for goals without any solution, since both just search for the false.

[haijinSk]

If once/1 is removed, we will see this:

?- run("10,000", O).
   O = [1,0,0,0]
;  O = [1,0,0]
;  O = [1,0,0]
;  O = [1,0]
;  O = [100,0,0]
;  O = [100,0]
;  O = [1000,0]
;  O = [10000]
;  false.

And:

?- run("10,000", O).
   O = [10000]
;  O = [1000,0]
;  O = [100,0]
;  O = [100,0,0]
;  O = [1,0]
;  O = [1,0,0]
;  O = [1,0,0]
;  O = [1,0,0,0]
;  false.

So there are more solutions (the answer(s) is the same, the order of the solutions doesn't matter in logic programming, it's a set), but with once/1 we get only the first answer/solution, in the both positions of number_tail(0, 0) --> []. The once/1 is, so to speak, destroying the set logic, in which the order is not important.

So with once/1, one has to be cautious, because in that case, suddenly, I would say, we have a list of clauses, not a set of clauses as in pure logic programming.

As I see it.

[haijinSk]

I feel, I want to say, I'm not a Prolog expert, nor a computer scientist: I'm almost a non-programmer, only: an inexperienced, naive user of Prolog. Moreover, there is theoretically more than one way how to understand "meaning" of a Prolog program.

I know, a real Prolog implementation "sees" clauses as, so to speak, lists, not sets, always; so their order matters, but that may be irrelevant for a user, if Prolog is used in a way that is coherent with logic programming (I know, it's not practically possible in every situation, nor in every definition in my mostly logical, (conceptually) "set oriented", Prolog program).

I'm sorry if my attempt here was, I'm afraid, confusing, or/and simply redundant. It was a quick attempt to help (hoping to be in a concise form), but yes, it was/is only "conceptual", and only in my own way, worse: a "lyrical" attempt. To help to understand when/why/how answers depends on a clause position. And that in using Prolog in a logic programming way, the order of clauses is not important conceptually (ignoring computational performance and termination/non-termination) to get the correct, intended answer(s), I believe.

[Kapelianovych]

I appreciate every comment. Unfortunately, I can select only one answer, but I carefully read every one of them, because I am sure there is useful information. So, thank you for listing your point of view 🙏

[haijinSk]

I was only confused by the "👀", then. :-)

Thank you.

[hurufu]

Returning to the OP question, problem lies in separator//0 and how it is used in repeated//1. Generally working with spaces can quickly make your grammar ambiguous, I usually normalize spaces and use e.g. single space " " as a delimiter.

[hurufu]

Also relevant: #2568 (comment)

[Kapelianovych]

I am trying to parse an interpreted language, where spaces between statements can be absent. Like in the following JavaScript snippet:

function a{let b=a+1;return b+1;}

I thought there is a straightforward way to define scannerless parser with Prolog and retain "greediness", but looks like I need that lexer stage to get rid of insignificant spaces.

[hurufu]

You can implement "greedy matching", but code will look different and more complex.

[Kapelianovych]

Thank you all for the comments!

[haijinSk]

As you said in a comment, you need more (parsing a programming language) than converting a string to a numeric data-type.

And as I said, I'm only a naive user of Prolog.

But, what about an approach like this (yes, it's quick and dirty and naive, no "optimization thinking" here) for converting a string to a number (yes, you need more, and this is only a toy even for "string-numbers"):

separator --> ",".
separator --> ".".

digit(D) --> { member(D,"0123456789") }, [D].

strNum([D]) -->  digit(D).
strNum([D|Ds]) --> digit(D), strNum(Ds).
strNum([D|Ds]) --> digit(D), separator, strNum(Ds).

anumber(N) --> strNum(Str), { number_chars(N,Str) }.

?- phrase(anumber(N),"10,000").
   N = 10000
;  false.

That anumber//1 grammar doesn't work as the true relation, it will parse or test, but not generate a "string-number" from a number.

In my imagination, it can be done in another way (to get the "num-string" ready to converting): by filtering out the separator, or mapping the separator to the empty string, if I know that I have only digits with separator(s). Or with a different definition of strNum//1, I think.

And then, for example:

space --> " ".

spaces --> space.
spaces --> space, spaces.

numbers([]) --> "".
numbers([N]) --> anumber(N).
numbers([N|Ns]) --> anumber(N), spaces, numbers(Ns).

?- phrase(numbers(Ns),"12,345   45.612").
   Ns = [12345,45612]
;  false.

And now, maybe, time for once/1, if I might:

spacesOrEmpty --> "".
spacesOrEmpty --> space, spacesOrEmpty.

numbersMaybeSpaceAround(Ns) --> spacesOrEmpty, numbers(Ns), spacesOrEmpty.

?- once(phrase(numbersMaybeSpaceAround(Ns),"  12,345   45.612 123456   ")).
   Ns = [12345,45612,123456].

Because of:

?- phrase(numbersMaybeSpaceAround(Ns),"  12,345   45.612 123456   ").
   Ns = [12345,45612,123456]
;  Ns = [12345,45612,123456]
;  Ns = [12345,45612,123456]
;  Ns = [12345,45612,123456]
;  Ns = [12345,45612,123456]
;  Ns = [12345,45612,123456]
;  Ns = [12345,45612,123456]
;  Ns = [12345,45612,123456]
;  Ns = [12345,45612,123456]
;  Ns = [12345,45612,123456]
;  Ns = [12345,45612,123456]
;  Ns = [12345,45612,123456]
;  Ns = [12345,45612,123456]
;  Ns = [12345,45612,123456]
;  false.

[UWN]

That anumber//1 grammar doesn't work as the true relation, it will parse or test, but not generate a "string-number" from a number.

It is not that bad. It enumerates the infinite set of numbers and their corresponding textual representation in an unfair manner. In fact, only the numbers 0..9 will be found.

To get all of them, simply enumerate them in a fair manner.

?- length(Xs,_),phrase(anumber(N),Xs).
   Xs = "0", N = 0
;  Xs = "1", N = 1
;  Xs = "2", N = 2
;  Xs = "3", N = 3
;  Xs = "4", N = 4
;  Xs = "5", N = 5
;  Xs = "6", N = 6
;  Xs = "7", N = 7
;  Xs = "8", N = 8
;  Xs = "9", N = 9
;  Xs = "00", N = 0
;  Xs = "01", N = 1
;  Xs = "02", N = 2
;  Xs = "03", N = 3
;  Xs = "04", N = 4
;  Xs = "05", N = 5
;  Xs = "06", N = 6
;  Xs = "07", N = 7
;  Xs = "08", N = 8
;  Xs = "09", N = 9
;  Xs = "10", N = 10 % so also numbers beyond 0..9 are found
;  ... .

[haijinSk]

With, for example, 10, I saw non-termination, so I was thinking: "Not the true (easy to use in the both directions) relation."

Thank you...

[haijinSk]

As I see it, your repeated//1 has so many different solutions (in that case the clause position matters with once/1) because separator//0 can be the empty string. And the empty string is between all characters in any string, therefore more numbers (all possibilities) are parsed than intended.

I apologize for writing here again; I use your code (plus my writing, plus examples/writing of others) as my own learning opportunity. So, thank you for posting it/the question here.

[UWN]

strNum([D]) -->  digit(D).
strNum([D|Ds]) --> digit(D), strNum(Ds).
strNum([D|Ds]) --> digit(D), separator, strNum(Ds).

I feel like it can help me change the code so parser won't produce a set of answers but only one (or at least much fewer than now).

Take in its stead:

digit(D) --> [D], { member(D,"0123456789") }.

strNum([D|Ds]) --> digit(D), strNum1(Ds).

strNum1([]) --> [].
strNum1(Ds) --> strNum(Ds).
strNum1(Ds) --> separator, strNum(Ds).

Exactly the same meaning and behaviour, but a bit faster, in particular if the length of the string is given.

[Kapelianovych]

Does char_type/2 from library(charsio) help?

Yes, initially I used that predicate, but then I had a need to express new line characters and identifier characters which could not be expressed with char_type, so replaced all character sets which contained non-typeable or non-ASCII characters with unicode_character and between_unicode_range.

[haijinSk]

In my words, Prolog can be hard for a new user because, so to speak, it has a rich history built-in, and sometimes we have to see "through" that, as with any tool for thinking, if programming is thinking, and if thinking means to find some useful perspective for the problem at hand.

Prolog doesn't enforce logic programming, as, for example, and at least in a sense, Haskell enforces functional programming. Prolog can be used, to some extend, for pure logic programming. And even then, there are more, at least theoretical, perspectives on what does it mean, the logic programming. It's easy to say that functional programming is programming with functions (of course, there is more things to it). So logic programming is programming with logic? There is nothing "un-logical" in functional programming, even in imperative programming (except notation like: "myVar = myVar + 1"), and even C programming language is a declarative programming in it's domain of low-level computer processes important for making operating systems.

There are things possible in C and impossible in other more high-level languages. They are easy in C. And we need the things now, and we will need them tomorrow. And it has nothing to do with speed of C. The thing is to see computer memory as a place for communicating at distance with "unknows". But I only know write "hello world" in C. I'm interested in some programming languages only from a "poetic" perspective, I like to read "poetic" things (some papers, some books, some articles, and essays: poetic by definition) about programming languages.

I love how easily I can create and process "structured data" in Prolog (and more things I love about Prolog). There are things I love to write in Prolog. And then, it's easier to write the whole program in Prolog, even if many parts of real Prolog are grey-zone or "I don't know what is it and I don't need it" for me. Maybe I'm not the right person to use Prolog, but I know: Prolog enforces. It enforces me to think about the most simple way of writing information about my "problem-domain" as data to be used for some computation. It enforces and enables that simplicity, I think.

[hurufu]

I don't think that Prolog is hard for new users – it is very hard if you are already trained in procedural languages. When you are fresh to the concept of programming then IMO Prolog is as difficult/easy as any other high-level programming language.

[rotu]

@haijinSk strong agree. It’s hard to tell by inspection whether code is well-behaved or not, since things like once and -> look benign enough until they bite you.

[haijinSk]

[...] That shows that the problem of parsing numbers is actually much broader and exists everywhere where sequence of expressions is expected. [...]

A great remark, I think. And maybe everything is on the web somewhere (for example, @UWN and @triska, Prolog experts and computer scientists, write things on-line), but I think, it might be a good candidate for "the first steps" on the Scryer web site, as parsing numbers (even in various DSL-like data-forms) from a text file might be useful. My naive view...

Here, I tried something different. A "brutal", extreme top-down, slow & "baroque", numerically fragile, definition of num//1 and nums//1. With "allusions" to some modules/libraries, If I might... This is not code for "profit", nor for a "CompSci class", only for fun, at best. At least, it can ignore everything but the numbers.

:- use_module(library(dcgs)).
:- use_module(library(lists)).
:- use_module(library(lambda)).
:- use_module(library(dif)).
:- use_module(library(reif)).

digits("0123456789").

separators(".,").

digitsAndSeparators(DandS) :-
  digits(Digits),
  separators(Separators),
  append(Digits,Separators,DandS).

num(N) -->
  seq([C|StrNum]), % I want at least one character, not the empty string here
  {
    digits(Digits),
    digitsAndSeparators(DandS),
    maplist(\E^member(E,DandS),[C|StrNum]), % lambda library
    tfilter(\E^memberd_t(E,Digits),[C|StrNum],StrNumWithoutSeparator), % reif library
    number_chars(N,StrNumWithoutSeparator)
  }.
 
nums([]) --> "".
nums([N]) --> num(N).
nums([N|Ns]) -->
  num(N),
  seq([C|NotStrNum]),
  {
    digitsAndSeparators(DandS),
    maplist(\E^maplist(dif(E),DandS),[C|NotStrNum]) % dif library
  },
  nums(Ns).

?- phrase(nums(N),"12.345 <-- here I have a dot // and here a comma --> 56,789 #### without a separator: 1000").
   N = [12345,56789,1000]
;  false.

[Kapelianovych]

Maan... How come you could think of this? The code is fascinating to me.

[haijinSk]

It's "don't try this at home" code, but thank you. I'm learning Prolog by doing things in crazy ways at first and often the crazy solution is ok for my purposes when the "input/output" is small.

In a sense, in that code I'm mostly abusing some very good and very useful things of the modern Prolog. Using a telegraphic style: I saw the good things on-line, by/via Markus @triska. And the things (as for example lambda and reif) are possible thanks to the work of @UWN (et al.).

Prolog is a practical/flexible programming language. The once/1 is here for example, the traditional "if-then-else" construct (good to know: we have the modern, relational version coherent with logic programming in reif library), negation ("as failure", but in a certain context it can be seen as "classical negation", google: Prolog inductive definitions), etc.

The flexibility, I would say, could be, for a new user, a daunting mix of the "declarative & procedural" meaning. And the new user, as I see it, has to learn seeing "through". To see when/where logic programming in Prolog ends and the pragmatic flexibility of Prolog begins.

[haijinSk]

Or, imagine... :-)

:- use_module(library(lists)).
:- use_module(library(lambda)).
:- use_module(library(dif)).
:- use_module(library(reif)).

digits("0123456789").

separators(".,").

digitsAndSeparators(DandS) :-
  digits(Digits),
  separators(Separators),
  append(Digits,Separators,DandS).

digit(D) :- digits(Digits), member(D,Digits).

separator(S) :- separators(Separators), member(S,Separators).

str_strNums("",[]).
str_strNums([D],[[D]]) :- digit(D).
str_strNums([D|Str],[[D|Ds]|StrNums]) :- digit(D), str_strNums(Str,[Ds|StrNums]).
str_strNums([S|Str],StrNums) :- separator(S), str_strNums(Str,StrNums).
str_strNums([C|Str],[[]|StrNums]) :- digitsAndSeparators(DandS), maplist(dif(C),DandS), str_strNums(Str,StrNums).

str_nums(Str,Nums) :-
  str_strNums(Str,StrNumsWithEmpties),
  tfilter(dif([]),StrNumsWithEmpties,StrNums),
  maplist(\S^N^number_chars(N,S),StrNums,Nums).

?- str_nums("  Numbers: 12,345, 67.890 30=10+20 Prolog was here... <---#@! 0000,,, 007 6 etc.  ",Nums).
   Nums = [12345,67890,30,10,20,0,7,6]
;  false.