Phrases from string work, but from file failes

You can find my current version of the code at my GitLab repository for advent of code.

From how I understand it, when I load the file into swipl using swipl y2015_d01.pl I see a warning that my first example is invalid and I do not see warnings for the remaining examples. This is as expected.

Though when I try to run ?- part1('y2015_d01.txt', S) from the REPL, the answer is false.

When I try ?- phrase_from_file(parens(P), 'y2015_d01.txt') the answer is also false, independantly if I have a trailing newline in the file or not.

If I hardcode the files content as an example, it suceeds with the already known value.

How can I repair my code to make part1('y2015_d01.txt', S) suceed and “return” a proper value in S? (And what is the proper terminology for this question?)

I was going to fix your code but found it easier to just write it from scratch.

Sorry I don’t have time at the moment to explain how it works. :smiley:


% parens_0//0 - Example DCG that only parses for validation. Does not return a structure.
parens_0 -->
    "(",
    parens_0, !.
parens_0 -->
    ")",
    parens_0, !.
parens_0 -->
    [_],
    parens_0, !.
parens_0 --> [].

% parens//1 DCG that returns only parenthesis from input.
parens(["("|T]) -->
    "(",
    parens(T), !.
parens([")"|T]) -->
    ")",
    parens(T), !.
parens(L) -->
    [_],
    parens(L), !.
parens([]) --> [].

parens_diff(List,Result) :-
    parens_diff(List,0,Result).

parens_diff(["("|T],Count0,Result) :-
    Count is Count0 + 1,
    parens_diff(T,Count,Result).
parens_diff([")"|T],Count0,Result) :-
    Count is Count0 - 1,
    parens_diff(T,Count,Result).
parens_diff([],Count,Count).

:- begin_tests(parens).

parens_0_test_generator("()()"   ).
parens_0_test_generator("(())"   ).
parens_0_test_generator("((("    ).
parens_0_test_generator("(()(()(").
parens_0_test_generator("))(((((").
parens_0_test_generator("())"    ).
parens_0_test_generator("))("    ).
parens_0_test_generator(")))"    ).
parens_0_test_generator(")())())").
parens_0_test_generator("a(b)c(d)e"   ).
parens_0_test_generator("a(b(c)d)e"   ).
parens_0_test_generator("a(b(c(d"    ).
parens_0_test_generator("a(b(c)d(e(f)g(h").
parens_0_test_generator("a)b)c(d(e(f(g(h").
parens_0_test_generator("a(b)c)d"    ).
parens_0_test_generator("a)b)c(d"    ).
parens_0_test_generator("a)b)c)d"    ).
parens_0_test_generator("a)b(c)d)e(f)g)h").

test(001,[forall(parens_0_test_generator(Input))]) :-
    string_codes(Input,Codes),
    phrase(parens_0,Codes,Rest),

    assertion( Rest == [] ).

parens_test_generator("()()"   ,["(",")","(",")"]).
parens_test_generator("(())"   ,["(","(",")",")"]).
parens_test_generator("((("    ,["(","(","("]).
parens_test_generator("(()(()(",["(","(",")","(","(",")","("]).
parens_test_generator("))(((((",[")",")","(","(","(","(","("]).
parens_test_generator("())"    ,["(",")",")"]).
parens_test_generator("))("    ,[")",")","("]).
parens_test_generator(")))"    ,[")",")",")"]).
parens_test_generator(")())())",[")","(",")",")","(",")",")"]).

test(002,[forall(parens_test_generator(Input,Expected_result))]) :-
    string_codes(Input,Codes),
    phrase(parens(Parens),Codes,Rest),

    assertion( Parens == Expected_result ),
    assertion( Rest == [] ).

parens_diff_test_generator(["(",")","(",")"]            ,0).
parens_diff_test_generator(["(","(",")",")"]            ,0).
parens_diff_test_generator(["(","(","("]                ,3).
parens_diff_test_generator(["(","(",")","(","(",")","("],3).
parens_diff_test_generator([")",")","(","(","(","(","("],3).
parens_diff_test_generator(["(",")",")"]                ,-1).
parens_diff_test_generator([")",")","("]                ,-1).
parens_diff_test_generator([")",")",")"]                ,-3).
parens_diff_test_generator([")","(",")",")","(",")",")"],-3).

test(003,[forall(parens_diff_test_generator(Input,Expected_result))]) :-
    parens_diff(Input,Result),

    assertion( Result == Expected_result ).

:- end_tests(parens).

Example run

?- make.
% c:/swi-discourse_027 compiled 0.00 sec, 0 clauses
% PL-Unit: parens .................................... done
% All 36 tests passed
true.

Thanks, even though I haven’t tried your code directly, at least I took the proper unit-tests from it, as they provide more helpful errors than my current “proof by example”.

I only changed my parens//1 to look like this (also inspired by yours):

parens([open|T]) --> "(", parens(T), !.
parens([close|T]) --> ")", parens(T), !.
parens(L) --> [_], parens(L), !.
parens([]) --> "".

This way

?- part1('y2015_d01.txt', S).

makes S = 0,
while

?- phrase_from_file(parens(Ps), 'y2015_d01.txt').

makes Ps = [].

I like to understand whats going on, and why phrase_from_file/2 doesn’t do what is expected (by me).

Finally I got it working.

