Overview

We propose a system semantic in which specification-like goals and techniques to satisfy those goals are formalized as formal language constructs. Goals provide an abstraction to state what a user wants or what a program requires in order to complete some task. Techniques are code objects that can satisfy some goals.

The goals runtime system hides the complexity of how each goal is satisfied. Given a high-level goal, the runtime system automatically explores the available techniques, dynamically composes an implementation from the resources available in the user environment that the techniques request, and, if necesary, successively revises the implementation to sustain the user goal.

Rationale

As a tiny example, consider a user in a videoconference with a colleague as he wanders about a well equipped campus. As he moves from one room to another, his video switches from the small LCD display of his handheld to a wall-mounted plasma screen as the latter comes into view. Similarly, networking technologies might shift between 802.11b and CDMA depending on resource availability, and video may degrade or disappear altogether as communication bandwidth warrants.

Such behavior necessarily requires frequent reevaluation of available alternatives, as well as heuristic compromises to best address the user's needs with imperfect resources. Conventional techniques for constructing applications, in which top-level function is decomposed into statically-partitioned subfunctions each affixed to a particular API, makes such adaptation exceedingly difficult to program. If there is a change in available resources, it is often insufficient simply to reconsider how to implement the function specified at each API: it is necessary to reconsider the reason that API was selected, and whether an alternative function and API has now become more appropriate.

Approach

By formalizing goals and techniques, we create a basic framework on which we can guide the automatic construction of a component-based system. Semantically, goals are similar to generic procedure calls: they involve a named generic service (the goal name) as well as an arbitrary number of typed parameters. Thus, TeleConference(Victor, Steve) might be a high-level goal whose satisfaction requires a teleconference link between Victor and Steve, each a parameter of type Person.

Unlike procedure calls, however, goals are disembodied from any block of code to be invoked during their execution. Rather, the system approaches the resolution of a goal by searching for one or more techniques, each of which constitutes a recipe for resolving a class of goals. Each technique specifies a pattern to be matched against a candidate goal, optional subgoals that must be satisfied for it to proceed, and code to be run in order to cause an incoming goal to be satisfied once the specified subgoals have been achieved. This semantic is reminiscent of Prolog and related logic languages of the 80s, although the implementation technology surrounding it is quite different.

Each of the techniques is embodied as an object that plays an active role during the resolution process, in effect offering to satisfy the stated goal so long as certain constraints (expressed as subgoals) are met. The resolution process takes the form of a negotiation between a system object (called a context) and a set of applicable technique objects. Typically the context will create and explore a goal tree, heuristically choosing the most satisfactory branch of that tree to be implemented.

Following implementation, however, the goal tree persists as a record of the logic by which implementation choices were made, so long as the goal remains active. As network connections break or new resources become available, the goal tree is reevaluated and alternative implementation choices may be made and implemented in real time.

Progress and Plans

Early prototype goal-oriented planners[2, 3] addressing toy problems in simple ubiquitous computing environments[1] have been demonstrated. Current efforts are directed toward generalization of the approach to other application areas, improvement of the language used for scripting techniques, and evaluating the approach in the context of more realistic applications.

Funding

This project has been funded by the Oxygen project, CMI, and the DARPA ACIP program.

References

[1] Umar Saif, Hubert Pham, Justin Mazzola Paluska, Jason Waterman, Chris Terman, and Steve Ward, A Case for Goal-oriented Programming Semantics. In System Support for Ubiquitous Computing Workshop at the Fifth Annual Conference on Ubiquitous Computing (UbiComp '03).

[2] Early goal-oriented concept demo, available at http://ward.lcs.mit.edu/curl/goalsdemo/index.html.

[3] Justin Mazzola Paluska. Automatic Implementation Generation for Pervasive Applications. Masters of Engineering Thesis, MIT, June 2004.