Interesting containers problem.

Interesting containers problem.

[Shark8]

Ok, so let's say we have a type for Identifiers:

   SubType Identifier is String
   with Dynamic_Predicate => Is_Valid( Identifier )
     or else raise Parse_Error with "Invalid identifier: """ & Identifier & '"';
--...
   -- ACH is a rename for Ada.Characters.Handling.
   Function Is_Valid( Input: String ) return Boolean is
     ( Input'Length in Positive and then
       ACH.Is_Letter(Input(Input'First)) and then
       ACH.Is_Alphanumeric(Input(Input'Last)) and then
       (for all Ch of Input => Ch = '_' or ACH.Is_Alphanumeric(Ch)) and then
       (for all Index in Input'First..Positive'Pred(Input'Last) =>
          (if Input(Index) = '_' then Input(Index+1) /= '_')
       )
     );

And a few types for types:
   Type Data_Type is ( Integer, Float, Fixed );
   Type Variable_Data( Type_Value : Data_Type ) is
    case Type_Value is
     when Integer => Integer_Value : Standard.Integer;
     when Float   => Float_Value   : Standard.Float;
     when Fixed   => Fixed_Value   : Fixed_Type; -- Defined elsewhere.
    end case;
   end record;

Now we can define a Symbol-table using the standard containers simply with this:

  Package Symbol_Table is
    new Ada.Containers.Indefinite_Ordered_Maps(
        Key_Type     => Identifier,
        Element_Type => Variable_Data,
        "<"          => Ada.Strings.Less_Case_Insensitive,
        "="          => "="
    );

And that's all well and good; however, there is one limitation here that is revealed when you need nesting scopes -- there is, apparently, no way to define an Element_Type to feed to Indefinite_Ordered_Maps which is an instance of Indefinite_Ordered_Maps.Maps or an instance of Variable_Data (by way of a variant record; even one which is forward declared).

What would be the proper way to handle this sort of situation?

Re: Interesting containers problem.

[Peter Chapin]

On Fri, 17 Apr 2015, Shark8 wrote:

> Ok, so let's say we have a type for Identifiers:

[snip]

> And that's all well and good; however, there is one limitation here that 
> is revealed when you need nesting scopes -- there is, apparently, no way 
> to define an Element_Type to feed to Indefinite_Ordered_Maps which is an 
> instance of Indefinite_Ordered_Maps.Maps or an instance of Variable_Data 
> (by way of a variant record; even one which is forward declared).
>
> What would be the proper way to handle this sort of situation?

Perhaps using access types directly? What if the Element_Type of the Map 
is an access type that points at an incomplete type, where the completion 
follows the instantiation of the Maps generic?

Peter

Re: Interesting containers problem.

[Randy Brukardt]

"Peter Chapin" <PChapin@vtc.vsc.edu> wrote in message 
news:alpine.CYG.2.11.1504171506500.2268@WIL414CHAPIN.vtc.vsc.edu...
> On Fri, 17 Apr 2015, Shark8 wrote:
>
>> Ok, so let's say we have a type for Identifiers:
>
> [snip]
>
>> And that's all well and good; however, there is one limitation here that 
>> is revealed when you need nesting scopes -- there is, apparently, no way 
>> to define an Element_Type to feed to Indefinite_Ordered_Maps which is an 
>> instance of Indefinite_Ordered_Maps.Maps or an instance of Variable_Data 
>> (by way of a variant record; even one which is forward declared).
>>
>> What would be the proper way to handle this sort of situation?
>
> Perhaps using access types directly? What if the Element_Type of the Map 
> is an access type that points at an incomplete type, where the completion 
> follows the instantiation of the Maps generic?

Bleech. Using access types means that you have to handle the memory 
management, defeating the #1 value of the containers. Typically, you can use 
cursors as references between related containers, and I think that is 
preferable.

To answer the OPs question, a symbol table for a language like Ada is a 
multiway tree. That's one reason I pushed for a multiway tree container in 
Ada, as it seems to be a common data structure. So I'd use a multiway tree 
as the basic structure. Identifier lookups would use a map (as you noted), 
and the things that each identifier points at is a list of the symbol table 
nodes associated with that identifier. So the lookup data is a map of lists 
of tree cursors. Hiding then is dealt with by checking the relationship of 
the nodes, or possibly by maintaining a visibility flag in the symbol 
records.

Note that for Ada, one does not prune the lists of identifiers immediately; 
that's the job of the resolver mechanism (because of homographs). The above 
is essentially how Janus/Ada deals with the symboltable (using access types 
since there were no containers in 1981!). Dealing with hiding isn't pretty 
and I don't think there is any way to make it pretty. Perhaps there is 
something elegant that can be done for a simpler language, but since there 
is only one language that matters, who cares? ;-)

                                           Randy.

Re: Interesting containers problem.

[Dmitry A. Kazakov]

On Fri, 17 Apr 2015 15:45:05 -0500, Randy Brukardt wrote:

> "Peter Chapin" <PChapin@vtc.vsc.edu> wrote in message 
> news:alpine.CYG.2.11.1504171506500.2268@WIL414CHAPIN.vtc.vsc.edu...
>> On Fri, 17 Apr 2015, Shark8 wrote:
>>
>>> And that's all well and good; however, there is one limitation here that 
>>> is revealed when you need nesting scopes -- there is, apparently, no way 
>>> to define an Element_Type to feed to Indefinite_Ordered_Maps which is an 
>>> instance of Indefinite_Ordered_Maps.Maps or an instance of Variable_Data 
>>> (by way of a variant record; even one which is forward declared).
>>>
>>> What would be the proper way to handle this sort of situation?
>>
>> Perhaps using access types directly? What if the Element_Type of the Map 
>> is an access type that points at an incomplete type, where the completion 
>> follows the instantiation of the Maps generic?
> 
> Bleech. Using access types means that you have to handle the memory 
> management, defeating the #1 value of the containers.

Except that in Ada we cannot access container elements for update without
access types or other helper types. Nastiness of the later raises
exponentially with every bit of safety added in order to prevent the mess
of the former.

> To answer the OPs question, a symbol table for a language like Ada is a 
> multiway tree. That's one reason I pushed for a multiway tree container in 
> Ada, as it seems to be a common data structure. So I'd use a multiway tree 
> as the basic structure. Identifier lookups would use a map (as you noted), 
> and the things that each identifier points at is a list of the symbol table 
> nodes associated with that identifier. So the lookup data is a map of lists 
> of tree cursors. Hiding then is dealt with by checking the relationship of 
> the nodes, or possibly by maintaining a visibility flag in the symbol 
> records.

Looks complicated and inefficient to me. The structure should support group
insertion or removal of submaps (e.g. a scope) into the current map.

> Note that for Ada, one does not prune the lists of identifiers immediately; 
> that's the job of the resolver mechanism (because of homographs). The above 
> is essentially how Janus/Ada deals with the symboltable (using access types 
> since there were no containers in 1981!). Dealing with hiding isn't pretty 
> and I don't think there is any way to make it pretty. Perhaps there is 
> something elegant that can be done for a simpler language, but since there 
> is only one language that matters, who cares? ;-)

and dealing with suggestions and listing conflicting variants should be
even less prettier...

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Interesting containers problem.

[Shark8]

On Friday, April 17, 2015 at 2:45:07 PM UTC-6, Randy Brukardt wrote:
> "Peter Chapin" wrote in message 
> > On Fri, 17 Apr 2015, Shark8 wrote:
> >
> >> Ok, so let's say we have a type for Identifiers:
> >
> > [snip]
> >
> >> And that's all well and good; however, there is one limitation here that 
> >> is revealed when you need nesting scopes -- there is, apparently, no way 
> >> to define an Element_Type to feed to Indefinite_Ordered_Maps which is an 
> >> instance of Indefinite_Ordered_Maps.Maps or an instance of Variable_Data 
> >> (by way of a variant record; even one which is forward declared).
> >>
> >> What would be the proper way to handle this sort of situation?
> >
> > Perhaps using access types directly? What if the Element_Type of the Map 
> > is an access type that points at an incomplete type, where the completion 
> > follows the instantiation of the Maps generic?
> 
> Bleech. Using access types means that you have to handle the memory 
> management, defeating the #1 value of the containers. Typically, you can use 
> cursors as references between related containers, and I think that is 
> preferable.
> 
> To answer the OPs question, a symbol table for a language like Ada is a 
> multiway tree. That's one reason I pushed for a multiway tree container in 
> Ada, as it seems to be a common data structure. So I'd use a multiway tree 
> as the basic structure. Identifier lookups would use a map (as you noted), 
> and the things that each identifier points at is a list of the symbol table 
> nodes associated with that identifier. So the lookup data is a map of lists 
> of tree cursors. Hiding then is dealt with by checking the relationship of 
> the nodes, or possibly by maintaining a visibility flag in the symbol 
> records.

Ok, I see how a multiway tree maps the structure of nesting scopes... but maybe I'm being obtuse here, because I don't see how to access them because there's no 'key' type. (Maybe a bit of code would help here.)

The way I see it is that the structure we want is essentially a map where an identifier is keyed to one of two things: (a) a variable_data, or (b) another scope-map. -- This would allow/model nesting.

Re: Interesting containers problem.

[brbarkstrom]

On Saturday, April 18, 2015 at 1:21:59 PM UTC-4, Shark8 wrote:
> On Friday, April 17, 2015 at 2:45:07 PM UTC-6, Randy Brukardt wrote:
> > "Peter Chapin" wrote in message 
> > > On Fri, 17 Apr 2015, Shark8 wrote:
> > >
> > >> Ok, so let's say we have a type for Identifiers:
> > >
> > > [snip]
> > >
> > >> And that's all well and good; however, there is one limitation here that 
> > >> is revealed when you need nesting scopes -- there is, apparently, no way 
> > >> to define an Element_Type to feed to Indefinite_Ordered_Maps which is an 
> > >> instance of Indefinite_Ordered_Maps.Maps or an instance of Variable_Data 
> > >> (by way of a variant record; even one which is forward declared).
> > >>
> > >> What would be the proper way to handle this sort of situation?
> > >
> > > Perhaps using access types directly? What if the Element_Type of the Map 
> > > is an access type that points at an incomplete type, where the completion 
> > > follows the instantiation of the Maps generic?
> > 
> > Bleech. Using access types means that you have to handle the memory 
> > management, defeating the #1 value of the containers. Typically, you can use 
> > cursors as references between related containers, and I think that is 
> > preferable.
> > 
> > To answer the OPs question, a symbol table for a language like Ada is a 
> > multiway tree. That's one reason I pushed for a multiway tree container in 
> > Ada, as it seems to be a common data structure. So I'd use a multiway tree 
> > as the basic structure. Identifier lookups would use a map (as you noted), 
> > and the things that each identifier points at is a list of the symbol table 
> > nodes associated with that identifier. So the lookup data is a map of lists 
> > of tree cursors. Hiding then is dealt with by checking the relationship of 
> > the nodes, or possibly by maintaining a visibility flag in the symbol 
> > records.
> 
> Ok, I see how a multiway tree maps the structure of nesting scopes... but maybe I'm being obtuse here, because I don't see how to access them because there's no 'key' type. (Maybe a bit of code would help here.)
> 
> The way I see it is that the structure we want is essentially a map where an identifier is keyed to one of two things: (a) a variable_data, or (b) another scope-map. -- This would allow/model nesting.

Maybe you could use an index (i.e. NDX : Natural) as a key to each container.
Everytime you add a model, you add an index.  You could think of the nodes
in the tree as members of an adjacency list.  See also Knuth's discussion
of Triply-Linked Trees in his Art of Computer Programming.  Those would handle
your multiway trees, I believe.

Bruce b.

Re: Interesting containers problem.

[Randy Brukardt]

"Shark8" <onewingedshark@gmail.com> wrote in message 
news:ced95bb5-0bb3-43ee-8d2c-212ea020fd10@googlegroups.com...
> On Friday, April 17, 2015 at 2:45:07 PM UTC-6, Randy Brukardt wrote:
...
> Ok, I see how a multiway tree maps the structure of nesting scopes... but 
> maybe I'm
>being obtuse here, because I don't see how to access them because there's 
>no 'key'
>type. (Maybe a bit of code would help here.)

The keys are into a map of which each element is a list of tree nodes (that 
is, tree cursors) that have the given identifier. Thus, you have:

    package Symbol_Tree is new Ada.Containers.Indefinite_Multiway_Trees 
(Element_Type => Symbol_Root'Class);

    package Symbol_List is new Ada.Containers.Doubly_Linked_Lists 
(Element_Type => Symbol_Tree.Cursor);

    package Identifier_Map is new Ada.Containers.Indefinite_Hashed_Map 
(Element_Type => Symbol_List.List,
         Key_Type => String, -- Probably really a UTF8_String,
         Hash => ..., Equivalent_Keys => ...);

  I'm too lazy to look up the proper names of the routines to use for the 
Hash function and the case insensitive equivalency; it's not relevant to the 
routine anyway.

> The way I see it is that the structure we want is essentially a map where 
> an identifier
>is keyed to one of two things: (a) a variable_data, or (b) another 
>scope-map. -- This
>would allow/model nesting.

But that doesn't help much (for Ada). In any case, you start with the entire 
list of declarations with the appropriate identifier and prune out 
inappropriate kinds of declarations (wrong scope, etc.). The problem is that 
declarations such as overloaded subprograms don't hide each other unless 
they're homographs (that is, have the same profile). The identifier alone 
doesn't tell you much; you have to collect all of the declarations that 
might be visible.

What you are talking about would help in an antique language that doesn't 
support any overloading, but I would hope that people in this group are 
beyond that. :-) If anything, Ada doesn't have enough overloading (too much 
reliance on scopes, something that should have almost no bearing on 
visibility).

Keep in mind that there are many possible queries into a symboltable, and 
it's never going to be viable to make it easy for all of them. For Ada, you 
need to look up by identifier, by visibility, by primitive for a given type, 
and so on. It's not sensible to make it easy to do all of those things.

                                                          Randy.

Re: Interesting containers problem.

[Randy Brukardt]

I wrote:

...
> What you are talking about would help in an antique language that doesn't 
> support any overloading, but I would hope that people in this group are 
> beyond that. :-) If anything, Ada doesn't have enough overloading (too 
> much reliance on scopes, something that should have almost no bearing on 
> visibility).

