Constraint Imperative Programming

Information

Martin Grabmüller: Constraint Imperative Programming, Diploma thesis, Technische Universität Berlin, February 2003.

130 pages, format DIN A4, English.

Abstract

Constraint-based programming languages are declarative programming languages. In constraint programs, the solutions of a problem are obtained by specifying their desired properties, whereas in imperative programs, the steps which lead to a solution must be defined explicitly, rather than being derived automatically from the specification. This work deals with the design and implementation of a programming language which integrates declarative constraints and imperative constructs in order to form a powerful programming paradigm suitable for solving a wide range of problems.

Table of Contents

• 1 Introduction
• 1.1 Motivation
• 1.2 Background
• 1.3 Goals
• 1.4 Outline
• 1.5 Notation
• 2 Constraint Programming
• 2.1 Introduction to Constraints
• 2.2 Constraints and Constraint Programming Languages
• 2.2.1 Definitions
• 2.2.2 Constraint Domains
• 2.2.3 Solving and Optimization Strategies
• 2.2.4 Constraint Hierarchies
• 2.3 Constraint Language Implementations
• 2.3.1 Constraint Logic Programming
• 2.3.2 Constraint Functional Programming
• 2.3.3 Constraint Imperative Programming
• 2.4 Industrial Applications
• 3 Constraint Imperative Programming
• 3.1 Constraint Imperative Languages and Systems
• 3.1.1 COOL
• 3.1.2 Alma-0: Embedded Search
• 3.1.3 Kaleidoscope
• 3.1.4 JACK
• 3.1.5 DJ: Declarative Java
• 3.1.6 Constraint Libraries
• 3.1.7 Other Systems
• 3.2 Imperative and Declarative Language Characteristics
• 3.3 Constraints in an Imperative Environment
• 4 Turtle - a Constraint Imperative Language
• 4.1 Requirements
• 4.2 Library or Language Integration
• 4.3 The Base Language
• 4.4 Constraint Programming Extensions
• • 4.4.1 Constrainable Variables
  • 4.4.2 Constraint Statements
  • 4.4.3 User-defined Constraints
  • 4.4.4 Constraint Store and Solver
• 4.5 Language Description for Turtle
• 4.5.1 Variables and Functions
• 4.5.2 Statements and Expressions
• 4.5.3 Data Types
• 4.5.4 The Module System
• 4.5.5 Constraints
• 4.6 Operational Semantics for Turtle
• 4.6.1 The Turtle Abstract Machine
• 4.6.2 Syntactic Transformation
• 4.6.3 Translating uTurtle to the Turtle Abstract Machine
• 5 The Implementation of Turtle
• 5.1 The Turtle Compiler
• 5.1.1 Compiler Description
• 5.1.2 Overload Resolution
• 5.1.3 Code Generation
• 5.1.4 Closure Representation
• 5.1.5 Tail Recursion Elimination
• 5.1.6 Compiling Constraint Statements
• 5.2 The Run-Time System
• 5.2.1 Memory Management
• 5.2.2 Data Representation
• 5.2.3 Hand-Coding
• 5.3 Run-Time Constraint Solver
• 5.3.1 Run-Time-Solver-Interface
• 5.4 The Standard Library
• 5.5 Discussion
• 5.5.1 Benchmarks
• 5.5.2 Open Issues
• 6 Summary and Evaluation
• 6.1 Alternative Designs and Implementations
• 6.2 Future Works
• 6.3 Conclusion
• A Turtle Grammar
• A.1 Lexical Entities
• A.2 Context-free Syntax
• B Example modules
• C The Standard Library
• D The Turtle System
• Bibliography
• Index

Download

This Thesis is available electronically: [ PDF ]

BibTeX Entry

@MastersThesis{Grabmueller2003CIP,
  author = 	 {Martin Grabm{\"u}ller},
  title = 	 {{Constraint Imperative Programming}},
  school = 	 {Technische Universit{\"a}t Berlin},
  year = 	 {2003},
  type =	 {Diploma Thesis},
  month =	 {February},
  abstract = {Constraint-based programming languages are declarative
              programming languages.  In constraint programs, the solutions
              of a problem are obtained by specifying their desired
              properties, whereas in imperative programs, the steps which
              lead to a solution must be defined explicitly, rather than
              being derived automatically from the specification.  This 
              work deals with the design and implementation of a programming
              language which integrates declarative constraints and
              imperative constructs in order to form a powerful programming
              paradigm suitable for solving a wide range of problems.}
}