[m-dev.] Re: summer scholarships - please send project descriptions to me _this week_

[Zoltan Somogyi]

On 04-Sep-2005, Aaron Harwood <aharwood at cs.mu.OZ.AU> wrote:
> Just a friendly reminder to send the project descriptions when you  
> have them.

Here they are. There is a sixth project, constraint-based mode analysis,
that we want to offer to just one person (Richard Fothergill, who started
on it last summer and did very nice job) that consequently doesn't
need a description; we will tell him about its availability directly.

Zoltan.

<hr>
<h3>
Mercury bindings to graphics libraries
</h3>
<p>
There are many libraries out there dealing with graphics.
Some are designed for creating, processing and displaying pictures;
some are designed for handling dialog boxes, checkbuttons
and all the other elements of graphical user interfaces (GUIs).
Most of these are implemented in C or C++.
A Mercury program that wants to use one of these libraries
needs a Mercury *binding* to that library.
For each C function in the C library,
the Mercury binding provides a Mercury function or predicate
that does what the corresponding C function does.
<p>
Some Mercury bindings are very simple.
The translation they provide is very literal,
each Mercury function or predicate
mimicking the C function as closely as the differences in language allow.
Implementing these bindings is relatively simple,
since the Mercury foreign language interface
makes calling C code from Mercury code quite simple.
(If necessary, C++ code can then be called from C.)
<p>
Other bindings are more sophisticated.
C/C++ libraries are often far too easy to misuse.
For example, if a function takes three integer arguments,
with one being the id of an object,
another being a count of the number of times to replicate the object,
and the third being the number of pixels between the replicas,
calls that pass the arguments in the wrong order
won't be detected by the C/C++ compiler;
they will just yield nonsensical results when executed.
A good Mercury binding would make
those three arguments have three different types,
to enmake that any errors can be picked up at compile time.
<p>
The project task would start by selecting,
in consultation with the Mercury team,
an application (such as a data structure browser in the Mercury debugger)
and an existing library that would be helpful in implementing that application.
It would then provide a Mercury binding to that library:
first a simple, direct binding,
and then (as time permits) a more sophisticated one.
<p>
<i>Supervisor:</i>zs
<p>
Preferred knowledge: good programming skills,
familiarity with a declarative language such as Haskell,
familiarity with the material taught in 371 and/or 380.
Knowledge of Mercury is not strictly required;
we will teach it to a qualified candidate.
We will also supply papers describing
the design of graphics libraries for declarative languages.

<hr>
<h3>
Intermodule inlining for Mercury
</h3>
<p>
One way compilers can speed up programs is by performing inlining,
which replaces a call to function with the definition of the function.
This has two benefits.
<ul>
<li>
First, it avoids the costs of the call,
which include
the jump to the called function,
the return jump back to the calling function, and
the allocation and initialization of the called function's stack frame.
<li>
Second, while the called function must be written
to cope with any possible value for its input arguments,
the calling function often knows
what the values of these input arguments will be.
This often allows the inlined version of the function definition
to be simplified.
For example, if the function tests whether the argument N is less than 10,
that test is unnecessary and can be optimized away
if the caller knows that N=20.
</ul>
<p>
The main limitation on the use of inlining
is that frequently the caller and the callee are in different modules.
Any compiler that compiles one module at a time
must employ some extra, nonstandard mechanism
to gain access to the code of the called function
when compiling the module containing the caller.
The Mercury system has a draft implementation of such a mechanism:
the intermodule optimization framework,
which is intended to support many different program analyses and optimizations.
The project task is to use the framework to implement intermodule inlining,
and to fix any problems with the framework encountered during this process.
<p>
<i>Supervisor:</i>zs
<p>
Preferred knowledge: good programming skills,
familiarity with a declarative language such as Haskell.
Knowledge of Mercury is not strictly required;
we will teach it to a qualified candidate.
We will also supply papers describing the intermodule optimization framework.
<p>
The chosen candidate will work on and extend the Mercury compiler,
a large piece of code, so after the relevant initial introduction
he or she must be willing to become familiar
with parts of the system as the need arises,
exploring them in a self-directed manner
(though backup from the other members of the Mercury project
is always available).
This makes this project an excellent preparation
for a software engineering career.

