Skip to content

Instantly share code, notes, and snippets.

@tociyuki tociyuki/secd.rb
Last active Dec 14, 2015

Embed
What would you like to do?
P. J. Landin's original SECD Machine simulator + RETURN control
#!/usr/bin/env ruby
# -*- coding: utf-8 -*-
# P. J. Landin, ``The mechanical evaluation of expressions'', 1964
# <http://comjnl.oxfordjournals.org/content/6/4/308.abstract>
require 'strscan'
module SECD
def self.run(string)
s, e, c, d = nil, nil, [parse(string), nil], nil
5000.times do
list(s, e, c, d)
return s.first if c.nil? and d.nil?
s, e, c, d = c.first.turn(s, e, c, d)
end
raise RuntimeError, 'too many iteration'
end
def self.list(s, e, c, d)
puts ' S ' + s.inspect
puts ' E ' + '#' + e.object_id.to_s + '=' + e.inspect
puts ' C ' + c.inspect
puts ' D ' + d.inspect
puts
end
class << (APPLY = Object.new)
def inspect() 'APPLY' end
def turn(s, e, c, d) s.first.jump(s, e, c, d) end
end
class << (RETURN = Object.new)
def inspect() 'RETURN' end
def turn(s, e, c, d) d.first.jump(s, e, c, d) end
end
class Expression
attr_reader :function, :argument
def initialize(lhs, rhs) @function, @argument = lhs, rhs end
def inspect() '(' + @function.inspect + ')(' + @argument.inspect + ')' end
# S E ((λx.exp)(arg) . C) D -> S E (arg exp APPLY . C) D
def turn(s, e, c, d)
[s, e, [self.argument, [self.function, [APPLY, c.last]]], d]
end
end
class Lambda
attr_reader :parameter, :expression
def initialize(v, e) @parameter, @expression = v, e end
def inspect() 'λ ' + @parameter.to_s + '.' + @expression.inspect end
# S E (λx.exp . C) D -> ((Closure x exp E) . S) E C D
def turn(s, e, c, d)
[[Closure.new(self.parameter, self.expression, e), s], e, c.last, d]
end
end
class Closure
attr_reader :parameter, :expression, :environment
def initialize(v, c, e)
@parameter, @expression, @environment = v, c, e
end
def inspect()
'{' + 'λ ' + @parameter.to_s + '.' + @expression.inspect \
+ ' #' + @environment.object_id.to_s + '#}'
end
# ((Closure x C' E') V . S) E (APPLY . C) D
# -> () ((x . V) . E') (C' . (RETURN)) ((Klosure S E C) . D)
def jump(s, e, c, d)
e1 = [[self.parameter, s.last.first], self.environment]
c1 = self.expression
[nil, e1, [c1, [RETURN, nil]], [Klosure.new(s.last.last, e, c.last), d]]
end
end
class Klosure
attr_reader :stack, :environment, :control
def initialize(s, e, c)
@stack, @environment, @control = s, e, c
end
def inspect()
'(%s #%d# %s)' % [@stack.inspect, @environment.object_id, @control.inspect]
end
# (V . S') E' (RETURN . C') ((Klosure S E C) . D) -> (V . S) E C D
def jump(s, e, c, d)
[[s.first, self.stack], self.environment, self.control, d.last]
end
end
class Constant
attr_reader :value
def initialize(x) @value = x end
def inspect() @value.to_s end
# S E (n . C) D -> (n . S) E C D
def turn(s, e, c, d)
[[self.value, s], e, c.last, d]
end
end
class Reference
attr_reader :name
def initialize(name) @name = name end
def inspect() @name.to_s end
# S (E' . ((x . v) . E")) (x . C) D -> (v . S) (E' . ((x . v) . E")) C D
def turn(s, e, c, d)
[[lookup(e), s], e, c.last, d]
end
def lookup(e)
while not e.nil?
return e.first.last if e.first.first == @name
e = e.last
end
croak RuntimeError, 'unbound variable' + @name.to_s
end
end
def self.parse(string)
scanner = StringScanner.new(string)
parsed = parse_expression(scanner)
unless scanner.eos?
raise SyntaxError, 'unexpected token ' + scanner.scan(/./).inspect
end
parsed
end
# expression -> primary !")" expression / primary
def self.parse_expression(scanner)
lhs = parse_primary(scanner)
while ! scanner.eos? && scanner.peek(1) != ')'
rhs = parse_primary(scanner)
lhs = Expression.new(lhs, rhs)
end
lhs
end
# primary -> "lambda" variable "." expression
# / variable / constant / "(" expression ")"
def self.parse_primary(scanner)
if scanner.scan(/(?:lambda|λ)[ ]*/)
unless scanner.scan(/([^\W\d]\w*)[ ]*/)
raise SyntaxError, 'expected lambda parameter'
end
parameter = scanner[1].intern
scanner.scan(/[.][ ]*/)
expression = parse_expression(scanner)
Lambda.new(parameter, expression)
elsif scanner.scan(/([^\W\d]\w*)[ ]*/)
Reference.new(scanner[1].intern)
elsif scanner.scan(/(\d+)[ ]*/)
Constant.new(scanner[1].to_i)
elsif scanner.scan(/[(][ ]*/)
parsed = parse_expression(scanner)
unless scanner.scan(/[)][ ]*/)
raise SyntaxError, 'expected right paren )'
end
parsed
else
raise SyntaxError, 'unexpected token ' + scanner.scan(/./).inspect
end
end
end
if __FILE__ == $0
p SECD.run('(λx.λy.x y)(λy.y)5')
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.