For years, we have enjoyed the robustness of programming without side-effects in languages such as Haskell and Mercury. Yet in order to use languages with true referential transparency, we seem to have to give up basic imperative constructs that we have become accustomed to: looping constructs, variable update, destructive update of arrays, and so on. In this thesis, we explore the design of programming languages which combine the benefits of referential transparency with imperative-style programming. First, we present a framework for classifying programming languages according to the benefits of pure programming. Our definition applies to a wider range of languages than common terms such as “declarative” and “pure,” capturing the specific benefit of prohibiting global side-effects, without ruling out imperative programming languages. Second, we present the design and implementation for a new programming language, Mars, which allows the programmer to write imperative-style code using Python syntax, yet has the benefits of a language with referential transparency. The design philosophy behind the language, and its future directions, are discussed. Third, we note the tendency for imperative programs to use array update operations, which are very slow in a naïve implementation of any language such as Mars. We explore static analyses for automatically converting slow array copying code into fast destructive update instructions, and present the design and implementation of an optimiser for Mars, which improves on previous work by precisely handling higher-order functions, including those that both accept and return functions. The sum of this work is an efficient imperative language with the demonstrable software engineering benefit of non-interfering functions.