PoolResolution

A new GST variable compilation order and extension interface

Traditionally, in GST, variables are resolved by a formula built by extension over years, for backward compatibility and maintenance of autobiographical separation. TwistedPools is a new, intermixed variable search order, designed to be more intuitive and fit separation of concepts in running images, rather than in a historical context.

Existing search order

Based on STInST.STSymTable, and what I recall from my foray into the libgst resolver, here is the search order for non-instance variables:

  1. Class methods use same resolution as instance, so for all following, always look at the plain class.
  2. Add the class's namespace, including all containing namespaces.
  3. Add the class's class pool (classVariableNames).
  4. Repeat the above two for each superclass in turn, up to nil.
  5. Add the class's shared pools, including all containing namespaces, besides the class pool.
  6. Repeat the above one for each superclass in turn, up to nil.

Expectations

How does the above violate expectations? Here are some simple examples.

Namespace current: MyLibrary [

Eval [
    MyLibrary at: #StandardOverrides put:
        (BindingDictionary from: {#Scape -> nil})
]

Object subclass: Foo [
    Exception := nil.
    Scape := nil.

    exception [
        "I expect to answer the above classvar, but instead answer
         Smalltalk.Exception."
        ^Exception
    ]
]

Foo subclass: Bar [
    <import: StandardOverrides>

    scape [
        "I expect to answer the StandardOverrides Scape, but instead
         answer Foo classPool at: #Scape."
        ^Scape
    ]
]

] "end namespace MyLibrary"

Namespace current: MyProject.MyLibWrapper [

Eval [
    "note this changes my superspace"
    MyProject at: #Exception put: Smalltalk.Exception
]

MyLibrary.Foo subclass: Baz [
    exception [
        "After trivial reordering for pools-first, I expect to answer
         MyProject.Exception, but instead answer
          Foo classPool at: #Exception."
         ^Exception
    ]
]

] "end namespace MyProject.MyLibWrapper"

Finding a new search order

The idea of twisting the class-pool and shared-pool resolution together is trivial. The real difficulty comes from the definitions in MyProject.MyLibWrapper. Were they to appear in the MyLibrary namespace instead, the pools-first behavior would make more sense. However, since Baz is not in the same namespace as Foo, it deserves a different outcome.

As such, no simple series of walks up the inheritance tree paired with pool-adds will give us a good search order.

Our goal in the design of PoolResolution's default resolver is to maintain a sense of containment within namespaces, while still allowing reference to all inherited environments, as is traditionally expected.

Variable search fundamentals

This is the essential variable search algorithm for TwistedPools.

  1. Given a class, starting with the method-owning class:
  2. Search the class pool.
  3. Search this class's shared pools, combined using IPCA, left-to-right, removing any resulting pools that are any of this class's namespace or superspaces.
  4. Search this class's namespace and each superspace in turn before first encounter of a namespace that contains, directly or indirectly, the superclass. This means that if the superclass is in the same namespace or a subspace, no namespaces are searched.
  5. Move to the superclass, and repeat from #2.

This is IPCA, the inheritable pool combination algorithm.

  1. Start a new list.
  2. From right to left, descend into each given pool not marked #visited.
  3. Recurse into #2 for each superspace.
  4. Mark this pool as #visited, and add to the beginning of #1's new list.
  5. After all recursions exit, return the new list.

Obviously, this is a topological sort, and is explicitly modeled after CLOS class precedence.

Combination details

While the add-namespaces step above could be less eager to add namespaces, by allowing any superclass to stop the namespace crawl, rather than just the direct superclasses, it is already less eager than the shared pool manager. The topological sort is an obviously good choice, but why not allow superclasses' namespaces to provide deletions as well as the pool-containing class? While both alternatives have benefits, I believe that an eager import of all superspaces, besides those that already contain the pool-containing class, would most closely match what's expected.

An argument could also be made that by adding a namespace to shared pools, you expect all superspaces to be included. However, consider the usual case of namespaces in shared pools: imports. While you would want it to completely load an alternate namespace hierarchy, I think you would not want it to inject Smalltalk early into the variable search. Consider this diagram:

         Smalltalk
             |
         MyCompany
          /      \
         /        \
    MyProject     MyLibrary
       /            /    \
      /           ModA   ModB
MyLibModule

If you were to use ModB as a pool in a class in MyLibModule, I think it is most reasonable that ModB and MyLibrary be immediately imported, but MyCompany and Smalltalk wait until you reach that point in the namespace walk.

Another argument could be made to delay further the namespace walk, waiting to resolve until no superclass is contained in a given namespace, based on the idea of exiting a namespace hierarchy while walking superclasses, then reentering it. Disregarding the unlikelihood of such an organization, I still think it would be less confusing to resolve the hierarchy being left first, in case the interloping hierarchy introduces conflicting symbols of its own.

You may note my lack of objective argument regarding the above points of contention. That is because I don't have a formal proof. Convenient global name resolution is entirely a matter of feeling, because a formal programmer could always explicitly spell out the path to every variable.

Integrating namespace pools

I have an idea to add shared pools to namespaces, thereby allowing users to import external namespaces for every class in a namespace, rather than each class. If this is integrated, it would need to twist nicely.

Here is how I think it would best work: after searching any namespace, combine its shared pools using IPCA, removing all elements that are any of this namespace or its superspaces, and search the combination from left to right.

Sample implementation

PoolResolution is implemented in a git branch called pool-resolution in Stephen and Paolo's private repositories, for the STInST compiler only. In Paolo's version it also applies to bindings unresolved at compile time, but not to code parsed directly from the REPL.

Besides the PoolResolution hierarchy and changes to STSymTable, there are two important protocol items of note:

  • PoolResolution>>current, a property defining the current resolution class; allows to switch the STInST compiler between the two resolution strategies.
  • Behavior>>#allSharedPoolDeclarationsDo:, which implements the TwistedPools algorithms.
Syndicate content

User login