REAL: Experiments in Programming Language Design and Implementation
Note: This project was completed as a 2008-2009 Final Year Project by Eliott Bartley (report | website).
- Supervisor Dr. Joseph Kiniry
- Subject Area Programming Languages
- Pre-requisite Reasonable knowledge of software design techniques, foundations of computing (in particular, automata, languages, etc.), and high competency in at least one programming language.
- Co-requisite (things you must learn along the way) Programming language design, Type theory, operational semantics, parser design and construction, compiler construction
- Subject Coverage Programming Languages (Theory and Implementation), Compilers, Software Design and Construction
- Project Type Theory, Design & Implementation
- Hardware/Software: any PC, laptop or workstation
Description
This project focuses on the creation of a simple imperative programming language, akin to the WHILE language (1), and its (correspondingly simple, but novel) development environment (2).
The novel feature of this research project is that this new language is compiled, executed, and (optionally) statically analyzed on-the-fly as a developer writes new code and makes changes to existing code. The results of execution and static analysis are shown to the developer in real-time. These results focus on the program's dynamic state and static properties.
In particular, a program's dynamic state is summarized much like modern debuggers do today, but instead of summarizing the current state of the stack and heap, REAL summarizes the state of the stack and heap at each quiescent program state.
In addition, other semantic information is summarized to the user. The static properties of interest are data flow dependencies and assertions about program properties. For example, if the developer highlights a given variable 'v', all other variables that depend, either directly or indirectly on 'v' in the program are also highlighted.
The underlying aim of the project is to create an environment that promotes developer understanding and helps developers reason about their programs by giving immediate and visual feedback about how changes in a program's source code affect the rest of the program.
Mandatory
- [Language Design] Design an imperative garbage-collected programming language with support for (at least) assertions, literals, types, variables, arithmetic operators, loops, conditionals, and procedures.
- [Parser] Implement a parser capable of compiling the language in real-time for an interpreter.
- [Interpreter] Implement an interpreter capable of executing the program in real-time.
- [IDE] Implement a simple development environment that permits a developer to edit program code and witness program state updating in real-time at each quiescent program point.
Discretionary
- [Compound types] Add support for compound types to the language and environment.
- [Reference types] Add support for reference types to the language and environment.
- [Subtypes] Add support for subtyping to the language and environment.
- [Static checks] Add support for performing static checks of the program in real-time.
- Implement one of the following static checks:
- data flow analysis,
- information flow analysis,
- assertion validity checking, or
- weakest-precondition/strongest-postcondition generation.
- [Concurrency] Add support for execution speed optimization by executing independent statements (or subsections of statements) concurrently.
- [Memory graph] Display a graph showing how memory (stack, heap, etc.) in used at any quiescent program state.
Exceptional
- Write, submit, and publish a paper on the results.