[Edu-sig] implementing summation notation (in Scheme & Python)

[Kirby Urner]

The generic sigma notation concept is presented in Scheme 
by authors Abelson and Sussman [1] as follows [2]:

  (define (sum term a next b)
    (if (> a b)
        0
        (+ (term a)
           (sum term (next a) next b))))

a and b are start, end values, with (term a) giving the 
actual term to be summed -- which might be a itself -- 
and (next a) giving the next value for a.  In other words, 
both term and next are functions, not numbers.

Here's the same thing in Python:

   def sum(term, a, next, b):
	if a>b: return 0
	return term(a) + sum(term,next(a),next,b)

And a non-recursive version:

   def sum2(term, a, next, b):
	total = 0
	while a<b:
	   total += term(a)
	   a = next(a)
	return total

or we could do it this way:

   from operator import add

   def sum3(term,a,next,b):
	def indexlist(a,next,b):
  	   output = []
	   while not a>b:
	      output.append(a)
	      a = next(a)
	   return output
	return reduce(add,[term(x) for x in indexlist(a,next,b)])

Recursively:

   from __future__ import nested_scopes
   from operator import add

   def sum4(term,a,next,b):
       def indexlist(a,next,b):
	   if a>b: return []
     	   else: return [a] + indexlist(next(a),next,b)
       return reduce(add,[term(x) for x in indexlist(a,next,b)])

If working in IDLE, you need to save the above in a new window,
then do CTRL-F5 to add it into to your namespace.  This is 
because the from __future__ thing doesn't work in the shell
window.

There's another problem with sum4 though -- it doesn't take advantage
of locally scoped bindings, i.e. there's no need to pass next and
b as parameters to indexlist if these are fixed within the outer 
function.  So a rewrite of sum4 might be:

  def sum4(term,a,next,b):
      def indexlist(s=a):
	  if s>b: return []
    	  else: return [s] + indexlist(next(s))
      return reduce(add,[term(x) for x in indexlist(a)])

I've introduced s to show that it changes through iterations
and only initializes to a.  sum3 could similarly benefit from
local bindings:

  def sum3(term,a,next,b):
      def indexlist():
          s=a
    	   output = []
	   while not s>b:
	      output.append(s)
	      s = next(s)
	   return output
      return reduce(add,[term(x) for x in indexlist()])

although again, if in IDLE, this will involve transfering the
def to a saved module/window and executing it with CTRL-F5.

If you want to sum consecutive integers, term(a) is just a, 
so the authors write ident:

   (define (identity x) x)

and another function to increment by 1:

   (define (inc n) (+ n 1))

We'll do the same in Python and find 1+2+3+...+10:

   def ident(a): return a

   def inc(a): return a+1

   >>> sum(ident, 1, inc, 10)
   55
   >>> sum2(ident, 1, inc, 10)
   55
   >>> sum3(ident, 1, inc, 10)
   55
   >>> sum4(ident, 1, inc, 10)
   55

Scheme:

  (define (pi-sum a b)
    (define (pi-term x)
      (/ 1.0 (* x (+ x 2))))
    (define (pi-next x)
      (+ x 4))
    (sum pi-term a pi-next b))

  > (* 8 (pi-sum 1 1000))
  3.139592655589783

Python:

  def pi_sum(a,b):
     def pi_term(x): return 1.0/(x * (x+2))
     def pi_next(x): return x+4
     return sum(pi_term,a,pi_next,b)

  >>> 8 * pi_sum(1,1000)
  3.1395926555897828

-- the above summation converges to pi.

Kirby

[1] http://mitpress.mit.edu/sicp/full-text/book/book.html
[2] http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html