String Pool Interning Saves the Weakly Separable Day

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 [cci lang=”java”]String.equals[/cci] in a separable method, like the [cci lang=”java”]Env.get(String y)[/cci] method that does an environment look-up, because [cci lang=”java”]String.equals[/cci] wasn’t declared separable itself. That’s why I used the [cci lang=”java”]==[/cci] operator in the initial Lint interpreter I wrote for the PLDI 2010 paper:

[cc lang=”java”]public static separable Env ext(final Env env,
final String x,
final Code v) {
return new Env() {
public separable Code get(String y) {
// error: if (x.equals(y))
if (x==y)
return v;
return env.get(y);
} [/cc]

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:

[cc lang=”java”]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|>));[/cc]

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

[cc lang=”java”]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|>));[/cc]

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

[cc lang=”java”]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 eval(Env e) {
return e.get(_s);
public static class Definition {
private String _name;
private Code _v;
public Definition(String name, Code 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 value() { return _v; }

This was a whole lot simpler and cleaner than making some kind of exception for [cci lang=”java”]String.equals[/cci].


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