scheme functions that "remember" values with let/set

Question

I'm new to Scheme and trying to understand how certain values that appear within a function can persist across multiple uses. Take the following counter:

(define count
   (let ((next 0))
     (lambda ()
       (let ((v next))
         (set! next (+ next 1))
         v))))

What I can't figure out (and haven't found explained anywhere), is why next doesn't get reset to 0 every time count is used.

Besse

This phenomenon is also known as "static variables". See this recipe in the Scheme Cookbook: schemecookbook.org/Cookbook/IdiomStaticVariables – Altostratus

Answer 1

I don't totally agree with your explanation. You're right in that the function's definition is evaluated only once, but the function itself is evaluated every time it is called.

The point I don't agree with is the "...rewrites the definition...", because the function is defined only once (and not explicitly overwritten).

I imagine it the following way: Due to the so-called lexical binding of variables in scheme, the scheme interpreter notices during the evaluation of the function definition that there's a variable defined in the environment of the function definition - the variable "next". Therefore it remembers not only the function definition, but the value of the variable "next", too (this means that it stores two things - the function definition and the enclosing environment). When the function in called for the first time, its definition is evaluated by the scheme interpreter within the stored environment (in which the variable "next" has the value 0, and were the value is incremented). The second time the function is called, exactly the same things happen - the same function definition is evaluated in its enclosing environment. This time, however, the environment provides the value 1 for the variable "next" and the result of the function call is 1.

To phrase is concisely: The function (definition) stays the same, it's the evaluation environment that changes.

Kymric

Answer 2

This is called a closure. There's only one version of next in the whole program.

To make this clearer, consider the following program:

(define next 0)

(define count
  (lambda ()
    (let ((v next))
      (set! next (+ next 1))
      v))))

Now it's clear that there's only one next.

The version you wrote is different, because you've used let to make sure that only the lambda expression can see next. But there's still only one next. If you changed it to this, instead:

(define count
  (lambda ()
    (let ((next 0))
      (let ((v next))
       (set! next (+ next 1))
       v))))

Then you would create a new version of next every time, because the declaration of next is inside the lambda, which means that it happens every time that lambda is called.

Sprang

Hi, Sam. I'm already a little familiar with closures as well as the importance of having the let over the lambda. But knowing that this syntax creates a closure is not the same as understanding why. I think I must be confused about the evaluation sequence: It seems that the assignment portion of (let ((next 0))) is only evaluated the first time count executes. How do I account for that? – Besse

Basically, the reason is that the function is created by lambda, not by define. So the binding of next happens outside the function, because it's outside the lambda. – Sprang

Answer 3

I have one thing to add to Sam's excellent answer: your question suggests that this behavior might have something to do with "let". It does not. Here's an example that does a similar thing without a "let" in it:

#lang racket

(define (make-counter-from counter)
  (lambda ()
    (set! counter (+ counter 1))
    counter))

(define count (make-counter-from 9))

(count)
(count)

The moral (if there is one): Yes! Mutation is confusing!

EDIT: Based on your comment below, it sounds like you really are looking for some insight into what kind of mental model you can use for a language with mutation.

In a language with mutation of local variables, you can't use the simple "substitution" model that replaces arguments with values. Instead, each call to a function creates a new "binding" that can later be updated (a.k.a. "mutated").

So, in my code above, calling "make-counter-from" with 9 creates a new binding that associates the "counter" variable with the value 9. This binding is then attached/substituted-for all uses of the "counter" variable in the body of the function, including those inside of the lambda. The result of the function is then a lambda (a function) that is "closed over" two references to this newly created binding. You can think of these as two references to a heap-allocated object, if you like. This means that every call to the resulting function results in two accesses to this object/heap-thing.

Arable

Thanks, this is a helpful example, though it stumps me for much the same reason (see the reply to Sam's post). – Besse

As far as I can judge, your revised post answers my question perfectly. I gave the nod to Valentin because he directly addresses my second post. – Besse

Answer 4

To directly answer your question, "next doesn't get reset to 0 every time count is used" because your code

(define count (let ((next 0))
                 (lambda ()
                    (let ((v next))
                       (set! next (+ next 1))
                       v))))

is equivalent to

(define count #f)

(set! count ( (lambda (next)              ; close over `next`
                 (lambda ()                  ; and then return lambda which _will_
                    (let ((v next))          ;   read from `next`,
                       (set! next (+ v 1))   ;   write new value to `next`,
                       v)))                  ;   and then return the previous value;
              0 ))                        ; `next` is initially 0

(this is "let-over-lambda" pattern; there's even a Lisp book by that name).

The value to assign count is "calculated" only once. This value is a closure referring to the binding for next, which (binding) is external to it (the closure). Then every time count is "used", i.e. a procedure that it refers to is called, it (the procedure) refers to that binding: first it reads from it, then it alters its contents. But it doesn't re-set it to its initial value; the binding is initiated only once, as part of its creation, which happens when the closure is created.

This binding is visible only from this procedure. The closure is a bundle of this procedure and the environment frame holding this binding. This closure is the result of evaluating the (lambda () ...) expression inside the lexical scope of next, the (lambda (next) ...) expression.

Mutt

Answer 5

Ok, I've had something of an epiphany. I believe my confusion relates to the distinction between a definition and a procedure (lambda): Definitions occur once, while procedures evaluate each time they are run. In the original function, let defines a procedure with next set to zero. That definition happens one time, but using set! within the procedure rewrites the definition as if retroactively. Thus, each use of count produces a new version of the function in which next has been incremented.

Please correct me if this is totally off-base.

Besse

The thing about bindings is that they can be shared among lambda-expressions: (let ((fg (let ((i 0)) (list (lambda()(set! i (+ i 1))) (lambda() (set! i (+ i 2))))))) (let ((once (car fg)) (twice (cadr fg))) .... )). Now calling once or twice inside the .... body increments the same counter. – Mutt

Answer 6

Here is a program that does precisely the same thing.

(define count
  (local ((define next 0)          
          (define (inc)
            (local ((define v next))
                    (begin 
                      (set! next (+ next 1))
                      v))))
    inc))

 (count)   0
 (count)   1
 (count)   2 .........

Maybe your let/set sequence follows the same mechanism. The procedure that you are actually calling is inc, not count. The inc procedure increments next every time. An equivalent definition can be

 (define next 0)

 (define (inc)
  (begin
    (set! next (+ next 1))
    (- next 1)))

 (define count inc)


 (count)  0
 (count)  1
 (count)  2......

So, I guess calling count in the first program is just like running the entire second program. I don't know. I too am new to scheme. Thanks, for the useful post.

Rentsch