Escher(ID:1770/esc003)declarative, general-purpose language which integrates the best features of both functional and logic programming languages. It has types and modules, higher-practicalorder and meta-programming facilities, and declarative input/output. It also has a collection of system modules, providing numerous operations on standard data types such as integers, lists, characters, strings, sets, and programs. The main design aim is to combine in a practical and comprehensive way the best ideas of existing functional and logic languages, such as GOEDEL, HASKELL, and LAMBDA PROLOG. Indeed, it goes well beyond GÖDEL in it's ability to allow function definitions, it's higher-order facilities, it's improved handling definitions, it's improved handling of sets, and it's declarative I/O. It goes well beyond HASKELL in it's ability to run partly-instantiated predicate calls, a familiar feature of logic languages which provides a form of non-deterimism, and it's more flexible handling of equality. The language also has clean semantics Structures: Related languages
References: After a brief introduction to the Escher language, a framework for declaratively debugging Escher programs is presented and an implementation of this framework is illustrated by an example. The paper concludes with a discussion of the practicalities of declarative debugging and some open problems. in Machine Intelligence 15 K. Furukawa, D. Michie, and S. Muggleton (eds). Oxford University Press 1995 view details in Machine Intelligence 15 K. Furukawa, D. Michie, and S. Muggleton (eds). Oxford University Press 1995 view details in Machine Intelligence 15 K. Furukawa, D. Michie, and S. Muggleton (eds). Oxford University Press 1995 view details Introduction Escher is a general-purpose, declarative programming language that integrates the best features of both functional and logic programming languages. It has types and modules, higher-order and meta-programming facilities, concurrency, and declarative input/output. The main design aim is to combine in a practical and comprehensive way the best ideas of existing functional and logic languages, such as Haskell [PKH] and Goedel [HL94]. Indeed, Escher goes beyond Haskell in its ability to run function calls containing variables, its more flexible handling of the connectives and quantifiers, and its set processing facilities. Escher goes beyond Goedel in its provision of function definitions, its higher-order facilities, its improved handling of sets, and its provision of concurrency and declarative input/output. Originally, Escher grew out of the Goedel language by moving to a higher order logic, using equations instead of clauses as statements, and adding function definitions. However, after several years development, it has become clear that the most enlightening and appropriate way to present Escher is as an extension of Haskell, which also allows the traditional logic programming style. Syntactically, the extensions needed by Escher as compared with Haskell are rather modest. However, they imply significant changes at the implementation level, particularly in the underlying abstract machine. The extensions needed to turn a Haskell abstract machine into an Escher abstract machine are discussed in [Ede99]. An implementation of the ideas in [Ede99] based on the Brisk system [HS97] is currently underway at Bristol. I discuss here only the key ideas of the proposed extensions. There are still a number of less important points that need addressing before the proposed extensions can become fully compatible with Haskell. Most of these points arise because Escher originally began as a language independent from Haskell and with a different treatment of many issues. However, presenting Escher as an extension of Haskell necessitates changing a number of minor aspects of Escher beyond those I have already dealt with. For example, my preferred view of Escher's underlying logic, which is given in Appendix A, is somewhat different from the corresponding Haskell treatment and hence some modifications to the current version of Escher are needed. The operational semantics, given in Appendix B, has been written only in outline and needs to be made more precise. Also there are a few places where I have ignored Haskell's class system. I intend to deal with each of these issues as the Bristol implementation proceeds and the changes required become clearer. The most important extension of Escher over Haskell is the ability to reduce expressions that contain variables. This extension, together with careful handling of the quantification of local variables, is sufficient to allow Escher to subsume the traditional logic programming style. In addition, Escher provides sophisticated set-processing facilities. A set in a higher-order logic can be identified with a predicate, and hence set-processing facilities can be provided by higher-order functions whose definitions contain lambda expressions in the heads of the equations. The bulk of this paper is concerned with elaborating these extensions of Escher over Haskell and showing their utility for programming. This paper is written from a functional programming perspective. Essentially, the question I pose and answer is: What has to be added to Haskell so that it can provide the facilities made available by typical logic programming languages? For a functional programmer, I believe this question is interesting for at least two reasons. First, these extensions provide a functional programmer with new programming idioms. In particular, the provision of sets as a data type improves the expressive power of Haskell. Typically, sets are simulated by lists, but this is not usually satisfactory. Sets and lists are distinct data types with distinct properties. It is usually preferable to use precisely the data type required rather than attempt to approximate by another. An alternative approach is to provide an ADT for sets, where the sets are implemented by lists. There are well-known difficulties with this approach and, furthermore, it does not provide set abstractions. However, ultimately, the choice of sets or lists is partly a matter of taste, and it is indeed true that all the programs in this paper could, with varying degrees of difficulty, be coded successfully in Haskell. The second and, I believe, more compelling reason for a functional programmer to be interested in these extensions to Haskell is that they substantially increase the likelihood of logic programmers using (or switching to) Haskell. If one can provide the familiar logic programming style, as well as all the other sophisticated features of Haskell, the language becomes a very attractive alternative to the languages currently used by logic programmers. Thus Haskell, extended with these Escher features, could become the first widely used, integrated declarative language - a lingua franca for functional and logic programmers. Furthermore, these extensions open the way to adding constraint-solving capabilities to Haskell, thus greatly increasing the potential for industrial and commercial applications of functional programming. How should a logic programmer go about trying to appreciate the advantages of what is proposed in this paper? If the programmer knows Haskell, then the only problem is to investigate the extent to which the logic programming style is provided by Escher. Perhaps the main difference between Escher and typical logic programming languages, such as Prolog, is Escher's use of equality at the top level of a statement where Prolog uses implication. This difference means that a little massaging is needed to convert Prolog code into Escher code. However, once some experience is gained in this conversion, a logic programmer will, I believe, come to the conclusion, as I have done, that equality is easier to work with than implication. In other words, the equations of Escher are simpler and easier to write than the clauses of Prolog. For a logic programmer who does not know Haskell or any other modern functional language, the job is harder. However, once the power of types, modules, higher-order functions, and so on, is appreciated, it is very difficult to go back to Prolog! Much useful background material on the issue of integration including a comprehensive list of references up to 1994 can be found in the survey paper by Hanus [Han94]. Also a general discussion of the advantages of declarative programming can be found in the first chapter of [Llo95]. The original proposal for Escher appeared in [Llo94]. Some discussion of the motivation for the design of Escher is given in Section 2.1 of [Llo95]. More detail concerning the logic underlying Escher appears in Appendix A of [Llo95]. An approach to debugging Escher programs appears in [Llo99]. Also a discussion of concurrency in Escher is given in [Llo98]. An integrated functional logic language called Curry ([Han97], [Han99]) is also under development by a group of researchers from both functional and logic programming. It is intended to serve the same role for the declarative programming community as Haskell does for the functional community. Curry has similar facilities to Escher but uses a generalized form of narrowing as the operational semantics, whereas Escher uses rewriting. The next section introduces the key ideas of the Escher language. The third section contains a variety of programs to illustrate the Escher programming style. The fourth section shows how the extensions proposed here are incorporated into entire programs. The fifth section contains a more detailed discussion of the definitions in the Booleans module, which contains the extensions of Escher over Haskell concerning the connectives, quantifiers, and sets. The last section contains some conclusions. To make the paper self-contained, Appendix A gives a brief introduction to the logic underlying Escher and a table summarizing the notational conventions, Appendix B contains the operational semantics, and Appendix C contains the Booleans module. in Machine Intelligence 15 K. Furukawa, D. Michie, and S. Muggleton (eds). Oxford University Press 1995 view details |