Chapter 1.1.2:
Step: a maximalist clairvoyant language

Step is a declarative programming language that's relatively easy to learn.  If you're familiar with Prolog, it's basically a generalization of Prolog¹ with a gentler learning curve.  It was developed for interactive narrative but is general-purpose in the sense that you can write any algorithm in it you can write in other languages.  If Prolog is a language for the Chess Club, Step is a language for theater kids.

We'll begin with how to write Step programs that print things.  Programs that only print things are basically grammars.  Grammars are frequently used in games to make names of things (characters, items, planets, etc.) and quests.  Later, we'll show an example text generator from the influential 80's game Starflight (Binary Systems, 1986), which was cited as an influence on both Mass Effect and Dwarf Fortress.

After showing you how to write simple grammars, we'll show you how to write parameterized grammars that can intelligently print descriptions of things based on their characteristics.

Next, we'll show you how the same techniques used to write parameterized grammars can be used to write simple databases, and more importantly, query languages for those databases.  This is known as logic programming because those same techniques can be used (again) to let the computer perform an approximation to logical reasoning.

Standard logic programming makes it cumbersome to represent things that change over time.² Having looked at the basics of logic programming, we'll then look at how Step works with variables and other things whose state can change over time during the program.  This lets you more naturally write programs like planners or games that have world state.

Next, we'll discuss how to structure information using lists, tuples, and “feature structures”³.  If you've seen JSON, Step data structures are a lot like JSON objects that support a special kind of pattern matching.

The rest of the Step discussion is more technical.  Primitive tasks provides more information on the built-in operations in the language.  Higher-order tasks discusses how Step code can be parameterized by other bits of Step code.  If you've programmed before, then you've seen things like this in the forms of statements like while and if: they take code (the stuff in { ... }) as their arguments and they decide which of those things to run when.  Step has a much more general version of this that lets you write your own higher-order operations.

Finally, we'll talk about reflection, which is the ability to write programs with a limited ability to reason about themselves.  This is useful for writing debugging tools, planners, and other kinds of programs.

Notes