Scope and Abstract

...

Function

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.

...

Is this version relatively efficient?
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 better.

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

...

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

≤

...

n

...

.
This should just follow the template for
natural numbers on

...

i

...

.

...

Yournums-upto-helprepeatedly help repeatedly passed one argument
unchanged to its recursive call.
I.e., it's an

...

invariant

...

argument.

Rewrite your function, adding a helper, hidden bylocalby 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 yournums-upto-helpto do most of the work.

...

Edit your code to use local to uselocalto hide the helper
nums-upto-helpinside your main function
nums-upto.

...

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.

...

1. Avoid re-mentioning an unchanging argument.

...

2. To hide the name of helper functions.

...

An Aside

...

1. An AsideWhile important conceptually, most programming languages (including

...

1. Scheme) provide alternate mechanisms for this which scale better to

...

1. large programs. These mechanisms typically have names like

...

modules

...

or

...

packages

...

1. modules orpackages. As this one example shows,

...

1. even small programs can get a bit less clear when hiding lots of

...

1. helpers.

...

...

1. Name individual parts of a computation, for clarity.

...

1. On the other hand,

...

1. don't get carried away

...

1. .

Here are two easy ways to misuselocalmisuse local:

...

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)

...

)

...

])))

...

Question

...

: What's wrong with this?

...

...

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

...

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 offirstof 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 alocalevaluatealocal evaluate? The following is one way to
understand it.

...

...

For each {{ define }}d name in the list of definitions, rename it
something entirely unique, consistently through
the entirelocal.

...

entire local. 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.:

(define x 5)

...

(local (define x 7)

...

x)

?⇒

(define x 5)

...

(local (define x^ 7)

...

x^)

?⇒

(define x 5)

...

(define x^ 7)

...

x^

Example:

...

(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 askwhich definitioncorresponds 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:

...

1. Parameters of a function.

...

2. Local definitions.

...

2. "Global" definitions. (This is a special case of local definitions,

...

1. if we simply consider there to be an implicitlocal

...

1. around everything.)

...

1. local implementation

...

...

The actual waylocalis 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: theCheck 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.

HTMLcode
(define growth-rate 1.1)

...

(define (grow n)

...

(* n growth-rate))

...

(local (define growth-rate 1.3)

...

(grow 10))

...

(grow 10)
HTML

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

...

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

HTMLcode
(define growth-rate 1.3)

...

(define (grow n)

...

(local (define growth-rate 1.1)

...

(* n growth-rate)))

...

(grow 10)

...

html

Once again, confirm your understanding with DrScheme.

...

In each case, grow "knows" which placeholder namedgrowthnamed growth-ratewas rate was in scope when it was defined, because that knowledge is part ofgrowof grow's

...

closure

...

.

...

More scoping exercises

...

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

As a result, first figure outwithout 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.)

Code Block
HTML
HTML
HTML
(define w 1)

...

(define x 3)

...

(define y 5)

...

Code Block
(local

...

[(define w 2) (define x 4) (define z 6)

...

] (

...

+ w x y z))

...

(+ w x y)
HTML
HTML
HTML
HTML

...

Code Block
(define w 1) (define x 3) (define (test x y) (local

...

[(define w 2) (define x 4) (define z 6)

...

] (

...

+ w x y z))))

Code Block
(test 8 3)

...

(test x w)

...

(test

...

w x)

Code Block
(define x 1) (define y 1) (local

...

[(define x 2) (define y x)

...

] (

...

+ x y)) (

...

+ x y)
HTML
HTML
HTML

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."

...

Code Block
(local

...

[; my-odd?: natnum

...

--> boolean (define (my-odd? n) (cond

...

(zero?

...

n) false (positive? n) (my-even? (sub1 n))

...

))

Code Block
; 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)

...

html

Note that the two local functions are in each others' closure; they
willalwayscall will always call each other, no matter how you define other
placeholders with the same namesmynames 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.

Code Block
HTML
HTML
HTML
(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:

...

Wiki Markup

; 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|(empty? l) empty] \[(cons? l) (cond [(keep? (first l)) (cons (first l) (filter-helper (restl)))|(keep? (first l)) (cons (first l) (filter-helper (restl)))] [else(filter-helper (restl))|else(filter-helper (restl))])\]))\] (filter-helper l)))

...

)

filterexercises

...

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.

...

Anchor
map_Review map_Review

mapReview

...

We are familiar with writing functions such as the following:

...

(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.

...

Anchor
The_Big_Picture The_Big_Picture

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.

...

Anchor
foldr foldr

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:

...

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.

...

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
.

...

Anchor
More_examples More_examples

More examples

...

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

...

filter
-
selects some elements from a list

...

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.

...

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

...

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
.

...

Anchor
foldl foldl

foldl

...

The mathematically inclined might have noticed thatfoldr

...

(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.

...

...

Anchor
Other_types Other_types

Other types

...

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