This paper summarises the results of an extensive study into the foundations of functional logic programming with Escher. It introduces the Escher language and compares Escher to the purely functional language Haskell. Based on this study an abstract machine is proposed that supports the rewriting computational model of Escher. The machine is based on a simplified version of the Spineless Tagless G-Machine which was developed for the implementation of higher-order, lazy, purely functional languages. This paper shows how to add a representation for variables, a technique to deal with insufficiently instantiated arguments in function calls and a mechanism to handle pattern matching on function symbols. It studies how the rewrite rules that define the logical features of Escher can be implemented, and also addresses the integration of sharing into a machine model that supports rewriting in the presence of variables.