Class: Heist::Runtime::Stack

Inherits:
Array
  • Object
show all
Defined in:
lib/runtime/stack.rb

Overview

Stack is responsible for executing code by successively evaluating expressions. It provides fine-grained intermediate result inspection to support the Scheme notion of continuations, working with the Frame and Body classes to evaluate expressions and function bodies piece by piece. Using the Stack engine allows the creation of Continuation functions, which save the current state of the stack (i.e. the state of any unfinished expressions and function bodies) and allow it to be resumed at some later time.

Stack inherits from Array, and is a last-in-first-out structure: the next expression evaluated is always the last expression on the stack.

You should think of the Stack as an array of Frame objects that hold expressions and track their progress. For example, take the expression:

(+ (- (* 8 9) (/ 21 7)) 4)

Evaluating it involves evaluating each subexpression to fill in holes where we expect values; when all the holes in an expression have been filled, we can apply the resulting function to the arguments and get a value. Evaluating this expression causes the stack to evolve as follows, where STATE lists the expressions on the stack and [] represents a hole that is waiting for a value:

PUSH:  (+ (- (* 8 9) (/ 21 7)) 4)
STATE: ([] [] 4)

PUSH:  +
VALUE: #<procedure:+>
STATE: (#<procedure:+> [] 4)

PUSH:  (- (* 8 9) (/ 21 7))
STATE: (#<procedure:+> [] 4), ([] [] [])

PUSH:  -
VALUE: #<procedure:->
STATE: (#<procedure:+> [] 4), (#<procedure:-> [] [])

PUSH:  (* 8 9)
STATE: (#<procedure:+> [] 4), (#<procedure:-> [] []), ([] 8 9)

PUSH:  *
VALUE: #<procedure:*>
STATE: (#<procedure:+> [] 4), (#<procedure:-> [] []), (#<procedure:*> 8 9)

VALUE: 72
STATE: (#<procedure:+> [] 4), (#<procedure:-> 72 [])

PUSH:  (/ 21 7)
STATE: (#<procedure:+> [] 4), (#<procedure:-> 72 []), ([] 21 7)

PUSH:  /
VALUE: #<procedure:/>
STATE: (#<procedure:+> [] 4), (#<procedure:-> 72 []), (#<procedure:/> 21 7)

VALUE: 3
STATE: (#<procedure:+> [] 4), (#<procedure:-> 72 3)

VALUE: 69
STATE: (#<procedure:+> 69 4)

VALUE: 73

So we find that (+ (- (* 8 9) (/ 21 7)) 4) gives the value 73. Whenever a value is returned by a subexpression we must inspect it to see if a Continuation has been called. All this inspection of intermediate values takes time; if you don’t need full Continuation support, use the faster Stackless engine instead.

Instance Attribute Summary collapse

Instance Method Summary collapse

Instance Attribute Details

#value ⇒ Object

Returns the value of attribute value.



76
77
78
 
# File 'lib/runtime/stack.rb', line 76

def value
  @value
end

Instance Method Details

#<<(frame) ⇒ Object

Pushes a new Frame or Body onto the Stack and then executes the resulting code until the pushed frame returns a value, which is then returned.



81
82
83
84
 
# File 'lib/runtime/stack.rb', line 81

def <<(frame)
  super
  clear!(size - 1)
end

#clear!(limit = 0) ⇒ Object

Causes the stack to evaluate expressions in order to pop them off the stack, until it gets down to the size given by limit. The resulting value if returned after all necessary computations have been done, and if an error takes place at any point we empty the stack.



114
115
116
117
118
119
120
 
# File 'lib/runtime/stack.rb', line 114

def clear!(limit = 0)
  process! while size > limit
  @value
rescue Exception => ex
  restack!
  raise ex
end

#copy(keep_last = true) ⇒ Object

Creates and returns a copy of the stack, which represents the current computational state: any unfinished expressions and function bodies are stored in the stack. Pass false to discard the final frame, which will typically be a call to (call/cc) when creating a Continuation.



91
92
93
94
95
96
97
98
 
# File 'lib/runtime/stack.rb', line 91

def copy(keep_last = true)
  copy = self.class.new
  range = keep_last ? 0..-1 : 0...-1
  self[range].each do |frame|
    copy[copy.size] = frame.clone
  end
  copy
end

#fill!(subexpr, value) ⇒ Object

Fills a hole in the final Frame on the Stack by replacing the given epxression subexpr with the given value. If the value is a Frame, this frame is pushed onto the stack rather than filling a hole in the previous frame.



104
105
106
107
108
 
# File 'lib/runtime/stack.rb', line 104

def fill!(subexpr, value)
  return self[size] = value if Frame === value
  return @value = value if empty?
  last.fill!(subexpr, value)
end