Class: MiniKraken::Core::Context

Inherits:
Object
  • Object
show all
Defined in:
lib/mini_kraken/core/context.rb

Overview

The data structure that provides the information required at runtime to determine a MiniKraken computation. One can think of the context object as a container of the symbol table and the blackboard. The symbol table keeps tracks of the different scopes involved in when MiniKraken is executing and the blackboard keeps the progress towards the achievement (or not) of the provided goals.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Context

Initialize the context to a blank structure



43
44
45
46
47
48
49
 
# File 'lib/mini_kraken/core/context.rb', line 43

def initialize
  @vars2cv = {}
  @cv2vars = {}
  @symbol_table = SymbolTable.new
  @blackboard = Blackboard.new
  clear_ranking
end

Instance Attribute Details

#blackboard ⇒ Core::Blackboard (readonly)

Returns Holds variable bindings and backtrack points.

Returns:



32
33
34
 
# File 'lib/mini_kraken/core/context.rb', line 32

def blackboard
  @blackboard
end

#cv2vars ⇒ Hash{String => Array<String>} (readonly)

An inverse mapping from a combining variable i_name to the fused variables i_name

Returns:

  • (Hash{String => Array<String>}) 


26
27
28
 
# File 'lib/mini_kraken/core/context.rb', line 26

def cv2vars
  @cv2vars
end

#ranking ⇒ Hash{String => Integer} (readonly)

Variables that remain unbound in a solution, are given a rank number. This rank number is used when variable values must be displayed. Since an unbound variable can take any value, the special notation ‘_’ + rank number is used to represent this state . The Reasoned Schemer book calls these variable as “reified”.

Returns:

  • (Hash{String => Integer}) 


40
41
42
 
# File 'lib/mini_kraken/core/context.rb', line 40

def ranking
  @ranking
end

#symbol_table ⇒ Core::SymbolTable (readonly)

Returns The MiniKraken symbol table.

Returns:



29
30
31
 
# File 'lib/mini_kraken/core/context.rb', line 29

def symbol_table
  @symbol_table
end

Instance Method Details

#add_substitution_for(iName, theSubstitutions) ⇒ Object

Update the provided substitutions Hash. If the given variable is dependent on other variables, then the substitution is updated recursively.

Parameters:

  • iName (String) —

    internal name of a logival variable

  • theSubstitutions (Hash {String => Association}) 


289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
 
# File 'lib/mini_kraken/core/context.rb', line 289

def add_substitution_for(iName, theSubstitutions)
  return if theSubstitutions.include? iName # Work already done...

  i_name = blackboard.fused?(iName) ? blackboard.vars2cv[iName] : iName
  assocs = blackboard.associations_for(i_name, true)
  assocs.delete_if { |e| e.kind_of?(Core::Fusion) }

  if assocs.empty?
    theSubstitutions[iName] = nil # Unbound variable
    return
  end
  # TODO: cover cases of multiple associations
  a = assocs.first
  theSubstitutions[iName] = a
  a.dependencies(self).each do |i_nm|
    # Recursive call!
    add_substitution_for(i_nm, theSubstitutions)
  end
end

#add_vars(var_names) ⇒ Object

Add one or more logical variable to the current scope

Parameters:

  • var_names (String, Array<String>) —

    one or more variable names



86
87
88
89
 
# File 'lib/mini_kraken/core/context.rb', line 86

def add_vars(var_names)
  vnames = var_names.kind_of?(String) ? [var_names] : var_names
  vnames.each { |nm| insert(LogVar.new(nm)) }
end

#associate(aName, aValue, aScope = nil) ⇒ Object

Build an assocation and enqueue it.

