lc.rb

require 'colorize'

class ParseError < Exception
end

class EOF < ParseError
end

class Stream < Struct.new :stream, :line, :col, :offset
    def self.of text
        self.new text, 1, 1, 0
    end

    def here
        stream[offset]
    end
    
    def attempt &block
        backup = dup
        begin
            self.instance_eval &block
        rescue ParseError => e
            self.line = backup.line
            self.col = backup.col
            self.offset = backup.offset
            nil
        end
    end

    def some &block
        res  = self.instance_eval &block
        rest = many(&block)
        [res] + rest
    end
    
    def many &block
        accum = []
        loop do
            res = attempt do
                self.instance_eval &block
            end
            break if res.nil?
            accum << res
        end
        accum
    end
    
    def step
        throw EOF if here.nil?
        c = here
        if c == '\n' then
            self.line += 1
            self.col   = 1
        else
            self.col  += 1
        end
        self.offset += 1
        nil
    end
    
    def spaces
        while here == ' ' do
            step
        end
    end
    
    def some_of set
        spaces
        (raise ParseError, expected: set) unless set.include? here
        acc = ""
        while set.include? here do
            acc += here
            step
        end
        spaces
        return acc
    end
    
    def token str
        if stream[offset... offset + str.length] == str then
            str.length.times do
                step
            end
            spaces
            str
        else
            raise ParseError, expected: str
        end
    end
end

class UndefinedVariable < Exception
end

class Var < Struct.new :name, :version
    def self.parse ps
        self.new ps.some_of('a'.. 'z'), 0
    end
    
    def refresh
        Var.new name, version + 1
    end
    
    def reduce
        step
    end
    
    def step
        raise UndefinedVariable, "#{self.inspect} is not defined"
    end
    
    def subst env
        if env.has_key? self then
            env[self]
        else
            self
        end
    end
    
    def inspect
        colors = [:cyan, :yellow, :red, :green, :magenta, :blue]
        colors = (colors + [:white]).map { |c| "light_#{c}" }
        colors -= ["light_white"]
        name.send colors[(name.hash + version) % colors.length]
    end
end

class Func < Struct.new :arg, :body
    def self.parse ps
        ps.token "\\"
        args = ps.some do
            Var.parse ps
        end
        ps.token "->"
        body = App.parse ps
        args.reverse.reduce(body) do |b, arg|
            Func.new arg, b
        end
    end
    
    def reduce
        self
    end
    
    def step
        self
    end
    
    def refresh
        new_arg = arg.refresh
        new_body = body.subst arg => new_arg
        Func.new new_arg, new_body
    end
    
    def subst env
        if env.has_key? arg then
            self
        else
            Func.new arg, body.subst(env)
        end
    end
    
    def inspect
        args = []
        i = self
        while i.is_a? Func do
            args << i.arg
            i = i.body
        end
        argz = args.map(&:inspect).join(' ')
        "\\".light_black + argz + " -> ".light_black + i.inspect
    end
end

class App < Struct.new :f, :x
    def self.parse ps
        res = ps.some do
            i = ps.attempt { Var.parse   ps }        
            i = ps.attempt { Func.parse  ps } if i.nil?
            i = ps.attempt { Group.parse ps } if i.nil?
            i = ps.attempt { Num.parse   ps } if i.nil?
            raise ParseError, "expected expression" if i.nil?
            i
        end
        res.reduce do |f, x|
            App.new f, x
        end
    end
    
    def reduce
        i = self
        j = self
        while (i = i.step) != j do
            j = i
        end
        j
    end
    
    def step
        f1 = f.reduce
        x1 = if x.is_a? Func then x.refresh else x end
        case f1
        when Func
            f1.body.subst f1.arg => x1
            
        else
            raise "#{f1.class}(#{f1.inspect}) cannot be used as function"
        end
    end
    
    def subst env
        App.new f.subst(env), x.subst(env)
    end
    
    def inspect
        xs = []
        i = self
        while i.is_a? App do
            xs << i.x
            i = i.f
        end
        is = if i.is_a? Func then 
            "(".light_black + i.inspect + ")".light_black
        else
            i.inspect
        end
        xs.reverse.reduce(is) do |rest, x|
            xs = if x.is_a? Func then 
                "(".light_black + x.inspect + ")".light_black
            else
                x.inspect
            end
            "(".light_black + rest + " " + xs + ")".light_black
        end
    end
end

module Group
    def self.parse ps
        ps.token "("
        res = App.parse ps
        ps.token ")"
        res
    end
end

class Num < Struct.new :raw
    def self.parse ps
        Num.new ps.some_of('0'..'9').to_i
    end
    
    def subst env
        self
    end
    
    def step
        self
    end
    
    def reduce
        self
    end
    
    def inspect
        raw.to_s.light_white
    end
end

def parse text
    App.parse Stream.of text
end

def repl
    loop do
        print "> "
        begin
            line = gets
            next if line == "\n"
            prog = parse line
            puts "got:     #{prog.inspect}"
            puts "reduced:".green + " #{prog.reduce.inspect}"
            puts ""
        rescue Interrupt => e
            puts
            puts "Bye!"
            break

        rescue Exception => e
            puts "error:".red + "   #{e}"  
            
        end
    end
end

repl