Dr. Peter J. Knaggs: Project Ideas

The following are ideas or suggestions for projects I would like to see undertaken. They are all within the scope of an individual project. You may adopt any of these suggestions without having me as your supervisor, although they can be used as a guide to the nature of project I would be interested in supervising. If you are interested in any of these projects you can contact me at .

Compiler Related Projects

Programme Compare

This is a method of providing an automatic marking system for programming related assignments. The system will compare two source code programs, a model answer and the students submission, and provide a rating as to how similar the two programs are. It can do this by converting the source into an abstract syntax tree, and comparing the trees. In this way the order of functions, variables name, program syntax, and comments, can be ignored. Thus only the basic program structure is actually compared. This project would be partially interesting to any student interested in programming languages, and compilers.

Pretty Print

The school has now adopted a standard programming style for C, C++, and Java programs. A pretty print program is required, which would take a program source and reformat it into the new standard layout. This program could be extended to rewrite part of the program, i.e., variable names, where necessary.

Dynamic analyser (Profiler)

Dynamic analysers are tools which determine the execution path of a piece of software under test. An analyser has two parts: a code instrumenter which automatically adds extra statements to a source code to record the execution history and a back-end which calculate the test coverage and draws graphs etc. The project will implement the instrumenter for a common programming language e.g. Java (or a subset thereof), and construct a very basic back end. This is a challenging project that requires a competent programmer.

Z Interpreter

The second year students frequently have difficulty understanding or developing Z specification documents. This project would provide a tool which would read and validate a specification written in an ASCII form. The tool should be able to identify syntax errors in the Z notation and type errors within the specification.

Once the basic validation tool has been developed, the tool could be extended, or a new tool developed, which would allow the students to test their specifications. The program would allow the student to initialise and examine the state schema and execute operational schemas.

This project would be particularly well suited to students with an interest in formal notation and compilers/interpreters.

SAD: State Automaton Drawing

During the early stages of compiler design, it is frequently necessary to draw state automata. This project would develop a program capable of reading a description of a state automaton and producing the graph of the automaton. The program could be extended to process the output of the bison program which is used to convert a BNF description of a grammar into an automation. It is anticipated that the dot graph generator program would be used to produce the final graph. Thus the program would convert in the description to a form acceptable to the dot program.

Code Optimisation Related Projects

Virtual Machine Implementation

Most virtual machines (p-code, JVM, .NET, etc) are developed as stack machines, whilst most physical processors are register based systems. This project is to compare the performance of a simple virtual machine which has been optimised to use none, one, two, and three registers.

Parametric Peephole Optimiser

It is my belief that much of the optimisation which can be obtained from more traditional data analysts techniques, such as register renaming, dynamic register allocation and data flow analysis can be achieved via a simple rule-based parametric peephole optimiser. This project would be to develop two optimisers, one using traditional techniques and another using the peephole optimiser to test this belief.

The Forth Programming Environment Related Projects

MinForth

The ANS Forth standard defines a core language and a growing number of libraries. This project would be to produce a minimal implementation of the core Forth language with the intention of exploring the exact nature of a minimal Forth system. It can be written in either assembler (i386, AMD64 or ARM) using Subroutine Threaded Code or in a high level language (C, C++ or Java) using Direct Threaded Code.

NetForth: A Forth based NetBeans Plugin

The NetBeans development environment is a good example of an extensible programming framework which can be extended with additional classes implementing the appropriate interfaces. This project would be to develop an extension to the NetBeans environment which will apply the NetBeans development features, syntax highlighting, code navigation, documentation lookup, etc, to the Forth programming language.

FLint: Forth Lint

The stack based language Forth is implemented in a type-free manner, i.e., there are no types. There have been recent developments that would allow the type signature of a program to be derived from the type signatures of its constituent operations. This project is to provide a static software analysis tool (FLint) that can read a Forth source file and check the type signatures.

WinForth: A Windows/GUI API for Forth

We have access to several Forth compilers, both commercial and freeware. There is no standard method of program windows in Forth, such as Microsoft's .NET library or Sun's AWT and SWING libraries for Java. This project is to review the various Windows APIs (including wxWindows, QT, TK and GTK) in order to develop such a Forth library.

OOF: Object Orientated Forth

