Monthly Archives: December 2013

The less-familiar parts of Lisp for beginners — adjoin

We continue this series of posts about functions that a beginning Lisp user coming from C++ might not have encountered with adjoin.  There isn’t really too much to say about this one, other than to note that it is really a shortcut for a common construction.

The adjoin command is really just a conditional cons.  It builds a new list by prepending a new element, but only if that element is not already present in the list under the equality condition defined by the :key and :test parameters.
 

CL-USER> (let ((a '(1 2 3 4 5)))
           (format t "Input list is:  ~A~%" a)
           (format t "Adjoined with '1':  ~A~%" (adjoin 1 a))
           (format t "Adjoined with '10':  ~A~%" (adjoin 10 a)))
Input list is:  (1 2 3 4 5)
Adjoined with '1':  (1 2 3 4 5)
Adjoined with '10':  (10 1 2 3 4 5)

Note that, as with cons, the place isn’t modified as it is with pushd.  That is, (push 1 a) modifies ‘a’ so it points to the new list with the ‘1’ prepended.  The adjoin and cons functions do not do this.
 
CL-USER> (let* ((a '(1 2 3 4 5))
                (b (adjoin 1 a))
                (c (adjoin 10 a)))
           (format t "~%A EQ B has value:  ~A~%~%" (eq a b))
           (plot-lists c a))

A EQ B has value:  T

 C
   .       A
   .         .
   .         .
 -----     -----     -----     -----     -----     -----
 |A|D| --> |A|D| --> |A|D| --> |A|D| --> |A|D| --> |A|D| -->NIL
 -----     -----     -----     -----     -----     -----
  |         |         |         |         |         |
  |         |         |         |         |         |
  |         |         |         |         |        5
  |         |         |         |        4
  |         |         |        3
  |         |        2
  |        1
 10

The less-familiar parts of Lisp for beginners — add-method

Next in the series of methods that the C++ programmer might never have encountered when picking up Lisp, and might not know how to use, is add-method.  This function is used to add a generic function to the running Lisp.  Before continuing, you might want to review a brief overview of the differences between C++ and Lisp object models, available here, here, and here.

In C++ parlance, imagine the following:  you have a base class that defines a virtual function fred().  There is a derived class that does not define its own version of fred(), so it uses the base class function.  The effect of add-method is as if you could, at run time, add a new fred() function specialized on the derived class, or replace an existing specialization.

In Lisp, add-method is typically used by the system, as part of the defmethod macro, but it can be invoked by the programmer if needed.

To demonstrate the use of add-method, let’s create a tiny portion of a dungeon crawling game.  One with players, non-player characters, and monsters.  These entities can fall and be injured, but will heal with time.  We’ll say that monsters are tougher, they take half damage from falling:
 

;; Demonstrate the add-method function

(defclass actor ()
  ((hit-points          :accessor get-hp
                        :initform 100)
   (max-hp              :accessor get-max-hp
                        :initform 100)))

(defclass player (actor)
  ())

(defclass npc (actor)
  ())

(defclass monster (actor)
  ())

(defparameter *basic-fall-distance* 10.0)
(defparameter *basic-regeneration-time* 100.0)

(defgeneric apply-fall-damage (object distance)
  (:documentation "Modify the object's HP by distance fallen."))

(defgeneric regenerate-hp (object time-since-prev-regen)
  (:documentation "Apply time-based healing.  Returns the unused time."))

(defmethod apply-fall-damage ((object actor) distance)
  (decf (get-hp object) (floor (/ distance *basic-fall-distance*))))

(defmethod apply-fall-damage ((object monster) distance)
  (decf (get-hp object) (floor (/ distance (* 2 *basic-fall-distance*)))))

(defmethod regenerate-hp ((object actor) time-since-prev-regen)
  (multiple-value-bind (regen remainder)
      (floor (/ time-since-prev-regen *basic-regeneration-time*))
    (setf (get-hp object) (min (get-max-hp object)
                               (+ regen (get-hp object))))
    remainder))

(defun play ()
  (let ((player (make-instance 'player))
        (npc (make-instance 'npc))
        (monster (make-instance 'monster)))

    (format t "Player's hit points:  ~D~%" (get-hp player))
    (format t "NPC's hit points:  ~D~%" (get-hp npc))
    (format t "Monster's hit points:  ~D~%" (get-hp monster))
    (format t "~%~%")
    (format t "All of them fall 100'~%~%")
    (apply-fall-damage player 100.0)
    (apply-fall-damage npc 100.0)
    (apply-fall-damage monster 100.0)
    (format t "Player's hit points:  ~D~%" (get-hp player))
    (format t "NPC's hit points:  ~D~%" (get-hp npc))
    (format t "Monster's hit points:  ~D~%" (get-hp monster))
    (format t "~%~%")
    (format t "They all rest for 250 seconds~%~%")
    (regenerate-hp player 250.0)
    (regenerate-hp npc 250.0)
    (regenerate-hp monster 250.0)
    (format t "Player's hit points:  ~D~%" (get-hp player))
    (format t "NPC's hit points:  ~D~%" (get-hp npc))
    (format t "Monster's hit points:  ~D~%" (get-hp monster))
))

Now, if we run the play function, we get this:
 

CL-USER> (play)
Player's hit points:  100
NPC's hit points:  100
Monster's hit points:  100

All of them fall 100'

Player's hit points:  90
NPC's hit points:  90
Monster's hit points:  95

They all rest for 250 seconds

Player's hit points:  92
NPC's hit points:  92
Monster's hit points:  97

So, imagine that you have this system, and somebody comes along with an add-on module.  This module, among other things, adds an “easy mode” to make falling less damaging to players, but not to NPCs.  There is a single base-class falling damage method that applies to both players and NPCs, so how do we do that?  Well, we can add a method, specialized on players, and give it a different falling damage calculation:
 

(defun set-easy-mode ()
  (add-method (ensure-generic-function 'apply-fall-damage)
              (funcall #'make-instance 'standard-method
                       :specializers (list (find-class 'player)
                                           (find-class 't))
                       :lambda-list '(object distance)
                       :function #'(lambda (args ignore-me)
                                     (declare (ignorable ignore-me))
                                     (let ((object (first args))
                                           (distance (second args)))
                                       (decf (get-hp object) (floor (/ distance (* 2 *basic-fall-distance*)))))))))

Now, we invoke the easy mode, and re-run play:
 

CL-USER> (set-easy-mode)
#<STANDARD-GENERIC-FUNCTION APPLY-FALL-DAMAGE (3)>
CL-USER> (play)
Player's hit points:  100
NPC's hit points:  100
Monster's hit points:  100

All of them fall 100'

Player's hit points:  95
NPC's hit points:  90
Monster's hit points:  95

They all rest for 250 seconds

Player's hit points:  97
NPC's hit points:  92
Monster's hit points:  97

The player now receives less damage from the fall, while the NPC doesn’t benefit from the change.

Of course, if this particular scenario had been envisioned when the game was being written, we would not have to use add-method to modify it this way.  There are other ways to code this kind of flexibility, but if you have a running Lisp instance and realize that you need to create or modify a generic function, this is the way to do it.  There is no parallel for this exact behaviour in C++.

The less-familiar parts of Lisp for beginners — acons

I’m continuing this series of posts introducing Lisp to C++ programmers.  So, you’ve decided to try your hand at Lisp.  You’ve read some introductory book, or looked at your old class notes, and started programming with an editor on the screen and a language reference at hand.

As you go, you pick up some useful functions and techniques, but you probably realise after a while that you’re using maybe fewer than half of the functions defined in the standard.  Maybe this is because “there’s more than one way to do it”, but maybe you’re writing code that’s more convoluted than necessary because you haven’t come across the function that would perform in one step what you’re doing in three steps.

I’m going to try to guess at which functions you’ve somehow managed not to run across in your initial programming attempts, and show, with context, what these functions do.  I’m not going to be going over functions that are deprecated according to the standard, those really are examples of “more than one way to do it”, and you should try to stick to the non-deprecated functions in new code.

I’m going through these functions in alphabetical order, and the first one that I think might not be have been encountered in a casual introduction to Lisp is acons.

Before I get into this, it’s probably a good idea to review the behaviour of lists in Lisp.  Your introduction to Lisp probably showed you the basic model of a list in Lisp.  Conceptually, you have a set of cells, each divided into two parts, the car and the cdr.  Don’t worry about those strange names, they are, along with cons, actually assembly-language mnemonics for instructions on the old IBM 704 computer that can be used to implement these Lisp operations.

Recalling the descriptions of lists that I laid out in this posting, one way in which you can prepend data to a list is to use the cons function.  The acons function is similar, but is specifically designed for use with association lists.

An association list is a particular form of list in Lisp.  It is a list of conses, where the car component holds a key and the cdr component holds a value.  Here’s how an association list might look:
 

CL-USER> (let (alist)
           (setf alist (acons 1 "ONE" alist))
           (setf alist (acons 2 "TWO" alist))
           (setf alist (acons 3 "THREE" alist))
           (plot-lists alist))
 ALIST
   .
   .
 -----     -----     -----
 |A|D| --> |A|D| --> |A|D| -->NIL
 -----     -----     -----
  |         |         |
  |         |         |
  |         |        (1 . ONE)
  |        (2 . TWO)
 (3 . THREE)

An association list is typically used to accumulate key/value pairs, a bit like a C++ std::map.  There are some differences, though:

  • Lisp association lists don’t require a weak ordering, as the list is unsorted.
  • Consequently, searching is O(N), rather than O(log N) as it is for std::map.
  • The first encountered match is returned, so entries can be superseded simply by pushing an entry with a matching key earlier in the list, as long as one remembers that the hidden elements are still there and still affect traversal time.
  • Because Lisp isn’t strongly typed, the keys and values can be anything, subject to the restriction that the keys must all be valid inputs to your :test function when looking up values with the assoc function.

Now, acons behaviour can be duplicated with push, as shown here:
 

CL-USER> (let (alist)
           (setf alist (acons 1 "ONE" alist))
           (setf alist (acons 2 "TWO" alist))
           (push (cons 3 "THREE") alist)
           (plot-lists alist))
 ALIST
   .
   .
 -----     -----     -----
 |A|D| --> |A|D| --> |A|D| -->NIL
 -----     -----     -----
  |         |         |
  |         |         |
  |         |        (1 . ONE)
  |        (2 . TWO)
 (3 . THREE)

Given this easy substitution, is there any reason to use acons when push does the same thing with fewer keystrokes?  Well, that will be a matter of programmer preference.  By using acons, you make it obvious that you’re working with an association list, as opposed to another form of list.  Personally, I use the push form when I’m programming.