Copyright © 1994, Dr. Dobb's Journal

Copyright © 1994, Dr. Dobb's Journal

Copyright © 1994, Dr. Dobb's Journal

Copyright © 1994, Dr. Dobb's Journal

Larry Medwin

The two versions of constraint solver are known as calc and icalc and represent alternate front ends to the equation solver. The functionality of the two programs is almost identical, but calc is accessed via a stdio-driven interface, while icalc is a GUI program built with the InterViews toolkit for X Windows. The application's ability to access the constraint-solving "engine" via calc's stdio interface allows it to be used in batch-style regression testing: calc receives input from test files, and the resulting output can be compared automatically with known good output. Internally, user-visible functionality is implemented via virtual functions. In calc, these become tty commands for input, output, and control; in the GUI version, these functions have overloaded equivalents.

To use calc, you launch the program and type some simple commands--for example, the keyword equation followed by an algebraic equation. An equation is defined as two algebraic expressions joined by an equal sign. Other commands include the set command, to force a value on a variable, and unset, which leaves the value unspecified. Note that a variable must be unset before it can be given a new value with set. Finally, you can simply type the name of a variable to obtain its solved value. At any time during the session, you can use the equation command to switch to another problem.

The constraint-solving engine is in the constraint.c module, available electronically (see "Availability," page 3). My implementation is based on a system described in Abelson and Sussman's The Structure and Interpretation of Computer Programs (MIT Press, 1985), except that their's is built using the Lisp-like language Scheme.

I chose C++ because I found that the components of the constraint network can be naturally modeled as objects that encapsulate functions and state. Inheritance allows a "constraint protocol" to be defined for a virtual base class, Constraint. The type and connectivity of objects of classes derived from Constraint is known only to the equation parser and the objects themselves. Polymorphism allows me to treat objects of classes derived from Constraint as objects of class Constraint itself. Constrained values, from Constants or user controlled Syms, are propagated around the network by Connectors according to a message protocol.

The bidirectional properties of the constraint network are the result of the behavior of the primitive constraints--operators which enforce relationships like x+y=z. In this case, knowing any two variables allows computation of the third. The other primitive constraints are Constants and Syms. A Constant always forces its value, but a Sym is a UI object for input (user sets value) or output (value is calculated from other known values). In the InterViews version, I added a class derived from Sym, called IVSym, which inherits from both Sym and the MonoGlyph classes in InterViews.

With the addition of Connector objects, primitive constraint objects can be combined to express more complex relationships. Connectors connect pairs of constraints. They can hold and propagate values. When a connector gets a new value from one constraint, it sends the value to its other one. A constraint can also "unconstrain" a connector. In this case, the Connector will tell its other constraint to forget the value previously forced by that Connector.

A Binop (BINary OPerator) is an operator that computes a result from two operands. It is a primitive constraint attached to three connectors. It represents the symmetrical relationship between two operands and a result. The symmetry results from the fact that knowing any two values, the third can be computed. For example, assume x+y=z. If x and y are known, z can be calculated. Alternatively, if z and y are known, x can be calculated as z--y. The same Binop represents both addition and subtraction by assigning the proper connectors to its operands and results. In normal operation of the network, a Binop is told every time one of its connectors gets or loses a value.

The root of the inheritance hierarchy is the Constraint class. A Constraint object must be able to determine if it has enough information to calculate a new value, and to tell attached Connectors about that new value. Similarly, it can withdraw a value lost when one of its inputs loses a value. These behaviors are implemented by the member functions process_new_value() and process_forget_value(), defined as pure virtual member functions in Constraint, implemented only its subclasses. This interface protocol allows client classes, such as Connector, to invoke process_new_value() and process_forget_value() on attached objects, knowing only that the objects are derived from class Constraint.

The other common behavior of all Constraints has to do with the construction of the constraint network. The member function replace_connector() asks the Constraint to disconnect itself from one specified connector and replace it with another. This is used when the equation parser sees an equal sign. All Constraints are attached to one or more Connectors, but the connectivity is specialized by the derived classes.

The process_delete() member function is similar to a destructor, except that it requires a single argument to identify the caller. The network is destroyed by traversing it and passing process_delete() messages recursively to each network object, except the caller. If a conventional destructor were called, the recursion step would pass a delete message to all attached Connectors, including the caller, resulting in an infinite loop.

The Binop class encapsulates the behavior of a generalized undirected operator taking two arguments. Binop has no state or value; it only responds to changes in its inputs. Binop is also a virtual class, and although it has a constructor, Binop objects themselves cannot be instantiated.

