Gan's Runtime & Script Interpreter

[x]

Gan, do you use any languages objects?

[Gan]

I'm afraid I don't quite understand that question.

I have around 6 custom classes I've made. Runtime, ParseLine, ParseKeyword, CodeLine, CodeEquation, and Variable. Those are objects. All subclasses of the NSObject.

I'm not really using any code that's proprietary to a single language. I could port this to plain C or C++ I suppose. Would take a little bit of work though.

[x]

Do you do any lexical analysis? Do you create a token tree and "interpret" from there?

What kind of pre-processing are you doing, or are you parsing raw input?
(these questions go for Mike too, if he wants to answer)


Also, if those are objects, not just static classes, you might have a little trouble porting it to C :p but Im sure you know that.

[GMG Mike]

http://www.youtube.com/watch?v=glqlORHLbdY
I think that's 32 bit but I'm not use to Xcode 4 at all. May have done completely different compiler settings as well.

So it definitely got slower - because of the fewer registers available, but faster.

A boat load of new commands could be added to my script interpreter and this speed test would produce the same results. Commands don't influence the speed of equations or the language structure. Though a negligible slow down would occur when calling a command.

True function support would probably slow down equations.

Additional commands would most likely slow down the speed test but I still need to look at your code.

REALbasic may have additional unknown speed penalties related to objects or recursive function calling. The key to speeding up the SilverCreator runtime is to work around these speed penalties. Although honestly I think the SC interpreter is not the current bottleneck - the graphics system is.

[Gan]

Do you do any lexical analysis? Do you create a token tree and "interpret" from there?

Oh crap, I gotta pull out the dictionary.
Just a sec...
Lexic...
Aha yes. I have made a function similar. You put in a raw string and it spits out keywords from the string. Like "LET x = 1" would turn into 4 keywords, LET, x, =, 1. Of course they wouldn't be in strings, they'd be the keyword object filled with identifiers and other useful info.

My solver is a tree. The parser splits equations into chunks, linking them and stuff. Until there's only 1 equation object that links to all sorts of other equations. Like a tree. I could draw a picture to show it but I gotta get some sleep. So when the single equation goes through the solver, it sends the message on through and solves the outermost branches of the equation, folding back in until it hits the base of the equation and the equation spits out a final result. Makes it fairly efficient and fast when running code in real time.

What kind of pre-processing are you doing, or are you parsing raw input?
(these questions go for Mike too, if he wants to answer)

Yeah, raw strings go into the parser which get turned into smart keywords with further get turned into code lines and equations.

Also, if those are objects, not just static classes, you might have a little trouble porting it to C :p but Im sure you know that.

I had no idea. My knowledge is fairly lopsided.

So it definitely got slower - because of the fewer registers available, but faster.

Yeah, I think I want to do some tests in Xcode 3 cause I understand how to manipulate the compiler controls and stuff.

True function support would probably slow down equations.

I'm not sure I understand.

Additional commands would most likely slow down the speed test but I still need to look at your code.

They wouldn't. Commands are recognized before code runs. If there are no commands inside the for loop, it won't slow it down.

REALbasic may have additional unknown speed penalties related to objects or recursive function calling. The key to speeding up the SilverCreator runtime is to work around these speed penalties. Although honestly I think the SC interpreter is not the current bottleneck - the graphics system is.

Yeah, I agree.

[GMG Mike]

In SilverCreator each script is represented by a SCScript object. SCScript objects consist of 3 arrays of equal length.

commands() as UInt16
linenums() as UInt32
params() as UInt32

For each scripting instruction there will be an entry in all three arrays. Consider this one line script as compiled into our object:

command(0) = 75
linenums(0) = 5
params(0) = 1

Instructions are given numbers. Instruction 2 is string variable assignment (LET, when allocating a value to a string). Assigning a value to a number variable is Instruction 75. Which instruction to use for a LET command is determined by the line parser (which is not detailed here).

In Run mode (debugging), it's useful to know exactly what line of a script that some instruction is representing. Even though this is the first and only instruction, it was on the 5th line of the script, perhaps because the first 4 lines had some comments which we threw away. Compiled games do not store this information.

Each instruction most likely has some parameters. For instructions with no parameters (such as CLEAR to clear the text area), this would be set to 0. Otherwise, it is a reference to the position in an array of a particular SCParameters object.

