Comp 210 Lab 7


More functional abstraction
===========================

Recall the function make-list-combiner from lecture last week:

(define make-list-combiner
  (lambda (null-val elt-fun combiner)
    (lambda (lst)
      (if (null? lst)
	  null-val
	  (combiner (elt-fun (car lst))
		    ((make-list-combiner null-val elt-fun combiner)
		     (cdr lst)))))))

We saw how to define functions such as list-postpend-22 in terms of
make-list-combiner:

(define list-postpend-22
  (make-list-combiner (list 22) (lambda (x) x) cons))

Consider the function list-remove-primes.

(define list-remove-odd
  (lambda (num-list)
    (if (null? num-list)
	null
	(if (odd? (car num-list))
	    (list-remove-odd (cdr num-list))
	    (cons (car num-list) (list-remove-odd (cdr num-list)))))))

Define list-remove-odd in terms of make-list-combiner.


Abstracting over lists with two functions
=========================================

make-list-combiner (defined above) takes three arguments (two of them
functions).  It separates the mechanisms of operating on a list element and
combining the result of that operation with the recursive call.  We can
also write a function which combines operating on a list element with
combining the result; this function takes only a single function that does
all the work for the non-null case:

(define make-list-function
  (lambda (null-val cons-fun)
    (lambda (lst)
      (if (null? lst)
	  null-val
	  (cons-fun (car lst)
                    (cdr lst)
                    (make-list-function null-val cons-fun))))))

cons-fun does all the work for the cons case, including calling the
function recursively if appropriate.  Try rewriting the following functions
in terms of make-list-function:

(define list-sum-of-squares
  (make-list-combiner 0 square +))
(define list-length
  (make-list-combiner 0 (lambda (x) 1) +))
(define list-product-of-primes
  (make-list-combiner 1 (lambda (x) (if (prime? x) x 1)) *))
(define list-postpend-22
  (make-list-combiner (list 22) (lambda (x) x) cons))

You may find it helpful to look at the full definitions of these functions,
which appear in the lecture notes.

Also rewrite list-insert-5, which you saw on the test:

;; Insert 5 in its proper place in a list sorted in ascending order.
(define list-insert-5
  (lambda (lst)
    (if (null? lst)
        (list 5)
        (if (< 5 (car lst))
            (cons 5 lst)
            (cons (car lst) (list-insert-5 (cdr lst)))))))

It is possible, but very inconvenient, to write list-insert-5 using
make-list-combiner because we don't always want to make the recursive call,
but make-list-combiner creates functions that always make the recursive
call.


Avoiding recomputation
======================

The homework defines these two functions:

      (define slow-list-max
        (lambda (l)
          (if (null? l)
              0
              (if (> (car l) (list-max (cdr l)))
                  (car l)
                  (slow-list-max (cdr l))))))

      (define fast-list-max
        (lambda (l)
          (if (null? l)
              0
              (local ((define cdr-max (fast-list-max (cdr l))))
                (if (> (car l) cdr-max)
                    (car l)
                    cdr-max)))))

We can use the make-list function to make a list of a particular length,
all of whose elements are identical.  For instance, 
(make-list 100 22) makes a list containing 100 copies of the number 22.

Use the "time" function in Chez Scheme to compare the running time of
slow-list-max and fast-list-max on a 20-element list.
fast-list-max is about as fast on a 200,000-element list as slow-list-max
is on a 20-element list.  Don't try running the programs on substantially
larger inputs, as they will take a very long time to finish.

(Challenge:  why is slow-list-max just as good as fast-list-max when the
list is sorted in descending order?)


Non-lexically identical recomputation
=====================================

One obvious way to avoid repeated work is to notice when two subexpressions
are lexically identical.  For instance, anyone can improve the efficiency
of the search program from assignment 2:

;; Return 0 if n doesn't appear in l;
;; otherwise, return the position of n in l (1 = first element)
(define search
  (lambda (n lst)
    (cond
      [(null? lst) 0]
      [else (if (eq? n (car lst))
                1
                (if (= (search n (cdr lst)) 0)
                    0
                    (add1 (search n (cdr lst)))))])))

