Date: Tue, 10 Dec 1996 22:28:41 GMT
Server: NCSA/1.4.2
Content-type: text/html
UW Constraint-Based Languages and Systems
UW Constraint-Based Languages and Systems
Welcome to the home page for Constraints at
UW CSE.
A constraint is a relation that should be satisfied; for example, that a line
remain horizontal, that a resistor in an electrical circuit simulation
obey Ohm's Law, or that the height of a bar in a bar chart be proportional
to some number in an application program. Constraints have been used in a
variety of languages and systems, particularly user interface toolkits,
in planning and scheduling, and in simulation.
Our research is in several areas:
- constraint imperative programming, in particular the
Kaleidoscope language
- constraint logic programming, in particular the HCLP language scheme
- constraint hierarchies
- constraint solvers
- using constraints in user interface construction
People
Faculty:
Current Students:
Alumni:
- Jeffrey Berg
- Scott Bradley
- Rob Duisberg
- Bjorn Freeman-Benson, bnfb@oti.com
- Axel Kramer
- John Maloney
- Amy Martindale
- Sean McAteer, smcateer@cs.washington.edu
- David Nagy-Farkas, davidnf@cs.washington.edu
- Michael Sannella, sannella@faline.bellcore.com
- Paul Williams
- Molly Ann Wilson
- Michael Woolf
Papers
The following list contains citations for recent papers. Click on a title
to go to that paper's page, containing an abstract and a link to the
postscript file.
Constraint Imperative Programming
- Bjorn Freeman-Benson and Alan Borning,
"The Design and Implementation of
Kaleidoscope'90, A Constraint Imperative Programming Language",
Proceedings of the IEEE Computer Society 1992 International Conference
on Computer Languages, April 1992, pages 174-180.
- Bjorn Freeman-Benson and Alan Borning,
"Integrating Constraints with an
Object-Oriented Language", Proceedings of the 1992 European Conference
on Object-Oriented Programming, June 1992, pages 268-286.
- Gus Lopez, Bjorn Freeman-Benson, and Alan Borning,
"Kaleidoscope: A Constraint Imperative
Programming Language", In Constraint Programming, B. Mayoh,
E. Tougu, J. Penjam (Eds.), NATO Advanced Science Institute Series, Series
F: Computer and System Sciences, Vol 131, Springer-Verlag, 1994, pages
313-329.
- Gus Lopez, Bjorn Freeman-Benson, and Alan Borning,
"Constraints and Object
Identity", Proceedings of the 1994 European Conference on
Object-Oriented Programming, Bologna, Italy, July 1994, pages 260-279.
- Gus Lopez, Bjorn Freeman-Benson, and Alan Borning,
"Implementing Constraint Imperative
Programming Languages: the Kaleidoscope'93 Virtual Machine",
Proceedings of the 1994 ACM Conference on Object-Oriented Programming
Systems, Languages, and Applications, Portland, Oregon, October 1994, pages
259-271.
Hierarchical Constraint Logic Programming
- Alan Borning, Michael Maher, Amy Martindale, and Molly Wilson,
"Constraint Hierarchies and Logic
Programming", Proceedings of the Sixth International Logic Programming
Conference, Lisbon, Portugal, June 1989, pages 149-164.
- Molly Wilson and Alan Borning,
"Extending HCLP Languages: Nonmonotonicity and Inter-Hierarchy
Comparison", Proceedings of the 1989 North American Logic Programming
Conference, Cleveland, October 1989, pages 3-19.
- Molly Wilson and Alan Borning, "Hierarchical
Constraint Logic Programming", The Journal of Logic Programming,
special issue on Constraint Logic Programming, Vol. 16 Nos. 3 & 4,
July-August 1993, pages 227-318.
- Molly Ann Wilson, "Hierarchical Constraint
Logic Programming", PhD dissertation, April 1993.
Constraint Solvers
- Michael Sannella, "The SkyBlue
Constraint Solver", UW tech report 92-07-02.
- Michael Sannella, John Maloney, Bjorn Freeman-Benson, and Alan
Borning, "Multi-way versus One-way
Constraints in User Interfaces: Experience with the DeltaBlue
Algorithm", Software--Practice and Experience, Vol. 23 No. 5, (May
1993), pages 529-566.
- Michael Sannella, "The Skyblue
Constraint Solver and Its Applications", Vijay Saraswat
and Pascal van Hentenryck, editors, Proceedings of the 1993 Workshop on
Principles and Practice of Constraint Programming, MIT Press, 1995, pages
385-406.
- Problem with SkyBlue and Cycles.
- Alan Borning and Bjorn N. Freeman-Benson,
"The OTI Constraint Solver: A Constraint
Library for Constructing Interactive Graphical User Interfaces",
Proceedings of the First International Conference on
Principles and Practice of Constraint Programming, September 1995,
pages 624-628.
- Alan Borning, Richard Anderson, and Bjorn Freeman-Benson,
"Indigo: A Local Propagation Algorithm for
Inequality Constraints", Proceedings of the 1996 ACM Symposium on
User Interface Software and Technology, pages 129-136. A companion
technical report, "The Indigo Algorithm", UW
tech report 96-05-01, contains additional material (proofs of theorems and
definitions of interval operations).
Theory of Constraint Hierarchies
- Alan Borning, Bjorn Freeman-Benson, and Molly Wilson,
"Constraint Hierarchies",
Lisp and Symbolic Computation, Vol. 5 No. 3, (September 1992), pages
223-270.
Constraints and User Interfaces
- Bjorn Freeman-Benson, "Converting an
Existing User Interface to Use Constraints", Proceedings of the
1993 ACM Symposium on User Interface Software and Technology, Atlanta,
Georgia, November 1993, pages 207-215.
- Michael Sannella and Alan Borning,
"Multi-Garnet: Integrating Multi-Way Constraints with Garnet", UW tech
report 92-07-01.
- Michael Sannella, "Analyzing and
Debugging Hierarchies of Multi-Way Local Propagation Constraints", in
Alan Borning (ed.), Proceedings of the 1994 Workshop on Principles and
Practice of Constraint Programming, Springer-Verlag, Lecture Notes in
Computer Science No. 874, pages 63-77.
- Michael Sannella, "Constraint
Satisfaction and Debugging for Interactive User Interfaces", PhD
dissertation, August 1994. Revised version published as UW Tech Report
94-09-10.
- Michael Sannella, "SkyBlue: A
Multi-Way Local Propagation Constraint Solver for User Interface
Construction", in Proceedings of the 1994 ACM Symposium on User
Interface Software and Technology, pages 137-146.
Funding
This research is currently supported in part by two grants from the
National Science Foundation:
"Constraint-Based Languages and Environments for Building Interactive
Systems", Grant No. IRI-9302249, Interactive Systems Program, and
"Constraint Imperative Programming", Grant No. CCR-9402551, Programming
Languages and Compilers Program. The work on constraint satisfaction
algorithms and libraries is supported in part by
Object Technology International.
Other Resources
We also maintain an
anonymous ftp directory at UW on
//ftp.cs.washington.edu/pub/constraints
. The
code
subdirectory contains source code for various constraint solvers and
systems, including DeltaBlue and SkyBlue. All this code is public domain.
The
ppcp94 subdirectory contains papers from the 1994 Principles and
Practice of Constraint Programming Workshop. There is a
papers subdirectory with research papers (but all of the
papers are also listed in this WWW document, so don't bother).
Finally, there is a
drafts subdirectory, which sometimes contains preliminary drafts of
papers.
For more general information on constraints, and links to lots of
interesting stuff, see the
Constraints Archive page.
borning@cs.washington.edu