--[[ Lazy Cell-Based List Module
     Functional Programming Example in Lua
     H. Conrad Cunningham, Professor
     Computer and Information Science
     University of Mississippi

Developed for CSci 658, Software Language Engineering, Fall 2013

1234567890123456789012345678901234567890123456789012345678901234567890

2013-09-26: Developed from eager cell list module by adding delay
            macro and the force and memoize fucntions, modifying
            the primitive operations, and adding explicit delay calls
2013-10-03: Updated comments for use of C preprocessor
            Changed file names from lazyList... to lazyList1...
2013-12-27: Added function deepCopy

This Lua module exports a set of functions for a lazily evaluated List
abstract data type (ADT). By further replacing the cons function calls
with a macro, this module implements a cons cell in which the tail is
a delayed expression (i.e., an expression inside an argumentless
closure).

The design of the "stream" primitives given in Section 3.5 of SICP
motivated the design for the helper functions delay, force, and
memoize and the list primitive functions in this module.

--]]


-- PRIMITIVE OPERATIONS AND CONSTANTS

-- These primitive definitions directly access and manipulate the Lua
-- data representation for the lists.  They provide a layer of
-- functional abstraction that the non-primitive and user functions
-- use to create and manipulate lists. In some sense, these primitive
-- definitions are themselves an information-hiding module hiding the
-- secret of how the lists are represented.

-- Function "show_data" converts raw Lua data structures to strings to
-- assist in debugging and testing.  This was not in the SICP Scheme
-- 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

-- Function "memoizes" a lazily evaluated function by storing the
-- value of the first evaluation and returning the stored value for
-- future evaluations.

local function memoize(expr)
  assert(type(expr) == "function",
    "Argument to memoize must be a function.")
  local alreadyRun = false
  local result
  return function()
    if not alreadyRun then
      result     = expr()
      alreadyRun = true
      return result
    else
      return result
    end
  end
end


-- New lazy cons macro for C preprocessor that can be processed with as
-- cpp -P lazyList.lua lazyListX.lua




-- Function "force" causes its argument "delayedExpr" to be evaluated
-- and the value returned.  If the argument is a closure (function),
-- "force" assumes that it was created by a call to "delay". If the
-- argument is not a closure (function), then "force" returns the
-- argument unmodified.

local function force(delayedExpr)
  if type(delayedExpr) == "function" then
    return delayedExpr()
  else
    return delayedExpr
  end
end
     
 
-- Define a constant for a Nil list singleton object
local NILLIST = {}


-- Function "isNil" returns true if and only if argument "l" is the
-- Nil list.  If "l" is a delayed expression, then its evaluation is
-- forced before checking to see if it is a Nil list.

local function isNil(l)
  l = force(l)
  return l == NILLIST
end


-- Function "isList" returns true if and only if argument "l" is a
-- valid non-Nil list cell.  If "l" is a delayed expression, then its
-- evaluation is forced before checking to see if it is a Nil list.

local function isList(l)
  l = force(l)
  return type(l) == "table" and l.head ~= nil and l.tail ~= nil
end


-- Function "Nil" returns the canonical representation for the Nil
-- list.  

local function Nil()
  return NILLIST
end

-- Function "eCons" takes a non-nil head element "h" and a tail list
-- cell "t" and returns a new list cell for the list with head "h" and
-- tail "t". If "t" is nil or absent, then it defaults to the Nil
-- list. This "eager Cons" is the same as "Cons" in the previous cell
-- list implementations.  Calls to this function are generated by the
-- "Cons" macro used for this version.

local function eCons(h,t)
  t = t or Nil()
  assert(h ~= nil, "head element in eCons call must be non-nil.")
  return { head = h, tail = t }
end


-- Functions "head" and "tail" return the respective fields of the
-- list "l".

local function head(l)
  l = force(l)
  assert(isList(l),
    "head function not defined for lists without head fields.")
  return l.head
end
    
local function tail(l)
  l = force(l)
  assert(isList(l),
    "tail function not defined for lists without tail fields.")
  return l.tail
end


-- NON-PRIMITIVE CONVENIENCE FUNCTIONS

-- These operations do not directly access the data structure
-- implementing the list cell table. They build on the primitive
-- operations above.

-- No changes were necessary in the implementation of these functions
-- for lazy lists except that now the "Cons" function calls are "Cons"
-- macro applications.

-- Function "isValidList" returns true if and only if argument "l" is
-- a validly structured finite list.  If does not return if the list
-- is infinite (e.g., contains cycles).  (Calling this function does a
-- deep validity check on the list, but does not look at data embedded
-- in the head elements of cells.)

local function isValidList(l)
  if isList(l) then
    return isValidList(tail(l))
  else
    return isNil(l)
  end
end


