Class: Stamina::Utils::Decorate

Inherits:
Object
  • Object
show all
Defined in:
lib/stamina-core/stamina/utils/decorate.rb

Overview

Decorates states of an automaton by applying a propagation rule until a fix point is reached.

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(output = :invariant) ⇒ Decorate

Creates a decoration algorithm instance



10
11
12
13
14
15
16
17
 
# File 'lib/stamina-core/stamina/utils/decorate.rb', line 10

def initialize(output = :invariant)
  @output    = Decorate.state_output(output) if output
  @suppremum = nil
  @propagate = nil
  @initiator = nil
  @backward  = false
  @start_predicate = nil
end

Class Method Details

.state_output(decoration_key) ⇒ Object

Builds an output hash that keeps decoration in states



20
21
22
23
24
25
26
27
28
29
 
# File 'lib/stamina-core/stamina/utils/decorate.rb', line 20

def self.state_output(decoration_key)
  Object.new.extend Module.new{
    define_method :[] do |state|
      state[decoration_key]
    end
    define_method :[]= do |state,deco|
      state[decoration_key] = deco
    end
  }
end

Instance Method Details

#backward=(val) ⇒ Object

Sets if the algorithms works backward



83
84
85
 
# File 'lib/stamina-core/stamina/utils/decorate.rb', line 83

def backward=(val)
  @backward = val
end

#backward? ⇒ Boolean

Work backward?

Returns:

  • (Boolean) 


122
123
124
 
# File 'lib/stamina-core/stamina/utils/decorate.rb', line 122

def backward?
  @backward
end

#call(fa, out = nil) ⇒ Object

Executes the propagation algorithm on a given automaton.



129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
 
# File 'lib/stamina-core/stamina/utils/decorate.rb', line 129

def call(fa, out = nil)
  with_output(out) do |output|
    fa.states.each{|s| output[s] = init_deco(s) }        # Init decoration on each state
    to_explore = fa.states.select{|s| take_at_start?(s)} # Init to_explore (start predicate)
    until to_explore.empty?                              # empty to_explore now
      source = to_explore.pop
      each_edge_and_target(source) do |edge, target|
        p_decor = propagate(output[source], edge)
        p_decor = suppremum(output[target], p_decor)
        unless p_decor == output[target]
          output[target] = p_decor
          to_explore << target unless to_explore.include?(target)
        end
      end
    end
    fa
  end
end

#execute(fa, bottom, d0) ⇒ Object

Executes the propagation algorithm on a given automaton.



149
150
151
152
153
154
 
# File 'lib/stamina-core/stamina/utils/decorate.rb', line 149

def execute(fa, bottom, d0)
  warn "Decorate#execute is deprecated, use Decorate#call (#{caller[0]})"
  self.initiator       = lambda{|s| (s.initial? ? d0 : bottom)}
  self.start_predicate = lambda{|s| s.initial? }
  call(fa)
end

#init_deco(s) ⇒ Object

Returns the initial decoration of state ‘s`



110
111
112
113
 
# File 'lib/stamina-core/stamina/utils/decorate.rb', line 110

def init_deco(s)
  return @initiator.call(s) if @initiator
  raise "No initiator function installed"
end

#initiator=(proc) ⇒ Object

Same as #set_initiator but with an explicit proc



66
67
68
 
# File 'lib/stamina-core/stamina/utils/decorate.rb', line 66

def initiator=(proc)
  set_initiator(&proc)
end

#propagate(deco, edge) ⇒ Object

Computes the propagation rule. By default, this method looks for a propagate function installed with set_propagate. If not found, it tries calling a + method on deco. If not found it raises an error. This method may be overriden.



103
104
105
106
107
 
# File 'lib/stamina-core/stamina/utils/decorate.rb', line 103

def propagate(deco, edge)
  return @propagate.call(deco, edge) if @propagate
  return deco.+(edge) if deco.respond_to?(:+)
  raise "No propagate function installed or implemented by decorations"
end

#propagate=(proc) ⇒ Object

Same as #set_propagate, but with an explicit proc



53
54
55
 
# File 'lib/stamina-core/stamina/utils/decorate.rb', line 53

def propagate=(proc)
  set_propagate(&proc)
end

#set_initiator(&block) ⇒ Object

Set an initiator methods, responsible of computing the initial decoration of each state

Raises:

  • (ArgumentError) 


59
60
61
62
63
 
# File 'lib/stamina-core/stamina/utils/decorate.rb', line 59

def set_initiator(&block)
  raise ArgumentError, 'Initiator expected through a block' if block.nil?
  raise ArgumentError, 'Block of arity 1 expected' unless block.arity==1
  @initiator = block
end

#set_propagate(&block) ⇒ Object

Installs a propagate function through a block.

Raises:

  • (ArgumentError) 


46
47
48
49
50
 
# File 'lib/stamina-core/stamina/utils/decorate.rb', line 46

def set_propagate(&block)
  raise ArgumentError, 'Propagate expected through a block' if block.nil?
  raise ArgumentError, 'Block of arity 2 expected' unless block.arity==2
  @propagate = block
end

#set_start_predicate(&block) ⇒ Object

Sets the start predicate to use

Raises:

  • (ArgumentError) 


71
72
73
74
75
 
# File 'lib/stamina-core/stamina/utils/decorate.rb', line 71

def set_start_predicate(&block)
  raise ArgumentError, 'Start predicate expected through a block' if block.nil?
  raise ArgumentError, 'Block of arity 1 expected' unless block.arity==1
  @start_predicate = block
end

#set_suppremum(&block) ⇒ Object

Installs a suppremum function through a block.

Raises:

  • (ArgumentError) 


34
35
36
37
38
 
# File 'lib/stamina-core/stamina/utils/decorate.rb', line 34

def set_suppremum(&block)
  raise ArgumentError, 'Suppremum expected through a block' if block.nil?
  raise ArgumentError, 'Block of arity 2 expected' unless block.arity==2
  @suppremum = block
end

#start_predicate=(proc) ⇒ Object

Same as #set_start_predicate but with an explicit proc



78
79
80
 
# File 'lib/stamina-core/stamina/utils/decorate.rb', line 78

def start_predicate=(proc)
  set_start_predicate(&proc)
end

#suppremum(d0, d1) ⇒ Object

Computes the suppremum between two decorations. By default, this method looks for a suppremum function installed with set_suppremum. If not found, it tries calling a suppremum method on d0. If not found it raises an error. This method may be overriden.



93
94
95
96
97
 
# File 'lib/stamina-core/stamina/utils/decorate.rb', line 93

def suppremum(d0, d1)
  return @suppremum.call(d0, d1) if @suppremum
  return d0.suppremum(d1) if d0.respond_to?(:suppremum)
  raise "No suppremum function installed or implemented by decorations"
end

#suppremum=(proc) ⇒ Object

Same as #set_suppremum, but with an explicit proc



41
42
43
 
# File 'lib/stamina-core/stamina/utils/decorate.rb', line 41

def suppremum=(proc)
  set_suppremum(&proc)
end

#take_at_start?(s) ⇒ Boolean

Returns the start predicate

Returns:

  • (Boolean) 


116
117
118
119
 
# File 'lib/stamina-core/stamina/utils/decorate.rb', line 116

def take_at_start?(s)
  return @start_predicate.call(s) if @start_predicate
  raise "No start predicate function installed"
end