Tag Archives: programming

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.

List-printing code for upcoming posts

I’m about to start what may be a long series of posts about the Lisp language for newcomers arriving from a C++ background.  Before I get to that, I’m going to write a bit of handy code to produce drawings of lists similar to those we often see in Lisp textbooks.

To review, lists in Lisp are a bit different from std::slist classes in the C++ STL.  In C++, a list has a single entry point, and, while you can have multiple references to the list, they all have the same view on the list.  In Lisp, you could think of a reference to a list as a data pair.  The reference has a pointer to the list object itself, but it also has a position marker, like an iterator, which is its entry point into the list.  Because lists in Lisp are singly-linked, you can have multiple references to the same underlying object, but they’ll have different views of the list.  To demonstrate this, here’s some printing code.
 

;; Some code to pretty-print a list with multiple entry points
;;
(defparameter *rec-width* 10)

(defun plot-list-worker (&rest entries)
  "Given inputs of the form (list1 \"list1\") (list2 \"list2\")..., pretty-prints the list with multiple entry points.  That is, the first entry in 'lists' is the symbol-name proper superlist of the second, which is a proper superlist of the third, etc."
  (let* ((big-list (first (first entries)))
         (total-list-len (length big-list)))

    ;; print the entry points
    (let ((prev-indents '()))
      (dolist (entry entries)
        (let* ((e-handle (first entry))
               (e-name (second entry))
               (indent (1+ (* *rec-width* 
                              (- total-list-len 
                                 (length e-handle))))))
          (dolist (p-i (reverse prev-indents))
            (format t "~VT." (+ p-i 2)))
          (format t "~VT~A~%" indent e-name)
          (push indent prev-indents)))
      (dotimes (i 2)
        (dolist (p-i (reverse prev-indents))
          (format t "~VT." (+ p-i 2)))
        (format t "~%")))

    ;; print the boxes
    (dotimes (i total-list-len)
      (format t "~VT-----" (1+ (* i *rec-width*))))
    (format t "~%")
    (dotimes (i total-list-len)
      (format t "~VT|A|D| -->" (1+ (* i *rec-width*))))
    (format t "NIL~%")
    (dotimes (i total-list-len)
      (format t "~VT-----" (1+ (* i *rec-width*))))
    (format t "~%")

    ;; print the drops to the values
    (dotimes (i 2)
      (dotimes (j total-list-len)
        (format t "~VT |" (1+ (* j *rec-width*))))
      (format t "~%"))

    (dotimes (i total-list-len)
      (let ((j (- total-list-len i 1)))
        (dotimes (k j)
          (format t "~VT |" (1+ (* k *rec-width*))))
        (format t "~VT~A~%" (1+ (* j *rec-width*)) (nth j big-list))))
))

(defmacro plot-lists (&rest lists)
  "Set up and invoke plot-lists-worker"
  (let ((arglist))
    (dolist (lname lists)
      (push (list 'list lname (symbol-name lname)) arglist))
    `(plot-list-worker ,@(reverse arglist))))

Now, I can create a single list with multiple entry points, and plot them.  Here’s the invocation and output, from the SLIME development environment.
 

CL-USER> (let* ((clist (list 5)) 
                (blist (append (list 3 4) clist))
                (alist (append (list 1 2) blist)))
           (plot-lists alist blist clist))
 ALIST
   .                 BLIST
   .                   .                 CLIST
   .                   .                   .
   .                   .                   .
 -----     -----     -----     -----     -----
 |A|D| --> |A|D| --> |A|D| --> |A|D| --> |A|D| -->NIL
 -----     -----     -----     -----     -----
  |         |         |         |         |
  |         |         |         |         |
  |         |         |         |        5
  |         |         |        4
  |         |        3
  |        2
 1
NIL

The ‘alist’ view on the list sees a list of 5 objects, while ‘blist’ cannot see the first two objects, and sees only a list of 3.

There is, however, another way in which Lisp lists differ from C++ std::slist objects.  Lists in Lisp can be spliced together.  It is possible to have two different lists which join partway down their lengths, so that they share all elements beyond the join.  I’m not going to try to draw that.  There is no parallel to this in C++ std::slist objects.

OK, with that taken care of, further posts will follow.

Getting Lisp programming help

I’m not really going to say much here, there are places you can go to get help with Lisp problems.  One can go looking at the usual suspects, like stackoverflow or the Lisp reddit page.  You can also look for help on the #lisp IRC channel on freenode.net.  There may even be a Lisp users group in your local area.

As always, though, don’t perform drive-by questioning where you pop in, brusquely ask a question, then run off.  By asking questions on any of these, you’re talking with real people who have to take the time to explain to you, they’re doing you a favour.  Spend a few hours reading the text of other questions, or watching the interactions of the people on the IRC channel.  Get to understand the culture of the group you’re going to be asking questions of, even if just a little bit.  Also, spend some time trying to figure out the solution to your problem before going for help, and, if appropriate, describe what you tried to do and what went wrong.  The replies you receive are likely to be more helpful then, as people explain not only how you should approach the problem, but also why your unsuccessful attempts did not work out.

Later, when you feel your understanding is sufficient, consider spending time watching those resources for an opportunity to help newcomers.