Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!olivea!uunet!mcsun!ub4b!kulcs!saturnus.cs.kuleuven.ac.be
From: bimandre@saturnus.cs.kuleuven.ac.be (Andre Marien)
Newsgroups: comp.lang.prolog
Subject: Re:  general data structures are impossible
Message-ID: <1948@n-kulcs.cs.kuleuven.ac.be>
Date: 14 Feb 91 15:33:09 GMT
References: <1991Feb12.013413.24312@cs.ubc.ca> <4765@goanna.cs.rmit.oz.au> <1991Feb13.235655.6202@cs.ubc.ca> <17853@cs.utexas.edu>
Sender: news@cs.kuleuven.ac.be
Organization: Dept. of Computer Science (K.U.Leuven)
Lines: 68
Originator: bimandre@saturnus

> As a computational engine, Prolog is Turing complete.  The issue
> is not whether the application can be implemented Prolog, but
> whether one can implement this particular data structure, with
> its particular performance characteristics.)
> 
> Russell

Don't blame Prolog; some Prologs can do it: you need support for infinite
terms. PrologII and PrologIII are the leading examples, I think.
(not that others don't have it)

The following program works as requested with inf tree support:

     register_person(P,L,L) :- 
     	member_chk(P,L), ! . 
     register_person(P,L,[P|L]) . 
      
     write_person(P) :- 
     	name_person(P,NN), 
     	age_person(P,AN), 
     	ref_partner(P,S), 
     	name_person(S,NS), 
     	age_person(S,AS), 
     	write(name = NN), nl, 
     	write(' age' = AN), nl, 
     	write(partner = NS), nl, 
     	write(' age' = AS), nl . 
      
     name_person(p(N,S,A),N) . 
     ref_partner(p(N,S,A),S) . 
     age_person(p(N,S,A),A) . 
      
     p(L,a(NN,NS,NA),NL) :- 
     	name_person(PS,NS), 
     	ref_partner(PS,PN), 
     	name_person(PN,NN), 
     	ref_partner(PN,PS), 
     	age_person(PN,NA), 
     	register_person(PN,L,TL), 
     	register_person(PS,TL,NL), 
     	write('added:'), nl, 
     	write_person(PN)more, 
     	nl . 
     p(L,n(NN),NL) :- 
     	name_person(PN,NN), 
     	register_person(PN,L,NL), 
     	write_person(PN), nl . 
      
     member_chk(X,[Y|L]) :- 
     	member_chk(X,Y,L) . 
      
     member_chk(X,X,L) :- ! . 
     member_chk(X,_,[Y|L]) :- 
     	member_chk(X,Y,L) . 
      
     test :- 
     	p([],a(john,jane,22),L1), 
     	p(L1,a(jane,john,21),L2), 
     	p(L2,a(mark,mia,60),L3), 
     	p(L3,a(mia,mark,18),L), 
     	p(L,n(john),_), 
     	p(L,n(jane),_), 
     	p(L,n(mark),_), 
     	p(L,n(mia),_) . 
      
 
Andre' Marien
bimandre@cs.kuleuven.ac.be