#lang racket

;;; A plain recursive version of product, which returns the product of
;;; the elements of a list passed to it. When it sees zero, it will stop
;;; processing the list, but still needs to return from all recursive calls.

(define product
  (lambda (ls)
    (cond [(null? ls) 1]
	  [(zero? (car ls)) 0]
	  [else (* (car ls) (product (cdr ls)))])))

;;; The tail-recursive version. When it sees zero, the computation terminates.
;;; While technically, it needs to return from all recursive calls, an optimizing
;;; interpreter will exit straight away. Notice that we did compute the prodcut
;;; of the list elements before the zero.

(define productT
  (lambda (ls accu)
    (cond [(null? ls) accu]
	  [(zero? (car ls)) 0]
	  [else (productT (cdr ls) (* (car ls) accu))])))

;;; Here is a modification of the tail recursive version of product
;;; that builds up a nested lambda expression. When it sees zero, the evaluation
;;; terminates, yet we still evaluate the lambda expression built up. As
;;; such there is NO performance improvement over the plan tail-recursive version.

(define product-cps
  (lambda (ls k)
    (cond [(null? ls) (k 1)]
	  [(zero? (car ls)) (k 0)]
	  [else (product-cps (cdr ls) (lambda (x) (k (* (car ls) x))))])))

;;; Here is a modification of the cps version in which we pass in two procedures
;;; One for the regular base case and one in case we see zero. Now, when we see
;;; zero, we call the "return" function and exit without evaluating the accumulated
;;; lambda expression. You should call product-cps-return as follows:
;;; (product-cps-return '(3 4 0 5 6) (lambda (x) x) (lambda (x) x))

(define product-cps-return
  (lambda (ls k return)
    (cond [(null? ls) (k 1)]
	  [(zero? (car ls)) (return 0)]
	  [else (product-cps-return (cdr ls) (lambda (x) (k (* (car ls) x))) return)])))