Class: Heist::Runtime::Cons

Inherits:
Object
  • Object
show all
Includes:
Enumerable, Expression
Defined in:
lib/heist/runtime/data/cons.rb

Overview

Cons is the basic data structure element in Scheme. A Cons is an object with two pointers to other objects, the pointers being called the car and the cdr. You can typically think of this type of object as representing a pair of values, though not all Cons objects are pairs according to the (pair?) procedure; specifically NULL is not considered a pair.

Cons objects can be joined together to form lists; a list is either the empty list or a Cons whose cdr is a list. That is, a list is chain of Cons pairs joined by their cdr fields, whose car fields hold the elements of the list. A list is considered ‘proper’ if its final Cons is NULL, and improper otherwise. Some examples:

Proper list: (1 2 3)    Improper list: (1 2 3 . 4)

      .                         .                    . = cons
     / \                       / \                   / = car
    1   .                     1   .                  \ = cdr
       / \                       / \                () = NULL
      2   .                     2   .
         / \                       / \ 
        3  ()                     3   4

This also illustrates the relationship between dotted pairs and Cons cells; '(a . b) is equivalent to (cons 'a 'b), and the list (1 2 3) is more fully written as (1 . (2 . (3 . ()))).

Cons objects are Enumerable, though always keep in mind that a Cons does not ‘contain’ a whole list, it contains one value and a pointer to the rest of the list. Iterating on a Cons involves walking this object graph.

Constant Summary collapse

NULL =

NULL is a special Cons instance representing the empty list, which is used as a nil value in Scheme. The empty list is a singleton: there is only ever one empty list in memory, and the Scheme expressions '() and (list) always return the same object. NULL is frozen, and its car and cdr are pointers back to itself.

self.new
ACCESSORS =

An array of all the c+r functions supported by Heist

cadr_combos
SHORTHANDS =

For stringifying purposes, we need an inverted copy of the table of quoting shorthand symbols

Scheme::SHORTHANDS.invert

Instance Attribute Summary collapse

Attributes included from Expression

#parent

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Expression

#eval, #replace

Constructor Details

#initialize(car = nil, cdr = nil) ⇒ Cons

A Cons is initialized using a car and a cdr value.



102
103
104
105
 
# File 'lib/heist/runtime/data/cons.rb', line 102

def initialize(car = nil, cdr = nil)
  self.car = car
  self.cdr = cdr
end

Instance Attribute Details

#car ⇒ Object

Returns the value of attribute car.



40
41
42
 
# File 'lib/heist/runtime/data/cons.rb', line 40

def car
  @car
end

#cdr ⇒ Object

Returns the value of attribute cdr.



40
41
42
 
# File 'lib/heist/runtime/data/cons.rb', line 40

def cdr
  @cdr
end

Class Method Details

.construct(enum, linking = false, &block) ⇒ Object Also known as: []

Creates a new list from the elements of the enumerable object enum, and returns the Cons that forms the head of the list. If enum is empty, NULL is returned. construct optionally takes a block that can be used to transform each value as the list is constructed:

Cons.construct([1,2,3,4]) { |x| x*x }
#=> (1 4 9 16)

The method also takes an optional second parameter linking, which, if set to true, makes each car element aware of the Cons that holds it. This is used when inlining macro expansions, where expressions need to replace themselves in their parent expression.

Note that this method copies improper lists correctly, though iteration over a Cons list does not include the tail value.



84
85
86
87
88
89
90
91
92
93
94
95
96
97
 
# File 'lib/heist/runtime/data/cons.rb', line 84

def construct(enum, linking = false, &block)
  return NULL if enum.nil?
  root, last = nil, nil
  enum.each do |value|
    value = block.call(value) if block_given?
    pair = self.new(value)
    pair.hosts(value) if linking
    root ||= pair
    last.cdr = pair if last
    last = pair.tail
  end
  last.cdr = enum.tail.cdr if last and Cons === enum
  root || NULL
end

Instance Method Details

#==(other) ⇒ Object

Returns true iff other is equal to the receiver, that is to say that other is a Cons with the same car and cdr as the receiving Cons.



182
183
184
185
186
 
# File 'lib/heist/runtime/data/cons.rb', line 182

def ==(other)
  return false unless Cons === other
  return false if NULL == other
  @car == other.car and @cdr == other.cdr
end

#clone(&block) ⇒ Object

Creates and returns a copy of the Cons list, taking an optional mapping block (see construct).



149
150
151
 
# File 'lib/heist/runtime/data/cons.rb', line 149

def clone(&block)
  Cons.construct(self, &block)
