From: brbarkstrom@gmail.com
Subject: Re: Interesting containers problem.
Date: Sun, 19 Apr 2015 10:10:51 -0700 (PDT)
Date: 2015-04-19T10:10:51-07:00 [thread overview]
Message-ID: <95445200-8367-4c2e-a37c-611fbe3c2f7f@googlegroups.com> (raw)
In-Reply-To: <ced95bb5-0bb3-43ee-8d2c-212ea020fd10@googlegroups.com>
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.
next prev parent reply other threads:[~2015-04-19 17:10 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
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 [this message]
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
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox