Efficient sideways composition in Pepsi via 'Lieberman' prototypes

1   Introduction

1.1   Inheritance and delegation

In Lieberman prototypes, delegation occurs between objects (not between object behaviours). Any object can delegate messages to any other object at any time. The entire chain of delegation between any number of prototypes is considered a single composite object. The meaning of self is independent of the number of times a message has been delegated between prototypes since the original send. Sending to self from any prototype within the composite object causes the dispatch to begin again in the 'outermost' prototype.

2.1   Receiver splitting

Pepsi method signatures are augmented accordingly. A method

FamilyName messageName: arguments... [ ... ]

oop FamilyName__messageName(oop closure, oop self, arguments...) { ... }

oop FamilyName__messageName(oop closure, oop stateful_self, oop self, arguments...) { ... }

self selector: arguments...

_send(s_selector, self, arguments...)

self->v_instVarName

stateful_self->v_instVarName

Both self and stateful_self are treated by the compiler as normal method arguments. If 'self' appears free in a lexically-enclosed block then self will be assigned a slot in the state vector of the block's defining context that is stored in the closures created each time control passes the block's point of definition in the program. Similarly, if an instance variable appears free in an inner block then stateful_self will be assigned to a slot in the state vector, and hence captured and stored in all closures associated with the block. This guarantees correct (and intuitively expected) behaviour of sends to 'self' and accesses to state within arbitrarily-nested blocks of prototypical methods.

2.2   Multi-dimensional dynamic bind

Message sends were previously implemented by code equivalent to

#define _send(MSG, RCV, ARG...) ({		\
  register oop _r= (RCV);			\
  struct __closure *_c= _bind((MSG), _r);	\
  (_c->method)((oop)_c, _r, ##ARG);		\
})

struct __lookup {
  struct __closure *closure;
  oop               prototype;
};

#define _send(MSG, RCV, ARG...) ({					\
  register oop _r= (RCV);						\
  struct __lookup _l= _bind((MSG), _r);					\
  (_l.closure->method)((oop)_l.closure, _l.prototype, _r, ##ARG);	\
})

The implementation of _bind() is extended from the original one-dimensional lookup

struct __closure *_bind(oop selector, oop receiver)
{
  if (cache[receiver.vtable].selector == selector)
    return cache[receiver.vtable].closure;
  assoc := receiver.vtable.lookup(selector);
  if (assoc == nil)
    errorDoesNotUnderstand();
  cache[receiver.vtable].selector= selector;
  return cache[receiver.vtable].closure= assoc.closure;
}

struct __lookup _bind(oop selector, oop receiver)
{
  do {
    if (cache[receiver.vtable].selector == selector)
      return (struct __lookup){ cache[receiver.vtable].closure, receiver };
    assoc := receiver.vtable.lookup(selector);
    if (assoc != nil) {
      cache[receiver.vtable].selector= selector;
      cache[receiver.vtable].closure= assoc.closure;
      return (struct __lookup){ assoc.closure, receiver };
    }
    receiver := receiver._delegate();  /* message send */
  } while (receiver != nil);
  errorDoesNotUnderstand();
}

The overhead (once caches have settled) for this implementation strategy is (on average) one method cache probe and one message send for each step along the delegation chain. The overhead for objects that do not participate in prototypical delegation is essentially zero: their '_delegate' method always returns nil and is only ever invoked immediately before a guaranteed 'doesNotUnderstand' situation. No state whatsoever is added to these objects.

Prototype : Object ( next )

Prototype _delegate [ ^next ]

Prototype withDelegate: anObject
[
    self := self new.
    next := anObject.
]

A : Prototype ()

A a	[ 'A.a' putln ]

B : Prototype ()

B a	[ 'B.a' putln ]
B b	[ 'B.b ' put.  self a ]

C : Prototype ()

C c	[ 'C.c ' put.  self a; b ]

[
    | a |
    a := A withDelegate: (B withDelegate: C new).
    '======== a a:\n' put.  a a.
    '======== a b:\n' put.  a b.
    '======== a c:\n' put.  a c.
]

======== a a:
A.a
======== a b:
B.b A.a
======== a c:
C.c A.a
B.b A.a

4   Caveats

The default definition of 'new' clones only the first prototype in the delegation chain. This method must be overridden if all (or some arbitrary portion) of the delegation chain is to be duplicated when cloning the 'composite object' formed by them.

Bullet-proof proxies, formed by a two-deep delegation chain in which the first prototype is the proxy and the second is the object 'wrapped' by the proxy. All sends to self within methods of the wrapped object will be invoked on the enclosing proxy object.

Layers and Context-Oriented Programming. Supporting these effectively was the principal motivation for adding 'Lieberman' prototypes to Pepsi.

Implementation object for JavaScript, Python and similar languages.

Using 'here sends' to implement robust proxies (methods that cannot be overriden in a more specific prototype within the composite object).

'Perfect' encapsulation: no state whatsoever is visible between prototypes. Message sends are the only form of interaction between prototypes.