Using Overloading to Express Distinctions Between Evaluators1

Cordelia V. Hall
Department of Computing Science,
University of Glasgow, G12 8QQ, U.K.
[email protected]

Key words: evaluator, overloading,
functional programming, abstract interpretation

Abstract. Evaluators, also called interpreters", play a variety of roles in the study of programming languages. Given this, it's surprising that we don't have a better framework for developing evaluators and specifying their relationship to each other. This paper shows that type classes in HASKELL provide an excellent framework for exploring relationships between evaluators, using abstract interpretation as a motivating example.

1. Introduction

Evaluators, also called interpreters", play a variety of roles in the study of programming languages. They define the meaning of programs [7], support the development of new language paradigms [3], relate abstract semantics of programs to the corresponding concrete semantics [2], provide debugging information [5], and yet are simple enough to teach students about the implementation of programming languages. Given this, it's surprising that we don't have a better framework for developing evaluators and specifying their relationship to each other. For example, at least two new innovations in the implementation of functional languages were expressed as subtle variations on the familiar metacircular Lisp evaluator [1]. The original Lisp evaluator developed by McCarthy implemented dynamic instead of static scoping and didn't support higher order functions. A few small changes yielded an evaluator for a statically scoped higher order language. Friedman and Wise

1To appear in Information Processing Letters