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

[Christian Aistleitner]

Hello Martin,

On Fri, 20 Oct 2006 19:01:49 +0200, Martin Rubey  
<martin.rubey at univie.ac.at> wrote:

>> >  
>> -------------------------------------------------------------------------------
>> >
>> > 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.
>>
>>  From my point of view, your code looks like this in memory (I use the  
>> format
>> Adress: Data. All references to other entities are explicitely written
>> down).
>
> Hm, I find these “virtual memory locations” difficult to follow, but  
> I'll try.
> Let's stick to the example
> grammar(["Union(Atom,Cross(Self1,Self1))"]). However, I have difficulties
> following your setup:
>
>> It translates
>>
>> Definition of CombinatorialClass:
>> 00001000: [...]
>>
>> Definition of List( CombinatorialClass ):
>> 00002000: [...] 00001000 [...]
>>
>> Definition of Atom:
>> 00003000: [...]
>>
>> Definition of A:
>> 00004000: [...] 00003000 [...]
>>
>> Definition of res:
>> 00005000:  00003000 00005010
>> 00005010:  00003000 00000000
>
> but res depends also on List(CombinatorialClass), doesn't it?

The fact that the data at location 00005000 is of type  
List(CombinatorialClass), is only known in the universe.
Remember, we do not have types on data, but types on variables.
Unfortunately, you did not quote the universe of my setup -- let me give  
it again:

The grammar scope of the Universe (variable name, value, type) :
...
(A  , 00004000, 00001000 )
(res, 00005000, 00002000 )

That's the only place, where res is connected to its type and its memory  
location.

Of course, during compilation, the universe is again stored somewhere in  
memory. But at run-time, it need not be available.

> I suggest the following scheme. The situation before E(1) is called is

I condesned your setup a little.

> memory loc | Name     | associated functions and data
>
> 01           Atom
> 02           CC
> 03           List(CC)
> 10           A          CC, Atom
> 20           res        List(CC), 21
> 21                      10                     
> -------------------------------------------------------------------------------
> Now E(1) is called. Suppose the result is stored in mem. loc. 31

I think, your setup is already broken at this point.
I would remove CC from like 10, as described above.

Your location 20 is very problematic. Its compacted too much. It is  
crucial to separate between the elements of a node of a list.
Look at my setup above:

>> 00005000:  00003000 00005010
>> 00005010:  00003000 00000000

That means:

00005000:  00003000   -- reference to A
00005001:  00005010   -- reference to next node
00005010:  00003000   -- reference to A
00005011:  00000000   -- reference to next node

You condensed 00005000 and 00005001 into 21.

This condensing is relevant, I suppose. Because you should not get
   Union(Atom, Cross( 00005000, 00005000 ))
but
   Union(Atom, Cross( 00003000, 00003000))
. The content of the node of the list. Not the node of the List.

Assume, Cross is passed 00005000. How should Cross infer that at 00005000  
there is actually a node of a list and not a domain?

However, it might also be
   Union(Atom, Cross( apply( 00005000, 1 ), apply( 00005000, 1 ) ) )
due to lazy evaluation. This would explain why the whole thing works, bit  
is very, very tricky.

> Is this what you had in mind?

Yes, partly. Because, now I have a better picture, of what you'd expect to  
happen.
Hopefully, my explanations gave som impressions, why the code looks  
dangerous to me.

--
Kind regards,
Christian