A bit harder

The last few exercises have been easy.  These will be intermediate.

So far, we've been using the integer serial numbers to refer to audit records when we don't have the record itself.  The record can be read and written in a transaction, but outside the transaction we need a non-persistent object to act as a name.  The problem with integers is that they aren't typed: whatever the number 42 means in one context is unlikely to be relevant in another.  The second problem is that we are deriving the integers from an underlying implementation artefact.  The number 42 just identifies an object to most of the code, but it derives from an index into a vector.  If we change how the number is generated, then any numbers we already know about would have to change as well.

We need an external naming scheme so we can refer to the audit records in a repository.

Exercise 5:

1. Have a required "name" argument when creating a repository.  The name should be immutable and you should be able to access the name without a transaction.
2. Define an identifier object.
   

   (defstruct (distributed-identifier
               (:conc-name did/)
               (:constructor %make-distributed-identifier (domain repository class numeric-id))
               (:copier nil)
               (:predicate distributed-identifier?))
     "DIDs are interned, so you can use EQ to test for equality.  However, you should
      never modify the slots in a DID."
   
     (domain ""     :read-only t :type string)
     (repository "" :read-only t :type string)
     (class nil     :read-only t :type (or null keyword))
     (numeric-id 0  :read-only t :type non-negative-integer))
   

   You can skip the domain element for now, but the other fields are needed.
   
3. Define a printer for a distributed-identifier so they print like this: [test-repository.AUDIT-RECORD.22] the name, class, and numeric id are printed with periods between them.
4. Define a parser that can read the fields out of a string.
5. Hook up the parser to the reader so that programmers can use the square bracket notation as a literal in a program.
6. Intern these objects in a weak hash table.  We want to be able to use EQ to test these. So typing (eq [test-repository.AUDIT-RECORD.22] [test-repository.AUDIT-RECORD.22]) will return true. If two distributed-identifiers print the same way, then they refer to the same object and they should be EQ.
7. Add a mapping table to the repository for the audit records.  You want it so that when an audit record is newly created it will have a new identifier. You'll want to decouple the assignment of the audit-record serial number from the assignment of the numeric ID in the distributed-identifier.  This is so we can import audit-records from other repositories.
   
   
   Consider [test-repository.AUDIT-RECORD.22]. It is the twenty-second audit record created by the test repository, but it is not necessarily at the twenty-second offset in the repository's table of audit-records. It could be, for example, at location 165. The mapping table gives the location. If a new audit-record is created, say at location 166, a new entry in the mapping table will map [test-repository.AUDIT-RECORD.23] to location 166.
   
   The mapping table will be persistent, and thus require a transaction to read.

Fairly easy

The prior post had some easy exercises.  This is easy, too.

Every audit record in a repository has a unique serial number (relative to the repository).  We want a way to represent sets of serial numbers.

Exercise 4:  Implement these:

Constructors:

• bitmap->serial-number-set repository vector-1b
• range->serial-number-set repository start end
  Start is inclusive, end is exclusive.
• list->serial-number-set repository list

Selectors and predicates:

• serial-number-set? object
• serial-number-set/repository serial-number-set
• serial-number-set/empty? serial-number-set
• serial-number-set/equal? left-serial-number-set right-serial-number-set
• serial-number-set/member? serial-number-set serial-number
• serial-number-set->bitmap serial-number-set

These return new sets rather than mutate the old ones:

• serial-number-set/adjoin serial-number-set serial-number
• serial-number-set/remove serial-number-set serial-number
• serial-number-set/union left-serial-number-set right-serial-number-set
• serial-number-set/exclusive-or left-serial-number-set right-serial-number-set
• serial-number-set/intersection left-serial-number-set right-serial-number-set

Two more:

• serial-number-set/intersaction? left-serial-number-set right-serial-number-set
  Returns true if the intersection is not empty. Ought to be faster than (serial-number-set/empty? (serial-number/intersection left right))
• serial-number-set/last-serial-number serial-number-set
  Returns the largest serial number in the set.
  
  

We'll use serial numbers and serial-number-sets so we can refer to audit-records and sets of audit-records without needing the records themselves.  We can only get to the records within a transaction, but we can refer to them by serial number outside of a transaction.

