Class: MiniKraken::Composite::ConsCell

Inherits:
CompositeTerm show all
Defined in:
lib/mini_kraken/composite/cons_cell.rb

Overview

In Lisp dialects, a cons cell (or a pair) is a data structure with two fields named car and cdr (for historical reasons). Cons cells are the key ingredient for building lists in Lisp. A cons cell can be depicted as a box with two parts, car and cdr each containing a reference to another object.

+-----------+
| car | cdr |
+--|-----|--+
   |     |
   V     V
  obj1  obj2

The list (1 2 3) can be constructed as follows:

+-----------+
| car | cdr |
+--|-----|--+
   |     |
   V     V
   1  +-----------+
      | car | cdr |
      +--|-----|--+
         |     |
         V     V
         2  +-----------+
            | car | cdr |
            +--|-----|--+
               |     |
               V     V
               3    nil

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(obj1, obj2 = NullList) ⇒ ConsCell

Construct a new conscell whose car and cdr are obj1 and obj2. In Scheme, a list is terminated by a null list. In MiniKraken, a list is terminated by a Ruby nil. Therefore, when setting the cdr to the null list, the implementation will silently replace the null list by a nil.

Parameters:

  • obj1 (Term, NilClass)
  • obj2 (Term, NilClass) (defaults to: NullList) 


55
56
57
58
59
60
61
62
63
 
# File 'lib/mini_kraken/composite/cons_cell.rb', line 55

def initialize(obj1, obj2 = NullList)
  super()
  @car = obj1
  if obj2.kind_of?(ConsCell) && obj2.null?
    @cdr = NullList
  else
    @cdr = obj2
  end
end

Instance Attribute Details

#car ⇒ Term (readonly)

The first slot in a ConsCell

Returns:

  • (Term) 


42
43
44
 
# File 'lib/mini_kraken/composite/cons_cell.rb', line 42

def car
  @car
end

#cdr ⇒ Term (readonly)

The second slot in a ConsCell

Returns:

  • (Term) 


46
47
48
 
# File 'lib/mini_kraken/composite/cons_cell.rb', line 46

def cdr
  @cdr
end

Class Method Details

.null ⇒ ConsCell

Specialized constructor for null list.

Returns:



67
68
69
 
# File 'lib/mini_kraken/composite/cons_cell.rb', line 67

def self.null
  new(nil, nil)
end

Instance Method Details

#==(other) ⇒ Boolean

Return true if car and cdr fields have the same values as the other ConsCell.

Parameters:

Returns:

  • (Boolean) 


138
139
140
141
142
 
# File 'lib/mini_kraken/composite/cons_cell.rb', line 138

def ==(other)
  return false unless other.respond_to?(:car)

  (car == other.car) && (cdr == other.cdr)
end

#children ⇒ Object 



100
101
102
 
# File 'lib/mini_kraken/composite/cons_cell.rb', line 100

def children
  [car, cdr]
end

#dependencies(ctx) ⇒ Set<String>

Return the list of variable (i_names) that this term depends on. For a variable reference, it will return the i_names of its variable

Parameters:

Returns:

  • (Set<String>) —

    A set of i_names



174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
 
# File 'lib/mini_kraken/composite/cons_cell.rb', line 174

def dependencies(ctx)
  deps = []
  visitor = ConsCellVisitor.df_visitor(self)
  skip_children = false
  loop do
    side, cell = visitor.resume(skip_children)
    if cell.kind_of?(Core::LogVarRef)
      deps << ctx.lookup(cell.name).i_name
      skip_children = true
    else
      skip_children = false
    end
    break if side == :stop
  end

  Set.new(deps)
end

#dup_cond(substitutions) ⇒ ConsCell

File ‘lib/mini_kraken/atomic/atomic_term.rb’, line 91 Make a copy of self with all the variable reference being replaced by the corresponding value in the Hash.

Parameters:

  • substitutions (Hash {String => Term})

Returns:



251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
 
# File 'lib/mini_kraken/composite/cons_cell.rb', line 251

def dup_cond(substitutions)
  head = curr_cell = nil
  path = []

  visitor = ConsCellVisitor.df_visitor(self) # Breadth-first!
  skip_children = false

  loop do
    side, cell = visitor.resume(skip_children)
    # next if cell == self
    break if side == :stop

    if cell.kind_of?(ConsCell)
      new_cell = ConsCell.null
      if curr_cell
        curr_cell.set!(side, new_cell)
        path.push(curr_cell)
      end
      curr_cell = new_cell
      head ||= new_cell

    else
      duplicate = cell.nil? ? nil : cell.dup_cond(substitutions)
      curr_cell.set!(side, duplicate)
      curr_cell = path.pop if side == :cdr
    end
  end

  head
end

#eql?(other) ⇒ Boolean

Test for type and data value equality.

Parameters:

Returns:

  • (Boolean) 


