Melbourne School of Engineering Computer Science & Software Engineering

Declarative Languages

Overview

The central theme of the Declarative Languages Research Group is supporting the high-level specification of what a program should accomplish without the need to specify the low-level details of how it should be accomplished. This is a more abstract style of programming, leading to higher programmer productivity and more reliable programs.

Programming languages are the machine tools of programming. While a programming language is usually invisible to an end user, using an appropriate language for a given task has a clear impact on programmer productivity, software reliability, and cost of maintenance. There is therefore a continual effort to develop and experiment with new programming languages. Programming language research in the department covers the study of semantics, design and implementation of high-level languages, as well as programming methodology. Important programming languages have their roots here, including MU-Prolog, NU-Prolog, CLP(R), Lygon, Mercury, and HAL.

The paragraphs below describe the current activities of the group. For more detailed information, and advice about research opportunities, contact the leader of that project.

Analysis and Transformation of Programs

Program analysis is crucial for many programming tools. Optimizing compilers for high-level programming languages use sophisticated program analysis methods to discover pertinent facts about programs' runtime behaviour, to allow automatic generation of efficient programs from less efficient versions. Program analysis can also provide the programmer with feedback that may help pinpoint program errors or performance problems, or warn the user of a piece of software about possible security risks involved in its use.

Our interest in program analysis ranges from the foundational to the practical and applied. We develop program analyses together with their use in source-to-source transformation, optimizing compilers, and other programming tools. Most of our work is based on abstract interpretation or constraint-based inference methods, applied to analysis problems in the areas of functional and (constraint) logic programming.

Project Leader: Associate Professor Harald Søndergaard.

Project Members: Dr Lee Naish, Dr Peter Schachte, Dr Zoltan Somogyi, Professor Peter Stuckey.
Research Students: Khalid Al-Jasser, Amy Corman, Brian Herlihy, Mark Jones, Tariq Mahmood.
Other Collaborators: Clem Baker-Finch (ANU), Michael Codish (Ben-Gurion University), Maria Garcia de la Banda (Monash), Kim Marriott (Monash), Simon Peyton Jones (Microsoft Research), Martin Sulzmann (National University of Singapore).
Funding: This project has received funding via ARC Discovery projects, the University Grants Committee (Hong Kong), Japanese Project grants, the ARC REIF program, and the National University of Singapore ARF Grant program.

Constraint Programming

Constraint programming is the use of constraints directly within a programming language, whose underlying paradigm may be imperative, functional or logical. Constraint programming languages offer support for symbolic reasoning within a variety of 'constraint domains', such as integers, real numbers, rational trees and Booleans. They are particularly appropriate for tackling difficult combinatorial problems encountered for instance in job scheduling, timetabling, and routing which stretch conventional programming techniques beyond their breaking point.

Though constraint programming is still the subject of intensive research, it has considerable industrial usage, since it is clear that this emerging technology solves difficult problems quicker and with less development time than other approaches. Constraint programming is being used for solving difficult planning problems in large corporations such as manufacturers Michelin and Dassault, the French railway authority SNCF, airlines Swissair, SAS and Cathay Pacific, and Hong Kong International Terminals, the world's largest privately-owned container terminal.

Constraint logic programming (CLP) is the most developed of the constraint programming paradigms. CLP languages are a natural combination of logic programming and constraint programming, both of which deal with relations. In a short time, CLP has become industry's preferred constraint programming tool. CLP is ideal for interactive mathematical modelling work and for expressing complex combinatorial optimisation problems. The founding work on CLP languages was completed in the University of Melbourne and Monash University in 1987. One of the first CLP language implementations, CLP(R), which deals with constraints over real linear arithmetic, was developed at Monash around this time.

Project Leader: Professor Peter Stuckey.
Research Students: Bruce Davey, Liam Merlot, Jeremy Wazny, Lei Zheng.
Funding: This project has received funding via ARC Discovery projects, the University Grants Committee (Hong Kong), Japanese Project grants, the ARC REIF program, and the National University of Singapore ARF Grant program.

Declarative Debugging

Declarative debugging is an interactive technique that pinpoints errors using programmers' responses to queries. The program, as a logical description of what is to be computed, is held up against the programmer's replies. By asking the programmer questions or using a formal specification, the system can identify precisely where in a program a bug is located. Our research into declarative debugging has improved the original algorithms for debugging Prolog, and extended the ideas to functional and object-oriented languages.

Project Leader: Dr Lee Naish.
More Information: http://www.cs.mu.oz.au/~lee/papers/dd.html
Project Members: Zoltan Somogyi.
Research Students: Mark Brown, Ian MacLarty, Bernard Pope.

HAL

HAL is a new constraint programming language being developed jointly at the University of Melbourne and Monash University. HAL combines ideas from Mercury and constraint logic programming to create a new language. Key features of HAL are: the use of optional declarations about type, mode and determinism to allow programs to be compiled to execute very efficiently; a well-defined solver interface, allowing any kind of solver to be incorporated in the system; user-extensible dynamic scheduling allowing constraints solvers, and combinations of constraint solvers to be programmed easily and efficiently; and the ability to create efficiently implemented user-defined search strategies.

Project Leader: Professor Peter Stuckey.
More Information: http://www.csse.monash.edu.au/~mbanda/hal
Project Members: Ralph Becket, Vitaly Lagoon, David Overton.
Research Students: Greg Duck.
Other Collaborators: Maria Garcia de la Banda (Monash), Francisco Bueno (Universidad Polytecnica de Madrid), Kim Marriott (Monash), Bart Demoen (KU Leuven), Warwick Harvey (IC PARC), Christian Holzbaur (Vienna University), Fred Mesnard (Universite de La Reunion).
Funding: This project has received funding via ARC Discovery projects, and Belgian FWO projects.

Logic Programming Techniques

Though the logic programming paradigm has been in use for over twenty years, the programming methodology continues to be enriched. Work on skeletons and techniques aims at systematic development of logic programs for both novices and experts. Related to this are higher order styles of programming. Various other techniques more familiar in lazy functional, object oriented, imperative or relational database languages have been adapted to logic programming, sometimes using extensions to Prolog. Other extensions to Prolog which are motivated by programming methodology are coroutining, sound negation, types, modes and new pruning operators. The study of semantics also provides new ways of reasoning about the correctness of programs.

Project Leader: Dr Lee Naish.
More Information: http://www.cs.mu.oz.au/~lee/papers/lpt.html
Project Members: Dr Peter Schachte, Professor Leon Sterling

Mercury

Mercury is a new logic/functional programming language, which combines the clarity and expressiveness of declarative programming with advanced static analysis and error detection features. Its highly optimized execution algorithm delivers efficiency far in excess of existing logic programming systems, and close to conventional programming systems. Mercury addresses the problems of large-scale program development, allowing modularity, separate compilation, and numerous optimization/time trade-offs.

Project Leader: Zoltan Somogyi.
More Information: http://www.mercury.csse.unimelb.edu.au
Project Members: Ralph Becket, Fergus Henderson, Simon Taylor.
Research Students: Julien Fischer, Ian MacLarty, David Overton.
Other Collaborators: Maria Garcia de la Banda (Monash), Bart Demoen (KU Leuven), Warwick Harvey (IC PARC), Kim Marriott (Monash), Nancy Mazur (KU Leuven), Peter Moulder (Monash), Peter Ross (Mission Critical, Belgium), Kostis Sagonas (Uppsala University).
Funding: This project has received funding from Microsoft Corporation and ARC Discovery projects.

 

Further information:

 

top of page