Scope, local, and Abstract Functions

Instructions for students & labbies: Students use DrScheme, following the design recipe, on the exercises at their own pace, while labbies wander among the students, answering questions, bringing the more important ones to the lab's attention.

Quick Review of Scope

A function definition introduces a new local scope - the parameters are defined within the body.

• (define ( parameters ...) body )

A local expression introduces a new local scope--the names in the definitions are visible both within the bodies of the definitions and within the body. A new local name that collides with (matches) a name in the surrounding program shadows the enclosing name; i.e., the matching name in the enclosing program is invisible within the local expression. The same thing happens when a parameter name in a function definition collides with a name defined in the surrounding program.

• (local [ definitions ...] body )

Note that the use of square brackets [ ] here is equivalent to parentheses( ). The brackets help set off the definitions a little more clearly for readability.

In order to use local and the other features about to be introduced in class, you need to set the DrScheme language level to Intermediate Student.

Exercises

Finding the maximum element of a list.

Let's consider the problem of finding the maximum number in a list which is used an example in Lecture 7.

• Develop the function max-num without using local exactly as in lecture.

• Develop the optimized version of this function (call it opt-max-num) using local exactly as in lecture.

Try running each version on the following input (or longer ones):

(list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)

If it is convenient, use your up function from last lab to avoid typing long input lists like the preceding one.

What difference do you see?

For each version, determine approximately how many calls to your function is made for the input

(list 1 2 3 ... n)

for various values of n.

Which version is more efficient?

Note that you can write an efficient solution without using local; you can use an auxiliary function instead. The auxiliary function takes the expression appearing on the right hand side of the local definition as an argument. Quickly write this version of ma function including a contra

In general, you can take any program using local, and turn it into an equivalent program without local.
Using local doesn't let us write programs which were impossible before, but it does let us write them more cleanly and concisely.

Generating lists of ascending numbers

Retrieve your code for the up function and its helper upfrom from last lab.