Parameters:

  • aName (String, #name) —

    User-friendly name

  • aValue (Core::Term)
  • aScope (Core::Scope, NilClass) (defaults to: nil) 


173
174
175
176
177
178
179
180
181
182
 
# File 'lib/mini_kraken/core/context.rb', line 173

def associate(aName, aValue, aScope = nil)
  name = aName.kind_of?(String) ? aName : aName.name
  if aScope
    raise NotImplementedError
  else
    vr = symbol_table.lookup(name)
    as = Association.new(blackboard.relevant_i_name(vr.i_name), aValue)
    enqueue_association(as)
  end
end

#associations_for(aName, aScope = nil) ⇒ Array<Core::Association>

Retrieve the association(s) for the variable with given name By default, the variable is assumed to belong to top-level scope.

Parameters:

  • aName (String) —

    User-friendly name of the logical variable

  • aScope (Core::Scope, NilClass) (defaults to: nil)

Returns:



189
190
191
192
193
194
195
196
197
198
199
 
# File 'lib/mini_kraken/core/context.rb', line 189

def associations_for(aName, aScope = nil)
  unless aName.kind_of?(String)
    raise StandardError, "Invalid argument #{aName}"
  end
  if aScope
    raise NotImplementedError
  else
    vr = symbol_table.lookup(aName)
    blackboard.associations_for(vr.i_name, true)
  end
end

#build_solution ⇒ Object

Returns a Hash with pairs of the form:

{ String => Association }, or
{ String => AnyValue }



242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
 
# File 'lib/mini_kraken/core/context.rb', line 242

def build_solution
  solution = {}
  return solution if failure?

  substitutions = {}

  # Fill in substitutions hash by starting with root variables
  symbol_table.root.defns.each_pair do |_nm, item|
    next unless item.kind_of?(LogVar)

    add_substitution_for(item.i_name, substitutions)
  end
  # require 'debug'
  handle_unbound_vars(substitutions)

  # Copy the needed associations by expanding the substitutions
  symbol_table.root.defns.each_pair do |_nm, item|
    next unless item.kind_of?(LogVar)

    next if item.name =~ /[0-9a-f]{8}-[0-9a-f]{4}-[0-9a-f]{4}-[0-9a-f]{4}-[0-9a-f]{12}/

    i_name = item.i_name
    solution[item.name] = expand_value_of(i_name, substitutions)
  end

  solution
end

#enqueue_association(anAssociation, aScope = nil) ⇒ Object

Add the given association to the association queue

Parameters:



161
162
163
164
165
166
167
 
# File 'lib/mini_kraken/core/context.rb', line 161

def enqueue_association(anAssociation, aScope = nil)
  if aScope
    raise NotImplementedError
  else
    blackboard.enqueue_association(anAssociation)
  end
end

#enter_scope(aScope) ⇒ Object

Set the provided scope as the current one

Parameters:



100
101
102
103
104
 
# File 'lib/mini_kraken/core/context.rb', line 100

def enter_scope(aScope)
  # puts __callee__
  symbol_table.enter_scope(aScope)
  blackboard.enter_scope
end

#expand_value_of(iName, theSubstitutions) ⇒ Object 



337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
 
# File 'lib/mini_kraken/core/context.rb', line 337

def expand_value_of(iName, theSubstitutions)
  replacement = theSubstitutions[iName]
  return replacement if replacement.kind_of?(AnyValue)

  return replacement.value if replacement.dependencies(self).empty?

  value_to_expand = replacement.value
  expanded = nil

  case value_to_expand
    when LogVarRef
      expanded = expand_value_of(value_to_expand.i_name, theSubstitutions)
    when Composite::ConsCell
      expanded = value_to_expand.expand(self, theSubstitutions)
  end

  expanded
end

#failed! ⇒ Core::Context

Notification that the current goal failed.

Returns:



53
54
55
56
 
# File 'lib/mini_kraken/core/context.rb', line 53

def failed!
  blackboard.failed!
  self
end

#failure? ⇒ Boolean

Does the latest result in the context represent a failure?

Returns:

  • (Boolean) —

    true if failure, false otherwise



67
68
69
 
# File 'lib/mini_kraken/core/context.rb', line 67

def failure?
  blackboard.failure?
end

#fuse(names) ⇒ Object

Two or more variables have to be fused.

- Create a new (combining) variable
- Create a fusion object

Parameters:

  • names (Array<String>) —

    Array of user-friendly names of variables to fuse.



205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
 
# File 'lib/mini_kraken/core/context.rb', line 205

def fuse(names)
  return if names.size <= 1

  vars = names.map { |nm| symbol_table.lookup(nm) }
  i_names = vars.map(&:i_name)

  # Create a new combining variable
  new_name = fusion_name
  cv_i_name = insert(LogVar.new(new_name))

  # Update the mappings
  @cv2vars[cv_i_name] = i_names.dup
  i_names.each { |i_nm| @vars2cv[i_nm] = cv_i_name }

  # Add fusion record to blackboard
  fs = Fusion.new(cv_i_name, i_names)
  blackboard.enqueue_fusion(fs)
end

#handle_unbound_vars(theSubstitutions) ⇒ Object 



309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
 
# File 'lib/mini_kraken/core/context.rb', line 309

def handle_unbound_vars(theSubstitutions)
  relevant_vars = symbol_table.all_variables.select do |vr|
    i_name = vr.i_name
    included = theSubstitutions.include? i_name
    included & theSubstitutions[i_name].nil?
  end

  rank_number = 0
  relevant_vars.each do |vr|
    i_name = vr.i_name
    if blackboard.fused?(i_name)
      cv_i_name = blackboard.vars2cv[i_name]
      fused = cv2vars[cv_i_name]
      fused << cv_i_name # TODO: delete this line
      already_ranked = fused.find { |i_nm| !theSubstitutions[i_nm].nil? }
      if already_ranked
        theSubstitutions[i_name] = theSubstitutions[already_ranked]
      else
        theSubstitutions[i_name] = AnyValue.new(rank_number)
        rank_number += 1
      end
    else
      theSubstitutions[i_name] = AnyValue.new(rank_number)
      rank_number += 1
    end
  end
end

#insert(anEntry) ⇒ String

Add an entry in the symbol table

Parameters:

Returns:

  • (String) —

    Internal name of the entry



80
81
82
 
# File 'lib/mini_kraken/core/context.rb', line 80

def insert(anEntry)
  symbol_table.insert(anEntry)
end

#leave_scope ⇒ Object

Pop the current scope and make its parent the current one



107
108
109
110
111
112
113
114
115
116
117
118
119
120
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
150
151
152
153
154
155
156
 
# File 'lib/mini_kraken/core/context.rb', line 107

def leave_scope
  # puts __callee__
  current_scope = symbol_table.current_scope
  parent_scope = current_scope.parent
  return unless parent_scope

  # Retrieve all i_names from current scope
  i_name_set = Set.new(current_scope.defns.values.map(&:i_name))

  # Remove all associations from queue until the scope's bookmark
  items = blackboard.leave_scope
  curr_asc, ancestor_asc = items.partition do |a|
    i_name_set.include? a.i_name
  end
  vars_to_keep = Set.new

  ancestor_asc.each do |assoc|
    if assoc.dependencies(self).intersect?(i_name_set)
      dependents = assoc.dependencies(self).intersection(i_name_set)
      vars_to_keep.merge(dependents)
    end
    enqueue_association(assoc, nil) # parent_scope
  end

  assocs_to_keep = []

  unless vars_to_keep.empty?
    loop do
      to_keep, to_consider = curr_asc.partition do |a|
        vars_to_keep.include? a.i_name
      end
      break if to_keep.empty?

      to_keep.each do |a|
        vars_to_keep.merge(a.dependencies(self).intersection(i_name_set))
      end
      assocs_to_keep.concat(to_keep)
      curr_asc = to_consider
    end
  end
  symbol_table.leave_scope

  vars_to_keep.each do |i_name|
    v = LogVar.new(i_name)
    v.suffix = ''
    symbol_table.insert(v)
  end

  assocs_to_keep.each { |a| blackboard.enqueue_association(a) }
end

#lookup(aName) ⇒ Core::LogVar

Search for the object with the given name

Parameters:

  • aName (String)

Returns:



94
95
96
 
# File 'lib/mini_kraken/core/context.rb', line 94

def lookup(aName)
   symbol_table.lookup(aName)
end

#next_alternative ⇒ Object 



229
230
231
232
 
# File 'lib/mini_kraken/core/context.rb', line 229

def next_alternative
  # puts __callee__
  blackboard.next_alternative
end

#place_bt_point ⇒ Object 



224
225
226
227
 
# File 'lib/mini_kraken/core/context.rb', line 224

def place_bt_point
  # puts __callee__
  blackboard.place_bt_point
end

#retract_bt_point ⇒ Object 



234
235
236
237
 
# File 'lib/mini_kraken/core/context.rb', line 234

def retract_bt_point
  # puts __callee__
  blackboard.retract_bt_point
end

#succeeded! ⇒ Core::Context

Notification that the current goal succeeded.

Returns:



60
61
62
63
 
# File 'lib/mini_kraken/core/context.rb', line 60

def succeeded!
  blackboard.succeeded!
  self
end

#success? ⇒ Boolean

Does the latest result in the context represent success?

Returns:

  • (Boolean) —

    true if success, false otherwise



73
74
75
 
# File 'lib/mini_kraken/core/context.rb', line 73

def success?
  blackboard.success?
end