Class: Lernen::Algorithm::Procedural::ATRManager

Inherits:
Object
  • Object
show all
Defined in:
lib/lernen/algorithm/procedural/atr_manager.rb

Overview

ATRManager is a collection to manage access, terminating, and return sequences.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(alphabet, call_alphabet, return_input, scan_procs: true) ⇒ ATRManager

: (

  Array[In] alphabet,
  Array[Call] call_alphabet,
  Return return_input,
  ?scan_procs: bool
) -> void


28
29
30
31
32
33
34
35
36
37
# File 'lib/lernen/algorithm/procedural/atr_manager.rb', line 28

def initialize(alphabet, call_alphabet, return_input, scan_procs: true)
  @alphabet = alphabet
  @call_alphabet_set = call_alphabet.to_set
  @return_input = return_input
  @scan_procs = scan_procs

  @proc_to_access_sequence = {}
  @proc_to_terminating_sequence = {}
  @proc_to_return_sequence = {}
end

Instance Attribute Details

#proc_to_access_sequenceObject (readonly)

: Hash[Call, Array[In | Call | Return]]



39
40
41
# File 'lib/lernen/algorithm/procedural/atr_manager.rb', line 39

def proc_to_access_sequence
  @proc_to_access_sequence
end

#proc_to_return_sequenceObject (readonly)

: Hash[Call, Array[In | Call | Return]]



41
42
43
# File 'lib/lernen/algorithm/procedural/atr_manager.rb', line 41

def proc_to_return_sequence
  @proc_to_return_sequence
end

#proc_to_terminating_sequenceObject (readonly)

: Hash[Call, Array[In | Call | Return]]



40
41
42
# File 'lib/lernen/algorithm/procedural/atr_manager.rb', line 40

def proc_to_terminating_sequence
  @proc_to_terminating_sequence
end

Instance Method Details

#embed(proc, word) ⇒ Object

: (Call proc, Array[In | Call] word) -> Array[In | Call | Return]



84
85
86
87
88
89
# File 'lib/lernen/algorithm/procedural/atr_manager.rb', line 84

def embed(proc, word)
  access_sequence = @proc_to_access_sequence[proc]
  expanded_word = expand(word)
  return_sequence = @proc_to_return_sequence[proc]
  [*access_sequence, *expanded_word, *return_sequence]
end

#expand(word) ⇒ Object

: [In, Call, Return] (Array[In | Call] word) -> Array[In | Call | Return]



92
93
94
# File 'lib/lernen/algorithm/procedural/atr_manager.rb', line 92

def expand(word)
  Automaton::ProcUtil.expand(@return_input, word, @proc_to_terminating_sequence)
end

#find_call_index(word, index) ⇒ Object

: (Array[In | Call | Return] word, Integer index) -> Integer



102
103
104
# File 'lib/lernen/algorithm/procedural/atr_manager.rb', line 102

def find_call_index(word, index) # steep:ignore
  Automaton::ProcUtil.find_call_index(@call_alphabet_set, @return_input, word, index)
end

#find_return_index(word, index) ⇒ Object

: (Array[In | Call | Return] word, Integer index) -> Integer



107
108
109
# File 'lib/lernen/algorithm/procedural/atr_manager.rb', line 107

def find_return_index(word, index) # steep:ignore
  Automaton::ProcUtil.find_return_index(@call_alphabet_set, @return_input, word, index)
end

#project(word) ⇒ Object

: [In, Call, Return] (Array[In | Call] word) -> Array[In | Call | Return]



97
98
99
# File 'lib/lernen/algorithm/procedural/atr_manager.rb', line 97

def project(word)
  Automaton::ProcUtil.project(@call_alphabet_set, @return_input, word)
end

#scan_positive_cex(cex) ⇒ Object

: (Array[In | Call | Return] cex) -> Array



44
45
46
47
48
# File 'lib/lernen/algorithm/procedural/atr_manager.rb', line 44

def scan_positive_cex(cex)
  new_procs = extract_potential_terminating_sequences(cex)
  extract_potential_access_and_return_sequences(cex)
  new_procs
end

#scan_procs(proc_to_dfa, proc_to_state_to_prefix) ⇒ Object

: (

  Hash[Call, Automaton::DFA[In | Call]] procs,
  Hash[Call, Hash[Integer, Array[In | Call]]] proc_to_state_to_prefix
) -> void


54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
# File 'lib/lernen/algorithm/procedural/atr_manager.rb', line 54

def scan_procs(proc_to_dfa, proc_to_state_to_prefix)
  return unless @scan_procs

  updated = false
  stable = false
  until stable
    stable = true
    proc_to_dfa.each do |proc, dfa|
      current_terminating_sequence = @proc_to_terminating_sequence[proc]
      state_to_prefix = proc_to_state_to_prefix[proc]
      hypothesis_terminating_sequence =
        dfa.accept_state_set.to_a.map { |accept_state| expand(state_to_prefix[accept_state]) }.min_by(&:size)

      next unless hypothesis_terminating_sequence
      next if current_terminating_sequence.size <= hypothesis_terminating_sequence.size

      updated = true
      stable = false
      @proc_to_terminating_sequence[proc] = hypothesis_terminating_sequence
    end
  end

  return unless updated

  optimize_sequences(@proc_to_terminating_sequence)
  optimize_sequences(@proc_to_access_sequence)
  optimize_sequences(@proc_to_return_sequence)
end