Since the introduction of Object Orientated programming there are been a number of suggestions as to how the Forth language may be adapted to this method. The project is to investigate what constitutes an object orientated language, rather than an object based one. Suggest how these ideas can be reconciled with the philosophy which underpins the Forth language. The end result of this work will be a survey of existing object orientated extensions to the Forth programming language. This survey could then be used as the basis for a new extension. This is a research based project.

FLiP: Forth Literate Programming

It has become common over the years to represent programs, not by giving code or code fragments, but rather using an algorithmic representation of the program or fragment.

Whilst this works well for normal imperative languages (such as C, Pascal or Java) it is difficult to represent ideas for other notations. I.e., in functional languages (such as Scheme, SML or Hope) or stack based language (such as PDF, PostScript or Forth).

This project is to try and find a mechanism similar to that used by imperative languages to represent the algorithmic approach taken by such stack based languages. The student is to develop a system that does not infringe on the developer (to an unnecessary extent) that will provide an equivalent algorithmic description of such stack based notations.

Real-Time/Embedded Systems Related Projects

Software Metrics for Real-Time/Embedded Systems

In 1988 Tom Hand attempted to apply the McCabe cyclomatic metric to a program written in Forth, a stack based language. In accordance with this metric he found that the program (an 8080 assembler) had no complexity! This is because Hand was measuring at the wrong level of abstraction. In this project the student is asked to develop a system that would allow managers to collect various metrics about the software. Having collected the metrics, we must then investigate the relationship between the metric and good software practice.

Real-Time Processor

Recent years have seen the development of a number of specialised microprocessors, designed for real-time processing. Unfortunately, these processors have had to be programmed directly in assembler. A new processor is proposed, which applies these techniques to the development of a Real-Time microcore processor capable of executing C programe code. There are three possible projects based on this processor design:

• The design and implementation of an emulator for this processor. This would act in a similar manner to spim and provide an interactive development tool for low-level (assembler based) development.
• The design and implementation of a compiler for a subset of the C language that produces code for the processor. Any number of compiler design tools could be used (LLVM, ANTLR, JavaCC, SableCC, ...). This would allow the evaluation of the processor as a C-based Real-Time Processor.
• The development of a Varilog implementation of the processor.

Formal Methods Related Projects

VDM++ type checker

Develop a tool which is capable of reading a LaTeX document which incorporates a VDM specification written using Mario Wolczko's VDM markup package. The tool should be able to identify syntax errors in the VDM notation and type errors within the specification.

VDM++ Animator

This would be a tool which could read a VDM specification written for the VDM-Tool, which would allow the user to: test the operation of the specification; view the current state; altar at the state; run the operations and functions provided by the specification. This could be either a command line or GUI based tool.

Z Interpreter

The second year students frequently have difficulty understanding or developing Z specification documents. This project would provide a tool which would read and validate a specification written in an ASCII form. The tool should be able to identify syntax errors in the Z notation and type errors within the specification.

Once the basic validation tool has been developed, the tool could be extended, or a new tool developed, which would allow the students to test their specifications. The program would allow the student to initialise and examine the state schema and execute operational schemas.

This project would be particularly well suited to students with an interest in formal notation and compilers/interpreters.

Proof Editor

To develop an interactive proof assistant. It would display the proof up to now, and then suggest what rules could be applied at this point. After the user has applied the rule, it should update its display and make a new selection.

Such a tool would be of use to students learning the use of formal argument, thus it should also understand the properties of ZF set-theory, and not just the rules of natural deduction.

FOOM: Formal Object-Orientated Methods

A number of Formal Methods have been developed which claim to work with object-oriented software development. This project would review and compare these methods. For this project the student would need to develop a specification using a traditional notation (VDM, Z, or B) and then develop an object-orientated version of the specification using these new methods, namely VDM++ and Object-Z. This will allow the student to compare the methods and assess their suitability for use in an object-orientated development life cycle.

LaTeX Document Processing System Related Projects

TeXpad

A NotePad/WordPad style What You See Is Almost What You Get (WYSIAWYG) editor for LaTeX documents. It should only use standard (LaTeX2e) commands and environments, unlike LyX which uses custom packages. The idea is that the program should be easy for non-TeXsperts to use, thus should provide a Word/Note-pad style user interface.

Bib Browser

