Leonard Ritter paniq

Low-Level Datalog

With the right low level composition primitives, it would be possible to even describe accelerating data structures in a relational way.

Let's begin by treating the heap as a special relation.

# arcmem heap as polymorphic lattice
# .decl heap(address : T*, value : T)

Encoding polymorphic values (sum types) in the heap can be trivially done by a type code/index (or simply tag) in the value's header.

For large per-tag pools of monotypal objects, the pool range itself can serve as identifying the type. A pointer into the pool can be checked against all known pool extents to extract the tag. Unfortunately this makes memory relocation difficult, and prohibits the use of multiple pools for the same tag.

A better approach when the heap supports baseable pointers (such as arcmem), is to store the tag of a pool at its beginning; a pointer into the pool can then be based to the pool header, amortizing the cost of a type tag.

All three mentioned approaches suffer from the issue however that casts are expensive as we need to copy values just to change their type, even though the actual attributes of the value did not change.

For the case where the number of types for a sum type S is smaller than the alignment of S, which is invariant, the type index (or tag) can instead be stored

Doubly linked list with delta pointers:

p[x] = { value, xor(p[x-1], p[x+1]) }

Then, starting at p[-1] = null, p[0] = p_first:

p[n+1] = xor(p[n][1], p[n-1])

	fn bitstripes (n)
	-1:u64 // ((1:u64 << n) \| 1)

	fn rbitstripes (n)
	d := (1:u64 << n) \| 1
	f := max (n * 2) 1
	k := 64:u64 // f
	kf := k * f
	sh := 64:u64 - kf
	m := (-1:u64 // d) >> sh

	% strongly connected components

	% example from sedgewick, algorithms in C++, part 5, figure 19.28, §19.8, p. 207
	% edge(from, to)
	e(0,1). e(0,5). e(0,6).
	e(2,0). e(2,3).
	e(3,2). e(3,5).
	e(4,2). e(4,3). e(4,11).
	e(5,4).
	e(6,4). e(6,9).

	% dominator analysis

	% example from sedgewick, algorithms in C++, part 5, figure 19.21, §19.6, p. 191
	% edge(from, to)
	e(0,1). e(0,2). e(0,3). e(0,5). e(0,6).
	e(2,3).
	e(3,4). e(3,5).
	e(4,9).
	e(6,4). e(6,9).
	e(7,6).



	symbol(1,"the").
	symbol(2,"quick").
	symbol(3,"brown").
	symbol(4,"fox").
	symbol(5,"jumped").
	symbol(6,"over").
	symbol(7,"the").
	symbol(8,"lazy").


	L(23,1).
	L(2,75).
	L(5,75).
	L(60,90).
	L(5,101).
	L(60,3).
	L(707,66).
	L(42,77).
	L(5,15).



	L(23).
	L(60).
	L(5).
	L(707).
	L(42).

	adj(?a,#min(?b)) :- L(?a), L(?b), ?a < ?b.

	% directed acyclical graph related queries in nemo/datalog

	% example from sedgewick, algorithms in C++, part 5, figure 19.21, §19.6, p. 191
	% edge(from, to)
	e(0,1). e(0,2). e(0,3). e(0,5). e(0,6).
	e(2,3).
	e(3,4). e(3,5).
	e(4,9).
	e(6,4). e(6,9).
	e(7,6).