Category Archives: Uncategorized

The less-familiar parts of Lisp for beginners — allocate-instance

Continuing our series of posts on the more obscure commands of Lisp that beginners arriving from C++ might not have encountered and might not know when to use, we come to allocate-instance.

Think of this command as something that returns an object that hasn’t been constructed/initialized.  It’s an operation that has no counterpart in C++.  The object is built without filling in any of its slots.

Now, this may seem like a somewhat unnecessary function.  After all, why not just build the object with its slots initialized, and then overwrite the slots in a separate operation?  Well, there can be cases where allowing the object to be built normally, with make-instance, is undesirable.  A simple example might be the following:
 

;; A situation where you might prefer allocate-instance to
;; make-instance.


(let ((number-seq 0))

  (defun get-next-seq-id ()
    (incf number-seq)))

(defclass myclass ()
  ((id          :reader get-id
                :initform (get-next-seq-id))
   (data        :accessor get-data)))

(defun demonstrate ()
  (let ((obj1 (make-instance 'myclass))
        (obj2 (make-instance 'myclass))
        (obj3 (make-instance 'myclass)))

    (format t "ID of obj1= ~D~%" (get-id obj1))
    (format t "ID of obj2= ~D~%" (get-id obj2))
    (format t "ID of obj3= ~D~%" (get-id obj3))))

So, let’s say you’ve built this system, and you have some need to construct a new object which reuses an earlier ID.  Perhaps there was a bug that showed up only when a specific ID was passed into your hashing function, and you need to replicate the bug, but the object no longer exists.  As set up, a call to make-instance results in the next number in the sequence being allocated, and there’s no way to prevent the ID allocator from incrementing its internal state.

By using allocate-instance, you create a new object without calling its initform slot options.  Of course, you can imagine other contexts where avoiding the initform options are desirable, such as if the initform is very time-consuming, or if it invokes operations that affect the state in some way, such as opening network connections or disc files.

One place where I have seen allocate-instance used is in a generic object serializer in the cl-containers package.  There, objects can be passed to a method that writes them out to disc, and later they can be read back in.  To avoid complications during the read-in, the objects are allocated with allocate-instance and then the slots are individually restored from the disc file using a (setf (slot-value …) …) construct.

The less-familiar parts of Lisp for beginners — adjust-array

Continuing this series of posts on less familiar parts of Lisp that C++ programmers might not have encountered when starting with Lisp, we have adjust-array.

I’m only going to talk about this in the absence of displaced arrays.  We’ll get to a discussion of displaced array later in this series.  For now, we’ll just describe a simple use of adjust-array.

This function is used to change the dimensions of an array (but not the rank of the array, i.e. the number of dimensions).  When applied, adjust-array either modifies the array or returns a new array whose contents are derived from the contents of the array being adjusted.  If when the original array was created, it was marked as adjustable, then adjust-array modifies the array, otherwise it returns a new array.  Note that, if the input array was not adjustable, and a new array is created, the original array is destructively modified.

For each index in the array, if the new size of that dimension is smaller, elements that are no longer spanned by the new dimensions are absent from the adjusted array.  If the new size of that dimension is larger, new elements are inserted into those positions that did not exist in the input array.  If a particular n-tuplet of indices exists in both the input array and the adjusted array, then the contents of both arrays will be the same there.

To visualize this in two dimensions, imagine that you’ve laid out the array, populating its cells.  You then overlay a second array of the same rank but different dimensions.  Some rows or columns may be absent in this second array, and those elements will not appear in the second array.  Some rows or columns may be present in the second array but not in the first, in which case the new elements will be filled in with a default value.  Where the arrays overlap, the elements are the same.

Here are some examples using both a non-adjustable array and an adjustable array.  The original array is filled with a number sequence, and the adjustment is told to fill in newly-available array slots with the number 20.
*slime-repl sbcl*  

CL-USER> (let ((original-array 
                (make-array '(3 3) 
                            :initial-contents '((1 2 3)
                                                (4 5 6)
                                                (7 8 9))
                            :adjustable nil)))
           (format t "original-array before adjust= ~A~%"
                   original-array)
           (let ((new-array (adjust-array original-array
                                          '(2 4) 
                                          :initial-element 20)))
             (format t "original-array after adjust= ~A~%"
                     original-array)
             (format t "new-array= ~A~%" new-array)
             (format t "Arrays are same object= ~A~%" 
                     (eq new-array original-array))))

original-array before adjust= #2A((1 2 3) (4 5 6) (7 8 9))
original-array after adjust= #2A((1 2 3) (20 4 5) (6 20 9))
new-array= #2A((1 2 3 20) (4 5 6 20))
Arrays are same object= NIL
NIL
CL-USER> (let ((original-array 
                (make-array '(3 3) 
                            :initial-contents '((1 2 3)
                                                (4 5 6)
                                                (7 8 9))
                            :adjustable t)))
           (format t "original-array before adjust= ~A~%"
                   original-array)
           (let ((new-array (adjust-array original-array
                                          '(2 4) 
                                          :initial-element 20)))
             (format t "original-array after adjust= ~A~%"
                     original-array)
             (format t "new-array= ~A~%" new-array)
             (format t "Arrays are same object= ~A~%" 
                     (eq new-array original-array))))
original-array before adjust= #2A((1 2 3) (4 5 6) (7 8 9))
original-array after adjust= #2A((1 2 3 20) (4 5 6 20))
new-array= #2A((1 2 3 20) (4 5 6 20))
Arrays are same object= T
NIL

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.