Monthly Archives: July 2014

The less-familiar parts of Lisp for beginners — sublis and nsublis

Now, we look at sublis, and its relative nsublis.  You’ve probably realized by now that those functions with the ‘n’ prefix are generally destructive versions of the corresponding unprefixed function.  That is, the nsublis function is permitted to destroy its input tree.

What the sublis function does is to walk a tree and look up all subtrees and nodes as keys in the association list.  When a match is found, the value corresponding to that key is substituted.  A new tree is created that contains the substituted elements, and that may share elements with the input tree.  I will provide some examples below.

Note that the spec does not appear to provide any hard rules about the order of tree traversal, so the programmer should be careful to avoid changes that might feed back into themselves, as can happen with more complex :test functions.

Here are some examples of sublis use.  Note that if you provide your own test function it has to be able to handle receiving both sublists and nodes in its arguments.
*slime-repl sbcl*

CL-USER> (let ((swaps '((1 . "ONE")
                        (2 . "TWO")
                        (3 . "THREE")
                        (4 . "FOUR")))
               (demo-tree '((1 2)
                            (3 4 5 6)
                            (7 (8 9 10) 1))))
           (sublis swaps demo-tree))
(("ONE" "TWO") ("THREE" "FOUR" 5 6) (7 (8 9 10) "ONE"))
CL-USER> (labels
             ((same-type (x y)
                (and (numberp x)
                     (numberp y)
                     (= (mod x 2)
                        (mod y 2)))))
           (let ((types '((1 . "ODD")
                          (2 . "EVEN")))
                 (demo-tree '((1 2)
                              (3 4 5 6)
                              (7 (8 9 10) 1))))
             (pprint-linear t
                            (sublis types demo-tree 
                                    :test #'same-type))))

(("ODD" "EVEN")
 ("ODD" "EVEN" "ODD" "EVEN")
 ("ODD" ("EVEN" "ODD" "EVEN") "ODD"))

The less-familiar parts of Lisp for beginners — stream-external-format

Our next obscure function is stream-external-format.  This is entirely an implementation-dependent function.  Some implementations may have different on-disc formats for data, and using a different external format may result in different bytes being delivered to the disc.  All return values from this function have implementation-dependent meanings, so the programmer must be aware of this fact when writing code intended to be portable.

To provide a specific example, SBCL allows the user to open a character stream for writing with any of several external formats.  For instance, one can write in UTF-8, UTF-16BE, UTF-32LE, ISO-8859-5, EBCDIC-US, to name just a few.  Each of these has a different external format keyword, which stream-external-format will return.

The less-familiar parts of Lisp for beginners — stream-element-type

Moving on to the stream-element-type function.  We should first describe streams and their element types.  A stream in Lisp looks a little like an iostream in C++.  It is an opaque object that defines an interaction between the program and what a UNIX system would call a character device (as opposed to a block device).  A stream may take special action to distinguish between text and binary data, and has equivalents to tellp and seekp.

A Lisp stream has an associated element type which must be a subtype of character or of integer.  If it’s a subtype of character, it can be used with functions like format, read, and others.  If it’s a subtype of integer, it can be used with functions like read-byte, write-byte, read-sequence, and write-sequence.

The stream-element-type function allows the programmer to detect at runtime whether a stream is a character stream or an integer stream.  Appropriate behaviour can then take place based on the compatibility with that particular stream.

One thing I will note.  While I was testing behaviour in SBCL 1.1.14, I was a bit surprised to see that the write-byte and read-byte functions, while defined in the CLHS as writing individual bytes, actually write and read one entry from the stream.  If the stream element type is (integer 0 65535), the entries are 16 bits long, and read-byte reads a 16-bit word from the stream, not a single byte.  I was unable to find anything in the CLHS among the clarifying notes that would tell me whether this is required, allowed, or a bug.  If anybody knows, please pass on your knowledge in the comments.

The less-familiar parts of Lisp for beginners — special-operator-p

In Common Lisp there are several operators that are referred to as “special”.  A special operator is one which has different behaviour in terms of bindings or flow control.  The list can be found, for instance, here.  The programmer cannot create their own special operators, there is no way to create a new entity for which special-operator-p returns non-nil.

Some examples will, perhaps, clarify what this means.  The Common Lisp if special operator takes two or three arguments.  The first is the condition, the second is evaluated only if the condition evaluates to non-nil, and the optional third argument is evaluated only if the condition evaluates to nil.  Hidden within the if form, there is a flow control that decides whether or not to evaluate certain arguments.

In the context of bindings, catch sets up a dynamic binding that becomes important if code below it invokes throw.  The labels special operator sets up a lexical binding within its scope.

The special-operator-p function returns non-nil if the symbol passed as its argument corresponds to a special operator.  Now, when might the programmer need to use this?  Most obviously in a code walker, something that reads and analyses Lisp code.  I have never seen it used other than in informational contexts, to label a particular piece of code as containing a special operator, or by the implementation to forbid the redefinition of such operators.  I haven’t seen a context in which complex actions are initiated by special-operator-p returning non-nil, only messages, errors, or skipping over a block while analysing code.

The less-familiar parts of Lisp for beginners — special

We’ve hinted a few times at special variables, but I’ll put it here in one spot to make it easier to find.  The special declaration is used, for instance in declaim or declare, to indicate that a variable should have dynamic binding.

The most important thing to realize about a dynamic variable is that it behaves as if implemented by a push-down stack.  Declaring a new local variable with the same name, for instance with let, creates a new dynamic extent that is visible in any called functions.  Modifications to the value of the variable are visible until the dynamic extent is exited, at which point the next enclosing extent becomes the current one.

It is a common convention that special variables have variable names that begin and end in an asterisk, but this is not typically enforced by the implementation.  Variables created with defvar or defparameter are always dynamic.

Here’s some simple code to demonstrate the behaviour:

(defparameter *myvar* 10)

(defun printvar ()
  (format t "*myvar*= ~D~%" *myvar*))

(defun incvar ()
  (incf *myvar*))

(defun demonstrate ()
  (format t "Outermost dynamic extent:~%")
  (format t "Incrementing the value~%")
  (format t "Creating a new dynamic extent with value 15:~%")
  (let ((*myvar* 15))
    (format t "Incrementing the value~%")
  (format t "Exiting this new dynamic extent~%")

with output:
*slime-repl sbcl*
CL-USER> (demonstrate)
Outermost dynamic extent:
*myvar*= 10
Incrementing the value
*myvar*= 11
Creating a new dynamic extent with value 15:
*myvar*= 15
Incrementing the value
*myvar*= 16
Exiting this new dynamic extent
*myvar*= 11