Strings as lists of CLP(Z) characters!

[panasenco]

EDIT: From the discussion below, I realized that I was using CLP(Z) as a crutch because I did not know how to deal with termination and instantiation issues. Now that I understand the difference between logic and control, and that instantiation checks should be done in such a way as to not impact the logic, I'm perfectly comfortable with instantiation errors, and recognize their value. For more details, see the responses below. The approach in this original post is not a good practice.

---

I'm having a fantastic experience writing DCGs that reason about characters as CLP(Z) integers rather than atoms.

I began working on library(json) based on this official spec and was immediately bogged down with checking whether variables are instantiated, running into strange instantiation-related errors, coding around parsing/generating directions, etc. It was not fun. Here's a link to my first stab at writing library(json).

At this point I was getting very frustrated and disappointed. I felt that the promise of Prolog was broken and if I couldn't reason about things declaratively in Prolog, I might as well just stick to Python. I thought "If only I had a char_type/2 that worked declaratively without instantiation issues." That's when it hit me that there's a limited number of characters, so it should be possible to reason about them using CLP(Z) domains.

So I sat down and wrote a first version of library(pure). This library provides a predicate code_type/2 that links a code to its character type in the exact same way that char_type/2 does, except it does it with CLP(Z) domains. With code_type/2 you don't have to worry about instantiating either the character or the type.

It further occurred to me that since I was now working with CLP(Z) domains, I could do more sophisticated things with boolean logic, specifically checking whether a character is in one of multiple domains or checking whether a character is NOT in a domain. So I wrote code_incl_excl/3 which you can use to declaratively reason about characters based on the types they're of or not of, and lists they're in or not in. You can additionally use code_incl_excl/4 to reify that reasoning to use with library(reif).

Using the above tools, I began writing a much more elegant and flexibie library(json). I've only written the string parsing/generating section so far, but I'm very happy with how simple it is to write and read, and its termination properties.

Example run:

?- use_module(library(json)).
?- use_module(library(dcgs)).
?- use_module(library(lists)).
?- maplist(char_code, "H3ll\b\xd7a4\o W$rl\nd\t!", InnerCodes), phrase(json_string(InnerCodes), JsonCodes), maplist(char_code, JsonChars, JsonCodes).
   InnerCodes = [72,51,108,108,8,55204,111,32,87,36|...], JsonCodes = [34,72,51,108,108,92,98,92,117,100|...], JsonChars = "\"H3ll\\b\\ud7a4o W$rl ..."
;  false.
?- maplist(char_code, "\"H3ll\\b\\ud7a4o W$rl\\nd\\t!\"", JsonCodes), phrase(json_string(InnerCodes), JsonCodes), maplist(char_code,
 InnerChars, InnerCodes).
   JsonCodes = [34,72,51,108,108,92,98,92,117,100|...], InnerChars = "H3ll\b\xd7a4\o W$rl\nd\t!", InnerCodes = [72,51,108,108,8,55204,111,32,87,36|...]
;  false.

The only thing that puts a dampener on my bright spirits right now is that the performance is truly awful. Even parsing the above 26 character long JSON string takes 20 seconds. I hope that this can be improved somehow...

At this point I want to solicit feedback from the community before proceeding further. Has what I've done been tried or considered before? Do you see any future in this approach? Does anyone have ideas about how to resolve the performance issue?

I greatly appreciate any and all feedback.

[mthom]

I'll try the example and see if I can't find the time sink.

[triska]

Independently of the modeling question, I think a worthwhile question to ask is: Are these the kind of answers we want to see on the toplevel, and when reasoning about the program (during slicing, tracing, debugging etc.)? The key attraction of using characters instead of codes is that characters are so nicely readable, and for this reason Scryer Prolog has dedicated support for them in the form of a very compact and efficient representation. library(charsio) is designed to further encourage reasoning about characters due to their convenience and readability.

So, I think working with characters is overall much preferable. If too much manual work becomes involved when writing a parser over characters, I think this should be taken as a sign and motivation to search for better abstractions. For example, a predicate like char_type_/3 could be useful for reification: It is like char_type/2, and the third argument is a truth value denoting whether this is the case. In this case, char_type_/3 can be used as a test in if_/3.

