Monthly Archives: September 2013

Some Lisp musings, part 2

Having written a somewhat basic and brute-force version of the doubly-linked list code in the previous post, I’m going to start cleaning it up.  This first change is fairly small.  Collection of common code, and an improved unit test.

One helpful shortcut in lisp is the ability to build lists at function invocation time, with the &rest keyword.  That’s just a bit of syntactic convenience, it can easily be implemented with the (list) function, but it’s worth pointing out.  In C/C++, I’d have to use some repetitive boilerplate for this, either building up C arrays, or filling in C++ vectors.  Not really a big deal, though.  The real magic will come later.  Continued in part 3.

;; We started with a fairly basic version.  It worked, but was clunky.
;; Now, we start making changes.

(declaim (optimize (debug 3) (safety 3)))

;; Define the node.  They're opaque types to the user, but they double
;; as iterators (also opaque).
(defstruct (dl-node)
  (value        nil)
  (next-node    nil)
  (prev-node    nil))

;; Define the doubly-linked list.
(defstruct (dl-list)
  (first-node   nil)
  (last-node    nil))

(defun dl-list-empty-p (dl-list)
  "Returns non-nil if the list is empty."
  (not (dl-list-first-node dl-list)))

(defun dl-list-length (dl-list)
  (let ((rv 0))
    (do ((iter (dl-list-iter-front dl-list) (dl-list-iter-next dl-list iter)))
        ((not iter) rv)
      (incf rv))))

(defun dl-list-iter-front (dl-list)
  "An iterator to the first element in the list."
  (dl-list-first-node dl-list))

(defun dl-list-iter-back (dl-list)
  "An iterator to the last element in the list."
  (dl-list-last-node dl-list))

(defun dl-list-iter-next (dl-list iter)
  "The next iterator, or nil if we're at the end of the list."
  (declare (ignore dl-list))
  (dl-node-next-node iter))

(defun dl-list-iter-prev (dl-list iter)
  "The previous iterator, or nil if we're at the beginning of the list."
  (declare (ignore dl-list))
  (dl-node-prev-node iter))

(defun dl-list-insert-after-worker (dl-list iter val)
  "Insert a value in the dl-list after the iterator.  As a special case, 
if 'iter' is nil, inserts at the front of the list."

  (let* ((next-node (if iter (dl-node-next-node iter) (dl-list-first-node dl-list)))
         (prev-node iter)
         (new-node (make-dl-node :value val
                                 :next-node next-node
                                 :prev-node prev-node)))
    (cond
      (next-node
       (setf (dl-node-prev-node next-node) new-node))
      (t
       (setf (dl-list-last-node dl-list) new-node)))
    (cond
      (prev-node
       (setf (dl-node-next-node prev-node) new-node))
      (t
       (setf (dl-list-first-node dl-list) new-node)))

    new-node))

(defun dl-list-delete-at-worker (dl-list iter)
  "Deletes the value under the iterator."
  (assert iter)
  (let ((prev-node (dl-node-prev-node iter))
        (next-node (dl-node-next-node iter)))
    (cond
      (prev-node
       (setf (dl-node-next-node prev-node) next-node))
      (t
       (setf (dl-list-first-node dl-list) next-node)))

    (cond
      (next-node
       (setf (dl-node-prev-node next-node) prev-node))
      (t
       (setf (dl-list-last-node dl-list) prev-node))))

  (dl-node-value iter))

(defun dl-list-push-front (dl-list val)
  "Push a value onto the front of the list."
  (dl-list-insert-after-worker dl-list nil val))

(defun dl-list-push-back (dl-list val)
  "Push a value onto the back of the list."
  (dl-list-insert-after-worker dl-list (dl-list-last-node dl-list) val))

(defun dl-list-pop-front (dl-list)
  "Remove the first value from the list and return it.  Returns nil if the list is empty."
  (let ((first-iter (dl-list-iter-front dl-list)))
    (when first-iter
      (dl-list-delete-at-worker dl-list first-iter))))

