Implementing Operational Semantics
Supervisor: Roy Crole (rlc3)
This project requires familiarity with either a functional or object oriented programming language. If you enjoyed CO2008 Functional Programming you are likely to enjoy this project which is ideally suited to coding in a functional style; however coding in OO style is also quite acceptable. A short version of this project is also ideal for a 20 credit Maths and Computer Science project.
Aims of Project
Programming languages can be specified at different levels of abstraction. At the lowest level we have processor microprogramming, and at the highest we have programming languages such as Haskell and Java. A method known as structured operational semantics (SOS) allows computer scientists to describe the syntax (written language) and semantics (the meaning or execution behaviour) of high level languages, without concern for the complication of low level machine detail. In fact, a SOS amounts to a description of an interpreter.
The aim of this project is to study a simple high level language (let's call it L) by describing L using a SOS, and then implementing the SOS-interpreter for L within a real language such as C++, JAVA or Haskell.
Challenges presented by the project
This is a reasonably challenging project, but the reward will be learning a great deal about the ways in which high level languages can be defined, and the ways in which they execute. Also, this project ties up very well with the module CO3008, Semantics of Programming Languages. The key challenges are to understand how a collection of syntax "rules" can be used to give a high level description of run-time behaviour; and how to turn such rules into interpreter code.
- An account of the SOS of a simple language L.
- Review of an appropriate programming language in which the SOS will be implemented.
- The construction of a parser for L.
- The implementation of the SOS-interpreter for L (this will be a substantial part of the project).
Nature of End-Product
Implementation of SOS-interpreter, including a user friendly interface. The inputs will be simple L programs, and the outputs will be illustrations of the execution of the L program.
Review/learn an appropriate programming language, study the SOS of a small high level language L, specify and design the SOS-interpreter.
Implement the SOS-interpreter, build a GUI, and write up project report.
References can be obtained from Dr. Roy Crole.