How many recursive calls to search does this version make if the element is
not found?  How many recursive calls does your improved version make?

There are also important efficiencies to be gained when the same value is
computed during different function calls.

How many times is make-list-combiner called by the following sequence of
expressions?  (You might want to use Donkey to verify your answer.)

(define list-postpend-22
  (make-list-combiner (list 22) (lambda (x) x) cons))
(list-postpend-22 (list 1 2 3 4 5))
(list-postpend-22 null)
(list-postpend-22 (list 100 101))

Notice that evaluation of the first two expressions creates five distinct
functions, which are functionally equivalent:  in particular, their bodies
are identical.  We don't really need all those different functions -- we
could use the same one in each case.

Use local to modify make-list-combiner so that it returns a function which
does not call make-list-combiner, but which returns the same result.  Test
your function.

Here's an even more difficult challenge:  consider a function that computes
the Fibonacci numbers:

(define fib
  (lambda (n)
    (if (< n 2)
        n
        (+ (fib (- n 1))
           (fib (- n 2))))))

How many times is fib called?  How many different arguments to fib are
provided?  There are several good ways to make this function more
efficient; three of them are accumulator-style recursion, memoization, and
passing previous values to a function.  As a difficult challenge, think
about how you would compute the nth Fibonacci numbers with only n (plus or
minus one or two) function calls.


Rules for local
===============

The evaluation rules for local state that local variables are turned into
global variables.  Global variables are defined at the top level and are
visible everywhere in your program.  The illusion of local variables being
accessible in only small parts of your program is maintained by renaming
variables which are lifted from local to global scope.  The new name is
guaranteed to occur only in the scope of the original local definition, so
that no other code can use the new global variable; we have effectively
created a variable that is global in name only, because most parts of the
code will never see it.

Step through some examples to understand what local does.

(local ((define x 5))
  (* x 3))
(define foo
  (local ((define x 3))
    (lambda ()
       (+ x 1100))))
foo
(foo)


(define f
  (lambda (x)
    (local ((define y (+ x 2)))
      (lambda (z) (cons x y z)))))
f
(f 10)
((f 15) 20)
(define g (f 25))
g
(g 30)
(g 35)


Take note of the "Global-defs" and "Local-defs" Donkey menus.
The former shows you all the global definitions, including global
definitions created by lifting local definitions to the top level.
The latter is empty unless you are in the middle of evaluating a
local form, in which case it shows you which local values are currently
available.


(define f (local (...) (lambda (...) ...)))
is a way of making private variables for a function.
Why would we want to put the local outside the lambda?


Scope
=====

Given a variable, how can we determine where its value comes from?
One way is to simply evaluate the expression containing the variable until
we get around to evaluating the variable; this answers our question but
doesn't provide any intuition.

We can determine where a variable is bound (where that variable gets its
value) by simply looking at the expression containing the variable.

We know of three binding constructs (mechanisms for creating variables and
assigning them values):

 * function parameters
 * global definitions
 * local definitions

Given a use of a variable in an expression, if you want to know how that
variable gets its value, and from where, then you can simply look lexically
outward; you will eventually reach a local definition of that variable, or
a use of that variable as a function parameter, or will get to the
top-level expression (in which case the variable's value is found in the
global environment -- a global definition sets its value).

What result is returned by this expression?  Try evaluating it by hand
first, then use Donkey to see what is going on.

(define x 5)
(local ((define y x)
        (define x 7))
  (+ x y))



Capture
=======

Hand-evaluate the following code with a partner.  What goes wrong?

(define length
  (lambda (l)
    (if (null? l)
        0
        (+ 1 (length (cdr l))))))

(define foo
  (lambda (f l)
    ;; an approximation to the true length that returns 0, 1, or infinity
    (local ((define length (cond
			     ((null? l) 0)
			     ((null? (cdr l)) 1)
			     (else +inf.0))))
      (<= (f l) length))))

(foo length (cons 'a null))

Capture occurs when the same name is used for variables, and one gets
substituted into the scope of the other.  In a lexically-scoped language
like Scheme, capture is always an error.

Now step through the code using Donkey.  What does Donkey do to avoid the
capture error?