# http://cubiclemuses.com/cm/blog/tagsMisp

require 'misp.tab' # racc-generated parser
require 'pp'

module Misp

  module SExpr
    def self.new(str)
      Misp.parse(str)
    end
    def atom?
      kind_of? Symbol
    end
    def pair?
      kind_of? Pair
    end
    def quote_expr?
      pair? && hd == :quote && tl.pair? && tl.tl == :nil
    end
    def function_expr?
      pair? && hd == :fn && tl.pair? && tl.tl.pair?
    end
    def evaluate(env = {})
      puts "evaluating: #{self.inspect}"
      return env[self].evaluate(env) if env.has_key?(self)
      case self
      when :nil, :atom, :eq, :hd, :if, :fn, :pair, :quote, :tl
        self
      when Pair
        case hd
        when Pair
          Pair.new(hd.evaluate, tl).evaluate(env)
        when Function
          hd.evaluate(env, tl)
        when :atom
          if tl.hd.evaluate(env).atom? then :true else :nil end
        when :eq
          if tl.hd.evaluate(env).equal? tl.tl.hd.evaluate(env)
            :true
          else
            :nil
          end
        when :hd
          tl.hd.evaluate(env).hd
        when :if
          if tl.hd.evaluate(env) != :nil
            tl.tl.hd.evaluate(env)
          else
            tl.tl.tl.hd.evaluate(env)
          end
        when :fn
          Function.new(tl.hd, tl.tl.hd)
        when :pair
          Pair.new(tl.hd.evaluate(env), tl.tl.hd.evaluate(env))
        when :quote
          tl.hd
        when :tl
          tl.hd.evaluate(env).tl
        else
          raise RuntimeError, "can't evaluate undefined atom '#{ hd.inspect }'"
        end
      else
        raise RuntimeError, "can't evaluate undefined atom '#{ self.inspect }'"
      end
    end
    def to_sexp
      self
    end
  end

  class ::Symbol
    include SExpr
  end

  class Pair
    include SExpr
    attr_accessor :hd, :tl
    def initialize(hd, tl = :nil)
      @hd, @tl = hd, tl
    end
    def inspect
      "(#{ hd.inspect } . #{ tl.inspect })"
    end
    def ==(other)
      if other.respond_to?(:hd) && other.respond_to?(:tl)
        hd == other.hd && tl == other.tl
      end
    end
    def to_s(use_special_syntax = true)
      if tl == :nil
        # Nil Hiding
        "(#{ hd })"
      elsif use_special_syntax && quote_expr?
        # Quote
        "'#{ tl.hd }"
      elsif use_special_syntax && function_expr?
        # Function notation
        params = if tl.hd.atom? then ".#{tl.hd}" else tl.hd.to_s[1...-1] end
        "{|#{ params }| #{ tl.tl.hd }}"
      elsif tl.pair?
        # Tail Folding
        "(#{ hd } #{ tl.to_s(false)[1...-1] })"
      else
        "(#{ hd } . #{ tl })"
      end
    end
  end

  class Function
    def initialize(arg_names, body)
      raise "arg_names must be a SExpr" unless arg_names.kind_of?(SExpr)
      raise "body must be a SExpr" unless body.kind_of?(SExpr)
      @arg_names = arg_names
      @body = body
      puts "Function: #{arg_names.inspect}, #{body.inspect}"
    end
    def evaluate(env, args)
      puts "calling function: #{env.inspect}, #{args.inspect}"
      @body.evaluate bind_args(env.dup, @arg_names, args)
    end
    def bind_args(env, arg_names, args)
      puts "binding args: #{env.inspect}, #{arg_names.inspect}, #{args.inspect}"
      hd, tl =
        if args.atom?
          [args, :nil]
        else
          [args.hd, args.tl]
        end
      if arg_names.atom?
        env[arg_names] = args
      elsif arg_names.tl == :nil
        bind_args env, arg_names.hd, hd
      elsif arg_names.tl.atom?
        bind_args env, arg_names.hd, Pair.new(:hd, Pair.new(hd, :nil)) if args.pair?
        bind_args env, arg_names.tl, Pair.new(:tl, Pair.new(hd, :nil))
      else
        bind_args env, arg_names.hd, hd
        bind_args env, arg_names.tl, tl
      end
      env
    end
  end

  class ::Array
    def to_sexp() Pair.new(self[0].to_sexp, self[1].to_sexp) end
  end
  class ::NilClass
    def to_sexp() :nil end
  end

  def self.parse(str)
    Parser.new(str).do_parse
  end
end

if $0 == __FILE__
  require 'test_misp'
end