Class: Ibex::Samples

Inherits:
Object
  • Object
show all
Defined in:
lib/ibex/samples.rb,
sig/ibex/samples.rbs

Overview

Generates bounded terminal sentences from Grammar IR.

Constant Summary collapse

DEFAULT_MAX_EXPANSIONS =

Signature:

  • Integer

Returns:

  • (Integer) 
100_000

Instance Method Summary collapse

Constructor Details

#initialize(grammar, seed: 0, max_tokens: 32, max_depth: 16, max_expansions: DEFAULT_MAX_EXPANSIONS, strategy: :random, path_length: 1) ⇒ Samples

Returns a new instance of Samples.

RBS:

  • (IR::Grammar grammar, ?seed: Integer, ?max_tokens: Integer, ?max_depth: Integer, ?max_expansions: Integer, ?strategy: Symbol | String, ?path_length: Integer) -> void

Parameters:

  • grammar (IR::Grammar)
  • seed: (Integer) (defaults to: 0)
  • max_tokens: (Integer) (defaults to: 32)
  • max_depth: (Integer) (defaults to: 16)
  • max_expansions: (Integer) (defaults to: DEFAULT_MAX_EXPANSIONS)
  • strategy: (Symbol, String) (defaults to: :random)
  • path_length: (Integer) (defaults to: 1) 


11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
# File 'lib/ibex/samples.rb', line 11

def initialize(grammar, seed: 0, max_tokens: 32, max_depth: 16, max_expansions: DEFAULT_MAX_EXPANSIONS,
               strategy: :random, path_length: 1)
  raise ArgumentError, "max_tokens must be positive" unless max_tokens.positive?
  raise ArgumentError, "max_depth must be positive" unless max_depth.positive?
  raise ArgumentError, "max_expansions must be positive" unless max_expansions.positive?

  normalized_strategy = strategy.to_sym
  unless %i[random coverage].include?(normalized_strategy)
    raise ArgumentError, "strategy must be :random or :coverage"
  end
  raise ArgumentError, "path_length must be 1 or 2" unless [1, 2].include?(path_length)

  @grammar = grammar
  @random = Random.new(seed)
  @max_tokens = max_tokens
  @max_depth = max_depth
  @max_expansions = max_expansions
  @strategy = normalized_strategy
  @path_length = path_length
  @path_coverage = Hash.new(0) #: Hash[Array[Integer], Integer]
  @productions = grammar.productions.group_by(&:lhs)
  @minimum_costs = compute_minimum_costs
  @minimum_heights = compute_minimum_heights
end

Instance Method Details

#bounded_productions(nonterminal_id, budget) ⇒ Array[IR::Production]

RBS:

  • (Integer nonterminal_id, Integer budget) -> Array[IR::Production]

Parameters:

  • nonterminal_id (Integer)
  • budget (Integer)

Returns:



175
176
177
178
179
180
181
182
183
184
185
186
 
# File 'lib/ibex/samples.rb', line 175

def bounded_productions(nonterminal_id, budget)
  productions = @productions[nonterminal_id]
  raise Ibex::Error, "(samples):1:1: no bounded derivation for symbol #{nonterminal_id}" unless productions

  candidates = productions.select do |production|
    cost = production_cost(production)
    cost && cost <= budget
  end
  raise Ibex::Error, "(samples):1:1: no bounded derivation for symbol #{nonterminal_id}" if candidates.empty?

  candidates
end

#choose_production(nonterminal_id, budget, depth, path) ⇒ IR::Production

RBS:

  • (Integer nonterminal_id, Integer budget, Integer depth, Array[Integer] path) -> IR::Production

Parameters:

  • nonterminal_id (Integer)
  • budget (Integer)
  • depth (Integer)
  • path (Array[Integer])

Returns:



164
165
166
167
168
169
170
171
172
 
# File 'lib/ibex/samples.rb', line 164

def choose_production(nonterminal_id, budget, depth, path)
  candidates = bounded_productions(nonterminal_id, budget)
  candidates = minimum_height_productions(candidates) if depth >= @max_depth
  return candidates.fetch(@random.rand(candidates.length)) if @strategy == :random

  minimum_coverage = candidates.map { |production| path_count(path, production) }.min
  least_covered = candidates.select { |production| path_count(path, production) == minimum_coverage }
  least_covered.fetch(@random.rand(least_covered.length))
end

#compute_minimum_costs ⇒ Hash[Integer, Integer?]

