Sometimes you just have to make a better mousetrap. Creating Languages in Racket cHoosInG THe RIGHT tool for a simple job is easy: a screwdriver is usually the best option when you need to change the battery in a toy, and grep is the obvious choice to check for a word in a text document. for more complex tasks, the choice of tool is rarely so straightforward-all the more so for a programming task, where programmers have an unparalleled ability to construct their own tools. Programmers frequently solve programming problems by creating new tool programs, such as scripts that generate source code from tables of data. Since programmers often build task-specific tools, one way to make them more productive is to give them better tool-making tools. When tools take the form of program generators, this idea leads to libraries for creating languages that are directly extensible. Programmers may even be encouraged to think about a problem in terms of a language that would better support the task. This approach is sometimes called language-oriented programming. Racket is both a programming language and a framework for building programming languages. A Racket program can contain definitions that extend the syntax of the language for use later in the same program, and language extensions can be packaged as modules for use in multiple programs. Racket supports a smooth path from relatively simple language extensions to completely new languages, since a programming tool, like any other piece of software, is likely to start simple and grow as demands on the language increase. As an example task, consider the implementation of a text-adventure game (also known as interactive fiction), where a player types commands to move around in a virtual world and interact with objects: You're standing in a meadow. There is a house to the north. > north You are standing in front of a house. There is a door here. > open door The door is locked. > To make the game interesting, a programmer must populate the virtual world with places and things that have rich behavior. Most any programming language could implement this virtual world, but choosing the right language construct (that is, the right tool) to represent each game element is a crucial step in the development process. The right constructs allow commands, places, and things to be created easily-avoiding error-prone boilerplate code to set up the world's state and connections-while also allowing a programming language's full power to implement behaviors. In a general-purpose programming language, no built-in language construct is likely to be a perfect fit. For example, places and things could be objects, while commands could be implemented as methods. The game's players, however, don't practice call methods but instead type commands that have to be parsed and dynamically mapped to responses for places and things. Similarly, saving and loading a game requires inspecting and restoring the state of places and things, which is partly a matter of object serialization but also of setting variables to unmarshalled values (or else using an indirection through a dictionary for each reference from one object to another). Some programming languages include constructs-such as overloading or laziness-that a clever programmer can exploit to encode a domain-specific language. The design of Racket addresses the problem more directly; it gives programmers tools to explicitly extend the programming language with new syntax. Some tasks require only a small extension to the core language, while others benefit from the creation of an entirely new language. Racket supports both ends of the spectrum, and it does so in a way that allows a smooth progression from one end to the other. As a programmer's needs or ambitions grow for a particular task, the programmer can take advantage of ever more of Racket's unified framework for language extension and construction. The text-adventure example presented here illustrates the progression from a simple embedding in Racket to a separate domain-specific language (including IDE support for syntax coloring), explaining relevant Racket details along the way; no prior knowledge of Racket is necessary. Readers who prefer a more complete introduction to the language should consult The Racket Guide. The example is a "toy" in multiple senses of the world, but it is also a scale model of industry practice. Most every video-game developer uses a custom language, including the Racket-based language that is used to implement content for the Uncharted video-game series. 2 Evidently, when billions of entertainment dollars are on the line, the choice of programming language matters-even to the point of creating new, special-purpose languages. Our text adventure game contains a fixed set of places, such as a meadow, house, or desert, and a fixed set of things, such as a door, key, or flower. The player navigates the world and interacts with things using commands that are parsed as either one or two words: a single verb (that is, an intransitive verb, since it does not have a target object) such as help or look; or a verb followed by the name of a thing (that is, a transitive verb followed by a noun) such as open door or get key. Navigation words such as north or in are treated as verbs. A user can save the game using the save and load verbs, which work everywhere and prompt the user for a file name. To implement a text-adventure game in Racket, you would start by declaring structure types for each of the three game elements shown in Figure 1 . Racket is a dialect of Lisp and a descendant of Scheme, so its syntax uses parentheses and a liberal grammar of identifiers (for example, transitive? is an identifier). A semicolon introduces a newline-terminated comment. Square brackets are interchangeable with parentheses but are used by convention in certain contexts, such as grouping a field name with modifiers. The #:mutable modifier declares a field as mutable, since fields are immutable by default. (define names (make-hash)) ; symbol to place/thing (define elements (make-hash)) ; place/thing to symbol (define (record-element! name val) (hash-set! names name val) (hash-set! elements val name)) Consequently, the complete implementation of the meadow is: The first struct form in the code binds verb to function taking one argument for each field and creating a verb instance. For example, you can define a south verb with alias s as (define south (verb (list 'south 's) "go south" #false)) Lisp and Racket programs tend to use strings for the text that is to be shown to an end user-for example, verb descriptions such as "go south". A symbol, written with a leading single quote (for example, 'south), is more typically used for an internal name, such as a verb alias. Given the definition of south and a thing, flower, you could define a meadow place where the south verb moves the player to a desert place as illustrated in Figure 2 . The list function creates a list, while cons pairs two values. The cons function usually pairs an element with a list to form a new list, but here cons is used to pair a verb with a function that implements the verb's response. The lambda form creates an anonymous function, which in this case expects zero arguments. When a verb's response function produces a place, such as desert in the example, the game execution engine will move the player to the returned place. The game engine's support for saving and loading game state, meanwhile, requires a mapping between places and their names. (Places can be implemented as objects that can be serialized, but restoring a game requires both deserialization and updating Racket-level variables such as meadow.) The record-element! function implements mappings between names and places as shown in Figure 3 . Things must be defined and registered in much the same way as places. Verbs must be collected into a list to be used by the game's command parser. Finally, the parsing and execution engine needs a set of verbs that work everywhere, each with its response function. All of those pieces form the interesting part of the game implementation, while the parsing and execution engine is a few dozen lines of static infrastructure. See the accompanying sidebar for links to the complete game implementation. The code needed to construct the virtual world is particularly verbose. Although the data-representation choices discussed previously are typical for a Racket program, a Racket programmer is unlikely to write the repetitive code that directly defines and registers places, since it includes so many boilerplate lists, conses, and lambdas. Instead, a Racket programmer would write and would add a define-place form to Racket using a pattern-based macro. The simplest form of such a macro uses define-syntax-rule as depicted as Figure 4 . The form immediately after define-syntax-rule is a pattern, and the form after the pattern is a template. A use of a macro that matches its pattern is replaced by the macro's template, modulo substitutions of pattern variables for their matches. The id, desc, thng, vrb, and expr identifiers in this pattern are pattern variables. Note the define-place form cannot be a function. The desert expression after south is, in general, an expression whose evaluation must be delayed until the south command is figure 4. the define-place macro. figure 5. the generalized define-place and define-thing macros. ellipses work in the obvious way, and with this generalized define-place, you can put both a cactus and a key initially in the desert and respond to direction verbs other than north by staying in the desert: (define-place desert "You're in a desert." The macro for a thing is similarly straightforward: 52 Co MMuniCations of th e aC M | jA nUA RY 2 0 1 2 | VO L. 5 5 | nO. 1 practice entered. More significantly, the form should bind the variable meadow so that Racket expressions for commands can refer to the place directly. In addition, the variable's source name (as opposed to its value) is used to register the place in the table of elements. The define-place macro so far matches exactly one thing in a place and exactly one verb and response expression. To generalize to any number of things, verbs, and expressions, you This example defines four verbs: quit as an intransitive verb with no aliases; north as an intransitive verb with alias n and a preferred description "go north"; knock as a transitive verb (as indicated by the underscore) with no aliases; and get as a transitive verb with aliases grab and take and preferred description "take". Finally, all of these verbs are collected into a list that is bound to all-verbs for use by the game's command parser. Implementing the define-verbs form requires a more general kind of pattern matching to support different shapes of verb specifications and to match = and _ as literals. An implementation of define-verbs can defer the work of handling an individual verb to a define-one-verb macro, which uses define-syntax and syntaxrules as shown in Figure 6 . The define-place, definething, and define-verb macros are examples of syntactic abstraction. They abstract over repeated patterns of syntax, so that a programmer can avoid boilerplate code and concentrate on the creation of interesting verbs, places, and things. The revised game implementation, which has a compact and readable implementation of the virtual world, is available online (see the accompanying sidebar for links). A Racket programmer who is interested in writing a single text-adventure game would likely stop extending the language at this point. If the text-adventure engine should be reusable for multiple worlds, however, a Racket programmer is likely to take a step beyond syntactic abstraction to syntactic extension. The difference between abstraction and extension is partly in the eye of the beholder, but extension suggests that functions such as place and recordelement! can be kept private, while define-place is exported for use in the world-defining module with implementation-independent semantics. In the world-defining module, macros add ellipses to the pattern as shown in Figure 5 . Verbs are slightly trickier, because you want to make simple verbs especially compact to specify, and you need one kind of pattern for intransitive verbs and another for transitive verbs. The following example illustrates the target syntax: (define-verbs all-verbs [quit] figure 7. the typed compile-time structure. (begin-for-syntax (struct typed (id ; an identifier type) ; a string #:property prop:procedure (lambda (self stx) (typed-id self)))) An identifier is written as a symbol, but with a # prefix, so that (typed #'gen-desert "place") figure 6 . the define-one-verb and define-everywhere macros. such as define-place have the same status as built-in forms such as define and lambda. To make this shift, you can put the define-verbs, define-place, define-thing, and define-everywhere definitions in their own module, called world.rkt. The #lang racket line that starts each module indicates that the module is implemented in the racket language. In world.rkt, require additionally imports both the syntactic extensions and functions that are exported by the txtadv.rkt module. Since macro binding is part of the Racket language, as opposed to being implemented as a separate preprocessor, macro bindings can work with module imports and exports the same as variable bindings. In particular, the definition of the define-verbs macro can see the verb constructor function because of the rules of lexical scope, while code in the world.rkt module cannot access verb directly because of the same scoping rules. Since a use of define-verbs in world.rkt expands to a use of verb, considerable language machinery is required for Racket to maintain lexical scope in the presence of macro expansion, but the result is that syntactic extension is easy for programmers. The modular game implementation is available online (see the accompanying sidebar for links). Although the world.rkt module cannot directly access constructor functions such as verb, the module still has access to all of the Racket language and, via require, any other module's exports. More constraints on world.rkt may be appropriate to ensure that assumptions of txtadv.rkt are satisfied. To exert further control, you can convert txtadv.rkt from a module that exports a language extension to one that exports a language. Then, instead starting with #lang racket, world.rkt starts with #lang s-exp "txtadv.rkt" For now, s-exp indicates that the language of world.rkt uses S-expression notation (that is, parentheses), while txtadv.rkt defines syntactic forms. Later, the S-expression and syntactic-form specifications are combined into a single name, analogous to #lang racket. Along with changing world.rkt, you can change txtadv.rkt to export everything from racket: #lang racket (provide define-verbs .... (all-from-out racket)) .... Instead of (all-from-out racket), you could use (except-out (allfrom-out racket) require) to withhold the require form from world.
Racket REF allows the implementation of custom programming languages on top of Racket.
Creating languages in Racket
CACM
Computer Science