, Scope and Abstract Functions...
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.
...
...
<PRE>
...
...
...
A local definition
expression introduces a new local scope--the names in the definitions are defined
within visible both within the bodies of the definitions and within the
local's body.
| Wiki Markup |
|---|
\(local \[_definitions_ …\]
_body_\) |
Note that the use of square brackets
here is equivalent
to parentheses
body. If a local name collides with (matches) a name in the surrounding program, the local name shadows the enclosing name; i.e., the matching name in the enclosing program is invisible within the local expression; only the matching local name can be accessed. The same shadowing phenomenon 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
...
| HTML |
|---|
<TABLE bgColor=#efefdf border=1 class="MsoBodyTextIndent"> |
...
Finding the maximum element of a list
...
...
.
Let's consider the problem of finding the maximum number in a list .
In general, there's an issue answering "What is the maximum number in
an empty list?"
To simplify the problem for today's goal, we'll only use non-negative
numbers, and define the maximum number of the empty list to be zero.
(Alternatively, we could write the function
only for non-empty lists.)
Develop the function without using local. For the
purposes of this exercise, do not use any helper functions, nor the
built-in Scheme function max.
Stylistically what don't (or shouldn't) you like about this
code?
Develop the function using local. Again, don't use a
helper function, or max.
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 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
)
... n)
for various values of
n
.
Can you write a mathematical equation that
describes this number of calls?
(This exercise is a small example of what you'd learn to do
in COMP 280.)
Develop a third version that does not use
,
but does use Scheme's built-in
function.
Is this version relatively efficient?
In general, you can take any program using
,
and turn it into an equivalent program without
.
Using local doesn't let us write programs which were impossible
before, but it does let us write them better.
| HTML |
|---|
<TABLE bgColor=#efefdf border=1 class="MsoBodyTextIndent"> |
List of descending numbers exercises
We'll develop functions returning the list of positive numbers 1…
n
(left-to-right), given
n
as input.
Develop a function that, given
n
and
i
normally
returns the list of length
i
of numbers
up to
n
:
(list
n
-(
i
-1) …
n
-1
n
)
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
.
Your nums-upto-help repeatedly passed one argument
unchanged to its recursive call.
I.e., it's an
invariant
argument.
Rewrite your function, adding a helper, hidden by local,
which avoids having an invariant argument.
Don't forget to include a contract and purpose for
this new local function, too.
Develop the function we really want:
(nums-upto 5) ⇒ (list 1 2 3 4 5)
Use your nums-upto-help to do most of the work.
Edit your code to use local to hide the helper
nums-upto-help inside your main function
nums-upto.
Advice on when to use local
These examples point out the reasons why to use local:
| HTML |
|---|
<UL class="MsoBodyTextIndent"> |
| HTML |
|---|
<LI class="MsoBodyTextIndent"> |
Avoid code duplication. I.e., increase code reuse.
| HTML |
|---|
<LI class="MsoBodyTextIndent"> |
Avoid recomputation.
This sometimes provides dramatic benefits.
| HTML |
|---|
<LI class="MsoBodyTextIndent"> |
Avoid re-mentioning an unchanging argument.
| HTML |
|---|
<LI class="MsoBodyTextIndent"> |
To hide the name of helper functions.
| HTML |
|---|
<TABLE bgColor=#bfbfbf border=1> |
An Aside
While 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
or
packages
. As this one example shows,
even small programs can get a bit less clear when hiding lots of
helpers.
| HTML |
|---|
<LI class="MsoBodyTextIndent"> |
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:
| HTML |
|---|
<UL class="MsoBodyTextIndent"> |
| HTML |
|---|
<LI class="MsoBodyTextIndent"> |
| Wiki Markup |
|---|
; max-of-list: non-empty-list \-> number
\(define \(max\-of-list a-nelon\)
\(local \[\(define max-rest \(max-of-list \(rest a-nelon\)\)\)\]
\(cond \[\(empty? \(rest a-nelon\)\) \(first a-nelon\)\]
[else \(cond \[\(< \(first a-nelon\) max-rest\) max-rest\]
\[else \(first a-nelon\)\]\)]\)\)\) |
| HTML |
|---|
<TABLE bgColor=#efefdf border=1 class="MsoBodyTextIndent"> |
Question
What's wrong with this?
Make sure you don't put a local too early in your code.
| HTML |
|---|
<LI class="MsoBodyTextIndent"> |
| Wiki Markup |
|---|
; max-of-list: non-empty-list \-> number
\(define \(max\-of-list a-nelon\)
\(cond \[\(empty? \(rest a-nelon\)\) \(first a-nelon\)\]
[else \(local \[\(define max-rest \(max-of-list \(rest a-nelon\)\)\)
\(define first-smaller? \(< \(first a-nelon\) max-rest\)\)\]
\(cond \[first-smaller? max-rest\]
\[else \(first a-nelon\)\]\)\)]\)\) |
This isn't wrong, but the local definition of first-smaller?
is unnecessary. Since the comparison is only used once,
this 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 does a local evaluate? The following is one way to
understand it.
| HTML |
|---|
<OL class="MsoBodyTextIndent"> |
| HTML |
|---|
<LI class="MsoBodyTextIndent"> |
For each {{define}}d name in the list of definitions, rename it
something entirely unique, consistently through
the entire local.
| HTML |
|---|
<LI class="MsoBodyTextIndent"> |
Lift those defines to the top level, and erase the surrounding
local, leaving only the body-expression.
Example:
Observe how the rewriting makes it clear that there are really two
independent placeholders.
| Wiki Markup |
|---|
\(define x 5\)
\(local \[\(define x 7\)\]
x\) |
⇒
| Wiki Markup |
|---|
\(define x 5\)
\(local \[\(define x^ 7\)\]
x^\) |
⇒
(define x 5)
(define x^ 7)
x^
Example:
| Wiki Markup |
|---|
\(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 x)
(define z (+ x y))
(define x^ 7)
(define y^ x^)
(+ x^ y^ z)
As an equivalent way of looking at things, we can look at the original code
and ask which definition corresponds to each placeholder use.
The answer is simple -- it is always the closest (in terms of nestedness)
enclosing
binding
definition. We have three forms of binding:
| HTML |
|---|
<UL class="MsoBodyTextIndent"> |
| HTML |
|---|
<LI class="MsoBodyTextIndent"> |
Parameters of a function.
| HTML |
|---|
<LI class="MsoBodyTextIndent"> |
Local definitions.
| HTML |
|---|
<LI class="MsoBodyTextIndent"> |
"Global" definitions. (This is a special case of local definitions,
if we simply consider there to be an implicit local
around everything.)
| HTML |
|---|
<TABLE bgColor=#bfbfbf border=1 class="MsoBodyTextIndent"> |
local implementation
The actual way local is implemented is along these lines.
The interpreter keeps track of these bindings in an
environment
, which maps placeholder names to their values.
Then, an expression is evaluated in the context of the current
environment.
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.
| HTML |
|---|
<TABLE bgColor=#efefdf border=1 class="MsoBodyTextIndent"> |
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))
| Wiki Markup |
|---|
\(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)
| Wiki Markup |
|---|
\(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
.
| HTML |
|---|
<TABLE bgColor=#efefdf border=1 class="MsoBodyTextIndent"> |
More scoping exercises
In each of the following, determine which definition corresponds to
each placeholder usage.
As a result, first figure out without DrScheme what each example produces.
To do so, you may want to use
'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)
| Wiki Markup |
|---|
\(local \[\(define w 2\)
\(define x 4\)
\(define z 6\)\]
\(+ w x y z\)\) |
(+ w x y)
| Wiki Markup |
|---|
\(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)
| Wiki Markup |
|---|
\(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."
| Wiki Markup |
|---|
\(local [; my-odd?: natnum --> boolean
\(define \(my-odd? n\)
\(cond \[\(zero? n\) false\]
\[\(positive? n\) \(my-even? \(sub1 n\)\)\]\)\) |
| Wiki Markup |
|---|
; 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)
| Wiki Markup |
|---|
\(define \(f x\)
\(local \[\(define \(g x\) \(+ x y\)\)
\(define y 100\)\]
\(g \(g x\)\)\)\) |
| Wiki Markup |
|---|
\(local \[\(define x 30\)
\(define y 31\)
\(define \(g x\) \(* x y\)\)\]
\(g 20\)\) |
(g 20)
(f 20)
...
As a reminder, we've discussed filter.
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:
| Code Block |
|---|
; 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? (rest l)))]
[else
(filter keep? (rest l))])]))
|
As an alternative, we could note that the above definition repeats
the code
| Code Block |
|---|
(filter keep? …) |
.
I.e.,
is an invariant argument.
We could choose to avoid that, as follows:
| Code Block |
|---|
; 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 (rest l)))]
[else
(filter-helper (rest l))])]))]
(filter-helper l)))
|
| HTML |
|---|
<TABLE BORDER=1 BGCOLOR=#EFEFDF class="MsoBodyTextIndent"> |
| HTML |
|---|
<CAPTION class="MsoBodyTextIndent"> |
filter exercises
Using DrScheme'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
, define a
function that takes a list of numbers and returns a list of
all the positive numbers in that list.
...
We are familiar with writing functions such as the following:
| Code Block |
|---|
; double-nums : [number] -> [number]
; Given a list of numbers, return a 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 (rest a-lon)))]))
; lessthan3-nums : [number] -> [boolean]
; Given a list of numbers, return a 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 (rest a-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:
| Code Block |
|---|
; map : (X -> Y) [X] -> [Y]
(define (map f l)
(cond
[(empty? l) empty]
[(cons? l) (cons (f (first l)) (map f (rest l)))]))
; double-num : number -> number
(define (double-num n) (* 2 n))
; double-nums : [number] -> [number]
(define (double-nums a-lon) (map double-num a-lon))
; lessthan-3-nums : [number] -> [boolean]
(define (lessthan3-nums a-lon) (map (lambda (n) (< n 3))
a-lon))
|
map abstracts 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 understand map is by the following equation.
It describes what map does without the usually
extraneous details of how it does it.
| Code Block |
|---|
(map f (list x<sub>1</sub> … x<sub>n</sub>)) = (list (f x<sub>1</sub>) … (f x<sub>n</sub>))
|
| HTML |
|---|
<TABLE BORDER=1 BGCOLOR=#EFEFDF class="MsoBodyTextIndent"> |
| HTML |
|---|
<CAPTION class="MsoBodyTextIndent"> |
map exercises
Write double-nums using map and
local, without a global function
double-num.
Write double-nums using map and
lambda, without any named function like
double-num.
...
.
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 the function.
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 use local:
- Avoid code duplication. I.e., increase code reuse.
- Avoid recomputation.
This sometimes provides dramatic benefits. Avoid re-mentioning an unchanging argument. - To hide the name of helper functions. An aside: many programming languages (including Java) provide alternate mechanisms (such as
public/private attributes) for hiding helper functions and data which scale better to large programs and accomodate the unit testing of hidden functions (which local does not!). - 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:
| Code Block |
|---|
;; max-num: non-empty-list-of-number -> number
(define (max-num alon)
(local [(define max-rest (max-num (rest alon)))]
(cond [(empty? (rest alon)) (first alon)]
[else (if (<= (first alon) max-rest)
max-rest
(first alon))])))
|
Try running this example on any legal input (according to the contract). It blows up!
Make sure you don't put a local too early in your code.
| Code Block |
|---|
;; max-num: non-empty-list-of-number -> number
(define (max-num alon)
(cond [(empty? (rest alon)) (first alon)]
[else (local [(define max-rest (max-num (rest alon)))
(define first-smaller? (<=(first alon) max-rest))]
(if first-smaller? max-rest (first alon)))]))
|
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 reduction 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 _i to its name for a suitable choice of i. A good choice for i is simply the index (starting from 0) of this particular local evaluation in the course of the evaluation. The DrScheme stepper follows this convention. When renaming local variables,
make sure that you consistently change each defined name in the entire local expression.
2. Lift the modified 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. See Example 1 below.
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 explicit program text
Example 1
Observe how the rewriting makes it clear that there are two separate variables initially named x.
| Code Block |
|---|
(define x 5)
(local [(define x 7)] x)
|
=>
| Code Block |
|---|
(define x 5)
(define x_0 7)
x_0
|
=>
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.)
| Code Block |
|---|
(define x 5)
(local (define x 7) x)
|
=>
| Code Block |
|---|
(define x 5)
(local (define x_0 7) x_0)
|
=>
| Code Block |
|---|
(define x 5)
(define x_0 7)
x_0
|
=>
Example 2.
| Code Block |
|---|
(define x 5)
(define y x)
(define z (+ x y))
(local [(define x 7) (define y x)] (+ x y z))
|
=>
| Code Block |
|---|
(define x 5)
(define y 5)
(define z (+ x y))
(local [(define x 7) (define y x)] (+ x y z))
|
=>
| Code Block |
|---|
(define x 5)
(define y 5)
(define z (+ 5 y))
(local [(define x 7) (define y x)] (+ x y z))
|
=>
| Code Block |
|---|
(define x 5)
(define y 5)
(define z (+ 5 5))
(local [(define x 7) (define y x)] (+ x y z))
|
=>
| Code Block |
|---|
(define x 5)
(define y 5)
(define z 10)
(local [(define x 7) (define y x)] (+ x y z))
|
=>
| Code Block |
|---|
(define x 5)
(define y 5)
(define z 10)
(local [(define x_0 7) (define y_0 x_0)] (+ x_0 y_0 z))
|
=>
| Code Block |
|---|
(define x 5)
(define y 5)
(define z 10)
(define x_0 7)
(define y_0 x_0)
(+ x_0 y_0 z)
|
=>
| Code Block |
|---|
(define x 5)
(define y 5)
(define z 10)
(define x_0 7)
(define y_0 7)
(+ x_0 y_0 z)
|
=>
| Code Block |
|---|
(define x 5)
(define y 5)
(define z 10)
(define x_0 7)
(define y_0 7)
(+ 7 y_0 z)
|
=>
| Code Block |
|---|
(define x 5)
(define y 5)
(define z 10)
(define x_0 7)
(define y_0 7)
(+ 7 7 z)
|
=>
| Code Block |
|---|
(define x 5)
(define y 5)
(define z 10)
(define x_0 7)
(define y_0 7)
(+ 7 7 10)
|
=>
| Code Block |
|---|
(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.
Review
In Lectures 8-9, we developed the Scheme filter function, a functional that takes a unary predicate and a list as arguments. 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:
| Code Block |
|---|
;; filter : (X -> boolean) (list-of X) -> (list-of X)
;; Purpose: (filer p alox) returns the elements e of alox for which (p e) is true
(define (filter keep? alox)
(cond [(empty? alox) empty]
[(cons? alox) (if (keep? (first alox))
(cons (first alox) (filter keep? (rest alox)))
(filter keep? (rest alox)))]))
|
We can putatively improve the preceding definition by eliminating the repetition of the code (filter keep? (rest alox)):
| Code Block |
|---|
;; filter : (X -> boolean) (list-of X) -> (list-of X)
;; (filer p alox) returns the elements e of alox for which (p e) is true
(define (filter keep? alox)
(cond [(empty? alox) empty]
[(cons? alox)
(local [(define kept-rest (filter keep? (rest alox)))]
(if (keep? (first alox))
(cons (first alox) kept-rest)
kept-rest))]))
|
The refactoring of the first definition of filter given above is borderline. It does not improve the running time of the program since the duplicate calls appear in disjoint control paths. Which of the two preceding definitions is easier to understand? The answer is debatable; it is not clear that the "improved" definition is better.
Some functional programmers advocate performing yet another "optimization": introducing a recursive helper function in the body of filter because the keep? parameter is unnecessary in filter except as single a top-level binding. Since keep? never changes in any recursive call, it can be eliminated as a parameter in a helper function nested inside filter where the binding of keep? is visible. We are not persuaded that this revision is a good idea for two reasons. First, eliminating constant parameters from function calls is a low-level transformation that is best performed by a compiler. In many cases, it may degrade rather than improve efficiency. Second, the program with the helper function is harder to understand than either program above.
Note the preceding definitions of filter are not acceptable to DrScheme because the name filter collides with the Scheme library function named filter (which performs the same operation). If you want to run either of the preceding programs in DrScheme, you will have to rename filter (as say Filter).
Optional Exercise: rewrite filter in the following "optimized" form:
| Code Block |
|---|
(define (Filter keep? alox)
(local [(define (filter-help alox) ...]
(filter-help alox)))
|
Do not bother writing a contract, purpose statement, or template instantiation for this function since we recommend that you throw this code away after the lab is over. The name has been changed to Filter to avoid colliding with the Scheme library function named filter.
Exercises
- Load one of the more interesing Scheme programs you have written (such as HW2) into DrScheme. (If you did the preceding optional exercise, you can use this program.) Perform the "Check Syntax" command to identify where each variable is bound. 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.
- X Using the Scheme library function
filter, develop a function that takes a list of numbers and returns a list of all the positive numbers in that list.
The map functional
We are familiar with writing functions such as the following:
| Code Block |
|---|
;; double-nums : (list-of number) -> (list-of number)
;; (double-num (list e1 ... ek)) returns (list d1 ... dk) where each element di is twice ei.
(define (double-nums alon)
(cond [(empty? alon) empty]
[(cons? alon) (cons (* 2 (first alon)) (double-nums (rest alon)))]))
;; <3-nums : (list-of number) -> (list-of boolean)
;; (<3-nums (list e1 ... en)) returns (list b1 ... bn) where bi has the value (< ei 3)
(define (<3-nums alon)
(cond [(empty? alon) empty]
[(cons? alon) (cons (< (first alon) 3) (<3-nums (rest alon))))]))
|
These functions are very similar and can be written trivially using the Scheme library function map discussed in Lecture 9.
Exercises.
- Write
double-nums and <3-nums using map.
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 practice allows us to write shorter code that is also clearer and more understandable
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 value base as the result for the empty list and a function f to combine the elements of the list. The elements can be combined in two different ways: one associating to the right (foldr) and one associating to the left foldl. The following equations describe how these two form of combining work:
| Code Block |
|---|
(foldr f base (list x1 x2 ... xn)) = (f x1 (f x2 ... (f xn base))) [1]
(foldl f base (list x1 x2 ... xn)) = (f xn ... (f x2 (f x1 base))...) [2]
|
Many functions we've written fit this pattern, although this fact might not be obvious at first.
Exercises
- X Based upon the preceding equation ([1]), what should the following evaluate to? Think about them first, then try them in DrScheme (where
foldr is pre-defined). - (foldr + 5 (list -1 5 -3 4 2))
- (foldl + 5 (list -1 5 -3 4 2))
- (foldr - 5 (list -1 5 -3 4 2))
- (foldl - 5 (list -1 5 -3 4 2))
- (foldr cons empty (list -1 5 -3 4 2))
- (foldl cons empty (list -1 5 -3 4 2))
- (foldr append empty (list (list 1 2) (list 4) empty (list 8 1 2)))
- (foldr append empty (list (list 1 2) (list 4) empty (list 8 1 2)))
- X What is the contract for
foldr? For foldl? You should be able to determine this from the equations and the examples above.
(We also covered the typing of foldr in lecture.) Hint: First, determine the type of foldr and foldl assuming the input list is a list of numbers, and then generalize. - Using
foldr, define a function to compute the product of a list of numbers. Do the same for foldl. - Using
foldr, define map. (Also done in lecture.) Do the same for foldl. - Define the function
Foldr to satisfy equation (1) above. As you might expect, it follows the template for a function consuming a list. (It was also done in lecture.) Test your function against Scheme's built-in foldr to make sure they give the same results for the same inputs. - Define the function
Foldl to satisfy equation (2) above. As you might expect, it follows the template for a function consuming a list. Test your function against Scheme's built-in foldl to make sure they give the same results for the same inputs. - Define a function to compute whether all elements in a list of numbers are greater than 6. Write two version versions, one using
foldr and one using foldl, choosing suitable names (distinct from filter for each.
Then generalize both definitions to define filter. Are your two filter functions identical? Hint: look at computations that generate errors. - Define a function that, given a list of numbers, returns the sum of all the positive numbers in the list. Write two versions, one using
foldr and one using foldl. - Without using explicit recursion, develop a function
upfrom that, given i and n returns the list of length i of numbers up to n.
More examples
Here are a few more pre-defined abstract functions:
(andmap f (list x1 ... xn)) = (and (f x1) ... (f xn))(ormap f (list x1 ... xn)) = (or (f x1) ... (f xn))(build-list n f) = (list (f 0) ... (f (sub1 n)))
Exercises
The following can be defined using some combination of the pre-defined abstract functions.
- X Define a function that, given a list of numbers, determines whether all of the numbers in the list are even. Write two versions one using
foldr and one using foldl. - Define
andmap and ormap using foldr rather than recursion. Do the same using foldl.
Summary
The following table presents 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 | applies a function to each list element and reduces this list using and |
|---|
ormap | applies a function to each list element and reduces this list using or |
|---|
build-list | given a unary function f and a natural n, constructs (list (f 0) ... (f n)) |
|---|
foldr | associating to the right, reduces a list using the specified binary function and base case |
|---|
foldl | associating to the left, reduces a list using the specified binary function and base case |
|---|
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 find filter and map among
the easier ones to use at first.
On the other hand, foldr and foldl are more general
and take more practice to get comfortable with.
You will get practice on homeworks and the next two exams.
...
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 value base as the result for the empty list
and a function f to combine the first
element and the result on all the rest of the elements.
Combining all the elements means satisfying the following equation:
| Code Block |
|---|
(foldr f base (list x<sub>1</sub> x<sub>2</sub> … x<sub>n</sub>)) = (f x<sub>1</sub> (f x<sub>2</sub> … (f x<sub>n</sub> 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
and its arguments in a different order.
There we saw this is also equivalent to turning
our list template into an abstract function.
| HTML |
|---|
<TABLE BORDER=1 BGCOLOR=#EFEFDF class="MsoBodyTextIndent"> |
| HTML |
|---|
<CAPTION class="MsoBodyTextIndent"> |
foldr exercises
Based upon this equation, what should the following evaluate to?
Think about them first, then try them in DrScheme
(where
is pre-defined).
| Code Block |
|---|
(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 for foldr?
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.
Using foldr, define a function to compute
the product of a list of numbers.
Using foldr, define map.
Define the function my-foldr to 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
foldr to make sure they give the same results for
the same inputs.
If you have time…
Using foldr, define a function to compute
whether all elements in a list of numbers are greater than 6.
Then generalize this to using
to define
.
...
Here's a few more pre-defined abstract functions:
| Code Block |
|---|
(andmap f (list x<sub>1</sub> … x<sub>n</sub>)) = (and (f x<sub>1</sub>) … (f x<sub>n</sub>))
(ormap f (list x<sub>1</sub> … x<sub>n</sub>)) = (or (f x<sub>1</sub>) … (f x<sub>n</sub>))
(build-list n f) = (list (f 0) … (f (sub1 n)))
|
The following is a quick summary of the abstract functions mentioned
in this lab:
| HTML |
|---|
<ul class="MsoBodyTextIndent"> |
--
selects some elements from a list
–
applies a function to each list element
/
--
applies a function to each list element and combines the resulting booleans
–
constructs a list of the given length according to the given function
/
–
combines all elements of a list
| HTML |
|---|
<TABLE BORDER=1 BGCOLOR=#EFEFDF class="MsoBodyTextIndent"> |
| HTML |
|---|
<CAPTION class="MsoBodyTextIndent"> |
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
:
| Code Block |
|---|
(list <VAR>n</VAR>-(<VAR>i</VAR>-1) … <VAR>n</VAR>-1 <VAR>n</VAR>)
|
More concretely, e.g.,
| Code Block |
|---|
(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…
Define andmap, which computes
whether all elements in a list of booleans are true:
| Code Block |
|---|
(andmap f (list x<sub>1</sub> … x<sub>n</sub>)) = (and (f x<sub>1</sub>) … (f x<sub>n</sub>))
|
First, define it recursively following the list template, then
define it using
and
,
then using only
.
...
The mathematically inclined might have noticed that foldr
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:
| Code Block |
|---|
(foldl f base (list x<sub>1</sub> x<sub>2</sub> … x<sub>n</sub>)) = (f x<sub>n</sub> … (f x<sub>2</sub> (f x<sub>1</sub> base))…)
|
| HTML |
|---|
<TABLE BORDER=1 BGCOLOR=#EFEFDF class="MsoBodyTextIndent"> |
| HTML |
|---|
<CAPTION class="MsoBodyTextIndent"> |
foldl exercises
Based upon this equation, what should the following evaluate to?
Think about them, then try them in DrScheme
(where
is pre-defined).
| Code Block |
|---|
(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
.
Do
| Code Block |
|---|
(foldr + 0 <em>numlist</em>) |
and
| Code Block |
|---|
(foldl + 0 <em>numlist</em>) |
always give the same results?
Hint: Think back a couple labs.
Define the function
to satisfy the above
equation, testing it against Scheme's built-in
.
Hint: Use
.
If you've read ahead a few chapters:
Define my-foldl without using
.
Hint: Use an accumulator.
...
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:
| Code Block |
|---|
(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
|
| HTML |
|---|
<TABLE BORDER=1 BGCOLOR=#EFEFDF class="MsoBodyTextIndent"> |
| HTML |
|---|
<CAPTION class="MsoBodyTextIndent"> |
Tree exercises
If you have time…
Define a
-like function on btns.
Semi-challenge:
Define a
-like function on btns.
Hint: Whereas
on lists took a binary
function argument, this one needs a ternary function argument.
!! Access Permissions
...