instacheck.reduce — kanaka/instacheck 0.9.2

memoized-distance-trek clj/s

prune-grammar clj/s

(prune-grammar grammar {:keys [wtrek start removed] :as ctx})

Takes a grammar and returns a pruned grammar based on keys specified in the options map. Three different prune operations are performed:

• Removes rules listed in :removed
• Prune rule bodies/productions based on :wtrek
• If :start is specified in the options or is on the meta of the grammar, then rules are removed that cannot be reached (directly or indirectly) from the start rule/production..

prune-grammar->sorted-ebnf clj/s

(prune-grammar->sorted-ebnf grammar {:keys [wtrek cycle-set] :as ctx})

reduce-wtrek clj/s

(reduce-wtrek grammar
              start-wtrek
              &
              [{:keys [reduced-subset reduce-mode reducer-fn]
                :or {reduce-mode :zero reducer-fn reducer-zero}
                :as opts}])

Takes a grammar and wtrek and returns a new reduced wtrek with weights reduced/propagated according to reduce-mode.

If the optional reduced-subset node set is then only those nodes will be propagated. If reduced-subset is not specified then all reducible/weighted nodes will be considered. The former may result in a wtrek that is not fully reduced but the latter can take a while for large grammars/wtreks.

The way that weights are reduced/propagated depends on reduce-mode:

:zero If all siblings of a node have a zero weight, reduce parent edge weights to zero.

Algorithm/psuedocode:
- pend := reduced-subset OR all weighted nodes in the tree
- while pend:
  - node   := pop(pend)
  - mcw    := max-child-weight(node)
  - if mcw > 0: continue at while
  - foreach pnode of parents(node):
    - push(pend, pnode)
    - wtrek[pnode] := mcw

:max-child: If all siblings of a node have a weight that is less than parent edge weight then reduce the parent edge weights to the largest sibling weight.

Algorithm/psuedocode:
- pend := reduced-subset OR all weighted nodes in the tree
- while pend:
  - node   := pop(pend)
  - mcw    := max-child-weight(node)
  - foreach pnode of parents(node):
    - if pnode child weight towards node > mcw
      - then:
        - push(pend, pnode)
        - wtrek[pnode] := mcw

:reducer: When all siblings of a node are zero, reduce parent edge weights by reducer-fn function and distribute the removed weights to valid (no removed descendant) child edges of node.

Algorithm/psuedocode:
- pend := reduced-subset OR all weighted nodes in the tree
- while pend:
  - node   := pop(pend)
  - mcw    := max-child-weight(node)
  - if mcw > 0: continue at while
  - acc    := 0
  - foreach pnode of parents(node):
    - tmp := wtrek[pnode]
    - wtrek[pnode] := reducer-fn(wtrek[pnode])
    - acc  += tmp - wtrek[pnode]
    - if max-child-weight(pnode) == 0:
      - push(pend, pnode)
  - cnodes := children-with-no-removed-descendants(node)
  - foreach cnode of cnodes:
    - wtrek[code] += acc / count(cnodes)

Any zero weights in the :wtrek map represent a node edge that has been removed. If all edges of a node are 0 then this is represents a node that has been removed and the removal must be propagated up the tree to the next weighted node edge. If the propagation of removed nodes (0 weights) reaches the root/start of the grammar and cannot propagate further then an exception is thrown because this represents an invalid weighted grammar: grammar productions could reach the removed node from the root/start rule (a removed node does not exist in the sense that epsilon does).

The propagation of node removals continues until there are no more pending node to remove. A node may have more than one parent which means the number of nodes being considered during propagation may increase temporarily but already removed nodes will not be added again so the process will eventually terminate.

reduce-wtrek-with-weights clj/s

(reduce-wtrek-with-weights grammar
                           wtrek
                           weights-to-reduce
                           &
                           [{:keys [reduce-mode reducer-fn pick-mode pick-pred
                                    rnd-obj]
                             :or {reduce-mode :zero
                                  reducer-fn reducer-half
                                  pick-mode :weight-dist
                                  pick-pred identity}
                             :as opts}])

Takes a grammar, wtrek, a weights-to-reduce map, a reduce-mode keyword, and a reducer-fn. A path from weights-to-reduce is selected based on pick-mode. For that path the reducer-fn is called with the weight for the path from wtrek and the weight for the path from weights-to-reduce. Based on those two values the reducer-fn should return a new value to be updated in the wtrek.

pick-mode values: :weight - randomly pick a node weighted by node weights. :dist - randomly pick a node weighted by node distances from the start node :weight-dist - randomly pick a node weighted by node weights multiplied by node distances from the start node.

The resulting wtrek will then be passed to the reduce-wtrek function to propogate the weight reduction according reduce-mode.

reducer-div clj/s

(reducer-div divisor start-weight parsed-weight)

If parsed-weight > 0 then returns the start-weight divided by the divisor: (partial reducer-div 4)

reducer-half clj/s

(reducer-half start-weight parsed-weight)

If parsed-weight > 0 then returns start-weight divided in two and rounded down.

reducer-ladder clj/s

(reducer-ladder seq-ladder start-weight parsed-weight)

If parsed-weight > 0 then returns the next weight in seq-ladder that is lower than start-weight. Designed to be used as a partial like this: (partial reducer-ladder [30 10 3 1]) The values in the ladder will be sorted in descending order and an implicit zero is added to the end.

reducer-zero clj/s

(reducer-zero start-weight parsed-weight)

If parsed-weight > 0 then returns 0