Fun with Audit Trails!

Gotta change direction here.  It's getting boring.  Let's implement an audit trail!  How hard could it be? We'll make an audit trail out of audit records.  Pick your favorite language and try this.

Exercise 1:  Implement an audit record.  Make sure it has these features:

• a timestamp of when the record was created
• a user-id to tell us who created the record
• a reason why in the form of human readable text
  

• immutable, including transitively reachable subobjects
• Malformed records cannot be created.  Automatically set the timestamp so it cannot be forged.

Now we have to keep them somewhere safe, and get them back on occasion.

Exercise 2a: Make a repository with some sort of stable storage for a backing store, like a file.

Exercise 2b:  When creating an audit record, log it to stable storage. Make the repository be a required argument for creation of an audit record.  Log the record in the repository, but don't store info about the repository itself in the record.  The record doesn't have to know where it lives.

Exercise 2c:  Have a way to load all the audit records back in from stable storage.  Intern the audit records so re-loading is idempotent and eq-ness is preserved.

Exercise 3:  Implement random access to a repository's audit log (indexed by integer)

These are all very easy.  Don't worry, I'll make it harder.

Persistent vectors

Simulating mutation by creating a new object is reasonable for CLOS objects, but it is terrible idea for persistent vectors. The large amount of copying would be bad enough, but algorithms that rely on growable vectors (by calling vector-push) will change from linear to quadratic in space. That's a disaster.

We simulate mutation by replacing an entry in the object-map. This forces the granularity of mutation to be the same as the granularity of the object-map. In other words, we cannot update just a single item in a vector because there is no object-map entry referring to just that item.

So why not fix that? The obvious solution is to allocate a contiguous set of object-ids. Easy enough, but if we want to "grow" the vector we'll have a problem. The vector storage itself can easily be moved, but the range of object-ids that map to the vector cannot easily be extended.

My solution was to change how object-ids and the object-map work. The object-map maps integers to persistent objects. Conceptually, the object-map itself is a vector. If we add an orthogonal index to object-map it becomes a 2-dimensional array. Now we can place vectors in the map and assign them a single primary index and map the secondary indices on to the vector elements. Vectors can grow (or shrink) without changing their primary index.

Now that we have persistent vectors that we can mutate, we can create mutable persistent cons cells (just a 2-element vector) and mutable persistent hash tables.

Faking mutability

Dan Lentz said

I do think the term immutability is being thrown around a bit here somewhat in denial of the reality that what we are in the very process of doing is mutating the instance. Is immutability even the goal? I mean, yes the wbtree is persistent in the sense that older versions of an object are never overwritten, but that doesn't preclude us from representing changes to an object in subsequent updates to the tree and expressing its value at a given point in time as MVCC. Any given version of the object is immutable, but the object itself can model mutability without detracting from that.

Exactly what I was going to write about next!

When we create a persistent object, we assign it a unique object id. We cannot change the object, but we can change mapping from ids to objects. The procedure remake-instance does this. remake-instance takes an persistent object and some initargs and creates a brand new object, but it updates the object-map with the old object id. We simulate slot mutation by creating a new object that differs only in that slot value and giving it the old object id.

This simplifies transaction handling quite a bit. If a transaction aborts we want to restore the world to the state it was in when we started. Since we didn't actually change the original object, all we need to do is go back to using the old object map.

You could use a monad.

On the Racket Users list Ben Duan asked

Scenario: A piece of data is determined in the first function `f1', but is only processed in a sub-sub-sub-… function `fx'.

One way is to use pass `the-data' as arguments from `f1' through `f2' all the way down to `fx':

(define f1 (the-data …)
  …
  (f2 the-data …)
  …)

(define f2 (the-data …)
  …
  (f3 the-data …)
  …)

…

(define fx (the-data …)
  … the-data …)

But in the above way, the body of `f2', `f3', `f4' and so on doesn't use `the-data'. It is only passed to the next function. And I still have to add the argument `the-data'.

Are there other ways to solve this problem?

You could use a monad.

