Bluish Coder

Programming Languages, Martials Arts and Computers. The Weblog of Chris Double.


2009-07-16

Prototype Based Programming Languages

I've been reading up on protoype based programming languages recently. Mainly using the Io Programming Language and Self but also looking at LambdaMOO and similar languages. A good overview of using the prototype based approach to building programs is Organizing Programs without Classes. This post is based on examples from that paper and from Attack of the Clones which covers design patterns using Self.

Self

In the Self programming language objects are created using a literal object syntax. This syntax defines code and slots within the (| and |) delimiters. An example object looks like:

point = (|
  parent* = traits point.
  x.
  y.
|)

This creates an object with 3 slots. The slots are 'parent', 'x' and 'y'. The 'parent' slot is assigned an inital value of 'traits point' which is the traits object for points (more on what this is later). The '*' that is suffixed to the 'parent' slot means it is a prototype slot and used in the prototype slot lookup chain.

This means when a message is sent to the 'point' object the lookup starts with the 'point' object. If a slot with the messages name is not found in that object then each prototype slot (those suffixed with '*') are searched looking for a slot with that name.

So in the 'point' case, looking for 'x' will find it immediately in the point object. Looking for 'print' will not so it will look for it in the 'traits point' object. If it's not there it will look in that objects prototype slots and so on until it is found or the search is exhausted.

The idiom in Self (and other prototype based languages) is to create global objects like these and use 'clone' to create copies of it. So creating two different points would look like:

a = point clone.
b = point clone.

Notice that 'point' has no method slots. Only the 'x' and 'y' which contain data. The methods are defined in the 'traits point' object. The definition of that could look something like:

traits point = (|
  parent* = traits clonable.
  print = x println y println.
|)

