This is on the Web at http://pobox.com/~kragen/sw/dhtml-sniki.html. I
wrote it in May but for some reason, as far as I can tell, I never got
around to telling anyone about it, perhaps because I was too ashamed of
the lameness of the implementation.
Like everything else posted to this mailing list without notices to the
contrary, this is in the public domain.
<html>
<head>
<title>Sniki-like DHTML</title>
<!--
Darius Bacon wrote this amazingly cool hack called SnikiSniki, a
Wiki that contained typed links --- rather like RDF triples. I
wanted to play with this same idea in DHTML (probably with Ajax
persistence eventually).
This implementation is really lame in several ways:
- My implementation of depth-first search on the "knowledge base" is
awfully clumsy; I anticipate that in time I will learn to express
this concept more clearly in code.
- Despite living in the browser, the user interface is the
traditional "type text strings into a small box and hit enter"
that we've all come to know and love over the last few decades.
- There's no way to get the first few results before chewing up
large amounts of browser time.
-->
<script src="http://pobox.com/~kragen/sw/jstest-v1.js";></script>
<script>
// -*- c -*-
// simple (yet over-complex) triple-store library; originally in a
// separate file, included here for email
function makebits() {
var stack = [[]]
var results = []
while (stack.length) {
var next = stack.pop()
if (next.length == 3) results.push(next)
else {
var choices = [1, 0]
for (var choice in choices) {
stack.push(next.concat([choices[choice]]))
}
}
}
return results
}
function split_triple(triple) {
return triple.split(/\s+/)
}
function is_var(atomname) {
return atomname.match(/^[A-Z]/)
}
function freevars(triples) {
var rv = []
var seen = {}
for (var ii in triples) {
var items = triples[ii]
for (var jj in items) {
if (is_var(items[jj]) && !seen[items[jj]]) {
rv.push(items[jj])
seen[items[jj]] = 1
}
}
}
return rv
}
function make_object(names, values) {
var rv = {}
for (var ii in names) rv[names[ii]] = values[ii]
return rv
}
function map(cb, list) {
var rv = []
for (var ii = 0; ii < list.length; ii++) rv.push(cb(list[ii]))
return rv
}
function instantiate(triples, instantiations) {
return map(function(triple) {
return map(function(atom) {return instantiations[atom] || atom}, triple)
}, triples)
}
function queryfunction(query_triples) {
var split_query_triples = map(split_triple, query_triples)
var variables = freevars(split_query_triples)
var stack = [[]]
var rv = []
while (stack.length) {
var assignments = stack.pop()
var state = make_object(variables, assignments)
var instantiated_triples = instantiate(split_query_triples, state)
if (this.may_contain(instantiated_triples)) {
if (assignments.length == variables.length) {
rv.push(state)
} else {
var current_variable = variables[assignments.length]
var possible_values =
this.get_candidate_values(instantiated_triples, current_variable)
for (var ii in possible_values) {
stack.push(assignments.concat([possible_values[ii]]))
}
}
}
}
return rv
}
function triple_match(pattern, triple) {
var rv = {}
for (var jj in pattern)
if (!is_var(pattern[jj]) && pattern[jj] != triple[jj]) return null
else rv[pattern[jj]] = triple[jj]
// XXX note that this will be overly optimistic for multiple
occurrences of the variable!
return rv
}
function contains(array, item) {
for (var ii = 0; ii < array.length; ii++)
if (array[ii] == item) return true
return false
}
function triplestore() {
this.triples = []
this.add = function(triples) {
for (var x in triples) this.triples.push(split_triple(triples[x]))
}
this.query = queryfunction
this.may_contain = function(triples) {
for (var ii in triples)
if (!this.may_contain_triple(triples[ii])) return false
return true
}
this.may_contain_triple = function(triple) {
for (var ii in this.triples) {
if (triple_match(triple, this.triples[ii])) return true;
}
return false
}
this.get_candidate_values = function(triples, variable) {
// XXX highly duplicative of may_contain!
var rv = []
var seen = {}
for (var ii in triples)
if (contains(triples[ii], variable))
for (var jj in this.triples) {
var match = triple_match(triples[ii], this.triples[jj])
if (match && !seen[match[variable]]) {
rv.unshift(match[variable])
seen[match[variable]] = 1
}
}
return rv
}
}
tests = {
bits: function() {
assert_equal(makebits(), [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1],
[1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]])
},
is_var: function() {
assert(is_var("A"), "A")
assert(!is_var("a"), "a")
assert(is_var("Ax"), "Ax")
assert(!is_var("xA"), "xA")
assert(is_var("Z"), "Z")
},
freevars: function() {
assert_equal(freevars([]), [])
assert_equal(freevars([['a', 'b', 'c']]), [])
assert_equal(freevars([['a', 'b', 'C']]), ['C'])
assert_equal(freevars([['A', 'B', 'C']]), ['A', 'B', 'C'])
assert_equal(freevars([['A', 'A', 'A']]), ['A'])
},
make_object: function() {
assert_equal(make_object(['beatrice', 'kragen', 'mikel'], ['murch',
'sitaker', 'jay']),
{beatrice: 'murch', kragen: 'sitaker', mikel: 'jay'})
},
triplestore: function() {
var ts = new triplestore()
ts.add(['a b c'])
var yes = [{}]
var no = []
assert_equal(ts.query([]), yes)
assert_equal(ts.query(['a b c']), yes)
assert_equal(ts.query(['a b d']), no)
assert_equal(ts.query(['a b c', 'a b c']), yes)
assert_equal(ts.query(['a b c', 'a b d']), no)
assert_equal(ts.query(['a b d', 'a b d']), no)
assert_equal(ts.query(['a b d', 'a b c']), no)
assert_equal(ts.query(['a b X']), [{X: 'c'}])
assert_equal(ts.query(['a X c']), [{X: 'b'}])
assert_equal(ts.query(['X b c']), [{X: 'a'}])
assert_equal(ts.query(['a X d']), no)
assert_equal(ts.query(['a X Y']), [{X: 'b', Y: 'c'}])
assert_equal(ts.query(['a X X']), no)
assert_equal(ts.query(['A B C']), [{A: 'a', B: 'b', C: 'c'}])
ts.add(['same c c', 'a b e'])
assert_equal(ts.query(['a b c']), yes)
assert_equal(ts.query(['a b c', 'a b e']), yes)
assert_equal(ts.query(['a b e', 'a b c']), yes)
assert_equal(ts.query(['a b d', 'a b c']), no)
assert_equal(ts.query(['A B C']), [
{A: 'a', B: 'b', C: 'c'},
{A: 'a', B: 'b', C: 'e'},
{A: 'same', B: 'c', C: 'c'},
])
assert_equal(ts.query(['A B C', 'A b c']), [
{A: 'a', B: 'b', C: 'c'},
{A: 'a', B: 'b', C: 'e'}])
assert_equal(ts.query(['a b X']), [{X: 'c'}, {X: 'e'}])
assert_equal(ts.query(['X Y Y']), [{X: 'same', Y: 'c'}])
assert_equal(ts.query(['A B C', 'X C Y']), [
{A: 'a', B: 'b', C: 'c', X: 'same', Y: 'c'},
{A:"same", B:"c", C:"c", X:"same", Y:"c"}])
},
triplestore_bits: function() {
var ts = new triplestore()
ts.add(['bit bit 0', 'bit bit 1'])
assert_equal(ts.query(['bit bit B0', 'bit bit B1', 'bit bit B2']),
[{B0:"0", B1:"0", B2:"0"}, {B0:"0", B1:"0", B2:"1"},
{B0:"0", B1:"1", B2:"0"}, {B0:"0", B1:"1", B2:"1"},
{B0:"1", B1:"0", B2:"0"}, {B0:"1", B1:"0", B2:"1"},
{B0:"1", B1:"1", B2:"0"}, {B0:"1", B1:"1", B2:"1"}])
},
};
</script>
<script>
// DHTML bits for this sample page
function tablerow(contents, type) {
if (!type) type = 'td'
var el = document.createElement('tr')
for (var ii = 0; ii < contents.length; ii++) {
var td = document.createElement(type)
td.appendChild(document.createTextNode(contents[ii]))
el.appendChild(td)
}
return el
}
function clear_node(nod) {
nod.innerHTML = ''
// Mozilla erroneously caches some layout... fix it
var old_display = nod.style.display
nod.style.display = 'none'
nod.style.display = old_display
}
function perform_query(qel, ts, triples) {
clear_node(qel)
var headers = freevars(map(split_triple, triples))
qel.appendChild(tablerow(headers, 'th'))
var data = ts.query(triples)
for (var ii in data)
qel.appendChild(tablerow(map(function(propname){return
data[ii][propname]}, headers)))
}
var ts = new triplestore()
function handle_input(somestuff) {
var triples = somestuff.split(/,\s*/)
var free = freevars(map(split_triple, triples))
if (free.length) {
perform_query(document.getElementById('querytable'), ts, triples)
} else {
// add to triple store
var tb = document.getElementById('stufftable')
for (var ii in triples)
tb.appendChild(tablerow(split_triple(triples[ii])))
ts.add(triples)
}
return false
}
function set_up_test_stuff() {
handle_input('beatrice parent aggie, beatrice spouse kragen, kragen spouse
beatrice, beatrice parent walter, kragen parent greg')
handle_input('aggie spouse walter, greg spouse paula')
var query = 'Person spouse Spouse, Spouse parent In-law, In-law spouse
In-law-2'
var field = document.getElementById('theform').stuff
field.value = query
handle_input(query)
field.focus()
}
</script>
</head>
<body onload="barebones_run_tests();set_up_test_stuff()"><h1>Toy triple store
in DHTML</h1>
<p> Inspired by Sniki.</p>
<table id="stufftable">
<tr><th>object</th><th>property</th><th>value</th></tr>
</table>
<table id="querytable">
</table>
<form id="theform" onsubmit="return handle_input(this.stuff.value)">
<input size="80" name="stuff" />
</form>
</body>
</html>