Another approach could be to automatically generate a lower-level parser with all necessary tests from a more declarative description when the library is loaded. I'm using this approach to generate many predicates of library(clpz) at run-time from smaller, more declarative descriptions.

[panasenco]

My initial draw to Prolog was mostly the logical purity of Prolog you described in your book, @triska.

Let me try to formulate the JSON string problem in a pure way:

There exists some mapping between one or more internal (Prolog) characters and one or more external (JSON) characters. For example, the single internal character \b (code 8) is mapped to two external characters: \ (code 92) and b (code 98).

The mapping is composed of multiple sub-mappings that are conditional on the types (aka domains) of both the internal and the external characters. An internal character that's alphanumeric, graphic, or a space, and not one of the escape characters is mapped to itself externally. An internal character that's one of the escape characters gets mapped to two external characters: \ and its corresponding graphical character. All other internal characters get mapped to the characters \, u, and the 4-digit hex code representation of itself.

This bidirectional reasoning about domains and their unions and differences is easy and fun with CLP(Z), and I have no idea how to do it with library(charsio), if it's even possible. Trying to wrestle with library(charsio) was taking me further away from the logical purity and a deep understanding of the problem, while using CLP(Z) brought me closer. Reification is just a bonus, but I don't actually use it in my code yet.

Based on this context, what do you think is the best path forward to retain the ability to see characters on the toplevel while also gaining the ability to reason about the domains of characters in a pure manner? I want some built-in domains but also the ability to define my own domains and construct unions, intersections, and differences. I would ideally also like an analogue to library(clpz)'s label/1 in order to generate concrete characters on backtracking.

[ghost]

Example.
The goal shouldn't be to parse and generate (very expensive) but to parse/read and write.

You can delay the goal with freeze to avoid some of the instantiation error. But I don't think the user is interested in:
?- Ls = [_, _, \, _, _, _], Cs = [a|_], phrase(string(str(Cs)), Ls).
So lines 64-78 can be removed.

With code_type/2 you don't have to worry about instantiating either the character or the type.

For writing, the character must be instantiated. (Will the user generate all the possible JSON or only one specifically?)
The database for unicode is in the form of tests so the character is required even if the type is supplied, the user can freeze the goal.

This bidirectional reasoning about domains and their unions and differences... if it's even possible.

Not possible currently, for that you need to attach to a variable information (its type), attributed variables can achieve that.

But you will have a lot to develop like ?- char_type(A, alphabetic), char_type(A, lower), char_type(A, upper). should fail without instantiating A, then there is also char_type(A, upper(U)) or char_type(A, uppers(Us)) (depending which one stabilize) so you can attach upper to U and Us needs to be a list of upper. You can prototype with freeze to start.

Or you can instantiate a solution but for each choice point at worse you have 1112063 choices (even with 2) the power doesn't look good.

Other solutions?

That's when it hit me that there's a limited number of characters, ...

You still have to generate the domain manually (always updating to keep up with unicode) or automatically (term expansion but slow). If you generate it then why not a domain of atom (add a system predicate for next atom)?

You could extend char_type/2 and char_types/2 like in the example, you can create type/subdomain and make an union.

Trying to wrestle with library(charsio) was taking me further away from the logical purity...

The library clpz is built on impure, Prolog doesn't provide all the pure construct by default, you have to make them. If they are available then enjoy.

Line:
By default atom in Scryer are UTF-8, are you going to support more than UTF-8? If so then the atoms aren't enough.

[panasenco]

Your code example works reliably and quickly (except for parsing/generating non-ASCII characters, but I think that was intentional on your part). It even works when neither the internal string nor the JSON are instantiated, which is really cool! However, I have no idea how it works even after reading through it several times. I would be afraid to touch anything there because it feels like a skillfully constructed house of cards that will collapse if I try to add or remove anything. And it's not like I'm a complete newbie - I already wrote a DCG parser/generator in Prolog once.

I sincerely admire your skill and intellect, but your code is not maintainable by anyone with an IQ under 200 (to be fair, I feel that way about most Prolog code I see).

