Class: RazyK::VM

Inherits:
Object
  • Object
show all
Defined in:
lib/razyk/vm.rb

Defined Under Namespace

Classes: StackUnderflow

Instance Method Summary collapse

Constructor Details

#initialize(tree, input = $stdin, output = $stdout, recursive: false, statistics: nil) ⇒ VM

Returns a new instance of VM.



15
16
17
18
19
20
21
22
 
# File 'lib/razyk/vm.rb', line 15

def initialize(tree, input=$stdin, output=$stdout, recursive: false, statistics: nil)
  @root = Node.new(:root, [], [tree])
  @generator = nil
  @input = input
  @output = output
  @recursive = recursive
  @statistics = statistics
end

Instance Method Details

#evaluate(root, &blk) ⇒ Object 



58
59
60
61
62
63
64
65
66
67
68
69
 
# File 'lib/razyk/vm.rb', line 58

def evaluate(root, &blk)
  stack = [root]
  until step(stack, &blk).nil?
    if blk
      blk.call(self)
    end
  end
  if @recursive and stack.last.is_a?(Pair)
    evaluate(stack.last.cdr, &blk)
  end
  nil
end

#pop_pairs(stack, num) ⇒ Object

Pop num of Pairs nodes from stack. Each Pair node is destroyed if it isn’t referenced from other parent node Return value is [<root Pair node for replace>, cdr1, cdr2, …]

Raises:



31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
# File 'lib/razyk/vm.rb', line 31

def pop_pairs(stack, num)
  raise StackUnderflow if stack.size < num
  pairs = stack.pop(num)
  root = pairs.first
  root.cut_car if num <= 1
  cdrs = [ root.cut_cdr ]
  shared = false
  pairs.inject do |parent, child|
    parent.cut_car unless shared
    if child.from.size != 0
      shared = true
      cdrs.unshift(child.cdr)
    else
      cdrs.unshift(child.cut_cdr)
    end
    child
  end
  cdrs.unshift(root)
  cdrs
end

#reduce ⇒ Object 



195
196
197
198
 
# File 'lib/razyk/vm.rb', line 195

def reduce
  evaluate(self.tree) {|vm| return vm }
  nil
end

#replace_root(stack, old_root, new_root) ⇒ Object

replace old_root Pair with new_root Pair and push new_root to stack



53
54
55
56
 
# File 'lib/razyk/vm.rb', line 53

def replace_root(stack, old_root, new_root)
  old_root.replace(new_root)
  stack.push(new_root)
end

#run(&blk) ⇒ Object 



200
201
202
203
204
205
206
207
208
 
# File 'lib/razyk/vm.rb', line 200

def run(&blk)
  if @statistics
    @statistics[:started_at] = Time.now
  end
  evaluate(self.tree, &blk)
  if @statistics
    @statistics[:finished_at] = Time.now
  end
end

#step(stack, &blk) ⇒ Object 



71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
 
# File 'lib/razyk/vm.rb', line 71

def step(stack, &blk)
  return nil if stack.empty?
  @statistics[:count] += 1 if @statistics
  while stack.last.is_a?(Pair)
    stack.push(stack.last.car)
  end
  comb = stack.pop
  case comb.label
  when :I
    # (I x) -> x
    root, x = pop_pairs(stack, 1)
    replace_root(stack, root, x)
  when :K
    # (K x y) -> x
    root, x, y = pop_pairs(stack, 2)
    replace_root(stack, root, x)
  when :S
    # (S x y z) -> ((x z) (y z))
    root, x, y, z = pop_pairs(stack, 3)
    new_root = Pair.new(Pair.new(x, z), Pair.new(y, z))
    replace_root(stack, root, new_root)
  when :IOTA
    #  (IOTA x) -> ((x S) K)
    root, x = pop_pairs(stack, 1)
    new_root = Pair.new(Pair.new(x, :S), :K)
    replace_root(stack, root, new_root)
  when :CONS
    # (CONS a d f) -> (f a d)
    root, a, d, f = pop_pairs(stack, 3)
    new_root = Pair.new(Pair.new(f, a), d)
    replace_root(stack, root, new_root)
  when :IN
    # (IN f) -> (S (S I (K <CH>)) (K IN)) where <CH> is a byte from stdin
    ch = @input.getbyte
    if ch.nil?
      ch = 256
    end
    new_root = Node.list(Combinator.new(ch), terminator: Combinator.new(:IN))
    comb.replace(new_root)
    stack.push(new_root)
  when :CAR
    # (CAR x) -> (x K)       (CAR = (Lx.x TRUE), TRUE = (Lxy.x) = K)
    root, x = pop_pairs(stack, 1)
    new_root = Pair.new(x, :K)  # K means TRUE
    replace_root(stack, root, new_root)
  when :CDR
    # (CDR x) -> (x (K I))  (CDR = (Lx.x FALSE), FALSE = (Lxy.y) = (K I)
    root, x = pop_pairs(stack, 1)
    new_root = Pair.new(x, Pair.new(:K, :I)) # (K I) means FALSE
    replace_root(stack, root, new_root)
  when :OUT
    # (OUTPUT f) -> ((PUTC ((CAR f) INC <0>) (OUTPUT (CDR f)))
    root, f = pop_pairs(stack, 1)
    new_root = Pair.new(
                 Pair.new(:PUTC,
                   Pair.new(Pair.new(Pair.new(f, :K), :INC), 0)),
                 Pair.new(comb, # reuse :OUT combinator
                          Pair.new(f, Pair.new(:S, :K))))
    replace_root(stack, root, new_root)
  when :INC
    # (INC n) -> n+1 : increment church number
    raise StackUnderflow if stack.empty?
    evaluate(stack.last.cdr, &blk)
    root, n = pop_pairs(stack, 1)
    unless n.integer?
      begin
        msg = "argument of INC combinator is not a church number but #{n.inspect}"
      rescue
        msg = "argument of INC combinator is not a church number (too large combinator tree)"
      end
      raise msg
    end
    replace_root(stack, root, Combinator.new(n.integer + 1))
  when :PUTC
    # (PUTC x y) -> y : evaluate x and putchar it
    raise StackUnderflow if stack.size < 2
    x = stack.pop
    evaluate(x.cdr, &blk)
    unless x.cdr.integer?
      begin
        msg = "output is not church number but #{x.cdr.inspect}"
      rescue
        msg = "output is not church number (too large combinator tree)"
      end
      raise msg
    end
    num = x.cdr.integer
    if num >= 256
      if @output != $stdout and @output != STDOUT
        @output.close_write
      end
      return nil
    end
    @output.write([num].pack("C"))
    root = stack.pop
    y = root.cut_cdr
    replace_root(stack, root, y)
  else
    if comb.integer?
      # (<N> f x) -> x               (N == 0)
      #           -> (f (<N-1> f x)) (N > 0)
      root, f, x = pop_pairs(stack, 2)
      num = comb.integer
      if num == 0
        replace_root(stack, root, x)
      else
        # shortcut
        if f.label == :INC and x.integer?
          replace_root(stack, root, Combinator.new(num + x.integer))
        else
          dec_pair = Pair.new(Combinator.new(num-1), f)
          new_root = Pair.new(f, Pair.new(dec_pair, x))
          replace_root(stack, root, new_root)
        end
      end
    else # unknown combinator... treat as combinator without enough arguments
      raise StackUnderflow
    end
  end
  true
rescue StackUnderflow
  return nil
end

#tree ⇒ Object 



24
25
26
 
# File 'lib/razyk/vm.rb', line 24

def tree
  @root.to[0]
end