--[[ Skeleton Arithmetic Expression Tree Program
     Object-Oriented Inheritance from Superclass Version
     H. Conrad Cunningham, Professor
     Computer and Information Science
     University of Mississippi

Developed for CSci 658, Software Language Engineering, Fall 2013

1234567890123456789012345678901234567890123456789012345678901234567890

2013-10-01: Evolved inheritance version from object-based version

The program uses an abstract "superclass" Expr and three "subclasses"
Const, Var, and Sum.

This is based, in part, on Section 16.2 of the PiL textbook.

--]]

-- Constants for object type tags
local EXPR_TYPE  = "Expr"
local SUM_TYPE   = "Sum"
local VAR_TYPE   = "Var"
local CONST_TYPE = "Const"

-- Display strings for object type tags
local displayStr = { [EXPR_TYPE]  = "Expr",
                     [SUM_TYPE]   = "Sum",
                     [VAR_TYPE]   = "Var",
                     [CONST_TYPE] = "Const"
                    }


-- ABSTRACT SUPERCLASS Expr prototype object

local Expr = { tag = EXPR_TYPE }

-- Constructor "Expr:new" creates objects in the Expr class hierarchy
-- having instance body "o".  Its primary uses are to create subclass
-- prototypes or, when inherited, to create subclass objects.

function Expr:new(o)
  o = o or {}
  setmetatable(o,self)
  self.__index = self
  return o
end

-- Concrete method "getTag" returns the type tag for the object.

function Expr:getTag()  return self.tag  end

-- Deferred "hook" method "display" is used by method "toString" to
-- display the body of the string.  It must be implemented
-- appropriately by each subclass to return a table of strings to be
-- concatenated, separated by commas.

function Expr:display()
  return { " ERROR: Expr:display() called " }
end

-- Concrete "template" method "toString" converts object to a string
-- representation of form ObjectType( body ).  It calls down to "hook"
-- method "display" from the subclass to convert the body of the
-- expression to a string.

function Expr:toString()
  return displayStr[self:getTag()] .. 
         "("  ..  table.concat(self:display(), ", ")  ..  ")" 
end

-- Deferred method "eval" evaluates the object's expression using
-- environment "env".  It must be implemented appropriately by each subclass.

function Expr:eval(env)
  error("Invalid call of deferred method Expr:eval", 2)
end

-- Deferred method "derive" computes the derivative of the object's
-- expression with respect to variable "v".  It must implemented
-- appropriately in each subclass.

function Expr:derive(v)
  error("Invalid call of deferred method Expr:derive", 2)
end


-- Forward references for object constants (singletons)
local CONST_ZERO
local CONST_ONE


-- CONCRETE SUBCLASS Const prototype (inherits from Expr)

local Const = Expr:new { tag = CONST_TYPE }

-- Subclass Const inherits constructor "Const:new" and accessors
-- "Const:getTag" and "Const:toString" from superclass Expr.
-- "Const:new" creates new subclass object.
 
-- Constructor/initializer method "Const:init" creates a new subclass
-- object with value "v".  The object inherits the tag field and
-- methods from Const, which in term inherits from Expr.

function Const:init(v)
  if type(v) == "number" then
    local o = Const:new { value = v } 
    return o
  else
    error(
    "Const:init called with nonnumeric value field: " .. tostring(v), 2)
  end
end

-- Const inherits accessor methods "getTag" and "toString" from Expr.

-- Accessor method "Const:getValue" returns the "value" of this Const
-- object.

function Const:getValue() return self.value end

-- Accessor method "Const:display" returns a table with one string to
-- represent this Const object.

function Const:display()
  return { tostring(self.value) }
end

-- Method "Const:eval" evaluates this expression object using
-- environment "env".

function Const:eval(env)
  return self.value
end

-- Method "Const:derive" computes the derivative of this expression
-- object with respect to variable "v".

function Const:derive(v)
  return CONST_ZERO
end
  
-- Define frequently used Const object singletons
CONST_ZERO = Const:init(0)
CONST_ONE  = Const:init(1)



-- CONCRETE SUBCLASS Var prototype (inherits from Expr)

local Var = Expr:new { tag = VAR_TYPE }

