STELLA - Painless Symbolic Processing in C++

Robert MacGregor

USC/Information Sciences Institute, [email protected]

What is STELLA?

• strongly resembles Common Lisp, but adds
• strong-typing, and
• built-in object database/knowledge representation features.

• C++
• Common Lisp.

• STELLA combines the fast-prototyping of Lisp with the efficiency of C++.
• Programmer-friendly environment for developing (intelligent) symbol processing systems.
• Compatibility with commercial tools and applications.

Design Rationale

• The output of the C++ translator must be
  • readable;
  • conventional;
  • efficient.
• Fast prototyping, minimal redundancy, late-binding:
  • Minimal restrictions on placement of declarations;
  • Type inference (to minimize need for explicit type declarations);
  • Automatic casting and coersion;
  • Uniform syntax for function, method, and slot access.
• Full support for symbolic processing:
  • Symbols, keywords, lists, surrogates;
  • First-class literals; backquote;
  • Funcallable functions, methods, slot accessors, and constructors;
  • Meta-object protocol.

We have Succeeded!

• STELLA is almost as easy to program in as Lisp (subjective).
• C++ output is efficient (executes 10-15 times faster than CLOS).
• STELLA object system is more advanced than CLOS:
  • iterators
  • modules
  • surrogates
  • triggers
• STELLA is portable:
  • Translator has been compiled into Centerline C++, G++, Allegro CL and MCL.
  • STELLA is written in STELLA (except for one C++ file and one Common Lisp file).

A Few Features Aren't Finished

• Automatic memory management:
  • No decision yet on garbage collector vs. reference counting vs. something else.
  • Translator has memory leaks.
• Defsystem
• Load and save module to/from file(s)

Method Example #1

(defmethod (length INTEGER) ((self CONS))
  :documentation "Return the length of the CONS list 'self'.
                 CAUTION: Breaks if 'self' is not the head
                 of a CONS list."
  (let ((cons self)
        (i 0))
    (while (non-empty? cons)
      (++ i)
      (setq cons (rest cons)))
    (return i) ))

int Cons::length () {
 {
    Cons* cons = this;
    int i = 0;

    while (cons->non_emptyP()) {
      i = i + 1;
      cons = cons->rest;
    }
    return (i);
  }
}

Method Example #2:

(defmethod (member? BOOLEAN) ((self CONS) (object OBJECT))
  :documentation "Return TRUE iff 'object' is a member of
                  the cons list 'self'.  Uses an 'eql?' test."
  (foreach element in self
           where (eql? element object)
           do (return TRUE))
  (return FALSE) )

boolean Cons::memberP (Object* object) {
 {
    Object* element = NULL;
    Cons* iter_001 = this;

    while (!nilP(iter_001)) {
      element = iter_001->value;
      iter_001 = iter_001->rest;
      if (element == object) {
        return (TRUE);
      }
    }
  }
  return (FALSE);
}

Class Example #1

(defclass CONS (STANDARD-OBJECT)
  :parameters ((any-value :type OBJECT))
  :slots
  ((value :type (LIKE (any-value self)) :public? TRUE)
   (rest :type (CONS OF (LIKE (any-value self)))
         :public? TRUE
         :initially NIL)))

class Cons : public Standard_Object {
public:
  Object* value;
  Cons* rest;
public:
  virtual int length();
  virtual Cons* reverse();
  virtual Object* first();
  virtual Object* second();
  virtual Object* third();
       ....
  virtual boolean memberP(Object* object);
}

Class Example #2

(defclass MAPPABLE-OBJECT (STANDARD-OBJECT DYNAMIC-SLOTS-MIXIN)
  :documentation "Enables the definition of projections."
  :abstract? TRUE
  :slots
  ((native-name :type STRING :allocation :dynamic
                :documentation "Used when native name cannot be a symbol.")))

class Mappable_Object : public Standard_Object,
                        public Dynamic_Slots_Mixin {
public:
  virtual String_Wrapper* wrapped_native_name_setter(String_Wrapper* value);
  virtual String_Wrapper* wrapped_native_name();
};

String_Wrapper* Mappable_Object::wrapped_native_name () {
 { char* barevalue =
          ((String_Wrapper*)
             (dynamic_slot_value(this,
                   SYM_KERNEL_NATIVE_NAME,
                   NULL_STRING_WRAPPER)))->wrapper_value;
    return (((barevalue != NULL) ?
             string_wrap_literal(barevalue) : NULL));
  }
}

STELLA vs. Common Lisp/CLOS

• Formal parameters are explicitly typed.
• Uninitialized local variables are explicitly typed.
• Definition of methods on top-level classes (e.g., on OBJECT) is discouraged (use typecase instead).
• No multiple inheritance (except for mixin classes).
• Some STELLA statements do not return values:
  case, cond, progn, let, foreach.
• NULL (undefined value) and NIL (empty cons list) are distinct.
• Sometimes (not often) explicit casting is needed.

• eval, lexical closure, multi-methods, call-next-method, keyword arguments, unwind-protect.

STELLA vs. C++

• Casts are seldom needed (but translated C++ code contains lots of casts).
• Coersion of literals to/from objects is automatic and transparent.
• Most of the idiosyncrasies of the C++ type system are hidden.
• No header files.
• Free placement of method declarations.
• Elegant iterators.
• Versatile foreach loop (mimics Common Lisp loop for):
  in, on, as, collect into, forall, exists.
• Parameterized and anchored types (superior to C++ templates).
• Class-specific print methods use dynamic dispatch (``<<'' is static).
• Classes, slots, global variables, and modules are first-class objects.
• Run-time type inference (C++'s RTTI is quite inadequate).
• Initial and default values.
• Dynamically-allocated slots (transparent accessor syntax).
• startup-time-progn.
• Null values for integer, float, and character classes.
• Constructor, initializer, terminator, destructor.

Support for Symbolic Processing

• First-class literals;
• Funcallable slots accessors and constructors;
• Meta-object protocol.

Writing a translator, using the ``program-as-data'' paradigm, requires something equivalent to:

• Symbols and conses;
• Common Lisp's backquote.

STELLA's Triggers (``Demons'')

• Updates to a particular slot;
• Updates to any (active) slot;
• Instantiation of a particular class;
• Instantiation of any (active) class.

Only an ''active'' slot/class can have demons, non-active slots incur no overhead.

Demons can be activated and deactivated at run-time.

Why a new language, why not just extend C++?

Many STELLA features (critical for rapid prototyping) could not be implemented even with a powerful macro facility. Their implementation requires type inference and/or two-pass compilation:

• Automatic casting and coersion;
• Clean type system;
• No header files;
• Free placement of method declarations.

Conclusions

• Implementing a STELLA-to-C++ translator has consumed about three person years.
• Upgrading C++ to support the implementation of PowerLoom® would have taken more than 1.5 person years.
• We expect that, over the long term, our investment in translation technology will have paid for itself several times over.

Automatic generation of efficient, readable C++ is feasible.

Translation to other object-oriented languages (e.g., Java) would not be difficult.

PowerLoom

PowerLoom features:

• Fully-expressive logic.
• Multiple logic languages (KIF, Loom, OQL, ???)
• Multiple inference engines; modular components.
• Scalable, parallelizable inference architecture.
• Deliverable in C++ and Common Lisp.

PowerLoom Components

First PowerLoom Release

First release features:

• Fully-expressive logic-definitions and assertions phrased in KIF;
• Query processor;
• Load and save knowledge base from files;
• Common frame protocol API;
• C++ and Common Lisp versions.