147
148
149
 
# File 'lib/mini_kraken/composite/cons_cell.rb', line 147

def eql?(other)
  (self.class == other.class) && car.eql?(other.car) && cdr.eql?(other.cdr)
end

#expand(ctx, theSubstitutions) ⇒ Object

Parameters:

  • ctx (Core::Context)
  • theSubstitutions (Hash{String => Association}) 


194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
 
# File 'lib/mini_kraken/composite/cons_cell.rb', line 194

def expand(ctx, theSubstitutions)
  head = curr_cell = nil
  path = []

  visitor = ConsCellVisitor.df_visitor(self)
  skip_children = false

  loop do
    side, cell = visitor.resume(skip_children)
    # next if cell == self
    break if side == :stop

    case cell
      when ConsCell
        new_cell = ConsCell.null
        if curr_cell
          curr_cell.set!(side, new_cell)
          path.push(curr_cell) unless side == :cdr
        else
          head = new_cell                
          path.push(new_cell)
        end
        if side == :cdr && cell.null?
          curr_cell = path.pop
        else
          curr_cell = new_cell
        end

      when Core::LogVarRef
        # Is this robust?
        if cell.i_name
          i_name = cell.i_name
        else
          i_name = ctx.symbol_table.lookup(cell.name).i_name
        end
        expanded = ctx.expand_value_of(i_name, theSubstitutions)
        curr_cell.set!(side, expanded)
        curr_cell = path.pop if side == :cdr
      else
        curr_cell.set!(side, cell)
        curr_cell = path.pop if side == :cdr
    end
  end

  head
end

#floating?(ctx) ⇒ Boolean

Does the composite have a variable that is itself floating?

Returns:

  • (Boolean) 


121
122
123
 
# File 'lib/mini_kraken/composite/cons_cell.rb', line 121

def floating?(ctx)
  !pinned?(ctx)
end

#null? ⇒ Boolean

Return true if it is an empty list, otherwise false. A list is empty, when both car and cdr fields are nil.

Returns:

  • (Boolean) 


107
108
109
 
# File 'lib/mini_kraken/composite/cons_cell.rb', line 107

def null?
  car.nil? && cdr.nil?
end

#pinned?(ctx) ⇒ Boolean

Does the cons cell have a definite value?

Returns:

  • (Boolean) 


127
128
129
130
131
132
 
# File 'lib/mini_kraken/composite/cons_cell.rb', line 127

def pinned?(ctx)
  pinned_car = car.nil? || car.pinned?(ctx)
  pinned_cdr = cdr.nil? || cdr.pinned?(ctx)

  pinned_car && pinned_cdr
end

#quote(anEnv) ⇒ ConsCell

Return a data object that is a copy of the ConsCell

Parameters:

  • anEnv (Core::Environment)

Returns:



154
155
156
157
158
159
160
 
# File 'lib/mini_kraken/composite/cons_cell.rb', line 154

def quote(anEnv)
  return self if null?

  new_car = car.nil? ? nil : car.quote(anEnv)
  new_cdr = cdr.nil? ? nil : cdr.quote(anEnv)
  ConsCell.new(new_car, new_cdr)
end

#set!(member, element) ⇒ Object

Set one element of the pair

Parameters:

  • member (Symbol)
  • element (Term) 


74
75
76
77
78
79
80
81
82
83
 
# File 'lib/mini_kraken/composite/cons_cell.rb', line 74

def set!(member, element)
  case member
    when :car
      set_car!(element)
    when :cdr
      set_cdr!(element)
    else
      raise StandardError, "Undefined cons cell member #{member}"
    end
end

#set_car!(element) ⇒ Object

Change the car of ConsCell to ‘element’. Analogue of set-car! procedure in Scheme.

Parameters:

  • element (Term) 


88
89
90
91
 
# File 'lib/mini_kraken/composite/cons_cell.rb', line 88

def set_car!(element)
  @cdr = NullList if null?
  @car = element
end

#set_cdr!(element) ⇒ Object

Change the cdr of ConsCell to ‘element’. Analogue of set-cdr! procedure in Scheme.

Parameters:

  • element (Term) 


96
97
98
 
# File 'lib/mini_kraken/composite/cons_cell.rb', line 96

def set_cdr!(element)
  @cdr = element
end

#to_s ⇒ String

Use the list notation from Lisp as a text representation.

Returns:

  • (String) 


164
165
166
167
168
 
# File 'lib/mini_kraken/composite/cons_cell.rb', line 164

def to_s
  return '()' if null?

  "(#{pair_to_s})"
end

#unbound?(_ctx) ⇒ FalseClass

Is the receiver an unbound variable? By definition, a composite isn’t a variable.

Parameters:

Returns:

  • (FalseClass) 


115
116
117
 
# File 'lib/mini_kraken/composite/cons_cell.rb', line 115

def unbound?(_ctx)
  false
end