Mutable Objects in Kernel

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.
This entry was posted in Uncategorized and tagged , , , , , . Bookmark the permalink. Post a comment or leave a trackback: Trackback URL.

7 Comments

  1. Posted 2012-01-19 at 11:03 pm | Permalink

    Neatly done. A few items (most interesting first):

    Your $set! does not appear to be less general than Kernel’s built-in version; it should handle compound definiends just fine. Though it seems a worthwhile exercise to implement it here.

    In new-queue, the local environment has no initial *local* bindings. It does have plenty of visible bindings, not that they do any harm since the environment is encapsulated so that those who can access it are already able to see its parent environment. Using the local environment brings home the lesson that it’s really an *environment*, in the usual sense.

    “indicating that this is causes mutation” (spurious “is”).
    “an new (empty) queue” (spurious “-n”).

  2. Dale Schumacher
    Posted 2012-01-20 at 8:38 am | Permalink

    Thanks for your precision, John.

    Operationally, my $set! is the same as your standard version. Only my explanation is less general, focusing only on the “special case” of a single named field.

    I considered using make-environment to construct a truly-empy “dictionary” for the object. That’s still a valid implementation choice. In the back of my mind I was considering potential extensions for inheritance. Also, using the local environment was the simplest thing that seemed to work, and (as you said) is relatively harmless.

    Typos fixed. Thanks!

  3. Posted 2012-01-20 at 8:52 am | Permalink

    I object to the use of environments as “objects”, even if only internal to the implementation. Why? Environments are more powerful than a mere dictionary (e.g. they have a parent link and special rules governing name lookup). I fear that “let’s use 1st class environments for everything” may become the new “let’s use conses for everything” in Kernel.

  4. Dale Schumacher
    Posted 2012-01-20 at 9:03 am | Permalink

    Interestingly enough, that’s one of the points I wanted to make with this article. What other structured types does Kernel offer? Pairs, which have a rich history demonstrating their use in building nearly anything (but with what efficiency). And Environments, which are mutable Dictionaries (think Smalltalk) with a multiple-inheritence chaining mechanism.

    I think one of the best things about Kernel’s environments is that mutation is limited to environments to which you have direct access (not just inherited). This supports a copy-on-write semantics which reminds me of JavaScript objects. YMMV.

  5. Posted 2012-01-20 at 3:51 pm | Permalink

    The *other* other structured data type is, of course, the combiner. Using combiners as objects is a standard exercise in Scheme, and I gather past RxRS authors have had that style specifically in mind. Plus, of course, it’s the origin of the claimed analogy between procedures and actors. Oh yes, and in reflective Lisps, from what I understand of them, it’s a standard technique to use procedures as environments.

  6. Dale Schumacher
    Posted 2012-01-21 at 10:40 am | Permalink

    Of course! How could I have forgotten about procedural representation? I presume you mean the technique described in SICP section 2.1.3.

    Message-passing style, as described in 2.4.3 and elaborated in 3.1.1, uses quoted symbols to implement dynamic dispatch. Since Kernel discourages quoting, what would you recommend we use in place of these symbolic constants?

  7. Posted 2012-01-22 at 2:22 pm | Permalink

    I had to think about this, but (as often happens) eventually decided most solutions are making it harder than it has to be. A straightforward approach is to use strings. Strings have an external representation (a weakness of encapsulated types that I recognized from the outset but didn’t, and still don’t, see an obviously “Right” way to fix). Strings are also immutable (though I see I never even started adding content to that section of the Report).

One Trackback

  1. By Implementing Actors in Kernel on 2012-02-16 at 10:14 pm

    [...] predicates actor? and behavior? are exported. We also create an empty queue for events, using the object-oriented queue implementation shown [...]

Post a Comment

Your email is never published nor shared. Required fields are marked *

*
*