-- Function "listToString" converts list "l" to a convenient string
-- format and returns the string. If an element of a list is itself a
-- list, this function recursively converts that element to a list.

-- Precondition: isValidList(l)


local function listToString(l)
  if isList(l) then
    local h, hstr = head(l), ""
    if isList(h) or isNil(h) then
      hstr = listToString(h)
    else
      hstr = tostring(h)
    end
    return "Cons(" .. hstr .. ", " .. listToString(tail(l)) .. ")"
  else
    assert(isNil(l),
      "Argument of listToString is not a validly structured list.")
    return "Nil"
  end
end


-- Function "copy" constructs a "shallow" copy of list "l" and returns
-- the copy.  That is, it creates duplicates of the cells in the list
-- itself, but it does not copy the data embedded within the head
-- elements of the cells.

-- Precondition: isValidList(l)

local function copy(l) 
  if isList(l) then 
    return (eCons(head(l),memoize(function() return copy(tail(l)) end)))
  else 
    assert(isNil(l),"Can only copy validly structured lists.")  
    return Nil() 
  end
end


-- Function "deepCopy" constructs a "deep copy" of its argument "l".
-- That is, if any element of the list "l" is itself a list, the
-- function copies that list.  It also does a shallow copy of any
-- other table encountered.

local function deepCopy(l)
  if isList(l) then
    return (eCons(deepCopy(head(l)),memoize(function() return deepCopy(tail(l)) end)))
  elseif isNil(l) then
    return Nil()
  elseif type(l) == "table" then
    print("DEBUG: table")
    local newl = {}
    for k,v in pairs(t) do
      newl[k] = v
    end
    return newl
  else
    return l
  end
end


-- Function "length" returns the length of list "l".  The length is
-- the number of cells in the list, not counting the Nil at the end.

-- Precondition: isValidList(l)

local function length(l)
  if isList(l) then 
    return 1 + length(tail(l))
  else 
    assert(isNil(l),
           "Can only evaluate length for validly structured lists.")
    return 0  
  end
end


-- Function "take" returns the list constructed by extracting the
-- first "n" elements from list "l".

-- Precondition: n >= 0 and isValdList(l)
-- This function does not do a deep validity check on "l".

local function take(n,l)
  assert(n >= 0,
         "Cannot take negative number of elements from a list.")
  local msg = 
    "Second argument of take must be a validly structured list."
  if n == 0 then
    assert(isList(l) or isNil(l), msg)
    return Nil()
  elseif isList(l) then
    return (eCons(head(l),memoize(function() return take(n-1,tail(l)) end)))
  else
    assert(isNil(l),msg)
    return Nil()
  end
end


-- Function "drop" returns the the list constructed by removing the
-- first n elements of list "l".

-- Precondition: n >= 0 and isValdList(l)
-- This function does not do a deep validity check on "l".

local function drop(n,l)
  assert(n >= 0,
         "Cannot drop negative number of elements from a list.")
  local msg = "Second argument of take must be a list."
  if n == 0 then
    assert(isList(l) or isNil(l), msg)
    return l
  elseif isList(l) then
    return drop(n-1,tail(l))
  else
    assert(isNil(l), msg)
    return Nil()
  end
end


-- Function "append" takes lists "x" and "y" and returns a new
-- list consisting of the elements of "x" followed by the
-- elements of "y".

-- Precondition: isValidList(x) and isValidList(y)
-- This function does not do a deep validity check on "y".

local function append(x,y)
  if isNil(x) then
    assert(isList(y) or isNil(y),
      "Second argument of append must be a list.")
    return y
  else
    assert(isList(x),
      "First argument of append must be a validly structured list.")
    return (eCons(head(x),memoize(function() return append(tail(x),y) end)))
  end
end


-- Function "traverse" sets up a stateless iterator compatible with
-- Lua's generic-for statement. The function takes a list and returns
-- three values needed by the generic-for: the iterator function
-- "getnext", the invariant state (the entire list), and the
-- control variable (initially the first cell).  

-- When used with the generic for, the "getnext" iterator steps from
-- cell to cell through the list, returning the next (tail) cell and
-- the current head value for each step. (See sections 7.2 and 7.3,
-- pages 63-65, of PiL for an explanation.)

-- Precondition of getnext: 
--   isValidList(l) and cell is some tail segment of l

local function getnext(l,cell)
  if not cell or isNil(cell) then
    return nil
  else
    assert(isList(cell),
      "Argument to traverse must be a structurally valid list.")
    return tail(cell), head(cell)
  end
end

-- Precondition of traverse: isValidList(l)

function traverse(l)
  assert(isList(l) or isNil(l),
    "Argument to traverse iterator must be a list.")
  return getnext, l, l
end


-- Function "map" applies (i.e., maps) function "f" to every element
-- of list "l" and returns the resulting list, preserving the relative
-- order of the elements. 