It strikes me that there is an easy way to use the containers for a purely 
scoped language without any overloading. There's some overhead with scope 
exit (but that seems necessary in any case). The basic idea is to use 
cursors to link nested items together, and have the map point at the 
currently visible item:

   package Symbol_Tree is new Ada.Containers.Indefinite_Multiway_Trees
       (Element_Type => Symbol_Root'Class);

   package Identifier_Map is new Ada.Containers.Indefinite_Hashed_Map
        (Element_Type => Symbol_Tree.Cursor,
         Key_Type => String, -- Probably really a UTF8_String,
         Hash => ..., Equivalent_Keys => ...);

For this to work, each item in Symbol_Root'Class needs a 
Previous_Declaration component that also has type Symbol_Tree.Cursor. That 
points at the previous item (if any) that was visible before the current 
one.

A new declaration updates the map to point at itself in the symbol table, 
but not before squirreling the previous item (if any) into 
Previous_Declaration. When a declaration goes out of scope, the map has to 
be updated to put again at the Previous_Declaration (if any). This is 
essentially the same way one would write such a symbol table with access 
types.

Such a pure scheme doesn't work for module visibility (i.e. use clauses in 
Ada), because there can be multiple items visible at once that way. But I 
suppose that a very simple language might make it work (no overloading, no 
modules or at least only dot notation for modules). Janus/Ada worked that 
way initially (when doing the Pascal subset), but that didn't last long for 
obvious reasons.

                                   Randy.

