Imagine you’re attending a presentation about a new topic in the financial market, Ramifications to the Individual Investor of Holding Derivative-based Warrants during Corporate Mergers. The speaker is an expert in the field; you’re not much more than a novice. The subject is presented in a straightforward way, and though you get the gist of what’s being said, on some points the material is beyond your comprehension. So, interested but bewildered, you jot down a few notes to look up later. Over the next few days you google for a bit, discover some information that clarifies things, and bit-by-bit everything starts making sense.
Formally, the gaps that you experienced are called forward references, references to information that does not yet exist in your perspective. Some of the things that were being told to you could not yet be integrated into your thought processes because you were missing information vital to their understanding. What you did by looking up new information was to resolve these forward references so they could be successfully integrated into what you know. Only when you established the additional information were you able properly interpret what had been said.
Forward referencing is one of the basic constraints of programming: you can’t use an object before it is defined. Part of the art of programming, and indeed creating any mechanical procedure to solve a problem, is avoiding forward references. When you don’t, your program may try to access something that isn’t known at the current point in its execution and it can’t go on. Programs that encounter this situation usually fail, either crashing or returning an unsatisfying result to their users. Of course this only make sense: how can a system use something that isn’t there?
But what if instead of failing, the program could be designed to wait until it had more information at it’s disposal and try again, just as you did after the lecture: achieving understanding by integrating new information and resolving the unknowns?
The Natural State
While forward referencing may be a difficult problem in programming, it’s something we all do quite naturally do every day as humans. At birth, life is nothing but a mystery to be decoded; everything starts out with forward reference - gaps and meta-gaps abound. The drive to survive in such a world teaches us to reach out with our senses, to discover, communicate, learn and try to reason with all of the unknowns we face. Fortunately, minor mistakes are tolerated and help to teach us; we become experts at learning to understand. It’s survival of the fittest: we stay alive by learning how to correctly fill in the gaps and by avoiding the bad mistakes that can kill us.
Software, on the other hand, is not natural. While it may spring forth from the fingers of life-experienced programmers, it leads a sheltered existence, the data it digests being pre-chewed and carefully spoon-fed to it. Deviation from the expected causes errors, from minor hiccups to fatal crashes. We patch and enhance software to deal with its shortcomings, and eventually we bury it and do a rewrite. Only the most painstakingly crafted software ages well, and then only in very restricted domains.
Forward referencing is just one of the many kinds of trouble in a programmer’s world - unless software is specifically designed to handle it by developers who have understood and anticipated the need, problems are intrinsic.
Simple Forward Referencing
Let us start by creating a program that can resolve simple forward references. We’ll read a set of lines that contain a two strings: the first is data, and the other is a link to the data on another line. What we want to do is create a structure from these lines that represents a chain from the line who’s data is ‘start’ through all the other lines.
The data file we’ll work with contains:
It’s pretty apparent what we want to end up with, but for some reason the lines were sorted into alphabetical order by some other system. Our task is to untangle the mess, but to do it generically so that the lines in any input file that looks like this can be chained in this fashion.
There are lots of ways to write the code to build our chained structure, but we want to it done in a way that illustrates the concept of forward reference resolution. A little Ruby program will do nicely.
Though this is obviously the long way around a simple problem, we’ll ignore that.
The code is made up of two classes,
LineLink (lines 3-13) and
LineChain (lines 15-38).
We start by creating a new LineChain with the file lines.txt (line 47).
load method (lines 18-37) creates two objects, an array we’ll use to hold unresolved links, and a hash we’ll use to hold the
linelinks we create.
We create a new
LineLink object from the two words on each line of the file (lines 21-30).
A LineLink is initialized (lines 6-8) added to the chain (line 24), and then dereferenced (lines 25-29).
Dereferencing is what we use in this example to find our forward references.
LineLink we want to link to has already been created (line 25) then we establish the link (line 26); otherwise, we add it to the list of unresolved forward references (line 28).
Once we’ve loaded the lines (for the purposes of this example, we assume that all the lines are present) we resolve the unresolved forward references (lines 33-35): for each unresolved LineLink (line 33), set its link to the LineLink its link references (line 34).
There are a few puts in the code to show the dereferencing that happened during loading and the resolution of forward references afterward:
Though this code is not very robust, it does illustrate the forward reference process:
As each object is loaded it is processed as far as possible; if the processing hits a snag, we have a forward reference.
At a suitable point in the processing, these forward references are resolved.
We now have the foundation for a more robust model in hand.
The simplifying assumptions that we made should be removed to create a real-world facility - we can hardly expect such a sanitized situation in what we’ll actually encounter in everyday use.
We knew that all the required data would be arriving by the time we were ready for it. When we resolved the forward references that were accumulated (lines 33-35), all that we did was run through them once. We assumed no additional data was coming in and that we could resolve each link successfully.
Many applications can neither predict when information will arrive nor what meaning it may have. This implies that there may be many different types of resolution required. What’s more, resolution may need to occur whenever new information arrives, many times instead of just once at the end; we’ll usually have to leave forward references that are still unresolved for another try later. A more robust system will need to be able to handle integration often and easily - but not necessarily effortlessly. Forward reference resolution must still be carefully planned.
We only considered data. This simple program reads lines from a file, but forward reference doesn’t just occur in data. We could have just as easily encountered forward reference by calling methods that did not yet exist - or that depended on other data that had not yet arrived.
Processing can contain forward references quite naturally. For instance, in Ruby a Domain Specific Language (DSL) expresses information in code itself; instead of being read as a data file, it is evaluated like any other code - part of the Ruby interpretation process. A DSL is a more “humane” approach to definition (through active processing, not just passive declaration) allowing people with experience in that domain to easily codify knowledge. The good programming practices that developers know to follow - such as avoiding forward reference - may not be important to an expert non-programmer using a DSL. A more robust system must be able to handle forward referencing in both data and processing.
We knew we could find forward references by inspecting data, rather than through raised exceptions. We only had to make a simple decision (line 25) to determine whether or not we had a forward reference. It is more likely that this situation will not be decidable by inspection, especially when we take processing into account. We may be deep into the execution of a program when we try to access information that is not (or is not completely) defined; to have anticipated all of the possible dependencies on all of the information that might be required to make an decision a priori is impractical.
While inspection works in some situations, it’s often more productive to identify forward reference by gracefully catching a failed usage than by performing validation. Validation ahead of use only works when you cover every possibility - it’s always the one you miss that gets you. Of course, sometimes testing conditions can lead to improved performance, and judicious use of validation is useful and warranted, but this can often only be determined once a system is in place and is being enhanced. Most of the time we cannot predict where to make improvements until their need has been identified - long after a system is in production. A more robust system should allow for the possibility of failure due to forward referencing, and provide the opportunity to recover from those failures once new information has been integrated.
The task then is to build forward referencing as a facility that can work for both code and data, allows us to capture attempted use before declaration, and lets us try to resolve forward references on-demand.
The Co-resolution Problem
The problem that cannot yet be overcome is co-resolution. Co-resolution occurs when neither A nor B can be defined without reference to the other: when they both must be resolved together to be resolved at all. Circular reasoning and logic stemming from it is the generally the cause of this sort of trouble.
This problem is just as prevalent in human cognition as it is potentially in computer-based systems. Sometimes the resolution and integration of information is too complex for processors, computer or human. It may require order-of-magnitude leaps in understanding to solve complex co-resolution problems. Systems without careful coding to recognize co-resolution can end up with pathologic problems including such runtime horrors as exceeding stack depth or infinite loops.
People tend to overcome such problems by building and using definitions incrementally and co-resolving the simpler incremental references, by redefining the dependencies so there is no circularity, or even by just ignoring them. While we could try to mimic human approaches to beating co-resolution, we’ll avoid tackling the issue in this discussion. For now, know that this problem is there and can typically only be prevented if it can be identified - a difficult problem to treat generally. Instead, we need to be able to live with unresolved forward references in our systems and to be able to try to resolve them periodically. The system mustn’t fail unreasonably - it should just fail to compute results when unreasonable requests have been made.
A General Forward Referencing Handler
Generalizing our simple example and factoring in robustness, there are two abstractions we’ll need: a
ForwardReference and a
ForwardReference will indicate where a forward reference was encountered, and the
ForwardReferencer will be used to manage its capture and resolution.
Going a step further, consider that the forward reference manager should be able to be an integral part of any object that wants to handle forward referencing.
ForwardReference is a class of objects, the functionality of the
ForwardReferencer should be able to be mixed into other classes.
So we’ll generalize this capability into a ForwardReferencing module, and we’ll realize ForwardReferencer as a simple class wrapper for ForwardReferencing to be used by classes that would rather be a ForwardReferencer than have ForwardReferencing ability.
The understands method used here is just an alias for Module’s include method, a personal modification to promote readability. It’s perfectly compatible with core Ruby, so don’t fret. In a language with such capabilities, small enhancements such as this can make picking up code that I wrote long ago much easier to become familiar with again.
So, this is our basic skeleton. Now we’re ready to put some meat on these bones.
ForwardReference is basically a placeholder - a place that processing may return to if it is preempted for some reason.
It needs to know where it occurred so resolution can proceed appropriately, and why it got there to allow
ForwardReferencing to make decisions about when to try to resolve it.
There is no formula for deciding the content of the why - it should be general purpose.
Any object that
ForwardReferencing can use should be able to be a dependency.
The where portion, however is more specific.
The executing program needs to return to the spot where the
ForwardReference was created to try to resolve it.
Fortunately, Ruby has a class to do this that is available through the
Kernel object: the
A Continuation is basically a snapshot of a program’s execution that can be restarted at a future time - it doesn’t have to ever be restarted, but it can be.
Profound technical details aside, what this will allow us to do is to start something, switch to do something else, and then switch back to what we’d originally started.
With it, we can build control structures that transcend the local control structures within individual methods.
For our purposes, when we create a new
ForwardReference, it creates a
Continuation at that point and goes on.
At some point downstream in processing, we’ll be able to jump back to the spot at which the object’s
continuation was created.
The initialize method creates a
continuation, and then assigns the dependency.
There’s not really anything interesting in this code on except the strange looking assignment to
Here’s what’s going on…
Imagine we’re deep into some code and create a
ForwardReference, which in turn creates a
Continuation, right here.
continuation is called, execution will pick up again, right here.
The problem is that at the time we call it, we don’t know whether or not the forward reference will be resolvable or not - remember, we’re not necessarily going to try to inspect the situation to determine what must be done, we’ll just attempt to resolve the forward reference again.
So, if we can’t resolve it, we’ll want to try again later, from right here.
However when we call the
continuation, we get back a
nil - we didn’t give
continuation any arguments when it was constructed, so we get nothing back.
And, of course, we couldn’t give
continuation itself as an argument, since it didn’t yet exist.
We need to create a new
Continuation that can pick up again right here so we can give it another try if resolution still fails.
That’s why we wrap the creation of the Continuation in a while loop - when we come back from calling it, it’s value is
nil so the while repeats and we generate a new
Continuation that is reassigned to the forward reference and can be called the next time around.
Note that the first time we enter into the code to generate the
ForwardReference, we force
nil - as a placebo.
nil of course, but it keeps the test framework from complaining.
By using this little loop around the assignment we’re assured to have a good, non-
We then assign the dependency, and we’ve got a valid
The strategy works first time, every time.
We’ll use another Continuation during the resolution process, but we’ll come to that shortly.
ForwardReferencing module is intended to be mixed into any class that wishes to handle forward reference capture and resolution.
The module collects
ForwardReference instances and removes those that get resolved.
Because modules can’t piggyback on the initialization of objects without explicit handling, the
start_forward_referencing method is provided to be called in the includer’s
The method sets up the initial state of the
ForwardReferening by making three assignments to instance variables: the first sets up an array of active forward references to hold the accumulated unresolved
ForwardReference instances that have been created, the second keeps a boolean to record whether any resolutions were made, and the third is a forward reference resolver that is used during resolution (it’s the other
Continuation - but again, more on that later).
The last two instance variables are only important during resolution.
Creating a forward reference is done by calling the
create_forward_reference method, passing in the dependency.
ForwardReference is created, added to the list of unresolved forward references, and returned.
ForwardReference is almost as simple as creating one.
We delete it from the list of unresolved forward references if it’s a
ForwardReference, and then we remember that something was resolved.
But why should we mark something as resolved if a
ForwardReference wasn’t passed in?
Because we’re not deciding absolutely how resolution might be accomplished.
If a resolution was made (indicated by calling this method) when we’re resolving, the resolution method will be run again; you’ll see where this is done in a moment.
The resolving mechanism in the includer may do something special and set it with this to help guide further resolutions or any subsequent processing requiring another chance to resolve.
ForwardReferencing module is used as a simple framework - the basis for a solution, not a solution itself.
Bottom line: we are providing a facility not dictating procedures, so if the caller relies on re-resolving immediately, the system will facilitate it.
You may have noticed by now that the method names in
ForwardReferencing are a bit verbose.
Why not just name the method
start instead of
create instead of
remove instead of
This isn’t because I’m being obsessive - it’s because we’re creating a
Module, not just a
A module can be included into any class; if we used simple short names, we’d almost certainly collide with other names that are already defined elsewhere in in the includer.
While Ruby lets you deal with these issues using
Module names, I’ve found that they’re harder to read than just spelling things out.
It all comes down to personal preference.
When reasonable, I prefer longer names to alleviate ambiguity over module name prefixing.
Of course, everybody would really rather have short names, me included.
We do this in the
ForwardReferencer class by including the
ForwardReferencing module and aliasing the longer names to shorter ones.
Since this is a class and not a module, we don’t need to worry about name collisions - we get to define the methods there, not in some other class with which we’re trying to maintain amicable relations.
We’ll do this shortly, but first we’ll finish describing
This method has a little more complexity. It runs through the list of unresolved forward references and tries to resolve each one into the system using information that may have been integrated since we last tried, as we re-accumulate the list of unresolved forward references in the process.
The first thing we do is swap the unresolved forward references into a local variable, clean out the unresolved forward references and assert that we’ve had no resolutions.
Next we loop over the unresolved forward references.
We use the local variable because our instance variable will now hold new accumulations.
The first step in the loop is to do our trick with
continuations again - making sure we have a good
Continuation to give us a valid place to jump back to after we attempt to resolve the forward reference being tried in this cycle of the loop.
We then shift the unresolved forward references to get the next
ForwardReference to attempt from the list and then call it’s
continuation to try to resolve it.
Hang on just a minute here, you say. There’s no loop in that code! Well, there is, but it’s part of the external control structures put in place with continuations. What we see here is the top of the loop. Lets quickly run through the bottom of the loop and then we’ll tie them together.
The bottom of the loop is trivial.
continuation exists, call it.
Now you can see what’s happening when the loop comes together.
When we start the loop, we create the
When a resolution happens (or not) the bottom of the loop is called and we jump back try the next
ForwardReference - until the shift in the top of the loop returns
nil because we’re at the end of the list.
Here comes the part that is critical!
The first time we run through the code, we’re finding our initial set of forward references.
When we start a section of code we assume we will have an unresolved forward reference and call
If we make it through the section successfully we call
remove_forward_reference to remove it from the list of unresolved forward references; if we weren’t successful, we leave it on the list by not making the call.
Then, pass-or-fail, we immediately call
Since we haven’t gone through the top of the loop,
nil and the call is a no-op; we go right into the next section of code, possibly accumulating more forward references.
At some time afterwards, we call
The top of the loop sets up the
forward_reference_resolver - and now the
continue_forward_reference_resolution method is no longer a no-op!
During resolution, we jump to the beginning of each section of code that did not have its initially-created forward reference removed.
We create the
ForwardReference again, and remove it from the list if we could resolve it this time.
But now, pass-or-fail, the call to
continue_forward_reference_resolution jumps back into the loop instead of continuing to the next code section.
The same code lets control flow in a straight line in one case and as a loop in another! This is exactly the cognitive behavior involved in forward reference resolution: once new information has been added, try to re-understand each thing that wasn’t understood the first time in the same context in which it was initially evaluated. After you’ve tried to resolve one forward reference, loop on to the next until everything has been given a chance. Then, if anything was resolved, we try resolution again since that may have been something that some other forward reference depended upon. If nothing was resolved when we run the loop, we stop - we’ll try again at some other time.
Understand that this mechanism can only resolve one forward reference in a cycle, not co-resolutions. We’re just not up to handling the Eureka moments in which multiple references get resolved at once. While that capability may be developed in the future, the dependency analysis needed is domain-specific and could only be done using a special facility, not our general one. For now it’s simply out of reach. This may seem limiting, but it captures many of the types of logical reasoning problems we encounter as humans, and will suffice for most of the forward referencing we’ll encounter in our programs.
To make life easy for the user of forward references, a few Ruby-friendly support methods are provided.
forward_reference_dependencies returns a hash of dependencies to arrays of unresolved
ForwardReferences with those dependencies.
Using this, an includer can carefully tailor the list of unresolved forward references to be tried during resolution, and merge the rest back in once we’re finished.
Carefully is the important word here - we must take great care to make sure we don’t accidentally lose any unresolved forward references.
But despite the risks, the capability is available.
The other calls are simply for returning the state of the forward referencing world.
These methods don’t add anything necessary to the functioning of the base mechanism, but they can be useful to developers.
forward_references_to_s method returns a string containing the number of remaining unresolved forward references, and
forward_references_remaining returns the number of remaining unresolved forward references.
to_s returns a string with information about its dependency and continuation.
self_name method being called in the string rendering methods.
This is a convenience method I wrote that returns the name of a class, the instance’s class name when called on an instance or the name of the class itself when called on a class.
I used it often because it frees me to work with classes and instances uniformly.
This is especially appropriate for
ForwardReferencing since it can be included or extended into a class.
As promised, a base class that provides
ForwardReferencing functionality is also provided.
This class is convenient to build upon, aliasing shorter names for the longer ones defined in the
Note that we don’t get rid of the longer names, but the shorter ones will help to make code more readable and are preferred since the context of the class is based purely on forward reference capture and resolution.
Simple Forward Referencing Revisted
With our solution for forward referencing in hand, we can now go back and factor it into our simple example.
The main change:
LineChain is now a
We no longer have to keep track of our unresolved forward references at the top level; it’s done for us below the surface by the
We also eliminated the resolution code because we get to reuse the chaining code by jumping back to it with the
The mechanism looks much simpler on the surface as well. We create a forward reference (line 26), remove it if it was resolved (line 29), continue the resolution (line 31) and resolve any unresolved forward references (line 35). Note again that the first time through continue is a no-op, but when resolve is being called, continue completes the bottom of the resolve-loop.
We made one other change - we now specifically test for the
This exclusion was actually an error in the original example, but just happened to work by coincidence because of how we were explicitly resolving our forward references.
Though the modified example is the same size as the original, the mechanics of the forward reference capture and resolution is all being done under the surface.
The real win is that this mechanism can handle both data and processing, and works with any forward reference processing. Disparate types of forward referencing problems can all be managed using the same mechanism, and the resolve loop will keep running until everything that can be resolved is actually resolved.
Clearly, there is still some pain involved in handling forward references. Regions of code that could potentially have the problem must be surrounded with the create, remove and continue. However this is a comparatively small amount of work that must be done in exchange for the freedom gained by gracefully solving a fundamental data processing problem.