Re: RM and abstract syntax trees

From: David BL <davidbl_at_iinet.net.au>
Date: 31 Oct 2007 19:50:50 -0700
Message-ID: <1193810534.716595.45040_at_t8g2000prg.googlegroups.com>

[Quoted] 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?

[Quoted] I guess I equate pointers with edges in a directed graph (where by directed graph I'm referring to the formalised notion of a set of nodes plus a set of directed edges between nodes), and naturally I regard an AST as an acyclic directed graph.

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.

[Quoted] [Quoted] 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 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 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.

Received on Thu Nov 01 2007 - 03:50:50 CET