What I find appealing in my CLP(Z)-based code is that it's very short, pure, and to the point without multiple levels of conditionals, cuts, and instantiation checks.

The goal shouldn't be to parse and generate (very expensive) but to parse/read and write.

I don't understand the difference. Of course we want to be able to both parse and generate/serialize JSON. And your code does that just fine.

For writing, the character must be instantiated. (Will the user generate all the possible JSON or only one specifically?)

The user will probably be interested in only one version of the JSON. However, I feel that to take full advantage of the power of Prolog, we must be able to reason about the mapping between the internal representation and JSON characters in the abstract, and only parse or generate as a side effect of narrowing down the mapped domains.

But you will have a lot to develop like ?- char_type(A, alphabetic), char_type(A, lower), char_type(A, upper). should fail without instantiating A, then there is also char_type(A, upper(U)) or char_type(A, uppers(Us)) (depending which one stabilize) so you can attach upper to U and Us needs to be a list of upper. You can prototype with freeze to start.

Thanks, I'll look into using freeze/2, have never used it before.

Or you can instantiate a solution but for each choice point at worse you have 1112063 choices (even with 2) the power doesn't look good.

Yeah I think ideally we would reason about this in terms of domains rather than backtracking over every possible character with brute force.

You still have to generate the domain manually (always updating to keep up with unicode) or automatically (term expansion but slow). If you generate it then why not a domain of atom (add a system predicate for next atom)?

A domain of atom would be ideal! Maybe there's some way to move CLP(Z)'s domain reasoning logic into the Rust backend so that we can apply domain reasoning to not just integers but characters and possibly other applications down the line (rationals? dates? custom domains?).

Line:
By default atom in Scryer are UTF-8, are you going to support more than UTF-8? If so then the atoms aren't enough.

I think just UTF-8 is enough, but any good solution can probably be easily extended with other encodings as necessary.

[ghost]

I should have talk more about the example: The first part is how char_type/2 could be extended and creates char_types/2. The second part is a partial implementation of a JSON string. The last part is how to use term expansion to generate type_domain, comment the last line to load faster.

...(except for parsing/generating non-ASCII characters, but I think that was intentional on your part).

Being non-ASCII isn't the goal, but for generation a smaller set is quicker, you can change line 65.

The ideal end result for the internal string (still incomplete):

str([]) --> [].
str([C|Cs]) --> [C],
    {   \+ ex_char_type(C, chars("\\\"/")),
        ex_char_types(C, [alphanumeric, ascii_graphic, chars(" ")])
    }, % !,
    str(Cs).
str([C|Cs]) --> [\, C0],
    { escape_meta(C0, C) },
    str(Cs).

But it isn't possible to generate when there are uninstantiated variables.

I don't understand the difference. Of course we want to be able to both parse and generate/serialize JSON. And your code does that just fine.

If you do like CLP(Z) where you formulate some constraints then label to find/generate some solutions, it's going to be expensive. When parsing/reading, everything that's needed is instantiated and when serializing/writing there must not be uninstantiated variable. Of course the end result on disk is a generated JSON (generated but not by a search).

It even works when neither the internal string nor the JSON are instantiated, which is really cool!

Cool but it's complicated and the user will never uses that (unless it's testing/fuzzing other parsers).

Maybe there's some way to move CLP(Z)'s domain reasoning logic into the Rust backend...

The Rust part is supposed to be very simple and porting is probably harder that reusing the Prolog code directly.

With a codes approach, extension isn't going to be an issue and it can be based on CLP(Z). You could keep track of the input if it's atom-based or code-based to output the result.

With an atom approach, you have work, modeling ahead of you for charsio and json library.

[panasenco]

I really really like your 'ideal end result', actually! I'd be happy if I could write code like that. I don't actually mind that one of the sides has to be instantiated - as long as I don't have to write special cases for the instantiation logic.

Could you modify library(charsio) with your code and open a pull request when you're ready? If it really ends up working as well as you hope to achieve, then your ex_char_type/2 and ex_char_types/2 should become char_type/2 and char_types/2 while existing char_type/2 should become something like internal_char_type/2 and be removed from the public interface.

