T$'e describe a refinement of ML's type system allowing the specification of recursively defined subtypes of user-defined datatypes.The resulting system of rejirzemeni f,ypes preserves desirable properties of ML such as decidability of type inference, while at the same time allowing more errors to be detected at compile-time.The type system combines abstract interpretation with ideas from the intersection type discipline, but remains closely tied to ML in that refinement types are given only to programs which are already well-typed in ML.

We discuss the design, implementation, and benchmarking of a system that can manipulate symbolic expressions represented by their straight-line computations. Our system is capable of performing rational arithmetic on, evaluating, differentiating, taking greatest common divisors of, and factoring polynomials in straight-line format. The straight-line results can also be converted to standard, sparse format. We show by example that our system can handle problems for which conventional methods lead to excessive intermediate expression swell.