Small SICP/Scheme question (local state)

Question

I'm actually reading the book for fun but it might be considered homework. At any event, I don't feel comfortable with local state variables at all with this language... Take for example this code:

(define flip
  (let ((count 0))
    (lambda ()
      (if (= 0 count)
          (begin (set! count 1) count)
          (begin (set! count 0) count)))))

why does this code alternate between 1 and 0? count is given the value of 0 every time this function is called! A python equivalent would be:

class Flip:
    def __init__(self):
        pass
    def __call__(self):
        count = 0
        if count == 0:
            count = 1
            return count
        else:
            count = 0
            return count

This returns the same thing every time. I'm confused...

Answer 1

I have a little experience with writing compilers for functional languages, so perhaps a short description of how that function is stored/represented in memory is in order. Every function can roughly be thought of as a pair (E,F) where E is the set of free variables, and F is the "code" of the function itself. When you call the function, it takes the values in E and substitutes those in for the variables in F, and then executes the code using those values.

So, where your example is concerned, you have defined the variable "flip" to be the function returned by your let expression. That function is the stuff inside your lambda. Because "count" is defined outside the lambda, it's a free variable, so it's stored in the function's environment. Then, every time you call (flip), the interpreter goes to the code in the lambda, sees that it needs to look up the value of "count" in the environment, does that, changes it, and returns. That's why each time you call it, the value stored in "count" persists.

If you want count to be zero every time you call flip, put the let expression inside the lambda, so it's a bound variable instead of a free variable.

Answer 2

The lambda is a closure. It's a function that references a free variable (count), which, not being locally defined or one of the parameters, is bound to the closest enclosing lexical environment.

The function being called is the lambda, not "flip". Flip is just a name you've given to the lambda that's returned out of the (let ...) expression.

As for the Python, I don't know the language, but it looks like count should be a member of the Flip object, not a variable local to call.

Answer 3

Because your flip function actually returns a function (which is defined inside lambda)

Each time you call the returned function it modifies its environment.

If you think about it the let creates the environment (and initializes count to 0) only once - when the lambda function is returned to you.

In a sense lambda creates a function object for you which uses environment, whose last frame was initialized in let with a single variable count. Each time you call your function it modifies its environment. If you call flip a second time it returns another function object with different environment. (count initialized to 0) You can then toggle the two functors independently.

If you want to undestand fully how it works you should read about environmantal model.

Answer 4

it's more like

class Flip:
    def __init__(self):
        self.count = 0
    def __call__(self):
        if self.count == 0:
            self.count = 1
            return self.count
        else:
            self.count = 0
            return self.count

Update with more explanation: The function in Scheme is a closure that "closes" around the free variable count, which is defined in the scope outside it. The way that count is defined in a let with just the function as the body, means that the function is the only thing that can access it -- making count effectively a kind of private mutable state that is attached to the function.

This is the way "objects" are traditionally created in Scheme in SICP -- to have a let define a bunch of variables (the instance variables, initialized to their initial values), and in the body define a bunch of functions which are "methods" that have shared access to the instance variables. That is why it is natural here to use a Python class to represent what is going on, with count being an instance variable.

A more literal translation into Python 3.x would be something like this (note that it is only approximate as Python doesn't have a let (limited-scope local variable declaration) syntax, and Python's lambdas can't be used because they don't take statements):

count = 0

def flip():
    nonlocal count
    if count == 0:
        count = 1
        return count
    else:
        count = 0
        return count

# pretend count isn't in scope after this

Answer 5

The problem with the original code is that it has a strong influence of the imperative style. A more idiomatic solution will be:

(define (flip)
  (let ((flag #t))
    (lambda ()
      (set! flag (not flag))
      (if flag 1 0))))

Answer 6

To answer the question in you comment ooboo, you want a function that returns a function

(define make-flipper
  (lambda ()
    (let ((count 0))
      (lambda ()
    (let ((v count))
      (set! count (- 1 count))
      v)))))

;; test it
(let ((flip-1 (make-flipper)))
  (format #t "~s~%" (flip-1))  
  (format #t "~s~%" (flip-1))
  (format #t "~s~%" (flip-1))

  (let ((flip-2 (make-flipper)))
    (format #t "~s~%" (flip-2))
    (format #t "~s~%" (flip-2))
    (format #t "~s~%" (flip-2))))

You can trivially change the set! line so that it becomes a counter, not a flipper (more useful).