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) ⇒ Samples

Returns a new instance of Samples.

RBS:

  • (IR::Grammar grammar, ?seed: Integer, ?max_tokens: Integer, ?max_depth: Integer, ?max_expansions: 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) 


11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
# File 'lib/ibex/samples.rb', line 11

def initialize(grammar, seed: 0, max_tokens: 32, max_depth: 16, max_expansions: DEFAULT_MAX_EXPANSIONS)
  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?

  @grammar = grammar
  @random = Random.new(seed)
  @max_tokens = max_tokens
  @max_depth = max_depth
  @max_expansions = max_expansions
  @productions = grammar.productions.group_by(&:lhs)
  @minimum_costs = compute_minimum_costs
  @minimum_heights = compute_minimum_heights
end

Instance Method Details

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

RBS:

  • (Integer nonterminal_id, Integer budget, Integer depth) -> IR::Production

Parameters:

  • nonterminal_id (Integer)
  • budget (Integer)
  • depth (Integer)

Returns:



152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
 
# File 'lib/ibex/samples.rb', line 152

def choose_production(nonterminal_id, budget, depth)
  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?

  if depth >= @max_depth
    minimum = candidates.filter_map { |production| production_height(production) }.min
    candidates = candidates.select { |production| production_height(production) == minimum }
  end
  candidates.fetch(@random.rand(candidates.length))
end

#compute_minimum_costs ⇒ Hash[Integer, Integer?]

RBS:

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

Returns:

  • (Hash[Integer, Integer?]) 


51
52
53
54
55
56
 
# File 'lib/ibex/samples.rb', line 51

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?]) 


59
60
61
62
63
64
 
# File 'lib/ibex/samples.rb', line 59

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?]) 


68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
# File 'lib/ibex/samples.rb', line 68

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 ]) 


121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
 
# File 'lib/ibex/samples.rb', line 121

def expand(start, remaining_expansions)
  result = [] #: Array[String]
  work = [[start.id, 0]] #: Array[[Integer, 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 = 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)
    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] }
  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]]) 


27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/ibex/samples.rb', line 27

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) 


170
171
172
173
 
# File 'lib/ibex/samples.rb', line 170

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

#production_cost(production) ⇒ Integer?

RBS:

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

Parameters:

Returns:

  • (Integer, nil) 


176
177
178
 
# File 'lib/ibex/samples.rb', line 176

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) 


181
182
183
184
 
# File 'lib/ibex/samples.rb', line 181

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) 


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

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]) 


92
93
94
95
96
97
98
99
 
# File 'lib/ibex/samples.rb', line 92

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) 


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

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