This is the web site for the book Data, Syntax and Semantics by J V Tucker and K Stephenson.
J V Tucker is Professor of Computer Science at the University of Wales Swansea. K Stephenson is Senior Scientist at QinetiQ. She is also an Honorary Lecturer in Computer Science at the University of Wales Swansea.
At present the book is in preparation, as are these web pages. If you would like to read a draft of the book please contact one of us at:
|
J V Tucker Department of Computer Science University of Wales Swansea Singleton Park Swansea SA2 8PP United Kingdom
|
K Stephenson QinetiQ St Andrews Road Malvern WR14 3PS United Kingdom
|
Data, syntax and semantics can be found everywhere in Computer Science. Each is now an independent subject with an interesting and useful theory, and advanced practical techniques and tools. Each has many applications in the design of languages for specifying, implementing and reasoning about software. Their origins lie in mathematical logic, where the foundations of reasoning were analysed using mathematical models such as logics and idealised machines. However, the subjects have been transformed and moulded in tackling problems in the technologies of programming. In Computer Science, they find their most important applications in the creation of programming and specification languages.
This book provides an elementary introduction to these three fundamental theoretical subjects through the study of models for the design of programming and specification languages. In addition to educating students in the three theories and their applications, and laying foundations for advanced study and research, the book it aims, more generally, to
introduce students to a scientific view of computing;
train students in thinking abstractly and precisely;
develop student's experience of mathematical modelling.
The book begins by reflecting on our
understanding of data and programming languages. In the
first chapter a range of questions about languages are posed that
clearly require a major scientific investigation. The theories of
data, syntax and semantics are developed in order to answer them.
An imperative language is based on the idea that a
Program = Data + Store + Algorithm.
We describe informally a simple language called the language of
while programs over abstract data types.
This language captures the essential ideas about imperative programming and acts as a kernel language for extensions to richer languages.
After a historical account of the development of data, syntax, and semantics, in Chapter 2, we divide the work into three parts:
Data
This is an introduction to modelling data using algebras. It covers simple examples, interfaces, axiomatic specifications, advanced examples, comparing algebras using homomorphisms, and ends with a full treatment of the real numbers.
Syntax
This is an introduction to modelling rules for defining all sorts of syntax using grammars, especially context free grammars. It begins with a wide range of case studies, from URLs to programming and interface definition languages. Standard results about normal forms, pumping lemmas, etc., are used to chart the scope and limits of the context-free grammars. It ends with a study of abstract syntax using term models.
Semantics
This is an introduction to modelling the behaviour of programs using operations on states. The while language over abstract data types is studied in detail. Structural induction is introduced and extensively applied. Computation on real numbers is discussed. A virtual machine is also introduced. It ends with a study of compilation.
Each part starts with elementary material and increases gently in difficulty to a final chapter that contains material that is more advanced.
Readers must know the elements of (i) programming and (ii) discrete mathematics and logic.
The book is designed for undergraduate students in the second year of their study. Depending upon the curricula, it may be better suited for third year students, in courses that progress quickly through the elementary chapters.
The chapters from the different parts can be mixed together to provide a full study of an imperative language. However, the three parts enable the book to be used for independent accounts of data, syntax, and semantics for students of different years and different levels.
A selection of overheads in a pdf form can be downloaded here.
A selection of ideas for final year student projects that are based on the material in the book are listed here.
An important part of the education of all computer scientists should be a clear understanding of some truly basic concepts that shape the whole field. Data, syntax and semantics certainly are among those subjects. In addition the theoretical education we desire will enable the students
to enjoy a scientific view of computing, in which simple, fundamental questions are asked and answered;
to think abstractly and express themselves precisely;
to develop and comprehend mathematical models of complex phenomena.
All of these general aims are difficult to achieve...
Computer Science is in its infancy, Today's students would do well to reflect on the changes in the subject and in the working careers of people in their sixties. Students need an education that prepares them for such life of technical change and volatility. Students need to master theoretical concepts and ideas, and be comfortable dealing with abstractions, idealisations, and precision in their thinking.
The Swansea education in Computer Science has been guided by nine general Educational Aims. The subject of the book serves the needs to several of these aims.
The book has grown from lectures on programming languages at the University of Wales Swansea given by both authors. All the text has been "class tested", even the advanced chapters, but at different levels.
The primary course from which it has developed is the Theory of Programming Languages. This is a compulsory course for second year students, normally taught in the first term of the academic year. The advanced chapters have been used in other courses including Algebraic Specification of Software and Hardware.
The philosophy, the choice of material, the exposition in the text, and the suggested projects have proved to be practical and, in our opinion, successful in the education of computer scientists.
About the book ● Support for teaching ● Swansea experiences ● Philosophy