;;;; I used quine-like programs to implement the classical binary-chop.
;;;; Completely useless and rather silly, but lots of fun!



;; Iteration

(defun chop1 (array n)
  (let ((low 0)
        (high (array-dimension array 0)))
    (loop while (> (- high low ) 1) do
         (let ((halfway (floor (/ (+ low high) 2))))
           (if (< n (aref array halfway))
               (setf high halfway)
               (setf low halfway))))
    (if (= (aref array low) n)
        low
        -1)))

;; Recursion

(defun chop2 (array n)
  (labels ((looper (low high)
              (let ((halfway (floor (/ (+ low high) 2))))
                (cond ((< (- high low) 2)
                       (if (= (aref array low) n)
                           low
                           -1))
                      ((< n (aref array halfway))
                       (looper low halfway))
                      (t
                       (looper halfway high))))))
    (looper 0 (array-dimension array 0))))

;; Let the silliness begin!
;; We start with the archetypal Lisp quine:

((lambda (x) `(,x ',x)) '(lambda (x) `(,x ',x)))

;; Transform it into a quine that takes four extra arguments:

((lambda (x a b c d) `(,x ',x ,a ,b ,c ,d))
 '(lambda (x a b c d) `(,x ',x ,a ,b ,c ,d)) 1 2 3 4)

;; Now we want it to be a quine if high - low > 2, otherwise
;; it should return low if (aref array low) is n, and -1 if not.
;; We'll also wrap it in a defun:

(defun chop3a (array n)
  (let ((low 0)
        (high (array-dimension array 0)))
    ((lambda (x array n low high)
       (if (< (- high low) 2)
           (if (= (aref array low) n)
               low
               -1)
           `(,x ',x ,array ,n ,low ,high)))
     '(lambda (x array n low high)
       (if (< (- high low) 2)
           (if (= (aref array low) n)
               low
               -1)
           `(,x ',x ,array ,n ,low ,high))) array n low high)))

;; Next we need to make it compute halfway, and change low or
;; high to halfway accordingly:

(defun chop3b (array n)
  (let ((low 0)
        (high (array-dimension array 0)))
    ((lambda (x array n low high)
       (let ((halfway (floor (/ (+ low high) 2))))
         (if (< n (aref array halfway))
             (setf high halfway)
             (setf low halfway)))
       (if (< (- high low) 2)
           (if (= (aref array low) n)
               low
               -1)
           `(,x ',x ,array ,n ,low ,high)))
     '(lambda (x array n low high)
       (let ((halfway (floor (/ (+ low high) 2))))
         (if (< n (aref array halfway))
             (setf high halfway)
             (setf low halfway)))
       (if (< (- high low) 2)
           (if (= (aref array low) n)
               low
               -1)
           `(,x ',x ,array ,n ,low ,high))) array n low high)))

;; Finally we make it loop until it's finished:

(defun chop3c (array n)
  (let* ((low 0)
         (high (array-dimension array 0))
         (result ((lambda (x array n low high)
                    (let ((halfway (floor (/ (+ low high) 2))))
                      (if (< n (aref array halfway))
                          (setf high halfway)
                          (setf low halfway)))
                    (if (< (- high low) 2)
                        (if (= (aref array low) n)
                            low
                            -1)
                        `(,x ',x ,array ,n ,low ,high)))
                  '(lambda (x array n low high)
                    (let ((halfway (floor (/ (+ low high) 2))))
                      (if (< n (aref array halfway))
                          (setf high halfway)
                          (setf low halfway)))
                    (if (< (- high low) 2)
                        (if (= (aref array low) n)
                            low
                            -1)
                        `(,x ',x ,array ,n ,low ,high))) array n low high)))
    (loop while (not (numberp result)) do
         (setf result (eval result)))
    result))