The basic gist of it is that instead of manipulating the-data, we manipulate functions. So the inner functions f2, f3, ... will change from this:

(define (f2 the-data arg arg …)
      …
      (f3 the-data x y …))

to this:

(define (f2 arg arg …)
  (lambda (the-data)
      …
      ((f3 x y …) the-data)))

We just move the-data to the end of the argument list and curry the functions. That makes things more complicated at first, but the inner functions that don't actually use the-data can be eta-reduced. (lambda (x) (f x)) => f

So f2 eta-reduces to:

(define (f2 arg arg …)
      …
      (f3 x y …))

and all mentions of the-data disappear in the inner functions (pretty slick!) The innermost fx can't be reduced this way, of course, and the callers of f0 have to change to pass the initial value of the-data.

I just did this with an ad-hoc code transformation. A "monad" formalizes this. (and I skipped over a lot of detail.)

Matthias Felleisen elaborated further:

Here is what Joe is saying, with fake macros; the first two parts are real:

#lang racket

;; -----------------------------------------------------------------------------
;; an example using lexical scope

(define (f1-lexical-scope x)
  (define the-data (sin x))
  (define (f2 y)
    `(f2 ,(f3 y)))
  (define (f3 z)
    `(f3 ,(f4 z)))
  (define (f4 w)
    `(f4 ,the-data ,w))
  (f2 10))

(f1-lexical-scope pi)

;; -----------------------------------------------------------------------------
;; the same example with the 'monad' spelled out

(define (f1-monad x)
  (define the-data (sin x)) ;;
  ((f2 10) the-data))

(define ((f2 y) the-data)
  `(f2 ,((f3 y) the-data)))

(define ((f3 z) the-data)
  `(f3 ,((f4 z) the-data)))

(define ((f4 w) the-data)
  `(f4 ,the-data ,w))

(f1-monad pi)

;; -----------------------------------------------------------------------------
;; a sketch of how syntax would hide the monad where needed

;; the following macros are fake, because I don't have time to write them out:
;; see the HtDP language macros for #%app, which register functions too

;; defines the-data and initializes it
(define-syntax-rule (create-store x) (define the-data x))
;; registers f as a store-passer
(define-syntax-rule (define-store-passer (f x) e) (define ((f x) the-data) e))
;; this supplements #%app so that when a registered store-passer f is applied,
;; it picks up the-data in a curried application; other functions work normally
(define-syntax-rule (apply-store-passer f x ...) (old-apply (f x ...) the-data))
;; pick up the-data from secret stash
(define-syntax-rule (access-store) 42)

;; if you had these macros, the above would read like this:

(define (f1-monad.v2 x)
  (create-store (sin x)) ;;
  (f2 10))

(define-store-passer (f2.v2 y)
  `(f2 ,(f3 y)))

(define-store-passer (f3.v2 z)
  `(f3 ,(f4 z)))

(define (f4.v2 w)
  `(f4 ,(access-store) ,w))

(f1-monad.v2 pi)

What about...

John Cowan said:

The arguments passed to `make-instance` are the sum total of the information needed to create the instance in its initial state.

Since you require that instances be transitively immutable, the initial state is the only state.

If you have those arguments squirreled away, then you can create another instance in the exact same initial state.
∎

That's the basic argument. It's demonstrably false.

(setq foo (make-instance 'test-class))

(test-class/name foo)
ZIPPY

So the game begins. I point out a trivial technicality, you adjust for it.

The arguments passed to `make-instance` combined with the appropriate
defaults from the initargs are the sum total of the information needed
to create the instance in its initial state.

Well, that's wrong, too. As Dan Lentz pointed out, "What about any stateful behavior encoded into the objects class?"

I'm pretty sure you ultimately win. But by the time I run out of objections your argument is going to be a patchwork quilt of exceptions, special cases, "implementation artifacts", "things that might be technically wrong, but can never make a real difference", etc. etc.

This doesn't inspire much confidence in our proof.

Mr. Lentz also asked:
Couldn't it just have trapped the out of date schema version in shared-initialize and dispatched it off to update-instance-for-redefined-class?

I don't know. When we bring an object from the store, it isn't really an instance yet.