Java is very good at high allocation rates for short-lived objects; it's
optimized for it.  Don't believe Jon's rants, people.

I'll post the code tonight. I have not tried to reduce the line count.

My program first prints the expression, then run 10 loops with 10000000
iterations and prints the duration for each loop. At the end it prints
the final reduction. The machine is a 2.4GHz Core 2 Quad.

[* x [+ [+ [* 12 0] [+ 23 8]] y]]
1355
1281
1275
1273
1277
1284
1279
1279
1272
1274
[* x [+ 31 y]]

I'm used to Ocaml, but it looked like Haskell, so I think my simplify is
correct.

The last rule, that it should handle arbitrary precision integers made
me use BigIntegers, with int the program ran about twice as fast.

//Roger Lindsjö

[[CAVEAT: hacked together over a lunchtime or so, in no way any
 official statement of anything from anyone, etc.]]

OK, my broken-handed implementation running on a 3.06GHz Xeon with 2GB
memory (not that that matters much, since the JVM is only using the
default which is more like 64M) using FC5 with

 Java(TM) SE Runtime Environment (build 1.6.0-b105)
 Java HotSpot(TM) Client VM (build 1.6.0-b105, mixed mode, sharing)

and running (of course) with -server takes 2.498s, 2.94s, 3.002s,
for the 10000000-times loop (ie neglecting start-up times, which
according to `time` are about 0.2s). I don't know why there's so
much variability in the reported times.

Drat. OK, those times are using BigDecimal, not BigInteger, which
gets me 3.258s, 3.281s, 3.207s as the loop times. (Using plain
`int` gets those times down to 1.986s, 1.62s, 1.987s, as a measure
of the work done by the big-integer arithmetics.)

-server about halves the runtime. My initial -server-free code took
about 9s [with BigDecimal], but some straightforward optimisation work
(none of which comes close to the obvious caching cheat; just reordering
the tests and ensuring that the important values 0 and 1 were testable
with ==) reduced that.

I tried the obvious tactic of going for double-dispatches to avoid
multiple consecutive instanceof tests, but that made it /slower/,
perhaps because hotspot couldn't collapse code across method
boundaries? I don't really mind because in this case the multiple
dispatches made the code rather more long-winded than it already
was.

Count the line-size yourselves and subtract lines you deem not
relevant to the benchmark.

;;; -- code starteth here ----------------------------------

package temp;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertSame;

import java.math.BigDecimal;
import java.util.StringTokenizer;

import org.junit.Test;

