Re: RM and abstract syntax trees

On Oct 31, 12:23 pm, paul c <toledobythe...@xxxxxxxx> 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 find it interesting that LISP and Prolog have far simpler integrity
constraints. RM is trying to *emulate* pointers, and the shoe
doesn't fit too well.

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.

Anyway, what matters is whether RM is suited to representing ASTs. I
find it significant that RM forces one to generate unique but
otherwise meaningless identifiers on all the nodes and exposes them
for all to see, whereas LISP, Prolog and even C/C++ allow the user/
programmer to work at a level of abstraction where node identifiers
are hidden.

I find it particularly telling that Prolog provides the choice of
1. using the approach above (which is how RM would be used); or
2. using nested terms, (which is outside of RM's scope)
and the clear winner is 2.



.

Relevant Pages

  • Re: RM and abstract syntax trees
    ... Isn't it helpful to see the analogy with a pointer dereference? ... 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 ...
    (comp.databases.theory)
  • Re: Introducing Perl Programmers to Prolog
    ... obvious analogy between Prolog and goal-oriented Makefile rules (except ... Another possibility is to take a SQL query and write it as a Prolog ...
    (comp.lang.prolog)