Environments and closures

Last lesson, makeAdder(3) returned a closure that still knew n was 3 long after makeAdder had finished. To explain why, CS61A uses environment diagrams: a picture of which names are bound to which values, and where Swift looks when it meets a name.

Frames and environments

A frame is a table of bindings from names to values. The global frame holds everything bound at the top level of the program. Each call to a function creates a new local frame for its parameters and local names.

An environment is a sequence of frames. To look up a name, Swift checks the innermost frame first, then the frame it was defined in, and so on out to the global frame. The first binding found wins.

let x = 10

func f() -> Int {
    let x = 20
    return x
}

print(f(), x)   // 20 10

Here is the diagram at the moment f returns:

Global frame
  x │ 10
  f │ func f()  [parent = Global]

f  [parent = Global]
  x      │ 20
  Return │ 20

Inside f, the local x shadows the global one: lookup stops at the first frame that has the name. The global x is never changed.

let n = 1
func g(_ n: Int) -> Int {
    return n * 10
}
print(g(5), n)

Nested functions

A function can be defined inside another function. The inner function’s parent frame is the frame of the call that defined it, so it can use the outer function’s names:

func sumOfShifts(_ n: Int) -> Int {
    func shifted(_ k: Int) -> Int {
        k + n       // n comes from sumOfShifts's frame
    }
    return shifted(1) + shifted(2)
}
print(sumOfShifts(10))   // 23

This is lexical scoping: what a name means depends on where the code is written, not on who calls it.

Closures capture

When a closure is returned from a function, the frame it was defined in does not disappear. The closure captures the names it uses and keeps them alive:

func makeCounter() -> () -> Int {
    var count = 0
    return {
        count += 1
        return count
    }
}

let a = makeCounter()
print(a(), a(), a())   // 1 2 3

In diagram form, after the first call to a:

Global frame
  makeCounter │ func makeCounter()  [parent = Global]
  a           │ closure  [parent = f1]

f1: makeCounter  [parent = Global]
  count  │ 1          ← kept alive because the closure captured it
  Return │ closure

Each call to makeCounter makes a new frame, so each counter gets its own count.

func makeCounter() -> () -> Int {
    var count = 0
    return {
        count += 1
        return count
    }
}
let a = makeCounter()
let b = makeCounter()
print(a(), a(), b())

Closures are reference types. Binding a closure to a second name does not copy its captured state; both names refer to the same closure.

func makeCounter() -> () -> Int {
    var count = 0
    return {
        count += 1
        return count
    }
}
let a = makeCounter()
_ = a()
let alsoA = a
print(alsoA(), a())

Capturing a variable, not a value

A closure captures the variable itself, so it sees later changes. To capture the value at the moment the closure is created, list the name in a capture list in square brackets:

var x = 1
let live = { print("live", x) }
let frozen = { [x] in print("frozen", x) }
x = 2
live()
frozen()

func makeAccumulator() -> (Int) -> Int {
    var total = 0
    return { amount in
        total += amount
        return total
    }
}
let deposit = makeAccumulator()
print(deposit(5), deposit(10), deposit(-3))

Lab 4: Environments

Q1: Draw it

Without running the code, draw the environment diagram at the moment the program prints, and say what it prints.

func makeMultiplier(_ factor: Int) -> (Int) -> Int {
    return { x in x * factor }
}
let factor = 100
let triple = makeMultiplier(3)
print(triple(factor))

Global frame
  makeMultiplier │ func makeMultiplier(_:)  [parent = Global]
  factor         │ 100
  triple         │ closure  [parent = f1]

f1: makeMultiplier  [parent = Global]
  factor │ 3
  Return │ closure

f2: closure  [parent = f1]
  x      │ 100
  Return │ 300

Q2: Curry

curry2 turns a two-argument function into a function that takes one argument and returns another one-argument function: curry2(f)(x)(y) is f(x, y).

func curry2(_ f: @escaping (Int, Int) -> Int) -> (Int) -> (Int) -> Int {
    // your code here
}

func curry2(_ f: @escaping (Int, Int) -> Int) -> (Int) -> (Int) -> Int {
    return { x in
        return { y in f(x, y) }
    }
}

let add = curry2(+)
let addFive = add(5)
assert(addFive(3) == 8)
assert(curry2(*)(4)(5) == 20)
assert(curry2(-)(10)(3) == 7)

Q3: A Fibonacci generator

Write makeFibber(), which returns a function that returns the next Fibonacci number each time it is called: 0, 1, 1, 2, 3, 5, …

func makeFibber() -> () -> Int {
    // your code here
}

func makeFibber() -> () -> Int {
    var current = 0
    var next = 1
    return {
        let result = current
        (current, next) = (next, current + next)
        return result
    }
}

let fibber = makeFibber()
let firstSix = (1...6).map { _ in fibber() }
assert(firstSix == [0, 1, 1, 2, 3, 5])

let another = makeFibber()
assert(another() == 0)   // a separate frame, starting over
assert(fibber() == 8)    // the first fibber continues

What’s next

Next lesson: using everything so far to design functions well, with generalization, documentation, and tests.