* 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