/*
let rec ( +: ) f g = match f, g with
  | `Int n, `Int m -> `Int (n +/ m)
  | `Int (Int 0), e | e, `Int (Int 0) -> e
  | f, `Add(g, h) -> f +: g +: h
  | f, g -> `Add(f, g)

let rec ( *: ) f g = match f, g with
  | `Int n, `Int m -> `Int (n * / m)
  | `Int (Int 0), e | e, `Int (Int 0) -> `Int (Int 0)
  | `Int (Int 1), e | e, `Int (Int 1) -> e
  | f, `Mul(g, h) -> f *: g *: h
  | f, g -> `Mul(f, g)

let rec simplify = function
  | `Int _ | `Var _ as f -> f
  | `Add (f, g) -> simplify f +: simplify g
  | `Mul (f, g) -> simplify f * : simplify g

*/
public class SimplifyViaInstanceOf
   {    @Test public void ensureParseCompleteConstants()
       {
       assertSame( zero, parse( "0" ) );
       assertSame( one, parse( "1" ) );
       assertEquals( new Val( new BigDecimal( "17" ) ), parse( "17" ) );
       assertEquals( new Val( new BigDecimal( "1234567890" ) ), parse( "1234567890" ) );
       }
   
   @Test public void ensureParseCompleteNames()    
       {
       assertEquals( new Sym( "x" ), parse( "x" ) );
       assertEquals( new Sym( "y" ), parse( "y" ) );
       assertEquals( new Sym( "calico" ), parse( "calico" ) );
       assertEquals( new Sym( "whoot" ), parse( "whoot" ) );
       }
   
   @Test public void ensureParseSimpleExpression()
       {
       assertEquals( new Add( new Sym( "x" ), new Sym( "y" ) ), parse( "(x+y)" ) );
       assertEquals( new Add( one, new Sym( "y" ) ), parse( "(1+y)" ) );
       assertEquals( new Add( zero, new Sym( "y" ) ), parse( "(0+y)" ) );
       assertEquals( new Add( new Sym( "x" ), zero ), parse( "(x+0)" ) );
       assertEquals( new Mul( new Sym( "x" ), new Sym( "y" ) ), parse( "(x*y)" ) );
       assertEquals( new Mul( new Sym( "z" ), zero ), parse( "(z*0)" ) );
       assertEquals( new Mul( zero, new Sym( "x" ) ), parse( "(0*x)" ) );
       }
   
   @Test public void ensureParseCompoundExpression()
       {
       assertEquals( new Mul( parse( "(x+y)" ), one  ), parse( "((x+y)*1)" ) );
       assertEquals( new Mul( parse( "(x+y)" ), zero  ), parse( "((x+y)*0)" ) );
       assertEquals( new Mul( parse( "(x+y)" ), new Sym( "x" )  ), parse( "((x+y)*x)" ) );
       assertEquals( new Mul( parse( "(x+y)"), parse( "(0*1)" ) ), parse( "((x+y)*(0*1))" ) );
       }
   
   private Exp parse( String string )
       {
       StringTokenizer st = new StringTokenizer( string, "+*()", true );
       return parse( st, st.nextToken() );
       }

   private Exp parse( StringTokenizer st, String current )
       {
       char ch = current.charAt(0);
       if (ch == '(')
           {
           Exp L = parse( st, st.nextToken() );
           ch = st.nextToken().charAt( 0 );
           Exp R = parse( st, st.nextToken() );
           String ket = st.nextToken();
           if (!ket.equals( ")" )) throw new RuntimeException( "ket needed: " + ket );
           return ch == '*' ? new Mul( L, R ) : new Add( L, R );
           }
       else if (Character.isDigit( ch ))
           return Val.create( new BigDecimal( current ) );
       else if (current.equals( "*" ) || current.equals( "+" ) || current.equals( " )" ))
           throw new RuntimeException( "misplaced punctuation: " + current );
       else
           return new Sym( current );
       }

   @Test public void ensureSimplifiesAddZero()
       {
       assertEquals( parse( "x" ), parse( "(x+0)" ).simplify() );
       assertEquals( parse( "x" ), parse( "(0+x)" ).simplify() );
       }
   
   @Test public void ensureAddsLiterals()
       {
       assertEquals( parse( "3" ), parse( "(1+2)" ).simplify() );
       assertSame( zero, parse( "0+0" ).simplify() );
       }
   
   @Test public void ensureMultipliesLiterals()
       {
       assertEquals( parse( "15" ), parse( "(5*3)" ).simplify() );
       assertSame( zero, parse( "(0*0)" ).simplify() );
       assertSame( zero, parse( "(x*0)" ).simplify() );
       assertSame( zero, parse( "(0*y)" ).simplify() );
       }
   
   @Test public void ensureSimplifiesMulZero()
       {
       assertSame( zero, parse( "(x*0)" ).simplify() );
       assertSame( zero, parse( "(0*x)" ).simplify() );
       }
   
   @Test public void ensureSimplifiesMulOne()
       {
       assertEquals( parse( "x" ), parse( "(x*1)" ).simplify() );
       assertEquals( parse( "x" ), parse( "(1*x)" ).simplify() );
       }
   
   @Test public void ensureLeftAssociatesAdds()
       {
       assertEquals( parse( "((x+y)+z)" ), parse( "(x+(y+z))" ).simplify() );
       }
   
   @Test public void ensureLeftAssociatesMuls()
       {
       assertEquals( parse( "((x*y)*z)" ), parse( "(x*(y*z))" ).simplify() );
       }
   
   static abstract class Exp
       {
       abstract Exp simplify();
       }
   
   static final Val zero = new Val( BigDecimal.ZERO );
   static final Val one = new Val( BigDecimal.ONE );
   
   static class Val extends Exp
       {
       final BigDecimal val;
       
       Val( BigDecimal val ) { this.val = val; }
       
       Exp simplify() { return this; }
       
       public String toString() { return val.toString(); }
       
       public boolean equals( Object other )
           { return other instanceof Val && val.equals( ((Val) other).val ); }
       
       public static Exp create( BigDecimal d )
           { return d.equals( BigDecimal.ZERO ) ? zero : d.equals(  BigDecimal.ONE ) ? one : new Val( d ); }
       }
   
   static class Sym extends Exp
       {
       String name;
       Sym( String name ) { this.name = name; }
       Exp simplify() { return this; }
       public boolean equals( Object other )
           { return other instanceof Sym && name.equals( ((Sym) other ).name ); }
       public String toString() { return name; }
       }
   
   static abstract class Inf extends Exp
       {
       final Exp L, R;
       Inf( Exp L, Exp R ) { this.L = L; this.R = R; }
       }
   
   static class Add extends Inf
       {
       Add( Exp L, Exp R ) { super( L, R ); }
       Exp simplify()
           {
           return sum( L.simplify(), R.simplify() );
           }
       private Exp sum( Exp sL, Exp R )
           {
           if (sL ==zero) return R;
           if (R == zero) return sL;
           if (sL instanceof Val && R instanceof Val) return Val.create( ((Val) sL).val.add( ((Val) R).val ) );
           if (R instanceof Add) return sum( sum( sL, ((Add) R).L ), ((Add) R).R );
           return new Add( sL, R );
           }
       public String toString() { return "(" + L + " + " + R + ")"; }
       
       public boolean equals( Object other )
           { return other instanceof Add && same( (Add) other ); }
       
       private boolean same( Add other )
           { return L.equals( other.L ) && R.equals( other.R ); }
       }
   
   static class Mul extends Inf
       {
       Mul( Exp L, Exp R ) { super( L, R ); }        
       Exp simplify(){ return prod( L.simplify(), R.simplify() ); }
       private Exp prod( Exp L, Exp R )
           {
           if (L == zero || R ==zero) return zero;
           if (L == one) return R;
           if (R == one) return L;
           if (L instanceof Val && R instanceof Val) return Val.create( ((Val) L).val.multiply( ((Val) R).val ) );
           if (R instanceof Mul) return prod( prod( L, ((Mul) R).L ), ((Mul) R).R );
           return new Mul( L, R );
           }
       public String toString() { return "(" + L + " * " + R + ")"; }
       
       public boolean equals( Object other )
           { return other instanceof Mul && same( (Mul) other ); }
       
       private boolean same( Mul other )
           { return L.equals( other.L ) && R.equals( other.R ); }
       }
   
   public static void main( String [] args )
       {
       // [* x [+ [+ [* 12 0] [+ 23 8]] y]]
       Exp a28_8 = new Add( Val.create( new BigDecimal( 23 ) ), Val.create( new BigDecimal( 8 ) ) );
       Exp m12_0 = new Mul( Val.create( new BigDecimal( 12 ) ), Val.create( new BigDecimal( 0 ) ) );
       Exp aAB = new Add( m12_0, a28_8 );
       Exp aABY = new Add( aAB, new Sym( "y" ) );
       Exp it = new Mul( new Sym( "x" ), aABY );
       Exp itx = new SimplifyViaInstanceOf().parse( "(x*(((12*0)+(23+8))+y))" );
       System.err.println( ">> original expression: " + it );
       System.err.println( ">> original expression: " + itx );
       System.err.println( ">> simplified expression: " + itx.simplify() );
       long base = System.currentTimeMillis();
       for (int i = 0; i < 10000000; i += 1) it.simplify();
       long after = System.currentTimeMillis();
       System.err.println( ">> took " + (after - base)/1000.0 + "s" );
       }
   }

