Prototype-based programming language with fast dynamic binding

[MiJaGourlay]

(new post on blog: http://misinformedcognoscenti.blogspot.com/)

Prototype-based programming language with fast dynamic binding

The problem:

The game engine FIEA graduate students write each year (as part of
their second programming class) uses a prototype-based programming
paradigm that shares principles with object-oriented programming (OOP)
but the limited version previously assigned lacks several desirable
features, partly due to performance considerations. Prototype-based
programming readily provides inheritance and encapsulation with no
significant performance penalty but polymorphism and even common
procedure calls can be expensive due to name resolution. As mentioned
in Steve Yegge's article, "The Universal Design Pattern", prototype-
based programming comes with some costs: performance and early
verification. I want to explore the possibilities of creating a
prototype-based programming language, intended for use in a game
engine, that addresses the performance issue.

The FIEA game engine implements a very limited prototype-based
programming language by using the prototype design pattern and
composition to associate attributes with objects (called Entities).
Attributes can be either prescribed at compile time or added at run
time. The system uses factories to instantiate new objects. Each
object implements a "clone" method (a virtual constructor) which
duplicates the entity, its attributes and behaviors. Behaviors are
something like procedures, implemented using the "strategy" design
pattern (and we call these behaviors "Actions"), and objects use
composition to contain lists of these behaviors. By cloning objects
and modifying them, this simple system provides a simple form of
inheritance. (By restricting access to members, we can encapsulate
object members, although in some sense this provides no additional
functionality, so the assignments omit this property.) The system is
simple and somewhat powerful for its simplicity in that it allows game
entities to have script-driven properties and behaviors.

The FIEA game engine contains a list of these Entities, and the
simulation consists of processing each Entity for each frame by
executing a special Action (dubbed the "sim" action). The game engine
has a few other features but those are topics for future posts.
Essentially (at least for the purpose of this post), the FIEA game
engine consists of an ordered list of entities that have attributes
and actions, and the "sim" action of each entity runs every frame.

Past incarnations of this system use early (or static) binding (i.e.
names are resolved when parsing configuration files and populating the
system), so behavior execution runs relatively quickly, but the
configuration language (I hesitate to call it a scripting language)
lacks certain rudimentary features such as traditional procedure
calls. The system lacks late (or dynamic) binding, i.e. there is no
scope tree traversal to resolve names within the runtime environment,
so this system lacks polymorphic "method calls" and closures. We could
readily add dynamic binding but obvious general and simple solutions
would entail run-time name resolution, which could be slow. (The
system also has a scriptable event system which allows messages to be
passed between Entities, and this provides method invocation somewhat
akin to a limited form of how the programming language "Io" passes
messages, but those invocations have excessive overhead.) The problem
at hand entails adding more power (e.g. procedure calls) but without
the performance costs associated with dynamic binding via scope
traversal.

Actions in past incarnations of the FIEA game engine differ from
traditional procedures in most other languages in that they do not
have positional parameters and cannot be invoked from another action;
all parameters were accessed by name, and all actions were called by
the core engine (not from script). It might help to think of the
former Entities and Actions system as being closer to declarative than
to imperative, inasmuch as the "language" used to define the system
consisted of populating a tree with properties. The description
language happens to be in XML and could probably just as well be in
JSON. The motivation behind using only named properties and only
sequences of predefined Actions has roots in the design goal of
allowing a non-technical game developer (e.g. an artists or a
producer) to assign attributes and behaviors via a drag-and-drop or
other visual content creation user interface where the author does not
need to know the syntax of a programming language. (Again, the notion
of drag-and-drop programming is a topic for another post.) We
therefore wish to preserve this trait of not requiring positional
parameters in behavior configuration.

More common and fully-featured programming languages provide the
ability to decompose problems into small pieces and solve them
separately without the separation introducing undue overhead. In
programming terms, it comes down to being able to make "local"
function calls cheaply. ("Remote" function calls, which involve
synchronizing execution across multiple cores, or accessing memory
distributed across multiple cores, is a somewhat separate problem so
let's leave that aside for now, except to mention that the existing
event system is well-suited to that problem.) The solution should run
fast, retain existing features and have a solution that can be
implemented in a short amount of time (otherwise FIEA students would
not have enough time to write it in a single semester).

Forms of dynamic binding and what they buy you:

The term "dynamic binding" has a variety of meanings depending on
context so though I claimed that "the engine should have dynamic
binding", the problem statement still requires quite a bit more
refinement. Let's review various forms of dynamic binding and features
they provide.

Procedure calls bind function arguments in the sense that the formal
parameters are mapped to the actual parameters (or arguments) passed
at the procedure call. This happens by placing values (in the scope of
the caller) into registers or memory that are used locally within the
procedure code (in the scope of the callee). This binding could be
called static in the sense that the variables passed by the caller are
determined at compile time. The only sense in which this binding is
"dynamic" is in the limited (perhaps artificial, definitely not
conventional) sense that semantically, the arguments refer to
different variables at run time. And past FIEA engines lack even this
rudimentary form of binding.

If a function can call itself or if a function can be called multiple
times "simultaneously" then we say the language support recursion.
This implies that the same formal arguments can be bound to a multiple
sets of actual arguments (i.e. memory locations) simultaneously. If
the mechanism used to pass arguments simply involved storing values
into registers or fixed memory locations then a second simultaneous
call to the same procedure would overwrite and obliterate the values
in those locations, defeating any attempt to call recursively. To
support recursion, usually procedure argument values are pushed onto a
call stack at the caller side and extracted from the stack at the
callee side. Just as with non-recursive function calls, this form of
parameter binding does not conventionally get listed as dynamic
binding.

Polymorphism via virtual function calls entails dynamic dispatch, i.e.
which method gets called (i.e. receives the message passed) depends on
the object on which that method is called (i.e. to which the message
is passed). In this form of dynamic binding, the compiler cannot
resolve which function to call so the decision is delayed until run
time. In practice this happens by dereferencing a table of function
pointers, and the object holds the address of the table -- so it
actually involves a pair of pointer dereferences. Actually it usually
involves three pointer dereferences since the object itself is usually
referenced by a pointer. (If you had the object itself instead of a
pointer to the object, then you wouldn't need polymorphism because you
could resolve the method at compile-time.) But despite the fact that
the function name gets bound at run time, the arguments are still
bound at compile time; This form of polymorphism is such that the
function call always has the same "signature" or "form" i.e. the
formal parameters are always the same, regardless of the object type.

The forms of dynamic binding discussed above apply to C++, Java and
C#, but dynamic languages such as Lisp, Io and JavaScript include
additional forms of dynamic binding. These include the dynamic lookup
of so-called "free variables", the use of "continuations" instead of a
call stack, and the use of "duck typing" to decide which methods shall
handle messages passed to an object.

Prototype-based languages offer a form of inheritance where each
object has a "parent" object used as a prototype to create the new
object. The clone operation has at least two choices: Either have the
child object hold a pointer to the parent or have the child duplicate
all members (including all code and all data) of the parent. The
former conserves memory, so seems desirable. If using that method then
name resolution (i.e. binding) involves traversing parent pointers and
looking for the attributes that match the name of the sought
attribute. (Please read Steve Yegge's article for more detail.) Lookup
therefore takes at least O(N) time where N is the number of ancestors
the child has.

Some programming languages treat functions as first-class objects,
meaning (among other things) they can be passed as arguments and
returned as any other value. These so-called lambda functions are
anonymous procedures which can be defined within the scope of another
procedure. They can refer to at least 3 kinds of variables: local,
arguments and "free". Free variables are those which are defined
outside the context of the procedure body, e.g. inside the procedure
containing the definition of the lambda function. (Formal language
theory makes a distinction between bound and free variables although
both require some form of binding, and in fact binding "free
variables" entails a lookup which is more conventionally called
"dynamic binding". In this nomenclature, "bound" variables refer to
function arguments, which in the current context is admittedly
confusing.) With lambda functions comes the problem (called the funarg
problem) of deciding how to bind variables which are defined locally
within the enclosing scope, after that scope as ostensibly
disappeared. An example (in pseudocode) will help explain:

int procedure(int x) foo(int x)
{
return int lambda(int y)
{
return x + y ;
}
}
b = foo(1) ; // returns a procedure
b(2) ; // returns 3

In this example, foo is a procedure that takes an integer argument (x)
and returns a procedure which is defined inside foo. The procedure it
returns (which has no name) takes an integer argument (y) and returns
an integer (the sum of x and y). The problem is, when foo returns, its
local variable (x), which traditionally gets allocated on the call
stack, would normally no longer exist, yet the lambda function refers
to that variable. If x is allocated on the stack then when b(2) is
called (which invokes the lambda function, which refers to x, defined
outside the lambda), then it seems as though the attempt to reference
"x" would yield undefined behavior (a euphemism for saying that some
random memory location would be accessed, leading to tragedy). This is
the funarg problem, and it has at least two solutions: Disallow free
variables or use closures. A closure is a "scope" which is associated
with a function, which is used to dynamically bind a variable.
Resolving (i.e. binding) a free variable thus entails searching
closures for the nearest one which maps a name to a value. This is
"real" dynamic binding for variables, and with it comes great power,
especially when you remember that in languages with closures,
variables themselves can refer to functions. So this technique allows
you to write functions that create functions from other functions.

As an alternative to using a call stack, the system can use
continuation passing style (CPS) which allows for continuations and
coroutines. At first glance, CPS seems like an extraordinarily
overwrought notion and excruciatingly difficult to use to write
programs. In fact, writing code in CPS style would lead to early
insanity. But its purpose is not to be used by humans for authoring
code, but as a way to translate code automatically, behind the scenes,
to facilitate continuations. It is useful at this stage to note that a
"continuation" includes a function and its arguments, and the caller
will not know the "signature" of the function until run-time. This
contrasts sharply with polymorphism as present in C++ where the
function signature is static. This discussion rapidly leads to a
tangent so I will leave the rest for another post. Meanwhile, suffice
it to say that CPS solves useful problems in interesting ways and the
dynamic binding problem solved by closures applies there also.

It might seem like closures and CPS provide solutions in search of
arcane problem, especially in the current context of deciding how to
implement the ability to bind names in a scripting language for games.
After all, since the goal is to make a scripting language that non-
technical people can use to author games, then esoteric features like
anonymous procedures and concurrent coroutines probably lie well
outside the abilities of the intended audience. Perhaps. We should
explore some possibilities and see where that leads, but we might
eventually return to these more powerful techniques.

There is a form of polymorphism which effectively combines the dynamic
binding schemes discussed so far. The examples above include dynamic
binding of two kinds of names: functions and variables. C++ and its
ilk use "dynamic dispatch", i.e. dynamic binding of functions.
Prototype-based languages can use "parent" pointers and dynamic
programming languages use "closures" to represent scopes or
environments which map names to values, which can be used to bind
variables dynamically. The object-oriented programming paradigm refers
to "passing messages between objects"; it does not refer to "calling
procedures". C++ implements message passing (or a limited form of it)
as a procedure call, and the compiler checks to make sure the object
being passed the message actually has a method to handle that message.
But in dynamic prototype-based languages like JavaScript, you can pass
any message to any object, regardless of whether the object has a
method that handles that message. This is called duck typing. This
provides an extremely flexible form of polymorphism.

Dynamic Binding Options:

What form of dynamic binding should the game engine support, and how
should it be implemented? It is possible that "how" has multiple
answers depending on the what. As "Io" shows, it is possible to unify
all of them, but Io values simplicity and power over performance,
whereas the FIEA game engine values simplicity and performance over
power. So instead of deciding which of the features above we want,
consider the list above to be a menu without prices. Our decision of
which items to choose depends on their price. So let us determine the
prices: What implementations can we concoct, and which seem both
simple and computationally efficient?

The system needs a name-to-value map, which we will call the
Environment.

Former version of the FIEA game engine implemented the Environment as
a single flat dictionary where names have 2 parts: context and
instance. This presented the appearance of a hierarchical namespace
but with constant-time lookup on any symbol.

Consider defining a struct called Scope which maps names to values. In
principle, each scope contains other scope objects. This would form a
tree of scopes, or a hierarchical namespace with an actually
hierarchical structure in memory. Traversing this namespace usually
happens from the leave nodes upward so instead of (or in addition to)
each scope containing children, each child should contain a reference
to its parent. Each object (Entity or Action) would contain a pointer
to its local scope. As mentioned above, name lookups would require
O(N) time where N is the depth of the child.

We can flatten the tree traversal using something akin to "Lambda
lifting": Convert each variable that resides in a parent scope into a
local variable in the scope associated with the Action. In other
words, all non-local attributes become local to the scope of an
object.

In a similar spirit, any non-local variables accessed by an Action can
be bound using tree traversal, then the results can be cached into the
Action's local scope for future accessed. (This resembles a copy-on-
write policy, although its goals are different.) But since all the
referents are known at compile-time there is no obvious reason to
delay this operation until run-time.

Imagine that each Scope does not know its children, and that children
only know their parents. Action invocations could include a pointer to
another scope object and name resolution would require looking at the
passed-in scope (and its parents) prior to using the scope statically
associated with the Action. In this way, any variable (free, bound or
local) could be redefined by the caller, upon invocation. I will call
this notion "scope tree surgery" since it effectively replaces one
branch of the tree with another branch from another part of the tree.
(The analogy is somewhat strained because the result of the surgery is
to have one branch refer to another; the attached limb is never
removed from the other part of the tree.) This technique provides
immense power, including and exceeding even the most esoteric forms of
dynamic variable binding techniques discussed above, including
argement passing and closures. For example, even Lisp does not provide
a mechanism for rebinding local variables inside a function. How could
this seemingly dangerous and atypical property be useful? In the
context of a game engine, each variable (including locals) stores
properties which control behaviors, and we aim to make all behaviors
tunable via script. Phrased differently, using this technique, all
variables in an Action act as though they are arguments, all of which
have default values. The caller can choose to change those variables
or leave them alone. From the caller perspective, there is no
distinction between function arguments, locals, and free variables.

Unfortunately, in terms of performance, this raises the cost of name
binding considerably. It includes not only the usual cost of lookup
associated with a more conventional scope tree used with stack-based
or CPS function calling, but also this notion of searching the "passed
in" scope prior to the usual scope (and/or closure). That is, usually,
function arguments are passed by position, e.g. on a stack, and the
callee unpacks those arguments and places the passed-in values into
the memory locations of what are tantamount to temporary local
variables. That process involves no lookups, just linear scan-and-
unpack which can be written and automated prior to run-time.

Regardless of whether dynamic binding requires a tree traversal (i.e.
even if we use some flavor of tree flattening), and even if the local
scope uses a hash table, name binding will require some sort of lookup
that costs more than a pointer dereference, and as it is, even pointer
dereferences get scornful looks from optimization czars. Former
versions of the FIEA game engine avoided this cost by caching all
prescribed parameters (i.e. those known at compile-time) into member
variables of the Action class. And (as mentined above) most
programming languages make this "lookup" trivial by making it a hard-
coded (thought automatically generated) register-to-stack (and vice
versa) transfer, which relies on function arguments being fixed in
size and order, at compile time. We want to preserve the property that
Action variables are assigned by name, not by position, but we want
the speed of positional parameters and structures (which both amount
to lookups by offset).

Perhaps we can have our cake and eat it too, by prescribing parameter
order within scopes. Instead of caching parameter addresses into
member variables (as was done in the past), each scope would contain
an array of pointers to Datum, and at compile-time the ordering of
those would be known. When an Action gets invoked, a "replacement"
scope would be populated but its ordering would remain the same as it
was at compile-time. This trick would only help for prescribed
parameters and it has some fragility issues but most of that noise
gets hidden from the end user and could potentially be automated with
some clever tools.

There is also a concept of "late static binding" which essentially
amounts to rebinding a static member variable used in a method defined
in a base object which a derived object inherits. The notion of
"static" member variables only applies in languages which separate
classes from instances, which is not the case in prototype-based
languages.

I have left several loose ends in this post; what about duck typing,
CPS, lambda functions and closures? Do we want them? At what price?
Those are open for discussion.

Meanwhile, this post has outlined a way to inject traditional
procedure calls into the FIEA game engine, without adding to the cost
of accessing prescribed parameters. The current topic of discussion
is, does this seem sane?