-- Precondition: isValidList(l) and "f" is a one argument function
-- defined for all elements in "l".

local function map(f,l)
  if isList(l) then
    return (eCons(f(head(l)),memoize(function() return map(f,tail(l)) end)))
  else 
    assert(isNil(l),
      "Second argument to map must be a validly structured list.")
    return Nil()
  end
end


-- Function "filter" applies boolean function (i.e., a predicate)
-- "pred" to every element of list "l" and returns the new list
-- consisting of those elements for which the predicate is true.

-- Precondition: isValidList(l) and "pred" is a one-argument boolean
-- function defined for all elements in "l"

local function filter(pred,l)
  if isList(l) then
    local h = head(l)
    if pred(h) then
      return (eCons(h,memoize(function() return filter(pred,tail(l)) end)))
    else
      return filter(pred,tail(l))
    end
  else
    assert(isNil(l),
      "Second argument to filter must be a validly structured list.") 
    return Nil()
  end
end


-- Function "foldr" inserts the binary operator "op" between every
-- pair of elements in the list "l" with value "init" after the last
-- element of the tail. It computes the resulting value with operator
-- "op" binding from the right: op(x1,op(x2,op(x3,init))) for list
-- {x1,x2,x3}. Often, "init" is the right identity element of the
-- operation "op".

-- Precondition: isValidList(l) and "op" is a binary operator that
-- takes an element of the list as its left operand and elements of
-- the same kind as "init" as its right operand and returns a value of
-- the same kind as its right operand.

-- For example, if "op" is addition of numbers and we wish to add the
-- numbers in the list, we can set "init" to 0, which is the identity
-- element and, hence, both the right and left identity element.`

local function foldr(op,init,l)
  if isList(l) then
    return op(head(l),foldr(op,init,tail(l)))
  else
    assert(isNil(l),
      "Third argument to foldr must be a validly structured list.")
    return init
  end
end


-- Function "foldl" inserts the binary operator "op" between every
-- element in the list "l" with value "init" added before the head. It
-- computes the resulting value with the operators binding from the
-- left: op(op(op(init,x1),x2),x3) for list {x1,x2,x3}. Often, "init"
-- is the left identity element of the operation "op".

-- Precondition: isValidList(l) and "op" is a binary operator that
-- takes an element of the list as its right operand and elements of
-- the same kind as "init" as its left operand and returns a value of
-- the same kind as its left operand.

local function foldl(op,init,l)
  if isList(l) then
    return foldl(op,op(init,head(l)),tail(l))
  else
    assert(isNil(l),
      "Third argument to foldr must be a validly structured list.")
    return init
  end
end


-- Function "toList" constructs a list from array-style table "t" and
-- returns the list.

local function toList(t)
  assert(type(t) == "table","Argument to toList must be a table.")

  local function toList_iter(t,i,l)
    if i == 0 then
      return l
    else
      return toList_iter(t,i-1,(eCons(t[i],memoize(function() return l end))))
    end
  end

  return toList_iter(t,#t,Nil())
end


-- Function "fromList" takes a list "l" and constructs the equivalent
-- array-style table "t".

-- Precondition: isValidList(l)

local function fromList(l)
 
  local function toTable(l,t)
    if isList(l) then
      t[#t+1] = head(l)
      return toTable(tail(l),t)
    else
      assert(isNil(l),
        "Argument to fromList must be a validly structured list.")
      return t
    end
  end

  return toTable(l,{})
 end


--[[ MODULE EXPORT LIST (the external interface)

This module chunk (script) is compiled into a zero-argument function.
Another Lua chunk can load this module using the Lua "requires"
function, supplying "requires" the base filename of this module as the
argument.  When this module is loaded, it executes and returns the
following table to that chunk.

A module's table usually consists of references to functions and
values that the developer of the module wishes to make available
(i.e., export) to the user. The module can keep some functions and
values local to the module and not export them. (Remember that a
reference to a "function" is really a reference to a "closure" object.
So it can access and update the local variables and closures that are
not exported.)

The table returned below has fields defines as "outside = inside". The
key "outside" is the name that can be used to access the field from
outside the module. The "inside" is the internal value being exported.
These are often the same name, but they can be different.

--]]

return { Nil          = Nil,
         eCons        = eCons,
         head         = head,
         tail         = tail,
         isList       = isList,
         isNil        = isNil,
         isValidList  = isValidList,
         copy         = copy,
         deepCopy     = deepCopy,
         length       = length,
         take         = take,
         drop         = drop,
         append       = append,
         traverse     = traverse,
         map          = map,
         filter       = filter,
         foldr        = foldr,
         foldl        = foldl,
         toList       = toList,
         fromList     = fromList,
         listToString = listToString,
         show_data    = show_data,
         memoize      = memoize
       }