CODEWITHSUNDEEP
prologdcgnon-termination
Edgar
Edgar

Reputation: 159

Termination of prolog query using using dcgs

Given the program

foo([]) --> [].
foo([Start|Rest]) --> alphanum(Start), foo(Rest).

alphanum(Ch)  --> [Ch], { char_type(Ch, alnum) }.

How can I make the query length(I, 2), phrase(foo(C), I), false. terminate? I am using SWI-Prolog version 8.4.3 for x86_64-linux

The non-termination seems to be originating from the last dcg rule. With the following program (not what I want), the query terminates.

foo([]) --> [].
foo([Start|Rest]) --> alphanum(Start), foo(Rest).

alphanum(Ch)  --> [Ch].

I don't mind any other formulation of the program that achieves the same results

Upvotes: 0

Views: 80

Answers (1)

brebs
brebs

Reputation: 4422

It will terminate - but there's a lot of Unicode character combinations to loop through.

You probably want instead (note that this is using usually-preferable codes instead of chars):

foo([]) --> [].
foo([Start|Rest]) --> alnum(Start), foo(Rest).

alnum(Digit) --> [Digit], { between(0'0, 0'9, Digit) }.
alnum(Lower) --> [Lower], { between(0'a, 0'z, Lower) }.
alnum(Upper) --> [Upper], { between(0'A, 0'Z, Upper) }.

Result in swi-prolog:

?- length(I, 2), phrase(foo(C), I), writeln(I), false.
...
[90,88]
[90,89]
[90,90]
false.

Upvotes: 1

Related Questions