A browser with Wasm GC and tail call support is required for this demo. We recommend using either Mozilla Firefox or Google Chrome.
Datalog in miniKanren
Having access to an embedded logical programming language makes some tasks really easy. One prerequisite for RealTalk is some form of Datalog, and I built one in Scheme using miniKanren so that I had access to all of the internals. This page explains the naive Datalog implementation I did before modifying some of it to fit my version of Dynamicland.
As a typical example we can look at a directed graph with five vertices labeled a through e. Using Datalog, we introduce these vertices as separate records, establish facts about directed edges between them, and then introduce rules about what it means for a vertex to be reachable from another vertex. In the end we manually trigger fixpoint analysis and run a query against the resulting database of initial and derived facts.
(define dl (make-new-datalog)) (define a (dl-record! dl 'vertex)) (define b (dl-record! dl 'vertex)) (define c (dl-record! dl 'vertex)) (define d (dl-record! dl 'vertex)) (define e (dl-record! dl 'vertex)) (define (dl-edge x y) (dl-assert! dl x 'edge y)) (dl-edge a c) (dl-edge b a) (dl-edge b d) (dl-edge c d) (dl-edge d a) (dl-edge d e) (dl-rule! dl (reachable ,?x ,?y) :- (edge ,?x ,?y)) (dl-rule! dl (reachable ,?x ,?y) :- (edge ,?x ,?z) (reachable ,?z ,?y)) (dl-fixpoint! dl) (define query (dl-find dl ,?id where (,?id reachable ,?id)))
This is roughly the syntax that I want to go for, minus some of the commas (or unquotes) that I did not get rid of. Now that we have a goal, let's jump into the implementation! We can define a Datalog instance as a record with the following fields:
(define-record-type (make-datalog edb idb rdb idx-entity idx-attr counter) datalog? (edb datalog-edb) (idb datalog-idb set-datalog-idb!) (rdb datalog-rdb set-datalog-rdb!) (idx-entity datalog-idx-entity) (idx-attr datalog-idx-attr) (counter datalog-counter set-datalog-counter!))
Most of these are internal indices, each a different hash-table. Facts are always a 3-tuple of entity-ID, attribute-name and value. Whenever we assert a fact we not only update the main entity table (edb), we also update two indices that index facts by entity (idx-entity) and attribute (idx-attr) respectively.
(define (dl-assert! dl entity attr value) (hashtable-set! (datalog-edb dl) (list entity attr value) #t) (dl-update-indices! dl (list entity attr value))) (define (dl-update-indices! dl tuple) (let ((entity (car tuple)) (attr (cadr tuple)) (idx-entity (datalog-idx-entity dl)) (idx-attr (datalog-idx-attr dl))) (let ((m (hashtable-ref idx-entity entity #f))) (if m (hashtable-set! m tuple #t) (let ((new (make-hashtable))) (hashtable-set! idx-entity entity new) (hashtable-set! new tuple #t)))) (let ((m (hashtable-ref idx-attr attr #f))) (if m (hashtable-set! m tuple #t) (let ((new (make-hashtable))) (hashtable-set! idx-attr attr new) (hashtable-set! new tuple #t))))))
The dl-record! macro lets us introduce one or more facts in an easy way:
... continue reading