Occur-check Problem!

I’m using: SWI-Prolog version 8.4.0

In “Logic Programming to Prolog by Krzysztof R. Apt. Prentice Hall 1997” I found an example that this query member(X, [f(X),X]) will produce the following interrupted listing:

X = f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(f(

But I’m finding different result:
KB:

mem(X, [X | List]).
mem(X, [Y | List]) :- mem(X, List).

Query:

member(X, [f(X),X])
X = f(X) ;
true.

Why is that?

Following A. Colmerauer 's rational tree unification, I think the answer equation " X = f(X)" denotes a cyclic term t such that t satisfies the equaiton t = f(t). Intuitively, t is a cyclic term t = f(f(f(f(…
There must be better answers to your question.

The textbook assumes that the Prolog implementation struggles to represent a cyclic term. SWI-Prolog however knows how to print the cyclic term that you construct with X = f(X).

1 Like

SWI-Prolog can handle cyclic terms. Here’s a more complicated example:

?- X = f(Y), Y = g(Z), Z = h(X).
X = f(g(h(X))),
Y = g(h(X)),
Z = h(X).

Are these cyclic terms useful for anything? From what I read here and elsewhere, they are mostly a nuisance, flooding the screen and memory if not handled properly.

Out of curiosity, can anyone point me to an application where the representation as a cyclic term solves a problem?

In a nutshell:

  • They are mostly a nuisance. In the first place for the Prolog implementation to avoid crashing on them and in the second place for the user to avoid loops.
  • They are unavoidable as while implementing the occurs check everywhere works for the vast majority of Prolog programs, there is also a class of algorithms that suffers badly (performance wise).
  • They twice helped me implementing a graph isomorphism problem. One time seriously implementing a demo version of RDF 1.1 semantics and once to solve a challenge problem at the ICLP programming contest :slight_smile:
  • They also allow implementing data structures such as double linked lists, using setarg/3 to insert and remove cells. That has little to do with logic programing though :frowning:
2 Likes

Sounds very interesting. I’m reading about Keras, and any details related to graphs in Prolog would be welcome. Could you share which ICLP challenge problem you’re referring ?

Its quite few years ago. I just recall that my partner in the challenge recognised the core of the problem as an isomorphism problem between two cyclic graphs that required the same semantics as Prolog’s ==/2 on cyclic terms. So, we could translate the graphs into cyclic terms and use ==/2 :slight_smile:

I disagree with the characterization that they are a nuisance. Cyclic terms can be effectively used to model graphs and graphs are a fundamental data structure in mathematics and computer science. Real world examples of things that can be modelled by graphs include transportation, communication and power networks, electrical circuits, finite state machines, and computer programs.

Pretty much any programming language supports the equivalent of cyclic terms, usually by some form of reference that permit the construction referential loops in data structures. And any algorithm that attempts to convert them to a linear format, e.g., a write procedure producing text, must take that into account. (Note that you can’t actually output a graph; at best you can output a “program” that produces that graph if executed.)

Graphs can modelled without cyclic terms by breaking them down into acyclic pieces that can be labelled, and references can be replaced by the corresponding labels. (And sometimes that’s a natural way to build them in the first place.) The pieces get put back together by adding something akin to a symbol table that map labels back to the pieces. That’s fine but adds complexity (the symbol table) and degrades performance by having to “resolve” the labels whenever a reference is accessed. And now you have multiple pieces so it requires a custom output “function” in any case to produce a textual representation. So representing graphs as cyclic terms has some obvious advantages IMO.

As for examples, I have two in recent experience:

  1. Grammars (e.g., a BNF or PEG) consist of one or more rules and rule bodies can reference other rules so loops are not uncommon on grammars of any complexity, e.g., a grammar for parenthetical arithmetic expressions, e.g., 2*(3+5). So a grammar can be represented by a cyclic term where “calls” to a rule are represented by variables which then get bound to the term corresponding to that rule.
    Now grammars can be viewed as declarative programs - given a suitable “virtual machine”, a grammar term can be executed to parse an input string in that grammar. Since parsing efficiency is usually an issue, the ability to represent a grammar as a cyclic term is an advantage.

  2. The interval constraint network in pack clpBNR is one large cyclic term (incrementally constructed). Intervals are attributed variables whose attributes include a list of constraints, e.g., {X*Y=<1}. Each constraint is an expression between that interval and others and so cycles are impossible to avoid. These constraint networks can be quite large - hundreds of intervals and constraints - but that’s all hidden behind the interval instances.

In both examples, performance is an important success criteria. Fortunately the cyclic terms can be largely hidden behind a module API. For example, the need to write them out in some text form is rarely, if ever, necessary, although debugging can sometimes be a challenge.

My 2¢.

4 Likes

This, in a nutshell is my concern with representing a directed graph in the Prolog KB vs. providing the graph with real pointers through an external library. Eventually, I will benchmark this to see what the cost of each really is …

Dan

Prof. Gupta explained in this video that cyclic terms are essential for coinduction, that is, they fueled the innovation behind s(ASP). Interesting, but I 'm unsure how the showcased coinductive predicates and queries could play in practical use cases.

2 Likes

I remember that some library for coinductive programming existed in an old SWI-Prolog. I put “coinduction” in the search box of this forum, but failed to get information about the library.

Around Minute 45 Gupta explains a conductive version of member using a very accessible language, really impressive. Thanks for the hint to the video.

See coinduction.pl

Thanks. Interesting.

% cat > test.pl
:- use_module(library(coinduction)).

:- coinductive p/1.

p([1|T]) :- p(T).
% more test.pl
:- use_module(library(coinduction)).

:- coinductive p/1.

p([1|T]) :- p(T).
% swipl
Welcome to SWI-Prolog (threaded, 64 bits, version 8.5.1-26-ga67eb016c-DIRTY)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.
Please run ?- license. for legal details.

For online help and background, visit https://www.swi-prolog.org
For built-in help, use ?- help(Topic). or ?- apropos(Word).

?- pwd.
% /Users/cantor/
true.

?- [test].
true.

?- listing(p).
p(A) :-
    prolog_current_frame(B),
    prolog_frame_attribute(B, parent, C),
    prolog_frame_attribute(C, parent_goal, user:p(A)).
p(A) :-
    'coinductive p'(A),
    coinduction:no_lco.

true.

?- p([X,Y,Z|R]).
X = Y, Y = Z, Z = 1,
R = [1, 1|R]