• Advertisement
  • entries
  • comments
  • views

Side Project - Om Script

Sign in to follow this  


I'm working on a side project alongside my game, a dynamically typed scripting language for execution on a virtual machine. It will become part of the game eventually but its a fun project in its own right and one that has long fascinated me. The language is named Om, after the holy symbol chanted by Buddists.

I came across an interesting problem with the latest incarnation (no pun intended) of the language the other day. Functions are fully first class objects in my language and can be assigned to variables just like any other rvalue. All variables exist on a stack - there is no concept of a global value at a fixed point in memory since one of the aims of this language was to keep a standard approach to doing everything.

But consider this:var a = 10;var f = func{ out a;};f();var b = 20;f();So 'a' is pushed on the stack, then the function is generated and 'f' is pushed on the stack, so when the function is actually generated, a is at position 0. After the assignment to 'f', 'a' is now at 1. Then we call f(), then 'b' is pushed. Now when we call 'f' again, 'a' is in a different position on the stack to when we called it the first time, due to 'b' being pushed.

Eeek! The stack positions of non-local variables is different depending on where we call the function! What an absolute nightmare.

So what I decided to do was pay a small runtime cost to keep this structure working. When the compiler creates a var, it assigns it a unique unsigned int ID which is stored in the symbol table. When the var is pushed onto the runtime stack, its ID is stored in the runtime value stack (other entities on the stack just have an invalid_uint or -1 ID).

When the compiler starts writing out a function, it pushes a marker onto the symbol stack so it can tell whether a symbol is local to the function or not. If it is, we can directly calculate the offset from the top of the stack as normal (the symbol table keeps track of locations in the compiler) but if it is a non-local, we fall back on a runtime backwards search up the stack looking for the var's ID.

This gets around all the issues at the price of some stack searching at runtime, but that's okay. This language is designed to be easy and flexible rather than necessarily fast, although I doubt the searching will take very much time since the value stack is contiguous in memory and we are just doing comparisons on unsigned ints.

I thought all was doomed when I first hit this, but I'm actually quite happy with the solution. Most of the application of this language is going to be operating on named members of objects, which is going to require a similar lookup anyway, so its no big deal that we have to do this search for non-local variables either.

Came up with a nice use of templates in the runtime as well. Binary operations (+, -, * etc) are type-resolved at runtime and have to be implemented in different ways for different combinations of types (int -> int, int -> float, string -> string etc) which would have meant a mass of code if I had to handle each operation separately.

Instead I discovered I could template the logic based on a tag struct representing the operation, then allow the compiler to cookie cutter out the code for each operation for me:#ifndef BINARYOPS_H#define BINARYOPS_Henum { AdditionType, SubtractionType, MultiplicationType, DivisionType };struct Addition { static const int type = AdditionType; static const char *name(){ return "Addition"; } };struct Subtraction { static const int type = SubtractionType; static const char *name(){ return "Subtraction"; } };struct Multiplication { static const int type = MultiplicationType; static const char *name(){ return "Multiplication"; } };struct Division { static const int type = DivisionType; static const char *name(){ return "Division"; } };template V binary_op(V a, V b){ return V(); }template<> int binary_op(int a, int b){ return a + b; }template<> int binary_op(int a, int b){ return a - b; }template<> int binary_op(int a, int b){ return a * b; }template<> int binary_op(int a, int b){ return a / b; }template<> float binary_op(float a, float b){ return a + b; }template<> float binary_op(float a, float b){ return a - b; }template<> float binary_op(float a, float b){ return a * b; }template<> float binary_op(float a, float b){ return a / b; }template bool binary_check(V a, V b, Om::Value &v){ return true; }template<> bool binary_check(int a, int b, Om::Value &v){ if(!b){ v = Om::ValueFactory::makeError("Division by zero"); return false; } return true; }template<> bool binary_check(float a, float b, Om::Value &v){ if(!b){ v = Om::ValueFactory::makeError("Division by zero"); return false; } return true; }template bool binary_operation_imp(const TypedValue &a, const TypedValue &b, TypedValue &r, Om::Value &v, State &s){ if(a.type() == Om::Int) { if(b.type() == Om::Int) { if(!binary_check(a.toInt(), b.toInt(), v)) return false; r = TypedValue(Om::Int, binary_op(a.toInt(), b.toInt())); return true; } else if(b.type() == Om::Float) { if(!binary_check(static_cast(a.toInt()), b.toFloat(), v)) return false; r = TypedValue(Om::Float, binary_op(static_cast(a.toInt()), b.toFloat())); return true; } } else if(a.type() == Om::Float) { if(b.type() == Om::Float) { if(!binary_check(a.toFloat(), b.toFloat(), v)) return false; r = TypedValue(Om::Float, binary_op(a.toFloat(), b.toFloat())); return true; } else if(b.type() == Om::Int) { if(!binary_check(a.toFloat(), static_cast(b.toInt()), v)) return false; r = TypedValue(Om::Float, binary_op(a.toFloat(), static_cast(b.toInt()))); return true; } } else if(a.type() == Om::String) { if(b.type() == Om::String) { if(T::type == AdditionType) { r = TypedValue(Om::String, s.eh.add(new StringEntity(s.entity(a.toUint()).value + s.entity(b.toUint()).value))); return true; } } } v = Om::ValueFactory::makeError(stringFormat(T::name(), " on invalid types - ", Om::typeToString(a.type()), " and ", Om::typeToString(b.type()))); return false;}template bool binary_operation(ValueStack &vs, Om::Value &v, State &s){ TypedValue b = vs.pop().value; TypedValue a = vs.pop().value; TypedValue r; if(!binary_operation_imp(a, b, r, v, s)) return false; s.dec(a); s.dec(b); vs.push(ValueData(r)); s.inc(r); return true;}#endif // BINARYOPS_HNow you can add a new binary operation by adding a few lines to this file and it all works, its resolved as much as possible at compile time and no execution time cost is paid.

I tried to template the actual binary_op<> methods so I didn't need a separate one for int, float etc but didn't seem to be able to specialise in that way, but its no big deal. The built in types for Om are just int, float, bool, string, function, object and maybe list.

I'm using deterministic destruction of reference counted resources for strings, functions and objects and so on. There is an entity heap which is basically a vector of pointers that also maintains a stack of free slots, so you can remove an entity and keep the indices of the others the same. Each entity has a reference count which is incremented whenever it is pushed onto the value stack and decremented whenever it is popped, and when a pop causes a reference count to drop to zero, the entity decrements all its children recursively then deletes and removes the entity. So no dynamic garbage collection required here.

There will ultimately be an Om::Value class which can extend the life of an entity to the lifetime of the Om::Value object, so that entities can be passed outside the scripting environment to the hosting application.
Anyway, just a couple of interesting things there. Thanks for reading.

Edit: editing posts in my phone a bad idea. Will have to repost later when at a screen
Sign in to follow this  


Recommended Comments

There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement