;;; File:
;;;   watch-recursion.ss
;;; Author:
;;;   Samuel A. Rebelsky
;;; Version:
;;;   1.0 of September 2003
;;; Summary:
;;;   Some extended recursive procedures that let us "watch" the 
;;;   steps in recursive evaluation.

;;; Name:
;;;   watch
;;; Type:
;;;   boolean
;;; Value:
;;;   Set to #t if we want to "watch" procedures and false otherwise.
(define watch #t)

;;; Procedure:
;;;   observe
;;; Parameters:
;;;   procName, a value
;;;   params, a list of values
;;; Purpose:
;;;   Observe that the procedure has been colled.
;;; Produces:
;;;   Nothing; called for side-effects.
;;; Preconditions:
;;;   watch is defined.
;;; Postconditions:
;;;   Output may have been printed.
(define observe
  (lambda (proc params)
    (display (cons proc params))
    (newline)))
  
;;; Procedures:
;;;   sum
;;;   new-sum
;;;   newer-sum
;;; Parameters:
;;;   numbers, a list of numbers.
;;; Purpose:
;;;   Find the sum of the elements of a given list of numbers
;;; Produces:
;;;   total, a number.
;;; Preconditions:
;;;   All the elements of numbers must be numbers.
;;; Postcondition:
;;;   total is the result of adding together all of the elements of ls.
;;;   total is a number.
;;;   If all the values in numbers are exact, total is exact.
;;;   If any values in numbers are inexact, total is inexact.

; Most popular: Clinton
;   Straightforward
;   Doesn't need an extra procedure
;   Who cares about tradition?  sum is commutative
(define sum
  (lambda (numbers)
    (display (list 'sum numbers))
    (newline)
    (if (null? numbers)
        0
        (+ (car numbers) (sum (cdr numbers))))))

; Moderately popular: All eligible democratic candidates
;   Sums in the traditional way (left-to-right rather than right-to-left)
;   Probably more efficient.
;   Easier to "observe"
(define new-sum
  (lambda (numbers)
    (new-sum-helper 0 numbers)))

; Unpopular: Fred the Dog
(define newer-sum
  (lambda (numbers)
    (new-sum-helper (car numbers) (cdr numbers))))

;;; Procedure:
;;;   new-sum-helper
;;; Parameters:
;;;   sum-so-far, a number.
;;;   remaining, a list of numbers.
;;; Purpose:
;;;   Add sum-so-far to the sum of the elements of a given list of numbers
;;; Produces:
;;;   total, a number.
;;; Preconditions:
;;;   All the elements of remaining must be numbers.
;;;   sum-so-far must be a number.
;;; Postcondition:
;;;   total is the result of adding together sum-so-far and all of the 
;;;     elements of remaining.
;;;   total is a number.
;;;   If both sum-so-far and all the values in remaining are exact, 
;;;     total is exact.
;;;   If either sum-so-far or any values in remaining are inexact, 
;;;     total is inexact.
(define new-sum-helper
  (lambda (sum-so-far remaining)
    (display (list 'new-sum-helper sum-so-far remaining))
    (newline)
    (if (null? remaining)
        sum-so-far
        (new-sum-helper (+ sum-so-far (car remaining))
                        (cdr remaining)))))



;;; Procedure:
;;;   step
;;; Parameters:
;;;   prefix, a string
;;;   value, a Scheme value
;;;   suffix, a string
;;; Purpose:
;;;   Displays prefix, value, and suffix on a line.
;;;   Used primarily for showing steps of computation.
;;; Produces:
;;;   value (exactly the same as value).
;;; Preconditions:
;;;   [Standard]
;;; Postconditions:
;;;   The parameters have been displayed.
(define step
  (lambda (prefix value suffix)
    (display prefix)
    (display value)
    (display suffix)
    (newline)
    value))

;;; Procedure:
;;;   watch-sum
;;; Parameters:
;;;   lst, a list of numbers of the form (n_1 n_2 ... n_k)
;;; Purposes:
;;;   Sum the values in lst.
;;;   Show the steps involved in computing that sum.
;;; Produces:
;;;   result, a number
;;; Preconditions:
;;;   [Standard]
;;; Postconditions:
;;;   result = n_1 + n_2 + ... + n_k.
;;;   The steps in evaluation have been printed.
(define watch-sum
  (lambda (lst)
    (watch-sum-helper lst "" "")))

(define watch-sum-helper
  (lambda (lst prefix suffix)
    (step prefix (list 'sum (cons 'list lst)) suffix)
    (if (null? lst)
        (step prefix 0 suffix)
        (step prefix
              (+ (car lst)
                 (watch-sum-helper (cdr lst)
                                   (string-append prefix 
                                                  "(+ "
                                                  (number->string (car lst))
                                                  " ")
                                   (string-append ")" suffix)))
              suffix))))

;;; Procedure:
;;;   watch-greatest-of-list
;;; Parameters:
;;;   numbers, a list of numbers of the form (n_1 n_2 ... n_k)
;;; Purposes:
;;;   Find the largest value in numbers.
;;;   Show the steps involved in computing that value.
;;; Produces:
;;;   greatest, a number
;;; Preconditions:
;;;   [Standard]
;;; Postconditions:
;;;    greatest >= n_i for all reasonable i.
(define watch-greatest-of-list 
  (lambda (numbers)
    (wgol-helper numbers "" "")))

(define wgol-helper
  (lambda (numbers prefix suffix)
    (step prefix (list 'greatest-of-list (cons 'list numbers)) suffix)
    (if (null? (cdr numbers))
        (step prefix (car numbers) suffix)
        (step prefix
              (max (car numbers)
                   (wgol-helper (cdr numbers)
                                (string-append prefix
                                               "(max " 
                                               (number->string (car numbers))
                                               " ")
                                (string-append ")" suffix)))
              suffix))))