Rewrite this program so that the helper function upfrom is hidden inside a local} expression and takes only one argument since the upper bound argument is available as the parameter to the enclosing definition of {{up.

Don't forget to revise the contract and purpose for the improved upFrom function.

Advice on when to use local

These examples point out the reasons why to uselocal:

1. Avoid code duplication. I.e., increase code reuse.
2. Avoid recomputation.
   This sometimes provides dramatic benefits. Avoid re-mentioning an unchanging argument.
3. To hide the name of helper functions.An AsideWhile important conceptually, most programming languages (including Scheme) provide alternate mechanisms for this which scale better to large programs. These mechanisms typically have names like modules orpackages. As this one example shows, even small programs can get a bit less clear when hiding lots of helpers.
4. Name individual parts of a computation, for clarity.On the other hand, don't get carried away.

Here are two easy ways to misuse local:

max-num: non-empty-list -> number
(define (max-num a-nelon)
  (local [(define max-rest (max-num (rest a-nelon)))]
    (cond [(empty? (rest a-nelon)) (first a-nelon)]
          [else  (if (<= (first a-nelon) max-rest) 
                     max-rest
                     (first a-nelon))])))

Question: What's wrong with this?

Make sure you don't put a local too early in your code.

max-num: non-empty-list -> number
(define (max-num a-nelon)
  (cond [(empty? (rest a-nelon)) (first a-nelon)]
        [else  (local [(define max-rest (max-num (rest a-nelon)))
                       (define first-smaller? (<=(first a-nelon) max-rest))]
                  (if first-smaller? max-rest (first a-nelon)))]))

This isn't wrong, but the local definition of first-smaller? is unnecessary. Since the comparison is only used once, this refactoring is not a case of code reuse or recomputation. It provides a name to a part of the computation, but whether that improves clarity in this case is a judgement call.

Scope and the semantics of local

How are local expressions evaluated? The following rule describes how to evaluate a local expression when it is the leftmost un-evaluated expression.

1. Rename each defined name in the local expression by appending

to its name for a suitable choice of number i to the name. A good choice for i is simply the index of this local evaluation starting from 0.
make sure that you consistently change each defined name in the entire {{local} expression.

2. Lift the modifed define} statements from the {{local expression to the top level (at the end of top level program), and replace the local expression by it body (which has been transformed by renaming).

This two-part process is technically a single step in an evaluation. But you can make each part of the rule a separate step if you choose.

Evaluating Program Text

Now that we have extended our hand-evaluation model to include the definitions forming a program, we can describe how to handle define statements that bind ordinary variables rather than functions. The right hand sides of define} statements are not necessarily values. When evaluating a program, you must always reduce the leftmost expression that is not a value; in some cases this expression may be part of the right hand size of a {{define.

Sample evaluations involving local and bexplicit program text

Example 1

Observe how the rewriting makes it clear that there are two separate variables initially named x.

(define x 5)
(local [(define x 7)] x)

=>

(define x 5)
(define x_0 7)
x_0

=>

7

This evaluation can also be written in a slightly longer form where the evaluation of a local expression takes two reduction steps rather than one. (The one-step form is better technically, but the two-step form is acceptable in the context of an introductory course.)

(define x 5)
(local (define x 7) x)

=>

(define x 5)
(local (define x_0 7) x_0)

=>

(define x 5)
(define x_0 7)
x_0

=>

7

Example 2.

(define x 5)
(define y x)
(define z (+ x y))
(local [(define x 7) (define y x)] (+ x y z))

=>

(define x 5)
(define y 5)
(define z (+ x y))
(local [(define x 7) (define y x)] (+ x y z))

=>

(define x 5)
(define y 5)
(define z (+ 5 y))
(local [(define x 7) (define y x)] (+ x y z))

=>

(define x 5)
(define y 5)
(define z (+ 5 5))
(local [(define x 7) (define y x)] (+ x y z))

=>

(define x 5)
(define y 5)
(define z 10)
(local [(define x 7) (define y x)] (+ x y z))

=>

(define x 5)
(define y 5)
(define z 10)
(define x\_0 7) 
(define y\_0 x\_0)
(+ x\_0 y\_0 z)

=>

(define x 5)
(define y 5)
(define z 10)
(define x\_0 7) 
(define y\_0 7)
(+ x\_0 y\_0 z)

=>

(define x 5)
(define y 5)
(define z 10)
(define x\_0 7) 
(define y\_0 7)
(+ 7 y\_0 z)

=>

(define x 5)
(define y 5)
(define z 10)
(define x\_0 7) 
(define y\_0 7)
(+ 7 7 z)

=>

(define x 5)
(define y 5)
(define z 10)
(define x\_0 7) 
(define y\_0 7)
(+ 7 7 10)

=>

(define x 5)
(define y 5)
(define z 10)
(define x\_0 7) 
(define y\_0 7)
24

Note: {} is a function of an arbitrary number of numbers in Scheme. Hence ( 7 7 10) reduces to 24 in a single step. The longer form of this evaluation adds an extra step in lifiting the local.

If any aspect of hand evaluation confuses you, try running examples in DrScheme using the stepper.

DrScheme provides an easy way to look at this: the Check Syntax button. Clicking on this does two things. First, it checks for syntactic correctness of your program in the definitions window. If there are errors, it reports the first one. But, if there aren't any, it then annotates your code with various colors and, when you move your cursor on top of a placeholder, draws arrows between placeholder definitions and uses.

Scoping Exercise

What does the following code do? Explain it in terms of the evaluation rule above.

(define growth-rate 1.1)


(define (grow n)
(* n growth-rate))
(local (define growth-rate 1.3)
(grow 10))

(grow 10)

Confirm your understanding with DrScheme, with the Check Syntax button, and by evaluating the code.

Is the following code essentially different from the previous example? Why or why not?

(define growth-rate 1.3)


(define (grow n)
(local (define growth-rate 1.1)
(* n growth-rate)))


(grow 10)

Once again, confirm your understanding with DrScheme.

In each case, grow "knows" which placeholder named growth-rate was in scope when it was defined, because that knowledge is part of grow's closure.

More scoping exercises

In each of the following, determine which definition corresponds to each placeholder usage.

As a result, first figure out without DrSchemewhat each example produces. To do so, you may want to use local's hand-evaluation rules above.
Then confirm your results by using DrScheme.

(Note - Some examples give errors about unbound placeholders.)

(define w 1)
(define x 3)
(define y 5)

(local [(define w 2)
(define x 4)
(define z 6)]
(+ w x y z))


(+ w x y)

(define w 1)
(define x 3)
(define (test x y)
(local [(define w 2)
(define x 4)
(define z 6)]
(+ w x y z))))

(test 8 3)
(test x w)
(test w x)

(define x 1)
(define y 1)
(local [(define x 2)
(define y x)]
(+ x y))
(+ x y)

Here is an example of mutually recursive functions following the template for natural numbers.
It is motivated by the observation "a positive number n is even if n-1 is odd, a positive number n is odd if n-1 is even, and 0 is even."

(local [; my-odd?: natnum --> boolean
(define (my-odd? n)
(cond (zero? n)     false
(positive? n) (my-even? (sub1 n))))

; my-even?: natnum --> boolean
(define (my-even? n)
(cond (zero? n)     true
(positive? n) (my-odd? (sub1 n))))]


; Now, the body of the local:
(my-odd? 5))


; Outside the local:
(my-odd? 5)

Note that the two local functions are in each others' closure; they will always call each other, no matter how you define other
placeholders with the same names my-even?. Also note that this is an example of mutually recursive functions, where the mutual recursion does not result from a mutually recursive data structure.

(define x 1)
(define y 2)


(define (f x)
(local [(define (g x) (+ x y))
(define y 100)]
(g (g x))))


(local [(define x 30)
(define y 31)
(define (g x) (* x y))]
(g 20))


(g 20)
(f 20)

Review

As a reminder, we've discussedfilter.
Starting from several examples using specific predicates,
we noticed a great deal of similarity.
By abstracting away that similarity into a function parameter,
we obtained the following definition:

; filter : (X ->boolean) [X] -> [X] ; Purpose: Returns a list like the one given, except with those ; elements not passing the given predicate test removed. (define (filter keep? l) (cond [(empty? l) empty] [(cons? l) (cond [(keep? (first l)) (cons (first l) (filter keep? (restl)))] [else(filter keep? (restl))])]))

As an alternative, we could note that the above definition repeats
the code
(filter keep? ...)
.
I.e.,keep?
is an invariant argument.
We could choose to avoid that, as follows:

; filter : (X ->boolean) [X] -> [X] ; Returns a list like the one given, except with those ; elements not passing the given predicate test removed. (define (filter keep? l) (local [(define (filter-helper l) (cond [(empty? l) empty] [(cons? l) (cond [(keep? (first l)) (cons (first l) (filter-helper (restl)))] [else(filter-helper (restl))])]))] (filter-helper l)))

filterexercises

UsingDrScheme's "Check Syntax" feature to identify
where each variable is bound in the second definition.
Recall that when you put your cursor above a binding instance,
it will draw arrows to the uses, and when you put your
cursor above a use, it will draw an arrow to its binding instance.

Using either definition of
filter
, define a
function that takes a list of numbers and returns a list of
all the positive numbers in that list.

mapReview
We are familiar with writing functions such as the following:

;double-nums : [number] -> [number] ; Given a list of numbers,returna list of ; numbers that are twice the value of the corresponding items in ; the original list. (define (double-nums a-lon) (cond [(empty? a-lon) empty] [(cons? a-lon) (cons (\* 2 (first a-lon)) (double-nums (resta-lon)))])) ; lessthan3-nums : [number] -> [boolean] ; Given a list of numbers,returna list of ; booleans that indicate whether the corresponding items in ; the original list are less than 3. (define (lessthan3-nums a-lon) (cond [(empty? a-lon) empty] [(cons? a-lon) (cons (< (first a-lon) 3) (lessthan3-nums (resta-lon)))]))

Since these functions are so similar, we'd like to package together the
similar parts and separate out the different parts. We'll "package"
the similar parts as a new function that can take either of the
"different" parts as an argument that tells us what to do:

; map : (X -> Y) [X] -> [Y] (define (map f l) (cond [(empty? l) empty] [(cons? l) (cons (f (first l)) (map f (restl)))])) ;double-num : number -> number (define (double-num n) (* 2 n)) ;double-nums : [number] -> [number] (define (double-nums a-lon) (mapdouble-num a-lon)) ; lessthan-3-nums : [number] -> [boolean] (define (lessthan3-nums a-lon) (map (lambda (< n 3)) a-lon))

mapabstracts the general idea of "computing
a new element from each old element and building a list of the new
elements" away from what specifically you are computing from each
element.

Another way to understandmapis by the following equation.
It describeswhatmapdoes without the usually
extraneous details ofhowit does it.

(map f (list x₁ ... x_n)) = (list (f x₁) ... (f x_n))

mapexercises

Writedouble-numsusingmapand
local, without aglobalfunction
double-num.

Writedouble-numsusingmapand
lambda, without any named function like
double-num.

The Big Picture
Abstract functions are both powerful and convenient.
By using abstract functions to group all the common similar elements
of many functions, we can concentrate on what's different.
This allows us to write shorter code that is also clearer and more
understandable.

The examples in this lab are certainly not the only abstract functions,
but they are among those that are particularly useful because they
correspond to common list computations.
Because Scheme has lists built in and since these functions are so useful,
Scheme has them pre-defined.

Usually, using abstract functions takes the place of following our
standard templates. So, what happens to our design recipes? In the short term, while you are still getting used to abstract functions,
we strongly recommend that you first follow the design recipe, and then
go back and edit your code to use abstract functions where applicable.
In the long term, you will learn to identify common patterns before you
actually write code and be able to go directly to writing the shorter
versions using abstract functions.
You will probably findfilterandmapamong
the easier ones to use at first.
On the other hand,foldrandfoldlare more general
and take more practice to get comfortable with.
You will get practice on homeworks and the next two exams.

foldr
We have written many functions to combine elements of a list, e.g.,
to sum the numbers in a list and to find the maximum element in a list.
In each, we have some valuebaseas the result for the empty list
and a functionfto combine the first
element and the result on all the rest of the elements.
Combining all the elements means satisfying the following equation:

(foldr f base (list x₁ x₂ ... x_n)) = (f x₁ (f x₂ ... (f x_n base)))

Many functions we've written fit this pattern, although
this might not be obvious at first.

This function was discussed in class, but with the name
fun-for-l
and its arguments in a different order.
There we saw this is also equivalent to turning
our list template into an abstract function.

foldrexercises

Based upon this equation, what should the following evaluate to?
Think about them first, then try them inDrScheme
(where
foldr
is pre-defined).
(foldr + 0 (list -1 5 -3 4 2)) (foldr - 0 (list -1 5 -3 4 2)) (foldr cons empty (list -1 5 -3 4 2)) (foldr append empty (list (list 1 2) (list 4) empty (list 8 1 2)))

What is the contract forfoldr?
You should be able to determine this from the equation and
examples above.
First ask yourself the question assuming the input list
is a list of numbers, then generalize.

Usingfoldr, define a function to compute
the product of a list of numbers.

Usingfoldr, definemap.

Define the functionmy-foldrto satisfy the
above equation. As you might expect, it follows the template
for a function consuming a list.
Test your function against Scheme's built-in
foldrto make sure they give the same results for
the same inputs.

If you have time... Usingfoldr, define a function to compute
whether all elements in a list of numbers are greater than 6.
Then generalize this to usingfoldr
to define
filter
.

More examples

Here's a few more pre-defined abstract functions:

(andmap f (list x₁ ... x_n)) = (and (f x₁) ... (f x_n)) (ormap f (list x₁ ... x_n)) = (or (f x₁) ... (f x_n)) (build-list n f) = (list (f 0) ... (f (sub1 n)))

The following is a quick summary of the abstract functions mentioned
in this lab:

filter
-
selects some elements from a list

map
-
applies a function to each list element

andmap
/ormap
-
applies a function to each list element and combines the resulting booleans

build-list
-
constructs a list of the given length according to the given function

foldr
/foldl
-
combines all elements of a list

Exercises

The following can be defined using some combination of
the pre-defined abstract functions.

Define a function that, given a list of numbers, returns
the sum of all the positive numbers in the list.

Define a function that, given a list of anything, determines
whether all of the numbers in the list are even.

If you have time... (This is from the last lab, but use abstract functions this time,
and then compare the function to the one you wrote last week.)
Develop a function that, given n and i normally
returns the list of length i of numbers
up to n :
(list <VAR>n</VAR>-(<VAR>i</VAR>-1) ... <VAR>n</VAR>-1 <VAR>n</VAR>)More concretely, e.g.,
(nums-upto-help 5 0) ? empty (nums-upto-help 5 2) ? (list 4 5) (nums-upto-help 5 5) ? (list 1 2 3 4 5) (nums-upto-help 6 5) ? (list 2 3 4 5 6) (nums-upto-help 7 5) ? (list 3 4 5 6 7)

For simplicity, you may assume that
i = n .
This should just follow the template for
natural numbers on i .

If you have time... Defineandmap, which computes
whether all elements in a list of booleans are true:
(andmap f (list x₁ ... x_n)) = (and (f x₁) ... (f x_n))First, define it recursively following the list template, then
define it using
foldr
andmap
,
then using onlyfoldr
.

foldl
The mathematically inclined might have noticed thatfoldr

groups the binary operations right-associatively. Thus the "r" in the name.
What if we want to group left-associatively?
Well, we also have the following:

(foldl f base (list x₁ x₂ ... x_n)) = (f x_n ... (f x₂ (f x₁ base))...)

foldlexercises

Based upon this equation, what should the following evaluate to?
Think about them, then try them inDrScheme
(where
foldl
is pre-defined).
(foldl + 0 (list -1 5 -3 4 2)) (foldl - 0 (list -1 5 -3 4 2)) (foldl cons empty (list -1 5 -3 4 2)) (foldl append empty (list (list 1 2) (list 4) empty (list 8 1 2)))Compare the results to those for
foldr
.

Do
(foldr + 0 <em>numlist</em>)and
(foldl + 0 <em>numlist</em>)always give the same results?
Hint: Think back a couple labs.

Define the function
my-foldl
to satisfy the above
equation, testing it against Scheme's built-in
foldl
.
Hint: Usereverse
.

If you've read ahead a few chapters:
Definemy-foldlwithout using
reverse
.
Hint: Use an accumulator.

Other types

Abstract functions are also quite useful. Scheme has lists and
their abstract functions built-in, so they get more attention,
but the ideas transfer to trees perfectly well.

For example, one definition of binary tree is the following:
(define-struct node (n left right)) ; A binary tree of numbers (btn) is ; - empty ; - (make-node n l r) ; where n is a number and l,r are btns

Tree exercises

If you have time...

Define a
map
-like function on btns.

Semi-challenge: Define afoldr
-like function on btns.
Hint: Whereasfoldr
on lists took a binary
function argument, this one needs a ternary function argument.

!! Access Permissions

• Set ALLOWTOPICCHANGE = Main.TeachersComp211Group