Virtually brilliant – part one

It all happened in 1994 when I came across the book. I couldn’t put it down. The idea that you could define a virtual machine which people could implement, then sent them a heap image for the system and have it work on their implementation was a magical idea. Especially as the image could contain a portable gui that all worked using the BitBlt primitive which it used for drawing graphics and fonts and the windows itself. More impressively the system supported concurrent processes, multitasking by switching the byte interpretation to a new context on a timer. Lastly, most of the system was written in itself – the debugger, the compiler and all of the graphics. From there it was on to reading the "purple book" though the book I really wanted, and which I couldn’t get hold of, was the earlier blue book which covered all of the definitions for the virtual machine and its object memory. A while back I found the definitions here.
 
In a series of posts, I’m hoping to communicate some of the beauty of the Smalltalk VM, particularly the way that the whole system including the compiler can be written in Smalltalk with the VM hooking into the system via the Behavior class. By implementing this using F# I am hoping to get a better understanding of this interplay between the system and the VM across this interface.
 
However, this is going to take some effort so in this first post I want to get the basic instance and class structure set up. All we are going to look at is representing data. In later posts we’ll look at adding  methods and then object creation into the picture. This will mean that we’ll have to add to the classes that we define here, in terms of methods and instance variables. We’ll also be starting with a class structure that looks like it has too many classes. I will simplify things from real Smalltalk in some cases, but the meaning of some of these classes won’t become clear until we get closer to the VM.
 
The original smalltalk virtual machine divided the space of words into two by using the lower bit as a tag. One represented an integer in 2’s complement form and a zero lower bit represented a pointer value. This pointer pointed into an object table that contained details of the class of the object together with a pointer to the object’s data area.
 
type SmalltalkValue = SmallInt of int | Instance of InstanceValue
and InstanceValue = { mutable classType : SmalltalkValue option; slots : SlotValues }
and SlotValues = Standard of SmalltalkValue array | StringValue of string | Bytes of byte array;;
 
The first key detail is that values are either small integers that are representable in a word of memory or are instances of another type. Hence whenever we have a value in our hand we may ask for the objects type, first by checking if it is the well known integer value in which case the VM has a pointer to the class object for the SmallInteger type or we can go to the class slot inside the instance object and follow that to get the class object. The classType is a mutable option. This is because the actual class hierarchy is quite large and contains some circularities which can’t be filled in when the object is created.
 
The instance itself contains some values – typically these are the values of the instance variables which will be represented as an array of normal Smalltalk values. For items like strings we’ll have a special representation and for code objects we’ll use a byte array. The real Smalltalk-80 uses an object table to record all live instances. We’ll not be simulating that here.
 
In some of the coming examples we’ll use a Point object as an example. A Point instance has an x and y coordinate, so we’d represent the 1@2, the point with x coordinate 1 and y coordinate 2 as
 
let point_1_2 = Instance { classType = None; slots = Standard [| SmallInt 1; SmallInt 2 |] };;
 
Smalltalk now has something rather clever. Our point (1,2) is an instance of a class named Point, like in languages such as C#. However, we’re also going to make this class object an instance of another class, a metaclass. Inside the class object for a Point we are going to need to maintain an array of instance variable names. This will be represented using an array of strings.
 
let string_x = Instance { classType = None; slots = StringValue "x" }
let string_y = Instance { classType = None; slots = StringValue "y" }
let PointInstanceVars = Instance { classType = None; slots = Standard [| string_x; string_y |] };;
 
We’ll fill in the classTypes later to reflect the types of the objects. For the strings we’ll need a String class and for the array we’ll need an array class. Points are also going to inherit from a base class type named Object. Let’s start constructing the class object for object. This has slots representing the superclass, a slot representing the method dictionary and a slot representing the array of instance variables introduced by this class. We’ll use nil for this for the moment. In order for
us to define the superclass of Object as nil, we need an object representing nil. In SmallTalk, nil is the singleton instance of the class UndefinedObject.
 
let nil = Instance { classType = None; slots = Standard [| |] }
let UndefinedObjectInstanceVars = Instance { classType = None; slots = Standard [| |] }
let ObjectInstanceVars = Instance { classType = None; slots = Standard [| |] }
let Object = Instance { classType = None; slots = Standard [| nil; nil; ObjectInstanceVars; |] }
let UndefinedObject = Instance { classType = None; slots = Standard [| Object ; nil;  UndefinedObjectInstanceVars|] }
 
We can now define a function for filling in the class type of an instance.
 
let setType instance value =
  match instance with
  | Instance y -> y.classType <- Some value
  | _ -> failwith "bad instance";;
 
We can now use this to set the type of nil.
 
setType nil UndefinedObject;;
 
Let us also define the String and Array classes. These are both subclasses of Object.
 
let String = Instance { classType = None; slots = Standard [| Object ; nil; UndefinedObjectInstanceVars |] }
let Array = Instance { classType = None; slots = Standard [| Object ; nil ; UndefinedObjectInstanceVars |] }
setType string_x String;;
setType string_y String;;
setType UndefinedObjectInstanceVars  Array;;
setType ObjectInstanceVars  Array;;
setType PointInstanceVars Array;;
 
We may now define the Point class
let Point = Instance { classType = None; slots = Standard [| Object ; nil; PointInstanceVars |] }
setType point_1_2 Point;;
 
Now we’re starting to have a class hierarchy! We have a type Object with subclasses such as Point and UndefinedObject. We have made an instance of the former bound into point_1_2 and of the latter bound to nil.
 
