# Re: RM and abstract syntax trees

Date: Wed, 31 Oct 2007 05:53:33 -0700

Message-ID: <1193835213.716681.17810_at_v23g2000prn.googlegroups.com>

On Oct 31, 12:23 pm, paul c <toledobythe..._at_ooyah.ac> wrote:

*> David BL wrote:
**>
**> ...
**>
*

> > Yes RM references things uniquely with values, but pointers are "value

*> > types"! ...
**>
**> Sure, but what good does it do to think of them that way, when plain old
**> "values" suffices?
*

A fair question.

Using Prolog notation, consider the following relations

var(N,S) :- node N is a variable named S number(N,I) :- node N is a number with value I add(N,N1,N2) :- node N is the addition of nodes N1,N2 mult(N,N1,N2) :- node N is the product of nodes N1,N2

Suppose we define a view called nodes(N) which is a union of projections as follows

nodes(N) :- var(N,_). nodes(N) :- number(N,_). nodes(N) :- add(N,_,_). nodes(N) :- mult(N,_,_).

Note that I use underscores for attributes to be projected away.

There are numerous integrity constraints. Each of the following SPJ queries must be empty.

var(N,S1), var(N,S2), S1 <> S2?

number(N,I1), number(N,I2), I1 <> I2?
add(N,N1,_), add(N,N2,_), N1 <> N2?

add(N,_,N1), add(N,_,N2), N1 <> N2? mult(N,N1,_), mult(N,N2,_), N1 <> N2? mult(N,_,N1), mult(N,_,N2), N1 <> N2? var(N,_), number(N,_)? var(N,_), add(N,_,_)? var(N,_), mult(N,_,_)?

number(N,_), add(N,_,_)?

number(N,_), mult(N,_,_)?

add(N,_,_), mult(N,_,_)? add(_,N,_), not nodes(N)? add(_,_,N), not nodes(N)?

mult(_,N,_), not nodes(N)?

mult(_,_,N), not nodes(N)?

*>From these integrity constraints we can deduce that joins used to
*

traverse down through the AST give us back precisely one tuple in the
result set.

Isn't it helpful to see the analogy with a pointer dereference (which also gives us a single result)?

I'll leave it up to you as to whether you dislike the analogy between node identifiers and pointer values, and the idea that a join can be compared to a pointer dereference. Perhaps you are right and the analogy creates confusion.

I find it particularly telling that Prolog provides the choice of

- using the approach above (which is how RM would be used); or
- using nested terms, (which is outside of RM's scope) and the clear winner is 2.