Golden Section Search in Lisp

Question

I implemented the golden section search algorithm recursively in Lisp. My code is:

(defconstant phi 0.618033988749895D0)    

(defun linemin (f x1 x2 &key (xi1 (- x2 (* (- x2 x1) phi)))
                             (xi2 (+ x1 (* (- x2 x1) phi)))
                             (tol 0.001))
   (if (> tol (- xi2 xi1))
      (/ (+ xi1 xi2) 2)
      (if (> (funcall f x1) (funcall f x2))
         (linemin f xi1 x2 :tol tol :xi1 xi2)
         (linemin f x1 xi2 :tol tol :xi2 xi1))))

I sought to make this tail-recursive. Does Lisp provide a way of ascertaining whether the function was optimized and turned into a loop at compile time? Btw I'm using Lispworks.

Any other input is appreciated, of course.

Answer 1

The Common Lisp standard does not require implementations to eliminate tail calls, but this is an optimization supported by many implementations. It is the case for Lispworks. You can write your code so that it works portably with multiple implementations, provided you wrap your declarations as required for each one of them (e.g. #+sbcl). Otherwise, you have to use an iterative approach, which is not hard to implement in your case.

Remarks

The code looks well-formatted, but consider using meaningful names:

• Write tolerance instead of tol
• Write line-min (?) or golden-section-search instead of linemin
• x1, x2, xi1 and xi2 are a little hard to read. Granted, what you write is close to mathematical notations where variable names are short and written with indices, but maybe there are more interesting name to give (low, high?), especially when those names are used as keyword arguments.