(in-package "USER")

;; Die Fibonacci-Reihe besteht aus Zahlen, die jeweils die
;; Summe ihrer beiden direkten Vorgaenger darstellt. Die
;; ersten beiden Zahlen der Reihe sind per Definition 1.
;; 1, 1, 3, 5, 8, 13, 21, ...

(defun fibonacci (n)
  (if (<= n 1)
      1
    (+ (fibonacci (- n 1))
       (fibonacci (- n 2)))))

;; Eine closure ist ein lambda-Ausdruck (anonyme Funktion), der lexikalische
;; Variablen enthaelt, deren Bindungsumgebungen ausserhalb des lambda-Koerpers
;; etabliert wurden.  
;; 
;; counter ist ein Beispiel fuer eine closure. Die Variable n erhaelt ihre
;; Bindung durch die Parameterliste von counter. Man spricht davon, dass eine
;; solche Variable eine unbegrenzte Lebensdauer hat: Auch nach dem Verlassen
;; des Funktionskoerpers von counter hat n einen definierten Wert; Aber sie hat
;; einen lokalen scope: Ausser ueber ein funcall der closure ist n nicht
;; zugaenglich.

(defun counter (n)
  #'(lambda ()
      (incf n)))

;;; MEMOIZE realisiert mit Hilfe einer closure: eine lokale
;;; Bindungsumgebung wird erzeugt, in der der Cache und die
;;; Originalfunktion gespeichert werden.

(defun memoize (name &key (key #'identity)
                          (test #'equal))
  (setf (symbol-function name)
        (let ((table (make-hash-table :test test))
              (function (symbol-function name)))
          #'(lambda (&rest args)
              (let ((index (funcall key args)))
                (multiple-value-bind (value value-p)
                    (gethash index table)
                  (if value-p
                      value
                    (setf (gethash index table) (apply function args)))))))))