Lecture 16

​

Variables, Scope, Pairs, Mutation

Programming Languages

UW CSE 341 - Spring 2021

Local Bindings

• 4 ways to define local variables, but they have different semantics!
• let
• let*
• letrec
• define
• For different situations, different ones are needed or most natural or just the best style
• Plus, for us: helps learn more about scope and semantics!
• Like OCaml, all the lets can appear anywhere an expression can

let expression

• Can bind any number of variables
• Be careful with parentheses!
• Right-hand-sides evaluated in environment from before let (!!)
• Then body is evaluated in environment extended with all new bindings
• A bit weird, but sometimes useful

let*

• Syntax the same as let plus the *
• Semantics different: bindings are added to environment “as you go”
• Can repeat bindings (later bindings shadowed)
• Equivalent to nested lets (but better style; syntactic sugar)

letrec

• Syntax also the same as let
• But all the bindings are in scope for all right-hand-sides
• Useful for (mutual) recursion

​

​

• WARNING: right-hand-sides still evaluated in order
• So it is an error to look up a later binding’s value before it is defined
• Remember: functions don’t look up variables until they are called!

letrec for mutual recursion

​

​

​

• Notice: does not use later bindings until function is called
• Error example:

Local define

• In certain positions, including beginning of function body, can put defines
• Local define has same semantics as letrec

​

​

• In “real-life” Racket, local define is the preferred style
• We will use let / let* / letrec just to get a better feel for them

Our Style

• Each form of let is the best fit for different situations
• let when shadowing (e.g., swap)
• let* for sequence where earlier ones needed
• letrec for mutual recursion
• If “all work equally well”, then use let
• Communicates that there is no sequencing or mutual recursion to be concerned about
• In any case, most interesting part is that the three have different and useful semantics

Top Level

• Top-level defines also work like letrec
• So:
• Can refer to earlier bindings whenever you want
• Can refer to later bindings from within function bodies
• Unlike OCaml, cannot bind same top-level name twice!
• Would not make sense because both are in scope

REPL

Unfortunate optional detail you hopefully won’t run across:

• REPL works slightly differently than top-level in a file
• Not quite let* or letrec
• Weird interactions with shadowing and stuff-not-written-yet
• Best to avoid directly in the REPL:
• Recursive function definitions
• Forward references to not-yet-defined values
• Fine (of course) to call recursive functions defined in files

Cons

The Truth About cons

• cons always just makes a pair (also known as “cons cell”)
• Non-empty lists are “just” right-nested pairs ending with null

​

​

​

​

​

• “Improper list” : doesn’t end in null
• Will cause an error if passed to, e.g., length

The Truth About cons

• Why allow improper lists?
• Pairs are useful
• No static types, so why distinguish (e1, e2) from e1 :: e2
• Style: use (proper) lists for collections of unknown size
• But feel free to use fixed-size nested pairs
• Useful predicates
• list? : check if argument is (possibly empty) proper list
• pair? : check if argument is a cons cell (⇒ includes ALL nonempty lists!)

Mutation

set!

• Unlike OCaml, can update value of a binding (⚠️)
• Use only when mutation really necessary

(set! x e)

• Evaluate e to a value v, then update x ↦ v in environments that use “that” x
• Yes, this is an assignment statement (you’re used to x=e;)
• Once you have side-effects, sequencing is useful

(begin e1 e2 … eN)

• Evaluate the ei in order and return result of eN
• (Can also can be defined as sugar for let)

​

set! Example

• Environment of closure g is NOT copied
• It is the env from when it was defined
• Mutating b influences the body of g
• Once an expression produces a value, how it did so is irrelevant

Top-level set!

• Would be really weird “in the large”
• Consider: what if someone replaced the value of map of + 😱
• But sometimes useful within a file
• Example: top-level mutable variable
• So, Racket has a compromise:
• If a file doesn’t use set! On a top-level variable x,

then nobody outside that file (module) can either

cons cells are immutable

• Big difference from Scheme (Racket’s predecessor)
• This is a great choice
• List aliasing doesn’t matter
• Lists can’t have cycles
• Can make list? constant time, O(1)

set! does not mutate list contents!

Instead, set! changes which immutable list x points to

Mutable Lists & Pairs [moved to section]

• Sometimes useful (we’ll use them in coming lectures 😉)
• Completely separate from immutable lists and pairs

​

​

• Operations analogous to cons:
• mcons mcar mcdr mpair?
• Additional operations for mutation:
• set-mcar! set-mcdr!

Run-time errors:

(car (mcons 1 2))

(mcar (cons 1 2))