CATEGORY: Language Processing CM or BM or SH 

Project: ?	Supervisor: PJJ 	Grading: CM=F, SH=LF, BM in-between

Implementing a simple text-processing language, TRAC

This project consists of implementing an interpreter for the text-processing language TRAC. As an example of TRAC, the following: 

	#(ds,factorial,(#(eq,x,1,1,(#(ml,x,#(cl,factorial,#(su,x,1)))))))'
	#(ss,factorial,x)'
defines the equivalent of a function, factorial, with one parameter, and: 
	#(cl,factorial,5)'
invokes it to calculate 5!.

Initially you will concentrate on implementing the kernel of the interpreter, subsequently progressing to implementing some of the other primitive operations, or maybe even designing your own. You will have to write significant test programs in TRAC at all stages of the work. Alternatively, once you have implemented sufficient of TRAC, you could concentrate on writing a significant program in TRAC itself, such as a text processor.

REFERENCES:
A short introduction to TRAC: http://www.cs.man.ac.uk/~pjj/projects/trac_doc
TRAC Language Institute http://www.trac-language.org/

CATEGORY: Language Processing CM or BM or SH 

Project: ?	Supervisor: PJJ 	Grading: CM=F, SH=LF, BM in-between

Design and Implementation of a Forth-like language

Threaded code is a technique for implementing interpreters for computer languages, and is especially suitable for reverse-polish notation. (It has nothing to do with using "threads" to get the effect of multiple processes running in parallel.) This project consists of designing and implementing a threaded code language and system based on the paper reference, available from me.

Initially you can implement any sensible subset of 'Generalisations' 1 to 11 and any 'Advanced Concepts', including those from the bibliography, such as 'defining words'. It would be reasonable to aim initially at about generalisation 8 but to design your program to be easily extended. You will have to select your own set of primitive commands, including integer arithmetic and input-output. You should expect to enhance your language by implement new facilities such as virtual memory, filestore, parallelism, data structures, or any other features to be found in computer languages.

REFERENCES:
What is threaded code: http://www.complang.tuwien.ac.at/forth/threaded-code.html
Kogge P.M. An Architectural Trail to Threaded-Code Systems IEEE computer March 1982 pp22-31

CATEGORY: Language Processing SH 

Project: ?	Supervisor: PJJ 	Grading: UF

A debugger for lex and yacc

The second-year language/compiler course, CS2111, uses lex and yacc in most of the lab exercises. Despite being specially designed for creating compilers and the like, lex and yacc are relatively low-level languages and (like assembly languages) do not give much assistance to users. They are particularly unhelpful to new users, such as the students taking CS2111! This can be seen, for example, in the superficial and often incomprehensible error messages that users get, compared to the actual problems in their code, and the way that many errors are not reported until the resulting C code is compiled, and then are rarely reported in terms of the original lex or yacc programs.

The aim of this project is to create a debugger that can read programs intended for lex and yacc, find any errors in them, and sensibly report them to the user. For users to get the full benefit from the debugger, it needs to check that names are being used consistently, both within the lex or yacc, and across the interface between the two.

The debugger will be somewhat like the "lint" program, which can be used to check C programs, even when they are distributed across several files. In fact, it might be useful to run lint on the C programs created by lex and yacc from the user's programs, but this would not report errors in terms of the original source code, and would not help with problems detected by lex and yacc themselves.

If time permits, a possible entension of this project would be to create a second program, somewhat like "cdecl" for C type-declarations, that can translate (in either or both directions) between grammar rules intended for lex and/or yacc and simple english (or some other user-friendly format). A good test would be to try to translate between the description of the DFSA format and the corresponding grammar for the 5th lab exercise.

REFERENCES:
man lint
CS2111 lab - hints for understanding error messages: http://www.cs.man.ac.uk/~pjj/cs2111/debug.html
man cdecl
CS2111 lab exercise 5 - the description of the dfsa format: http://www.cs.man.ac.uk/~pjj/cs2111/ex5_grammar.html
COURSE PREREQUISITES: CS2111 (or perhaps CS3041) would be a big help, but is not absolutely necessary

CATEGORY: Language Processing CM, BM or SH 

Project: ?	Supervisor: PJJ 	Grading: LF

lex and yacc substitutes for Java

The second-year language/compiler course, CS2111, uses lex and yacc in most of the lab exercises. However, these tools are specifically designed to be compatible with C, and we expect to make more use of Java over the next few years. There are several alternatives to lex and yacc that are compatible with Java - some are direct replacements, some are very different but with similar functionality. The aim of this project is investigate these various alternatives, and in particular to redo the various examples and exercises. The ultimate objective is to decide which of the available tools should be used in a future version of CS2111. It may be that more than one such tool is picked, as there are examples of several different classes of parser-generators available (e.g. bottom-up, like yacc, or top-down), and CS2111 could discuss their relative merits.

An obvious extension of this project would be to use the chosen tool to solve a bigger problem. One possibility would be to re-implement one of the programs I use to process student or timetable information, currently written in C.

REFERENCES:
CS2111: http://www.cs.man.ac.uk/~pjj/cs2111/index.html
available tools are listed at: http://www.first.gmd.de/cogent/catalog/java.html
COURSE PREREQUISITES: CS2111 (or perhaps CS3041) would be a big help, but is not absolutely necessary
EQUIPMENT: Java

CATEGORY: Language Processing SH or BM or CM 

Project: ?	Supervisor: PJJ 	Grading: C