It seems as if phrase_from_file/2 reads the file as a list of integers, while my parens//1 was built to consume a list of atoms.

After I rewrote my parens//1 to actually consume integers and the examples to be a list of integers as well by using backtick-strings (`()()`) everything worked and I can now proudly say, that I solved AoC 2015 day 1 both parts using (SWI) Prolog.

I’m pretty sure there is much room for improvement, but for now it works.

Final code (as it is now) is available on the repo.

assertion(Result = Expected)

See: Little testing tip

Also see:
The string type and its double quoted syntax
What type is a single quoted string?


:- expects_dialect(sicstus).

I didn’t know that could be done. Learn something new everyday.

Thanks! Will refactor that.

The “Book” I’m learning from (The Power of Prolog) introduces if_/3 from library(reif) at some point, but that doesn’t seem to work on SWI (though its advertised to work in that book), so I googled and found https://www.swi-prolog.org/pldoc/doc/_SWI_/library/dialect/sicstus.pl.

Thanks, I will do, but not tonight anymore :smiley:

There are a lot more of those pure predicates advocated by two of the advanced Prolog users who hang out on StackOverflow: false or repeat. Look at their bio pages and then click on the links to the predicates. Sometimes the code changes as time progresses and some of the needed predicates are spread amongst several post in different answers, but I tend to always find all of it in their Q&A.

1 Like

This is of course a matter of personal opinion, but the code looks fine as it is. It was also educational: your solution has a pretty high astonishment factor to me. I hope it is OK to ask a couple of questions.

Why CLP(FD), and why SICSTUS dialect? I couldn’t figure out what purpose those two serve.

Why are you parsing the input to a (seemingly) identical list, instead of just working with the input as it is – isn’t the “open” and “close” just a longer way of writing “(” and “)”?

I am also not sure about the purpose of the “if”.

It seems that the original input doesn’t have a new line at the end, and you added a new line in the file y2015_d01.txt in your repo. If you wanted to write a DCG that parses your input regardless of any trailing “blanks”, you could use blanks//0 from library(dcg/basics). For example, this DCG accepts a string of “(” and “)”, optionally terminated by a new line or any number of “blank” characters:

:- use_module(library(dcg/basics)).

parens -->
    paren,
    parens.
parens --> blanks.

paren --> "(".
paren --> ")".

It doesn’t do anything but at least it correctly parses the file.

Now you can “seed” it with a 0, for the initial floor, and add or subtract 1 on every “(” or “)”.

:- use_module(library(dcg/basics)).

floor(N0, N) -->
    next_floor(N0, N1),
    !,
    floor(N1, N).
floor(N, N) --> blanks.

next_floor(N0, N1) --> "(", { N1 is N0 + 1 }.
next_floor(N0, N1) --> ")", { N1 is N0 - 1 }.

(I added a cut because this problem doesn’t seem to require generating sequences of parentheses…)
To my untrained eye it looks like this is all you need for the first part. You call it as:

?- phrase_from_file(floor(0, Solution), Filename).

In a similar fashion, you can next_floor//2 you already have to solve the second part, and remainder//1 from library(dcg/basics) to ignore the rest of the input.

pos(-1, Pos, Pos) -->
    !,
    remainder(_).
pos(Floor, Pos0, Pos) -->
    next_floor(Floor, Next_floor),
    !,
    {   Pos1 is Pos0 + 1
    },
    pos(Next_floor, Pos1, Pos).

You call this as:

?- phrase_from_file(pos(0, 0, Solution), Filename).

But of course this is all very much a matter of taste. To me personally the big advantage of phrase_from_file and its sibling phrase_from_stream is processing arbitrary input in constant memory, using a DCG.

1 Like

Because thats what I was able to find. Well, CLP(FD) was used in the book all over the place, and in my functional/imperative mind using if and comparison felt the easiest.

I’m not quite sure, what ! does or how to properly use (;)/2. This is way over my head.

For now I’m happy I came up with something at all ;).

Mainly for learning purposes.

! (!/0) is the cut operator.

If you think of Prolog as an SLD resolution which can be represented as a search tree (example on slide 6), then having the ability to prune off a branch of the search (cut) is desirable as it will save having to process down a branch. (image)

I know those aren’t the greatest images, but those are the best I can find. Maybe someday I will make some better ones.


; (;/2) is the logical or and , (,/2) is the logical and. When you put , at the end of a line in a clause, the comma does not signify the end of the line, it signifies that you want the logical and of the results.

Likewise ; signifies that you want the logical or.

?- true,true.
true.

?- true,false.
false.

?- true;true.
true .

?- true;false.
true .

See: Control Predicates

An if in Prolog is most commonly done as

(
   <conditional>
->
   <execute if conditional true>
;
   <execute if conditional false>
)

:smiley: At the end, writing working code beats everything else, so again, good work!

1 Like

Just for the record, unification (=) is rarely the proper test. If Result is a variable (or more in general not sufficiently instantiated) the test will succeed. As with unit tests, result testing is typically done using
==/2 or =@=/2 (variant) and in some cases subsumes_term/2 if you do not care about some part of the term (such as the second argument of error/2 terms used in exceptions).

1 Like

Now that you mention it, while looking for examples, I noticed that all comparisons in src/Tests/library/test_csv.pl are actually using =/2 instead of ==/2.