Here's another Java one.  I didn't bother with parsing an
input string because it looks like people were timing
just the time to walk the parse tree and simplify it.

I've been hesitant to post it because it feels like cheating
(and the code isn't very OO - I actually tend to think in
a different language for these puzzles and then cast the
result into Java).

Here are times on my dual-Opteron@2GHz, using BigInteger,
each run does 10,000,000 simplifications and then outputs
the original string and the simplified version (taken
from the last run):

------------------------------------------------------
time java -server Simplify 10000000 10
10000000 '[* x [+ [+ [* 12 0][+ 23 8]] y ]]' -> '[* x [+ 31 y]]':: 0.0090
10000000 '[* x [+ [+ [* 12 0][+ 23 8]] y ]]' -> '[* x [+ 31 y]]':: 0.0
10000000 '[* x [+ [+ [* 12 0][+ 23 8]] y ]]' -> '[* x [+ 31 y]]':: 0.0
10000000 '[* x [+ [+ [* 12 0][+ 23 8]] y ]]' -> '[* x [+ 31 y]]':: 0.0
10000000 '[* x [+ [+ [* 12 0][+ 23 8]] y ]]' -> '[* x [+ 31 y]]':: 0.0
10000000 '[* x [+ [+ [* 12 0][+ 23 8]] y ]]' -> '[* x [+ 31 y]]':: 0.0
10000000 '[* x [+ [+ [* 12 0][+ 23 8]] y ]]' -> '[* x [+ 31 y]]':: 0.0
10000000 '[* x [+ [+ [* 12 0][+ 23 8]] y ]]' -> '[* x [+ 31 y]]':: 0.0
10000000 '[* x [+ [+ [* 12 0][+ 23 8]] y ]]' -> '[* x [+ 31 y]]':: 0.0010
10000000 '[* x [+ [+ [* 12 0][+ 23 8]] y ]]' -> '[* x [+ 31 y]]':: 0.0
java -server Simplify 10000000 10  0.11s user 0.03s system 103% cpu 0.135 total
------------------------------------------------------

