It's Actors All The Way Down

One important difference between Kernel and traditional LISP/Scheme is Kernel’s pervasive use of encapsulated types [1]. There is a clear distinction in Kernel between decomposable structures and opaque objects. Encapsulated types are a significant contributor toward smooth extensibility. They allow the definition of objects, and operations on those object, that are indistinguishable from primitives. We will demonstrate this extensibility by implementing a Banker’s Queue [2] in both Functional and Object-Oriented forms.

Functional Queue

As previously described, a Banker’s Queue maintains a pair of stacks. The “front” stack contains elements ready to be taken from the queue, from first to last. The “back” stack contains elements put on the queue, from last to first. The queue is normalized by ensuring that the “front” stack is only empty when the queue is empty. If the “front” stack is empty, the normalization procedure transfers items from the “back” stack to the “front” stack, reversing their order in the process. This strategy yields amortized O(1) performance.

We will find it convenient to define a simple implementation of reverse for lists. Our implementation “pop”s elements from the “back” stack, and “push”es them on the “front” stack using the push-pop helper function. The push-pop function returns just the “front” stack, since the “back” stack will always become empty in the process.

($define! push-pop
	($lambda (r s)
		($if (null? s)
			r
			(push-pop
				(cons (car s) r)
				(cdr s)))))
($define! reverse
	($lambda (s)
		(push-pop () s)))

With push-pop defined, reverse is simply push-pop with an empty “front” stack to reverse the “back” stack and return it.

Now we build an encapsulated Functional Queue data type. The Kernel $provide! operative is a convenient way to export a limited set of identifiers from an encapsulated environment. We will use it to define the following:

(new-q)

Create a new (empty) functional queue object.

(q? . objects)

Return #t iff all objects are functional queues.

(q-empty? queue)

Return #t iff queue is an empty functional queue.

(q-put queue item)

Return the new queue created by adding item to the back of queue.

(q-take queue)

Return (item new-queue) where new-queue is queue after item is removed from the front.

Note that the symbols E, D and q-norm are not exported. They are visible only within the local environment used to evaluate to body of $provide!, and thus to each function defined there.

($provide! (new-q q? q-empty? q-put q-take)
	($define! (E q? D) (make-encapsulation-type))
...

Kernel’s built-in make-encapsulation-type applicative creates new encapsulated data type and returns a set of tools for manipulating that type. The encapsulator/constructor (E value) creates an instance of the encapsulated type, initialized with value. The type predicate (q? . objects) returns #t iff all objects are instances of the encapsulated type. The decapsulator/accessor (D object) retrieves the encapsulated value originally passed to E.

...
	($define! new-q
		($lambda ()
			(E (cons () ()))))
...

new-q constructs a new (empty) queue. The queue’s internal representation is simply a pair of stacks encapsulated by E. The front and back stacks are both initialized to (), representing the empty state. Note that the representation can only be accessed via the decapsulator D, which is not exported.

...
	($define! q-empty?
		($lambda (obj)
			(($lambda ((p . q))
				(null? p))
			(D obj))))
...

q-empty? checks a queue for the empty condition. The object obj is decapsulated with D (which signals an error if obj was not encapsulated by E) to access the representation. The representation is passed to an anonymous function which destructures it into a front stack p and back stack q. The queue is empty if the front stack is ().

...
	($define! q-norm
		($lambda (p q)
			($if (null? p)
				(E (cons (reverse q) ()))
				(E (cons p q)))))
...

q-norm is a helper function (not exported) that constructs a normalized encapsulated queue given a front stack p and back stack q. If the front stack is empty, the front stack becomes the reversed back stack and the back stack becomes empty. Otherwise, the front and back stacks are simply paired and encapsulated.

...
	($define! q-put
		($lambda (obj x)
			(($lambda ((p . q))
				(q-norm p (cons x q)))
			(D obj))))
...

q-put “adds” an item x to the back of a queue obj. A new queue is built by adding x to the back stack, then returning the normalized and encapsulated result. Note that the original queue obj is unchanged.

...
	($define! q-take
		($lambda (obj)
			(($lambda (((x . p) . q))
				(list x (q-norm p q)))
			(D obj)))))

q-take “removes” an item from the front of a queue obj. The item x is extracted by the destructuring pattern, as is the remainder of the front queue p and the back queue q. A list is returned consisting of the item x and the new queue (normalized and encapsulated). Note that the original queue obj is unchanged.

Usage Example

The following example illustrates use of a functional queue. We use top-level variables to maintain the changing queue state.