(defun dl-list-pop-back (dl-list)
  "Remove the last value from the list and return it.  Returns nil if the list is empty."
  (let ((last-iter (dl-list-iter-back dl-list)))
    (when last-iter
      (dl-list-delete-at-worker dl-list last-iter))))

(defun dl-list-iter-contents (dl-list iter)
  "The value of the list element pointed to by the iterator."
  (declare (ignore dl-list))
  (dl-node-value iter))

(defun dl-list-insert-after-iter (dl-list iter val)
  "Insert a value into the list after the position of the iterator."
  (assert iter)
  (dl-list-insert-after-worker dl-list iter val))

(defun dl-list-insert-before-iter (dl-list iter val)
  "Insert a value into the list before the position of the iterator."
  (assert iter)
  (dl-list-insert-after-worker dl-list (dl-list-iter-prev dl-list iter) val))

(defun verify-dl-list-contents (dl-list &rest contents)
  (assert (= (dl-list-length dl-list) (length contents)))
  (assert (or (and contents (not (dl-list-empty-p dl-list)))
              (and (not contents) (dl-list-empty-p dl-list))))
  (let ((iter (dl-list-iter-front dl-list)))
    (dolist (entry contents)
      (assert (eq entry (dl-list-iter-contents dl-list iter)))
      (setf iter (dl-list-iter-next dl-list iter)))))

(defun unit-test ()
  (let ((test-list (make-dl-list)))

    (verify-dl-list-contents test-list)

    (dl-list-push-front test-list 10)
    (verify-dl-list-contents test-list 10)

    (dl-list-push-front test-list 5)
    (verify-dl-list-contents test-list 5 10)

    (dl-list-push-back test-list 20)
    (verify-dl-list-contents test-list 5 10 20)

    (let ((iter (dl-list-iter-front test-list)))
      (assert (= (dl-list-iter-contents test-list iter) 5))
      (dl-list-insert-after-iter test-list iter 7)

      (verify-dl-list-contents test-list 5 7 10 20)

      (setf iter (dl-list-iter-next test-list iter))
      (assert (= (dl-list-iter-contents test-list iter) 7))

      (dl-list-insert-before-iter test-list iter 6)

      (verify-dl-list-contents test-list 5 6 7 10 20)

      (setf iter (dl-list-iter-prev test-list iter))
      (assert (= (dl-list-iter-contents test-list iter) 6))

      (setf iter (dl-list-iter-next test-list iter))
      (assert iter)
      (assert (= (dl-list-iter-contents test-list iter) 7))

      (setf iter (dl-list-iter-next test-list iter))
      (assert iter)
      (assert (= (dl-list-iter-contents test-list iter) 10))

      (setf iter (dl-list-iter-next test-list iter))
      (assert iter)
      (assert (= (dl-list-iter-contents test-list iter) 20))

      (setf iter (dl-list-iter-next test-list iter))
      (assert (not iter)))

    (assert (= (dl-list-iter-contents test-list (dl-list-iter-front test-list)) 5))
    (assert (= (dl-list-iter-contents test-list (dl-list-iter-back test-list)) 20))

    (assert (= (dl-list-pop-front test-list) 5))
    (assert (= (dl-list-length test-list) 4))
    (assert (= (dl-list-iter-contents test-list (dl-list-iter-front test-list)) 6))

    (assert (= (dl-list-pop-back test-list) 20))
    (assert (= (dl-list-length test-list) 3))
    (assert (= (dl-list-iter-contents test-list (dl-list-iter-back test-list)) 10)))
  t)

(defmethod print-object ((node dl-node) stream)
  "Allow pretty-printing of the a node."
  (let ((prev-node (dl-node-prev-node node))
        (next-node (dl-node-next-node node)))
    (format stream "{ ~A <- ~A -> ~A }" 
            (and prev-node (dl-node-value prev-node))
            (dl-node-value node)
            (and next-node (dl-node-value next-node)))))

 

Lisp features I miss when programming in other languages

There are several features of Lisp that I find very useful, and miss when I’m working in, for example, C++. One in particular is the ability to create new flow-control syntaxes.