Re: Interesting containers problem.

[Dmitry A. Kazakov]

On Mon, 20 Apr 2015 18:39:54 -0500, Randy Brukardt wrote:

> What you are talking about would help in an antique language that doesn't 
> support any overloading, but I would hope that people in this group are 
> beyond that. :-)

We could introduce "checked use" as compared the "unchecked" one Ada has.
The difference would be that if "use P" would hide anything in the scope
the language would require explicit renaming. E.g.

package P is
   X : Integer;
end P;

package Q is
   X : Integer;
end Q;

not overriding use P, Q; -- Illegal
package R is
   ...
end R;

not overriding use P, Q with Y renames Q.X; -- That's OK
package R is
   -- X means P.X
   -- Y means Q.X
   ...
end R;

The same keyword could be used with the keywords introducing a declaration
scope (e.g. "declare") to ensure that any declarations in that scope hiding
anything will be rejected.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Interesting containers problem.

[J-P. Rosen]

Le 21/04/2015 10:06, Dmitry A. Kazakov a écrit :
> We could introduce "checked use" as compared the "unchecked" one Ada has.
> The difference would be that if "use P" would hide anything in the scope
> the language would require explicit renaming. E.g.
???
Use never hides anything, if something is directly visible, it stays so
even in the presence of use clauses.

