node.lua

function new_node(arity, value)
   local new_node = {}
   new_node['arity'] = arity
   new_node['child_count'] = 0
   new_node['children'] = {}
   new_node['type'] = type(value) == "function" and "function" or "terminal"
   new_node['value'] = value
   new_node['parent'] = nil
  
   return new_node
end

function clone_node(node)
   local new_node = {}
   new_node.arity = node.arity
   new_node.child_count = node.child_count
   new_node.children = node.children ~= nil and clone_node(node.children) or nil
   new_node.type = node.type
   new_node.value = node.value
   new_node.parent = node.parent

   return new_node
end

function add_child(node, child)
   assert(node.child_count <= node.arity, "Node can not take any more children")
   child.parent = node
   node.children[node.child_count] = child
   node.child_count = node.child_count + 1
end

function remove_child(node, index)
   assert(node.children[index], "Specified node does not exist")
   node.children[index] = nil
   node.child_count = node.child_count - 1
end

function replace_child(node, index, new_child)
   assert(node.children[index], "Specified node does not exist")
   node.children[index] = new_child
end

function eval(root)
   assert(root.arity == root.child_count, "Node does not have correct number of children")
   if root.arity > 0 then
	  local child_values = {}
	  for i,node in pairs(root.children) do
		 child_values[i] = eval(node)
	  end 
	  return root.value(child_values)
   else
	  if type(root.value) == "function" then
		 return root.value()
	  else
		 return root.value
	  end
   end
end