Translating between computer languages using Java

Rainbow, LARD and Balsa are all languages used for designing asynchronous hardware in this department. To make the tools associated with each language available to all users, we would like to have translators available that can convert between these languages. For purely selfish reasons, we would prefer to translate everything to Rainbow, but it may well turn out to be easier to translate from Rainbow to other languages. Whichever particular translation is chosen, we would like the translator to be written in Java, using the available parser-generator tools (similar to lex and yacc). Because of the intrinsic difficulties of translating between high-level languages, we really only expect a 95% translation, with the most difficult aspects being reported to the user for intelligent action. Note: although these languages are used for hardware design, and Rainbow is designed for use with formal methods, neither of these aspects should significantly affect this project.

Another similar project - translating Balsa to VHDL - is available from Doug Edwards.

REFERENCES:
Rainbow: http://www.cs.man.ac.uk/fmethods/projects/AHV-PROJECT/ahv-project.html
LARD: http://www.cs.man.ac.uk/amulet/projects/lard/
COURSE PREREQUISITES: CS2111 (or perhaps CS3041) would be a big help, but is not absolutely necessary
EQUIPMENT: Java

CATEGORY: Information Systems SH or CM or BM 

Project: ?	Supervisor: PJJ 	Grading: SH=LF, CM=F, BM in-between

Assessing Student Assessment

We spend a lot of time assessing students, and we put a lot of effort into ensuring that this process is fair and error-free, but we have done little to assess the usefulness of the results of this assessment. A previous project, using XForms and C, has created software that can input sets of exam marks, plot them (e.g. frequency or cumulative frequency graph) and calculate some simple statistics for an individual exam (e.g. mean and standard deviation) or for pairs of exams (e.g. correlation). The objective of this project is to enhance the facilities of the existing program and use them to investigate some real but anonymous marks. Some of the questions that need to be answered before we can really understand how well we are assessing students are:

If there is time, a possible extension of this project would be to investigate the correlation between A-level and university results, or between one year's results and the next.

Here are some more ideas and references

COURSE PREREQUISITES: some knowledge of statistics would be a help, but is not essential.

CATEGORY: Human Computer Interface SH or BM or CM 

Project: ?	Supervisor: PJJ 	Grading: F

Automatic timetabling using GATT

Timetabling for this department is currently performed with the minimum of computer assistance, only capable of detecting problems in the timetable I create, rather than creating it for me. GATT is a general-purpose program for generating timetables, developed at Edinburgh University. I would like to use GATT to automatically create the timetables for this department. However, because it is general-purpose, GATT has a very simple-minded control language, and it requires some very verbose problem-description files.

This project has two main objectives:

I would expect these two objectives to be pursued in parallel, incrementally modifying the user interface to add new details to the data files, and seeing how GATT handles the change. For example, it might be sensible to initially to block out the lab times and then simply timetable the lectures, ignoring examples classes, tutorials, and the detailed scheduling of labs. We could even initially ignore factors like the size of lectures and rooms, and the availability of lecturers. It may be sensible to start by using as much of my existing timetabling system as possible (e.g. for checking and viewing the resulting timetables) and so simply translate between the file formats used by it and by GATT.

REFERENCES:
GATT: http://www.dai.ed.ac.uk/staff/personal_pages/emmah/et.html

CATEGORY: General Applications SH or BM or CM 

Project: ?	Supervisor: PJJ 	Grading: F

Creating the departmental timetable

Timetabling for this department is very difficult and currently performed with the minimum of computer assistance. The major difficulty seems to be that it is only just possible to satisfy some of the constraints - e.g. the number of hours of lectures that must be in 1.1 is only slightly less than the number of hours in the week that it can be used. However, because of this, I have found that a heuristic for creating the timetable is to identify these constraints, pick the tightest, and resolve it before proceeding to the next tightest constraint. In practice, the major constraints on our departmental timetable seem to be:

There is also significant interaction between these 3 constraints - e.g. almost by definition, lectures that most or all students in a year need to be able to attend are usually those that need to be in 1.1. However, picking lab times to overlap with the maximum number of non-computer lectures seems to work. A final difficulty is that the second constraint has to be checked for all combinations of groups of students that attend various lectures e.g., when are all but CM students available, all but CSwBM, all but CM and CSwBM, etc..

The aim of this project is to produce a system that inputs information about the constraints on rooms and student availability, and outputs details about how tight each of them is, both alone and in combination, so that I can determine the order in which I should deal with them.


CATEGORY: Simulation SH or CM or BM 

Project: ?	Supervisor: PJJ 	Grading: C

Artificial Life

I have always been interested in the way in which human communities and economies develop, originally because I wanted to create imaginary countries to fight wargames in, but nowadays as a way of understanding history. In the past few years, simulations by social scientists, economists, archeologists and historians have progressed to the point where this almost seems a feasible, but long-term goal. This aim of this project is to investigate what has already been done, and then pick an interesting and relevant (i.e. computer-science) aspect of this work to follow up. Remember that this is only a third year project, and it is quite reasonable to reimplement an existing piece of work in a better way, e.g. in Java to make it more easily available.

REFERENCES: The easiest starting points are articles from:
New Scientist 4th October 1997: http://www.newscientist.co.uk/ns/971004/features.html
Discovery Channel: http://www.discovery.com/area/science/life/digitalplayroom.html
Science News: http://www.sciencenews.org/sn_arch/11_23_96/bob1.htm
Here are some more detailed references: