Understanding objects with local state -- Scheme

Question

i'm studying for my scheme final and objects with local state has always been a tough subject.

Here is a question from my final exam that i need help on.

(define (make-incrementer n)
  (let ((old 0)
        (new 0))
    (lambda ()
      (cond ((< new n) 
             (set! old new)
             (set! new (+ new 1))
             old)
            (else 
             (set! old 0)
             (set! new 1)
             old)))))

(define a (make-incrementer 3))
(define b (make-incrementer 3))
(define c a)

; 1) (a)
; 2) (a)

why when a is called the second time it returns 1? I'm looking at the code and the n we give it is always 3. So wouldn't it always do the else case?

Answer 1

Welcome to the wonderful world of closures! This is a textbook example of how closures in Scheme work.

So make-counter returns a function that has 3 variables that it captures from it's enclosing environment: n, old, new. In this case, the starting environment looks something like

_name_|_value_
 n    | 3
 old  | 0
 new  | 1

On each invocation, it increments old and new and wraps them around if they're greater than n. Because it's using set!, this incrementing is mutating the variables in the lambda's environment, but since these variables are captured from the surrounding environment, they are changed for all future calls as well.

That's why you get different returns even with the same input.

If this seems like witchcraft, you can think of it like objects in more common languages:

Eg Python:

class Foo():
    def __init__(self, n, m):
        self.n = n
        self.m = m
    def count(self):
        self.n += 1
        if self.n == self.m:
           self.n = 1
        return self.n-1

f = Foo(0, 2)

f.count() # 1
f.count() # 0

This is the same basic idea except here we're being a bit more explicit about where the environment is coming from, self. In Scheme, we mimic this with the lambda capturing the surrounding variables.

For more, check out SICP

Answer 2

Here are some examples, that might help with the concept of capturing state:

(define (always x) 
  (lambda rest x))
(define always-true (always #t))
(always-true #f)
-> #t

(define (add-n n) 
  (lambda (m)
    (+ n m)))
(define add-1 (add-n 1))
(add-1 10)
-> 11

(define (complement predicate)
  (lambda (x)
    (not (predicate x)))
(define not-positive? (complement positive?))
(not-positive? -1)
-> #t

Next is an example where the captured state, in this case l, is mutated. This is similar to your case where new and old are captures and modified.

(define (nexting l)
  (lambda ()
    (if (null? l)
        '()
        (let ((answer (car l)))
          (set! l (cdr l))
          answer))))
(define next-user (nexting '(Alice Bob David)))
(next-user)
-> Alice
(next-user)
-> Bob
(next-user)
-> David
(next-user)
'()