- Title: Distributed Protocols as behaviours in Erlang
Supervisor: Adrian Francalanza
Description: Erlang[1] is a parallel functional programming language that has been used commercially for a number of years to program highly-reliable distributed systems in the area of telecommunications. Behaviours are widely used, higher-order Erlang mechanisms facilitating code resue and abstraction. In essence, they permits one to decompose her code into modules where, through the use of module interfaces and the novel feature of callback obligations, one can define a form of contract between the module and the module client.
Behaviours have already been used to great effect in [2] to construct a suite of design patterns for concurrent code . In this project, we seek to extend this work by building a suite of erlang behaviours that facilitate the implementation of distributed algorithms such as 2/3 phase commits and consensus. The added challenge from [2] will be the element of distribution, which is at the heart of these behaviours. This entails for the provison and handling of failures, so as to make these behaviours fault-tolerant. The final artefact is expected to consist of:
- A suite of behaviours defining a number of widely used distributed algorithms.
- A case-study application that tests and makes use of these behaviours.
Requirements: Strong interest in distributed programming and functional programming.
Textbooks and Material:
- [1] Programming Erlang: Software for a concurrent world, Joe Armostrong, ISBN-10 193435600X
- [2] Assessing Design Patterns for Concurrency, Fikre Leguesse, BIT Final Year Project, 2009.
- [3] Distributed Algorithms. Nancy Lynch. ISBN 1-55860-348-4
- [4] Introduction to Distributed Algorithms. Gerard Tel. ISBN 0-521-7483-8.
- Title: A Pedagogic graphic Tool for Object-Based Languages
Supervisor: Adrian Francalanza
Description:
Object-based (prototype-based) languages such as Self[2], Cecil[3], JavaScript[4] and ActionScript[5] are object-oriented language which tend to be simpler and more flexible than their class-based counterparts such as Java and C#. This simplicity and flexibility makes these languages better candidates for teaching core object-oriented concepts and design features such as inheritance, delegation, dynamic dispatch, inheritance embedding, object creation and cloning. For a start, in object-based languages there is a clearer separation between object types(interfaces) and object implementations compared to class-based languages.
The tasks expected from this project can be decomposed in a number of stages. There first needs to be a survey of the existing object-based languages, categorising them according to their features. Based on this categorisation, two languages exhibiting diverse characteristics will be chosen and a Graphic Development Environment tool will then be implemented for the construction of object-based software for these two chosen languages. This tool will use a graphic notation to describe the object structure of the software system constructed and will be able to produce skeleton code for these two languages from this graphic representation. However, the main aim of this tool will be to bring forth the core object-oriented characteristics of one language compared to the other (eg. dynamic vs static inheritance, inheritance by embedding vs inheritance by delegation).
Requirements: Strong interest in object-oriented programming languages.
Textbooks and Material:
- [1] A Theory of Objects. Martin Abadi and Luca Cardelli. ISBN 0-387-94775-2.
- [2] The Self Language. http://selflanguage.org/
- [3] Cecil Home page. http://www.cs.washington.edu/research/projects/cecil/
- [4] JavaScript: The Definitive Guide. David Flanagan. ISBN 0-596-10199-6.
- [5] ActionScript Homepage. http://www.actionscript.org/
-
Title: Formalising (aspects of) Erlang
Supervisor: Adrian Francalanza
Description: Erlang is a parallel functional programming language that has been used commercially for a number of years to program highly reliable systems in the area of telecommunications.
The advent of multicore CPUs has spiralled interest for this language among many programming communities.
Widely used tutorial books such as [1] give an informal account of the Erlang language and its constructs. This project aims to formalise the behaviour a core subset of the language and compare this formalisation it against the actual Erlang implementation. This should improve the understanding of the language and act as a point of departure for further research relating to the semantics of the language.
More specifically, the tasks associated with this project are:
- Identification of a calculus, ie a core subset of the language which embodies the main features of the language. These would typically include parallelism, the mailbox synchornisation mechanism, and possibly a failure model for the language.
- Formalise the behaviour of the calculus using operational rules.
- Implement the rules, typically using a language that lends itself well to rapid prototyping (eg. Haskell)
- Compare the behaviour of the calculus with that of the actual Erlang implementation through judicious test examples.
Requirements: Interest in concurrency, programming languages and language design.
References, Textbooks and other Material:
- Programming Erlang: Software for a concurrent world, Joe Armostrong, ISBN: 193435600X
-
Title: Assessing Design Patterns for Concurrency
Supervisor: Adrian Francalanza
Description: The recent advent of cheap pervasive multi-core processors has raised concerns across the programming world because most programmers are not able to program adequately these machines and harness their true potential.
The study of Concurrency is not new. The Process Calculi community has been studying this phenomenon for the last 30 odd years, obtaining various important results. However, these results are often deemed abstract and "removed" for the working programmer. The Systems Programming community have also been successful in this regard. They have had to deal with concurrency since the inception of multiprogramming operating systems and they have constructed software that has stood the test of time (eg. Unix OS). However, the solutions proposed are often deemed too low level in nature.
The Object-Oriented Programming community, which nowadays is the main programming community, has had to deal with concurrency for some time as well.
Interestingly, it has been presenting its solutions as Design Patterns, programming idioms which have proved to be very palatable to programmers. One often wonders whether such an approach leads to solutions that are too centred around the object-oriented paradigm and which do not generalise to other paradigms used for concurrent programming such as message passing.
This project aims to investigate this question using a very pragmatic approach. We identify a number of concurrency patterns and try to apply them to a message-passing programming model.
We then asses how adequately these patterns adapted to the new programming paradigm. More concretely, the candidate is expected to:
- understand and familiarise herself with the concept of design patterns.
- Identify a number of patterns used for concurrency.
- Identify a language based around message passing such as CML, Occam or Erlang, on which the design patterns will be tested.
- Identify a case study to program in this language, while putting these design patterns to use.
- Critically asses the applicability and genericity of the patterns backing up this assessment with any experience obtained from the case study.
Requirements: Strong interest in programming methodologies, software design and concurrency.
References, Textbooks and other Material:
- Design patterns : elements of reusable object-oriented software
by Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides. Addison Wesley (1995) ISBN: 0201633612
- Design Patterns Explained: A New Perspective on Object-Oriented Design (Software Patterns) (Paperback) by Alan Shalloway, James Trott. Addison Wesley; 2 ed. (2004) ISBN: 0321247140
- Head First Design Patterns (Head First) (Paperback)
by Eric Freeman, Elisabeth Freeman, Bert Bates, Kathy Sierra, O'Reilly Media, Inc. (2004) ISBN: 0596007124
- Pattern-Oriented Software Architecture Volume 2: Patterns for Concurrent and Networked Objects (Hardcover) Douglas Schmidt, Michael Stal, Hans Rohnert, Frank Buschmann, Wiley 1 ed. (2000) ISBN: 0471606952
-
Title: A Pedagogic Tool for Predicate Logic
Supervisor: Adrian Francalanza
Description: There are usually two main uses for a logical language.
- As a deduction system (or proof system), ie. a system to construct proofs or refutations.
- As a vehicle to express statements which receive a meaning when they are given what is called an "interpretation."
The study of the first use is called Proof Theory and the study of the second use is called Model Theory. It is the interaction between these two aspects which makes logic an interesting and effective tool.
In fact, this dual view of logic has had a deep influence on various fields of Computer Science, from Artificial Intelligence, to Model Checking to the study of Programming Languages.
In this project the candidate is invited to build a pedagogic tool which assists the teaching of these logical concepts. It will initially focus on one of the simplest forms of logic, predicate logic, but may be extended to first order logic.
There are various aspects that the tool should be able to cater for and handle adequately, such as the clear delineation between syntax and semantics, the concept of multiple interpretations (models) for the same language (syntax), proof system soundness, proof system completeness, and the axiomatisation of interpretations.
The aggregation of a pool of examples highlighting these concepts and used by the tool will be considered a fundamental aspect of the project. The candidate will also be assessed on the understanding of any aspect handled by the tool constructed.
Requirements: An interest in the formal aspect of computer science. A good grasp of the logic preliminaries introduces in the Discrete Mathematics 1st year course.
References, Textbooks and other Material:
- Logic for Computer Science: Foundations of Automatic Theorem Proving. Jean Gallier, Chapters 3,4. (Out of print, but freely downloadable from http://www.cis.upenn.edu/~jean/gbooks/logic.html)
- Logic in Computer Science: Modelling and Reasoning about Systems. Michael Huth, Mark Ryan. Cambridge University Press. ISBN: 052154310X
-
Title: A Visual Editor for Haskell
Supervisor: Gordon Pace and Sandro Spina
Description:
A visual editor for Haskell exists, but unfortunately, it is not
very usable in practice. Since Haskell is a functional programming
language (and hence has no control flow - loops, conditionals,
etc), a visual editor can be very appropriate. The project aims to
produce a visual editor particularly suited for list and datatype
manipulation functions, and which handles refinement effectively,
making it usable in Haskell software development.
Requirements: Strong programming skills.
-
Title: Using Haskell as a Scripting Language for a Vector Graphics Editor
Supervisor: Gordon Pace and Joseph Cordina
Description: Various applications benefit from a scripting language, to enable the
automation of repetitive tasks - one finds programmable macros in word processors, and in
spreadsheets (eg MS Word and Excel using Visual Basic), in text editors (eg Emacs using Lisp),
CAD software (eg AutoCAD using Lisp), etc.
The aim of this project is to enhance an open-source vector-based graphics editor (eg XFig)
with a Haskell based scripting language, enabling the user to script commands which draw,
interact with the user, access the menus, etc.
Requirements: Strong programming skills.
-
Title: Teaching System Architecture Using Haskell and Lava
Supervisor: Gordon Pace
Description:
Lava is a hardware description language embedded in Haskell,
allowing elegant descriptions of regular hardware systems. The
student taking this FYP will use Lava and Haskell to create a
pedagological suite of tools for computer science students to
understand better, and experiment with the different layers in a
computer system. A simple processor defined in Lava, will allow
students to experiment with processor design. A small assembler
(built as an embedded language in Haskell) will then allow the
students to study the interaction between the machine and simple
programs. A small operating system written in the assembly
language will then abstract away the machine. A high level
language compiler will then complete the suite. Various techniques
for fast simulation and different approaches to understandable,
concise descriptions of the different modules should be explored
in this project.
Requirements: Strong programming skills.
-
Title: Optimised Compilation of Mode Automata
Supervisor: Gordon Pace
Description:
Modes are an alternative method of programming, whereby a programmer associates a particular piece of code with a particular mode (a sort of labelled state).
The programmer then specifies mode transition conditions that when met will halt the currently running mode and will continue executing the code in another mode.
In this FYP, you will be given a concrete language syntax for specifying modes and the corresponding actions within the modes and you will implement this language in Haskell (as an embedded language).
The aim of this is to investigate the translation process from the higher level syntax to actual execution code.
The next step (and most important) would be to investigate ways in which the compilation process can be optimised to generate efficient execution code.
This step can be done within or outside of Haskell as you may see fit.
Requirements: Strong programming skills.
-
Title: Strengthening C with Strong Types
Supervisor: Gordon Pace
Description:
The C language has gained wide-spread use in both academic instutions and industry. The main reason is the flexibility and efficiency provided by this language.
Functional Programmers commonly attribute the strength of the functional paradigm to the commonly associated strong type system and the availability of static type checking.
In fact, functional programmers state that most bugs are a result of type errors (something that C is not very good at capturing).
In this FYP, you will be building an extension to the C language that allows Haskell like data types to be defined in C.
Additionally you will then be able to build a static type checker (and maybe also a type inference engine), that will guarantee proper type usage.
Having a strong type system, you will also be able to enhance C to implement pattern matching on the types.
To be able to execute this Strongly-Typed-C, you will build a pre-processor that will then translate the new syntax to traditional C code, that can get be compiled using off the shelf compilers, but still maintaining all the strengths of the original specification.
Requirements:
Strong programming skills in both C and a strongly typed language (ex Haskell).
|
|