To draw from a real example from my work, let’s say I have an arbitrary closed polygon, defined as an ordered sequence of points, and I’m interested in performing operations on these points, either individually, pairwise, or in triplets. I also might want to go in forward or reverse directions.

I’ll represent my polygons as doubly-linked lists. Not circular, it will be up to the user of the data structure to wrap around, if necessary, upon reaching the end of the list.

I’m going to be developing and refining this code, starting simply, but moving on to doing things better. Here’s our first iteration of a doubly-linked list, with a few helper functions.

Work will continue in a later post.

;; Define the node.  They're opaque types to the user, but they double
;; as iterators (also opaque).
(defstruct (dl-node)
  (value        nil)
  (next-node    nil)
  (prev-node    nil))

;; Define the doubly-linked list.
(defstruct (dl-list)
  (first-node   nil)
  (last-node    nil))

(defun dl-list-empty-p (dl-list)
  "Returns non-nil if the list is empty."
  (not (dl-list-first-node dl-list)))

(defun dl-list-length (dl-list)
  (let ((rv 0))
    (do ((iter (dl-list-iter-front dl-list) (dl-list-iter-next dl-list iter)))
        ((not iter) rv)
      (incf rv))))

(defun dl-list-push-front (dl-list val)
  "Push a value onto the front of the list."
  (let* ((first-node (dl-list-first-node dl-list))
         (new-node (make-dl-node :value val
                                :next-node first-node
                                :prev-node nil)))
    (when first-node
      (setf (dl-node-prev-node first-node) new-node))

    (setf (dl-list-first-node dl-list) new-node)
    (unless (dl-list-last-node dl-list)
      (setf (dl-list-last-node dl-list) new-node))
    new-node))

(defun dl-list-push-back (dl-list val)
  "Push a value onto the back of the list."
  (let* ((last-node (dl-list-last-node dl-list))
         (new-node (make-dl-node :value val
                                :next-node nil
                                :prev-node last-node)))
    (when last-node
      (setf (dl-node-next-node last-node) new-node))

    (setf (dl-list-last-node dl-list) new-node)
    (unless (dl-list-first-node dl-list)
      (setf (dl-list-first-node dl-list) new-node))
    new-node))

(defun dl-list-pop-front (dl-list)
  "Remove the first value from the list and return it.  Returns nil if the list is empty."
  (when (dl-list-first-node dl-list)
    (let* ((first-node (dl-list-first-node dl-list))
           (second-node (dl-node-next-node first-node))
           (rv (dl-node-value first-node)))
      (cond
        (second-node
         (setf (dl-node-prev-node second-node) nil)
         (setf (dl-list-first-node dl-list) second-node))
        (t
         (setf (dl-list-first-node dl-list) nil
               (dl-list-last-node dl-list) nil)))
      rv)))

(defun dl-list-pop-back (dl-list)
  "Remove the last value from the list and return it.  Returns nil if the list is empty."
  (when (dl-list-last-node dl-list)
    (let* ((last-node (dl-list-last-node dl-list))
           (penultimate-node (dl-node-prev-node last-node))
           (rv (dl-node-value last-node)))
      (cond
        (penultimate-node
         (setf (dl-node-next-node penultimate-node) nil)
         (setf (dl-list-last-node dl-list) penultimate-node))
        (t
         (setf (dl-list-first-node dl-list) nil
               (dl-list-last-node dl-list) nil)))
      rv)))

(defun dl-list-iter-front (dl-list)
  "An iterator to the first element in the list."
  (dl-list-first-node dl-list))

(defun dl-list-iter-back (dl-list)
  "An iterator to the last element in the list."
  (dl-list-last-node dl-list))

(defun dl-list-iter-next (dl-list iter)
  "The next iterator, or nil if we're at the end of the list."
  (declare (ignore dl-list))
  (dl-node-next-node iter))

(defun dl-list-iter-prev (dl-list iter)
  "The previous iterator, or nil if we're at the beginning of the list."
  (declare (ignore dl-list))
  (dl-node-prev-node iter))

