Foundations of Programming Languages

This is an introduction to the concepts and methodologies underlying programming languages and their connection to actual computers and - by example - algorithms. It aims to provide a firm basis for the study of computer science and is intended in particular for undergraduate students taking an introductory course in computer science. The principles of programming languages are introduced by way of a specific language called PROSA (PROgramming language SAarbrucken), which is similar to PASCAL. The authors examine the mathematical foundations, the syntax and semantics of the language and methods for determining the efficiency and rectifying the correctness of programmes. The connection between programming languages and computers is illustrated by describing a compiler which translates PROSA into the machine language of a simple computer called RESA (REchner SAarbrucken). Each part is proved correct and comparisons to other languages are given. The aim is to help the reader understand and develop those techniques and skills conducive to the efficient construction of reliable programmes. Examples, theorems and exercises are used throughout the text.