This provides a method to print the 'x' and 'y' values of the object and another parent that provides other basic functionality like the ability to clone. The 'traits point' object doesn't define any data slots. It defines only methods. However it uses 'x' and 'y' messages that aren't defined. It expects to be used in a prototype slot of another object that defines the 'x' and 'y' slots (like our 'point' example earlier.

Separating the code out into data objects and trait objects allows the trait object to be reused in other objects. For example, an object that computes the 'x' and 'y' values rather than storing them can re-use the traits object:

computed_point = (|
  parent* = traits point.
  x = ..compute x..
  y = ..compute y..
|)

This 'computed_point' can be used anywhere a point is expected. The traits object sends the 'x' and 'y' messages when it needs their value and it doesn't matter if there stored as data as in the 'point' object, or as methods that calculate the value as in the 'computed_point' object. Each 'point' and 'computed_point' object shares a single trait object instance. This avoids the need to have multiple copies of the methods in each point object instance.

The prototype slots of an object effectively form an inheritance relationship. The way to subclass objects in Self is to create a new object and set a prototype slot to an instance of the parent object. Usually it's the trait objects that map the subclass relationship since it is those objects that contain the object behaviour (ie. the methods and no data). An example follows in Self of how a 'polygon' and 'filled_polygon' object can be modelled (this is from the 'Organizing Programs without Classes' paper):

polygon_traits = (|
  draw = ...draw using 'vertices' slot to get points...
|)

polygon = (|
  parent* = polygon_traits.
  vertices.
|)

filled_polygon_traits = (|
  parent* = polygon_traits.
  draw = ...draw using 'vertices' and 'fillPattern'...
|)

filled_polygon = (|
  parent* = filled_polygon_traits.
  vertices.
  fillPattern;
|)

Cloning the 'polygon' object and sending the 'draw' message will draw the polygon using the list of points held in the 'vertices' slot. Cloning the 'filled_polygon' object and sending the 'draw' message will draw using the specialized 'draw' method that also uses the 'fillPattern' slot to fill the polygon when drawing. This can re-use the 'draw' method in the 'polygon_traits' object if needed.

The new 'filled_polygon' object did require defining a new 'vertices' slot. Self allows multiple prototype slots, each of which is involved in the lookup for slot names. We can share the 'vertices' from the 'polygon' object by making that an additional prototype slot in 'filled_polygon'. This is often termed a 'data parent':

filled_polygon = (|
  parent* = filled_polygon_traits.
  dataParent* = polygon clone.
  fillPattern;
|)

Notice the 'dataParent' slot is a prototype slot (suffixed with a '*'). This means it participates in the slot lookup process. The data parent approach has an advantage over the previous example in that if we change the representation of the 'polygon' object then all new 'filled_polygon' instances will get this new representation. We don't need to edit the 'filled_polygon' definition for the modified or additional slots.

In the 'filled_polygon' example we re-used the 'vertices' slot from 'polygon'. We can also define subclasses that implement 'vertices' differently than 'polygon'. For example, a rectangle that stores the four corners and computes the vertices from this. Due to the seperation of state and behaviour this can be modelled easily:

rectangle_traits = (|
  parent* = polygon_traits.
  draw = ...draw rectangle using left, right, top, bottom...
  vertices = ...compute vertices list using left, right, etc...
|)

rectangle = (|
  parent* = rectangle_traits.
  left.
  right.
  top.
  bottom.
|)

Inheritance in Self can be dynamic if the prototype slots are made assignable. This means, at runtime, we can change the value of the slot used during message lookup, resulting in different behaviour. This can be used for objects that can be in different states.

An example is a 'file' object. It can be opened or closed. Some methods in 'file' can only be used when the file is open, and some only when it is closed. This could be managed by conditional checks in each method. Or the parent of the object could be changed to a different traits object depending on the state - this avoids the need for each method to check if the file is in the open or closed state:

open_file_traits = (|
  read = ...
  close = setParent: close_file_traits.
|)

closed_file_traits = (|
  open = setParent: open_file_traits.
|)

file = (|
  parent* = closed_file_traits.
|)

Methods like 'open' are only available on closed files. 'read' can only be called on opened files. This is basically the Strategy pattern made easy using Self's dynamic inheritance.

Io

Whereas Self defines the prototype lookup chain to be that of the prototype slots in an object, Io instead has a slot called 'protos' which is a list of all objects in the prototype chain. Instead of creating slots with a name suffixed with '*' you append to the existing 'protos' list.

The 'protos' list is initially populated when you clone an object with the object that you cloned. This is unlike Self where copying an object does a shallow copy of all the slots of that object. In Io you get a 'differential inheritance' model where your newly created object has no slots, just a 'protos' field that contains the original object that was cloned. The Self 'point' example I used earlier looks like:

Point := Object clone do(
  x := 0
  y := 0
)

Calling 'clone' on this new 'Point' object results in a new object that does not contain it's own 'x' and 'y' values. Instead its 'protos' field points to the 'Point' object which contains the values. When you set the 'x' value on the clone it will then create its own 'x' slot rather than changing the prototypes. In this way clones of big objects where relatively few slots are changed will save some memory:

a := Point clone
b := Point clone
a x = 5
a x println
 => 5
b x println
 => 0
a protos first == Point
 => true
b protos first == Point
 => true

This does have an interesting side effect in that if you clone a clone then you can end up with a longish prototype chain for the method lookup:

a := Point clone
b := a clone
c := b clone
c protos first == b
 => true
c protos first protos first == a
 => true
c protos first protos first protos first == Point
 => true

Inheritance is handled in much the same manner as Self but you need to manipulate the 'protos' slot instead of having multiple prototype slots. The filled polygon example looks like:

PolygonTraits = Object clone do(
  draw := method(vertices foreach(v, v println))
)

Polygon := PolygonTraits clone do(
  vertices := list(1,2,3,4)
)

FilledPolygonTraits := PolygonTraits clone do(
  draw := method(resend; fillPattern println)
)

FilledPolygon := FilledPolygonTraits clone do(
  appendProto(Polygon clone)
  fillPattern := "solid"
)

Polygon clone draw
  => 1
     2
     3
FilledPolygon clone draw
  => 1
     2
     3
     "solid"

'appendProto' appends an object to the prototype chain which is initially 'FilledPolygonTraits' in this examples as that was the initial object we cloned. The dynamic inheritance example can also be done in Io:

OpenFileTraits := Object clone do(
  read := method(n, "Reading #{n} bytes" interpolate println)
  close := method(
    self removeProto(OpenFileTraits)
    self appendProto(ClosedFileTraits)
  )
)

ClosedFileTraits := Object clone do(
  open := method(
    self removeProto(ClosedFileTraits)
    self appendProto(OpenFileTraits)
  )
)

File := Object clone do(
  init := method(self appendProto(ClosedFileTraits))
)

f := File clone
f read(255)
  => Exception: File does not respond to 'read'
f open
f read(255)
  => reading 255 bytes
f open
  => Exception: File does not respond to 'open'
f close

It's a bit more work than in Self to manually manage the prototype chain but does work.

JavaScript

JavaScript is also a prototype based programming language. Unlike Self or Io it only allows one object to be used as the prototype in any given object. This is stored in a hidden 'proto' member and cannot be updated once set on construction (some implementations allow changing it however). Objects are created by using the 'new' keyword on a constructor function that initializes the object. For now I'll leave it as an exercise for the reader to implement the examples above in JavaScript. I'd be interested in the approaches people take.

Tags


This site is accessable over tor as hidden service mh7mkfvezts5j6yu.onion, or Freenet using key:
USK@1ORdIvjL2H1bZblJcP8hu2LjjKtVB-rVzp8mLty~5N4,8hL85otZBbq0geDsSKkBK4sKESL2SrNVecFZz9NxGVQ,AQACAAE/bluishcoder/-44/


Tags

Archives
Links