- A Concurrent Affair - https://www.concurrentaffair.org -

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 [1]?

I knew before that we had some problems calling String [2].equals in a separable method, like the Env.get(String [2] y) method that does an environment look-up, because String [2].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 [3]:

1
2
3
4
5
6
7
8
9
10
11
12
13
public static separable Env ext(final Env env,
                                final String [2] x,
                                final Code<Integer> v) {
    return new Env() {
        public separable Code<Integer> get(String [2] 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 [2] _s;
    public Var(String [2] 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 [2] _name;
    private Code<Integer> _v;
    public Definition(String [2] name, Code<Integer> v) {
        _name = name.intern(); // must intern here, so we can use == in the ext method above
        _v = v;
    }
    public separable String [2] 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 [2].equals.

[4] [5]Share [6]