The SCParameters object is nothing but an array: list() as UInt32.

For our number variable allocation, the parameters object list array would have two items. list(0) would reference directly the number variable we are assigning to.

list(1) is trickier - how do we know if we are dealing with a constant, another variable, a built in function, a user function, an array, or an expression? In this case it references a huge table. The table then tells us three things:

Type - such as, is this a constant, or a variable, or an array
Value - which constant (they are all stored in another table)? which variable (direct reference to the index position of that variable in the array)? which array?
Ptr - only used for functions and arrays. for arrays this would reference another point in the table and we have to look up all over again, because maybe they referenced the index with a constant, or another variable, or another array's value, or a function, or an expression!

Now what's interesting is the support for code blocks such as IF. An IF statement, including the ELSE block, all of the code inside, etc. is considered ONE instruction. The IF instruction has numerous parameters such as:

list(0) = left side
list(1) = sign
list(2) = right side
list(3) = are we comparing strings or numbers
list(4) = SCScript to run if the comparison was true
list(5) = SCScript to run if the comparison was false (ELSE). if no ELSE then this array index does not exist.

The SCScripts referenced by the IF instruction, would have line numbers corresponding to their original true location in the parent script. This allows perfect debugging even though we are now dealing with nested scripts.

I'm a bit tired so this isn't the best explanation. The other main object used is SCMathExpression which consists of two arrays:

signs() as byte
vars() as UInt32

There is always one less signs than vars. There is always one sign though otherwise it's stupid, we would have just referenced the var directly and not wasted time on an expression.

signs() is self explanatory, it just represents + - / * etc

vars() references the big ass table above with the param types, ptrs, values. So to add a number to an expression in parenthesis might be represented as such:

vars(0) = 4
signs(0) = whatever means add
vars(1) = 2

vars(0), would have us go to the params lookup table, where we would see that the paramtype is a constant, the paramvalue references the constant. ptr is blank

vars(1) would have us go to the lookup table again, we would see that the paramtype is a math expression, value tells us which one. ptr is not used

NewMath deals with all use of numbers in your scripts. NewMath is used recursively, when dealing with expressions.

So basically - there are no trees, although the representation in memory for some things is tree-like, it uses recursion to do the heavy lifting. This may be a bottleneck but it was also the easiest to program and understand.

Really tired so I probably screwed up at the end a bit

[x]

Cool explanation Mike and Gan! I was just wondering for two reasons. Firstly I was thinking maybe we could determine some of the reasons why they perform the way they do, and because I just started a course in compiling+syntactical analysis, and its interesting too see the different approaches.

@Mike: Thats a nice way of doing things, seems streamlined enough and easy to work with/understand! Just a random thought: Mike, couldn't you use a hash table instead of arrays? Hence making the look-ups faster? Do they support them is REALbasic?
I just thought this since I am assuming its the constant function lookups/array searching that might be slowing SC down in comparison to Gans interpreter.

@Matt: I gotta say man, I'm pretty impressed. I'm not sure if you're aware of this, but the way you handled the interpreter is in essence the "standard" (and supposedly best) way too do it. At least according to my laymans understanding. Many kudos.

[Gan]

So basically - there are no trees, although the representation in memory for some things is tree-like, it uses recursion to do the heavy lifting. This may be a bottleneck but it was also the easiest to program and understand.

Ah yeah. Before I recoded my solver, it relied solely on recursion. It'd constantly loop through the equation looking for things to solve. Made it incredibly slow. Now the parser takes care of that and there's no recursion in the solver, just a straight shot through.
At first I thought taking out recursion that it'd be quite a bit more complicated and less friendly but, that's not true. It actually is kinda easier, most of everything is chunked together in the parser instead of part in the parser, part in the solver.

Here's a little description of how it works:
User types in:

Code: [Select]

Let x = 1 + 5 - 3 * 2

