Ok, so first of all by "Source engine scripting" I mean the in-game scripting language use in Valve's Source engine games (HL2, Portal, TF2...). The same language is also used in GoldSource and QuakeEngine games. In these games you have console commands that do a variety of things, such as controlling your character (ex: +forward to start moving forward, -forward to stop, +attack to start shooting, etc.). You can bind commands to a button (ex: bind w +forward, bind mouse1 +attack). And you can define aliases that execute a series of commands (ex: alias moveandshoot "+forward; +attack"), including settings binds and defining or redefining other aliases, including itself. When an alias is executed, it has the same effect as executing the present value of the alias. So using these you can write scripts that will do useful with a few clicks. Here is a simple example I use in TF2:
- Code: Select all
alias +attck "-det; +attack; spec_next"
alias -attck "-attack; +det"
alias +det ""
alias -det ""
alias +toggle "alias +det "+attack2"; alias -det "-attack2"; +attack2; spec_prev"
alias -toggle "alias +det ""; alias -det ""; -attack2"
bind mouse1 +attck
bind mouse2 +toggle
What this does is ensure that whenever I press mouse1, attack2 will stop (if it was previously active), and then restart when mouse1 is released. (A quick note on bind: "bind key +command" means that +command will be executed when key is pressed, and -command when key is released, but I will simplify this for my formulation below)
So anyways, that's a crash course in the language. The first thing to do is obviously to transform it into something more formal. This language is basically a function from keypresses to character controls (and other side-effectful console commands). These can be thought of as input and output tapes, respectively, that are read/written left-to-right, one character at a time (no going back, no reading/writing a position twice), where the alphabet of characters on these tapes are keypresses for input, and commands as output, but any alphabet could be used, such as a binary alphabet for simplicity. I'll also use parentheses instead of quotes for bracketing, hopefully it will be clearer (unrelated aside: The Source engine is remarkably good at parsing nested quotes). So the syntax of my more formal version of the language is something like:
bind c command: When character c is read from the input tape, execute command.
write c: Write character c to the output tape.
alias var commands: When var is executed, execute commands instead. commands is a single command, or a semi-colon separated list of commands enclosed in parentheses.
To convert my previous code example we'll use the (for both input and output) four-character alphabet "<>[]":
- Code: Select all
alias +attck ( -det; write < )
alias -attck ( write >; +det )
alias +det ()
alias -det ()
alias +toggle ( alias +det ( write [ ); alias -det ( write ] ); write [ )
alias -toggle ( alias +det (); alias -det (); write ] )
bind < +attck
bind > -attck
bind [ +toggle
bind ] -toggle
Now as an example of running this code (spaced just to highlight different corresponding sections):
- Code: Select all
Input: <> [] <[]> [<>] <[>] [<]>
Output: <> [] <[]> []<>[] <[>[] []<]>
That's my formalization. This is my speculation about the computational power of this language: The state of the machine at any time can be described the current set of binds and aliases, and if "alias var command" is a possible state of the var alias, then "alias var command" must appear in the source code (ie, you can't generate new binds or aliases at runtime), so there language is finite. I also believe you can simulate any DFA on it by using alias commands to define state transitions, outputting an accept or reject character, but I haven't really tried to show this formally. Since this has an input and output tape, it would be a finite state transducer*. According to Wikipedia, FSTs are equivalent in power to DFAs (it accepts regular languages), which answers the to my question.
So that's a lot of setup for not a lot of answer, but does it seem right? Is there anything I missed or that should be added? Any examples of regular/non-regular languages I should try to write a script for? (I've thought about (a^n)(b^n) and it should be impossible since the language is finite)
*The example code can be described as an FST with two states, state 1 and state 2: Reading reading [ transitions to state 2 (from either state), outputting [. Reading ] transitions to state 1 (from either state), outputting ]. Reading < in state 1 transitions to state 1 while outputting <. Reading < in state 2 transitions to state 2 while outputting ]<. Reading > in state 1 transitions to state 1, outputting >. Reading > in state 2 transitions to state 2, outputting >[.
