Efficiently combining logical constraints with functions

A declarative program specifies a set of logical constraints between a set of objects. The computer searches for the objects satisfying the constraints (i.e., the solution). An imperative program must specify a detailed algorithm for finding the solution. Declarative programming can increase productivity (by making programs shorter and simpler). However, some problems discourage its widespread use. This thesis discusses how to make declarative programming more useful, using the new language Q. A denotational description of pure Q defines a powerful specification language. A complete implementation (that can find concrete solutions for any constraint) is theoretically impossible. We must settle for concrete solutions in limited but useful cases. A technique called narrowing combines the power of Prolog-style logic programming (logic variables, unification, non-determinism) with the notational convenience (true expression evaluation) and first-class function values of programming. Additionally, Q supports more general constraints, including automatic solution of linear equations. A novel technique implements logical constraints by embedding logic variables (representing parameters) inside functionally dependent variables (representing results of constraints). Run-time efficiency requires an optimizing compiler. One should pay for extra power only when it is used. One optimization replaces expensive logic variables and unification with cheap simple variables and assignment. It works for any function written in a functional style. Also, the support for backtracking (and in general continuations) is non-intrusive, using the standard C calling convention and stack, combined with some stack manipulation tricks when required. Logic languages have poorly supported data abstraction and type definition. Types in Q are coercion functions, and hence first-class values, so a parametric type is just a higher-order function. A class is a type derived from a function that creates new records. Classes are used as the basis of a powerful module facility. Special methods that implement application make functions into true objects (that can contain internal state). Declarative languages usually communicate poorly with other languages, which complicates calling low-level or previously-written code. The Q implementation strives for maximum compatibility with C. It uses C as a portable assembly language, with standard calling conventions and data formats.