CS2500 Lecture 17

USES OF LOCAL

CS2500 1
Recap: local
● Yesterday, we saw how local can simplify our functions, and
hide helper functions that we don't really want visible at the
"global" level. But local can actually do much more. First let's
start with a warmup problem.

CS2500 2
What is the value of the following expression?

(define X 1)
(define Y 3)
(define Z (local [(define X 10)
(define Y 20)]
(local [(define X 30)]
(+ X Y))))
(+ X Z)

CS2500 3
Scope
Let's turn to ISL. Let's suppose I say...

(define (f x)
(+ x 2))

(f 3)
(+ x 2)

Where is x valid? What is its scope? Just within the function.

CS2500 4
Exercise
Use build-list to design a function that computes the first n
double-squares, or numbers that are twice as large as perfect
squares.

CS2500 5
; double-squares : Nat -> [List-of Nat]
; produce the first n double squares
(check-expect (double-squares 0) '())
(check-expect (double-squares 1) (list 0))
(check-expect (double-squares 4) (list 0 2 8 18))
(define (double-squares n)
(local [; double-square : Nat -> Nat
; The nth double square
(define (double-square n)
(* 2 (sqr n)))]
(build-list n double-square)))

CS2500 6
Design recipe for local
Often, we use local because we want to use a list abstraction ( map , filter , etc).
Thus, we'll describe the design recipe in terms of a problem that accepts a list.

We'll use an example of designing add-3-to-all , which accepts a [List-of

Number] and adds 3 to every number in the list.

