Eliminating Spurious Error Messages Using Exceptions, Polymorphism, and Higher-Order Functions

Norman Ramsey

Abstract

Many language processors make assumptions after detecting an error. If the assumptions are invalid, processors may issue a cascade of error messages in which only the first represents a true error in the input; later messages are side effects of the original error. Eliminating such spurious error messages requires keeping track of values within the compiler that are not available because of a previously detected error. Examples include symbol-table entries, types, and intermediate code.

This paper presents a discipline for tracking unavailable values and avoiding cascading error messages. The discipline extends the error monad described by Spivey and Wadler. The extension is expressed formally as a type constructor and combinators written in Standard ML. The type constructor distinguishes intermediate results that are unavailable because of a previously detected error. The combinators transform ordinary functions, which assume all intermediate results are available, into functions that silently propagate the unavailability of intermediate results. In an ML implementation, the ML type rules enforce the discipline; if the compiler writer does not account for a potentially unavailable value, the source code of the compiler does not type-check.

The cost of the discipline is negligible. In an experimental compiler, the discipline adds at most 5--10% to total compile time, and about 1% in the common case in which no errors are detected.

The full paper is available in PostScript form (456K), or you can view an automatic translation to HTML (89K), which is only slightly broken.