String Pool Interning Saves the Weakly Separable Day

Posted on August 31, 2010 by Mathias

I just took a swim in the string pool. Who would have thought that interning strings would be so useful for weak separability in Mint?

I knew before that we had some problems calling String.equals in a separable method, like the Env.get(String y) method that does an environment look-up, because String.equals wasn’t declared separable itself. That’s why I used the == operator in the initial Lint interpreter I wrote for the PLDI 2010 paper:

1
2
3
4
5
6
7
8
9
10
11
12
13
public static separable Env ext(final Env env,
                                final String x,
                                final Code<Integer> v) {
    return new Env() {
        public separable Code<Integer> get(String y) {
            // error: if (x.equals(y))
            if (x==y)
                return v;
            else
                return env.get(y);
        }
    };
}

This wasn’t a problem because we didn’t have a parser and were creating our ASTs using hand-written Java code. The variable names are string constants, which are always interned:

1
2
3
4
public static Program term10times20plus30 = new Program
    (new Add(new Mul(new Var("x"), new Var("y")), new Int(30)),
     new Definition("x", <|10|>),
     new Definition("y", <|20|>));

Tonight, I wrote a reflection-based S-expression parser, and now the variable names are substrings of a longer string:

1
2
3
4
public static Program parsedTerm10times20plus30 = new Program
    (parser.LintParser.parse(Exp.class, "(Add (Mul (Var x) (Var y)) (Int 30))"),
     new Definition("x", <|10|>),
     new Definition("y", <|20|>));

Substrings aren’t interned automatically, and the comparison using == fails. Fortunately, I can simply intern the strings when I create the Var AST nodes and the Definition variable bindings:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static class Var implements Exp {
    private String _s;
    public Var(String s) {
        _s = s.intern(); // must intern here, so we can use == in the ext method below
    }
    public separable Code<Integer> eval(Env e) {
        return e.get(_s);
    }
}
public static class Definition {
    private String _name;
    private Code<Integer> _v;
    public Definition(String name, Code<Integer> v) {
        _name = name.intern(); // must intern here, so we can use == in the ext method above
        _v = v;
    }
    public separable String name() { return _name; }
    public separable Code<Integer> value() { return _v; }
}

This was a whole lot simpler and cleaner than making some kind of exception for String.equals.

Share

About Mathias

Software development engineer. Principal developer of DrJava. Recent Ph.D. graduate from the Department of Computer Science at Rice University.
This entry was posted in Mint. Bookmark the permalink.

Leave a Reply