In your example, there is "mutual hiding", which is a way of saying that
neither declaration is directly visible (and therefore no risk of
confusion). You are free to add renamings if you want to make something
directly visible.

So, I don't see what your syntax would bring.

-- 
J-P. Rosen
Adalog
2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX
Tel: +33 1 45 29 21 52, Fax: +33 1 45 29 25 00
http://www.adalog.fr

Re: Interesting containers problem.

[Dmitry A. Kazakov]

On Tue, 21 Apr 2015 10:28:32 +0200, J-P. Rosen wrote:

> Le 21/04/2015 10:06, Dmitry A. Kazakov a écrit :
>> We could introduce "checked use" as compared the "unchecked" one Ada has.
>> The difference would be that if "use P" would hide anything in the scope
>> the language would require explicit renaming. E.g.
> ???
> Use never hides anything, if something is directly visible, it stays so
> even in the presence of use clauses.

Yes, but the distinction is irrelevant for practical use. The name cannot
be used for whatever reason.

> In your example, there is "mutual hiding", which is a way of saying that
> neither declaration is directly visible (and therefore no risk of
> confusion). You are free to add renamings if you want to make something
> directly visible.
> 
> So, I don't see what your syntax would bring.

It would warns early about the problem, which is very difficult to tack
later, especially with generic instantiations.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de