[Aldor-l] Should this "parser" work?

[Martin Rubey]

Consider the following snippet from Aldor-Combinat-experiments

-------------------------------------------------------------------------------

parse(s: String): ExpressionTree == {
...
}

-- evaluate basically replaces expressions "Self1", "Self2", etc. appearing in
-- t with the corresponding elements of selfList
evaluate(
    t: ExpressionTree,
    selfList: List CombinatorialClass
): CombinatorialClass == {
...
}

grammar(p: List String): List CombinatorialClass == {
        macro CC == CombinatorialClass;
        import from MachineInteger, List CC;
        A: CC == Atom;
        res: List CC := [A for x in p];

        E(i: MachineInteger): CC == evaluate(parse(p.i), res) add;

        for i in 1..#p repeat res.i := E(i);
        res;
}

-------------------------------------------------------------------------------

Consider for example the effect of

grammar(["Union(Atom, Cross(Self1, Self1))"])

* res is initialized to [b] with "b" being an instance of the
  CombinatorialClass Atom. In fact, it could be any CombinatorialClass.

* E(1) is called

  * parse("Union(Atom, Cross(Self1, Self1))") returns an ExpressionTree
    representation of the string. No magic. Let's call it "expr"

  * evaluate(expr, [b]) returns the CombinatorialClass 
    Union(Atom, Cross(b, b)).

* b is set to the result of E(1), i.e., Union(Atom, Cross(b, b))


With the current Aldor compiler, this "works", i.e., the result is the
CombinatorialClass recursively defined by 

b == Union(Atom, Cross(b, b)) add;

A more complicated example was given by Ralf. He wrote:

> Note that the last for loop modifies "res", so, in fact, one changes a
> (assumed to be constant) parameter in a domain construction (namely
> "evaluate"). Well, evaluate itself is actually NOT a domain constructor, it's
> just a function, but anyway. The whole thing is not yet formulated in a way
> that satisfies me.
>
> Suppose you take the grammar
> 
> A = Union(Atom, Cross(A, B))
> B = Union(Atom, Cross(B, A))
> 
> The for loop iterates 2 times.
> 
> E(1) means evaluate("Union(Atom, Cross(Self1, Self2))", [Atom, Atom])
> E(2) means evaluate("Union(Atom, Cross(Self2, Self1))", [E(1), Atom])
> 
> As you see from the grammar, A and B are the same thing, but how can one be
> sure by the "for" construction? See, E(1) and E(2) are evaluated with
> different parameters. Is everyone sure that E(1) = E(2)? (Whatever = means
> here.)

However, I think he made a slight mistake. Namely, I think that, with res
initialized to [b1, b2]

* E(1) means evaluate("Union(Atom, Cross(Self1, Self2))", [b1, b2])

* b1 is set to E(1), i.e. Union(Atom, Cross(b1, b2)

* E(2) means evaluate("Union(Atom, Cross(Self2, Self1))", [b1, b2])

* b2 is set to E(2), i.e. Union(Atom, Cross(b2, b1)

In other words, E(1) and E(2) are *not* evaluated with different
parameters. The elements of res point to some functions. The functions they
point to change during the for loop -- i.e., the values of b1 and b2 -- not the
elements of res themselves. I think it is similar to the following situation:

%1 >> #include "aldor"
%2 >> #include "aldorinterp"
%3 >> import from MachineInteger, List MachineInteger, List List MachineInteger
%4 >> b := [1]; res := [b]; res.1.1 := 2

b did not change, only the element within b did.

Christian objected:

> What it all comes down to is building a domain and afterwards_ exchanging its
> parameters with different values.  Its plainly a trick thats working --
> currently.  The reason why it is working, we can only guess.  [...] Maybe
> lazy instantiation (as hinted in the AUG).

Can my reasoning be made more precise? Can we rely on this behaviour?

Martin