lattice: a Racket prototype of a Lisp datastore
This post came from a short-lived blog I tried to run (tail-recursion.net) where I wanted to write up a short bit of code I'd written that week.
The background page might be useful.
lattice is an imagining of what this data store might look like, how
users might interface with it. This prototype is based on hash-tables,
with reader serialisation to and from disk for persistence—a very
crude beginning, but it's meant as the set on a stage: it's no way to
build a house, but we can talk about living.
The code aims to avoid exposing users to its implementation, and instead provides utilities to focus on the semantics.
(provide write-store!
load-store!
store!
lookup
select)
(define WORKSPACES (make-hash))
write-store! store the global workspaces to file; the simplest
implementation of this is to use the standard reader forms, and
write those to a file on disk. As the “database” is a
single value, reading it will return this single value later.
(define (write-store! filespec)
(write-to-file WORKSPACES
filespec
#:mode 'binary
#:exists 'replace))
Reading the datatstore from a file is easy when it's been done with
load-store!; the datastore is a single S-expression, and one that
can be read from the file..
(define (load-store! filespec)
(set! WORKSPACES (file->value filespec)))
Creating a new workspace is a simple-enough task, but including this as a utility function masks the fact that it is based on hash tables. In practice, it's useful to return the created workspace (because the end user will nearly always want to begin using it immediately).
(define (create-workspace name)
(hash-set! WORKSPACES name (make-hash))
(hash-ref WORKSPACES name))
workspace-exists? returns true if the workspace exists in the data
store.
(define (workspace-exists? name)
(hash-has-key? WORKSPACES name))
store writes the record to the named workspace under the given
name. records are alists; e.g.
> (store 'users "John Q. Public" '((#:id 42)
(#:plan #:basic)
(#:email "jqp@example.net")
(#:documents ("7C19B" "23FA6" "48ABD"))))
The alist is a simple (and common) Lisp structure, but it seems a bit unwieldy. This at least gives a platform to prototype ideas for new representations on.
(define (store! workspace name record)
(eprintf "Will attempt to store [~a] under ~a in ~a\n" record name workspace)
(let ([workspace-ht (if (workspace-exists? workspace)
(hash-ref WORKSPACES workspace)
(create-workspace workspace))])
(let ([record-ht (make-hash)])
(for ([rec record])
(hash-set! record-ht (car rec) (cadr rec)))
(hash-set! workspace-ht name record-ht)
'ok)))
record-exists? returns true if a record named by name is present
in the named workspace.
(define (record-exists? workspace name)
(if (workspace-exists? workspace)
(hash-has-key? (hash-ref WORKSPACES workspace) name)
#f))
Retrieve the record from the named workspace; if no such record exists, return an empty list. The hash→hash→hash→list detail is crude; fortunately the goal here isn't to focus on the implementation but the syntax.
(define (lookup workspace name)
(if (and (workspace-exists? workspace) (record-exists? workspace name))
(hash->list
(hash-ref
(hash-ref WORKSPACES workspace)
name))
'()))
select is the most interesting of these functions; it returns all
records in the workspace for which the application of the predicate on
the search-key for each record returns true.
For example, given the user workspace and "John Q. Public" entry from the comment on store:
> (select 'users '#:id (λ (id) (equal? id 42)))
'(("John Q. Public"
(#:plan . #:basic)
(#:id . 42)
(#:documents "7C19B" "23FA6" "48ABD")
(#:email . "jqp@example.net")))
If we add some more users:
> (store 'users "Alyssa P. Hacker" '((#:id 314)
(#:plan #:basic)
(#:email "aph@example.net")
(#:documents ("87FAC" "19D1A" "86BC2"))))
> (store 'users "Ben Bitdiddle" '((#:id 17)
(#:plan #:pro)
(#:email "bb@example.net")
(#:documents ())))
> (select 'users '#:plan (λ (plan) (equal? plan '#:basic)))
'(("Alyssa P. Hacker"
(#:plan . #:basic)
(#:id . 314)
(#:documents "87FAC" "19D1A" "86BC2")
(#:email . "aph@example.net"))
("John Q. Public"
(#:plan . #:basic)
(#:id . 42)
(#:documents "7C19B" "23FA6" "48ABD")
(#:email . "jqp@example.net")))
One of the interesting questions arises in the case of remote datastores: how can the lambda predicate be transmitted, preserving semantics, to the datastore? Racket permits syntax objects that enclose the S-expressions with lexical enclosures, but this won't work for Common Lisp. There's also the question of how much lexical information can be contained in the syntax object; one idea is to have the server send the value to the client, where the function will check the value against the predicate and indicate whether the record should be pulled. This has interesting applications, particularly (to me) in regards to cryptography. The records could be encrypted, the client decrypts and checks it, and the server responds. There are many problems to consider with this (performance, etc), but it is an idea.
(define (select workspace search-key pred)
(when (workspace-exists? workspace)
(let ([lookup-key (lambda (key) (lookup workspace key))]
[workspace (hash-ref WORKSPACES workspace)])
(filter-not empty?
(hash-map workspace
(lambda (key value)
(if (pred (hash-ref value search-key))
(cons key (hash->list value))
'())))))))
This code was the first "serious" code I wrote in Racket, and it represents a quickly put-together prototype of an idea I was mulling over the weekend.
The untransformed code is available.