alloy - Replacing recursion with transitive closure (reachability and productivity of non-terminals) -

sometimes, when use recursion in alloy, find can transitive closure, or sequences.

for example, in model of context-free grammars:

abstract sig symbol {} sig nt, t extends symbol {}  // grammar tuple(v, sigma, rules, start)  1 sig grammar {   v : set nt,   sigma : set t,   rules : set prod,   start : 1 v }  // production rule has left-hand side // , right-hand side sig prod {   lhs : nt,   rhs : seq symbol }  fact tidy_world {   // don't fill model irrelevancies   prod in grammar.rules   symbol in (grammar.v + grammar.sigma) } 

one possible definition of reachable non-terminals "the start symbol, , non-terminal appearing on right-hand side of rule reachable symbol." straightforward translation be

// non-terminal 'refers' non-terminals // in right-hand sides of rules pred refers[n1, n2 : nt] {   let r = (grammar.rules & lhs.n1) |   n2 in r.rhs.elems }  pred reachable[n : nt] {   n in grammar.start   or n2 : nt      | (reachable[n2] , refers[n2,n]) } 

predictably, blows stack. if take transitive closure of grammar.start under refers relation (or, strictly speaking, relation formed refers predicate), can define reachability:

// non-terminal 'reachable' if it's // start symbol or if referred // (rules for) reachable symbol. pred reachable[n : nt] {   n in grammar.start.*(     {n1, n2 : nt | refers[n1,n2]}   ) }  pred some_unreachable {   n : (nt - grammar.start)      | not reachable[n] } run some_unreachable 4 

in principle, definition of productive symbols recursive: symbol productive iff terminal symbol, or has @ least 1 rule in every symbol in right-hand side productive. simple-minded way write is

pred productive[s : symbol] {   s in t    or p : (lhs.s) |        r : (p.rhs.elems) | productive[r] } 

like straightforward definition of reachability, blows stack. have not yet found relation can define on symbols give me, via transitive closure, result want. have found case transitive closure cannot substitute recursion? or have not thought hard enough find right relation?

there obvious, if laborious, hack:

pred p0[s : symbol] { s in t } pred p1[s : symbol] { p0[s]    or p : (lhs.s)    | e : p.rhs.elems    | p0[e]} pred p2[s : symbol] { p1[s]    or p : (lhs.s)    | e : p.rhs.elems    | p1[e]} pred p3[s : symbol] { p2[s]    or p : (lhs.s)    | e : p.rhs.elems    | p2[e]} ... etc ... pred productive[n : nt] {   p5[n] } 

this works ok long 1 doesn't forget add enough predicates handle longest possible chain of non-terminal references, if 1 raises scope.

concretely, seem have several questions; answers of them welcome:

1 there way define set of productive non-terminals in alloy without resorting p0, p1, p2, ... hack?

2 if 1 have resort hack, there better way define it?

3 theoretical question: possible characterize set of recursive predicates can defined using transitive closure, or sequences of atoms, instead of recursion?

have found case transitive closure cannot substitute recursion?

yes, case. more precisely, found recursive relation cannot expressed first-order transitive closure (that supported in alloy).

is there way define set of productive non-terminals in alloy without resorting p0, p1, p2, ... hack? if 1 have resort hack, there better way define it?

there no way in alloy. however, there might way in alloy* supports higher-order quantification. (the idea describe set of productive elements closure on relation of "productiveness", use second-order quantification on set of productive symbols, , constraining set minimal. similar idea described in "a.1.9 axiomatizing transitive closure" in alloy book.)

as theoretical question: possible characterize set of recursive predicates can defined using transitive closure, or sequences of atoms, instead of recursion?

this interesting question. wiki article mentions relative expressiveness of second order logic when transitive closure , fixed point operator added (the later being able express forms of recursion).