I wondered the same, until I read "Refactoring to Patterns". Then I realized that I misunderstood the pattern. I always assumed that it was about building an interpreter to handle a language external to code. But what it in fact seems to be about (in my current understanding) is making code more flexibel by making an implicite language already existing in the code explicite.
An example for an implicite language might be a set of search methods in a DAO:
searchByName("Ilja Preu�")
searchByAge(36)
searchByAgeBetween(7, 42)
searchByNameAndAge...
Replacing this by the Interpreter pattern, that code could look more like
searchBy(name("Ilja Preu�"))
searchBy(age(exactly(36)))
searchBy(age(between(7,42)))
searchBy(and(name("Ilja Preu�"),age(between(7,42))))
Note that the above still is pure
Java code - the "language" we are talking about is not a new programming language, but more like a domain language as represented by the existing methods and how they can be combined.
The Interpreter pattern allowed us to decouple the search criteria from each other, so that we can combine them in new ways without having to write a new method for each combination.