まず大前提として,

Lispの関数呼出は値渡しである

ということを踏まえる.具体的例を示す.

> (defun qadd (queue element)
(setf queue (cons element queue)))
QADD
> (setf myqueue nil)
NIL
> (qadd myqueue 'a)
(A)
> myqueue 
NIL

関数qaddの返り値は(A)ではあるが,setf式にもかかわらず関数qaddはmyqueueの値に変更を加えることができていない.すなわち

(defun qadd (queue element)
(cons element queue))
QADD

と定義したのと変わらない.これがもしPerlなどの参照渡しである言語で同様のことをしたのであれば,呼出元でもmyqueueに変化がある.しかしLispでは値渡しである.すなわち関数内におけるqueueはmyqueueの値をコピーした別の(一時的な)変数であり,これを変更してもmyqueueに変化はないのである.一方でLispにはsortなど破壊的な関数と呼ばれる(この例でいうなら)myqueueを変更してしまう(ように見える)関数がある.この頁ではこの破壊的な関数を作ってみる.

上の関数をキューとして使用しようとするならば,呼出側で

> (setf myqueue (qadd myqueue 'a))
(A)
> myqueue 
(A)

などとqaddの返り値に対してqaddしなければならない.このsetfのステップを省略して,

> (qadd myqueue 'a)
(A B)
> myqueue 
(A B)

などとなる関数を作成する.実装上の都合により,目標の関数qaddの第一引数のキューはコンスでなければならない.理由は以降で明らかになる.

では,実装.

;; キューqueueの先頭に要素elementを加える.queueはコンスでなければならない.
;; elementはコンスでもアトムでもよい.
(defun qadd (queue element)
  (if (consp queue)
    (let ((newcons (cons (car queue) (cdr queue))))
      (setf (car queue) element)
      (setf (cdr queue) newcons))
    nil))

; ドライバ
(setf myqueue '(a))
(format t "~A~%" myqueue)
(qadd myqueue 'b)
(format t "~A~%" myqueue)
(qadd myqueue 'c)
(format t "~A~%" myqueue)
(qadd myqueue 'd)
(format t "~A~%" myqueue)

実行結果を以下に示す.

$clisp queue.lisp
(A)
(B A)
(C B A)
(D C B A)

ドライバを見れば分かるように,呼出し側のmyqueueが変更されている(ように見える).

前節で破壊的な関数の作成ができた.この破壊的関数qaddでは,何が起こっているのか.ポイントは「呼出し側のmyqueueが変更されている(ように見える)」と書いた括弧内である.実はmyqueueの値は変更されていない.では,その値とは何か.コンスへのポインタ値である.すなわちmyqueueが変わったのではなく,myqueueがポイントしているコンスのcar部とcdr部が変わったのである.それが結果としてはmyqueueが変わったように「見えた」わけである. この図は

(qadd myqueue 'd)

を呼び出す前と後のmyqueueがポイントしているリストの構成を示したものである.この図から分かるように,myqueueは同じコンスを指し続け(すなわち値はかわらない),そのコンスのcar部とcdr部のポイント先が変化している(※).

値の取り出しは簡単である.リストの最後のコンスのcdr部の参照先を一時変数に保持して,その一つ前のコンスのcdr部の参照先をnilにし,一時変数の値を返すだけである(※).

;; キューqueueの末尾から値を取り出す.
(defun qget (queue)
  (if (listp queue)
	  (let ((element (car (last queue))))
	    (if (> (length queue) 1)
		(setf (cdr (nthcdr (- (length queue) 2) queue)) nil)
	      (setf (car queue) nil))
	    element)
    nil))

;; ドライバ
(setf myqueue '(d c b a))
(format t "~A~%" myqueue)
(do '(i (length myqueue) (- i 1))
    ((<= i 0) myqueue)
  (format t "got : ~A~%" (qget myqueue))
  (format t "~A~%" myqueue))

最後の一つ前のコンスはlength関数を利用して取得した.これに伴い,引数のキューの要素数が1の場合の条件分岐も追加してある.実行結果を以下に示す.

$ clisp queue2.lisp
(D C B A)
got : A
(D C B)
got : B
(D C)
got : C
(D)
got : D
(NIL)