How does Lisp function remember state in this code

Question

I saw a piece of code from the website http://www.ccs.neu.edu/home/shivers/newstyle.html:

> (defun element-generator ()
    (let ((state '(() . (list of elements to be generated)))) ;() sentinel.
      (let ((ans (cadr state)))       ;pick off the first element
        (rplacd state (cddr state))   ;smash the cons
        ans)))
ELEMENT-GENERATOR
> (element-generator)
LIST
> (element-generator)
OF
> (element-generator)
ELEMENTS
> (element-generator)
TO
> (element-generator)
BE
> (element-generator)
GENERATED

I don't understand how the function remembers the state. Isn't state redefined to the whole list each time the function runs? And why the two layers of let (which is necessary)? It'd be appreciated if someone is able to explain how this function works.

Answer 1

It's out of the scope of CL standards. Some CL implementations might do these strange things, but other might not. I remember I found something similar when I was learning CL. My version was this:

(defun counter1 (&optional (x '(-1)))
   (rplaca x (+ (car x) 1))
   (car x))

(counter1) ; ==> 0
(counter1) ; ==> 1
(counter1) ; ==> 2

What's happening here, and in your code, is that the optional x and state are constants. It exist only one of them and if you change it you change it permanently. In my example; if the default value had been (cons -1 ()) it would always return 0 if I didn't supply x. Why you have two nested lets is because (cadr state) is different before and after the rplacd. I urge you to remove it and replace ans with (cadr state) to see the difference.

Here is how you example code would look if you were to want the same functionality within the standard:

(defun element-generator ()
  (let ((state (list () 'list 'of 'elements 'to 'be 'generated))); Make closure
    #'(lambda ()                        ;create function
        (let ((ans (cadr state)))       ;pick off the second element
          (rplacd state (cddr state))   ;mutate the list in the closure
          ans))))                       ;return element

(setf (symbol-function 'gen1) (element-generator))
(setf (symbol-function 'gen2) (element-generator))
(gen1) ; ==> LIST
(gen1) ; ==> OF
(gen1) ; ==> ELEMENTS
(gen2) ; ==> LIST
(gen2) ; ==> OF
(gen1) ; ==> TO

Here you get a new closure for every instancing of element-generator and when you call the function it returns you will get elements from that closure. See how the two functions returned has their own version of the list. Since we're not hacking the standard we might as well rewrite it to mutate state instead of the list:

(defun element-generator ()
  (let ((state (list 'list 'of 'elements 'to 'be 'generated))) ; create closure
    #'(lambda ()                       ;create function
        (let ((ans (car state)))       ;pick off the first element
          (setf state (cdr state))     ;mutate state to point to next element
          ans))))                      ;return first element

It will behave identical.

Answer 2

'(() . (list of elements to be generated))

That is a static list, but rplacd changes it anyway... modifying the function definition so that next time its run the list is shorter. If you looked at the function definition between calls you would see it getting shorter. Some lisp implementations are better at showing a function definition than others.

You should only use destructive list operations when you just created the list (or you really understand what you are doing).

Answer 3

The value of state in (let ((state '(() . (list of elements to be generated)))) ...) is a quoted literal, and it is being modified (which, as explained in this answer is undefined behavior). This behavior has been discussed other questions, such as:

• Strange Lisp Quoting scenario - Graham's On Lisp, page 37
• Why does this function return a different value every time?
• Modifying a list passed as a parameter gives different results in SBCL and CLISP
• Lisp, cons and (number . number) difference

Answer 4

(defun element-generator ()

Above defines a function.

  (let ((state '(() . (list of elements to be generated)))) ;() sentinel.

Here were define a local variable. There is literal data in the code. Think of the Lisp function itself data, and part of the code is this construct with the list. In the Common Lisp standard it is undefined what happens when one tries to modify this data object.

Since it is a literal data object, there is only one of it. The variable does not get a binding to freshly consed data. So on each call, here the variable points to the same literal data.

    (let ((ans (cadr state)))       ;pick off the first element

Above creates a temporary variable and saves the first element.

      (rplacd state (cddr state))   ;smash the cons

In above code the first element gets removed from the list. As mentioned already this is not recommended practice, since the list is literal data.

      ans)))

Above returns the saved value.

This LET idiom is in Common Lisp already provided by the macro PROG1.