pkgetset: A Persistent Keyed Container Convenience Library

A persistent keyed data structure library focusing on simple extensible interface.

After reading “Data-Oriented Programming” by Yehonathan Sharvit, I thought, I need a shared persistent data library to apply the ideas in his book. Along with shared persistent data structures, I’d also need a way to generate and apply diffs.

The pkgetset system contains getk, setk, ergonomic helpers to go with those functions, a few basic containers, and some methods so that getk can work with lists, hash tables and vectors.

The pkgetset.sycamore system has persistent data structures built using sycamore.

Built on top of sycamore, this provides an ergonomic way to use persistent data structures.

Example

A simple example: get by key

(let ((data (pk.sym :a 1
                    :b 2)))
  (getk data :a)) ;; => 1

Then set by key

(let ((persistent (pk.sym :a 1
                          :b 2)))
  (setk persistent :c 3)) ; => (pk.sym :a 1 :b 2 :c 3)
;; persistent is still (pk.sym :a 1 :b 2)

Nested data too

(let ((data (pk.sym :a 1
                    :b (pk.gen "ba" 0))))
  (getk* data '(:b "ba"))) ; => 0

Or something more complicated.

(ewith-keyed (json->pk.gen "{\"data\":{\"testing\":{\"rows\":[15,24,96]}},\"code\":100}")
    ("data" ("testing" ("rows" (1 second-testing-row)))
     "code" code)
  (list second-testing-row code)) ; => '(24 100)

Functions

The base functions either get, set of modify. They are named similarly with some consistency. There are a few modifiers that change the base functions “getk”, “setk” and “modk” in consistent ways.

e

(prefix) Error when key doesn’t exist.

?

(suffix) Tests if key exists

*

(suffix) Takes a path of keys instead of a single key

!

(suffix) Update in place. Does not change original persistent container.

Getters

getk

Get a value from a key (or provide optional default)

getk?

Does container have this key?

egetk

Get a value from a key or signal an error

getk*

Get a value by list of keys (a path)

egetk*

Get a value from a list of keys or signal an error

Setters

setk

Set a value by key

setk!

Set a value by key in place (doesn’t modify the original container)

setk*

Set a value by path

setk*!

Set a value by path in place (doesn’t modify the original container)

Modifiers

modk

Modify key by function

modk*

Modify path by function

emodk

Modify key by function. Error if key doesn’t exist.

emodk*

Modify path by function. Error if path doesn’t exist.

modk!

Modify key by function and update symbol in place (doesn’t modify original container)

modk*!

Modify path by function and update symbol in place (doesn’t modify original container)

emodk*!

Modify path by function in place (…). Error if path doesn’t exist.

Removers

remk

Remove key and return new container

remk!

Remove key and replace symbol

remk*

Remove path. Doesn’t remove empty containers.

remk*!

Remove path. Doesn’t remove empty containers. In place.

Special

keyed-merge

Combine containers by key and return new container

with-keyed

Bind symbols to keys

ewith-keyed

Bind symbols to keys and error if any missing

fold-keyed

Iterate over keys and values with function

over-keyed

Iterate over keys and values like dolist where bound symbols are identified by keywords :key, :value, :accumulator and :initial

Container classes

Built-in

The containers are:

mutable-dict

A hash-table based container that allows mutation until finalized as a pdict.

pdict

A naive hash-table based container that copies on set.

pkgetset.sycamore

The containers are:

pk.gen

Keys may be symbols, strings or numbers. Useful when converting from JSON.

pk.sym

Keys may only be symbols.

pk.str

Keys may only be strings.

pvec

Persistent vector. Setk functions also allow :start :end and (:insert n) as keys.

Convenience

Read only access is implemented to work with getk for

• array
• cons
• hash-table
• vector

Diffs

diff-by-keys and diff-by-keys-find-deleted returns a pk.gen that can be inspected, or applied with apply-diff. In a multi-threaded environment where two changes occur simultaneously, diffs-in-conflict-p can check if one needs to be rejected.

Testing

The system uses parachute as the testing framework. There are many tests which also serve as examples of use.

(asdf:load-system 'pkgetset)
(asdf:test-system 'pkgetset)

(asdf:load-system 'pkgetset.sycamore)
(asdf:test-system 'pkgetset.sycamore)

(asdf:load-system 'pkgetset.sycamore.shasht)
(asdf:test-system 'pkgetset.sycamore.shasht)

Future

• pkgetset.sycamore.shasht helpers need configurable parameters to control serialization
• Validation needs to be moved over into a separate system from my personal projects.