Game Engine Configuration Language, Part 5: Means of Abstraction

We want use our game configuration language to express solutions to specific problems in a way that meshes well with the rest of the language. In other words, we want to be able to extend the language in a way that blurs the distinction between intrinsic features that came with the language, and ad hoc features added to solve specific problems. The language facilitates this seamless extension via its means of abstraction.

Part 2 explained primitive data and the means of combining data into user defined types, but procedures also have primitives and means of combination.

Abelson summarizes a framework for abstraction in computer languages, which I paraphrase here:

	Procedures	Data
Primitives	+, *, ==	numbers, strings, true/false
Means of Combination	if, while, ...	Arrays, lists, dictionaries
Means of Abstraction	function definitions	Classes

Means of Abstraction

The means of abstraction amounts to how a language allows a programmer to extend it such that the view of the problem takes on a form more natural to that particular problem, rather than how the language would otherwise natively express that problem.

Consider machine language, which expresses procedures in terms most suitable for a CPU to use: Instructions include loading values from memory and placing them into registers, storing values from registers into memory, comparing values in registers, conditionally branching based on values in registers, unconditionally jumping to an instruction at another address, and performing arithmetic. That's all -- just those 5 kinds of instructions (plus a few more used for debugging and low-level stuff not really germain to solving computational problems). This way of phrasing procedures makes a lot of sense for a typical Von Neuman architecture, which has physical objects like memory, registers and arithmetic units built into hardware. But imagine trying to write millions of lines of machine language. Even if you never had to worry about porting to multiple platforms, this scenario constitutes a nightmare because it provides no way to divide the problem into chunks that correspond to a more intuitive description of the problem.

(Be careful, assembly afficianados. If you use an assembler, especially one that has macros, then you're already skipping two steps ahead of the point where I currently stand, which is in machine language -- or perhaps even microcode -- not assembly.)

Machine languages pose at least two barriers to solving a problem concisely: They deny programmers even straightforward conveniences like compound algebraic expressions, and they do not facilitate dividing and chunking a problem into a hierarchy of multiple, nested, modular subproblems, each solved at a different level of detail. Likewise, machine language has no formal notion that multiple pieces of data belong to the same set, nor that an element of data can have a structure with multiple pieces.

Higher-level languages like C ameliorate the first problem by providing higher-level control-flow constructs like if-then, while and for statements, which reduce the tedium of phrasing such common ideas in machine language. Likewise primitive "container" data structures like arrays (in C) or tables (in JavaScript) allow for aggregation of data. But those means of combination do not give programmers the power to change the language, in that the operations on those structures look the same as operations on any other structure. Means of combination provide the mechanism to put certain things in one place, but not to treat those things as first-class entities.

(As an aside, I'll mention that this series of articles has not yet described the how the game engine configuration language provides the means of combining primitive operations, nor even what those primitive operations are. The answer, ironically, is easier to explain after understanding the means of abstraction, so bear with me.)

This is where yet higher-level constructs come in: The ability to define a function creates the possibility of altering the structure of a program so that its description operates at a level commensurate with the domain of the problem, rather than the domain of the machine. And taken a step further, object-oriented languages allow us to bundle procedures and data together.

So providing a means of abstraction includes providing the ability to define procedures and possibly associating those procedures with a user-defined data type.

Tables as prototypes

This topic might seem familiar because Part 2 described using tables as a means of combination, and an earlier, rambling article presented the notion of "prototypes" which resemble a combination of objects and classes. But those articles lacked sufficient emphasis on abstraction, and specifically, how we should express abstraction in the source language. This ends up being related to binding, so review that article too.

The problem at hand then boils down to the following sub-problems:

How does the language express defining a new subroutine?

How does the language express invoking those subroutines?

How does the language facilitate creating user-defined types?

Defining subroutines

Our game configuration language has notions of Actions and Reactions. Both are named and both access data which technically resides outside of the scope of those constructs, so at first glance they both seem like subroutines. But it makes more sense to think of Actions as both primitives and as a means of combination, i.e. as a way to express a collection of instructions. Indeed, primitive Actions are the primitive operations of this language, and they are usually implemented in native code. And compound Actions, those which execute their contents, constitute a means of combination, because it allows grouping clusters of Actions together and giving them an order. Indeed, control flow statements such as if-the, while and for statements are readily expressed as compound Actions.

(Note that since Actions are tables, in the is-a sense), it is always possible for an Action to contain another Action. But when you do that, it does not always constitute a proper "combination" in a meaningful sense because not all Actions invoke, or execute, the Actions they contain. The analogy in C would be a struct that contains function pointers. A struct cannot execute its contents, so such a struct would not be a "means of combination" for procedures.)

In contrast, a Reaction contains an Action (which, by extension, includes compound Actions) and also has a name and creates a temporary scope which automatically binds calling parameters to the names used within the Reaction (and its Actions). So in our paradigm, Reactions play the role of the means of abstracting procedures.

Our game configuration language therefore supports defining subroutines via defining Reactions, where the event plays the role of the arguments and the activation record provides a way of binding event data to names used in the procedure definition.

Calling functions

Now that we see that Reactions provide the means of abstraction, it is clear that invoking subroutines amounts to throwing events. Done and done.

User-defined types

There are at least two contexts in which subroutines can live: When the subroutine is a member of a table, and when it is not. When a subroutine is a member of a table, and it has access to the particular table that is involved in the invocation, mere "tables" graduate from a means of combination into a means of abstraction.

As described elsewhere, our game configuration language supports "tables". The neato thing about this choice is that this choice, plus the choice of treating expressions as tables, and allowing tables to include tables, allows us to treat tables as both a means of combination and as a means of data abstraction. This dual role of tables is possible partly because of the fact that tables can include tables and that reference variables can refer to tables.

To graduate from mere collections of data into abstract data types requires formally associating operations with the table, such that the table itself has its own set of operations.

The trick involved is one of binding, which I (perhaps prematurely) discussed in part 3. So there you have it.

Coming up

Abelson describes the notion of a means of capturing common patterns, which includes higher-order procedures (i.e. procedures that operate on or with other procedures) and inheritance. I have touched on the topic of procedures that define other procedures, which is related. But perhaps there is more to consider when invoking a procedure from within another procedure. We need to consider how to alter the language so it can bind a procedure at run time.

Metalinguistic abstraction entails thinking of programming as creating languages to solve categories of problems, and programs as evaluators of those languages. Each of those languages has its own primitives, means of combination and means of abstraction. So maybe we will visit this topic in another article although it seems to me that this whole blog constitutes a discussion of metalinguistic abstraction, inasmuch as the blog discusses how to write a language. But maybe we can come up with a discussed which could be entitled meta-metalinguistic abstraction, in which we consider how to make the game configuration language suitable for use in solving even more specialized problem domains. Let's see how deep we can recurse before it gets intolerably silly.

Further reading

http://mitpress.mit.edu/sicp/toc/toc.html