(defun dl-list-iter-contents (dl-list iter)
  "The value of the list element pointed to by the iterator."
  (declare (ignore dl-list))
  (dl-node-value iter))

(defun dl-list-insert-after-iter (dl-list iter val)
  "Insert a value into the list after the position of the iterator."
  (let* ((next-node (dl-node-next-node iter))
         (new-node (make-dl-node :value val 
                                 :next-node next-node
                                 :prev-node iter)))
    (cond
      (next-node
       (setf (dl-node-prev-node next-node) new-node))
      (t
       (setf (dl-list-last-node dl-list) new-node)))
    (setf (dl-node-next-node iter) new-node)
    new-node))

(defun dl-list-insert-before-iter (dl-list iter val)
  "Insert a value into the list before the position of the iterator."
  (let* ((prev-node (dl-node-prev-node iter))
         (new-node (make-dl-node :value val 
                                 :next-node iter
                                 :prev-node prev-node)))
    (cond
      (prev-node
       (setf (dl-node-next-node prev-node) new-node))
      (t
       (setf (dl-list-first-node dl-list) new-node)))
    (setf (dl-node-prev-node iter) new-node)
    new-node))

(defun unit-test ()
  (let ((test-list (make-dl-list)))
    (assert (dl-list-empty-p test-list))
    (dl-list-push-front test-list 10)
    (assert (not (dl-list-empty-p test-list)))
    (assert (= (dl-list-length test-list) 1))
    (dl-list-push-front test-list 5)
    (assert (not (dl-list-empty-p test-list)))
    (assert (= (dl-list-length test-list) 2))
    (dl-list-push-back test-list 20)
    (assert (not (dl-list-empty-p test-list)))
    (assert (= (dl-list-length test-list) 3))
    (let ((iter (dl-list-iter-front test-list)))
      (assert (= (dl-list-iter-contents test-list iter) 5))
      (dl-list-insert-after-iter test-list iter 7)
      (assert (not (dl-list-empty-p test-list)))
      (assert (= (dl-list-length test-list) 4))

      (setf iter (dl-list-iter-next test-list iter))
      (assert (= (dl-list-iter-contents test-list iter) 7))

      (dl-list-insert-before-iter test-list iter 6)
      (setf iter (dl-list-iter-prev test-list iter))
      (assert (= (dl-list-iter-contents test-list iter) 6))

      (setf iter (dl-list-iter-next test-list iter))
      (assert iter)
      (assert (= (dl-list-iter-contents test-list iter) 7))

      (setf iter (dl-list-iter-next test-list iter))
      (assert iter)
      (assert (= (dl-list-iter-contents test-list iter) 10))

      (setf iter (dl-list-iter-next test-list iter))
      (assert iter)
      (assert (= (dl-list-iter-contents test-list iter) 20))

      (setf iter (dl-list-iter-next test-list iter))
      (assert (not iter)))

    (assert (= (dl-list-iter-contents test-list (dl-list-iter-front test-list)) 5))
    (assert (= (dl-list-iter-contents test-list (dl-list-iter-back test-list)) 20))

    (assert (= (dl-list-pop-front test-list) 5))
    (assert (= (dl-list-length test-list) 4))
    (assert (= (dl-list-iter-contents test-list (dl-list-iter-front test-list)) 6))

    (assert (= (dl-list-pop-back test-list) 20))
    (assert (= (dl-list-length test-list) 3))
    (assert (= (dl-list-iter-contents test-list (dl-list-iter-back test-list)) 10)))
  t)

(defmethod print-object ((node dl-node) stream)
  "Allow pretty-printing of the a node."
  (let ((prev-node (dl-node-prev-node node))
        (next-node (dl-node-next-node node)))
    (format stream "{ ~A <- ~A -> ~A }" 
            (and prev-node (dl-node-value prev-node))
            (dl-node-value node)
            (and next-node (dl-node-value next-node)))))

 

Programming in two computer languages

The circumstances of my job are a bit unusual.  I work on heavy math computational engines, and am the sole developer on these pieces of code.  Often there isn’t, at first, a clear path to solving the problem, and I will find myself trying out different approaches to see if they achieve the desired results.  It’s not unusual to have to discard code developed over two weeks because it turns out not to work for the problem.

