New methodology for compiler design



next up previous contents
Next: Ongoing activities Up: Opportunities Previous: Why do we

New methodology for compiler design

To avoid the consequences of the situation created by the historical evolution of the conventional compilers we need to develop a new methodology for language design and implementation that while accommodating the current programming tools would allow programmers to manufacture their own languages and compilers adapted to their own machines and problem domains. Such a methodology becomes feasible if it is based on mathematical concepts of programming language and programming language translation that are independent of the computer and computer user and could be easily mastered by the programmers. Since there is already a rather long history of using the universal algebra as a framework for language specification [11] and some successful experiments on compiler modeling by algorithms for homomorphism computation [21][8] we are seeking the new methodology for language processing in the framework of universal algebras.

The difficulty in using the algebraic methodology for the development of a new technology for language processing resides in the way programming languages evolved as ``notations with which people can communicate algorithms to computers and to one another" [2] and the manner in which algebraic mechanisms have been used to specify such a notation. In other words, while the concept of a programming language evolved as a notation of well understood but unspecified computations, the compiler design is based on formal specifications of both the computations expressed by a programming language and the notation used to express these computations. The notation part of the programming language, henceforth called the syntax, was precisely described within the framework of formal languages [15]. The computations expressed by the syntax, henceforth called the semantics, have been formalized using the domain theory [14] which is a different framework. These formalizations of syntax and semantics of a programming languages allowed us to understand the compilation process and to develop current technology for programming language processing but did not mature into a formal concept of a programming language and into a mathematical model of a compiler. The cause of this state of the art might be found in the lack of a mathematical framework naturally integrating the syntax, the semantics, and the compilation process.

Recently the universal algebra is used as a specification mechanism that integrates semantics and syntax [24] but the compilation process is still controlled by automata capable to recognize the syntax of programming languages. However, we have shown [21] that universal algebra can be used as a framework that integrates programming languages and their processors and have developed a technology for implementing computing systems, TICS system, where a compiler algorithm is developed on the basis of homomorphism computation rather than on automata theory. A compiler developed with TICS system allows programmers to develop their programs incrementally and thus frees program development from the restriction of monolithic programming imposed by context-free grammars. Correctness of a compiler generated by TICS is mathematically established and program portability between languages and machines is assured by language to language translators rather then by compatibility restrictions. Our experience shows that this paradigm of compilation supports automatic generation of production quality compilers and compiler customization by the programmer thus adapting the software environment to the problem domain and hardware platform.



next up previous contents
Next: Ongoing activities Up: Opportunities Previous: Why do we