A definition of abstraction.

Abstract

What does it mean to say that one program is "more abstract" than another? What is "abstract" about an abstract data type? What is the difference between a "high-level" program and a "low-level" program? In this paper we attempt to answer these questions by formally defining an abstraction relation between programs which matches our intuitive ideas about abstraction. The relation is based on examining the operational semantics of the programs, expressed as a set of traces (sequences of states) from a given initial state to a possible final state.