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

Game Engine Configuration Language Part 4: Visual Programming Languages

Game engine configuration languages should facilitate programming for non-programmers (e.g. game designers) to allow them to create game mechanics and autonomous entity behaviors. This problem has arisen through much of the history of computer programming, and for decades, people have tried to make computer programming accessible. Lately that trend has continued with some interesting new attempts. I want to review these languages with the hope that we can identify patterns -- what works and what does not -- and hope this guides our attempts to make a game configuration language which lets non-technical game developers the ability to control the interaction mechanic and other aspects of gameplay.


We can divide computer programming into at least two major components: data flow and control flow. We can categorize languages in terms of whether they principally focus on providing instructions (so-called imperative languages) or descriptions (so-called declarative languages). Imperative languages read like recipes -- a sequence of instructions (called a procedure) for how to accomplish a task (called a process). In contrast, declarative languages describe what results should look like, what properties they have, and the computer infers how to accomplish that. We should consider which of these is easier to understand and see whether we can construct a language accordingly.

Non-programmers struggle with the syntax of computer programs -- the grammatical rules that dictate whether a given sentence fits into the computer language. Computer language syntax is usually rather unforgiving, pedantic and arcane; even very small, seemingly insignificant changes in punctuation can drastically alter the meaning of a program. People have therefore made tools which strive to eliminate the possibility of writing programs with bad syntax. Such languages are often visual, in which authoring programs feels like constructing a physical machine. So in addition to constructing a game configuration language, we should consider how to construct a UI that assists authoring programs in that language -- since perhaps that will guide us on how to write the language.

In the study of formal language theory, the Chomsky hierarchy identifies connections between kinds of languages and the machines that can process them. Some machines are simpler than others, and perhaps we can exploit this fact to construct simpler languages. The resulting language should be easier to understand and use. The drawback is that the processes might be restricted but perhaps that is a Good Thing; perhaps non-programmers should have some restrictions on what they can do. Or perhaps the language can expose more sophisticated features only as-needed, such that non-programmers can use only the more restrictive, easier aspects if they choose -- then graduate to more complicated features when they become familiar with how they work.

After reviewing other language, I will propose adopting certain paradigms for game configuration languages: For AI, combine a finite-state machine (FSM) with steering behaviors. The language should facilitate both declarative and imperative paradigms. The authoring GUI should let user decide which to use, and provide a user-friendly visual dataflow interface with limited capabilities in addition to a text-based interface that exposes more sophisticated functionality for more advanced users.


Background


This section lists a sampling of computer programming languages intended for non-programmers or non-traditional programmers.

Alice: "Alice is an innovative 3D programming environment that makes it easy to create an animation for telling a story, playing an interactive game, or a video to share on the web. Alice is a freely available teaching tool designed to be a student's first exposure to object-oriented programming. It allows students to learn fundamental programming concepts in the context of creating animated movies and simple video games. In Alice, 3-D objects (e.g., people, animals, and vehicles) populate a virtual world and students create a program to animate the objects." Apparently Alice accomplishes its goal but its approach seems inappropriate for game configuration. I also find the GUI extraordinarily busy and distracting. Before you can learn to "program", you need to go through a rather long tutorial on how to use the Alice GUI. So even if Alice makes programming concepts more accessible, it does so at the cost of having to learn a complex GUI. Alice is fashionable in academia and worth knowing about but I do not find it inspirational for designing game configuration languages.

Kodu: "Kodu is a new visual programming language made specifically for creating games. It is designed to be accessible for children and enjoyable for anyone. The programming environment runs on the Xbox, allowing rapid design iteration using only a game controller for input." Although I have not read it described this way, it seems to use subsumption architecture -- the same scheme used by the "fast, cheap and out of control" robots. The GUI is elegant, pretty and engaging. The GUI only reveals elements that make sense in the context of what the user is doing at that precide moment, therefore is quite uncluttered. The user would therefore not get distracted by irrelevant aspects of the GUI. Kodu also effectively uses an FSM-plus-steering architecture, which I advocate. I would, however, change at least one aspect of the Kodu GUI: The fact that the user is effectively creating an FSM is never made visually explicity; each "state" (which Kodu calls a "page") can have a rule that would cause a transition to another "state" -- but there is no visual representation that shows the transitions between states. Also, the states have no meaningful name; they're simply numbered pages. So I would add the ability to label states with a meaningful name. More on that later. But in summary, I suspect that a person who had never seen Kodu before could walk write up to Kodu and, just by playing around, figure out how to write rather sophisticated programs. That's amazing.

