--[[ 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
Revised for CSci 450, Organization of Programming Language, Fall 2016

1234567890123456789012345678901234567890123456789012345678901234567890

2013-10-01: Evolved inheritance version from object-based version
2016-10-13: Enhanced comments
2026-10-15: Moved setting of __index out of new

The program uses an abstract "superclass" Expr and three "subclasses"
Const, Var, and Sum. I extracted it from the Prototype Object-Based
version and generalized.

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

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

--]]

-- 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 }
Expr.__index = Expr

-- Class method "Expr:new" -- a constructor -- 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 instance method "getTag" returns the type tag for the
-- object

function Expr:getTag()  return self.tag  end

-- I designed the "toString" functionality according to the
-- Template Method design pattern with template method "toString"
-- and hook method "display".  

-- Lua does not support abstract methods, but I want to include
-- various deferred methods in the Expr interface. So I implement the
-- deferred methods as concrete methods with some kind of default
-- error action. These are intended to be overridden.

-- Deferred instance "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 instance "template" method "toString" converts the
-- 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 instance 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 instance 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 }
Const.__index = Const

-- 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.

-- Note: Probably better to call this "Const:new" and change call of
-- superclass constructor to "local o = Expr.new(self,{value = v})".

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 }
Var.__index = Var

-- 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".

-- Note: See note on Const:init.

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 }
Sum.__index = Sum

-- 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".

-- Note: See note on Const:init.

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