let Number = Instance { classType = None; slots = Standard [| Object ; nil ;UndefinedObjectInstanceVars|] }
let SmallInteger = Instance { classType = None; slots = Standard [| Number ; nil ; UndefinedObjectInstanceVars|] }
 
We can get the class of an instance using
 
let ClassOf x =
  match x with
  | Instance x ->
     match x.classType with
     | None -> failwith "Improper class hierarchy"
     | Some c -> c
  | SmallInt y -> SmallInteger
 
let Super x =
    match x with
    | Instance data ->
       match data.slots with
       | Standard slots -> slots.[0]
       | _ -> failwith "Invalid class instance"
    | _ -> nil
 
let rec Subtype x y =
  if x = y 
  then true
  else
    if Super x = nil
    then false
    else Subtype (Super x) y
 
We can check that point_1_2 is an instance of Object, because the first two of the following return true and the third retruns false.
 
Subtype (ClassOf point_1_2) Object
Subtype (ClassOf point_1_2) Point
Subtype Number Point
 
We can write some functions to determine all of the instance variables for a given instance:
 
let UnpackString s =
  match s with
  | Instance data ->
      if data.classType <> Some String
      then failwith "Expecting a string"
      else
        match data.slots with
        | StringValue x -> x
        | _ -> failwith "Invalid string data"
  | _ -> failwith "Expecting a string"
 
let FlatternArray inst =
  match inst with
  | Instance data ->
      if data.classType <> Some Array
      then failwith "Expecting an array"
      else
        match data.slots with
        | Standard data -> List.map UnpackString (List.of_array data)
        | _ -> failwith "Expected an array"
  | _ -> failwith "Expected an array"
 
let rec AllInstVarNames c =
  if c = nil
  then []
  else
    match c with
    | Instance data ->
       match data.slots with
       | Standard slots ->  (AllInstVarNames (Super c)) @ (FlatternArray slots.[2])
       | _ -> failwith "Invalid class instance"
    | _ -> failwith "Invalid class"
 
And test it using
 
AllInstVarNames Object
AllInstVarNames Point
 
Now is where things start to get interesting. Object represents a class, but there is no reason why it should be special. It would be more useful if Object were itself an instance of another class.
 
let string_superclass = Instance { classType = Some String; slots = StringValue "superclass" }
let string_methodDictionary = Instance { classType = Some String; slots = StringValue "methodDict" }
let BehaviorInstanceVars =
   Instance { classType = Some Array; slots = Standard [| string_superclass; string_methodDictionary |] };;
let Behavior = Instance { classType = None; slots = Standard [| Object ; nil; BehaviorInstanceVars |] }
let string_instanceVars = Instance { classType = Some String; slots = StringValue "instanceVariables" }
let ClassDescriptionInstanceVars =
   Instance { classType = Some Array; slots = Standard [| string_instanceVars  |] };;
let ClassDescription = Instance { classType = None; slots = Standard [| Behavior ; nil ; ClassDescriptionInstanceVars |] }
let Class = Instance { classType = None; slots = Standard [| ClassDescription ; nil ; UndefinedObjectInstanceVars|] }
let MetaClass = Instance { classType = None; slots = Standard [| ClassDescription ; nil ; UndefinedObjectInstanceVars|] }
let ObjectClass = Instance { classType = Some MetaClass; slots = Standard [| Class ; nil; UndefinedObjectInstanceVars |] }
setType Object ObjectClass
let BehaviorClass = Instance { classType = Some MetaClass; slots = Standard [| ObjectClass ; nil; UndefinedObjectInstanceVars|] }
setType Behavior BehaviorClass
let ClassDescriptionClass = Instance { classType = Some MetaClass; slots = Standard [| BehaviorClass ; nil; UndefinedObjectInstanceVars|] }
setType ClassDescription ClassDescriptionClass
let MetaClassClass = Instance { classType = Some MetaClass; slots = Standard [| ClassDescriptionClass ; nil; UndefinedObjectInstanceVars|] }
setType MetaClass MetaClassClass
let ClassClass = Instance { classType = Some MetaClass; slots = Standard [| ClassDescriptionClass ; nil; UndefinedObjectInstanceVars|] }
setType Class ClassClass
 
Now we can add what we needed to do when we created the class Point. We needed to also create a class named PointClass, making it the type of Point. This class needs to inherit from ObjectClass and is of type MetaClass.
 
let PointClass = Instance { classType = Some MetaClass; slots = Standard [| ObjectClass ; nil; UndefinedObjectInstanceVars|] }
 
In a full implementation of Smalltalk-80, Squeak, we get the following values.
 
Point allInstVarNames  —> #(‘x’ ‘y’)
Point class allInstVarNames —> #(‘superclass’ ‘methodDict’ ‘format’ ‘instanceVariables’ ‘organization’ ‘subclasses’ ‘name’ ‘classPool’ ‘sharedPools’ ‘environment’ ‘category’ ‘traitComposition’ ‘localSelectors’)
 
In our model we get the values:
 
> AllInstVarNames Point;;
val it : string list = ["x"; "y"]
> AllInstVarNames PointClass;;
val it : string list = ["superclass"; "methodDict"; "instanceVariables"]
So it looks like we might have the initial class hierarchy right. Next time we will move on to adding some methods and a partial VM for interpreting them. If any of this is of interest, Eliot Miranda’s Cog Blog is currently covering his improvements to the existing VM implementation in Squeak.
 
Advertisements
This entry was posted in Computers and Internet. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s