--[[ Skeleton Arithmetic Expression Tree Program
     Prototype Object-Based Version
     H. Conrad Cunningham, Professor
     Computer and Information Science
     University of Mississippi

Developed for CSci 658, Software Language Engineering, Fall 2013
Revised for CSci 450, Organization of Programming Language, Fall 2016

1234567890123456789012345678901234567890123456789012345678901234567890

2013-09-03: Modified program from author's Scala object-oriented and
            Lua Recursive Function List versions
2013-09-07: Changed "type" field of table to be "tag"
2016-10-13: Enhanced comments and fixed typo in name getValue
2016-10-15: Moved setting of __index out of new

Note: This code should be modularized to enable reuse of the classes.

--]]


--[[ ARITHMETIC EXPRESSION TREES

This program represents an arithmetic expression tree by a
record-style table with a type tag field and one or more named fields
to hold the operands.

The representation could have been a list-style table as with the
Recursive Function and Evaluation Table versions.

Access Discipline: Although the data fields of the Lua objects created
by the following can be directly read or written, the intention is for
the fields to be immutable after initialization and for their values
to only be accessed through the setters provided.

Design note:  Class method new and instance methods eval, derive, getTag,
and toString occur in all three classes with similar definitions. 
Instance methods getValue, getName, getLeft, and getRight and the data
fields they access are unique to particular classes.

--]]

-- Constants for object type tags
local SUM_TYPE,   SUM_STR   = "Sum", "Sum"
local VAR_TYPE,   VAR_STR   = "Var", "Var"
local CONST_TYPE, CONST_STR = "Const", "Const"

-- Note: The above separates the tag used in the table from the
-- type string displayed in the string representation. The approach taken
-- in the inheritance version is better. But this did not turn out to be
-- particularly useful feature, so other examples did maintain this
-- separation.

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


-- Const "class" prototype

local Const = {}
Const.__index = Const

-- Class method "Const:new" creates a new CONST_TYPE instance object
-- with value "v". It sets the metatable of the new instance to the
-- Const class prototype object and sets the "__index" metamethod to
-- delegate any missing key references to the Const class object.

function Const:new(v)
  if type(v) == "number" then 
    local t = { tag = CONST_TYPE, value = v }
    setmetatable(t,self)
--  self.__index = self
    return t
  else
    error(
    "Const:new called with nonnumeric value field: " .. tostring(v), 2)
  end
end

-- Instance method "eval" evaluates the Const instance in environment "env"
function Const:eval(env)
  return self.value
end

-- Instance method "derive" returns the symbolic derivative
function Const:derive(v)
  return CONST_ZERO
end

-- Instance method "getTag" returns the type tag
function Const:getTag() return self.tag  end

-- Instance method "getValue" returns the Const value
function Const:getValue() return self.value end

-- Instance method "toString" converts the Const instance to a string
function Const:toString()
   return CONST_STR .. "(" .. tostring(self.value) .. ")"
end
  
-- Set values for Const object singleton objects.
-- These values occur frequently in this code. By making them
-- Singleton constants, we avoid creating multiple copies and can
-- use comparisons of addresses rather than values.

CONST_ZERO = Const:new(0)
CONST_ONE  = Const:new(1)


-- Var "class" prototype

local Var = {}
Var.__index = Var

-- Class method new creates a new VAR_TYPE instance object with name "n"
function Var:new(n)
  if type(n) == "string" then
    local t = { tag = VAR_TYPE, name = n }
    setmetatable(t,self)
    -- self.__index = self
    return t
  else
    error("Var:new called with nonstring name argument: " .. 
          tostring(n), 2)
  end
end

-- Instance method "eval" evaluates the Var instance in 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

-- Instance method "derive" returns the symbolic derivative
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

-- Instance method "getTag" returns the type tag
function Var:getTag() return self.tag end

-- Instance method "getName" returns the Variable name
function Var:getName() return self.name end

-- Instance method "toString" converts the Var instance to a string
function Var:toString()
  return VAR_STR .. "(" .. self.name .. ")"
end
 

-- Sum "class" prototype

local Sum = {}
Sum.__index = Sum

-- Class method "Sum" creates a SUM_TYPE instance with left and right operands
function Sum:new(l,r)
  if type(l) == "table" and l:getTag() then
    if type(r) == "table" and r:getTag() then
      local t = { tag = SUM_TYPE, left = l, right = r }
      setmetatable(t,self)
      -- self.__index = self
      return t
    else
      error("Second argument of Sum:new is not a valid object: " ..
            tostring(r), 2)
    end
  else
    error("First argument of Sum:new is not a valid object: " ..
          tosgtring(l), 2)
  end
end

-- Instance method "eval" evaluates the Sum instance in 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

-- Instance method "derive" returns the symbolic derivative of the node
function Sum:derive(v) 
  if type(v) == "string" then 
    return Sum:new(self.left:derive(v),self.right:derive(v))
  else
    error("Sum:derive called with invalid variable: " .. 
          tostring(v), 2)
  end
end

-- Instance method "getTag" returns the type tag
function Sum:getTag()   return self.tag  end

-- Instance method "getLeft" returns the left operand
function Sum:getLeft()  return self.left  end

-- Instance method "getRight" returns the right operand
function Sum:getRight() return self.right end

-- Instance method "toString" converts the node to a string
function Sum:toString()
  return SUM_STR .. "(" .. self.left:toString() .. "," 
                        .. self.right:toString() .. ")"
end


-- MAIN PROGRAM 

local exp = Sum:new( Sum:new(Var:new("x"),Var:new("x")), 
                     Sum:new(Const:new(7), Var:new("y")) )
local env = { x = 5, y = 7 }

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())