<hr>
<h3>
Region based memory management for Mercury
</h3>
<p>
Like most modern programming language languages,
the Mercury implementation uses a garbage collector.
As programs execute, they allocate memory, but they don't have to free memory.
Instead, the language implementation periodically looks for allocated blocks
that do not have any pointers to them anymore,
meaning that they cannot be reached from program.
Any such blocks are garbage and can be (and are) reclaimed.
<p>
The requirement for locating all pointers
that could point to allocated memory blocks
makes garbage collection quite slow.
A new technique, region based memory management,
aims to eliminate this overhead.
It is based on the observation that
programs frequently allocate data structures
for use only by a particular part of the program.
When that part of the program is finished,
the data structures created specifically for it become garbage,
and can be freed immediately and with low overhead.
Region-based memory management analyzes programs
to find code regions such that all blocks of a particular kind
allocated inside the region have their lifetimes end at the end of the region,
thus allowing those blocks to be freed then.
The project task is to implement this analysis for Mercury programs.
<p>
<i>Supervisor:</i>zs
<p>
Preferred knowledge: good programming skills,
familiarity with a declarative language such as Haskell.
Knowledge of Mercury is not strictly required;
we will teach it to a qualified candidate.
We will also supply papers describing region based memory management
and its implementation in other systems.
<p>
The chosen candidate will work on and extend the Mercury compiler,
a large piece of code, so after the relevant initial introduction
he or she must be willing to become familiar
with parts of the system as the need arises,
exploring them in a self-directed manner
(though backup from the other members of the Mercury project
is always available).
This makes this project an excellent preparation
for a software engineering career.

<hr>
<h3>
Compiling Mercury to Erlang
</h3>
<p>
Mercury and Erlang are both declarative programming languages
designed for the construction of large, reliable, efficient programs
by teams of programmers.
They each have strengths the other lacks.
Mercury has strict compile time checks
that detect a large fraction of programmers' errors,
allowing them to be found cheaply.
Erlang is dynamically typed, requiring most errors to be found by hand.
On the other hand, Erlang is well suited to writing concurrent programs,
and the Erlang implementation allows computations running on one machine
to recover from the failure of related computations running on other machines.
<p>
The Mercury compiler already has several backends,
each translating Mercury to a particular target language;
the target languages include C, Java, MSIL (the .NET intermediate language)
and the RL (the relational language of the Aditi deductive database system).
The project is to write one more backend,
one that translates Mercury to Erlang.
The resulting system would combine the strengths of the two languages.
<p>
Since the new backend would be much more useful
if the two languages were also integrated in other ways
(e.g. if Mercury code compiled to C could call Erlang or vice versa),
this project would best suit a candidate
who wants the use the summer studentship
as an introduction to an honours project.
<p>
<i>Supervisor:</i>zs
<p>
Preferred knowledge: good programming skills,
familiarity with a declarative language such as Haskell.
Knowledge of Mercury and Erlang are not strictly required;
we will teach them to a qualified candidate.
<p>
The chosen candidate will work on and extend the Mercury compiler,
a large piece of code, so after the relevant initial introduction
he or she must be willing to become familiar
with parts of the system as the need arises,
exploring them in a self-directed manner
(though backup from the other members of the Mercury project
is always available).
This makes this project an excellent preparation
for a software engineering career.

<hr>
<h3>
Scanner and parser generators for Mercury
</h3>
<p>
Recognizing the structure of the input data
is one of the more common programming tasks.
The task is usually divide into two parts:
scanning, which recognizes primitive items such as identifiers,
and parsing, which recognizes more complex items
such as statements and functions.
Most programming environments support
the automatic construction of scanners and parsers
from descriptions of the structure of the data to be recognized.
A considerable body of theory exists to
make the construction of these tools is much easier.
The project task is to finish a partially-done scanner generator
and a partially-done parser generator that are written in Mercury
and are designed to generate Mercury code.
<p>
<i>Supervisor:</i>zs
<p>
Preferred knowledge: good programming skills,
familiarity with a declarative language such as Haskell,
familiarity with the material taught in 361.
Knowledge of Mercury is not strictly required;
we will teach it to a qualified candidate.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------