Implementing Operational Semantics

Supervisor: Roy Crole (rlc3)

Prerequisites

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.

Learning Outcomes

• 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.

Project Timetable

Semester One
Review/learn an appropriate programming language, study the SOS of a small high level language L, specify and design the SOS-interpreter.

Semester Two
Implement the SOS-interpreter, build a GUI, and write up project report.

References

References can be obtained from Dr. Roy Crole.