dymokomi/luce-prism
Source of release 0.6.0
0.6.0 / src / logic / theory.lucb
## Ground the structured theory over its finite universe of constants.
import collections.sort as sorting
from logic.atoms import AtomData, RuleKind, read_atom, read_text
from model import DocumentData
from collections.index import Index
from storage import List, Buffer, text_copy
from path import path_name
from types import invalid, limit_exceeded, max_items
pub struct Literal:
pub var atom: AtomData
pub var key: Buffer
pub var complement: usize
pub var fact: bool
pub var definite: bool
pub var proof: bool
pub var refute: bool
pub var supporters: List[usize]
pub var rules: List[usize]
pub func close():
self.atom.close()
self.key.close()
self.supporters.close()
self.rules.close()
pub struct GroundRule:
pub var name: usize
pub var kind: RuleKind
pub var head: usize
pub var body: List[usize]
pub func close():
self.body.close()
struct RawRule:
var name: Buffer
var kind: RuleKind
var fact: bool
var head: AtomData
var body: List[AtomData]
func close():
self.name.close()
self.head.close()
for i in 0..<self.body.count:
self.body.items[i].close()
self.body.close()
pub struct Theory:
pub var literals: List[Literal]
pub var rules: List[GroundRule]
pub var order: List[usize]
pub var names: Index
var keys: Index
var superiority: Index
pub func find(key: str) -> usize?:
let bucket = self.keys.find(key) else return none
return self.keys.buckets.items[bucket].rows.items[0]
pub func superior(a: usize, b: usize) -> bool:
let bucket = self.superiority.find(self.names.buckets.items[a].key.view()) else return false
for name in self.superiority.buckets.items[bucket].rows.span():
if name == b:
return true
return false
func note_one(atom: const AtomData*, fact: bool) -> usize!:
var key = try atom.key()
defer key.close()
if let index = self.find(key.view()):
self.literals.items[index].fact = self.literals.items[index].fact or fact
return index
var literal = Literal(fact = fact)
errdefer literal.close()
literal.atom = try atom.copy()
literal.key = try key.copy()
try self.literals.reserve(self.literals.count + 1)
let index = self.literals.count
_ = try self.keys.add(key.view(), index)
try self.literals.push(literal)
return index
func note(atom: const AtomData*, fact: bool = false) -> usize!:
let index = try self.note_one(atom, fact)
var opposite = try atom.copy()
defer opposite.close()
opposite.negative = not opposite.negative
let complement = try self.note_one(&opposite, false)
self.literals.items[index].complement = complement
self.literals.items[complement].complement = index
return index
func ground(rule: const RawRule*, constants: const str[], variables: const Index*, assignment: const usize[]) -> !:
var ground = GroundRule(kind = rule.kind)
errdefer ground.close()
ground.name = try intern(&self.names, rule.name.view())
var head = try substitute(&rule.head, constants, variables, assignment)
defer head.close()
ground.head = try self.note(&head)
try ground.body.reserve(rule.body.count)
for atom in rule.body.span():
var body = try substitute(&atom, constants, variables, assignment)
defer body.close()
try ground.body.push(try self.note(&body))
try self.rules.reserve(self.rules.count + 1)
let literal = &self.literals.items[ground.head]
try literal.rules.reserve(literal.rules.count + 1)
if rule.kind != RuleKind.defeater:
try literal.supporters.reserve(literal.supporters.count + 1)
try literal.supporters.push(self.rules.count)
try literal.rules.push(self.rules.count)
try self.rules.push(ground)
pub func close():
for i in 0..<self.literals.count:
self.literals.items[i].close()
self.literals.close()
for i in 0..<self.rules.count:
self.rules.items[i].close()
self.rules.close()
self.order.close()
self.names.close()
self.keys.close()
self.superiority.close()
func intern(index: Index*, name: str) -> usize!:
if let existing = index.find(name):
return existing
return try index.add(name, 0)
func substitute(atom: const AtomData*, constants: const str[], variables: const Index*, assignment: const usize[]) -> AtomData!:
var result = AtomData(negative = atom.negative)
errdefer result.close()
result.predicate = try atom.predicate.copy()
for arg in atom.arguments.span():
var name = arg.name.view()
if arg.variable:
if let index = variables.find(name):
name = constants[assignment[index]]
try result.append(name, false)
return result
func collect(atom: const AtomData*, constants: Index*, variables: Index*, fact: bool) -> !:
for arg in atom.arguments.span():
if fact or not arg.variable:
_ = try intern(constants, arg.name.view())
elif arg.variable:
_ = try intern(variables, arg.name.view())
func close_raw(rules: List[RawRule]*):
for i in 0..<rules.count:
rules.items[i].close()
rules.close()
pub func build(doc: const DocumentData*) -> Theory!:
var theory: Theory
errdefer theory.close()
var raw: List[RawRule]
defer close_raw(&raw)
var constants: Index
defer constants.close()
var ignored: Index
defer ignored.close()
for element in doc.elements.span():
let kind = element.kind.view()
if kind == "sup":
var superior = try read_text(doc, element.path.view(), "superior")
defer superior.close()
var inferior = try read_text(doc, element.path.view(), "inferior")
defer inferior.close()
_ = try intern(&theory.names, superior.view())
let name = try intern(&theory.names, inferior.view())
_ = try theory.superiority.add(superior.view(), name)
continue
if kind != "fact" and kind != "strict" and kind != "defeasible" and kind != "defeater":
continue
var rule = RawRule(fact = kind == "fact", kind = RuleKind.strict if kind == "strict" else (RuleKind.defeater if kind == "defeater" else RuleKind.defeasible))
errdefer rule.close()
rule.name = try text_copy(path_name(element.path.view()))
for i in 0..<doc.child_count(element.path.view()):
let child = doc.child_at(element.path.view(), i) else error(invalid, "invalid Prism rule child index")
var atom = try read_atom(doc, child)
errdefer atom.close()
if path_name(child) == "head":
rule.head.close()
rule.head = atom
else:
try rule.body.push(atom)
atom = AtomData()
try collect(&rule.head, &constants, &ignored, rule.fact)
if not rule.fact:
for atom in rule.body.span():
try collect(&atom, &constants, &ignored, false)
try raw.push(rule)
var constant_names: List[str]
defer constant_names.close()
for bucket in constants.buckets.span():
try constant_names.push(bucket.key.view())
sorting.text(constant_names.span())
for rule in raw.span():
if rule.fact:
_ = try theory.note(&rule.head, true)
continue
var variables: Index
defer variables.close()
try collect(&rule.head, &constants, &variables, false)
for atom in rule.body.span():
try collect(&atom, &constants, &variables, false)
var combinations: usize = 1
for i in 0..<variables.buckets.count:
combinations = combinations *? constant_names.count else error(limit_exceeded, "Prism logic grounding exceeds the rule limit")
if combinations > max_items - theory.rules.count:
error(limit_exceeded, "Prism logic grounding exceeds the rule limit")
var assignment: List[usize]
defer assignment.close()
for i in 0..<variables.buckets.count:
try assignment.push(0)
for ordinal in 0..<combinations:
var remaining = ordinal
var position = assignment.count
while position > 0:
position -= 1
assignment.items[position] = remaining % constant_names.count
remaining = remaining // constant_names.count
try theory.ground(&rule, constant_names.span(), &variables, assignment.span())
var keys: List[str]
defer keys.close()
for literal in theory.literals.span():
try keys.push(literal.key.view())
sorting.text(keys.span())
for key in keys.span():
try theory.order.push(theory.find(key) else error(invalid, "invalid grounded Prism literal index"))
return theory