Вот подход к решению этой проблемы, который работает путем определения бесконечного потока чисел Пелла. Это основано на идеях, представленных в SICP , и в частности в разделе 3.5 . Каждый должен прочитать эту книгу.
Прежде всего нам нужно определить конструкцию, которая позволит нам говорить о бесконечных структурах данных. Мы делаем это, задерживая оценку всех, кроме их конечной части. Итак, начните с макроса с именем delay, который задерживает оценку формы, возвращает «обещание» (что, конечно, является функцией) и функцию с именем force, которая заставляет систему выполнить свое обещание:
(defmacro delay (form)
;; Delay FORM, which may evaluate to multiple values. This has
;; state so the delayed thing is only called once.
(let ((evaluatedp-n (make-symbol "EVALUATEDP"))
(values-n (make-symbol "VALUES")))
`(let ((,evaluatedp-n nil) ,values-n)
(lambda ()
(unless ,evaluatedp-n
(setf ,evaluatedp-n t
,values-n (multiple-value-list
(funcall (lambda () ,form)))))
(values-list ,values-n)))))
(defun force (promise)
;; force a promise (delayed thing)
(funcall promise))
(Эта реализация немного сложна для наших целей, но это то, что я должен был передать.).
Теперь мы будем использовать delay для определения потоков , которые потенциально представляют собой бесконечные цепочки конусов. Есть операции над ними, соответствующие операциям над conses, но с префиксом stream-, и есть объект с именем null-stream, который соответствует () (и фактически является тем же объектом в этой реализации).
(defmacro stream-cons (car cdr)
;; a cons whose cdr is delayed
`(cons ,car (delay ,cdr)))
(defun stream-car (scons)
;; car of a delayed cons
(car scons))
(defun stream-cdr (scons)
;; cdr of a delayed cons, forced
(force (cdr scons)))
(defconstant null-stream
;; the empty delayed cons
nil)
(defun stream-null (stream)
;; is a delayed cons empty
(eq stream null-stream))
Теперь определим функцию pell-stream, которая возвращает поток чисел Пелла. Эта функция вручную обрабатывает первые два элемента потока, а затем использует генератор для создания остальных.
(defun pell-stream ()
;; A stream of Pell numbers
(labels ((pell (pn pn-1)
(let ((p (+ (* 2 pn) pn-1)))
(stream-cons p (pell p pn)))))
(stream-cons 0 (stream-cons 1 (pell 1 0)))))
И теперь мы можем просто несколько раз взять stream-cdr для вычисления чисел Пелла.
(defun n-pell-numbers (n)
(loop repeat n
for scons = (pell-stream) then (stream-cdr scons)
collect (stream-car scons)))
А теперь
> (n-pell-numbers 20)
(0
1
2
5
12
29
70
169
408
985
2378
5741
13860
33461
80782
195025
470832
1136689
2744210
6625109)
Обратите внимание, что на самом деле pell-stream может быть глобальной переменной: она не должна быть функцией:
(defparameter *pell-stream*
(labels ((pell (pn pn-1)
(let ((p (+ (* 2 pn) pn-1)))
(stream-cons p (pell p pn)))))
(stream-cons 0 (stream-cons 1 (pell 1 0)))))
(defun n-stream-elements (stream n)
(loop repeat n
for scons = stream then (stream-cdr scons)
collect (stream-car scons)))
Если мы определим небольшую программу бенчмаркинга:
(defun bench-pell (n)
(progn (n-stream-elements *pell-stream* n) n))
Тогда интересно видеть, что это явно линейный процесс (он замедляется для более поздних элементов, потому что числа становятся большими и операции с ними занимают много времени), и что выполнение обещаний с учетом состояния делает это намного быстрее после первой итерации (за счет того, что вы держите много бигнумов вокруг):
> (time (bench-pell 100000))
Timing the evaluation of (bench-pell 100000)
User time = 2.020
System time = 0.803
Elapsed time = 2.822
Allocation = 1623803280 bytes
441714 Page faults
100000
> (time (bench-pell 100000))
Timing the evaluation of (bench-pell 100000)
User time = 0.007
System time = 0.000
Elapsed time = 0.006
Allocation = 1708248 bytes
0 Page faults
100000