Right, so, let me being by saying that I have in no way, ever, worked with anything remotely similar to programming. I'm a 100% hobbyist.

That said, I've been a CL hobbyist for quite a few years now. In this post my biggest fear is providing false information, and I sincerely hope I won't do that. You have been warned etc. As always, if in doubt, the HyperSpec is the place to check. If anything in the following seems hand-wavy it probably is.

I'm sure there are better ways of optimizing this code, I'm not saying that this is the way to do it.

SBCL (which is the implementation I happen to use) will help you figure a lot out if you compile your code with high SPEED settings.

If you use SLIME in Emacs, and compile the file (or individual forms), asking for optimization, an Emacs buffer named '*slime-compilation*' will be created or re-used.

If you split the Emacs frame so you have your code in one half, and that buffer in the other, you will be able to see many things the compiler has (and hasn't) done for you.

If you click on the hyperlinks in *slime-compilation*, focus in the other window (where your code is) will jump to that location.

This information comes from Lisp though, it's not something that SLIME adds, SLIME "packages" it, and makes it a lot easier to use compared to having it flash by in a terminal window.

Here's an example function to show it off:

(defun foo (x y)
  (+ x y))

When we compile that with high SPEED (M- C-c in SLIME), the compiler tells us:

1 compiler notes:

foo.lisp:16:3:
  note: 
    forced to do GENERIC-+ (cost 10)
          unable to do inline float arithmetic (cost 2) because:
          The first argument is a T, not a DOUBLE-FLOAT.
          The second argument is a T, not a DOUBLE-FLOAT.
          The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES DOUBLE-FLOAT
                                                                   &REST T).
          unable to do inline float arithmetic (cost 2) because:
          The first argument is a T, not a SINGLE-FLOAT.
          The second argument is a T, not a SINGLE-FLOAT.
          The result is a (VALUES NUMBER &OPTIONAL), not a (VALUES SINGLE-FLOAT
                                                                   &REST T).
          etc.

The text: 'The first argument is a T' basically means 'it could be anything'. So because the compiler doesn't know the types of A and B, it has to use an add-operation that applies to any (reasonable) numeric type.

Written like this instead, the compiler can use the addition op for not-too-big integers.

(defun foo (x y) (declare (type fixnum x y)) (the fixnum (+ x y)))

Declaring TYPE, and FTYPE (see the code below), are different. As I understand it, FTYPE, which can look like this: '(declare (ftype (function (point point) single-float) distance-sq))' means: When called with a POINT and a POINT as arguments, the function DISTANCE-SQ's return value will be of type SINGLE-FLOAT. TYPE on the other hand applies to a value: X is a FIXNUM. Both are promises to the compiler. It's like saying 'Hey, compiler, X is a FIXNUM, just use the cheap fixnum plus op, don't bother checking X's type'.

So, applied to the program in question, what I did was start with /u/ponkanpinoy's code, and compiled asking for SPEED. By a combination of suspecting what was needed,based on experience, and using the information from the compiler, I gradually changed and added stuff. I've commented the code (below) to indicate what I did, and why I did it.

(in-package :dp214h)

;; Very recklessly ask the compiler to throw safety out the window.  This could, and
;; probably should, be done with DECLARE instead, inside those forms where profiling has
;; indicated that it's needed.
(declaim (optimize (speed 3)
                   (safety 0)
                   (debug 0)
                   (space 0)
                   (compilation-speed 0)))

;; Using a struct instead of a list for points.  The constructor is just so we'll be
;; able to do '(make-point 0.5 0.5)' instead of providing keyword arguments '(make-point
;; :x 0.5 :y 0.5)'.  We specify the type as 'single-float' (which is the normal float
;; type -- there is also 'double-float', higher precision, and they have 'd0' tacked on
;; at the end: '(= 0.53242344d0 0.53242344)' => NIL.
(defstruct (point (:constructor make-point (x y)))
  (x 0.0 :read-only t :type single-float)
  (y 0.0 :read-only t :type single-float))

;; Ask the compiler to inline this function (that is, instead of calling it, just
;; execute its body in the caller.) Best used in non-recursive, short functions which
;; are called often. Whether this has any effect at all is implementation dependant.
(declaim (inline distance-sq))
(defun distance-sq (a b)
  "Evaluate the square of the Euclidean distance between points A and B"
  ;; Promise the compiler that DISTANCE-SQ if called with two POINTS (our struct
  ;; from above) as arguments, the return type will be single float.  This means
  ;; that the compiler is free to not bother checking types, and if we feed the
  ;; function values of other types, anything can happen.
  (declare (ftype (function (point point) single-float) distance-sq))
  (+ (expt (- (point-x a) (point-x b)) 2)
     (expt (- (point-y a) (point-y b)) 2)))

(defun distance (a b)
  "Evaluate the Euclidean distance between points A and B"
  ;; Another promise to the compiler about types.
  (declare (ftype (function (single-float single-float) single-float) distance))
  (sqrt (distance-sq a b)))

(defun nearest-neighbor (pos points)
  "Find the nearest neighbor of POS in POINTS"
  ;; Yet another promise to the compiler about types.
  (declare (ftype (function (point list) point) nearest-neighbor))
  (reduce #'(lambda (best next)
              (if (<= (distance-sq pos best) (distance-sq pos next))
                  best
                  next))
          points))

(defun solve (&rest points)
  "Find the total distance needed to visit each point in POINTS
using a greedy nearest-neighbor algorithm and starting at (0.5 0.5)"
  ;; And again.
  (declare (ftype (function (list) single-float) solve))
  (labels ((f (pos points distance)
             (declare (type single-float distance))
             (if (null points)
                 distance
                 (let ((point (nearest-neighbor pos points)))
                   (f point (remove point points :test #'equal)
                      ;; (THE <type> value) is another promise.
                      (the single-float (+ distance
                                           (the single-float (distance pos point)))))))))
    (f (make-point 0.5 0.5) points 0.0)))

(defun solve-file (filename)
  (let ((points nil))
    (with-open-file (file filename)
      ;; SINGLE-FLOAT is the default for *READ-DEFAULT-FLOAT-FORMAT*, but if you for
      ;; some reason wanted to read the values as double-floats, this is how to do it.
      (let ((*read-default-float-format* 'single-float))
        (setf points (loop repeat (read file)
                           collect (make-point (read file) (read file))))))
    (let ((result (apply #'solve points)))
      ;; Here at the end, we cast the result from SINGLE-FLOAT to DOUBLE-FLOAT (just
      ;; something I chose to do because the examples use high precision floats.)
      (coerce (the single-float result) 'double-float))))