* Interesting containers problem.
@ 2015-04-17 13:42 Shark8
2015-04-17 19:12 ` Peter Chapin
0 siblings, 1 reply; 11+ messages in thread
From: Shark8 @ 2015-04-17 13:42 UTC (permalink / raw)
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?
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Interesting containers problem.
2015-04-17 13:42 Interesting containers problem Shark8
@ 2015-04-17 19:12 ` Peter Chapin
2015-04-17 20:45 ` Randy Brukardt
0 siblings, 1 reply; 11+ messages in thread
From: Peter Chapin @ 2015-04-17 19:12 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Interesting containers problem.
2015-04-17 19:12 ` Peter Chapin
@ 2015-04-17 20:45 ` Randy Brukardt
2015-04-17 21:06 ` Dmitry A. Kazakov
2015-04-18 17:21 ` Shark8
0 siblings, 2 replies; 11+ messages in thread
From: Randy Brukardt @ 2015-04-17 20:45 UTC (permalink / raw)
"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.
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Interesting containers problem.
2015-04-17 20:45 ` Randy Brukardt
@ 2015-04-17 21:06 ` Dmitry A. Kazakov
2015-04-18 17:21 ` Shark8
1 sibling, 0 replies; 11+ messages in thread
From: Dmitry A. Kazakov @ 2015-04-17 21:06 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Interesting containers problem.
2015-04-17 20:45 ` Randy Brukardt
2015-04-17 21:06 ` Dmitry A. Kazakov
@ 2015-04-18 17:21 ` Shark8
2015-04-19 17:10 ` brbarkstrom
2015-04-20 23:39 ` Randy Brukardt
1 sibling, 2 replies; 11+ messages in thread
From: Shark8 @ 2015-04-18 17:21 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Interesting containers problem.
2015-04-18 17:21 ` Shark8
@ 2015-04-19 17:10 ` brbarkstrom
2015-04-20 23:39 ` Randy Brukardt
1 sibling, 0 replies; 11+ messages in thread
From: brbarkstrom @ 2015-04-19 17:10 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Interesting containers problem.
2015-04-18 17:21 ` Shark8
2015-04-19 17:10 ` brbarkstrom
@ 2015-04-20 23:39 ` Randy Brukardt
2015-04-21 3:05 ` Randy Brukardt
2015-04-21 8:06 ` Dmitry A. Kazakov
1 sibling, 2 replies; 11+ messages in thread
From: Randy Brukardt @ 2015-04-20 23:39 UTC (permalink / raw)
"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.
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Interesting containers problem.
2015-04-20 23:39 ` Randy Brukardt
@ 2015-04-21 3:05 ` Randy Brukardt
2015-04-21 8:06 ` Dmitry A. Kazakov
1 sibling, 0 replies; 11+ messages in thread
From: Randy Brukardt @ 2015-04-21 3:05 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Interesting containers problem.
2015-04-20 23:39 ` Randy Brukardt
2015-04-21 3:05 ` Randy Brukardt
@ 2015-04-21 8:06 ` Dmitry A. Kazakov
2015-04-21 8:28 ` J-P. Rosen
1 sibling, 1 reply; 11+ messages in thread
From: Dmitry A. Kazakov @ 2015-04-21 8:06 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Interesting containers problem.
2015-04-21 8:06 ` Dmitry A. Kazakov
@ 2015-04-21 8:28 ` J-P. Rosen
2015-04-21 8:45 ` Dmitry A. Kazakov
0 siblings, 1 reply; 11+ messages in thread
From: J-P. Rosen @ 2015-04-21 8:28 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Interesting containers problem.
2015-04-21 8:28 ` J-P. Rosen
@ 2015-04-21 8:45 ` Dmitry A. Kazakov
0 siblings, 0 replies; 11+ messages in thread
From: Dmitry A. Kazakov @ 2015-04-21 8:45 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2015-04-21 8:45 UTC | newest]
Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-04-17 13:42 Interesting containers problem Shark8
2015-04-17 19:12 ` Peter Chapin
2015-04-17 20:45 ` Randy Brukardt
2015-04-17 21:06 ` Dmitry A. Kazakov
2015-04-18 17:21 ` Shark8
2015-04-19 17:10 ` brbarkstrom
2015-04-20 23:39 ` Randy Brukardt
2015-04-21 3:05 ` Randy Brukardt
2015-04-21 8:06 ` Dmitry A. Kazakov
2015-04-21 8:28 ` J-P. Rosen
2015-04-21 8:45 ` Dmitry A. Kazakov
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox