How does the Lisp function remember the state in this code?

Question

I saw a code snippet from 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 do not understand how a function remembers a state. Is state overridden to the whole list every time the function is run? And why two layers let (which is necessary)? It would be helpful if someone could explain how this function works.

Answer 1

The state value in (let ((state '(() . (list of elements to be generated)))) ...) is the quoted literal, and it changes (which, as explained in this answer, is undefined behavior). Other issues were discussed in this behavior, such as:

• Strange Lisp Quote Script - Graham Inc. Lisp, page 37
• Why does this function return a different value each time?
• Changing the list passed as a parameter gives different results in SBCL and CLISP
• Lisp, cons and (number number) difference

Answer 2

 (defun element-generator () 

The function is defined above.

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

A local variable was defined here. The code has literal data. Think about the functions of the Lisp function itself, and part of the code is a list construct. In the Lisp undefined standard, what happens is when you try to modify this data object.

Since this is a data object with letters, there is only one of them. The variable does not get bound to freshly bound data. Thus, with every call here the variable points to the same literals.

  (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 the above code, the first item is removed from the list. As already mentioned, this is not recommended since the list is literal data.

  ans))) 

Above returns the stored value.

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

Answer 3

This is beyond the scope of CL standards. Some CL implementations may do these strange things, but others may not. I remember that I found something similar when I was studying CL. My version was the following:

 (defun counter1 (&optional (x '(-1))) (rplaca x (+ (car x) 1)) (car x)) (counter1) ; ==> 0 (counter1) ; ==> 1 (counter1) ; ==> 2 

What happens here and in your code is that the optional x and state are constants. It exists only one of them, and if you change it, you constantly change it. In my example; if the default value was (cons -1 ()) , it would always return 0 if I hadn't supplied x . Why do you have two nested inputs because (cadr state) is different before and after rplacd . I urge you to remove it and replace ans with (cadr state) to see the difference.

Here is what the example code would look like if you wanted to have the same functionality in 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 each start of the element generator, and when you call the return function, you get the elements from this closure. See how the two returned functions have their own version of the list. Since we do not crack the standard, we can also rewrite it to change state instead of a 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 

He will behave the same.

Answer 4

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

This is a static list, but rplacd changes it anyway ... modifies the function definition so that next time its launch is shorter. If you look at the definition of a function between calls, you will see that it gets shorter. Some lisp implementations show function definition better than others.

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