Atom = Struct.new(:name)
Lambda = Struct.new(:atbind, :args, :body)
Variable = Struct.new(:name)
Call = Struct.new(:object, :parameters)
Chain = Struct.new(:a, :b)
Tuple = Struct.new(:type, :items)

class Atom
  def vars
    []
  end

  def beta(env)
    self
  end

  def match?(other, env)
    self == other ? env : nil
  end

  def eval(env={})
    self
  end
end

class Lambda
  def vars
    [args.vars].flatten
  end

  def beta(env)
    env2 = clean env
    Lambda.new(atbind && atbind.beta(env2), args, body.beta(env2))
  end

  def match?(other, env)
    if env2 = args.match?(other, clean(env))
      if atbind.nil?
        env2
      elsif env3 = atbind.match?(other, env2)
        env3
      else
        nil
      end
    end
  end

  def eval(env={})
    self
  end

  def call(parameters, env)
    if e = match?(parameters, env)
      body.beta(e).eval(e)
    else
      Tuple.new(Atom.new("NoMatch"), [parameters])
    end
  end

  def clean(env)
    env_clean = {}
    (env.keys - vars).each { |k|
      env_clean[k] =  env[k]
    }
    env_clean
  end
end

class Chain
  def vars
    a.vars + b.vars
  end

  def beta(env)
    Chain.new(a.beta(env), b.beta(env))
  end

  def match?(other, env)
    a.match?(other, env) || b.match?(other, env)
  end

  def eval(env={})
    Chain.new(a.eval(env), b.eval(env))
  end

  def call(parameters, env)
    if env2 = a.match?(parameters, env)
      Call.new(a, parameters).eval(env2)
    else
      Call.new(b, parameters).eval(env)
    end
  end
end

class Tuple
  def vars
    items.map { |i| i.vars }.flatten
  end

  def beta(env)
    Tuple.new(type, items.map { |i| i.beta(env) })
  end

  def match?(other, env)
    return nil  unless Tuple === other
    return nil  if items.size != other.items.size

    if env = type.match?(other.type, env)
      items.zip(other.items) { |s, o|
        env = s.match?(o, env)
        return nil  if env.nil?
      }
      env
    end
  end

  def eval(env={})
    Tuple.new(type, items.map { |i| i.eval(env) })
  end
end

class Call
  def vars
    parameters.vars
  end

  def beta(env)
    Call.new(object.beta(env), parameters.beta(env))
  end

  def match?(other, env)
    if Call === other
      if env2 = object.match?(other.object, env)
        parameters.match?(other.parameters, env2)
      end
    else
      if env2 = parameters.match?(other, env)
        object.eval(env).match?(other, env2)
      end
    end
  end

  def eval(env={})
    if object.respond_to? :call
      object.call(parameters, env)
    else
      raise Theme::RunError, "can't eval #{object.inspect}"
    end
  end

  def call(ps, env={})
    o = eval(env)
    if o.respond_to? :call
      o.call(ps, env)
    else
      raise Theme::RunError, "can't eval #{o.inspect}"
    end
  end
end

class Variable
  def vars
    name
  end

  def beta(env)
    if env.include? name
      env[name]
    else
      self
    end
  end

  def match?(other, env)
    if env.include? name
      env[name] == other ? env : nil
    else
      env.merge name => other
    end
  end

  def eval(env={})
    if env.include? name
      env[name]
    else
      raise "undefined variable #{self}"
    end
  end

  def call(parameters, env)
    if env.include? name
      Call.new(env[name], parameters.eval(env)).eval(env)
    else
      raise "unbound call variable #{self}"
    end
  end
end