Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!bionet!agate!ucbvax!hplabs!hpfcdc!hpldola!patch
From: patch@hpldola.HP.COM (Pat Chkoreff)
Newsgroups: comp.lang.prolog
Subject: Re: Higher Order Extensions
Message-ID: <11500016@hpldola.HP.COM>
Date: 4 May 89 23:08:32 GMT
References: <11500013@hpldola.HP.COM>
Organization: HP Elec. Design Div. -ColoSpgs
Lines: 93

/ hpldola:comp.lang.prolog / cdsm@doc.ic.ac.uk (Chris Moss) /  4:00 am  Apr 26, 1989 /

> Ok if you raise everything up to the term level you can do everything
> (e.g. write Turing machine programs).

Precisely:  you can do anything in pure Prolog if you "raise everything
up to the term level".  All you need is pure Horn clauses:  no negation,
assert/retract, findall, etc.

The point about Turing machines proves this, but (obviously) you don't
have to go as far as emulating Turing machines.  Instead, you can
represent more interesting objects.  In my system, I like to represent
natural numbers, sets of natural numbers, partitioned sets of natural
numbers, directed acyclic graphs, etc.  I do this using very basic
concepts from universal algebra.

To model an enumerable set of objects which exist `in my head', I simply
define a set of terms which name the objects, and establish a one-to-one
correspondence between objects and their names.

The names are defined by a `term structure', by which I mean a set of
functors with fixed arities, along with some pure predicates that define
the `valid' terms constructed from applications of these functors.  Each
valid term is a name which denotes a unique object, and there is exactly
one name for every object.

I try to make the names as terse as possible, taking advantage of every
ordering or precondition I can think of to optimize the encoding scheme.

For example, let's say I wanted to represent all sets consisting of two
distinct natural numbers.  I might use the following term structure:

%     name (term)     object (interpretation)
%     ------------------------------------------------------------
%     [].             the natural number:  0.
%     s(N).           the natural number:  N+1.
%     p(A,B).         the set:             {A, (A+B+1)}.

natural([]).
natural(s(N)) :-
	natural(N).

pair(p(A,B)) :-
	natural(A),
	natural(B).


For example:

	p([],[])               denotes   {0,1}.
	p(s(s(s([]))),s([]))   denotes   {3,5}.
	p(s([]),s(s(s([]))))   denotes   {1,5}.

Note that this scheme captures the `precondition' that the numbers in
the set must be distinct.  You don't have to _check_ this condition,
since it is impossible to violate it.

I can change interpretation if I feel like it.  For example, the same
term structure can represent all sets consisting of two distinct _even_
natural numbers:

%     name (term)     object (interpretation)
%     ------------------------------------------------------------
%     [].             the natural number:  0.
%     s(N).           the natural number:  N+2.
%     p(A,B).         the set:             {A, (A+B+2)}.


For example:

	p([],[])               denotes   {0,2}.
	p(s(s(s([]))),s([]))   denotes   {6,10}.
	p(s([]),s(s(s([]))))   denotes   {2,10}.

---

In my system, the objects of interest are directed acyclic graphs, sets
of natural numbers, etc., so I'm doing this sort of thing for them.  In
pure Prolog, there is simply no way to manipulate these objects unless
they can be represented _as objects_.  And since I _want_ to represent
these objects anyway, I might as well use pure Prolog.

I vote in favor of "raising everything up to the term level".  I like
the sound of that.

All of this idealism is probably going to earn me a good kick in the
butt one of these days, the universe being what it is.  But maybe not,
Prolog compilers being what they are (:-}).



Patrick Chkoreff   719-590-5983  %  The quest for perfection is natural,
{hpfcla,hplabs}!hpldola!patch    %  rational, irrational, and transcendental.