Parser breaks that up into: let, x, =, 1,+,5,-,3,*,2
X is identified as a variable. This line is marked as a variable setting line. Everything after = is identified as the equation.
The parser takes that equation and sticks it into an equation parser. Which looks through and breaks the equation into equation objects:
Eq1 is 3*2
Eq2  is 1+5
Eq3 is Eq2 - Eq1
Then it realizes that the equation is all broken down into tree form and returns Eq3 as the base.
So after the parser, the runtime runs each line of code.
It realizes that the line is setting a variable, it takes the variable and the equation, Eq3, and it calls the solve function of Eq3.
Eq3 is the base so it calls solve on Eq2 and Eq1. Looks like:
Eq3 = Eq2 - Eq1
Eq3 = 6 - Eq1
Eq3 = 6 - 6
Returns 0.
Then the runtime takes the returned 0 and stores it in the variable.

There's no searching for stuff to solve, it just knows what to solve.

@Matt: I gotta say man, I'm pretty impressed. I'm not sure if you're aware of this, but the way you handled the interpreter is in essence the "standard" (and supposedly best) way too do it. At least according to my laymans understanding. Many kudos.

Thanks.


I've worked on it a bit more. So...

New Features

• LET is no longer require, can be used but makes no difference.
• +=, -=, *=, and /= have been added.

Here's the download: Gan's Runtime

Mini manual:
Making Variables

Code: [Select]

//Either form can be use
Let x = 1
or
x = 1

Let x$ = "test"
or
x$ = "test"

Variable Equations

Code: [Select]

//+=, -=, *=, and /= are supported
x = x + 5
or
x += 5

Complex Equations

Code: [Select]

//Complex equations are handled with ease.
x = (5 * (3 + 1) / 6 * 18) - 3

If Statement

Code: [Select]

//If statements and nested if statements work well.
If  x < 5 Then
x+=1
End If

For Statement

Code: [Select]

//For and nested for statements work.
For i = 1 to 5
x+=1
next

I'm thinking of adding support for comments, more commands, and rudimentary debugging but I'm not sure. But since I don't have plans for this, I'm really not sure what would be the point.

[GMG Mike]

Cool explanation Mike and Gan! I was just wondering for two reasons. Firstly I was thinking maybe we could determine some of the reasons why they perform the way they do, and because I just started a course in compiling+syntactical analysis, and its interesting too see the different approaches.

@Mike: Thats a nice way of doing things, seems streamlined enough and easy to work with/understand! Just a random thought: Mike, couldn't you use a hash table instead of arrays? Hence making the look-ups faster? Do they support them is REALbasic?
I just thought this since I am assuming its the constant function lookups/array searching that might be slowing SC down in comparison to Gans interpreter.

There aren't any array lookups really. The whole idea of the byte code/pre-interpreted system is to eliminate slow look ups.

For example, with the old interpreter I did use a hash table (called a Dictionary in REALbasic) to deal with variables. In the new byte code system, because variables are global, all variables are pre-assigned memory. All number variables are stored in one array and all string variables are stored in another array. If you only have one variable "x", then it will be assigned position 0 in the NumberVariables array. Compiled scripts have no reference to "x" at all. They reference position 0 of the NumberArrays variable. As far as this goes I don't think it could be made any faster.

You might say this wastes some memory, but consider that even a complicated game might only use a few hundred number variables. Number variables are all double precision and use 8 bytes each. Even if the game uses 500 number variables this only uses 4000 bytes memory. As far as strings go, they are variable length and REALbasic handles their management. I think REALbasic allocates some small amount of memory for each string and then uses an algorithm which doubles the memory used for each string when the string grows to run out of memory. REALbasic is not known for having the fastest strings - but it does have some of the easiest strings around with excellent Unicode support (SilverCreator supports Unicode for almost all game strings. You can write the entire game in Japanese if you wish. I think variable names/custom methods must still be ASCII.)

[GMG Mike]

Ah yeah. Before I recoded my solver, it relied solely on recursion. It'd constantly loop through the equation looking for things to solve. Made it incredibly slow. Now the parser takes care of that and there's no recursion in the solver, just a straight shot through.
At first I thought taking out recursion that it'd be quite a bit more complicated and less friendly but, that's not true. It actually is kinda easier, most of everything is chunked together in the parser instead of part in the parser, part in the solver.

Maybe you guys didn't understand. Nothing is parsed in my system anymore. The math expressions are fully parsed, but we still use recursion to solve them. Consider this expression (keeping in mind that SilverCreator still uses left to right math for historical reasons)

8 / (5 + 3) - (6 * (1 + 1)) + (5 + 3)

