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.cs.mu.oz.au/mercury/
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.

 

Selected Publications, 2001-2004

    Edited Collections

  1. P. Stuckey (Ed.) Proceedings of the Eighteenth International Conference on Logic Programming. Lecture Notes in Computer Science Volume 2401. Springer-Verlag, 2002.
  2. Y. Kameyama and P. Stuckey (Eds.) Proceedings of the 7th International Symposium on Functional and Logic Programming, Nara, Japan. Lecture Notes in Computer Science Volume 2998. Springer-Verlag, April 2004.

    Chapters in Books

  3. M. Codish and H. Søndergaard. Meta-circular abstract interpretation in Prolog. In T. Mogensen, D. Schmidt and I. Sudborough (Eds). In The Essence of Computation: Complexity, Analysis, Transformation, Lecture Notes in Computer Science Volume 2566, pp.109-134. Springer, Berlin, 2002.
  4. L. Sterling. Computational logic: logic programming and beyond. A. Kakas and F. Sadri (Eds). In Patterns for Prolog Programming. pp. 374-401. Springer Verlag, Berlin, 2002.

    Journal Articles

  5. C. Baker-Finch, K. Glynn and S. Peyton Jones. (2004) Constructed product result analysis for Haskell. Journal of Functional Programming 14(2) pp.211-245.
  6. S. Barker and P. Stuckey. (2003) Flexible access control policy specification with constraint logic programming. ACM Transactions on Information and System Security 6(4) pp.501-546.
  7. B. Davey, N. Boland and P. Stuckey. (2002) Efficient intelligent backtracking using linear programming. INFORMS Journal of Computing 14(4) pp.373-386.
  8. W. Harvey and P. Stuckey. (2003) Improving linear constraint propagation by changing constraint representation. Constraints, 8(2) pp.173-207.
  9. W. Harvey, P. Stuckey and A. Borning. (2002) Fourier elimination for compiling constraint heirarchies. Constraints, 7 pp.199-219.
  10. K. Marriott, P. Stuckey, V. Tam and W. He. (2003) Removing Node Overlapping in graph layout using constrained optimization. Constraints 8(2) pp.143-171.
  11. P. Schachte. (2003) Precise goal-independent abstract interpretation of constraint logic programs. Theoretical Computer Science 293(3) pp.557-577

    Conference Publications

  12. M. De La Banda, P. Stuckey and J. Wazny. Finding All Minimal Unsatisfiable subsets. In Proceedings of the 5th ACM SIGPLAN Conference on Principles and Practice of Declarative Programming pp.32-43 Uppsala, Sweden, August 2003.
  13. C. Cheung, J. Lee and P. Stuckey. Box constraint collections for adhoc constraints. In Principles and Practice of Constraint Programming Lecture Notes in Computer Science Volume 2833 pp.214-228 Kinsale, Ireland, October 2003.
  14. C. Choi, J. Lee and P. Stuckey. Propagation redundancy in redundant modelling. In Proceedings of Principles and Practice of Constraint Programming, Lecture Notes in Computer Science Volume 2833 pp.229-243 Kinsale, Ireland, October 2003.
  15. G. Duck, P. Stuckey, M. De La Banda and C. Holzbaur. Extending arbitrary solvers with constraint handling rules. In Proceedings of the 5th ACM SIGPLAN Conference on Principles and Practice of Declarative Programming pp.79-90 Uppsala, Sweden, August 2003.
  16. G. Duck, S. Peyton Jones, P. Stuckey, M. Sulzmann. Sound and decidable type inference for functional dependencies. In Proceedings 13th European Symposium on Programming pp.49-63, Barcelona, March 2004.
  17. V. Lagoon, F. Mesnard and P. Stuckey. Termination analysis with types is more accurate. In Logic Programming, Lecture Notes in Computer Science Volume 2916 pp.254-268 Mumbai, India, December 2003.
  18. K. Marriott, P. Stuckey and M. Sulzmann. Resource usage verification. In Programming Languages and Systems, Lecture Notes in Computer Science Volume 2895 pp.212-229 Beijing, China, November 2003.
  19. L. Merlot, N. Boland, B. Hughes and P. Stuckey. A hybrid algorithm for the examination timetabling problem. In Practice and Theory of Automated Timetabling IV Lecture Notes in Computer Science Volume 2740 pp.207-231 Gent, Belgium, August 2003.
  20. L. Naish. Approximating the success set of logic programs using constrained regular types. In Proceedings of the 26th Australasian Computer Science Conference pp.61-67 Adelaide, Australia, February 2003.
  21. B. Pope and L. Naish. A program transformation for debugging Haskell'98. In Proceedings of the 26th Australasian Computer Science Conference pp.227-236 Adelaide, Australia, February 2003.
  22. B. Pope and L. Naish. Practical aspects of declarative debugging in Haskell'98. In Proceedings of the 5th ACM SIGPLAN Conference on Principles and Practice of Declarative Programming pp.230-240 Uppsala, Sweden, August 2003.
  23. P. Stuckey, M. Sulzmann and J. Wazny. The chameleon type debugger. In Proceedings of the 5th International Workshop on Automated Debugging pp.247-260 Ghent, Belgium, September 2003.
  24. P. Stuckey, M. Sulzmann and J. Wazny. Interactive type debugging in Haskell. In Proceedings of the ACM SIGPLAN 2003 Haskell Workshop pp.72-83 Uppsala, Sweden, August 2003.
  25. P. Stuckey and L. Zheng. Improving nogood recording using 2SAT. In Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence pp.94-99 Sacremento, USA, November 2003.
  26. Z. Somogyi. Idempotent I/O for safe time travel. In Proceedings of the 5th International Workshop on Automated Debugging pp.13-24 Ghent, Belgium, September 2003.
  27. M. Wybrow, K. Marriott, L. McIver and P. Stuckey. The usefulness of constraints for diagram editing. In Proceedings of the 2003 Australasian Computer Human Interaction Conference pp.192-201 Brisbane, Australia, November 2003.

 

top of page