This program can be enhanced in several ways. One idea is to extend the underlying constraint mechanism to solve simultaneous equations. This might involve the propagation of partially constrained values around the network, and algorithms to reduce sets of partially constrained values to known values. This would be an interesting test of the generality and reusability of the class design used in this program.

Mark, known as the father of the InterViews toolkit, is the principle architect of Fresco. Portions of this article first appeared in X Resources, published by O'Reilly & Associates. Mark can be reached at [email protected].

The X Consortium's officially supported successor to InterViews is Fresco, a technology that supports "graphical embedding" by combining structured graphics and application embedding into a single architectural framework. With graphical embedding, you can compose both graphical objects (circles, polygons, and the like) and application-level editors (word processors, spreadsheets, and so on) with a uniform mechanism. Embedded application objects can appear within graphical scenes and will be appropriately transformed.

The Fresco API in X11R6 covers Xlib and Xt functionality, with additional features for graphical embedding. The Fresco API is defined using the Interface Definition Language (IDL) that's part of the Common Object Request Broker Architecture (CORBA) from the Object Management Group (OMG). Among IDL's advantages are:

• IDL is more abstract than object-oriented programming languages, yet concrete enough to be translated automatically into source code.
• IDL can be mapped to several languages. OMG has defined a mapping to C and is defining a mapping for C++ and Smalltalk.
• IDL can support distribution--the sender and receiver of an operation may be on different machines in a network.

As part of the support for graphical objects, Fresco operations are screen-resolution independent--coordinates are automatically translated by the implementation from application-defined units to pixels. Consequently, an application's appearance is the same on different screens or printers, without special coding by the programmer. Fresco includes a type that provides stencil/paint operations for rendering.

Fresco 1.0 in X11R6, written entirely in C++, includes an IDL-to-C++ translator, C++ include files, and a library that implements the Fresco classes. This implementation does not completely support distribution, though extensions to the run-time library would make that possible.

The sample implementation also includes an application called "Dish" that allows invocation of Fresco operations through the Tcl scripting language (developed at the University of California, Berkeley). Fresco does not include a Tcl implementation, but if you have the Tcl library installed, then Dish uses it along with CORBA dynamic invocation to create and manipulate Fresco objects from a script.

To summarize, the distinguishing features of Fresco are a standard object model (OMG CORBA) with a C++ implementation, resolution-independence, and graphical embedding. The use of CORBA means Fresco objects can be distributed across a network. Fresco also supports multithreaded applications in a single address space.