The expression parser receives this expression and outputs a SCMathExpression. Assume we have no previous expressions. After the parser is done, we will now have the following expressions in the list (represented in a human readable form):

MathExpressions(0) = 5 + 3

MathExpressions(1) = 1 + 1

MathExpressions(2) = 6 * MathExpressions(1)

MathExpressions(3) = 8 / MathExpressions(0) - MathExpressions(2) + MathExpressions(0)

The parser will return 3 (referencing MathExpressions(3)). We will store this in ParamValues(x). In ParamType(x) we store the value that indicates it's a MathExpression. ParamPtr is unused. "x" is then stored in list(1) for the LET command.

Now let's say we are running the script and we get the LET command which says store into variable "lard" the results of MathExpression(3). We then call NewMath which has an extremely fast solver. It just looks at two items and the sign. If one of the items is a MathExpression, then we call NewMath again (recursion).

It's the mechanism by which MathExpressions reference each other which makes it a sort of "tree" but as you can see, it's set up to optimize so we don't store any duplicate expressions (which is easy due to global variable scope).

MathExpressions are only objects because objects provide a convenient way to store arrays.

[GabrielCA]

This is all very interesting.

The talk about trees (and the pseudocode) reminded me of my own script interpreter experiment, which manages nested expressions by rewriting them in a pre-compiler phase:

Code: [Select]

x = 2/(3 *(4+5))

becomes

Code: [Select]

PS_EXP1 = 4+5
PS_EXP2 = 3 * PS_EXP1
x = 2/ PS_EXP2

Of course, this isn't very thoughtful, and my interpreter doesn't manage operator precedence.

One interesting script interpreter written by a teenager that I found out about a few months ago is "nscript". It is very well written (very readable and concise) and uses good, well-known algorithms.
Note that it is stack-based, unlike most programming languages discussed here.

Printing the sum of 253 and 561 is written, in nscript, as:

Code: [Select]

253 561 + print

It is hosted at https://github.com/nikki93/nscript

@Matt: can you put the source code of your interpreter on this site so we can look at it ?

[x]

@Gan. You could totally make a token compiler for this quite easily if you wanted.

[Gan]

@GabrielCA That's pretty neat. My equation parser works like that. It just targets the equations in operator precedence.

I'd like to post the source but (1) I'm on the road traveling and (2) I'm in the process of adding new stuff.

@X What's a token compiler?

[x]

Its a bit of an archaic/weird term, buts its what TNTbasic and Metal Basic did I think. Its not fast, but its easy to do.

Basically you bind the processed or "tokenized" script to a runtime. And tadah, its compiled. Its kind of cheating. All you would have to do is port your interpreter into a "run time" and have your "compiler" embed the script into it. Then every time the run time is executed it launches that script and works as a "compiled" executable. I managed to do it using an embedded databank in blitzmax at one point. There are other ways to do it, I've even seen some token compilers that just require you to put the source.txt file in the same folder, although IMO thats a little pointless.

EDIT: I almost forgot, since its on Mac, you could probably just add the preprocessed code as a resource file.

[GMG Mike]

Its a bit of an archaic/weird term, buts its what TNTbasic and Metal Basic did I think. Its not fast, but its easy to do.

Basically you bind the processed or "tokenized" script to a runtime. And tadah, its compiled. Its kind of cheating. All you would have to do is port your interpreter into a "run time" and have your "compiler" embed the script into it. Then every time the run time is executed it launches that script and works as a "compiled" executable. I managed to do it using an embedded databank in blitzmax at one point. There are other ways to do it, I've even seen some token compilers that just require you to put the source.txt file in the same folder, although IMO thats a little pointless.

EDIT: I almost forgot, since its on Mac, you could probably just add the preprocessed code as a resource file.

SilverCreator already does this. The SCScript object has Import and Export methods. All of the constants, and the big parameter lookup table are also written to the runtime (compiled game). SilverCreator compiled games contain no human readable scripting. The only thing you'd recognize would be the string constants, all clumped together towards the end of the runtime data file.

When the game is started it reads all of this back into the appropriate SCScripts, SCMathExpressions, SCParameters, etc. in the exact same order and your game runs. That is why it is not possible to have an Eval function in SilverCreator anymore.