This sort of coding progression can lead to very messy code.  You start down one path, set up your calling contexts and your APIs, then decide that this is the wrong approach and you have to come at the problem completely differently.  Now your APIs are wrong, or at least inefficient for the task.  There might be a pile of dead code intended to handle conditions that no longer arise.  You distort the code you’ve retained until it can be applied to the new approach, but your data structures are wrong, you’re re-doing expensive computations because it’s easier to call the function than to figure out how to cache it effectively, and so on.

The result of this tends to be that, by the time the code is done and working, it really desperately needs a rewrite for maintainability, ease of understanding, and support.

And this is where my employers have given me a very useful and valuable freedom.  Instead of shipping the messy prototype that works, they give me the time to rewrite it.  They use the prototype for demos and customer feedback, but meanwhile, I’m applying the lessons learned from the first time through to rewriting the code.  While this means that the project likely takes longer, it comes out more efficient, more maintainable, and more reliable.

However, programmers are famously lazy.  A rewrite can, all too easily, become a cut-and-paste edit session where the code is only modified in a few places.  To avoid this impulse, I write my prototypes in a language that is syntactically alien to the final version.

The code I write for work is in C++.  I prototype in Common Lisp.  Those languages are so different that I’m not going to be copying code from the prototype to the final C++ version.  I can apply the lessons I learned in redesigning my code paths.  I rewrite the code from the bottom-up.  I now understand what every class will be asked to do, so I can generate the write internal APIs, and then tie them together at the end.

Lisp has some very helpful features for this prototyping.  The ability to pass lambda functions to other functions makes it easy to try out several different options very quickly from the command line, without having to sit through a recompilation, and without needing to put in all the boilerplate that comes with building functions in C++.  This isn’t really a weakness of C++, the two languages are very different, and each has its own strengths.

I’m going to be talking a bit about Lisp in the next little while, bringing up some of the interesting parts of the language, the things that I miss when I’m not programming in Lisp.  I’m not likely to say anything that hasn’t already been said elsewhere, and probably more clearly, but maybe the perspective will be interesting.

I’ve been programming in Lisp for some years now.  A variant of it, muLisp, was one of the first languages that I programmed in, but I was inspired to come back to Lisp by this essay by Paul Graham.

Orbital mechanics and flying to the Sun

When I watch a science fiction television show or movie, I tend to divide the physics errors into two categories.  There are the ones that I ascribe to narrative or stylistic necessity, and there are the unnecessary mistakes.

In the first group I put things like sound effects in space scenes.  Of course, we all know that sound is not transmitted in a vacuum, but it is often an artistic choice to put sound into these scenes.  Certainly, there are cases where it is not done, the first example that springs to mind being “2001: A Space Odyssey“.  There, the sudden dead silence in some scenes was both realistic and dramatic.

In the second group, though, are things that generally don’t matter to the plot, that could be depicted realistically, but are not.  That brings us to flying into the Sun.

If one were to posit a spacecraft, starting at the Earth, with a trajectory intended to bring it close to the Sun in a flight time of weeks to months, how do you direct the thrust of your engines?  The common depiction treats a flight to the Sun as essentially driving a truck on an invisible highway.  You point your direction of thrust toward the centre of the Sun, turn on the engine, and fly straight there.  This is incorrect, such a trajectory is extremely inefficient, if achievable at all.

While there are many ways we can examine this problem, the simplest one I can think of uses very little math and fairly basic physics.  We will consider only angular momentum.

Angular momentum is a conserved quantity.  If I choose a point in space, the magnitude of my angular momentum relative to that point is equal to the product of my mass, speed and the distance of closest approach between my straight-line extended trajectory and the point of interest.  In mathematical terms, it is the cross product of my momentum and the vector connecting me with the point in space.

Just as momentum is conserved in the absence of a force, angular momentum is conserved in the absence of a torque.  Torque is, similarly, the cross product of the force applied and the vector connecting me with the point in space.