[ghost]

That extension still needs to be polished and discussed, I think you should do it (having one more maintainer is better).

... one of the sides has to be instantiated ...

Instantiation error isn't bad, you can always fix it by reordering goals or with freeze. It's error like representation_error that's an issue where you can only catch it.

... as long as I don't have to write special cases for the instantiation logic.

Many predicates test for instantiations like call/N, format/2, (in)/2, if_/3, phrase_from_file/3, ... and testing helps the user to narrow down where it is. At some point you are going to need to test/write it, don't hesitate (if there is too many then try changing the representation (defaulty?)). Don't go the integer/1 way (later comes integer_si/1).

[panasenco]

Unfortunately, I'm not qualified to maintain your extension code, @notoria. I'd be more than happy to use it to write library(json) once you finish it though.

[UWN]

This is a very nice attempt. There is a lot to say about it. Well, I will just string out one of the most relevant points first.

1mo, it seems that you are a bit annoyed by the instantiation errors Prolog produced. Don't! Sadly, these errors got a very bad rap, although they are one of the key elements of making otherwise impure, inefficient or ineffective code pure and that with reasonable effort. Rest assured, you are not the first to be annoyed. In fact, in the transition from Prolog I (dit Marseille Prolog) to Edinburgh Prolog (DEC10 Prolog) all meticulously designed errors were replaced by silent failure or even worse means. And to the present day we are still recovering from this decision. Also in your code there are such impure parts that would profit from instantiation errors. Think of Cs = [0'a], code_type(0'a, codes(Cs)) which succeeds whereas its generalization code_type(0'a, codes(Cs)) fails. An honest but annoying instantiation error would prevent this.

2do, you are encoding Unicode's highly irregular structure with the domain description of CLP(Z). But note that you are not really using the CLP(Z) functionality at all. It's rather this (\/)/2- disjonction of singletons and compact intervals which you use, but not the actual constraint solving process. And, as already remarked by @notoria, in case you really want some effective constraints, you rather would have to roll them on your own. It's possible, but way of an overkill.

3tio, on the advantages of chars, @triska's answer and this is all that needs to be said. Think of it, there is a factor of 24 between partial strings and list of codes, but much, much more with the current constraints...

4to, for the annoyance, there is more to come. Think of non-termination which nevertheless is preferable to incorrect answers. But don't despair, it's Programmation en logique and not sans logique.