RBS:

  • () -> Hash[Integer, Integer?]

Returns:

  • (Hash[Integer, Integer?]) 


61
62
63
64
65
66
 
# File 'lib/ibex/samples.rb', line 61

def compute_minimum_costs
  compute_minimum_values(1) do |production, values|
    rhs_values = resolved_rhs_values(production, values)
    rhs_values&.sum
  end
end

#compute_minimum_heights ⇒ Hash[Integer, Integer?]

RBS:

  • () -> Hash[Integer, Integer?]

Returns:

  • (Hash[Integer, Integer?]) 


69
70
71
72
73
74
 
# File 'lib/ibex/samples.rb', line 69

def compute_minimum_heights
  compute_minimum_values(0) do |production, values|
    rhs_values = resolved_rhs_values(production, values)
    rhs_values && ((rhs_values.max || 0) + 1)
  end
end

#compute_minimum_values(terminal_value) {|arg0, arg1| ... } ⇒ Hash[Integer, Integer?]

RBS:

  • (Integer terminal_value) { (IR::Production, Hash[Integer, Integer?]) -> Integer? } -> Hash[Integer, Integer?]

Parameters:

  • terminal_value (Integer)

Yields:

Yield Parameters:

Yield Returns:

  • (Integer, nil)

Returns:

  • (Hash[Integer, Integer?]) 


78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
 
# File 'lib/ibex/samples.rb', line 78

def compute_minimum_values(terminal_value)
  values = @grammar.symbols.to_h { |symbol| [symbol.id, nil] } #: Hash[Integer, Integer?]
  dependents = {} #: Hash[Integer, Array[IR::Production]]
  queue = seed_terminal_values(values, terminal_value)

  @grammar.productions.each do |production|
    update_minimum(values, queue, production.lhs, yield(production, values)) if production.rhs.empty?
    production.rhs.uniq.each do |symbol_id|
      (dependents[symbol_id] ||= []) << production
    end
  end

  index = 0
  while index < queue.length
    dependents.fetch(queue.fetch(index), []).each do |production|
      update_minimum(values, queue, production.lhs, yield(production, values))
    end
    index += 1
  end

  values
end

#expand(start, remaining_expansions) ⇒ [ Array[String], Integer ]

RBS:

  • (IR::GrammarSymbol start, Integer remaining_expansions) -> [Array[String], Integer]

Parameters:

Returns:

  • ([ Array[String], Integer ]) 


131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
# File 'lib/ibex/samples.rb', line 131

def expand(start, remaining_expansions)
  result = [] #: Array[String]
  work = [[start.id, 0, []]] #: Array[[Integer, Integer, Array[Integer]]]
  pending_minimum = minimum_cost!(start.id)

  while (entry = work.pop)
    if remaining_expansions.zero?
      raise Ibex::Error, "(samples):1:1: expansion limit of #{@max_expansions} steps exceeded"
    end

    remaining_expansions -= 1
    symbol_id, depth, path = entry
    pending_minimum -= minimum_cost!(symbol_id)
    symbol = @grammar.symbol_by_id(symbol_id) ||
             raise(Ibex::Error, "(samples):1:1: missing symbol #{symbol_id}")
    if symbol.terminal?
      result << symbol.name
      next
    end

    budget = @max_tokens - result.length - pending_minimum
    production = choose_production(symbol_id, budget, depth, path)
    production_path = (path + [production.id]).last(@path_length)
    @path_coverage[production_path] += 1
    pending_minimum += production_cost(production) ||
                       raise(Ibex::Error, "(samples):1:1: no bounded derivation for symbol #{symbol_id}")
    production.rhs.reverse_each { |child_id| work << [child_id, depth + 1, production_path] }
  end

  [result, remaining_expansions]
end

#generate(count: 1) ⇒ Array[Array[String]]

RBS:

  • (?count: Integer) -> Array[Array[String]]

Parameters:

  • count: (Integer) (defaults to: 1)

Returns:

  • (Array[Array[String]]) 


37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
# File 'lib/ibex/samples.rb', line 37