-- Subclass Var inherits constructor "Var:new" and accessors
-- "Var:getTag" and "Var:toString" from superclass Expr.
-- "Var:new" creates new subclass object.
 
-- Constructor/initializer method "Var:init" creates a new subclass
-- object with value "v".

function Var:init(n)
  if type(n) == "string" then
    local o = Var:new { name = n }
    return o
  else
    error("Var:init called with a non-string name argument: " .. 
          tostring(n), 2)
  end
end

-- Accessor method "Var:getName" returns the "name" of this Var
-- object.

function Var:getName()  return self.name  end

-- Accessor method "Var:display" returns a table with one string to
-- represent this Var object.

function Var:display()
  return { tostring(self.name) }
end
  
-- Method "Var:eval" evaluates this expression object using
-- environment "env".

function Var:eval(env)
  if type(env) == "table" and env[self.name] then 
    return env[self.name]
  else 
    error("Var:eval called with invalid environment: " .. 
          tostring(env), 2)
  end
end

-- Method "Var:derive" computes the derivative of this expression
-- object with respect to variable "v".

function Var:derive(v)
  if type(v) == "string" then 
    if v == self.name then
      return CONST_ONE
    else
      return CONST_ZERO
    end
  else
    error("Var:derive called with invalid variable: " .. 
          tostring(v), 2)
  end
end


-- CONCRETE SUBCLASS Sum prototype (inherits from Expr)

local Sum = Expr:new { tag = SUM_TYPE }

-- Subclass Sum inherits constructor "Sum:new" and accessors
-- "Sum:getTag" and "Sum:toString" from superclass Expr.
-- "Sum:new" creates new subclass object.
 
-- Constructor/initializer method "Sum:init" creates a new subclass
-- object with subexpression objects "left" and "right".

function Sum:init(l,r)
  if type(l) == "table" and l:getTag() then
    if type(r) == "table" and r:getTag() then
      local o = Sum:new { left = l, right = r }
      return o
    else
      error("Second argument of Sum:init is not a valid object: " ..
            tostring(r), 2)
    end
  else
    error("First argument of Sum:init is not a valid object: " ..
          tostring(l), 2)
  end
end

-- Accessor functions "Sum:getLeft" and "Sum:getRight" return the left
-- and right subexpressions of Sum, respectively.

function Sum:getLeft()  return self.left  end
function Sum:getRight() return self.right end

-- Accessor method "Sum:display" returns a table with one string to
-- represent this Sum object.

function Sum:display() 
  return { self.left:toString(), self.right:toString() }
end

-- Method "Sum:eval" evaluates this expression object using
-- environment "env".

function Sum:eval(env)
  if type(env) == "table" then 
    return self.left:eval(env) + self.right:eval(env)
  else 
    error("Sum:eval called with invalid environment: " .. 
          tostring(env), 2)
  end
end

-- Method "Sum:derive" computes the derivative of this expression
-- object with respect to variable "v".

function Sum:derive(v) 
  if type(v) == "string" then 
    return Sum:init(self.left:derive(v),self.right:derive(v))
  else
    error("Sum:derive called with invalid variable: " .. 
          tostring(v), 2)
  end
end


-- UTILITY FUNCTIONS

-- Function "show_data" converts raw Lua data structures to strings to
-- assist in debugging and testing.  This function was borrowed from the
-- complex number package.

local function show_data(d)
  if type(d) == "table" then
    local res = {}
    for k,v in pairs(d) do
      res[#res+1] = "[" .. show_data(k) .. "] = " .. show_data(v)
    end
    return "(" .. table.concat(res, ", ") .. ")"
  else
    return tostring(d)
  end
end


-- MAIN PROGRAM -- A SMALL AMOUNT of TESTING

print("Define exp")
local exp = Sum:init( Sum:init(Var:init("x"),Var:init("x")), 
                     Sum:init(Const:init(7), Var:init("y")) )
print("show_data(exp) = " .. show_data(exp))

print("Define env")
local env = { x = 5, y = 7 }

print("Begin exp tests.")
print("Expression: " .. exp:toString())
print("Evaluation with x = 5, y = 7: " .. exp:eval(env))
local d1, d2 = exp:derive("x"), exp:derive("y")
print("Derivative relative to x:\n  " .. d1:toString())
print("Derivative relative to y:\n  " .. d2:toString())