($define! q (new-q))         ; create empty q
(q? q)                       ; returns: #t
(q-empty? q)                 ; returns: #t
($define! q (q-put q 1))     ; add 1 to q
(q-empty? q)                 ; returns: #f
($define! q (q-put q 2))     ; add 2 to q
($define! (x q) (q-take q))  ; remove 1 from q
($define! (y q) (q-take q))  ; remove 2 from q
(q-empty? q)                 ; returns: #t
(list x y)                   ; returns: (1 2)

Object-Oriented Queue

The functional version of the Banker’s Queue is stateless. Each queue state is a persistent immutable value (though unreferenced states will be garbage-collected, eventually). What if we want the queue to exhibit stateful behavior? One possible design would be to encapsulate the queue state in a stateful object. This is what I’ll refer to as an Object-Oriented Queue data type.

We will represent our stateful objects with mutable environments. We will treat bindings in the environment as named fields of our object. This requires a pair of operatives to set/get field values.

($define! $set!
	($vau (env name value) dyn
		(eval
			(list $define! name 
				(list (unwrap eval) value dyn))
			(eval env dyn))))
($define! $get
	($vau (env name) dyn
		(eval name 
			(eval env dyn))))

The operative ($set! env name value) assigns a new value to the field name in the environment env. A compatible (but slightly more general) version of this operative is pre-defined in Kernel. The operative ($get env name) returns the value of field name in environment env. Both are operatives because name is the (unevaluated) symbol which names the field.

Now we build an encapsulated Object-Oriented Queue data type. Once again we use $provide! to selectively export the following definitions:

(new-queue)

Create a new (empty) object-oriented queue object.

(queue? . objects)

Return #t iff all objects are object-oriented queues.

(queue-empty? queue)

Return #t iff queue is an empty object-oriented queue.

(queue-put! queue item)

Add item to the back of queue (returns #inert).

(queue-take! queue)

Remove and return an item from the front of queue.

($provide! (new-queue queue? queue-empty? queue-put! queue-take!)
	($define! (E queue? D) (make-encapsulation-type))
...

As before, we use make-encapsulation-type to define an encapsulator, type predicate and decapsulator. Only the type predicate queue? is exported.

...
	($define! new-queue
		($lambda ()
			($define! Q (new-q))
			(E (get-current-environment))))
...

new-queue constructs a new (empty) object-oriented queue. The queue’s internal representation is an environment where Q is bound to a newly-created functional queue. The environment we use to represent our object is the local environment of the constructor (which has no initial bindings because it has no arguments). We capture this local environment with get-current-environment and encapsulate it with E.

...
	($define! queue-empty?
		($lambda (this)
			($let ((obj (D this)))
				(q-empty? ($get obj Q)))))
...

queue-empty? checks an object-oriented queue for the empty condition. The object this is decapsulated with D (which signals an error if this was not encapsulated by E) and the representation (environment) is bound to obj. We use $get to retrieve the underlying functional queue Q and check to see if it is empty.

...
	($define! queue-put!
		($lambda (this x)
			($let ((obj (D this)))
				($set! obj Q
					(q-put ($get obj Q) x)))))
...

queue-put! adds an item x to the back of this object-oriented queue. Note the “!” suffix indicating that this causes mutation. We retrieve the underlying functional queue Q with $get, and use q-put to construct a new queue, which is assigned back to Q with $set!.

...
	($define! queue-take!
		($lambda (this)
			($let ((obj (D this)))
				($let (((x QQ) (q-take ($get obj Q))))
					($set! obj Q QQ)
					x)))))

queue-take! removes and returns an item x from the front of this object-oriented queue. Note the “!” suffix indicating that this causes mutation. We retrieve the underlying functional queue Q with $get, and use q-take to extract an item x and construct a new queue QQ. The new queue QQ is assigned back to Q with $set!. The item x is returned.

Usage Example

The following example illustrates use of an object-oriented queue. The queue state is encapsulated and maintained inside the object.

($define! q (new-queue))  ; create empty q
(queue? q)                ; returns: #t
(queue-empty? q)          ; returns: #t
(queue-put! q 1)          ; add 1 to q
(queue-empty? q)          ; returns: #f
(queue-put! q 2)          ; add 2 to q
(queue-take! q)           ; returns 1
(queue-take! q)           ; returns 2
(queue-empty? q)          ; returns: #t

Summary

We have shown two implementations of a Banker’s Queue using encapsulated data types in Kernel. One implementation is purely functional. The other is object-oriented, using first-class environments to model mutable (private) named fields. Kernel’s rich support for manipulating first-class environments gives us a powerful and flexible mechanism for extensibility.

References

[1]

J. Shutt. Revised^-1 Report on the Kernel Programming Language. Technical report WPI-CS-TR-05-07, Worcester Polytechnic Institute, Worcester, MA, March 2005, amended 29 October 2009.

[2]

C. Okasaki. Purely Functional Data Structures. Cambridge University Press, 1998.