| Summary | The Game Programming
Language (GPL) is an object-based
language for specifying graphical interactive games. It was
developed specifically as a project for a compiler construction course
in which students write a GPL interpreter.
It is
expressive enough that it can be used to describe an interesting set of
games, but simple enough that it is very easy to learn. It is
particularly well suited for implementing early video games (circa
1970's). Students have used it to write simplified versions
of dozens
of games
including: Pong, Space
Invaders, Centipede, Break-Out, Frogger, and Pac
Man. The interpreter is small enough that most students at
Chico State can write it in a single semester. The language is based around animated graphical objects called game objects. Each game object has a geometry (e.g. a rectangle) that is parameterized by a set of attributes (e.g. color, size, location), and a code block, called an animation block, that changes its attributes. It provides definitions for triangle, rectangle, circle, pixmaps, and text-box game objects. Game object attributes can be initialized at instantiation time and modified at run time. (See the GPL Programmer's Manual for complete description of the language.) Students implement the interpreter in eight phases during a 15 week semester (see Project Description below). Similar to many modern interpreters, it has the front-end of a compiler (lexical, syntactic, and semantic analysis) and the back-end of a traditional interpreter (program execution). Students were given the choice of working independently or with one other student. Students are provided with C++ classes that encapsulate all the graphics, event handling, and window creation. Thus no graphics or windowing knowledge is necessary. The project has been used for three semesters. Most students like the project. Many report learning more from it then they have in any other course project. Several students remarked on the usefulness of the interpreter; they felt they had built something meaningful that they could use. On average, students felt the project was more fun, more exciting, and more engaging than previous course projects. |
| Topics | The primary topics are
compiler construction topics.
Students learn how to build the front end of a parser.
However, in our curriculum it also severs as an advanced
programming course. For many students this is the first large
project they have done and thus students often report learning more in this
class then any of their previous programming classes. |
| Audience | Junior/Senior Computer
Science majors at a typical teaching
university. |
| Difficulty | Sixty percent of
students at Chico State report this project
as the most difficult of any class project they have ever done.
Another 30% rate it as one of the hardest. About
60%
complete the project or come very close to completing it. Most of the
remaining students were only a few weeks from completion. |
| Strengths | The most important
lesson students take away from this
project is that it is feasible to invent a domain specific language.
Most students believe they will never get a job writing a
compiler and thus don't feel compiler construction courses have much
value. This project teaches them the wide applicability of
compiler construction technologies. At the end of the
semester,
most students are confident that they can use this technology to solve
problems, that is develop a new domain specific language and write an
interpreter for it. The ability to use a language to solve
problems is a valuable career skill. |
| Weaknesses | This is a large and
complex project. Students must
devote significant time in order to complete it in a single semester.
It requires about 12 lectures to fully explain the project.
The project does not touch on the compiler construction
topics of code generation and optimization. These are
important topics and it would be good to include them. |
| Dependencies | This assignment requires
that students are proficient C++
programmers and have a good understanding of object-oriented
programming. There are instances where the reference chain is
several levels deep. Students without a strong understanding
of
pointers and objects have a difficult time comprehending the long
reference chain. I provide students with C++ classes that
encapsulate all the graphics so the only graphics programming skill
necessary is to be able to place objects in a window by setting their x
and y values. Students have no trouble with this. |
| Variants | GPL was designed to
facilitate the implementation of the
interpretor. For example, it has a single global scope and
does
not support functions. It would be possible to increase the
scope
(and difficulty) of the project by extending the language. The current project does not have any code generation. In order to include code generation, the project could be altered so that students build a compiler which generates a custom byte-code instead of an interpreter. This would require that the byte-code be designed and an interpreter be written for the students. |
| Due | Title | Description | Handout |
| 2nd week | Expression Parser | Warm up exercise to learn flex/bison (GNU versions of lex/yacc) | Phase 1 |
| 3rd week | A GPL Game | Warm up exercise to introduce the language | Phase 2 |
| 4th week | Scanner & Parser | Build the scanner using flex and a skeleton of the parser using bison | Phase 3 |
| 6th week | Symbol Table | Implement a symbol table | Phase 4 |
| 9th week | Expressions | Implement a C++ tree structure to hold expressions and add actions to parser to parse expressions | Phase 5 |
| 11th week | Game Objects | Implement a C++ object to hold games objects (triangle, rectangle, etc) and add actions to parser to parse game objects | Phase 6 |
| 13th week | Statements & Event Handlers | Implement C++ objects to represent each type of GPL statement, implement the event handler class, add actions to the parser to handle both. | Phase 7 |
| 15th week | Animation Blocks | Implement the animation code blocks. | Phase 8 |
| GPL Programmer's Manual |
| Grammar |
| Interpreter Binaries (requires OpenGL and GLUT, see Getting the Software you Need) |
| Sample Games |