Unexciting code

Source code control isn't supposed to be interesting or exciting for the user. Blogging about source code control isn't going to be interesting or surprising for the reader, either. I'll spare you the walkthrough. You're old enough to figure it out without me holding your hand. It'll be more interesting if I blog about the problems and bugs we encountered.

Conman was the configuration manager built on the core ChangeSafe code. The master catalog in conman holds the highest level objects being managed.

(defclass master-catalog ()
  ;; subsystems and products (PC's) in this repository
  ((products   :initform nil
               :version-technique :composite-set
               :accessor master-catalog/products)


   (subsystems :initform nil
               :version-technique :composite-set
               :accessor master-catalog/subsystems)

   ;; All satellite repositories known to this master.  We don't allow
   ;; satellite repository names to change, though the projects they
   ;; contain may be renamed.  **WARNING** BE CAREFUL IF YOU OPERATE
   ;; in non-latest metaversion views of this list or you might try to
   ;; create a satellite which already exists.  Only update this list
   ;; using the latest metaversion.
   (satellite-repositories :initform nil :version-technique :composite-set)

   ;; Projects (a.k.a. ChangeSafe "classes") contained in satellite
   ;; repositories.  The descriptors contain the key mapping from a
   ;; project name to a satellite-repository-name.  We could almost
   ;; make this just a (project-name . satellite-name) mapping, but we
   ;; need to version project-name, and we also want to cache in the
   ;; master some information in the satellites so that we don't
   ;; always have to examine the satellites for often accessed
   ;; information.
   (classes :accessor master-catalog/classes
            :initform nil
            :version-technique :composite-set)

   ;; Cset-relationship-tuples is conceptually a list of sublists,
   ;; where each sublist is a tuple.  For every master cid which
   ;; results in the creation of satellite cids, a tuple is added
   ;; which enumerates the master cid and the satellite cids which it
   ;; caused to be created.  e.g. '((master.cid.1 satellite-1.cid.1
   ;; satellite-2.cid.1)) Because we want portable references, blah
   ;; blah blah, we actually reference DIDS of CHANGE-SET objects
   ;; rather than the cids.  We may instead wish to store CID-OBJECT
   ;; references.  TBD.

   ;; Right now, this information is maintained only for change
   ;; transactions which arise from WITH-CM-MASTER-TXN and
   ;; WITH-CM-SATELLITE-TXN.  This is ok, since those are the
   ;; interesting txns which manipulate satellite databases.

   ;; Note that because of the high volume of csets we expect to
   ;; track, we actually represent this information as a vector of
   ;; vectors to achieve space compaction.
   (cset-relationship-tuples :initform (make-instance 'persistent-vector
                                                           :initial-element nil
                                                           :size 1)
                             :version-technique :nonversioned)

   (cset-rel-tuples-index :initform (make-instance 'persistent-vector
                                                        :initial-element -1
                                                        :size 1)
                          :version-technique :nonversioned)

   ;; BOTH these slots are updated ONLY by vm-txn-note-change-set,
   ;; except for schema upgrading.

   ;; The cset-rel-tuples-index slot is a conceptual hash table into the
   ;; cset-relationship-tuples slot. This is used by
   ;; master-catalog-lookup-cset-relationship
   ;; to avoid an extremely costly linear search of cset-relationship-tuples.
   ;; This is very important for cset_add, cset_remove, and csets_from_file.

   ;; The idea is that the did-string of the master-cid's did is hashed.
   ;; Reducing that hash modulo the number of entries in cset-rel-tuples-index,
   ;; finds a "home" index of cset-rel-tuples-index. Using the sb32 value
   ;; in that element, we either have a -1 (so the entry is not in the
   ;; hash table) or we get an index into cset_relationship_tuples.
   ;; If there is no hash collision, that element of cset_relationship_tuples
   ;; will contain the desired master-cid did we are looking for. If it
   ;; isn't the one we want, we have had a hash collision, and we resolve it
   ;; by linear probing in the next-door (circularly) element of
   ;; cset-rel-tuples-index.
   ;; The number of elements of cset-rel-tuples-index is always a prime number,
   ;; and is also maintained to be more than twice as large as the number of
   ;; entries in cset-relationship-tuples. That is important, to prevent
   ;; clustering and slow searching. So when it grows, cset-rel-tuples-index
   ;; grows by a reasonable factor (about 2) so that it always contains
   ;; at least half "holes", that is, -1.  Further, we want to avoid frequent
   ;; growth, because growing requires computing every entry in the hash table
   ;; again. That makes for a big transaction, as every element of the
   ;; cid-relationship-tuple vector has to be mapped in, and rehashed with
   ;; the new size of cset-rel-tuples-index.
   ;; Space considerations: In Jack's db, there are roughly 40,000 elements
   ;; currently in the cset-relationship-tuples.  Suppose we had 100,000
   ;; elements. In Jack's db, it appears that the tuples are about 2 elements
   ;; each, average. Suppose it were 9. Then the tuples would take 4*(1+9)=40
   ;; bytes each, so 40*100,000 = 4Mb total (plus another 400,000 for the
   ;; cset-relationship-tuples vector itself).  This is large, but not likely
   ;; to be a cause of breakage anytime soon.


   ;; The cset-name-hashtable maps cset names to csets.  While the HP
   ;; model of ChangeSafe doesn't allow changing the name of a cset,
   ;; we allow this in general.  So this hash table is keyed by cset
   ;; name, and valued by all csets which EVER bore that name in their
   ;; versioned name component.  The hash value is therefore a list.
   ;; In the case of system augmented names (by
   ;; change_create/master_change), there shouldn't be any collisions.
   ;; We also use this slot to hash unaugmented user names to csets,
   ;; and those are far more likely to have collisions (one key ->
   ;; multiple csets).  In the case of un-augmented names, this is
   ;; expected. In the case of augmented names, this is an error.
   (cset-name-hashtable :version-technique nil
                        :initform (make-instance 'persistent-hash-table :size 1023)
                        :reader master-catalog/cset-name-hashtable)
   )
  (:documentation "Catalog/hierarchy-root of versioned information maintained in the master repository.")
  (:metaclass versioned-standard-class)
  (:schema-version 0))

Pretty straightforward, no? No? Let's list the products in the master catalog:

(defun cmctl/list-products (conman-request)
  "cheesy hack to list the products"
  (let ((master-repository-name (conman-request/repository-dbpath conman-request))
        (reason "list products")
        (userid (conman-request/user-name conman-request)))
    (call-with-master-catalog-transaction
     master-repository-name
     userid
     :master-metaversion :latest-metaversion
     :version :latest-version
     :reason reason
     :transaction-type :read-only
     :receiver (lambda (master-repository master-transaction master-catalog)
                 (declare (ignore master-repository master-transaction))
                 (collect 'list
                          (map-fn 't (lambda (product)
                                       (list (distributed-object-identifier product)
                                             (named-object/name product)
                                             (described-object/description product)))
                                  (master-catalog/scan-products master-catalog)))))))

That isn't very edifying.

Start from the end:

(master-catalog/scan-products master-catalog)

defined as