Develop a web based program to allow users to Browse around a bibliography. The program will have to read the bibliographic database, initially in BiBTeX format. The tool should allow the user to browse the bibliography by journal, conference, book, keyword, year, author, etc.

NetLaTeX: NetBeans plugin for LaTeX

The LaTeX document processing system includes a simple but flexible macro programming language. This project would be to bring the development tools of the NetBeans development environment to the LaTeX macro programming language. Of particular interest are the syntax highlighting, code navigation, documentation lookup and refactoring facilities provided by NetBeans.

Folk Music Related Projects

Festival Planner

There are many factors involved in the planning of the festival, Artists, Venus, Stewards, not to mention different types of Events. This project would be to produce a tool that would allow festival organisers to keep track of this information. The tool should be capable of checking the integrity of the data, i.e., identify double bookings, holes in the program, etc. It should be possible to download the database into a Mobile Computing Device for use by the organisers, during the festival itself. It may be possible to extend the idea to provide web/wap access to the database.

MAN: Mutual Advertising Network

A non-profit company wants to set up an advertising network, which allows members of the network to advertise on each others web sites. This project would be to develop such a system. This would require an investigation into similar systems, and requirements analysis, in addition to the development of the application.

Song Database

In this project you are asked to fully specify, design and implement a song database. The database will hold not only the song lyric but the score and comments on them. It may also hold information about artists and what discography information as may be supplied by the artists / recording company.

The specification may include a text compression method, search method and MIDI handling. For an example of a simple version of the proposed system can be found on the Digital Tradition web page (http://www.mudcat.org/).

Operating Systems Related Projects

Linux installer package

Distributing commercial level applications for Linux is very difficult and time consuming. As all the different variants of Linux have their own way of processing thing. Normally, this involves developing an install script, or building a lot of different packages for the various package managers (deb, rpm, etc).

Where as in the Windows world, which suffers from similar problems, package builders exist, which provide the developer with the ability to provide a single file (a .exe or .msi) which will install a suitable version of the program and support files in the relevant locations for users requirements.

This project would provide such an installation builder for the Linux environment. The program would need to process a configuration file describing the application. It should then be capable of operating on most Linux environments (Ubuntu, Fedora, openSUSE, Debian, Mint, Mandriva, and BSD).

The install program will probably consist of a base program that can unpack the binary archive, interrogate the system and run a configuration script which has been constructed by the builder application.

The project has the potential of becoming a commercially viable product.

Systems Administration Related Projects

Annual Dating System

Develop a system of identifying annual events without reference to a specific date. An example of such a non-specific date would be "the first Friday before the first Sunday of September", which would be August 31^th in 2001, but September 2^nd in 2005. The project would develop a method of entering and storing such a non-specific date along with a method of calculating the date for a specific year.

Web Graph

When managing a web site is it frequently to know which parts of the site depend on other parts of the site, and which refer to others. This project is to develop a tool that will scan a web page for links and dependencies (style sheets, images). Building a list of all the resources used by a page. By scanning all the local page referenced from the page it is possible to build a list of all the pages that use a resource. These lists should then be rendered in the form of a graph (possibly using the dot graph generator program) to show the interconnections between resources. Such a tool would help the site maintainer in identifying problem areas within the site.

Teaching Related Projects

SLING: ARM Support Tool

This is a windows based program which animates the operation of a ARM system to aid the users understanding of the system. The program would have to emulate the operation of the ARM processor, and provide the user with a visual representation of the data as it moves around the processor - animate the different stages of the instruction pipeline. Initially the program need only handle the MOV and LDM instructions, more can be added as the project develops. It is envisioned that the tool should be provided to first year students to aid in there understanding of assembler.

Enterprise Computing Related Projects

Flexidoc: Flexible Document Management

A system that will manage the creation, standardisation, revision, and deployment of semi-structured documentation. Using a single data source (structured database) to generate documentation in different media (Web and Paper based). This is an extension of an existing project which has defined the requirements and developed the database structure. This project would concentrate on coding the system.

PMT: Project Management Tool

The design and production of a tool for analysing and breaking down a project into work packages (a WBS) like a Structure Chart. Hierarchical decomposition tool that not only allows the task to be described but also indicates the who, how, when, where and how much, etc. At the lowest level each activity / task could be assigned to specific individuals in the team as a list of to do's.