/***** CALC.C --- simple tty interface to constraint solver.
#include <stdio.h>
#include "constraints.h"

extern int yyparse();

main()
{
    Phase = INIT;
    yyparse();    // Parse input
    exit(0);
}

// *** icalc.h -- Larry Medwin 4/5/93    (Abridged version)
// *** InterViews user interface for the constraint system

extern class IVSym;
extern class Lexio;
extern class App;
extern Style* global_style;
extern App* Myapp;

declareFieldEditorCallback(App)
declareFieldEditorCallback(IVSym)
declareActionCallback(IVSym)

//---------------------------------------------------------------------
class IVSym : public Sym , public MonoGlyph
{
  public:
    IVSym(Sym*);
    ~IVSym() {};
    void accept_editor(FieldEditor*);    // FieldEditor callbacks
    void cancel_editor(FieldEditor*);
    void click_me();                     // Pushbutton callback
    static Style* sym_style;             // set by App::App()
  private:
    void IVSym_init();
                                         // UI stuff
    FieldEditor* ed_;                    // User enters values here
    FieldEditor* uned_;                  // Replaces ed_ when not forced
    Deck* deck_;
    Patch* patch_;
    Button* pbutton_;                    // Displays name_

    virtual void show_val();             // Display value and state
    virtual void show_no_val();
    virtual void show_state();
};
// Replaces lex I/O handlers to read from char arrays instead of stdio
class Lexio
{
  private:
    char* equation_;            // char string for lex
    char* current_;             // cursor for lex
  public:
    Lexio(String);
    ~Lexio();
    // Undefine lex I/O macros
#   undef lex_input()
#   undef unput(char)
    // Lex I/O handlers
    int lex_input();
    void unput(char);
};
//----------------------------------------------------------------------

class App                  // Canvas with equation editor and ActiveSyms
{
  private:
    String equation_;                    // FieldEditor String
    IVSym* network_;                     // Access to constraint network
  public:
    App(Style*);
    Lexio* lex_handler;
    FieldEditor* eq_editor_;             // InterViews components
    Glyph* sym_box_;                     // vbox to hold sym_area_
    void accept_editor(FieldEditor*);    // FieldEditor callbacks
    void cancel_editor(FieldEditor*);
                                  // Start off App with initial equation
    void kick_start(char *);      // (shouldn't need this)
};

//*** icalc.c --  user interface for InterViews-based version of
//    the constraint equation solver.        By Larry Medwin, 1993

#include <stream.h>
#include "icalc.h"

Style* IVSym::sym_style;     // Set by App::App(), read by IVSym::IVSym()
App*    Myapp;               // Global I/O handlers for lex
implementFieldEditorCallback(IVSym)
implementActionCallback(IVSym)

//*** class IVSym ***
IVSym::IVSym( Sym* source_sym) : Sym(source_sym->name())
{
    state_ = source_sym->state();    // Copy state_ and value_
    value_ = source_sym->value();
    IVSym_init();
}
void IVSym::IVSym_init()
{
    WidgetKit&        kit   = *WidgetKit::instance();
    const LayoutKit& layout = *LayoutKit::instance();
    //--- Init field editors (one for editing, one for uneditable display)
    kit.begin_style("ed");
    ed_ = DialogKit::instance()->field_editor(
        "       ", sym_style,
        new FieldEditorCallback(IVSym)(
            this, &IVSym::accept_editor, &IVSym::cancel_editor)
    );
    kit.end_style();
    //-------------------
    kit.begin_style("uned");
    uned_ = DialogKit::instance()->field_editor(
                     "       ", sym_style,
                     new FieldEditorCallback(IVSym)(
                         this, &IVSym::cancel_editor, &IVSym::cancel_editor)
    );
    kit.end_style();
    //--- Put ed and uned in deck arrange the glyphs in the deck in same
    //  order as enum state_ values, so that flip_to can index the proper
    //  glyph by state
    deck_ = layout.deck( uned_, uned_, ed_, ed_);
    deck_->flip_to( state());

    patch_ = new Patch( deck_);
    //--- The Pushbutton
    pbutton_ = kit.push_button("Force value",
                   new ActionCallback(IVSym)(this, &IVSym::click_me));
    //--- Put all this stuff in an hbox
    body(
        layout.vbox(
            layout.vglue(),
            layout.hbox(
                layout.hglue(), kit.label(name()),  // Sym name
//              layout.hglue(), kit.label("  "),    // spaces
                layout.hglue(), patch_,             // deck
                layout.hglue(), pbutton_,
                layout.hglue()
            ),
            layout.vglue()
        )
    );
    //-------------------
    ed_->field("");    // Start these guys up
    uned_->field("");

    return;
};
void IVSym::click_me()                   // Implement state transition
{
    switch(state()) {
        case UNCONSTRAINED:
            state(ACTIVE_NO_VALUE);
            break;
        case PASSIVE:       // Can't make transition if Sym is constrained
            break;
        case ACTIVE_WITH_VALUE:
            state(UNCONSTRAINED);
            con_->forget_value( this );
            break;
        case ACTIVE_NO_VALUE:
            state(UNCONSTRAINED);
            break;
        default:

            assert(True);
    }
    // see /home/iv/src/examples/zoomer/main.c
    patch_->redraw();
    return;
//------------------------------------------------------------------
void IVSym::accept_editor(FieldEditor* ed)
{
    float ed_val;
    assert( state() != PASSIVE);            // Shouldn't try to set this
                                            // value if it is being forced
    const String& valueStr = *ed->text();   // Get value from field editor
    if (!valueStr.convert(ed_val)) {        // Illegal number?
        cancel_editor(ed);
    }
    else {
        con_->forget_value(this);           // Remove last constraint
        state(ACTIVE_WITH_VALUE);           // Update state & propagate value
        set_value(ed_val);
    }
    return;
};
void IVSym::cancel_editor(FieldEditor* ed)
{   switch(state())                         // Restore old value
    {   case PASSIVE:
        case ACTIVE_WITH_VALUE:
            show_val();
            break;
        case UNCONSTRAINED:
        case ACTIVE_NO_VALUE:
            show_no_val();
            break;
        default:
            assert(True);
    }
    return;
};
void IVSym::show_val()
{
    char tmp[100];
    assert( state() != ACTIVE_NO_VALUE);
    assert( state() != UNCONSTRAINED);
    switch(state())
    {
        case ACTIVE_WITH_VALUE:
            sprintf( tmp, "%6.2f", value());
            ed_->field(tmp);
            break;
        case PASSIVE:
            sprintf( tmp, "%6.2f", con_->get_value());
            uned_->field(tmp);
            break;

        default:
            assert(True);
    }
    return;
}
//----------------------------------------------------------------------
{
    assert( state() != ACTIVE_WITH_VALUE);
    assert( state() != PASSIVE);
    switch(state())
    {
        case ACTIVE_NO_VALUE:
            ed_->field("");
            break;
        case UNCONSTRAINED:
            uned_->field("");
            break;
        default:
            assert(True);
    }
    return;
}
void IVSym::show_state()
{
    deck_->flip_to(state());
    patch_->redraw();
    return;
}
//*** class Lexio ***
Lexio::Lexio( String equation)
{
    // Copy into lex input string
    // Format: "equation " %s '\0'
    equation_ = new char[equation.length()+strlen("equation ")+1];
    sprintf( equation_, "equation %s", equation.string());
    current_ = equation_;
}
Lexio::~Lexio()
{
    delete[] equation_;
}
int Lexio::lex_input()
{
    if (current_ < equation_)     // Don't step back over start of string...
        return 0;                 // EOF
    else                          // Return char, or 0 at end of string
        return *(current_++);
//---------------------------------------------------------------------
void Lexio::unput(char c)
{

    if (current_ > equation_)    // If not before beginning
        *(--current_) = c;       // Push back pointer and put in char
    return;
}
//*** class App ***
implementFieldEditorCallback(App)
App::App(Style* style) : network_(0)
{
    const LayoutKit& layout = *LayoutKit::instance();
    IVSym::sym_style = new Style(style);    // Save copy of style
    // Init field editor
    eq_editor_ = DialogKit::instance()->field_editor(
                      "                    ", IVSym::sym_style,
                      new FieldEditorCallback(App)(
                              this, &App::accept_editor, &App::cancel_editor
                              )
                      );
    sym_box_ = layout.vbox();    // Init CurSymArea & its enclosing box
}
void App::accept_editor(FieldEditor* ed)
{
    IVSym* tmp_sym;
    WidgetKit& kit = *WidgetKit::instance();

    // Get rid of old constraint network
    //  if( network_ != 0) {
    //  network_->process_delete((Connector*)0);
    //  delete network_;
    //}
    for (GlyphIndex g = sym_box_->count(); g > 0; g--)  // Clean up glyphs
    {
        sym_box_->remove(g-1);
    }
    lex_handler = new Lexio( *ed->text());    // Get FieldEditor string to lex
    delete Symtab;                            // Create and empty symbol table
    Symtab = new SymbolList;
    // Parse the equation, generate constraint network and symbol table
    Phase = PARSE;
    yyparse();
    // Build up sym_box area
    for (ListUpdater(SymList) i(*Symtab); i.more(); i.next())
    {
        Sym* cur_sym = i.cur();
        tmp_sym = new IVSym( cur_sym);        // "Promote" Sym to IVSym
        // Replace Sym with IVSym in the constraint network
        Connector* tmp_con = cur_sym->con_;
        tmp_con->disconnect(cur_sym);
        tmp_sym->connect(tmp_con);
        // delete cur_sym;
        // Put the IVSym in the sym_box_ area
        sym_box_->append(tmp_sym);
    }
    // Keep a hook into the network so we can clean up later

    // network_ = tmp_sym;
    // UI gives us access to symbols, not the symbol table
    // delete Symtab;
    // Send expose event (How??)
//---------------------------------------------------------------------
void App::cancel_editor(FieldEditor* ed)
{
    ed->field(equation_);                 // Restore old equation
    return;
//---------------------------------------------------------------------
void App::kick_start(char* s)             // Start it off
{
    eq_editor_->field( s );               // Set up initial string
    accept_editor( eq_editor_);           // Get started
    return;
}
//*** main() ***
int main(int argc, char** argv)
{
    Session* session = new Session("FieldEditorTest", argc, argv);
    WidgetKit& kit = *WidgetKit::instance();
    const LayoutKit& layout = *LayoutKit::instance();
    Myapp = new App(session->style());
    Myapp->kick_start("a+b+c+d+e=0");      // Start it off
    return session->run_window(            // Set up app window
        new ApplicationWindow(
            new Background(
                layout.hbox(
                    layout.hglue(),
                    layout.vbox(
                        layout.vglue(), Myapp->eq_editor_,
                        layout.vglue(), Myapp->sym_box_,
                        layout.vglue()
                    ),
                    layout.hglue()
                    ),
                kit.background()
            )
        )
    );
    exit(0);
}

Copyright © 1994, Dr. Dobb's Journal