(defun master-catalog/scan-products (master-catalog)
  (declare (optimizable-series-function))
  (versioned-object/scan-composite-versioned-slot master-catalog 'products))

The optimizable-series-function declaration indicates that we are using Richard Waters's series package. This allows us to write functions that can be assembled into an efficient pipeline for iterating over a collection of objects. This code:

(collect 'list
   (map-fn 't (lambda (product)
                (list (distributed-object-identifier product)
                      (named-object/name product)
                      (described-object/description product)))
           (master-catalog/scan-products master-catalog)))

takes each product in turn, creates a three element list of the identifier, the project name, and the product description, and finally collects the three-tuples in a list to be returned to the caller. Here is what it looks like macroexpanded:

(COMMON-LISP:LET* ((#:OUT-917 MASTER-CATALOG))
  (COMMON-LISP:LET (#:OUT-914)
    (SETQ #:OUT-914 'PRODUCTS)
    (COMMON-LISP:LET (#:OUT-913 #:OUT-912)
      (SETQ #:OUT-913 (SLOT-VALUE-UNVERSIONED #:OUT-917 #:OUT-914))
      (SETQ #:OUT-912
              (IF *VERSIONED-VALUE-CID-SET-OVERRIDE*
                  (PROGN
                   (DEBUG-MESSAGE 4 "Using override cid-set to scan slot ~s"
                    #:OUT-914)
                   *VERSIONED-VALUE-CID-SET-OVERRIDE*)
                  (TRANSACTION/CID-SET *TRANSACTION*)))
      (COMMON-LISP:LET (#:OUT-911 #:OUT-910 #:OUT-909)
        (MULTIPLE-VALUE-SETQ (#:OUT-911 #:OUT-910 #:OUT-909)
          (CVI-GET-ION-VECTOR-AND-INDEX #:OUT-913 #:OUT-912))
        (IF #:OUT-911
            NIL
            (PROGN
             (IF (COMMON-LISP:LET ((#:G717-902 #:OUT-910))
                   (IF #:G717-902
                       #:G717-902
                       (THE T (CVI/DEFAULT-ALLOWED #:OUT-913))))
                 NIL
                 (PROGN
                  (SLOT-UNBOUND (CLASS-OF #:OUT-917) #:OUT-917 #:OUT-914)))))
        (DEBUG-MESSAGE 5 "Active ion vector for retrieval:  ~s" #:OUT-911)
        (COMMON-LISP:LET (#:OUT-908)
          (SETQ #:OUT-908
                  (IF #:OUT-911
                      #:OUT-911
                      (THE T #())))
          (COMMON-LISP:LET (#:ELEMENTS-907
                            (#:LIMIT-905 (ARRAY-TOTAL-SIZE #:OUT-908))
                            (#:INDEX-904 -1)
                            (#:INDEX-903 (- -1 1))
                            #:ITEMS-915
                            #:ITEMS-900
                            (#:LASTCONS-897 (LIST NIL))
                            #:LST-898)
            (DECLARE (TYPE SERIES::VECTOR-INDEX+ #:LIMIT-905)
                     (TYPE SERIES::-VECTOR-INDEX+ #:INDEX-904)
                     (TYPE INTEGER #:INDEX-903)
                     (TYPE CONS #:LASTCONS-897)
                     (TYPE LIST #:LST-898))
            (SETQ #:LST-898 #:LASTCONS-897)
            (TAGBODY
             #:LL-918
              (INCF #:INDEX-904)
              (LOCALLY
               (DECLARE (TYPE SERIES::VECTOR-INDEX+ #:INDEX-904))
               (IF (= #:INDEX-904 #:LIMIT-905)
                   (GO SERIES::END))
               (SETQ #:ELEMENTS-907
                       (ROW-MAJOR-AREF #:OUT-908
                                       (THE SERIES::VECTOR-INDEX
                                            #:INDEX-904))))
              (INCF #:INDEX-903)
              (IF (MINUSP #:INDEX-903)
                  (GO #:LL-918))
              (SETQ #:ITEMS-915
                      ((LAMBDA (ION-SOUGHT)
                         (CVI-INSERTION-RECORD/GET-VALUE-FOR-ION
                          (SVREF #:OUT-909 ION-SOUGHT) ION-SOUGHT))
                       #:ELEMENTS-907))
              (SETQ #:ITEMS-900
                      ((LAMBDA (PRODUCT)
                         (LIST (DISTRIBUTED-OBJECT-IDENTIFIER PRODUCT)
                               (NAMED-OBJECT/NAME PRODUCT)
                               (DESCRIBED-OBJECT/DESCRIPTION PRODUCT)))
                       #:ITEMS-915))
              (SETQ #:LASTCONS-897
                      (SETF (CDR #:LASTCONS-897) (CONS #:ITEMS-900 NIL)))
              (GO #:LL-918)
             SERIES::END)
            (CDR #:LST-898)))))))

To be continued...

Next step

We build a simple project/branch/version hierarchical abstraction, and we implement it on top of the core layer.

• a project is a collection of branches that represent alternative ways the state evolves. Every project has a main branch.
• A branch is a collection of versions that represent the evolution of the branch state over time.
• A version is a collection of change-sets with some trappings.
  
• A change-set is our unit of change.

When we do a read/write transaction, we'll add a new change set to the repository. Read-only transactions will specify a version for reading the core objects. Or two versions for generating diffs. Or maybe even three versions for a three-way merge.

Under this development model, developers will sync their workspace with the most chronologically recent version of the main branch. Their new change sets will be visible only to them, unless (until, we hope) they are "promoted" into the development branch.

We wanted to encourage frequent incremental check-ins. We wanted hook this up to Emacs autosave. Frequent check-ins of much smaller diffs breaks even.

Once you get to the point where your code passes all the tests, you promote it into the branch so everyone can use it. Every now and then the admins will "fork a relase", do some "cherrypicks" and make a release branch in the project.

Once you get to the point where your code passes all the tests, you promote it into the branch so everyone can use it. Every now and then the admins will "fork a relase", do some "cherrypicks" and make a release branch in the project.

The core code does all the heavy lifting, this is window dressing. The style: minimalist. Skin the change model.

This is turning into the code equivalent of a power-point lecture. You can read it yourself, I'm not going to walk you through it.

So that's it? Is that all there is? Many source code or change management systems do something more or less similar to this with files and directory trees instead of CLOS objects. Cute hack, but why all the fuss? Hasn't this been done?

If it seems obvious to you how we'd implement some of the usual source code control operations, good. We don't have to train you.

I wont insult your intelligence explaining in detail how to do a rollback by removing a change-set from a version. Use SETF, of course.

I hope nobody notices the 300 lb chicken sitting next to that shady-looking egg in the corner.

And something for philosopher/implementors to worry about: If I demote the change-set that instantiates an object, where does the object go? Is it possible create a reference to an uninstantiated object? What happens if you try to follow it?

Putting it all together

A ChangeSafe repository is implemented as a transient wrapper object around a persistent object. The wrapper object caches some immutable metadata. You'd hate to have to run a transaction in the middle of the print function in order to print the repository name. The wrapper also contains metadata associated with the backing store that the repository is using.

Oh yeah, there is something interesting going on in the wrapper, We keep track of the ongoing transactions by mapping the user-id to a list of transaction contexts (every nested transaction by a user "pushes" a new txn-context).

Anyway, it's the repository-persistent-information that has the interesting stuff:

(defclass repository-persistent-information ()
  (
   (type  :initarg :type
          :initform (error "Required initarg :type omitted.")
          :reader repository-persistent-information/type
          :type repository-type)

   ;; Database parent is the root extent for an extent database, or the master database for a satellite.
   ;; Root extents or master repositories won't have a parent
   (parent-repository :initarg :parent-repository
                      :initform nil
                      :reader repository-persistent-information/parent
                      :type (optional relative-pathname))

   ;; Satellite repositories is non-nil only for master repositories.
   (satellite-repositories :initform nil
                           :initarg :satellite-repositories
                           :accessor repository-persistent-information/satellite-repositories)

   (canonical-class-dictionary :initform (make-instance 'canonical-class-dictionary)
                               :reader repository-persistent-information/canonical-class-dictionary)
   (cid-master-table :initform (make-instance 'cid-master-table)
                     :reader repository-persistent-information/cid-master-table)
   (root-mapper  :initarg :root-mapper
                 :initform (error "Required initarg :root-mapper omitted.")
                 :reader repository-persistent-information/root-mapper)
   (cid-mapper   :initarg :cid-mapper
                 :initform (error "Required initarg :cid-mapper omitted.")
                 :reader repository-persistent-information/cid-mapper)
   (local-mapper :initarg :local-mapper
                 :initform (error "Required initarg :local-mapper omitted.")
                 :reader repository-persistent-information/local-mapper)
   (locally-named-roots :initarg :locally-named-roots
                        :initform (error "Required initarg :locally-named-roots omitted.")
                        :reader repository-persistent-information/locally-named-roots)
   (anonymous-user :initarg :anonymous-user
                   :initform nil
                   :reader repository-persistent-information/anonymous-user))
  (:default-initargs :node-id +object-id-of-root+)  ;; force this to always be the root object.
  (:documentation "Persistent information describing a repositiory, and stored in the repository")
  (:metaclass persistent-standard-class)
  (:schema-version 0))

The repository-type is just a keyword:

(defconstant *repository-types* '(:basic :master :satellite :transport :extent :workspace)
  "Type of repositories.  Note that all but :EXTENT types of repositories
   serve as root extents for databases which have multiple extents, and therefore imply extent.")

The parent-repository and the
satellite-repositories are for juggling multiple "satellite" repositories for holding particular subsets of changes (for, say, geographically distributing the servers for different product groups).

The canonical-class-dictionary is an intern table for objects.

The cid-master-table is (logically) the collection of audit-records. A CID (after change id) is represented as an integer index into the master table.

The root-mapper is a mapping table from distributed identifiers to objects.

The cid-mapper is a mapping table from the distributed identifier that represents the CID to the integer index of that CID in the master table. It is a subtable of the local mapper.

The local-mapper is submapping of the root-mapping, but a supermapping of the cid-mapper.

The locally-named-rootsis a hash table for storing the root objects of the repository.

Finally, there is the anonymous-user slot, which is the user id assigned for bootstrapping.

And all this crap is in support of this procedure:

(defun call-with-repository-transaction (&key repository 
                                              transaction-type
                                              user-id-specifier
                                              reason

                                              ;; generally, you only want to specify these two
                                              meta-cid-set-specifier
                                              cid-set-specifier 
                                              ;; but if you are doing a comparison,
                                              ;; specify these as well
                                              aux-meta-cid-set-specifier
                                              aux-cid-set-specifier 

                                              receiver)
  (check-type user-id-specifier (or keyword distributed-identifier))
  (check-type transaction-type repository-transaction-type)
  (check-type reason string)
  ;; implementation omitted for brevity, ha ha
  )

Naturally we need to specify the :repository, the :transaction-type is one of

(defconstant *repository-transaction-types* '(:read-only
                                              :read-write
                                              :read-cons
                                              :read-only-compare
                                              :read-cons-nonversioned
                                              :read-only-nonversioned
                                              :read-write-nonversioned))

The :user-id-specifier should be a distributed-identifier of a core-user instance.

The :reason is a human readable string describing the transaction.

The :meta-cid-set-specifier is mumble, mumble... just a sec...

The :cid-set-specifier is how you specify which CIDs will form the basis view for the transaction. We allow this to be a procedure that returns a cid-set object, and we will call this procedure as we are setting up the transaction and use the :meta-cid-set-specifier to specify the CIDs to form the versioned view the procedure will see.

The :meta-cid-set-specifier can be the symbol :latest-metaversion, a timestamp, or a cid-set. :latest-metaversion means to use all CIDS while resolving the :cid-set-specifier, a timestamp is useful for rewinding the world, and the main use for using an explicit cid-set is for synchronizing views between master and satellite repositories.

The :receiver is invoked within the dynamic extent of a transaction. It is passed a core-txn object that contains the metadata associated with the transaction.

The ChangeSafe core components are the repository that holds changes and associated meta-information, and simple versioned CLOS objects. It is only useful as a foundation layer, though.

Next up, another level of abstraction...

Mix in a little CLOS

The obvious idea here is to make CLOS objects where the slots are implemented as versioned value objects. Then we override slot-value-using-class. You might consider this a stupid CLOS trick. You could just as well establish an abstraction layer through other means, but the point is to create an understandable abstraction model. It is easy to understand what is going to happen if we override slot-value-using-class.

We use the MOP to create a new kind of slot so that we can compose values on the fly when the programmer calls slot-value-using-class. We also override (setf slot-value-using-class) so that it calls the "diff" computing code. Again, the point is to make it easy to understand what is happening.

The end result is the versioned-standard-object. An instance of a versioned-standard-object (or any of it's inheritors, naturally), has all its slots implemented versioned value objects. The programmer should specify versioned-standard-class as the metaclass in the class definition.

(defclass test-class ()
  ((nvi-slot  :version-technique :nonlogged
              :accessor test-class/nvi-slot)
   (lnvi-slot :version-technique :logged
              :accessor test-class/lnvi-slot)
   (svi-slot  :version-technique :scalar
              :accessor test-class/svi-slot))
  (:metaclass versioned-standard-class)
  (:schema-version 0))

In this example, the test class has some of the different kinds of versioned values that are named by the version technique. A :nonlogged slot is the "escape mechanism". It's a fancy name for "Just turn off the versioning, and use this here value."

A :logged slot is less drastic. There's no versioning behavior, it's just a persistent slot, but we'll keep a list of the transactions that modified it.

Finally, the :scalar version technique is one where the last chronologically participating change has the value.

A versioned slot using the :composite-sequence uses a set of diffs to represent the versioned slot value, and these are composed as described in an earlier post.

(defclass test-cvi-class ()
  ((cvi-slot-a :version-technique :composite-sequence
               :accessor test-cvi-class/cvi-slot-a)
   (cvi-slot-b :version-technique :composite-sequence)
   (cvi-slot-c :version-technique :composite-sequence :initform nil))
  (:metaclass versioned-standard-class)
  (:schema-version 0))

Once this is working, we have what we need to bootstrap the rest of the versioned storage.

Putting things together

Ok, so we have audit records, a persistent store, and "diffs". Let's start putting them together. Naturally, we are going to keep the audit records in the persistent store, and we'll put the diffs in the audit records.

A versioned value is the abstraction we're aiming for. We're going to create a versioned value by combining the information held in the audit records. If the information is a set of insertion and deletion records, we combine them as I described in the previous posts.

What makes this interesting is that we can specify a subset of the audit records to participate in the construction of the value. We can extract the versioned value as it appeared at any point in time by specfying only those records that have a timestamp at or before that point. We can also synthesize interesting views by omitting some of the records.

We're going to store a lot of these versioned values and we'll use many of them every time we access the store. To get any kind of coherent view of the world, we want to use a single set of audit records when we view these values. But programmers, being who they are, won't want to think about this. So here's what we'll do: we already have transactions in order to talk to the store; we'll add a field to the transaction that specifies the audit records to be used during that transaction. Pretty simple. You want to look at the world as it was on July 4th, you start the transaction with those audit records dated July 4th or earlier and use that set for every versioned value that you want to look at. It would be crazy to look at some objects as if it were July 4th, but others as if it were December. (Heh, but on occasion....)

There is another reason we want to specify a set of audit records at the beginning of a transaction: we need to know the baseline that we compute our diffs against. When we do a read/write transaction we're going to modify some of our versioned values. When the transaction ends, we need to compute the diffs of the things we modified. We compute the diffs relative to the view we established at the beginning of the transaction.

So we need to modify our audit records to record the basis set of records we use when we begin a transaction. We modify the transaction API to require the programmer to specify which basis set of records are to be used for the transaction and we use that basis set for computing the diffs at the end of read/write transactions.

There is an interesting side effect of this change. Suppose we have some way of attaching a label to the transactions, and some transactions only use label 'A' and others only use label 'B'. Further transaction using label 'A' only see diffs relative to prior 'A' versions, while the 'B' transactions only see the 'B' diffs. The result is that a single versioned value can hold two completely different histories.

Plus ça change

Let's start with a list:

'(a b c)

We change it:

'(a b c d)

We change the result:

'(0 a b c d)

etc.

'(0 a b c)

etc.

'(a b c)

and now a big change:

'(-1 0 1 a a1 b b1 c d e f)

At each step we compute the indels for that step. If we so desire, we can reconstruct any of the intermediate lists by starting at the beginning and applying the appropriate indels in order.

But what if we skip some? We end up with a mess. Each set of indels is computed relative to the application
of the prior indels. If an indel is omitted, the indices of the subsequent indels will be wrong.

To solve this, we have to change the representation of our sequence (that is, we won't be modifying a list).
Instead, we'll represent our sequence as an ordered set of list segments that we'll concatenate. Insertion is easy — just add a segment. Deletion is slightly harder because we don't want to cross segment boundaries.

Reconstruction of an intermediate list requires more work, but we gain flexibility. We can apply a subset of the insertions and deletions and still get a meaningful result. For example, the first change we made was to create a list with the three elements '(a b c). The second change appended a 'd'. What if we apply the second change but omit the first? We append a 'd' to an empty sequence and get '(d).

How about if we apply only change 3? That inserts a '0' at the beginning giving us '(0).

If we apply change 2 and 3, still omitting 1, we get '(0 d).

That last change is tricky. We've deleted the 'a and prepended '(-1 0 1 a a1), and deleted the 'c and inserted '(b1 c d e f). If we omit change 4 and 5 (which delete the leading 0 and trailing 'd) we'll get '(-1 0 1 a a1 0 b b1 c d e f d). We preserve the order between different insertion points, so the inserted 0 is always before the inserted 'd, but we resolve ambiguous insertions by placing the later insertions before the earlier ones if they are in the same place.

Optional Exercise 7 (quite hard): Implement this as well.

Let's start with a list:

'(a b c d e f g h i j)

We'll add some elements:

'(a b c d e f g h i j k l m n o)

Delete some:

'(a b c d e i j k l m n o)

Add some more:

'(x y z a b c d e i j k l m n o)

Maybe delete one:

'(x y z b c d e i j k l m n o)

We want to compare the original sequence with the end sequence and
summarize the difference with a set of "indels", which specify the
indexes at where elements were inserted or deleted:

(diff '(a b c d e f g h i j) '(x y z b c d e i j k l m n o))

(#S(INDEL
    :LEFT-SUBSEQ-START 0         ;; 'a'
    :LEFT-SUBSEQ-LIMIT 1
    :RIGHT-SUBSEQ-START 0        ;; 'x y z'
    :RIGHT-SUBSEQ-LIMIT 3)
 #S(INDEL
    :LEFT-SUBSEQ-START 5         ;; 'f g h'
    :LEFT-SUBSEQ-LIMIT 8
    :RIGHT-SUBSEQ-START 7        ;; nothing
    :RIGHT-SUBSEQ-LIMIT 7)
 #S(INDEL
    :LEFT-SUBSEQ-START 10        ;; nothing
    :LEFT-SUBSEQ-LIMIT 10
    :RIGHT-SUBSEQ-START 9        ;; 'k l m n o'
    :RIGHT-SUBSEQ-LIMIT 14))

Exercise 6 (hard): Implement this.

For an extreme challenge, implement this in a way that is not hopelessly inefficient.

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.

Persisting CLOS objects

In a previous post, I described how a programmer would save simple primitive objects to the persistent store. How does a programmer save a CLOS object? Very simply. Here is a class definition:

(defclass test-class ()
  ((name :initarg :name
         :initform 'zippy
         :reader test-class/name)))

Here is the persistent version:

(defclass test-class ()
  ((name :initarg :name
         :initform 'zippy
         :reader test-class/name))
  (:metaclass persistent-standard-class)
  (:schema-version 0))

And here is how you save a persistent instance to the store:

(make-instance 'test-class)

I'll do another one:

(make-instance 'test-class :name 'griffy)

Not too shabby.

The point is that we can abstract away an awful lot of the persistence layer. This is really important because the versioning layer is at least as complex. Wrapping your mind around multiple versioned instances takes practice. It's a good thing that we don't have to think worry about the persistent layer at the same time.

But I said that I'd describe how it works. I have several attempts at description sitting here on my computer, and they are hard to read, hard to undertand, and it simply doesn't seem like it would work correctly. I've tried to logically argue that it does work, and certainly the fact that the code was working is empirical evidence, but I'm still trying to find a clear description so that it simply makes sense that it ought to work. So rather than describe why it ought to work, let me describe what happens beneath the covers.

The code in pstore/pclass.lsp has the implementation. The CLOS meta-object protocol allows you to customize the behavior of the object system by adding your own methods to the internal CLOS implementation. To create a CLOS object, you call make-instance. Magic happens, but part of that magic involves initializing the slots of the newly created object. At this point during the object instantiation magic CLOS calls the generic function shared-initialize. shared-initialize is responsible for assigning values to the slots of an object and it get called on the uninitialized object, the set of slot names to fill, and an argument list. The argument list is normally the same argument list given to make-class. The default behavior of shared-initialize is to match up the keyword-specified initargs with the appropriate slots and stuff the values in. But we'll modify that.

(defmethod clos:shared-initialize ((instance persistent-standard-object) slot-names
                                   &rest initargs
                                   &key persistent-store node-id node-index
                                   &allow-other-keys)

  (if (eq instance *restoring-instance*)
      (call-next-method)
      ;; If we are being called from elsewhere,
      ;; we have to wrap the initargs and initforms
      ;; in persistent-objects and create an initializer
      ;; for this object.
      (let* ((class (class-of instance))

             (init-plist (compute-persistent-slot-initargs class
                                                           (or persistent-store  *default-persistent-store*)
                                                           initargs))

             (node-id (persistent-object/save
                       (make-initializer class
                                         (class-schema-version class)
                                         init-plist)
                       (or persistent-store  *default-persistent-store*)
                       node-id)))

        (apply #'call-next-method instance slot-names (nconc init-plist initargs))

        (setf (persistent-standard-object/node-id instance) node-id)
        (setf (persistent-standard-object/node-index instance) node-index)
        (setf (object-map-info/%cached-value
               (persistent-object/find-object-map-info
                (or persistent-store  *default-persistent-store*)  node-id))
              instance)

        instance)))

First, we check if the instance we are initializing is being restored from the persistent store. When we first open a persistent store and re-instantiate the objects, we do not want the act of re-instatiation to cause the objects to be re-persisted. So in that case we simply invoke call-next-method and let the default actions take place.

But if we are creating a new object, we want it to persist. The call to persistent-object/save does the trick, but notice that we don't pass in the instance. We call make-initializer on the argument list and we save that instead.

An initializer is a simple structure that holds the class, a "schema-version", and the argument list:

(defstruct (initializer
            (:conc-name initializer/)
            (:constructor make-initializer (class schema-version init-plist))
            (:copier nil)
            (:predicate initializer?))
  (class        nil :read-only t   :type persistent-standard-class)
  (schema-version 0 :read-only t   :type non-negative-fixnum)
  (init-plist   '() :read-only t   :type list))

and persistent-object/save serializes it like this:

(:method ((object initializer) stream symbol-table)
    (write-byte serialization-code/initializer stream)
    (write-fixnum (symbol-table/intern-symbol symbol-table (class-name (initializer/class object))) stream)
    (write-fixnum (initializer/schema-version object) stream)
    (write-fixnum (length (initializer/init-plist object)) stream)
    (iterate (((key value) (scan-plist (initializer/init-plist object))))
      (write-fixnum (symbol-table/intern-symbol symbol-table key) stream)
      (serialize value stream symbol-table)))

(I'm skipping over an important detail, but I'll get to it...)

Something unusual is going on here. The persistent object itself is not placed in the store. The argument list passed to make-instance is stored instead. Because the persistent object is immutable, all the information needed to reconstruct the object is present in the initargs, so we don't need the resulting object.

Why would we do this? The object itself has structure. Instantiating the object imposes this structure on the values stored within. The structure of the objects in the store are collectively known as the schema. Persistent stores are intended to hold objects for a long time. We expect the code that manipulates the objects to change over time, and it is likely that we will want to change the object representation on occasion. When we change the object representation, we need to consider the legacy objects that were constructed under the old representation. This is called schema evolution and it is one of the most painful tasks in maintaining an object-oriented database. At its worst, the persistent schema is so different from the code schema that you have only one way to handle the schema change: dump the entire database into a neutral format (like a file full of strings!), create a new, empty database and read it all back in. My experience with other object oriented database is that the worst case is the common case.

If we store only the information needed to reconstruct the object, we no longer need to worry about the object layout. This finesses the problem of schema evolution.

But there is a :schema-version specified in the class definition, and that is most definitely stored. There are two kinds of information in the initargs: the values themselves are obvious, but the interpretation of the values is not. An example should illustrate this.

Suppose we start out a project where we are going to save named objects in the store. At some point in the code we invoke (make-instance 'foo :name "Joe") and so there is an initializer in the store something like [foo (:name "Joe")].

Now suppose that we extend our application. We are going to store family names as well. So we start storing initializers with more data: [foo (:name "John" :family "Smith")] What do we do about the legacy [foo (:name "Joe")]? Let us suppose we decided that we'll just default the missing last name to "Unknown". Everything is cool. Old and new objects live together.

But now we want to extend our application to handle people like Cher and Madonna. We want it to be the case that we can deliberately omit the family name for some people. The initializers will look like [foo (:name "Cher")]. But now we have an ambiguity. We don't know if the family name is omitted on purpose, or whether the object was stored before the family name became important. Do we default the last name to "Unknown" or not?

The :schema-version argument in the class definition is used to disambiguate these cases. When the objects are recovered from the store, the constructor can use this value to decide how to interpret the remainder of the initargs.

Admittedly, this is a bit klunky. But it doesn't complicate things too much. Programmers will have to do two things when changing a persistent class definition: bump the :schema-version, and decide how to reconstruct objects that were stored under the legacy expectations. (Actually, you can punt on these if you can prove that no ambiguous cases will arise.)

Now about that important detail. The initializers we store aren't exactly what we said. Instead, when the persistent class is defined a set of "hidden slots" is created in parallel with the declared slots. The initargs of the hidden slots are not persistent objects, but the persistent object ids of the initargs. We don't store [foo (:name "Joe")], we store [foo (:persistent-initarg-for-name 33)] where 33 is the persistent object id of the persistent string "Joe". I could write a few pages explaining why, but it would be deadly boring. I'm sure you can imagine uses for an extra hidden level of indirection (think multi-value concurrency).  (By the way, notice call to (apply #'call-next-method ...) uses nconc to paste the hidden arguments on the front of the argument list like I mentioned in the previous post.)

Does it work? Mostly. If you look at the code in conman/workspace.lsp you'll find a class with a schema-version of 1 and this method:

(defmethod pstore::restore-instance ((class (eql (find-class 'workspace))) (schema (eql 0)) 
                                     persistent-store node-id node-index init-plist)
  (debug-message 2 "Upgrading schema for workspace.")
  ;; This needs work.  The zeros are the OID of NIL.
  (pstore::restore-instance class 1 persistent-store node-id node-index
                    (list* :added-master-csets 0
                           :removed-master-csets 0
                           :transitional-added-master-csets 0
                           :transitional-removed-master-csets 0
                           init-plist)))

I added four slots to workspace objects. When resoring a workspace from the store, if it was a workspace created before these slots existed, this method overrides the usual restore method. It simply adds the new slots to the front of the init-plist before proceeding with the normal restore-instance. (The use of the number 0 instead of NIL is an implementation defect that I'm too lazy to fix at the moment.)

---

The problem in explaining this? I don't know an easy proof that storing initializers rather than objects is sufficient in all cases. It's not obvious that this even helps with schema evolution, and it took me a while before I was persuaded that there aren't lurking edge cases. In personal discussions, it takes a while to persuade people that this is in fact a solution to a problem. I'd love to hear a better argument.

alist or plist?

Another digression. We'll get to those persistent clos objects shortly, I promise.

In Lisp it is common to create little tables that map keys to values. You'd use a hash-table for any "serious" work, but sometimes you just want store a couple of items for a moment or two and you don't want to bother with the all the baggage that comes along with declaring, creating, and using hash tables.

There are two ways of doing this, both of which date back to the very earliest lisp implementations. An alist, or association list, is simply a list of associations. Each association has a key and a value. A plist, or property list, on the other hand, is a list of alternating keys and values.

Here is an alist:

((:name . "Joe")
 (:favorite-color . "Blue"))

Here is an equivalent plist:

(:name "Joe" :favorite-color "Blue")

There really isn't much of a difference between the two. Obviously you cannot just substitute one for the other because you need to use different accessors, but otherwise there seems little reason to prefer one to the other.

Alists have the nice property that they are implemented as a list of homogeneous elements. Each element in an alist is an "association". Lisp doesn't care about that, but it seems tidier.

Plists, on the other hand, are implemented with a heterogeneous list. The keys occupy the even elements, the values the odd. Again, Lisp doesn't care. But if you are misaligned in a plist, you'll end up thinking the keys are values and the values are keys and you'll pair the values with the keys to the subsequent entries.

Teachers love to make problem sets out of these things.

Alists are "deeper" because there is substructure to the entries. Plists are "flat" because the single list backbone is doing double duty linking keys to values and linking the key-value pairs together. Every key in a plist must have an associated value, but you can put a "key only" entry into an alist.

But there is one very special thing about a plist: it is isomorphic to a keyword argument list. This means you can apply a procedure to a plist and get the keyword argument mechanism to unpack it and bind the named parameters to the values. Watch:

(defun foo (&key name favorite-color)
  (format t "~%~a's favorite color is ~a" name favorite-color))

(let ((my-plist '(:name "Joe" :favorite-color "Blue")))
  (apply #'foo my-plist))

The order of the "entries" doesn't matter. This works, too:

(let ((another-plist '(:favorite-color "Blue" :name "Joe")))
  (apply #'foo another-plist))

Missing a table entry? Use argument defaulting:

(defun foo (&key (name "Unknown") favorite-color)
  (format t "~%~a's favorite color is ~a" name favorite-color))

(let ((another-plist '(:favorite-color "Blue")))
  (apply #'foo another-plist))

With judicious use of &rest, &key, and &allow-other-keys, you can pick out certain named entries, ignore the remaining ones, and pass the entire plist on to another procedure:

(defun baz (&rest args &key name &allow-other-keys)
  (print name)
  (apply #'foo args))

And because keyword handling works from left to right, with the earlier (leftmost) arguments taking precedence, you can override selected entries by simply shadowing them:

(define quux (&rest args &key name &allow-other-keys)
  (when (equalp name "Joe")
    (apply #'foo `(:favorite-color "Black" ,@args))))

Just some stupid plist tricks? No. When we couple this with generic procedures, method combination, and quasiquote we suddenly have a very powerful way to modify behaviors through delegation. We make considerable use of this in extending CLOS to handle persistent and versioned objects.

Try doing this in a more traditional language. It simply does not work anywhere nearly as smoothly.

CLOS?!

I did not like CLOS before I started working on ChangeSafe. It was "too complicated". It has weird things like "effective slots" and "method combinators" and update-instance-for-redefined-class. Most of CLOS seems to consist of circular definitions, and the documentation reflects this as well. When you are a blind man examining an elephant, no matter what you think you found, there seems to be an awful lot of it with no apparent purpose.

Code doesn't spring into life on the first iteration. It often takes many, many attempts at implementing something before you understand the problem you are trying to solve and figure out the best way to approach the solution. With iterative development, you re-approach the problem again and again in different ways trying to break it down into understandable pieces.

During the development of ChangeSafe I found myself "painted into a corner" on more than one occasion. The code had evolved to a point where it was clear that some core abstractions were the foundation of solving the problem, and the implementation of these core abstractions were at the very center of the solution. Sometimes we were wrong.

Sometimes a core, fundamental abstraction is best understood as a combination or special case of even more fundamental concepts that aren't obvious until later (or much later). This happens fairly often, so you re-implement the relevant code. Often the new abstractions are not completely compatible with the old ones, so you write some scaffolding code or an adapter API, or you bite the bullet and walk through your entire code base and fix up each and every call that used to do things the old way, and make it work the new way.

Sometimes, though, there is simply no way massage the old solution into the new one. You are faced with a tough choice: continue using the old code that doesn't quite do what you want and is becoming increasingly difficult to maintain, discard the entire body of code and start from scratch, or attempt to paper over the problem with some horrific kludge that you say will be temporary (but you know what that means).

Unfortunately, it is hard to tell if you will run into a roadblock like this until you are well down the path. Your new abstraction is making everything so much easier until you realize that in some obscure corner case it is fundamentally incompatible with the old code. Now you have a monstrous pile of code and half of it does things the new way, the other half does it the old way, and the two halves aren't on speaking terms anymore. That's bad.

Now consider that you have a persistent store full of objects that were created and curated by the old code. You cannot delete the old code if you want to access the old objects, but the new code cannot deal with the legacy objects without calling or incorporating the old code. Of course the old code will be confused by the new objects.

On one occasion I ran into a problem of this nature. A certain kind of object needed to be built using some new abstractions, but there were objects in the database that were incompatible with the new world order. I thought of different ways to deal with this. One possible solution was to create yet another abstraction that acted like a bridge between the two models. We'd migrate everything from the legacy system to the bridge system, then once there were no legacy objects, we'd replace the legacy system with the new system and then migrate everything back. "But Bullwinkle, that trick never works!" I can confirm that it does not.

But... in the particular case in point, there was a way it could work if only there were an extra level of indirection. If we could just juggle the underlying physical slot names of the legacy objects without changing the code that manipulates the logical fields, we could fake up a slot that doesn't actually exist in the legacy objects, but does exist in the new ones.

As it turns out, this is easy to do in CLOS by simply adding a couple of methods to the accessors to handle the legacy case. I was delighted to discover this clever escape hatch. It perfectly solved a problem that was starting to look like a depressing amount of very hard work. It almost seemed as if it were designed with this exact problem in mind. And of course, it was. Suddenly, I was very impressed.

A simple persistent store

ChangeSafe contains a simple persistent store.  The code is here.

To get an idea of how this works, start with tests.lsp

First, when  open-persistent-store is called, the persistent store is (obviously) opened.  If the store doesn't exist, it is created.  It is easier to write code with the assumption that there is always a persistent state that can be updated rather than having special code deal with a once only initialization.

All interaction with the contents of the store takes place within an atomic transaction.  When the transaction ends, either all the updates to the store take place, or none do.  This allows the programmer to briefly ignore consistency requirements during computation so long as the end result is consistent. The interface is fairly simple:

call-with-transaction pstore transaction-type reason receiver

pstore - a persistent store
transaction-type - one of :read-only, :read-write, or :read-cons
reason - a human readable string describing the purpose of the transaction
receiver - a procedure of one argument (the transaction object) which is invoked during the transaction

In the usual, expected case, the receiver runs, possibly makes updates to the store, and returns a value. When the receiver returns, the transaction commits (finishes) and the changes to the store are applied atomically.

In the less usual case, the transaction may be aborted.  In this case, no (detectable) changes are made to the store.

The decision to commit or abort is usually made implicitly:  if the receiver procedure returns normally, the transaction commits, if it performs a non-local exit, via a throw or through error recovery, the transaction aborts.  However, the programmer can explicitly cause the transaction to commit or abort through a call to transaction/commit or transaction/abort.

The transaction-type indicates what kind of transaction is to be performed.  Naturally :read-write is used to update the store and :read-only is used if no update is necessary.  :read-cons is for the case of a transaction that only creates new persistent objects and does not change existing objects.  The implementation ensures that transactions are isolated (transaction in progress are not visible to each other) and serializable (committed transactions can be placed in a consistent order even if executed in parallel).  :read-only transactions only have to be consistent throughout execution, so many can (in theory) be run in parallel.  :read-write transactions can be run in parallel only if they do not interfere with each other.  :read-cons transactions are a special case of :read-write.  Since new objects are not visible outside the transaction until the transaction commits, there can be no interference between multiple :read-cons transactions. (Support for :read-cons is sketchy, though.  Although there should be no interference, each transaction must issue unique object ids and thus they do interfere implicitly.  There are ways to deal with this, but I didn't implement them.)

The reason is simply a string that is recorded along with the transaction.  This is to help the user understand the sequence of transactions when examining the history of the store.

The receiver is invoked on an object representing the transaction.  It is often ignored because the implicit commit or abort behavior is usually used, but the argument is there if desired.

During the transaction, the special variable *current-transaction* is bound to the transaction object.

So let's look at some code:

(let ((store (persistent-store/open pathname))
       id
       vid
       (object1 '(this is a list))
       (object2 #(this is a vector))
       (object3 (list 1.0d0 -1.0d0 0.125d0 -0.125d0 1024.0d0 -1024.0d0 .3d0 -.3d0))
       (object4 (list #x87654321 #x12345678 1 -1 2147483647 -2147483648
                      #*101010101010101010101010101
                      #*100000000000000000000000000
                      #*000000000000000000000000001))
       o1id
       o2id
       o3id
       o4id)
   (call-with-transaction
    store :read-write "Save some objects."
    (lambda (transaction)
      (declare (ignore transaction))
      (setf o1id (persistent-object/save object1 store)
            o2id (persistent-object/save object2 store)
            o3id (persistent-object/save object3 store)
            o4id (persistent-object/save object4 store)))))

This code saves some simple lisp objects to the store.  persistent-object/save writes the object to the store and returns a unique integer (the object-id). Obviously we'll want a :read-write (or :read-cons) transaction.

 Later on, we call

       (call-with-transaction
        store :read-only "Verify objects."
        (lambda (transaction)
          (declare (ignore transaction))
          (verify
           (verify-one-return-value (verify-value-equal object1))
           (persistent-object/find store o1id))
          (verify
           (verify-one-return-value (verify-value-equalp object2))
           (persistent-object/find store o2id))
          (verify
           (verify-one-return-value (verify-value-equal object3))
           (persistent-object/find store o3id))
          (verify
           (verify-one-return-value (verify-value-equalp object4))
           (persistent-object/find store o4id))))

persistent-object/find takes the integer returned by persistent-object/save and returns the object.  In this case we use a :read-only transaction, but we would use :read-write if we were going to modify any objects.

One has to be careful about equality.  The object returned by persistent-object/find may not be EQ to the object saved. It would be very difficult to implement this in general, and it isn't needed in most cases. Symbols are treated specially to preserve EQ-ness.

A little lisp

Several years ago I worked on ChangeSafe, a change management and version control system written in Common Lisp.  The CTO of ChangeSafe, LLC (me) has decided to open the source code of ChangeSafe.

Licensing

The code has been placed in my source code repository, which is published under the "new BSD" license.  You may take any of the code and use it under that license.  Do not be intimidated by the very scary words you might find.  Please feel free to contact me about different licensing if that would be useful.

Confusion about functional programming

Lawrence Botroff posted a set of questions and I thought I'd reply in my blog.

I've read some of the discussions here, as well as followed links to other explanations, but I'm still not able to understand the mathematical connection between "changing state" and "not changing state" as it pertains to our functional programming versus non-FP debate.

The concepts of "change" and "state" implicitly involve some notion of time. A mathematical function does not.

Mathematical functions are, however, an incredibly useful concept. So, too, are the concepts of change and state.

There are two trivial solutions: ignore the problem and avoid the problem. We can simply ignore the problem of change and state and not attempt to use mathematical functions to model our program. Or we can avoid the problem of change and state and avoid programming in a way that makes implicit use of time. There are more complex solutions as well.

The "debate", such as it is, is whether the benefits of functional programming are worth the effort of either avoiding change or explicitly modeling it.

Then it get foggy in my mind.

All we need now is to sow discord.

Here's an example. Let's say I want to display closed, block-like polygons on an x-y field. In typical GIS software I understand everything is stored as directed, closed graphs, i.e. a square is four "vectors," their heads and ends connected. The raw data representation is just the individual Cartesian start and end points of each vector. And, of course, there is a "function" in the GIS software that "processes" all these coordinate sets.

Can we avoid overloading the word "function"? It will be confusing. Let's consider function to be a mathematical concept. I'll call the programming structure a subroutine, just to be old fashioned. A program is a collection of subroutines. If we so choose, we can avoid the implicit use of time in our programs and subroutines. If we do that, then it is easy to model our subroutines as mathematical functions, and model our program through functional composition.

So let me rephrase your sentence: And, of course, there is "program" in the GIS software that "processes" all these coordinate sets.

Good. But what if we represent each polygon in a mathematical way, e.g., a rectangle in the positive x, negative y quadrant might be:

Z = {(x,y) | 3 <= x <= 5, -2 <= y <= -1}

So we might have many Z-functions, each one expressing an individual polygon -- and not being a whiz with my matrix math, maybe these "functions" could then be represented as matrices . . . but I digress.

You're making a subtle shift in your point of view, and that may be part of what is confusing you. The earlier paragraph addressed the idea of using functions to model computer subroutines. This paragraph addresses the idea of using computer subroutines to model functions.

These are not equivalent concepts. Imperative programs, for example, can also use subroutines to model functions. But naturally, imperative programmers don't generally want to do this, and people that prefer functional programming tend to do this all the time.

Now if we can use a mathematical function to model a subroutine, then the code itself may be able to use that subroutine to model the mathematical function (these would be first-class procedures.  It would be odd, but conceivable to have a functional language without first class procedures.). This is conditional on how we write our code. If we write in imperative style, then we may not be able to model subroutines as a mathematical functions. But if we write in functional style, we get both the ability to model subroutines as functions and to use those same routines to model the functions. You can ignore the distinction between code and the mathematical function it is equivalent to.  Functional programmers think this is really cool. Imperative programmers are not so impressed.

So with the usual raw vector-data method, I might have one function in my code that "changes state" as it processes each set of coordinates and then draws each polygon (and then deals with polygons changing), while the one-and-only-one-Z-function-per-polygon method would seem to hold to the "don't change state" rule exactly -- or at least not change memory state all that much. Right? Or am I way off here? It seems like the old-fashioned, one-function-processing-raw-coordinate-data is not mutating the domain-range purity law really. I'm confused....

Slow down a bit. We're talking about a program and we want to analyze it. (By "analyze", I don't mean "gain a deep understanding", I mean "any effort to try to understand anything at all".) So in your hypothetical code you have polygons that are modeled by functional subroutines. That's great. You can model these parts of the code as mathematical functions.

But apparently, there is a subroutine in your program that "changes state". This means that there is an implicit time component, and therefore you cannot trivially model this part of the program with a mathematical function. That's all there is to it.

But the many individual polygon Z-functions method would seem to hold a perfect picture of state in memory -- no?

No. You have shifted to a different abstraction. What you mean by "state" in this case is an abstract set of polygons. Since the polygons are immutable, you could write a program which deals with this set of polygons in a completely functional manner. But there is no requirement that you do so. You could write an imperative program that mutates the data structures that hold the polygons.

Then I was reminded of my days (1980s) in Cartography when an object-oriented GIS package (written in Smalltalk) was being discussed. Everyone dismissed it as ludicrous because it tried to have exactly that: all the cartographic objects (roads, areal, symbols, polygons, etc.) in live memory at once. But isn't this ultimately what FP wants?

This is yet another abstraction. One could implement this imperatively or functionally. It's also a much older idea than the 80s.

You may be confusing yourself by attempting to shoehorn too many ideas into the word "functional".

Another avenue of my inspiration came from reading about a new idea of image processing where instead of slamming racks of pixels, each "frame" would be represented by one big function capable of quasi "gnu-plotting" the whole image: edges, colors, gradients, etc. Now I ask, Is this germane? I guess I'm trying to fathom why I would want to represent, say, a street map of polygons (e.g. city blocks) one way or the other.

You might want to render in different sizes. It is likely that a high resolution bitmap for a large window would take far more memory than the specification of how to generate the bitmap. Polygons carry more information than bitmaps. You might want to do something other than rendering.

I keep hearing functional language advocates dance around the idea that a mathematical function is pure and safe and good and ultimately Utopian, while the non-FP software function is some sort of sloppy kludge holding us back from Borg-like bliss.

I don't hang around the places you do.

But again, more confusing is memory management vis-a-vis FP versus non-FP. What I keep hearing (e.g. parallel programming) is that FP isn't changing a "memory state" as much as, say, a C/C++ program does.

Again, if you program functionally, you avoid introducting implicit time dependencies. This makes it much, much easier to determine where you can safely program in parallel (basically anywhere). You can do it the hard way, too.

Is this like the Google File System (or my Smalltalk GIS example) where literally everything is just sitting out there in a virtual memory pool, rather than being data moved in and out of databases, bzw. memory locations? Somehow I sense all these things are related.

Well, there is a connection. Notice you said "data moved in and out of databases". This has an implicit time component: sometimes the data is in, other times it is out. If we want to model our database with mathematical functions, we'll have a problem. One solution is to simplify the model by abstracting away the actual location of the data, that is, make it appear as if "literally everything is just sitting out there in a virtual memory pool". (Unfortunately this only gets you so far because the data is mutable.)

Therefore, it seems like the perfect FP program is just one single function (possibly made up of many sub-functions like nesting Russian dolls) doing all tasks

Programs of this sort are quite easy to write. I wouldn't call them perfect.

-- although a quick glance at any elisp code seems to be a study of programming schizophrenia on this count.

Nor would I call typical elisp code functional.

Nasty details

John Cowan wanted more detail.  If device drivers and bus cycles are not up your alley, I suggest you skip this post.  Seriously.

---

Still here?  You were warned.

For various historic reasons, the LMI Lambda was built as a NuBus card set. The NuBus interface could be driven from the memory interface, and this microcode shows how:

((MD) a-map-scratch-block)      ;following inst gives maps time to settle.
 ((M-1) DPB C-PDL-BUFFER-POINTER-POP (BYTE-FIELD 8 24.) A-1)  ;FULL 32 BIT NUBUS ADR
 ((L2-MAP-CONTROL) (a-constant 1464))    ;no caching.
 ((L2-MAP-PHYSICAL-PAGE) LDB M-1 (BYTE-FIELD 22. 10.) A-ZERO)
 ((VMA-START-READ) LDB (BYTE-FIELD 8 2) M-1 a-map-scratch-block)

The first line loads the MD (memory data) register with the virtual address of the "scratch block". The second line pops the desired NuBus address off the stack. The third and fourth lines write the Level 2 maps (the maps are addressed by MD) to address NuBus space. The final line initiates the bus cycle, and the result can be read from MD when it arrives.

With some argument checking and boxing of the result, this is surfaced to the Lisp world as a primitive instruction called %NUBUS-READ:

(DEFMIC %NUBUS-READ 761 (NUBUS-SLOT SLOT-BYTE-ADR) T)
                                ;SLOT is really the high 8 bits.
                                ;the "top F" can be supplied via slot,
    ;avoiding bignums.

(SETF (DOCUMENTATION '%NUBUS-READ 'FUNCTION)
  "NUBUS-SLOT is top 8 bits of physical address (usually the top 4 bits are 1's).
SLOT-BYTE-ADR is the lower 24 bits of physical address.")
;;arglist = (NUBUS-SLOT SLOT-BYTE-ADR)

If there was a debug card installed on your machine, you could find out which NuBus slot it was in by reading the system configuration, and you could talk to it by calling %NUBUS-READ and %NUBUS-WRITE:

(defun assure-debug-board ()
  (when (null *my-debug-board*)
    (let ((slot (find-a-debug-board)))
      (setq *my-debug-board* (logior #xF0 slot)))))     ;put it in slot space

(defun read-debug-board (address)
  (%nubus-read *my-debug-board* address))

(defun write-debug-board (address data)
  (%nubus-write *my-debug-board* address data))

And if you know the offsets of the control registers on the card

(defregister debug-mode-register              *my-debug-board* #xFFF7FC :read-write)
(defregister debug-address-register           *my-debug-board* #xFFF7F8 :write-only)
(defregister debug-data-start-transfer        *my-debug-board* #xFFF7F4 :write-only)
(defregister debug-response-register          *my-debug-board* #xFFF7F4 :read-only)
(defregister debug-control-start-transfer     *my-debug-board* #xFFF7F0 :write-only)
(defregister debug-status-response            *my-debug-board* #xFFF7F0 :read-only)
(defregister debug-nubus-analyzer-ram-pointer *my-debug-board* #xFFF7EC :read-write)
(defregister debug-nubus-analyzer-ram-data    *my-debug-board* #xFFF7E8 :read-write)
(defregister debug-nubus-analyzer-ram-control *my-debug-board* #xFFF7E4 :read-write)
(defregister debug-nubus-analyzer-function    *my-debug-board* #xFFF7E0 :write-only)
(defregister debug-test-register              *my-debug-board* #xFFF7C4 :read-write)

and what the bit fields in the registers are

(defconstant %%mode-init                 (byte 1. 0.))
(defconstant %%mode-master               (byte 1. 1.))
(defconstant %%mode-led                  (byte 1. 2.))
(defconstant %%debug-mode-loopback       (byte 1. 3.))
(defconstant %%debug-mode-speed          (byte 1. 4.))
(defconstant %%debug-mode-txwait         (byte 1. 6.))
(defconstant %%debug-mode-response-ready (byte 1. 7.))

(defconstant %%debug-control-start-bit (byte 1. 0.))
(defconstant %%debug-control-ack-bit   (byte 1. 1.))
(defconstant %%debug-control-tm-bits   (byte 2. 2.))
(defconstant %%debug-control-axr-bit   (byte 1. 4.))

(defconstant %%debug-response-start-bit (byte 1. 0.))
(defconstant %%debug-response-ack-bit   (byte 1. 1.))
(defconstant %%debug-response-tm-bits   (byte 2. 2.))
(defconstant %%debug-response-axr-bit   (byte 1. 4.))

and some good values to stuff in

(defconstant $$init 1.)

(defconstant $$disable-mastership 0)
(defconstant $$enable-mastership  1)

(defconstant $$led-off 0)
(defconstant $$led-on  1)

(defconstant $$disable-loopback 0)
(defconstant $$enable-loopback  1)

(defconstant $$slow-transfers 0)
(defconstant $$fast-transfers 1)

(defconstant $$transmitter-idle 0)
(defconstant $$transmitter-busy 1)

(defconstant $$no-response    0)
(defconstant $$response-ready 1)

it is pretty straightforward to run the debug card. Here are some examples

(defun reset-debug-board ()
  (setf (debug-mode-register) (dpb $$init %%mode-init 0)))

(defun blink-debug-light ()
  (loop
    (sleep .5)
    (setf (debug-mode-register)
          (dpb $$led-on %%mode-led (debug-mode-register)))
    (sleep .5)
    (setf (debug-mode-register)
          (dpb $$led-off %%mode-led (debug-mode-register)))))

(defun reset-nubus-analyzer ()
  (setf (debug-nubus-analyzer-function)
        (dpb $$disable-analyzer %%nubus-analyzer-enable 0)))

(defun board-idle? ()
  (= $$transmitter-idle (ldb %%debug-mode-txwait (debug-mode-register))))

The debug card in the Lambda was connected via a serial cable to the debug slave card in the K machine test rack. Writing to the data, addr, and control registers on the card would cause the slave to perform bus cycles on the test rack.

(defun debug-read-word (addr)
  (write-debug-addr addr)
  (write-debug-control #x01)
  (wait-for-debug-response))

(defun debug-write-word (addr data)
  (write-debug-data data)
  (write-debug-addr addr)
  (write-debug-control #x09)
  (wait-for-debug-response))

Now that we can do bus cycles on the test rack, we can talk to other cards on the test rack. Some of the data and control registers of the K machine can be read directly from the bus.

(defvar k-mem-addr   nil "K Processor - Memory address base")
(defvar k-io-addr    nil "K Processor - I/O address base")
(defvar k-mode-addr  nil "K Processor - Mode register address")
(defvar k-hptr-addr  nil "K Processor - History RAM pointer address")
(defvar k-hram-addr  nil "K Processor - History RAM data address")
(defvar k-pc-addr    nil "K Processor - Program Counter address")
(defvar k-mmfio-addr nil "K Processor - MMFIO bus address")
(defvar k-spy0-addr  nil "K Processor - Low spy Instruction Register address")
(defvar k-spy1-addr  nil "K Processor - Hi spy Instruction Register address")
(defvar k-spyc-addr  nil "K Processor - Spy command register address")
(defvar k-int-addr   nil "K Processor - NUBUS interrupt register base address")

Of particular interest here is the Spy Command register. This can be written with one of these values

(defconstant $$spy-command-stop                0.)
(defconstant $$spy-command-run                 1.)
(defconstant $$spy-command-step                2.)
(defconstant $$spy-command-reload-instruction  3.)      ;called ICLOAD in spy-pal
(defconstant $$spy-command-clear-opc-clock     4.)
(defconstant $$spy-command-set-opc-clock       5.)
(defconstant $$spy-command-clear-spy-mode      6.)
(defconstant $$spy-command-set-spy-mode        7.)
(defconstant $$spy-command-stepmode-full-clock 8.)      ;called clr-stepmode
(defconstant $$spy-command-set-stepmode 9.)             ;       set-stepmode

The Spy Command register allows you to start, stop, reset, and debug the machine externally. For example,

(defun k-stop ()
  "Stop the processor clocks, and init spy modes"
  (k-spy-cmd $$spy-command-stop)
  (k-spy-cmd $$spy-command-stepmode-full-clock)
  (k-spy-cmd $$spy-command-set-spy-mode)     ; set spy mode
  (k-spy-cmd $$spy-command-clear-opc-clock)     ; clear opc clk
  (setq k-run-flag nil)
  (k-read-spy-pc))

(defun k-run ()
  "Start the processor running"
  (k-spy-cmd $$spy-command-stop)
  (k-spy-cmd $$spy-command-clear-spy-mode)
  (k-spy-cmd $$spy-command-set-opc-clock)
  (k-spy-cmd $$spy-command-reload-instruction)
  (k-spy-cmd $$spy-command-run)
  (setq k-run-flag t)
  (k-read-spy-pc))

Especially useful was this one:

(defun k-step ()
  "Step the processor one clock cycle"
  (k-stop-if-running)
  (k-spy-cmd $$spy-command-stop)
  (k-spy-cmd $$spy-command-clear-spy-mode)
  (k-spy-cmd $$spy-command-set-opc-clock)
  (k-spy-cmd $$spy-command-reload-instruction)
  (k-spy-cmd $$spy-command-step)
  (k-read-spy-pc))

You may have noticed that it takes multiple local NuBus cycles to instruct the debug card to issue a single remote cycle, and it takes multiple remote cycles to drive the K hardware through the spy interface. It was fast enough for debugging, but it is much faster to put the K processor in the same rack as the LMI Lambda and get rid of the debug board altogether. We used the debug board early on so we could turn off the test rack and remove the hardware.

Still here? I salute your intestinal fortitude. The above code was selected from the files at https://code.google.com/p/jrm-code-project/source/browse/#svn%2Ftrunk%2Fkmachine