(And, if you are still here and interested in using CLP(Z) in a pure manner, don't forget clpz:monotonic.)

[triska]

I think the comment in the source file expresses the situation well:

Maybe at some point in the future we'll have a library that takes a pure logic character parsing/generating DCG and 'injects' control strategy into it. We aren't there yet...

One small thing I noticed: Using a so-called lagged argument, we can benefit from first argument indexing for example in json_members//1 by writing it like this:

json_members([Pair|Pairs]) --> json_members_(Pairs, Pair).

json_members_([], Key-Value) --> json_member(Key, Value).
json_members_([Pair|Pairs], Key-Value) -->
        json_member(Key, Value),
        ",",
        json_members_(Pairs, Pair).

This makes the predicate deterministic if the length of the list of pairs is known. The same approach can be used in other places too to symbolically distinguish between exactly one and at least two elements in the list.

[panasenco]

I fixed it, and did my best to explain why, but I'm actually confused now.

I understand that my original representation was defaulty, but the below one wouldn't be defaulty. What's the advantage of using a lagged argument over the below representation?

json_members([Key-Value])                        --> json_member(Key, Value).
json_members([Key1-Value1, Key2-Value2 | Pairs]) --> json_member(Key1, Value1), ",", json_members([Key2-Value2|Pairs]).

[UWN]

... but the ideal solution would be to either make it more pure so that it succeeds both ways or ...

Not necessarily so. With

code_type(Code, Type) :-
   when(( nonvar(Code), ground(Type) ), code_typeInternal(Code, Type) ).

both queries would terminate, that is ?- Cs = [0'a], code_type(0'a, codes(Cs)). and ?- code_type(0'a, codes(Cs)), Cs = [0'a]. succeed and terminate. (when/2 is a generalization of freeze/2 will surely be added some time.) So the problem seems to be solved but at the rather high price of floundering goals. Think of (for the sake of argument) ?- code_type(C, C). which clearly should fail, but instead you get back a conditional answer, with a so called floundering goal, saying: Yes, there is a solution for C, provided that code_typeInternal(C, C) holds.

So we have substituted instantiation errors and (some but not all) infinite loops by answers that no longer contain solutions. This approach has been particularly explored by Mu, xp, and Nu Prolog with quite limited success. Floundering goals are very hard to debug. Even worse if they mix with non-termination. Essentially you have to either trace your program step-by-step or use a modified algorithmic/declarative diagnosis procedure which requires you to play the role of an oracle thereby answering many detailed questions (which you could answer incorrectly as well ...).

Contrast this to regular Prolog execution where you can use a failure-slice to narrow down the reason for non-termination (or an instantiation error).

Maybe things could be improved further, though.

CLP(Z) terminates even when returning infinitely many solutions

Similarly, it may produce an answer, when there is no solution. Say:

?- [X,Y,Z] ins 1..sup, N #>2, X^N+Y^N#=Z^N.
   clpz:(_A+_B#=_C), clpz:(Z^N#=_C), clpz:(X^N#=_A), clpz:(Y^N#=_B), clpz:(_A in 1..sup), clpz:(_B in 1..sup), clpz:(Z in 1..sup), clpz:(_C in 2..sup), clpz:(X in 1..sup), clpz:(N in 3..sup), clpz:(Y in 1..sup).

And, CLP(Z) is throwing instantiation errors even when it could do better:

?- X #> 0, labeling([],[X]).
caught: error(instantiation_error,instantiation_error(unknown(from_to(n(1),sup)),1))
?- X in 1..Y.
caught: error(instantiation_error,instantiation_error(unknown(1.._1287335),1))

The first to guarantee termination of labeling/2, the second for consistency and conformity: CLP(Z) is a valid extension of ISO Prolog.

Now I don't know. What is your goal?

Foremostly, to get correct solutions for pure programs (when there is no error, no conditional answer or floundering, no unproductive non-termination). So we can exploit properties of programs directly without any complex analysis. That's why errors are so important. From this on, Scryer is here on a very promising track.

[panasenco]

CLP(Z) may produce an answer, when there is no solution

The answer that CLP(Z) returns - a definition of an empty set - is a logically and mathematically valid solution to the posed query.

But anyway, I completely concede that I was using CLP(Z) as a crutch because I did not know how to deal with termination and instantiation issues. Now that I understand the difference between logic and control, and that instantiation checks should be done in such a way as to not impact the logic, I'm perfectly comfortable with instantiation errors, and recognize their value.

[triska]

Regarding the representation: The representation is a list in both cases, i.e., a clean representation in both versions.

The difference between the two versions of the snippet only affects argument indexing: In the initial version, the principal functor of the first argument in both DCG rules was '.'/2, whereas in the version I posted, the two rules can be symbolically distinguished by the principal functor of their first argument: [] and '.'/2, respectively.

For this reason, the version I posted succeeds deterministically if the first argument is a list, whereas the initial version succeeds and leaves a choice-point. It is good practice to rely on argument indexing to prevent the creation of choice-points if possible.

We can tell whether Scryer Prolog succeeds deterministically by observing the toplevel answer. For instance, with the definition:

l([]) --> [].
l([L|Ls]) --> [L], l(Ls).

we get:

?- phrase(l("abc"), Ls).
   Ls = "abc".

i.e., deterministic success.

If we see no ".", as in:

?- phrase(l("abc"), Ls) ; false.
   Ls = "abc"

then a choice-point is still left. We need to ask for additional solutions, and only then do we get the information that no further solution exists:

?- phrase(l("abc"), Ls) ; false.
   Ls = "abc"
;  false.

Using a lagged argument, we allow argument indexing to automatically distinguish between the two possible rules based on the first argument: Either no element remains (the atom []), or at least one element remains ([_|_], i.e., a term with principal functor '.'/2).