YOUR OWN TINY OBJECT-ORIENTED LANGUAGE

C++? Smalltalk? What About Bob?

David Betz
Dr Dobbs Journal, Sep 1991, p.26ff

David is a technical editor for DDJ, and the author of XLisp, XScheme, and the TelePath conferencing system. He can be reached at DDJ, 501 Galveston Drive, Redwood City, CA 94063.

When I first started reading Dr. Dobb's back in the '70s, the articles I looked forward to the most were those describing tiny programming languages. First there were tiny implementations of Basic for various microprocessors, then small implementations of C and Forth, and even a tiny language for the control of robots. These articles intrigued me because they not only described a language, but also included complete source code for its implementation. I've always been interested in how programming languages are constructed, and this gave me an opportunity to look inside and see how things worked. Eventually, I decided to try my own hand at building languages.

Since then, I've built many different types of languages, ranging from simple assemblers to complete Lisp systems. This article describes my latest creation, a C-like, object-oriented language I call "Bob." Unlike the popular Small C compiler by Ron Cain, it isn't a strict subset of C or C++; hence it isn't possible to compile Bob programs with a standard C or C++ compiler. Instead, Bob is an interpreter for a language with C-like syntax and a class system similar to C++, but without variable typing and mostly without declarations. In a sense, Bob is a combination of C++ and Lisp.

Writing a Bob Program

Before I begin describing Bob in detail, let's discuss how you go about writing Bob programs. Example 1(a) presents a simple example program -- a function for computing factorials -- written in Bob.

This function definition looks a lot like its C counterpart. The only noticeable difference is the lack of a declaration for the type of the parameter n and for the return type of the function. Variable types do not need to be declared in Bob. Any variable can take on a value of any type. There is no need for type declarations.

To take this further, Example 1(b) shows a program that uses the factorial function above to display the factorials of the numbers from 1 to 10. Again, this program looks a lot like a similar program written in C. The main difference is in the first line. In a function definition's formal parameter list, the semicolon character introduces a list of variables local to the function. In this case, the variable i is local to the function main. Also, notice that I've used the print function to display the results instead of the C printf function. The print function in Bob prints each of its arguments in succession. It is capable of printing arguments of any type and automatically formats them appropriately.

Example 1: (a) A Bob program for computing factorials; (b) a program that uses the factorial function to display the factorials of the numbers from 1 to 10.

  (a) factorial(n)
      {
          return n == 1 ? 1 : n * factorial(n-1);
      }

  (b) main(; i)
      {
          for (i = 1; i <= 10; ++i)
              print(i," factorial is ",factorial(i),"\n");
      }

In addition to supporting C-like expressions and control constructs, Bob also supports C++-like classes. Again, Bob is a typeless language, so the syntax for class definitions is somewhat different from C++, but it is similar enough that it should be easy to move from one to the other. Example 2(a) shows a simple class definition.

Example 2: (a) A simple class definition; (b) a constructor function for the class foo.

  (a) class foo
      {
          a,b;
          static last;
          static get_last();
      }
  (b) foo::foo(aa,bb)
      {
          a = aa; b = bb;
          last = this;
          return this;
      }

This fragment defines a class called foo with members a and b, a static member last, and a static member function get_last. Unlike in C++, it is not necessary to declare all member functions within the class definition; only the static member functions need be declared. It is necessary, however, to declare all data members in the class definition.

As in C++, new objects of a class are initialized using a constructor function, which has the same name as the class itself. Example 2(b) is the constructor function for the foo class. This constructor takes two arguments, which are the initial values for the member variables a and b. It also remembers the last object created in the static member variable last. Lastly, it returns the new object. For those of you not familiar with C++, the variable this refers to the object for which the member function is being called. It is an implicit parameter passed to every nonstatic member function. In this case, it is the new object just created.

In Bob, all data members are implicitly protected: The only way to access or modify the value of a member variable is through a member function. If you need to access to a member variable outside a member function, you must provide access to member functions to do this; see Example 3(a). To set the value of a member variable, see Example 3(b). Finally, Example 3(c) is a member function that displays the numbers between a and b for any object of the foo class, and a main function that creates some objects and manipulates them. The new operator creates a new object of the class whose name follows it. The expressions in parentheses after the class name are the arguments to be passed to the constructor function.

