Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!tut.cis.ohio-state.edu!ucbvax!mlpvm1.iinus1.ibm.com!ludemann
From: ludemann@mlpvm1.iinus1.ibm.com ("Peter Ludemann")
Newsgroups: comp.lang.prolog
Subject: general data structures are .not. impossible
Message-ID: <9102181728.AA03502@ucbvax.Berkeley.EDU>
Date: 18 Feb 91 17:12:59 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: ludemann@mlpvm1.iinus1.ibm.com
Lines: 85

jha@cs.ed.ac.uk (Jamie Andrews) writes:

>     And here's an idea for the printout problem:  perhaps in
> the declaration of data structures, the user could specify which
> nodes are to be printed along with the top-level structures, and
> which are to be printed as pointers, to be displayed further at
> the user's discretion.

It's easy to print out "infinite" data structures in Prolog.
Here are some examples (these are from IBM-Prolog; I think that
Prolog-II and Prolog-III do something similar).  I've used the
mode where the goal is printed out both before and after execution:
     <-X = f(X) .
      goal : <- V1 = f(V1) .
      0ms success
      <- f(@(1)) = f(f(@(1))) .
     <- X = f(g(X)) .
      goal : <- V1 = f(g(V1)) .
      0ms success
      <- f(g(@(2))) = f(g(f(g(@(2))))) .
     <- X = f(f(X)) .
      goal : <- V1 = f(f(V1)) .
      0ms success
      <- f(f(@(2))) = f(f(f(f(@(2))))) .

Even though I seldom use them, it's nice to know that I can
use circular graphs if I want and that my Prolog won't go into
an infinite loop while unifying them or printing them (by the
way, the overhead of handling circular structures is almost nil).

If we can think of fixed-points of recursive programs, I see
no reason why we can't also think of fixed-points of circular
data structures.

The following is used to define a data structure for a
recursive grammar -- it defines Sentence to be a circular graph;
a simple predicate can walk this graph, to verify that a
sentence fits the grammar (adapted from Colmerauer et al):

grammar(Sentence) :-
     Sentence    = ( Noun_phrase, Verb_phrase ),
     Noun_phrase = ( (Determiner, Adjectives, Noun, Relative)
                   | ProNoun ),
     Determiner  = ( [] | [the] | [a] | [every] ),
     Adjectives  = ( Adjective, Adjectives )
                   | [] ),
     Adjective   = ( [happy] | [nice] | [big] | [red] ),
     Relative    = ( ([that], Verb_phrase)
                   | [] ),
     Noun        = ( [man] | [woman] | [apple] ),
     ProNoun     = ( [he] | [she] | [you] | [me] ),
     Verb_phrase = ( Verb, Noun_phrase ),
     Verb        = ( [likes] | [eats] ) .

which results in:

Sentence =
   (
     (
       ( [] | [the] | [a] | [every] ) ,
       (
         ( [happy] | [nice] | [big] | [red] ) ,
         @(2) | []
       ) ,
       (   [man] | [woman] | [apple] ) ,
       ( [that] , ([likes] | [eats]) ,
         @(7) | []
       )
       | [he] | [she] | [you] | [me]
     ) ,
     ( [likes] | [eats] ) ,
     (
       ([] | [the] | [a] | [every] ) ,
       (
         ([happy] | [nice] | [big] | [red] ) ,
         @(2) | []
       ) ,
       ([man] | [woman] | [apple]   ) ,
       ([that] ,
         @(7) | []
         ) | [he] | [she] | [you] | [me]
      )
    ) .

- peter ludemann