Name:			Karl Liebeherr, Jon LeBlanc
 Date:			23-Jan-95

Pattern Name and Classification

Adaptive Interpreter - Class Behavioral

Intent

"Given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in the language." [GOF94]

The adaptive version of this pattern is expanded from the above intent to support interpreters for families of grammars.

Also Known As

Motivation

After creating a grammar for a language an interpreter is built to interpret sentences of the language as well as of similar languages. The adaptiveness of this pattern allows the interpreter to be flexible and work on a variety of similar languages which makes it useful on a class of problems instead of one instance of a problem. (See the Demeter book for more information about Demeter.)

The CD is specified as an EBNF grammar in which the user defines all classes and data members. Demeter uses this grammar to create a parser and printer for the language which can both parse sentences into object trees and print the objects out as sentences in the language. For more information on the Demeter System see [DemeterBook].

Each sentence in a language defined by the CD must parse into a unique object graph (ie. two different sentences in the language cannot generate identical object graphs). This constraint is imposed so that the EBNF grammars are both easy to read for users and easy to parse and print for Demeter. The restriction described above means that the set of languages Demeter accepts fall into the LL(1) class of languages. For information on LL(1) languages and their particular attributes see [DemeterBook].

Applicability

Use the Adaptive Interpreter Pattern 
	- To interpret a language

Structure

A recursive class dictionary is used to specify the grammar and class structure.

Participants

Use propagation patterns to focus on the important participants.

Collaborations

Interpretation of an object is expressed in terms of its subobjects.

Consequences

The Adaptive Interpreter pattern has the following benefits and liabilities:

1) Support for expansion of the grammar. Since the grammar is defined in the Class Dictionary (CD) it is very easy to modify and extend the grammar. Since the interpreter is only loosely coupled to the grammar, the interpreter is significantly shielded from changes to the grammar.

2) Support for adapting the interpreter to a new language. The behavior of the interpreter is defined using Propagation Patterns (PP). Users of the Adaptive Interpreter pattern may change the PP's to create a new interpreter for the same language. See below for an example PP.

Implementation

Many of the implementation details are handled by the Demeter System. The user is only required to create the Class Dictionary and the Propagation Patterns.

1) The abstract syntax trees (objects) are created by Demeter. Demeter creates a parser by giving the CD that defines the language to Demeter's generic parser.

2) Interpretation is defined by Propagation Patterns.

Sample Code 


*component* evaluator
  *schema-examples* 
  // Minimal 
    Exp : Simple | Compound *common*.
    Simple =  Number.
    Compound =  Op  Exp.
    Op : AddSym | MulSym *common*.
    AddSym = .
    MulSym = .
    ,
  // Typical
    Exp : Simple | Compound *common*.
    Simple =  Number.
    Compound =  Op  List(Exp).
    Op : AddSym | MulSym *common*.
    AddSym = .
    MulSym = .
    List(S) ~ {S}. 

  *meta* // describes assumptions made on customizing cd	
	 // and defines suitable abbreviations
    *class* Exp, Compound, Simple, Op, AddSym, MulSym
    *relation* v // -> Simple,v,Number
    *class-set*
      Kinds = {Simple, Compound};
      Ops = {AddSym, MulSym};
    *dir*
      EK = *from* Exp *to-stop* *class-set* Kinds;
      CE = *from* Compound *to* Exp;
      FromOp = *from* Op *to* *class-set* Ops;
  *end*
  *operation* int eval() *init* (@ 0 @)
    *traverse* EK 
    *wrapper* Simple *prefix*
      (@ return_val = *v; @)
//      (@ return_val = v -> get_val();@)
    *wrapper* Compound *prefix*
      (@ return_val = this -> apply(op); @)
  *operation* int apply(Op* op) *init* (@ op -> unity() @)       
    *traverse* CE
    *wrapper* Exp *prefix*
      (@ return_val = op -> apply_op(return_val, this -> eval()) @)
  *operation* int unity()
    *traverse* FromOp
    *wrapper* MulSym *prefix* (@ return_val = 1; @)
    *wrapper* AddSym *prefix* (@ return_val = 0; @)
  *operation* int apply_op(int n1, int n2)
    *traverse* FromOp
    *wrapper* MulSym *prefix* (@ return_val = n1*n2; @)
    *wrapper* AddSym *prefix* (@ return_val = n1+n2; @)
*end* evaluator

The above CD and PP define a simple example of an expression language and and interpretation of the language. The CD contains concrete syntax (all parts surrounded by double quotes) which makes the sentences easier for people to read.

Known Uses

The Adaptive Interpreter pattern is used extensively in the Demeter product.

Related Patterns

Adaptive Iterator: Used to traverse over objects in the language

Adaptive Visitor: Used to interpret the language

Bibliography 

[GOF94] Erich Gamma,Richard Helm,Ralph Johnson,John Vlissides. 
        Design Patterns Elements of Reusable Object-Oriented Software.
        Addison-Wesley, Reading, MA.  pages 243-255

[ACM94]	Karl J. Lieberherr,Ignacio Silva-Lepe,Cun Xiao
	Adaptive Object-Oriented Programming using Graph-Based Customization
	Communications of the ACM, May 1994. pages 94-101