Example 3: (a) Providing access to a member variable outside a member function; (b) setting the value of a member variable; (c) a member function that displays the numbers between a and b for any object of the foo class, and a main function that creates some objects and manipulates them.

  (a)  foo::get_a()
       {
           return a;
       }

  (b)  foo::set_a(aa)
       {
           a = aa;
       }

  (c)  foo::count (; i)
       {
           for (i = a; i <= b; ++i)
               print (i, "\n");
       }

       main(; foo1, foo2)
       {

            foo1 = new foo (1, 2);           // create a object of class
                   foo
            foo2 = new foo (11, 22);         // and another
            print ("fool counting\n");       // ask the first to count
            foo1 ->count ();
            print ("foo2 counting\n");       // ask the second to count
            foo2 ->count ();
       }

Bob also allows one class to be derived from another. The derived class will inherit the behavior of the base class and possibly add some behavior of its own. Bob only supports single inheritance; therefore, each class can have at most one base class. The code in Example 4(a) defines a class bar derived from the base class foo, defined earlier.

Example 4: (a) Defining a class bar derived from the base class foo; (b) the constructor for bar needs to initialize this new member variable as well as doing the initialization normally done for objects of class foo.

  (a) class bar : foo
      // a class derived from foo
      {
         c;
      }

  (b) bar::bar (aa,bb,cc)
      {
          this->foo (aa,bb);
          c = cc;
          return this;
      }

The class bar will have member variables a and b inherited from foo as well as the additional member variable c . The constructor for bar needs to initialize this new member variable and do the initialization normally done for objects of class foo; see Example 4(b).

This definition points out another difference between Bob and C++. In C++, constructor functions cannot be called to initialize already existing objects. This is allowed in Bob, so the foo constructor can be used to do the common initialization of the foo and bar classes. In C++, it would be necessary to define an init function for foo and call it from both constructors.

That's a brief walk through the features of Bob. Table 1 details Bob's complete syntax.

Table 1: Bob syntax

  Class Definition

  class<class-name>[:<base-class-name>]
   {<member-definition>...}

  Member Definition

  <variable-name>...;
  static<variable-name>...;
  <function-name>([<formal-argument-list>]);
  static <function-name>([<formal-argument-list>]);

  Function Definition

  [<class-name>::]<function-name>
   ([<formal-argument-list>[;<temporary-list>])
   {<statement>...}

  Statement

  if (<test-expression>)<then-statement>[else<else-statement>];
  while (<test-expression>)<body-statement>
  do<body-statement>while<test-expression>);
  for(<init-expression>;<test-expression>;<increment-expression>)
   <body-statement>
  break;
  continue;
  return[<result-expression>];
  [<expression>];
  {<statement>...}

  Expression
  <expression>,<expression>
  <lvalue>=<expression>
  <lvalue>+=<expression>
  <lvalue>-=<expression>
  <lvalue>*=<expression>
  <lvalue>/=<expression>
  <test-expression>?<true-expression>:<false-expression>
  <expression>||<expression>
  <expression>&&<expression>
  <expression>|<expression>
  <expression>^<expression>
  <expression>&<expression>
  <expression>==<expression>
  <expression>!=<expression>
  <expression><<expression>
  <expression><=<expression>
  <expression>>=<expression>
  <expression>><expression>
  <expression><<<expression>
  <expression>>><expression>

  <expression>+<expression>
  <expression>-<expression>
  <expression>*<expression>
  <expression>/<expression>
  <expression>%<expression>
  -<expression>
  !<expression>
  ~<expression>
  ++<lvalue>
  --<lvalue>
  <lvalue>++
  <lvalue>--
  new <class-name>([<constructor-arguments>])
  <expression>([<arguments>])
  <expression>-><function-name>([<arguments>])
  (<expression>)
  <variable-name>
  <number>
  <string>
  nil

How Does it All Work?

