Statically Typing a Scripting Language in Java

Question

I'm building a scripting language in Java for a game, and I'm currently working on the parser. The language is to be utilized by players/modders/myself to create custom spells and effects. However, I'm having difficulty imagining how to smoothly implement static typing in the current system (a painful necessity driven by performance needs). I don't care so much if compilation is fast, but actual execution needs to be as fast as I can get it (within reason, at least. I'm hoping to get this done pretty soon.)

So the parser has next() and peek() methods to iterate through the stream of tokens. It's currently built of a hierarchy methods that call each other in a fashion that preserves type precedence (the "bottom-most" method returning a constant, variable, etc). Each method returns an IResolve that has a generic type <T> it "resolves" to. For example, here's a method that handles "or" expressions, with "and" being more tightly coupled:

protected final IResolve checkGrammar_Or() throws ParseException
{
    IResolve left = checkGrammar_And();

    if (left == null)
        return null;

    if (peek().type != TokenType.IDENTIFIER || !"or".equals((String)peek().value))
        return left;

    next();

    IResolve right = checkGrammar_Or();

    if (right == null)
        throwExpressionException();

    return new BinaryOperation(left, right, new LogicOr());
}

The problem is when I need to implement a function that depends on the type. As you probably noticed, the generic type isn't being specified by the parser, and is part of the design problem. In this function, I was hoping to do something like the following (though this wouldn't work due to generic types' erasure...)

protected final IResolve checkGrammar_Comparison() throws ParseException
{
    IResolve left = checkGrammer_Term();

    if (left == null)
        return null;

    IBinaryOperationType op;

    switch (peek().type)
    {
    default:
        return left;

    case LOGIC_LT:

        //This ain't gonna work because of erasure
        if (left instanceof IResolve<Double>)
            op = new LogicLessThanDouble();

        break;

    //And the same for these
    case LOGIC_LT_OR_EQUAL:
    case LOGIC_GT:
    case LOGIC_GT_OR_EQUAL:
    }

    next();

    IResolve right = checkGrammar_Comparison();

    if (right == null)
        throwExpressionException();

    return new BinaryOperation(left, right, op);
}

The problem spot, where I'm wishing I could make the connection, is in the switch statement. I'm already certain I'll need to make IResolve non-generic and give it a "getType()" method that returns an int or something, especially if I want to support user-defined classes in the future.

The question is:

What's the best way to achieve static typing given my current structure and the desire for mixed inheritance (user-defined classes and interfaces, like Java and C#)? If there is no good way, how can I alter or even rebuild my structure to achieve it?

Note: I don't claim to have any idea what I've gotten myself into, constructive criticism is more than welcome. If I need to clarify anything, let me know!

Another note: I know you're thinking "Why static typing?", and normally I'd agree with you-- however, the game world is composed of voxels (it's a Minecraft mod to be precise) and working with them needs to be fast. Imagine a script that's a O(n^2) algorithm iterating over 100 blocks twenty times a second, for 30+ players on a cheap server that's already barely squeaking by... or, a single, massive explosion effecting thousands of blocks, inevitably causing a horrendous lag spike. Hence, backend type checking or any form of duck-typing ain't gonna cut it (though I'm desperately aching for it atm.) The low level benefits are a necessity in this particular case, painful though it is.

Answer 1

The solution I'm going with, as some have suggested in the comments, was to separate parsing and typing into separate phases, along with using an enum to represent type as I originally felt I should.

While I appreciate Taymon's answer, I can't use it if I hope to support user defined classes in the future.

If someone has a better solution, I'd be more than happy to accept it!

Answer 2

You can get the best of both worlds by adding a method Class<T> getType() to IResolve; its implementers should simply return the appropriate Class object. (If the implementers themselves are generic, you need to get a reference to that object in the constructor or something.)

You can then do left.getType().equals(Double.class), etc.

This is entirely separate from the question of whether you should build your own parser with static typing, which is very much worth asking.