So, let’s consider our angular momentum relative to the centre of the Sun.  Now, when we begin our journey, we are traveling at the same speed as the Earth (approximately 30 km/s), around the Sun.  Our speed is roughly perpendicular to the line connecting the Earth to the Sun, as the Earth’s orbit is quite close to circular.  The magnitude of our angular momentum is, from basic trigonometry, about equal to mass times speed times distance.  That amounts to 4.5E+15 kg m^2/s per kilogram of spacecraft.

Now, we’ve pointed out engine straight away from the Sun, so that our applied force is exactly on the line connecting the spacecraft to the centre of the Sun.  That means that the torque is zero, because the cross product of parallel vectors is zero.  So, in this configuration, the engine cannot change the angular momentum of the spacecraft.  Yes, it can push us toward the Sun, but our initial sideways deflection keeps trying to push us out of the way.  Imagine that you just kept adjusting your engine so the thrust was always directed straight into the Sun, and you managed to just barely touch the edge of the Sun while swinging by.  The Sun’s radius is about 700000 km.  If, for simplicity, we ignore any change in the mass of the spacecraft, that means that it must have a speed along the surface of the Sun of 6430 km/s.  Now, it’s deeper in the Sun’s gravity.  An object starting at the Earth’s orbit and ending at the surface of the Sun would be expected to gain no more than 620 km/s in speed due to gravitational forces.  That leaves a deficit of about 5800 km/s that must come from the spacecraft’s engines.  That is a stupendous delta-V.  Holding onto this number, we now look at a better option.

If, instead, the spacecraft were to fire its engines so as to oppose its motion around the Sun, a much different result is seen.  We already mentioned that the Earth is moving at 30 km/s around the Sun.  So, we now set our engines to drive us backwards along the Earth’s orbit around the Sun.  We run the engines long enough to apply a delta-V of 30 km/s.  Our spacecraft is now sitting still in space, with zero angular momentum relative to the Sun.  But it can’t stay there.  The Sun’s gravity is pulling, and the spacecraft will fall into the Sun.  First slowly, then faster and faster, it will hit the Sun in just under 6 months.  If the trip is intended to take less time, then after the first burn has completed, the engines can now be directed to thrust toward the Sun, and thrust applied as needed.  Earlier thrust is more efficient than later thrust.

So, pushing toward the Sun, about 5800 km/s.  Pushing at 90 degrees to the Sun, about 30 km/s.  And yet you rarely see this handled correctly.

On the reading list

I used to spend an hour a day on the bus going to work, which was an hour a day to read a book.  Now, though, I bicycle to work whenever possible, and as my schedule doesn’t require me to go to the office every day, I bus to the office in the winter time, when I need to go in.  It’s a shorter ride, and there isn’t really time to set up and read, so my reading time has been greatly curtailed.

I used to buy lots of books by many different authors, but as my reading time has become more scarce, I’m having to narrow down to just the authors whose books I don’t want to miss.  I have reached the point where I’m buying almost only books from my “buy on sight” list.  That is, authors whose books I will buy on the strength of the author, without needing reviews, synopses, or even cover art.  If this author wrote it, I will buy it, and put it on my shelf to read.

While I have the Kindle software on my phone and tablet, I still prefer paper books to ones that are bound up in DRM software and the potential hassles and dangers.  I’ll buy unencumbered e-books, the Baen library is excellent for that.  I have bought a few Kindle books from Amazon, when they were in special sale bundles.  I also occasionally download out-of-copyright books from gutenberg.org.

Right now, I’m re-reading Vernor Vinge’s A Fire Upon The Deep. I read it almost 20 years ago, but now I have his sequel, The Children Of The Sky, on my shelf, to be read once I finish the earlier novel.

So, who is on my buy on sight list?

Together, these writers are writing faster than I can read to keep up.  I’m always hoping to find more time to read, and finish more books.

Other authors who would be promoted to this list if I could catch up include

Then, there are the authors who were on my buy on sight list, but have either died or stopped writing, and whose works I have read in close to their entirety.