I've implemented Bob as a hybrid of a compiler and an interpreter. When a function is defined, it is compiled into instructions for a stack-oriented bytecode machine. When the function is invoked, those bytecode instructions are interpreted. The advantage of this approach over a straight interpreter is that syntax analysis is done only once, at compile time. This speeds up function execution considerably and opens up the possibility of building a runtime-only system that doesn't include the compiler at all.

Runtime Organization

First, I'll describe the runtime environment of Bob programs. The virtual machine that executes the bytecodes generated by the Bob compiler has a set of registers, a stack, and a heap. The register set is shown in Table 2. All instructions get their arguments from and return their results to the stack. Literals are stored in the code object itself and are referred to by offset. Branch instructions test the value on the top of the stack (without popping the stack) and branch accordingly. Function arguments are passed on the stack, and function values are returned on top of the stack.

Table 2: Registers used by the virtual machine

   Register      Description
  ---------------------------------------

  code         currently executing code
                 object

  cbase        base of bytecode array for
                 the current code object

  pc           address of the next
                 bytecode to fetch

  sp           top of the stack
  fp           stack frame for the current
                 call

  stkbase      bottom stack limit
  stktop       top stack limit

In Bob, all member functions are virtual. This means that when a member function is invoked, the interpreter must determine which implementation of the member function to invoke. This is done by the SEND opcode, which uses a selector from the stack (actually, just a string containing the name of the member function) with the method dictionary associated with the object's class to determine which member function to use. If the lookup fails, the dictionary from the base class is examined. This continues, following the base class chain until either a member function is found or there is no base class. If a member function is found to correspond to the selector, it replaces the selector on the stack and control is transfered to the member function, just as it would have been for a regular function. If no member function is found, an error is reported and the interpreter aborts.

Bob supports five basic data types: integers, strings, vectors, objects, and nil. Internally, the interpreter uses four more types: classes, compiled bytecode functions, built-in function headers, and variables. Wherever a value can be stored, a tag indicates the type of value presently stored there. The structure for Bob values is shown in Example 5.

Example 5: The structure for Bob values

  typedef struct value {
    int v_type;      /* data type */
    union {      /* value */
      struct class *v_class;
      struct value *v_object;
      struct value *v_vector;
      struct string *v_string;

      struct value *v_bytecode;
      struct dict_entry *v_var;
       int (*v_code) ();
      long v_integer;
    } v;
  } VALUE;

Objects, vectors, and bytecode objects are all represented by an array of value structures. In the case of bytecode objects, the first element in the vector is a pointer to the string of bytecodes for the function, and the rest are the literals referred to by the bytecode instructions. Class objects are vectors, where the first element is a pointer to the class object and the remaining elements are the values of the nonstatic member variables for the object. Built-in functions are just pointers to the C functions that implement the built-in function. Variables are pointers to dictionary entries for the variable. There is a dictionary for global symbols and one for classes. Each class also has a dictionary for data members and member functions.

In addition to the stack, Bob uses a heap to store objects, vectors, and strings. The current implementation of Bob uses the C heap and the C functions malloc and free to manage heap space and uses a compacting memory manager.

The Source Code

The Bob bytecode compiler is a fairly straightforward recursive descent compiler. At the moment, it uses a set of heavily recursive functions to parse expressions. I intend to replace that with a table-driven expression parser. The bytecode interpreter (Listing One, page 86) is really just a giant switch statement with one case for each bytecode.

The source code for Bob is too large (more than 3000 lines) to be included in this issue. Consequently, it's available electronically; see "Availability" on page 3. I am including significant portions of the code here, though, and I hope this will give you a taste of the implementation of Bob.

Conclusions

Well, there it is -- a complete, if simple, object-oriented language. I don't think I'd want to throw away my C or C++ compiler in favor of programming in Bob, but it could serve as a good basis for building a macro language for an application program or just as a tool for experimenting with language design and implementation. It should be fairly easy to extend Bob with more built-in functions and classes or to build application-specific versions with functions tailored to your own application. I'm designing a computerized system for controlling theater lighting and will probably use Bob as a macro facility in that system. Anyway, have fun playing with Bob and please let me know if you come up with an interesting application for it.