next up previous contents index
Next: An Implementation Up: The Dreams System Previous: Reality   Contents   Index

Dynamic Binding

Since the concept of dynamic binding is at the heart of any implementation of Dreams, we must discuss what dynamic binding is. Binding is a term that refers to the semantics, or action, associated with a name, or symbol. In Forth, we frequently use the term word to refer to the name of a subroutine, and also to the action of that subroutine, or the instructions that comprise it. For the purposes of this discussion, we shall use the terms name and action, and allow the term word to continue to have its customary meaning(s).

There are several different kinds of binding that need to be distinguished from each other: early binding, late binding, and dynamic binding. The closely related concept of scoping also comes in two varieties: lexical scoping, and dynamic scoping. Algol derived languages (the so called ``structured'' programming languages in vogue these days) operate according to the principles of early binding and lexical scoping.

Lexical scoping means that objects, such as variables, subroutines, etc., that are declared within a block of code are visible only within that block, and perhaps within blocks inside of that block if the particular language permits nesting of blocks. Ada, Modula, and Pascal do permit this, but C only permits a limited form of this, and FORTRAN does not permit it at all.

Early binding means, in this case, that it is the responsibility of the compiler, at compile time, to determine what action is associated with each name. The compiler compiles code that will produce this action when that code is later executed.

Since Forth is not generally considered to be a block structured programming language, we must reconsider what lexical scoping means in a Forth programming system. If we consider a word-list (which used to be called a vocabulary before the ANS X3J14 effort [Com91]) to be the logical analog of the block in a block structured language, then lexical scoping and early binding means that the actions associated with the names in the current search order at the time of compilation will be compiled into the definitions of all new words. It should be apparent that this is just exactly what the Forth compiler does.

What about late binding? How does it differ from the early binding that we are familiar with? In late binding, the compiler does not compile code to perform the action associated with a name. It compiles code to determine the action associated with a name, followed by code to perform the action that has been determined.

Consider a late binding variation of the object oriented approach described by Pountain [Pou87]. In such a system, the compiler would compile code to search the list of methods belonging to an object, and when the name of the current word matched the name of the method, then the action associated with that method would be performed. This is known as run-time method searching, and is a characteristic of some late binding object oriented systems. Pountain realized that the overhead of method searching was too expensive for a real-time system, so he factored the method searching into compile time, resulting in an early binding implementation. This solved the speed problem, but made operations such as holding a message in a variable unfeasible. Late binding is needed if this is to be done.

So what is wrong with early binding? Why bother with a late binding strategy at all? In an early binding message passing object oriented system, the messages must be compiled at compile time, and the actions associated with the names of all the words comprising a message must be determined. This usually means that all the methods applicable to a particular object must be declared with that object at compile time. The messages that such an object may receive must be restricted so as to limit the words in the messages to only those words that have been declared valid for that object. In fact, the messages themselves are actually compiled as just more code in the sender's instruction stream, and the methods appear lexically following the recipient object. This is in violation of normal Forth usage, where an operator receives the data and acts on it. In this case, the message is the action, and the recipient of the message is actually passive. In an early bound system, it is not generally possible to have a variable hold a message, since the message needs to be compiled into the code that sends it to its recipient.

In a late binding system, a message can be an object too. A variable can hold a pointer to it. The message is passed passively on the stack to its recipient, which acts to interpret the message. If the implementation uses run-time method searching, then each name in the message will be looked up and performed. This gives the applications programmer an additional flexibility over an early binding system.

In Dreams, a message is called a thought, and it is known by the execution token of any word, such as a colon-definition, variable, constant, etc. The execution token is passed on the stack to a dream that is to ponder that thought within its own understanding. While Dreams does not use an early binding approach, it does not use a method searching late binding approach either. Dreams uses a dynamic binding approach, which is a late binding technique with dynamic rather than lexical scoping.

The dynamic binding technique permits altering the action associated with a name. Since a name is known at execution time by the execution token compiled by the compiler from the name found in the source code, the dynamic binding implementation must rely upon knowledge of the inner workings of the compiler and interpreter. What is done in the current Dreams implementation is to provide a way to read and write the parameter field address of a word. This permits providing a different parameter field for a word local to a dream. Since the threaded code is deposited by the compiler into the parameter field, then by modifying the parameter field address, a word can be given an action at run time that is different from the action associated with it at compile time.

By reading the original parameter field address of a word and pushing it on an active bindings stack before writing the new parameter field address in its place, a means of restoring the original action is provided. Each dream has an associated list of execution tokens and substitute parameter field addresses that specifies that dream's contribution to its understanding. When a dream becomes active, the list of execution tokens and parameter field addresses is traversed. For each execution token in the list, the original parameter field address is read and pushed on the active bindings stack. After this, the new parameter field address, obtained from the list, is written in its place. When the dream finishes, the old parameter field addresses are restored by popping them from the active bindings stack. Since this list is of a fixed and known length, a fixed and known execution overhead results. This property of deterministic timing is generally desirable in many embedded and real-time systems applications.

next up previous contents index
Next: An Implementation Up: The Dreams System Previous: Reality   Contents   Index
Robert J. Brown