CS2500 7
Step #1
1. Start with the first three steps of the design recipe for your outer
function.
; add-3-to-all : [List-of Number] -> [List-of Number]
; Adds 3 to every number
(check-expect (add-3-to-all '()) '())
(check-expect (add-3-to-all (list 0)) (list 3))
(check-expect (add-3-to-all (list -7 2.3)) (list -4
5.3))

CS2500 8
Step #2
2. Write a "stub" function for your main function that uses a local

(define (add-3-to-all lon)

(local [???
???]
(abstraction ???)))

CS2500 9
 Step #3
3. Decide which list abstraction is appropriate for your problem. Look at the
signatures of the list abstractions, see which one fits. Copy down its general
signature, and then fill in the dots.
(define (add-3-to-all lon)
(local [???
???]
; (X Y) [X -> Y] [List-of X] -> [List-of Y]
; X is Number
; Y is Number
; [Number -> Number] [List-of Number] -> [List-of Number]
(map ??? lon)))

CS2500 10
 Step #4
Design any functions you need inside the body of the local . Follow the full design
recipe, except that any tests have to be written in English.
(define (add-3-to-all lon)
(local [; add-3 : Number -> Number
; Adds 3 to a number
; Given 4, should return 7
(define (add-3 n)(+ n 3))]
; (X Y) [X -> Y] [List-of X] -> [List-of Y]
; X is Number
; Y is Number
; [Number -> Number] [List-of Number] -> [List-of Number]
(map add-3 lon)))

CS2500 11
local
● Now, the question is when should you use local ?
● What does it buy you?
● How does it help?
● Essentially, there are four reasons why local helps.

CS2500 12
Hiding helper functions

● Often, when using a list abstraction, we need a custom helper

function.
● Before local , this helper function needed to be written at the
"top level" of your program, making the code harder to read.
● In particular, this helper function may not be something you
want other people who use your code to call, but if it's a the top
level, it's visible.
● The first use of local is to "hide" these helper functions.

CS2500 13
(; A StringOrFalse (SoF) is one of:
; - String
; - #false
; Interpretation: A string, or #false if none exists
(define SOF-1 "hello")
(define SOF-2 "yo")
(define SOF-3 #false)

(define (sof-temp sof)

(...(cond [(string? sof) (... sof ...)]
[(boolean? sof) ...])))

CS2500 14
; shortest-string : [List-of String] -> SoF
; Returns the (first) shortest string, or #false if given ‘()
(check-expect (shortest-string '()) #false)
(check-expect (shortest-string (list "a")) "a")
(check-expect (shortest-string (list "a" "b" "c")) "a")
(check-expect (shortest-string (list "abc" "b" "cde")) "b")

CS2500 15
(define (shortest-string los)
(local [; String SoF -> SoF
; Combines the two, returning the shortest string
; if given "foo" and false, returns "foo"
; if given "foo" and "bar", returns "foo"
; if given "foo" and "b", returns "b"
(define (combine-shortest str sof)
(cond [(string? sof)
(if (<= (string-length str)
(string-length sof))
str sof)]
[(boolean? sof) str]))]
(foldr combine-shortest #false los)))

CS2500 16
Hiding helper functions
● Notice here that the combine-shortest function isn't really
useful outside of this context.
● It's better form to "hide" it in this way, and just expose the
shortest-string function to clients.

CS2500 17
Using context
● Recall that functions have no memory. They need to be given all of
the information they need to do their job.
● Before local, this information had to the passed in as an argument
● Using list abstractions prevents us from doing this in many
occasions because they have specific signatures
● But with local , functions can be defined inside of other functions,
meaning they have access to arguments passed into the outside
function.
● So, the second use of local is to enable list abstractions to be used
when they otherwise couldn't.

CS2500 18
Exercise
● Design a function usd->eur that accepts a [List-of Number]
representing prices in USD and a Number representing the
USD-EUR exchange rate, and converts each amount to EUR.

CS2500 19
Exercise
● Design a function usd->eur that accepts a [List-of Number]
representing prices in USD and a Number representing the
USD-EUR exchange rate, and converts each amount to EUR.

CS2500 20
; usd->eur : [List-of Number] Number -> [List-of Number]
; Converts USD to EUR with the given exchange rate
(check-expect (usd->eur '() 2.0) '())
(check-expect (usd->eur (list 1 2 3) 2.0) (list 2.0 4.0 6.0))
(define (usd->eur lon rate)
(local [; convert : Number -> Number
; Converts the USD amount to EUR
; If rate is 7.0, given 1.0 would produce 7.0
(define (convert n) (* n rate))]
(map convert lon)))

CS2500 21
Clarifying code
● Sometimes, your functions get quick complex, and you often
want to convey to the reader what you're doing.
● Example: the function slope that accepts two Positions and
returns a Number representing the slope of the line defined by
those two points.

CS2500 22
; A Position is a (make-posn Real Real)
; Interpretation: a 2d position
(define POSITION-0_0 (make-posn 0 0))
(define POSITION-1_2 (make-posn 1 2))
(define (position-temp p)
(... (posn-x p) ...(posn-y p) ...))
; slope : Position Position -> Number
; Calculates the slope of the line connecting the two points
(check-expect (slope POSITION-1_2 POSITION-0_0) 2.0)
(define (slope p1 p2)
(/ (- (posn-y p2) (posn-y p1))
(- (posn-x p2) (posn-x p1))))

CS2500 23
; slope/better : Position Position -> Number
; Calculates the slope of the line connecting the two points
(check-expect (slope/better POSITION-1_2 POSITION-0_0) 2.0)
(define (slope/better p1 p2)
(local [(define DELTA-Y (- (posn-y p2) (posn-y p1)))
(define DELTA-X (- (posn-x p2) (posn-x p1)))]
(/ DELTA-Y DELTA-X)))

CS2500 24
Efficiency
● The fourth use of local is somewhat subtle
● Sometimes, we want to remember the values of previous
computations so they do not need to be computed again
● This can increase efficiency
● Let's see an example of this

CS2500 25
; A [NEList-of X] is one of:
; - (cons X '())
; - (cons X [NEList-of X])
(define NELOX-1 (cons 1 '()))
(define NELOX-2 (cons 2 NELOX-1))
(define (nelox-temp nelox)
(...(cond [(empty? (rest nelox))(... (first nelox) ...)]
[(cons? (rest nelox))
(...(first nelox) ...
...(nelox-temp (rest nelox)) ...)])))

CS2500 26
; mymax : [NEList-of Number] -> Number
; Finds the biggest number in the list
(check-expect (mymax (list 1)) 1)
(check-expect (mymax (list 1 4 3 5)) 5)
(check-expect (mymax (list 5 3 4 1)) 5)
(define (mymax nelon)
(cond
[(empty? (rest nelon)) (first nelon)]
[(cons? (rest nelon))
(if (> (first nelon) (mymax (rest nelon)))
(first nelon)
(mymax (rest nelon)))]))

CS2500 27
Efficiency
● Let's see how this function scales. What happens if I call...
(mymax (build-list 22 identity))

Almost 3 seconds!? To find the max of 22 elements! Why?

Because to compute the if , DrRacket will compute all of the
arguments first. Thus it computes mymax twice. Each time.
What could we do? We could use a local to remember the
result and not have to compute it twice.

CS2500 28
Version 2 using local:

(define (mymax nelon)

(cond [(empty? (rest nelon)) (first nelon)]
[(cons? (rest nelon))
(local [(define MYMAX (mymax (rest nelon)))]
(if (> (first nelon) MYMAX)
(first nelon)
MYMAX))]))

CS2500 29
lambda
● Take a closer look at the double-square and add-3 functions.
● What do these functions do? They are extremely simple. But we had to go
through the design recipe for them, which seems ... overkill.
● If they were top-level functions (not in a local ), we'd need check-expect's as
well.
● Wouldn't it be nice if, for extremely simple functions like this, we had a simpler
way?
lambda
lambda comes to our rescue here. It is the essence of functions; if you've heard of
the lambda calculus, that's what it's all about.

Vocabulary: lambda

Grammar: (lambda (x1 x2 ...) expression)

Scope: x1 , etc are only valid inside of expression

Semantics: Creates a function. When the function is applied to vx1, ... its value
becomes the value of the expression with every x1 replaced by vx1 , etc.
;;Write the function, y-posn-mover:

;; [Number -> Number] -> [Posn -> Posn]

;; Returns a function that uses the given operator
;; to move the y coordinate of the posn
(define (y-posn-mover op)
…)

(define up-1 (y-posn-mover add1))

(define down-2 (y-posn-mover (lambda (height) (- height 2))))

(check-expect (up-1 (make-posn 3 9)) (make-posn 3 10))

(check-expect (down-2 (make-posn 3 9)) (make-posn 3 7))

(check-expect (map down-2 (list (make-posn 7 0) (make-posn 50 50)))

(list (make-posn 7 -2) (make-posn 50 48)))
;;Write the function, y-posn-mover:

;; [Number -> Number] -> [Posn -> Posn]

;; Returns a function that uses the given operator
;; to move the y coordinate of the posn
(define (y-posn-mover op)
(λ (p) (make-posn (posn-x p) (op (posn-y p)))))

(define up-1 (y-posn-mover add1))

(define down-2 (y-posn-mover (lambda (height) (- height 2))))

(check-expect (up-1 (make-posn 3 9)) (make-posn 3 10))

(check-expect (down-2 (make-posn 3 9)) (make-posn 3 7))

(check-expect (map down-2 (list (make-posn 7 0) (make-posn 50 50)))

(list (make-posn 7 -2) (make-posn 50 48)))
Questions?

https://xkcd.com/2824/

CS2500 34