traverser.groovy

/***********************************************
 * ON THE NATURE OF THE MM-ADT TRAVERSER (RFC) *
 ***********************************************/


// the "traverser" is an obj just like any other obj.
// what makes it a "CPU" is that its "mapped from" instructions (<=) are prefixed with a [choose] instruction.
// more specifically, its a [choose] whose branches encode variables, schema, rewrites, whatever...
// the "traverser" obj can contain read/write state (variables/schema) and flow control (rewrites) (i.e. a register-based CPU).
// it is important to note that there is nothing special about variables, schema, rewrites, etc.
// these are just useful terms developers use for categorizing/organizing/grouping branches.
// to mm-ADT, objs are mapped into the "traverser" and objs are mapped out. obj => traverser => obj
// SIDENOTE: for traversers in a superposition of states, + [branch] can be used instead of | [choose].

// below is a "traverser" obj.
obj{*} <=   // variables 
          [ x      -> 0
          | path   -> [;]
            // schema
          | person -> ['name':str,'age':int]
          | nat    -> int[is,[gt,0]]
            // rewrite
          | inst -> 
           [ nat: 
            [ [plus,0] -> [id]
            | [mult,1] -> [id]] 
           | person:
            [ [dedup]       -> [id]
            | [drop,'name'] -> [error]]]]
              
// the above is syntactic sugar that compiles to the nested [choose] instruction below
//     (note: not all branches above are represented below due to the author being lazy -- multiline cut/paste to the console doesn't work)
mmlang> obj{*} <= [x -> 0 | path -> [;] | person -> ['name':str,'age':int] | nat -> int[is > 0] | [inst -> [nat:[[plus,0] -> [id] | [mult,1] -> [id]]]]]
==>obj{*} <= [choose,[x:0,path:[;],person:['name':str,'age':int],nat:int[is,[gt,0]],inst:[nat:[choose,[[plus,0]:[id],[mult,1]:[id]]]]]]

// when used in a compilation (abstract interpretation) a proper domain is specified (e.g. int).
mmlang> int <= (obj{*} <= [x -> 0 | path -> [;] | person -> ['name':str,'age':int] | nat -> int[is > 0] | [inst -> [nat:[[plus,0] -> [id] | [mult,1] -> [id]]]]])
==>int <= [choose,[x:0,path:[;],person:['name':str,'age':int],nat:int[is,[gt,0]],inst:[nat:[choose,[[plus,0]:[id],[mult,1]:[id]]]]]]

// and then pushed into a query (note the appended instructions as expected from abstract interpretation)
mmlang> int <= [choose,[x:0,path:[;],person:['name':str,'age':int],nat:int[is,[gt,0]],inst:[nat:[choose,[[plus,0]:[id],[mult,1]:[id]]]]]] /
......> => [plus,2][mult,7][gt,2]
==>bool <= [choose,[x:0,path:[;],person:['name':str,'age':int],nat:int[is,[gt,0]],inst:[nat:[choose,[[plus,0]:[id],[mult,1]:[id]]]]]][plus,2][mult,7][gt,2]

// when the above resultant obj's "mapped from" instructions (<=) are used as the query for an "instance" input, the rewrite/schema-components of the "[choose] machine" can be dropped.
mmlang> 3 => [choose,[x:0,path:[;]]][plus,2][mult,7][gt,2]
==>true
// the above is contrived because x & path are never updated so the whole [choose] machine can be dropped.
mmlang> 3 => [plus,2][mult,7][gt,2]
==>true

/**
 * Why is this good?
 *
 * 1. The "traverser" is emergent.
 * -- different types of state machines can be designed purely within mm-ADT.
 * 2. A "traverser"'s state structures are emergent.
 * -- the complexity and computional power of the "traverser" is user defined and specified purely within mm-ADT.
 * -- instead of a register-based CPU, a stack-based CPU can be used.
 * -- schemas can be as expressive as desired (e.g. complex OWL semantics can be encoded).
 * 3. There is only one "rule" in mm-ADT.
 * -- the axioms associated with how objects are => (mapped into) objects. 
 * --   obj => inst (evaluate instruction on obj)
 * --   obj => obj (what aspect of lhs is in rhs)
 * --      inst => obj (this how the "traverser's" [choose] machine's rewrite rules are triggered
**/

////////////////////
// Creating a CPU //
////////////////////

// this cpu is basic.
// it knows the schema
// it has the value 1 paired with the symbol x
// int:[id] is a hack right now. 
//    [optional,[choose,[:]]] will allow us to have a default pass through
mmlang> cpu <= [choose,[int:[id],x:1,person:['name':str,'age':int],people:person{*}]]
==>cpu

// now lets attach it to the int token (sort of like a 'trait' on int)
// this is done by passing int into the <= of cpu. (standard abstract interpretation)
mmlang> int => (cpu <= [choose,[int:[id],x:1,person:['name':str,'age':int],people:person{*}]])
==>int~cpu

// now lets compile a query with this "little machine"-int.
// The sup'd up int~cpu is passed into [plus,1][gt,2]. (standard abstract interpretation)
mmlang> int => (cpu <= [choose,[int:[id],x:1,person:['name':str,'age':int],people:person{*}]]) => [plus,1][gt,2]
==>bool <= [plus,1][gt,2]

// now lets evaluate the query with an "instance" token. (standard abstract interpretation)
mmlang> 4 => (int => (cpu <= [choose,[int:[id],x:1,person:['name':str,'age':int],people:person{*}]]) => [plus,1][gt,2])
==>true
// which is the same as...
mmlang> 4 => [plus,1][gt,2]
==>true

NOTES
When a function needs data from an obj, it passes an obj representing the => desired embedding.

For instance:

Two types of "CPU register" data accesses here.

5~cpu => [plus,x]

1. Symbol access: The symbol x is the input to the <= [choose][...] which, if its stored there as a key will yield the value. The value from the larger example above is 1. It answers: How is x embedded in 5~cpu?
2. Process access: The instruction [plus,1] is the input to the <= [choose][...]. Given no match, and assuming [optional,[choose]]-semantics, [plus,1] is returned and evaluated on 5 to yield 6. How is [plus,1] embedded in 5~cpu? (its not, so its [id] (optional)) and then How is 5~cpu embedded in [plus,1]? It solves how 5 is represented/embedded/encoded in the set of all integers that have 1 added to them. Thus, 6.