Purity is not a really property of functions, but of optimizations. A pure function is simply those functions for which a "pure optimization" is desirable, and that ultimately depends on what you care about. Every impure function can become pure just by finding a context where the side-effects are moot. (Redirect all output to /dev/null and suddenly you won't care if your printf calls get elided or memoized.)

I fail to see how you couldn't specify a pure language using a pure subset of a sufficiently expressive impure language.