The fastest way to get to something workable would have been to create a library with a bunch of utility functions that I could call from a Go program. But my goal was bigger than just me being able to script a Spelunky 2 run. Ideally I wanted to create a tool that would allow anyone with very little programming knowledge to script their own runs, and not just for Spelunky 2, but for any game! In order to achieve this, I had an idea: a custom scripting language. And thus, keyScripter was born.
In this post we're going to go into the design of the keyScripter, and have a look at how the compiler works. I've tried to keep everything fairly high-level, so as not to make the post too long. If you want to dig deeper, be sure to check out the keyScripter repo on GitHub!
While designing a language it's important to think about what you want to achieve with it, and thus what it should (and shouldn't) be able to do. For the keyScripter its only goal is to send simulated inputs to the OS, so most of the functionality is designed around making that as straightforward as possible. Since it's meant for tool-assisted speedruns, timing is also very important. It's important to note that since the focus of the language is fairly specific, it doesn't have to be general-purpose. This is also why you'll see it doesn't have any loops or conditional statements - though these might be added in the future if there's a need for them. So what does it do?
Basically the whole language revolves around 2 concepts: calling built-in functions, and what I call "timestamp blocks". Besides this there are also some parts of the language less focused on functionality, and more on making the code easier to read and write, like defining variables and custom functions, and adding comments. Finally there's the ever-argued question: static type checking or not? Let's go into all of these concepts one by one.
Most functionality of the keyScripter comes from functions that are built into the language, which allow you to send various kinds of inputs to Windows, as seen in part 2 of this series. Besides that there are some functions to print some text, or wait a certain amount of time. We'll quickly go over the functions I used for the initial implementation.
vKeyPress send virtual key events to Windows. They respectively send key down, up, and down followed by up (i.e. press) events.
sleep waits a number of milliseconds before resuming the script.
A function call looks very similar to how you would run a program from the command line. The first word is the name of the function, then a whitespace, and then all arguments (separated by whitespaces). Since it only accepts a single function call per line, we don't need semicolons, brackets, or commas.
Another important difference with other languages is that functions never return anything, and they don't have side effects, meaning everything is a pure function. While this may seem restrictive, it helps keep the language simple and easy to understand.
Soon after running some initial tests with the language, I realised that most of the events would need to be timed fairly precisely - at least to within one frame in game time. Using
sleep calls does work, but it also means that changing the timing earlier in the script would affect all other timings. I wanted to have a way to fire events on specific times, without relying on previous
sleep calls, so I added
timestamps. Within a timestamps block, each line starts with a number: the amount of milliseconds since the start of the block. The rest of the line is a function call, which is to be executed at the given time.
The above example is functionally the same as:
As you can see, the timestamp notation also helps reduce the amount of code required for the same functionality. Nice!
It's good to keep in mind that it's still not a perfect solution though. In a speedrun events that are done earlier will always have an influence on the timing of later events. But at least with the timestamps it's possible to slightly change the timing of events without having to change all subsequent code.
Reusability and Readability
The first thing that comes to mind when trying to make code more readable is comments. These are thrown away by the compiler, but help any humans reading the code to understand what's going on.
Next, there's variables. These allow you to give certain values a name, like
a for the number value 65 (
0x41, the virtual key code for the letter a). These variables can then be used when calling functions, making the code way easier to understand because you don't have to know what the specific values used are. I can just say that the variable
a is 65, and forget all about the virtual key codes.
=>) and commas. Calling a custom function works the same as for built-in functions.
An important thing to note here is that, just like built-in functions, custom functions are always pure. They can't return anything, or modify variables outside of their own scope. For example:
This will print:
The assignment to
outer doesn't get applied to the scope outside of the function. What's actually happening is that the variable get shadowed inside of the function.
As you may have noticed in the examples above, there were no special keywords for declaring variables or type information. From that you might have guessed that the language would be dynamically typed, but you'd be wrong! I did want to have a type checking system, because having a runtime error occur because of a mistmatched type halfway through a script that's been running for a while is one of the most annoying things I could think of. On the other hand, I didn't like the idea of having to declare variable and parameter types everywhere either. So the solution was straightforward enough: type inference!
Type inference means that the type of an expression is automatically detected. In the keyScripter this can be either because it's assigned a certain value, or because it's passed to a function that expects a certain type. Let's look at some examples:
Such a type inference system is definitely more work to implement in the compiler, but I feel it pays off in not having to declare types in the script. It also means you'll get an error on compile time - rather than halfway through the script - if you're using a variable in a way you're not supposed to.
The Full Picture
So with the core concepts in mind, here's an example of a sample script that uses all of those features:
That looks pretty neat if you ask me! Next, let's take a look at how a compiler actually works.
Anatomy of a Compiler
Before going in-depth on how a compiler works it's important to note that various compilers can have differences in how they work under the hood, but overall the high-level concepts are generally the same.
We'll go through each part of this process step by step, and break down how it works in keyScripter.
Turning Text into Tokens
The first step when compiling code is what's called a lexical analysis (or tokenization). This is the process of turning a string of text into a list of tokens, and is done by a lexer (also called a tokenizer).
The lexer is a dumb processor, in that it's only aware of what it's looking at right now. It's not aware of any context around the current bit of text. Unless it's given an invalid character, it'll happily continue to churn out tokens, regardless of if they're valid in that position in the source code.
For example, the following keyScripter script:
would be turned into the following tokens:
Note how the lexer also doesn't know the difference between a function or a variable. It can only tell whether something is a valid identifier or not.
Parsing the Tokens
After we get our list of tokens from the lexer, it's the parser's turn. The parser analyzes the list of tokens, and checks to see if everything actually makes sense, turning it into a syntax tree. In keyScripter the tree is less of a tree, and more of a list of instructions, but the concept is the same.
The parser is more complex than the lexer, because it needs to match certain patterns of tokens to valid patterns in the language. For example, a line starting with an identifier can be a variable assignment or a function call. If it's an assignment, the value can be an integer or string literal, a function, or another variable. During each of those steps we also need to do a bunch of error checking and handling, because the last thing we want is useless error messages!
The tokens in the example above would be turned into the following instructions (note that this is a simplified view):
After we have a syntax tree, the next step is semantic analysis. This is a process of checking whether the entire tree actually makes sense. For example: are all variables we're referencing actually defined, and do all types from values passed to function calls match the parameter types?
In the keyScripter this is not actually a separate process, but it's also done by the parser.
Executing the Instructions
Since keyScripter scripts are interpreted we don't have to worry about generating machine code or other source code. So after we tokenized our input, parsed the tokens, and analysed the tree, we're ready to execute the script! In keyScripter this is fairly straightforward, because all instructions adhere to a certain interface. We can simply call
Execute() on each instruction, one by one.
Hold on, Is It Really That Simple?
Alright, you got me. The answer to that is a bit of yes and no. On a high level, yes, it really is that simple. The process of a compiler is not actually that complicated. I did leave a lot of details out of this post though, and in reality I spent a good amount of hours trying to get everything to work nicely.
Similarly the language design went through quite a few iterations, trying to find a nice balance between making it easy to write (and read) and making it easy to parse, while also adding functionality left and right.
The complexity of a compiler also greatly depends on the complexity of the language, especially in the parsing and semantic analysis. Since the keyScripter language is fairly straightforward and not made as a general purpose language, writing the compiler was also relatively easy. But the more features a language gets, the more complex the compiler will become.
The keyScripter in Action
Recall the end of the previous post, where I mentioned I was able to put down a bomb in Spelunky? Well, thanks to the keyScripter, I'm now able to do that in just a couple of lines of code. Note that here we use
scKey functions (instead of
vKey), because Spelunky 2 uses scan codes as input, not virtual key codes.
You Made It!
If you made it this far into the post, congrats! I hope it wasn't too dense. If you're interested in looking at the keyScripter (be it for the compiler, to use it for scripting, or just for fun), it's fully open source on GitHub:
I guess I should also really answer the question: was it worth my time? This is a tough one, because objectively it cost me way more time to write the entire compiler than it would've cost me to just make an easy-to-use go library for simulating input. However, I do like that I now don't necessarily need the Go compiler to run a script. Besides, the initial goal was to make scripting these kinds of runs more accessible (even if only slightly), which I do really think I accomplished.
With that, I'll leave you with an XKCD comic I stumbled upon:
Now that I know more about how compilers work, and I've succesfully written one, I feel it's a slipperly slope to creating silly esoteric languages...
In the next post we'll dive back into Spelunky 2, my plans for actually scripting a speedrun, and the progress so far!