end

#each ⇒ Object Also known as: tail

Iterates over each Cons in a list, yielding the car value for each Cons. Returns the final Cons in the list, from where we can inspect the tail’s cdr to see if the list if proper or not. The block is optional and the method is aliased as tail, so to get the tail value of an improper list you’d call list.tail.cdr.



158
159
160
161
162
163
164
165
166
 
# File 'lib/heist/runtime/data/cons.rb', line 158

def each
  pair, tail = self, NULL
  while Cons === pair and not pair.null?
    yield(pair.car) if block_given?
    tail = pair
    pair = pair.cdr
  end
  tail
end

#force! ⇒ Object

If the receiving list contains Binding objects, said objects are forced to evaluate themselves to populate the list.



190
191
192
193
194
195
196
197
198
 
# File 'lib/heist/runtime/data/cons.rb', line 190

def force!
  return self unless Binding === @car
  pair = self
  while not pair.null?
    pair.car = pair.car.force!
    pair = pair.cdr
  end
  self
end

#freeze! ⇒ Object

Recursively freezes the Cons and any conses it points to. This is used to prevent quoted list constants from being modified since they are part of the parse tree: quoting a list does not allocate a new object so changing a quoted list would have undesirable side effects on any other references to the list.



134
135
136
137
138
 
# File 'lib/heist/runtime/data/cons.rb', line 134

def freeze!
  return if null?
  [@car, @cdr].each { |slot| slot.freeze! if slot.respond_to?(:freeze!) }
  freeze
end

#hosts(value) ⇒ Object

Sets the parent pair of value to the receiver. Some car values need a reference back to their containing Cons for concerns such as macro expansion inlining.



143
144
145
 
# File 'lib/heist/runtime/data/cons.rb', line 143

def hosts(value)
  value.parent = self if Expression === value and value != NULL
end

#length ⇒ Object Also known as: size

Returns the length of the list whose head is the receiving Cons. If the list is improper an exception is raised.

Raises:



171
172
173
174
175
176
 
# File 'lib/heist/runtime/data/cons.rb', line 171

def length
  size = 0
  tail = each { |value| size += 1 }
  raise TypeError.new("Cannot get the length of improper list #{self}") unless tail.cdr == NULL
  size
end

#list? ⇒ Boolean

Returns true iff the receiving Cons is the head of a proper list.

Returns:

  • (Boolean) 


201
202
 
# File 'lib/heist/runtime/data/cons.rb', line 201

def list?
tail.cdr == NULL; end

#null? ⇒ Boolean

Returns true iff the receiving Cons is the empty list.

Returns:

  • (Boolean) 


209
210
 
# File 'lib/heist/runtime/data/cons.rb', line 209

def null?
self == NULL; end

#pair? ⇒ Boolean

Returns true iff the receiving Cons is a valid pair.

Returns:

  • (Boolean) 


205
206
 
# File 'lib/heist/runtime/data/cons.rb', line 205

def pair?
not null?; end

#to_a(deep = false) ⇒ Object

Returns an array representation of the list. If deep is true, the array conversion is performed recursively.



214
215
216
 
# File 'lib/heist/runtime/data/cons.rb', line 214

def to_a(deep = false)
  map { |cell| deep && Cons === cell ? cell.to_a : cell }
end

#to_ruby ⇒ Object

Returns a pure Ruby representation of the list, with any Heist specific objects converted to basic Ruby equivalents.



220
221
222
223
224
225
226
227
228
229
230
 
# File 'lib/heist/runtime/data/cons.rb', line 220

def to_ruby
  members = []
  tail = each do |cell|
    members << (cell.respond_to?(:to_ruby) ? cell.to_ruby : cell)
  end
  if NULL != tail.cdr
    members << RubyParser::DOT
    members << (tail.cdr.respond_to?(:to_ruby) ? tail.cdr.to_ruby : tail.cdr)
  end
  members
end

#to_s ⇒ Object Also known as: inspect

Returns a Scheme-style string representation of the list.



233
234
235
236
237
238
239
240
241
242
 
# File 'lib/heist/runtime/data/cons.rb', line 233

def to_s
  strings = []
  if Identifier === @car and SHORTHANDS.has_key?(@car.to_s) and list? and length == 2
    SHORTHANDS[@car.to_s] + Heist.stringify(@cdr.car)
  else
    tail = each { |value| strings << Heist.stringify(value) }.cdr
    '(' + (strings * ' ') +
          (tail == NULL ? '' : ' . ' + Heist.stringify(tail)) + ')'
  end
end