Notes on Lisp

Generators

Generators are functions that can be used to generate elements of a sequence by calling them repetitively. Generators maintain their state between function calls by using closures. Closures are objects that contain pointers to both a function and a binding environment. To understand how these work, make sure you have seen the material on lexical scope and extent.

;;; Examples from David Touretsky and Richard Gabriel, AAAI-87 tutorial
;;; EXAMPLE 1 - GENERATORS 
;;; each generator has its own copy of the variable temp
;;; the variable temp keeps the local state between function calls
;;; the generator returns a function

(defun make-generator-for-powers-of-two ()
  (let ((temp 1))
       ;; incf increments temp by temp (temp:= temp+temp)
       #'(lambda () (prog1 temp (incf temp temp)))))

;;; the symbol-value of g1 is the closure 
(setf g1 (make-generator-for-powers-of-two))
;;; so we need to call it like here
(funcall g1)
(funcall g1)

;;; here the symbol-function of g1 is the closure
(setf (symbol-function 'g1) (make-generator-for-powers-of-two))
;;; so we call it as any other function
(g1)
(g1)

;;; EXAMPLE 2 - AN INCORRECT GENERATOR
;;; in this example all generators share the same copy of the variable temp.
;;; Likely this is an error, because all generators end up sharing the same 
;;; state and there is no advantage in having multiple generators.

(let ((temp 1))
  (defun generator-for-powers-of-two ()
	 #'(lambda () (prog1 temp (incf temp temp)))))

(setf f1 (generator-for-powers-of-two))
(funcall f1)
(funcall f1)

;;; EXAMPLE 3 - A MORE COMPLEX GENERATOR
;;; the leaves of a tree of conses are the atoms.  This function takes
;;; as input a tree and returns a generator that enumerates the leaves of
;;; that tree.  The generator returns two values: a leaf, and a flag that
;;; is T in the normal case or NIL if the generator has run out of
;;; leaves.  In this last case the first value should be ignored.

(defun generate-leaves (tree)
  (let ((stk (list tree)))
       ;; this defines a local function gen-fn
       (labels ((gen-fn ()
			(cond ((null stk) (values nil nil))
			      ((atom (car stk)) (values (pop stk) t))
			      (t (let ((oldtop (pop stk)))
				      (push (cdr oldtop) stk)
				      (push (car oldtop) stk)
				      (gen-fn))))))
               ;; and returns it
	       #'gen-fn)))

(setf foo (generate-leaves '((a . b) . c)))

(funcall foo)
(funcall foo)