Lab 28: Sense and Reference

Implement this lab with the Intermediate Student Language with Lambda.

Choose the initial Head and Hands, and get started!

Binding and Reference

Today’s lab focuses on binding and reference of identifiers. To bind an identifier is to assign it some value. To reference an identifier is to access the value to which it is bound.

In this class, we’ve often used define to bind values:

(define foo 42)           ; foo bound to 42

(define (bar x) (+ 2 x))  ; bar bound to (λ (x) (+ 2 x))

Functions introduce bindings as well. The function bar above accepts a single argument: x. Any time bar is applied, the body of the function executes with x bound to some value.

Ex 1: What value is the argument x bound to in the following three applications of bar? (Leave your answer in a comment.)

(bar 0)    ; => 2

(bar 40)   ; => 42

(bar foo)  ; => 44

Hint: In DrRacket, you can step through the examples. You’ll see the reference to x replaced by its value each time bar is applied.

Consider the following example:

(define x 0)

(define (double x) (+ x x))

(+ x x)     ; => ???

(double 1)  ; => ???

(double 2)  ; => ???

Ex 2: How many bindings of the identifier x appear in the above code?

Ex 3: How many references to the identifier x appear?

Ex 4: To which binding of x do each of the references refer?

Hint If you get stuck, you can always copy the code into your definitions window and hit the [Check Syntax] button. DrRacket will draw arrows both to and from identifier bindings and references. (References will be called occurences by [Check Syntax].)

Understanding Environments

At any place in your code, there are identifiers that can be referenced: identifiers that are in scope. We call that set of known identifiers the environment.

Some identifiers are defined by the language itself.

Ex 5: Name two identifiers that are provided by the Intermediate Student Language with Lambda.

Those identifiers are part of the initial environment. The environment grows as you bind identifiers with define. We also have frequently extended our environment with libraries, such as the image and universe.

Of course, function bodies can refer to any known identifiers.

; Extend our environment to include

; place-image, circle, empty-scene, ...

(require 2htdp/image)

(define WIDTH  400)

(define HEIGHT 200)

(define (place-circle x y)

(place-image (circle 20 "solid" "red") x y (empty-scene WIDTH HEIGHT)))

(place-circle  20  20)  ; => places circle in upper left corner

(place-circle 200 100)  ; => places circle in center

(local [(define WIDTH  0)

(define HEIGHT 0)]

(place-circle 200 100)) ; => ???

Ex 6: What happens in the last application of place-circle? More to the point: do the local bindings of WIDTH and HEIGHT change the environment of the body of place-circle?

Spoiler Alert: the answer to Ex 6 is decidedly no. The references inside the body of place-circle keep their bindings from the environment in which place-circle is defined, not all of the places where the function may be applied. It’s much easier to reason about the single environment from the definition-site rather than the environments of all possible application-sites.

Closing over the Environment

Functions close over their original environments, so how can we use this to our advantage? We can encapsulate state! Consider the following data definition for simple counters:

; A Command is one of:

; - "next"

; - "reset"

; Interp: Commands that a Counter can accept.

; cmd-template : Command -> ???

(define (cmd-template cmd)

(cond [(string=? "next")  ...]

[(string=? "reset") ...]))

; A Counter is a (list Natural [Command -> Counter])

; Interp: the first of the list is the current

; counter-template : Counter -> ???

(define (counter-template c)

(... (first c) ...

(second c) ...))

; make-counter : Natural -> Counter

; Create a Counter starting at the given number.

(define (make-counter n) ...)

; next-counter : Counter -> Counter

; Return the next counter.

(define (next-counter c) ((second c) "next"))

; reset-counter : Counter -> Counter

; Reset the given counter to 0.

(define (reset-counter c) ((second c) "reset"))

; counter-value : Counter -> Natural

; Return the counter's value.

(define (counter-value c) (first c))

(define c0 (make-counter 0))

(define c1 (next-counter c0))

(define c2 (next-counter c1))

(define c0* (reset-counter c2))

(check-expect (counter-value c0) 0)

(check-expect (counter-value c1) 1)

(check-expect (counter-value c2) 2)

(check-expect (counter-value c0*) 0)

Ex 7: Define the function make-counter such that the check-expects pass. The first value of the counter will be the current count; the second value of the counter will be a function that creates a new counter given some command.

Hint: Follow your templates!

Hint: The function make-counter must be recursive.

Ex 8: Extend the data definition of command to allow double-counts (incrementing by 2).

Ex 9: Design a data definition and next function for a counter-like value that generates prime numbers.