--[[ Summation Function with Functional Parameters
     Functional Programming Example -- Higher Order
     H. Conrad Cunningham, Professor
     Computer and Information Science
     University of Mississippi

Developed for CSci 658, Software Language Engineering, Fall 2013

1234567890123456789012345678901234567890123456789012345678901234567890

2013-09-10: Completed prototype

This higher-order summation function is adapted from section 1.3.1 of
Abelson and Sussman's Structure and Interpretation of Computer
Programs (SICP) textbook.

Note: I leave out the precondition assertion checking to simplify the
presentation.

--]]

-- Function "sum_integers" computes the sum of the integers in the
-- range from "a" through "b".

local function sum_integers(a,b)
  if a > b then
    return 0
  else
    return a + sum_integers(a+1,b)
  end
end

-- Function "sum_cubes" computes the sum of the cubes of the integers
-- in the range from "a" through "b".

local function cube(x) return x * x * x end

local function sum_cubes(a,b)
  if a > b then
    return 0
  else
    return cube(a) + sum_cubes(a+1,b)
  end
end

-- Function "pi_sum" computes the sum of the series of terms 1/(i*(i+2)) from 
-- i = "a" until i > "b".  That is, for a = 1 and b = 10 this would be
-- 1/1*3 + 1/5*7 + 1/9*11.  For initial a = 1, this converges slowly on PI/8.

local function pi_sum(a,b)
  if a > b then
    return 0
  else
    return 1 / (a * (a+2)) + pi_sum(a+4,b)
  end
end

--[[

The above all satisfy template of the following form for some
NAME,TERM, and NEXT.

  local function NAME(a,b))
    if a < b then
      return 0
    else
      return TERM(a) + NAME(NEXT(a),b)
    end
  end

We can express this function as a higher-order function (for NAME)
with functional arguments for the operations TERM and NEXT.

--]]

-- Function "sum" adds the values of the application of function
-- "term" to integer i for all integers i in the range [1,b], where
-- the  difference from i to its successor j is next(i).

local function sum(term,a,next,b)
  if a > b then
    return 0
  else
    return term(a) + sum(term,next(a),next,b)
  end
end

-- sum_integers in terms of sum

local function id(x)   return x     end
local function incr(x) return x + 1 end

local function sum_integers2(a,b) return sum(id,a,incr,b) end

-- sum_cubes in terms of sum

local function sum_cubes2(a,b) return sum(cube,a,incr,b) end

-- pi_sum in terms of sum

local function pi_term(x) return 1 / (x * (x+2)) end
local function pi_next(x) return x + 4           end

local function pi_sum2(a,b) return sum(pi_term,a,pi_next,b) end

--[[
Function "sum" can be further generalized in various ways.

Question: How would we need to modify "sum" so that the resulting
higher-order function is capable of either summing or multiplying the
integers over a range?

--]]


-- Partial testing

print("sum_integers(1,10)  = " .. sum_integers(1,10))
print("sum_integers2(1,10) = " .. sum_integers2(1,10))
print("sum_cubes(1,5)      = " .. sum_cubes(1,5))
print("sum_cubes2(1,5)     = " .. sum_cubes2(1,5))
print("pi_sum(1,10000)     = " .. pi_sum(1,10000))
print("pi_sum2(1,10000)    = " .. pi_sum2(1,10000))