LabView: "LabVIEW is a graphical programming environment used by millions of engineers and scientists to develop sophisticated measurement, test, and control systems using intuitive graphical icons and wires that resemble a flowchart. LabVIEW offers unrivaled integration with thousands of hardware devices and provides hundreds of built-in libraries for advanced analysis and data visualization. The LabVIEW platform is scalable across multiple targets and operating systems, and since its introduction in 1986 has become an industry leader." Programming LabView resemblies creating a "factory floor" where you have "stations" that process data and "conveyer belts" that shuttle data between stations. (These are my terms.) A lot of dataflow lanaguages use this same idea.

Pure Data: "Pd (aka Pure Data) is a real-time graphical programming environment for audio, video, and graphical processing." To me, this resembles LabView.

Unreal Kismet: Yet another dataflow language -- this one specifically written for game configuration. Kismet also includes "events". Kismet control flow follows dataflow. As values pass from left-to-right, so does control flow (which is typical for a dataflow language). In addition, Kismet actions have "variables" which do not "flow" or cause processes to run; they just provide access to data. Resembles Virtools and I think that aside from the complexity of its GUI, this is worth studying further. Tutorials I read do not mention facilities for abstraction i.e. the ability to cluster a dataflow graph into a user-defined graph with fewer inputs. Many aspects of the FIEA game engine configuration language resemble what must be the underlying virtual machine for Kismet.

Virtools: Yet another dataflow language specifically for configuring simulations. Programs consist of "building blocks" (BB's), whose visual representation is arcane. Like dataflow nodes in other languages, BB's have inputs, outputs and variables, but the GUI does not label them so they just look like distracting decorations. Virtools also has "messages" which I believe are like events. I suspect the features of Virtools and Kismet are probably quite similar, but I find the Kismet GUI looks more intuitive -- but perhaps only slightly. Neither is obvious.


Further Reading

Have a look at these resources for more examples along the lines of the above systems:
Boshernitsan & Downes (1997): Visual Programming Languages: A Survey
ARK: Alternate Reality Kit (1986) for simulations, based on Smalltalk.

VIPR: Visual Imperative PRogramming (1994): Object-oriented. Nesting rings dominate diagrams. Inscrutible diagrams for anything more than trivial examples.

Prograph (1982): Object-oriented, imperative, dataflow determines flow control. Commercially available for a while. Shortcomings include messy diagram organization (user controlled) and unlabeled classes and inputs.

Forms/3: spreadsheet.

Cube: 3D programming language.

Nickerson (1994) Missing lots of figures which, for a survey of visual languages, is quite an impediment. Furthermore I was unable to find examples on the web of several topics covered there; one would probably have to obtain print versions of his references, and they are all out of print. What diagrams it contains are unreadable in some cases. It covers a lot of diagraming conventions.

H-graphs: expansion on detail of a state which contains substates.

PICT: resembles typical flowcharts.

Blox: puzzle pieces represent program structure.

Show-and-Tell: iteration results in a list of each value.

Programming in Pictures: Not imperative.

Garden: meta-language meant for constructing visual languages. Can build FSA, dataflow and flowchart languages.

Summary

Dataflow languages provide a visual programming environment which alleviates the problems of understanding and following pedantic computer language syntax. But the "visual grammar" can also be difficult to leanr, and diagrams for complicated procedures can become unwieldy. Loops difficult to implement because each block has no state, so input data needs to contain state (e.g. loop index variable), which is awkward in some dataflow languages, but others seem to solve this problem by discriminating between "variables" (which provide access to data) and "inputs" (which trigger control flow).

Although the hybrid dataflow-causes-control-flow paradigm seems to work, I wonder whether using signals/events/listeners introduces a lot of overhead for processing small signals. When messages point to huge arrays, overhead is acceptable but for single values, overhead costs more than the regular processing.

Dataflow languages can also model blocks as having explicit control-flow sockets in addition to having data sockets. The control-flow sockets depend on data, messages or signals. So each block effectively becomes something like a multiplexor or switch-case statement.