lambda-calculus-repl.rb

require 'colorize'

class String
    def indent
        lines.map { |l| '  ' + l }.join('')
    end
    
    def nest
        if lines.count == 1 then
            self
        else
            "\n" + indent
        end
    end
    
    def keyword
        light_black
    end
    
    def wrap br
        br[0].kw + self + br[1].kw
    end
    
    alias :kw :keyword
end

class ParseError < Exception
end

class EOF < ParseError
end

"""
    Parsing state
"""
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

    # operator + from RegExp
    #
    def some &block
        res  = self.instance_eval &block
        rest = many(&block)
        [res] + rest
    end
    
    # operator * from RegExp
    #
    def many &block
        accum = []
        loop do
            res = attempt { self.instance_eval &block }
            break if res.nil?
            accum << res
        end
        accum
    end
    
    # go one char ahead
    #
    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
    
    # skip spaces
    #
    def spaces
        while not here.nil? and " \n".include? 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
    
    def inspect
        stream[0... offset] + '['.light_white + stream[offset... stream.length]
    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
        @@uvid ||= 0
        @@uvid += 1

        Var.new name, @uvid
    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[(version) % colors.length]
    end
end

class Func < Struct.new :arg, :body
    def self.parse ps
        ps.token "\\"
        args = ps.some { Var.parse ps }
        ps.token "->"
        body = App.parse ps
        Func.with_many_args args, body
    end
    
    def self.with_many_args args, body
        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 split_all_args
        args = []
        i = self
        while i.is_a? Func do
            args << i.arg
            i = i.body
        end
        [args, i]
    end
    
    def inspect
        (args, i) = split_all_args
        argz = args.map(&:inspect).join(' ')
        "\\".kw + argz + " -> ".kw + i.inspect.nest
    end
end

class LetExpr < Struct.new :name, :body, :context
    def self.parse ps
        ps.token "let"

        name = Var.parse ps
        args = ps.many { Var.parse ps }

        ps.token "="

        body = App.parse ps

        ps.token ";"
        
        context = App.parse ps
        
        LetExpr.new name, Func.with_many_args(args, body), context
    end
    
    def reduce
        i = self
        j = self
        while (i = i.step) != j do
            j = i
        end
        j
    end
    
    def step
        context.subst name => body
    end
    
    def subst env
        if env.has_key? name then
            LetExpr.new name, body.subst(env), context
        else
            LetExpr.new name, body.subst(env), context.subst(env)
        end
    end

    def inspect
        (args, i) = if body.is_a? Func then
            body.split_all_args
        else
            [[], body]
        end
        argss = if args.empty? then
            ""
        else
            " " + args.map(&:inspect).join(' ')
        end
        "let ".kw + name.inspect + argss +
            " = ".kw + i.inspect.nest +
            ";\n".kw + context.inspect
    end
end

class App < Struct.new :f, :x
    def self.parse ps
        res = ps.some do
            i = ps.attempt { LetExpr.parse ps }
            i = ps.attempt { Var.parse     ps } if i.nil?       
            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
        App.from_multiple_calls res
    end
    
    def self.from_multiple_calls calls
        calls.reduce do |f, x|
            App.new f, x
        end
    end
    
    def to_multiple_calls
        xs = []
        i = self
        while i.is_a? App do
            xs << i.x
            i = i.f
        end
        [xs, i]
    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) = to_multiple_calls
        is = if i.is_a? Func then 
            i.inspect.wrap "()"
        else
            i.inspect
        end
        xs.reverse.reduce(is) do |rest, x|
            xs = if x.is_a? Func then 
                x.inspect.wrap "()"
            else
                x.inspect
            end
            (rest + " " + xs).wrap "()"
        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

class Let < Struct.new :name, :body
    def self.parse ps
        ps.token "let"

        name = Var.parse ps
        args = ps.many { Var.parse ps }

        ps.token "="

        body      = App.parse ps
        
        Let.new name, Func.with_many_args(args, body)
    end
    
    def eval ctx
        self.body = self.body.subst(ctx).reduce
        ctx[name] = body
        nil
    end
    
    def inspect
        (args, i) = if body.is_a? Func then
            body.split_all_args
        else
            [[], body]
        end
        argss = if args.empty? then
            ""
        else
            " " + args.map(&:inspect).join(' ')
        end
        "let ".kw + name.inspect + argss +
            " = ".kw + i.inspect.nest
    end
end

class Value < Struct.new :value
    def self.parse ps
        Value.new App.parse ps
    end
    
    def eval ctx
        value.subst(ctx).reduce
    end
    
    def inspect
        value.inspect
    end
end

class Statement
    def self.parse ps
        ps.spaces
        i = ps.attempt { Let.parse ps }
        i = Value.parse ps if i.nil?
        raise ParseError, "expected declaration or expression" if i.nil?
        i
    end
end

class Forget < Struct.new :name
    def self.parse
        ps.token "#forget"
        name = Var.parse ps
    end
end

def parse text
    Statement.parse Stream.of text
end

def repl
    puts "Lambda calculus repl v0.1, WTFPL.".light_white
    puts ""
    ctx = {}
    loop do
        unless ctx.empty?
            puts ctx.keys.map(&:inspect).join(' ').wrap("{}")
        end
        print "> ".light_white
        begin
            line = gets
            next if line == "\n"
            raise Interrupt if line.nil?
            prog = parse line
            print prog.inspect.indent
            result = prog.eval(ctx)
            puts ";".light_black
            unless result.nil?
                puts "= ".green + result.inspect.nest
            end
            puts ""
        rescue Interrupt => e
            puts
            puts "Bye!".light_white
            break

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

repl