def generate(count: 1)
  raise ArgumentError, "count must be positive" unless count.positive?

  start = @grammar.symbol(@grammar.start) || raise(Ibex::Error, "(samples):1:1: missing start symbol")
  minimum = @minimum_costs.fetch(start.id, nil)
  raise Ibex::Error, "(samples):1:1: start symbol #{@grammar.start} derives no terminal sentence" unless minimum

  if minimum > @max_tokens
    raise Ibex::Error, "(samples):1:1: minimum sentence needs #{minimum} tokens; limit is #{@max_tokens}"
  end
  if count > @max_expansions
    raise Ibex::Error, "(samples):1:1: count #{count} exceeds expansion limit #{@max_expansions}"
  end

  remaining_expansions = @max_expansions
  Array.new(count) do
    sample, remaining_expansions = expand(start, remaining_expansions)
    sample
  end
end

#minimum_cost!(symbol_id) ⇒ Integer

RBS:

  • (Integer symbol_id) -> Integer

Parameters:

  • symbol_id (Integer)

Returns:

  • (Integer) 


200
201
202
203
 
# File 'lib/ibex/samples.rb', line 200

def minimum_cost!(symbol_id)
  @minimum_costs.fetch(symbol_id) ||
    raise(Ibex::Error, "(samples):1:1: no bounded derivation for symbol #{symbol_id}")
end

#minimum_height_productions(candidates) ⇒ Array[IR::Production]

RBS:

  • (Array[IR::Production] candidates) -> Array[IR::Production]

Parameters:

Returns:



189
190
191
192
 
# File 'lib/ibex/samples.rb', line 189

def minimum_height_productions(candidates)
  minimum = candidates.filter_map { |production| production_height(production) }.min
  candidates.select { |production| production_height(production) == minimum }
end

#path_count(path, production) ⇒ Integer

RBS:

  • (Array[Integer] path, IR::Production production) -> Integer

Parameters:

Returns:

  • (Integer) 


195
196
197
 
# File 'lib/ibex/samples.rb', line 195

def path_count(path, production)
  @path_coverage[(path + [production.id]).last(@path_length)]
end

#production_cost(production) ⇒ Integer?

RBS:

  • (IR::Production production) -> Integer?

Parameters:

Returns:

  • (Integer, nil) 


206
207
208
 
# File 'lib/ibex/samples.rb', line 206

def production_cost(production)
  resolved_rhs_values(production, @minimum_costs)&.sum
end

#production_height(production) ⇒ Integer?

RBS:

  • (IR::Production production) -> Integer?

Parameters:

Returns:

  • (Integer, nil) 


211
212
213
214
 
# File 'lib/ibex/samples.rb', line 211

def production_height(production)
  child_heights = resolved_rhs_values(production, @minimum_heights)
  child_heights && ((child_heights.max || 0) + 1)
end

#resolved_rhs_values(production, values) ⇒ Array[Integer]?

RBS:

  • (IR::Production production, Hash[Integer, Integer?] values) -> Array[Integer]?

Parameters:

Returns:

  • (Array[Integer], nil) 


123
124
125
126
127
128
 
# File 'lib/ibex/samples.rb', line 123

def resolved_rhs_values(production, values)
  rhs_values = production.rhs.map { |symbol_id| values.fetch(symbol_id) }
  return nil if rhs_values.any?(&:nil?)

  rhs_values.compact
end

#seed_terminal_values(values, terminal_value) ⇒ Array[Integer]

RBS:

  • (Hash[Integer, Integer?] values, Integer terminal_value) -> Array[Integer]

Parameters:

  • values (Hash[Integer, Integer?])
  • terminal_value (Integer)

Returns:

  • (Array[Integer]) 


102
103
104
105
106
107
108
109
 
# File 'lib/ibex/samples.rb', line 102

def seed_terminal_values(values, terminal_value)
  @grammar.symbols.filter_map do |symbol|
    next unless symbol.terminal? && !symbol.reserved

    values[symbol.id] = terminal_value
    symbol.id
  end
end

#update_minimum(values, queue, symbol_id, candidate) ⇒ void

This method returns an undefined value.

RBS:

  • (Hash[Integer, Integer?] values, Array[Integer] queue, Integer symbol_id, Integer? candidate) -> void

Parameters:

  • values (Hash[Integer, Integer?])
  • queue (Array[Integer])
  • symbol_id (Integer)
  • candidate (Integer, nil) 


112
113
114
115
116
117
118
119
120
 
# File 'lib/ibex/samples.rb', line 112

def update_minimum(values, queue, symbol_id, candidate)
  return unless candidate

  current = values.fetch(symbol_id)
  return if current && current <= candidate

  values[symbol_id] = candidate
  queue << symbol_id
end