Why so fast?  Because the simplified string is built up as the parse
is constructed.  So the simplification loop just outputs the result!
I'll grant that this isn't in the spirit of things, but I couldn't see
where it was prohibited :)  After all, if you're allowed to simplify
while building the parse tree, this isn't much more of a stretch...

(Naturally, this would work when parsing of input strings is done instead
of hand-building the parse tree, as well.)

-----------------------------------------------------
import java.math.BigInteger;
import java.util.Date;

public class Simplify {

    private static BigInteger zero = new BigInteger("0");
    private static BigInteger one  = new BigInteger("1");

    private class Expr {
        public String type;
        public Expr left;
        public Expr right;
        public BigInteger iVal;
        public String sVal;

        public  Expr(int nVal) {
            type = "int";
            iVal = new BigInteger(""+nVal);
            sVal = iVal.toString();
            }

        public Expr(String var) {
            type = "var";
            sVal = var;
            }

        public Expr(String nType, Expr nLeft, Expr nRight) {
            if (nType == "+") {
                if (nLeft.eq(zero)) { mkCopy(nRight); }
                else if (nRight.eq(zero)) { mkCopy(nLeft); }
                else if ((nLeft.type == "int") && (nRight.type == "int")) {
                    type = "int";
                    iVal = nLeft.iVal.add(nRight.iVal);
                    sVal = iVal.toString();
                    }
                else lassoc(nType, nLeft, nRight);
                }
            if (nType == "*") {
                if (nLeft.eq(one)) { mkCopy(nRight); }
                else if (nRight.eq(one)) { mkCopy(nLeft); }
                else if ((nLeft.type == "int") && (nRight.type =="int")) {
                    type = "int";
                    iVal = nLeft.iVal.multiply(nRight.iVal);
                    sVal = iVal.toString();
                    }
                else lassoc(nType, nLeft, nRight);
                }
            }

        private void lassoc(String nType, Expr nLeft, Expr nRight) {
            if (nRight.type == nType) {
                type = nType;
                left = new Expr(nType, nLeft, nRight.left);
                right = nRight.right;
                sVal = "["+nType+" "+left+" "+right+"]";
                }
            else mkCopy(nType, nLeft, nRight, zero,
                    "["+nType+" "+nLeft+" "+nRight+"]");
            }

        private void mkCopy(Expr e) {
            mkCopy(e.type, e.left, e.right, e.iVal, e.sVal);
            }

        private void mkCopy(String nType, Expr nLeft, Expr nRight,
                            BigInteger nVal, String nsVal) {
            type = nType;
            left = nLeft;
            right = nRight;
            iVal = nVal;
            sVal = nsVal;
            }

        public boolean eq(BigInteger i) {
            return (type == "int") && (iVal.equals(i));
            }

        public String toString() { return sVal; }

        public String simplify() { return sVal; }
        }

    public static String simplify(Expr expr) {
        return expr.simplify();
        }

    public void runTest(int limit) {
        String s = "[* x [+ [+ [* 12 0][+ 23 8]] y ]]";
        System.out.print(""+limit+" '"+s+"' -> ");
        Expr e = new Expr("*",
                   new Expr("x"),
                   new Expr("+",
                     new Expr("+",
                       new Expr("*", new Expr(12), new Expr(0) ),
                       new Expr("+", new Expr(23), new Expr(8) ) ) ,
                     new Expr("y") ) );
        Date start = new Date();
        String newS = null;
        for (int i = 0; i < limit; ++i) {
            newS = simplify(e);
            }
        Date stop = new Date();
        System.out.println("'"+newS+"':: "+
                  (stop.getTime() - start.getTime())/1000.0);
        }

    public static void main(String[] args) {
        int limit = 10000000;
        if (args.length > 0) limit = Integer.parseInt(args[0]);
        int nRuns = 10;
        if (args.length > 1) nRuns = Integer.parseInt(args[1]);

        Simplify simplify = new Simplify();
        for (int i = 0; i < nRuns; ++i) {
            simplify.runTest(limit);
            }
        System.exit(0);
        }
    }
-----------------------------------------------------

Not at all.  Java can allocate objects very quickly;, it just peels
them off a giant contiguous block.  What takes the time is when you
have a large number of long lived objects since they have to be
enumerated each GC pass.  Short lived objects are recovered in zero
time.