A heap for proletarians

Hash tables and arrays typically support efficient access to arbitrary elements. What if we need efficient access to elements based on some priority? Say for example, we need to fetch the minimum element in O(1) time. The data type that provide this kind of access is known as a priority queue. Priority queues are typically implemented as heap-ordered trees, in which the element at each node has higher “priority” than the elements at its children. Under this invariant, the element with the top priority will always be at the root of the tree. The priority of each node will be determined by a predicate, like one of the comparison operators.

In this post we take a detailed look at the implementation of a purely functional priority queue using a variant of the heap data structure known as the leftist heap. We will do the implementation in two steps. First, a core set of Clojure functions that manipulate a leftist heap is implemented. Then we will wrap these functions into an object that can be recognized by the built-in sequence functions – first, rest and conj.

The Leftist Heap

In a leftist heap, each node has an associated s-value or rank which is the node’s distance to the nearest leaf (an empty-node). The leftist heap also maintains the invariant that the right subtree of each node has the lowest rank. In other words, the left subtree of a node will be at least as large as the right subtree. It is usually taller than the right subtree, giving the heap its name. As a consequence, the right subtree will always have the shortest path to an empty node.

The right subtree of a leftist heap is stored in sorted order. This means two leftist heaps can be merged by simply merging their right subtrees and then swapping the nodes along this path as necessary to restore the leftist property.

Merging leftist heaps has worst-case O(log n) complexity and this is what makes this data structure interesting. The merge operation we just described can be expressed in Clojure as,

(defn heap-merge
  [h1 h2]
  (cond
    (empty-heap? h1) h2
    (empty-heap? h2) h1
    :else (let [[_ x a1 b1] h1
                [_ y a2 b2] h2]
            (if (<= x y)
              (make-node x a1 (heap-merge b1 h2))
              (make-node y a2 (heap-merge h1 b2))))))

Heap-merge makes use of a few helper functions. The make-node function encodes a single node as the list  [rank, node-value, left-subtree, right-subtree]. It also calculates the rank of the node and swaps the left and right subtrees as needed.

(defn make-node
  [obj subtree-a subtree-b]
  (let [ra (node-rank subtree-a)
        rb (node-rank subtree-b)]
    (if (>= ra rb)
      [(inc rb) obj subtree-a subtree-b]
      [(inc ra) obj subtree-b subtree-a])))

The node-rank function returns the rank associated with a node:

(defn node-rank
  [h]
  (if (empty-heap? h)
    0
    (first h)))

An empty heap is represented by the keyword :E.

(def empty-heap :E)

(defn empty-heap?
  [h]
  (= h empty-heap))

With the efficient merge function in place, we may proceed to implement the interface of the priority queue. This consists of three functions – pq-insert, pq-find-min and pq-delete-min.

Pq-insert creates a single-node tree with the new element and merges it with an existing heap:

(defn pq-insert
  [obj h]
  (heap-merge [1 obj empty-heap empty-heap] h))

Pq-find-min return the root of the heap:

(defn pq-find-min
  [h]
  (when-not (empty-heap? h)
    (let [[_ obj _ _] h] obj)))

Pq-delete-min will discard the root and return a new heap constructed by merging the two subtrees:

(defn pq-delete-min
  [h]
  (if (empty-heap? h)
    h
    (let [[_ obj left right] h]
      (heap-merge left right))))

As pq-insert and pq-delete-min basically does a merge, both of them run in O(log n) time. Pq-find-min runs in O(1) time.

With these core functions in place, we are ready to use the leftist-heap priority queue!

clojure> (def pq (pq-insert 231
                   (pq-insert 154
                    (pq-insert 900 empty-heap))))
clojure> (pq-find-min pq)
;; 154
clojure> (def pq (pq-delete-min pq))
clojure> (pq-find-min pq)
;; 231
clojure> (def pq (pq-delete-min pq))
clojure> (pq-find-min pq)
;; 900
clojure> (def pq (pq-delete-min pq))
clojure> (pq-find-min pq)
;; nil

Exercise 1.  Heap-merge uses the <= numeric comparison function for prioritizing the nodes. Make this more generic by making the priority-operation configurable by the user.

The Priority Queue as a Seq

Clojure defines many useful operations in terms of sequences.  A sequence is immutable and persistent. As a result, they are thread-safe and can share their state freely.

The priority queue we implemented in the previous section is also immutable and persistent. So it would be a good candidate for being a sequence. Let us make the priority queue respond to the first, rest and conj functions. These functions in turn can be used to describe more sophisticated priority queue processing operations. This way our custom data structure is also given a chance to blend nicely with the rest of Clojure.

To be treated as a sequence, a type has to implement the clojure.lang.ISeq interface. We will use the deftype macro to define a LeftistHeapPriorityQueue that implements the ISeq interface.

While iterating over a sequence, it is idiomatic in Clojure to call the seq function to check for termination. A priority queue may sometimes be involved in an iteration, as part of a debugging session or for fetching all values sorted by priority. So let us also make our new type respond properly to the seq function call. This function is declared in the clojure.lang.Seqable interface.

The final definition of LeftistHeapPriorityQueue follows:

(deftype LeftistHeapPriorityQueue [pq]
  clojure.lang.ISeq
  ;; return a seq of the rest of the elements,
  ;; return nil if no elements remain.
  (next [_] (let [pq-rest (pq-delete-min pq)]
              (when-not (empty-heap? pq-rest)
                (LeftistHeapPriorityQueue. pq-rest))))

  ;; return the first element.
  (first [_] (pq-find-min pq))

  ;; return the sequence with the first item removed,
  ;; or an empty sequence if no items remain.
  (more [this] (or (next this) '()))`

  ;; return a new sequence with `obj` prefixed,
  ;; invoked via the global `conj`.
  (cons [_ obj] (LeftistHeapPriorityQueue. (pq-insert obj pq)))

  clojure.lang.Seqable
  (seq [this] (when (.next this) this)))

The helper function pq-insert-all used by cons is,

(defn pq-insert-all
  "Insert all elements from the sequence `objs` into the
   priority queue `pq`."
  [objs pq]
  (loop [xs objs, pq pq]
    (if (seq xs)
      (recur (rest xs) (pq-insert (first xs) pq))
      pq)))

Exercise 2.  The pq-insert-all function runs in O(n log n) time. Is a more efficient (as in O(n)) alternative implementation possible?

To make it convenient to create priority queues from a sequence of values,
let us define a “constructor” of LeftistHeapPriorityQueues:

(defn priority-queue
  ([objs]
   (LeftistHeapPriorityQueue. (pq-insert-all objs empty-heap)))
  ([]
   (priority-queue [])))

Finally, by implementing the print-method multimethod, we can let the REPL know how to display a LeftistHeapPriorityQueue literal:

(defmethod print-method LeftistHeapPriorityQueue
  [tree ^java.io.Writer w]
  (.write w (str "#lhpq<" (.first tree) " ...>")))

Before we say goodbye, here is a REPL session with our new sequence type:

clojure> (def a (priority-queue [1 123 12 45]))
clojure> (seq a)
;; #<lhpq<1 ...>
clojure> (seq? a)
;; true
clojure> (first a)
;; 1
clojure> (def a (rest a))
clojure> (first a)
;; 12
clojure> (def a (conj a 50))
clojure> (first (rest a))
;; 45
clojure> (first (rest (rest a)))
;; 50

Downloads

The full source code for this post.

References

  1. The original implementation of the leftist-heap priority queue can be found in Chapter 3 of Chris Okasaki’s Purely Functional Data Structures.
  2. Inside Clojure/Sequences.

Bits of things

Most programming languages provide I/O facilities over streams of bytes. For instance, the Java abstract classes java.io.InputStream and java.io.OutputStream declare interfaces for performing input and output on byte streams. These interfaces are implemented by classes dedicated for performing I/O on files, pipes and in-memory buffers. Sometimes we also have to deal with streams of bits. Consider the frames in an MP3 file where the frame header is encoded as bit-fields of varying lengths. Another example is that of a TCP header, the layout of which is illustrated below:

TCPHeader.png

Some fields in the TCP header are encoded using two or more bytes. For example, the Source and destination ports are 16 bits each (2 bytes). Sequence and acknowledgement numbers are 32 bit values (4 bytes). Normal byte streams should be sufficient for reading and writing these values. But there are also fields that do not fall on proper byte offsets. For instance, the data offset field is 5 bits and the reserved field is 6 bits. The six flags that follow are 1 bit each. As most I/O libraries treat bytes as the fundamental unit of information, special bit-twiddling code is required to encode and decode a TCP header. Writing such code can be difficult and error-prone. When we have to pack information in a space-efficient way, an abstraction that can perform I/O on streams of bits starts to look attractive!

In this blog post we develop such an abstraction for the JVM. In this process, we will learn how to mix high-performance Java code with Clojure. We will also see how the expressiveness of Clojure can enhance the usability of lower-level abstractions.

We will start with a simple and efficient library that allows us to read and write bits over an underlying stream. This underlying stream must be an implementation of java.io.InputStream or java.io.OutputStream. As objects of these classes can do I/O only on bytes, the bit stream library has to maintain some local state. At the bare minimum it will require a byte to pack together the bits seen so far. An integer counter is needed to keep track of the current bit position. As the library does I/O, fast and frequent updates to both these state variables become inevitable. So we will implement the lower-level I/O code as two Java classes – bits.BitsReader and bits.BitsWriter.

package bits;

import java.io.InputStream;
import java.io.IOException;

/**
 * Read bits from an InputStream.
 */
public class BitsReader {

    private InputStream bytesInput;
    private int currentByte;
    private int bit;

    public BitsReader(InputStream inputStream) {
        bytesInput = inputStream;
        currentByte = 0;
        bit = 0;
    }

    /**
     * Read the next bit, as either 1 or 0, from `bytesInput`.
     * At the end of the input stream, return -1.
     */
    public int read() throws IOException {
        // `currentByte` is exhausted of bits, read the 
        // next byte from the InputStream.
        if (bit == 0) {
            currentByte = bytesInput.read();
            if (currentByte == -1) return currentByte;
            // Reset bit index to the beginning 
            // of `currentByte`.
            // 128 = 10000000 in binary.
            bit = 128;
            return read();
        } else {
            // If `bit` is on in currentByte, return 1, 
            // if it is off, return 0.
            int r = ((currentByte & bit) > 0) ? 1 : 0;
            // Halving `bit` get the index ready to 
            // check for the next bit in `currentByte`.
            bit = bit/2;
            return r;
        }
    }

    /**
     * Read the next `n` bits from input, pad those into
     * a single integer value. Return -1 at end of stream.
     */
    public int read(int n) throws IOException {
        if (n <= 0 || n > 32)
            throw new IOException("invalid bit-count in read");
        int r = 0;
        for (int x = n-1; x >= 0; --x) {
            int b = read();
            if (currentByte == -1) return -1;
            r |= (b << x);
        }
        return r;
    }

    /**
     * Align input to the next byte in `bytesInput`.
     */
    public void align() {
        bit = 0;
    }
}

package bits;

import java.io.OutputStream;
import java.io.IOException;

/**
 * Write bits to an OutputStream.
 */
public class BitsWriter {

    private OutputStream bytesOutput;
    private int currentByte;
    private int bit;

    public BitsWriter(OutputStream output) {
        bytesOutput = output;
        currentByte = 0;
        bit = 7;
    }

    /**
     * If atleast one bit was padded to `currentByte`,
     * write it to the underlying OutputStream.
     */
    public void flush() throws IOException {
        if (bit < 7) bytesOutput.write(currentByte);
        currentByte = 0;
        bit = 7;
    }

    /**
     * If `b` is not zero, turn on the bit in `currentByte` at
     * position `bit`. If one byte is full, flush that to the
     * OutputStream.
     */
    public void write(int b) throws IOException {
        if (bit == -1) {
            flush();
            write(b);
        } else {
            if (b != 0) currentByte |= (1 << bit);
            bit -= 1;
        }
    }

    /**
     * Extract `n` bits from the integer `b` and write that to
     * the OutputStream.
     */
    public void write(int b, int n) throws IOException {
        if (n <= 0 || n > 32)
            throw new IOException("invalid bit-count in write");
        for (int x = n-1; x >= 0; --x)
            write(b & (1 << x));
    }
}

Invoking these classes from Clojure is quite easy. We just need to update the lein project.clj file with the path to the Java package. In the example project, I put the `bits` package in the `src/java` folder. This path should be specified in the :java-source-paths property of the project file as shown below:

(defproject bit-stream "0.1.0"
  :description "A Clojure library for bits IO."
  :license {:name "Eclipse Public License"
            :url "http://www.eclipse.org/legal/epl-v10.html"}
  :java-source-paths ["src/java"]
  :dependencies [[org.clojure/clojure "1.8.0"]])

You may want to define some simple wrappers to make the bit-stream functions easier to use from Clojure:

(ns bit-stream.core
  (import [bits BitsReader BitsWriter]))

(defn make-reader
  [input-stream]
  (BitsReader. input-stream))

(defn read-bit
  [reader]
  (not (zero? (.read reader))))

(defn read-bits
  [reader n]
  (.read reader n))

(defn make-writer
  [output-stream]
  (BitsWriter. output-stream))

(defn flush-bits
  [writer]
  (.flush writer))

(defn write-bit
  [writer b]
  (.write writer (if b 1 0)))

(defn write-bits
  [writer b n]
  (.write writer b n))

Now we’re all set to move on to the interesting part. Let’s design an abstraction that will allow us to program bit-streams from a much higher-level. This new abstraction should enable us to specify bit-encoded data as first-class objects in Clojure. We will also write new bit-stream functions that can read and write data based on these specifications. We won’t be calling I/O functions directly on bit-streams any more.

To understand our goal better, let us think about a simple object that can be bit-encoded. The example I have chosen is that of 16 bit colors, where the red and blue components are encoded using 5 bits and the green component is encoded in 6 bits. We can specify the structure of 16 bit colors as a vector of field names and their bit-lengths:

(def _16bit-color-spec [:red 5 :green 6 :blue 5])

Now we want to be able to encode three integer values into a single 16 bit color and decode a single 16 bit color value into red, green and blue components. The higher-level bit-stream functions that we are going to implement should enable us to do this:

(def encoded-color (bit-encode [:red 2 :green 52 :blue 16])
                     _16bit-color-spec))

(bit-decode encoded-color _16bit-color-spec)
;;=> [:red 2 :green 52 :blue 16]

The definitions of bit-encode and bit-decode are shown below:

(defn bit-encode
  "Return a byte-array with `data` bit-encoded into it.
  `data` is a vector in the format:
     [field-name1 value1, field-name2 value2, ...]
  `spec` is a vector in the format:
     [field-name1 bit-field-size1, field-name2 bit-field-size2, ...]
   Values in `data` will be encoded with corresponding
   bit-field sizes in `spec`.
  `field-names` in both `data` and `spec` are ignored
   during the encoding process."
  [data spec]
  (let [ba (java.io.ByteArrayOutputStream.)
        encoder (make-writer ba)]
    (loop [data-values (filter integer? data)
           bit-field-sizes (filter integer? spec)]
      (if (and (seq data-values) (seq bit-field-sizes))
        (do (write-bits encoder (first data-values)
              (first bit-field-sizes))
            (recur (rest data-values) (rest bit-field-sizes)))
        (do (when (seq data-values)
              (throw (Exception. "more data values")))
            (when (seq bit-field-sizes)
              (throw (Exception. "more bit field lengths"))))))
    (flush-bits encoder)
    (.toByteArray ba)))

(defn bit-decode
  "Decode a byte-array returned by `bit-encode`.
  `spec` is a vector in the format:
    [field-name1 bit-field-size1, field-name2 bit-field-size2, ...]
   A new vector is returned with the same field-names
   as `spec` and the associated values
   being integers initialized by reading the appropriate number
   of bits from the encoded stream."
  [encoded-data spec]
  (let [bi (java.io.ByteArrayInputStream. encoded-data)
        decoder (make-reader bi)]
    (loop [field-names (filter keyword? spec)
           bit-field-sizes (filter integer? spec)
           result []]
      (if (seq field-names)
        (recur (rest field-names) (rest bit-field-sizes)
          (concat result [(first field-names)
                          (read-bits decoder
                            (first bit-field-sizes))]))
        (vec result)))))

We can now easily decode and encode complicated structures like the TCP header. We just have to translate the layout of the data into a specification vector and apply bit-encode and bit-decode to it.

(def tcp-header-spec
  [:source-port 16
   :destination-port 16
   :sequence 32
   :acknowledgement-number 32
   :data-offset 4
   :reserved 6
   :urg-flag 1
   :ack-flag 1
   :push-flag 1
   :reset-flag 1
   :syn-flag 1
   :fin-flag 1
   :receive-window-size 16
   :checksum 16
   :urgent-pointer 16])

(defn encode-tcp-header
  [header]
  (bit-encode header tcp-header-spec))

(defn decode-tcp-header
  [encoded-header]
  (bit-decode encoded-header tcp-header-spec))

;; Example usage:
(let [sample-header [:source-port 38
                     :destination-port 47892
                     :sequence 1656212531
                     :acknowledgement-number 1481973485
                     :data-offset 5
                     :reserved 0
                     :urg-flag 0
                     :ack-flag 0
                     :push-flag 0
                     :reset-flag 0
                     :syn-flag 0
                     :fin-flag 0
                     :receive-window-size 17664
                     :checksum 888
                     :urgent-pointer 63404]]

(= (decode-tcp-header (encode-tcp-header sample-header)
   sample-header))
;;=> true

References

The basic bit-stream library is mostly based on a similar abstraction from the book More OCaml : Algorithms, Methods & Diversions. Pattern based encoding and decoding of bit-streams was inspired by Erlang’s bit syntax. Chapter 7 of the book Programming Erlang cover this topic well.

Download

Source code for the bit-stream library.

The truth about nothing

Conditionals like the if-else construct are something that programmers take for granted these days. In Lisp, conditionals are expressions, i.e, they evaluate to produce a value. John McCarthy invented the conditional if expression in the context of Fortran. In his original Lisp, it appeared as the more general cond form.

Conditional expressions has the mandate on distinguishing those objects that should be treated as the logical true and false values. If you have programmed in a language like Java, you would expect only constants like true and false to be recognized as logical values. This need not be the case in Lisp. A Lisp may use more than one type of object to represent true and false. This can be a source of confusion for beginners and sometimes even for experienced Lispers.

This post details on how three popular flavors of Lisp – Common Lisp, Scheme and Clojure – represent logical values. We will try to understand why these design decisions were made. We will also see how to write idiomatic conditional expressions in each of these Lisps.

Common Lisp

In Common Lisp, the symbol nil is used to represent both the empty list and boolean false. An empty list may, of course, also be written as () and evaluates to the same object as nil. All values other than nil (i.e the empty list) are considered true. Common Lisp conventionally uses the constant t to stand for true, when no other value makes more sense. The following REPL session shows all the various forms logical values can assume in Common Lisp:

clisp> (if nil 'yes 'no)
=> no

; The empty list and nil are represented by the same object.
clisp> (if '() 'yes 'no)
=> no

; The symbol literal nil also evaluates to logical false.
clisp> (if 'nil 'yes 'no)
=> no

; All values other than nil evaluates to logical truth,
; though the constant `t` is its canonical representation.
clisp> (if 100 'yes 'no)
=> yes
clisp> (if t 'yes 'no)
=> yes

Note: In code examples, clisp>, scheme> and clojure> stands for the input prompt of Common Lisp, Scheme and Clojure REPLs respectively. The value of an expression is preceded by the => symbol.

The Common Lisp language specification requires nil to be the default value returned by conditional expressions.

clisp> (if (< 5 4) 'ok)
=> nil
clisp> (when (< 5 4) 'ok)
=> nil

A predicate (i.e a function that return a true or false answer) may return the empty list or nil for a negative answer. But the generally accepted practice in Common Lisp is to return nil to signal false. Although any object other than nil is considered true, t is generally used when there is no special reason to prefer one such object over another. To better understand the Common Lisp conventions on predicates, let’s write one. The following function will return true only if the first element of the argument list is also a list.

clisp> (defun flistp (alist)
         (if (null alist)
           '()
           (listp (car alist))))

clisp> (if (flistp '()) 'yes 'no)
=> no
clisp> (if (flistp '(1 2 3)) 'yes 'no)
=> no
clisp> (if (flistp '((1 2) 3)) 'yes 'no)
=> yes

;; The predicate 'listp' returns true for
;; the empty list, despite it being the logical
;; false value!
clisp> (if (flistp '(() 1 2 3)) 'yes 'no)
=> yes

Note: It’s the naming convention in Common Lisp to end predicate names with the character `p`. It may appear strange that some of the built-in functions like `null` and `atom` do not follow this convention. These functions were part of earlier Lisp dialects and the designers of Common Lisp wanted to maintain some level of basic conformance with the Lisps of that time.

The first version of flistp works as expected but a stylistic improvement is possible. In the following rewrite, we omit an explicit negative answer, as nil is the default value of all conditional expressions.

clisp> (defun flistp (alist)
         (when (not (null alist))
           (listp (car alist))))

clisp> (if (flistp '()) 'yes 'no)
=> no
clisp> (if (flistp '(1 2 3)) 'yes 'no)
=> no
clisp> (if (flistp '((1 2) 3)) 'yes 'no)
=> yes
clisp> (if (flistp '(() 1 2 3)) 'yes 'no)
=> yes

Now you might be wondering why the designers of Common Lisp have overloaded nil  with three different meanings – the empty list, the false value and the symbol nil. The reason lies deep in the long history of Lisp. Almost from the very beginning, Lisp used the symbol nil as the special object that marked the end of a list. The same value was used to check for false values returned by predicates – an “unfortunate and lighthearted decision” according to John McCarthy. As Common Lisp aimed to unify and standardize the popular Lisps that existed at the beginning of 1980s, it did not deviate too much from the fundamental way logical values were represented and interpreted. As Lisp is mostly about list processing, using the same object to represent false and the empty list led not just to optimal resource usage but also to some economy in code. As an example of this, consider the following function that returns the first sublist from its list argument:

clisp> (defun fsublist (alist)
         (cond
           ((null alist) nil)
           ((listp (car alist)) (car alist))
           (t (fsublist (cdr alist)))))

clisp> (fsublist '(1 2 (3 4) (5)))
=> (3 4)
clisp> (fsublist '(1 2 3 4 5))
=> nil

As the empty list is the same as logical false, fsublist can be used in a predicate position without performing special type conversion on its return value.

clisp> (let ((s (fsublist '(1 2 (3 4) (5)))))
         (or s 'no-sublists))
=> (3 4)
clisp> (let ((s (fsublist '(1 2 3 4 5))))
         (or s 'no-sublists))
=> no-sublists

Early Lisp implementers also found that assigning the false value to the empty list can bring in some efficiency as well. As most platforms provided a “jump if zero” instruction, conditional expressions can be optimally implemented by using address zero (0) to represent the false value (i.e, the empty list!).

While Common Lisp sticked to tradition, there was a nascent Lisp community more interested in elegance and clarity. Scheme programmers considered treating nil, false and the empty list as the same object as nonsense.

Scheme

The designers of Scheme decided to use specific representations for boolean values. Scheme encode true and false with the symbols #t and #f respectively. Note that the Scheme conditional expressions  (if, cond, and, or) treat all values other than #f as true. That means, the empty list ‘() is also a truth value. Scheme distinguishes both the logical false (#f) and the symbol nil from the empty list. As per recent specifications, a Scheme implementation is not required to provide a name to denote the nil or null value.

scheme> (if '() 'yes 'no)
=> yes
scheme> (if #f 'yes 'no)
=> no
scheme> (> 5 4)
=> #t
scheme> (< 5 4)
=> #f
scheme> (and (> 5 4) 2)
=> 2
scheme> (and (> 5 4) (= 2 1))
=> #f

Unlike Common Lisp, the default value of conditional expressions is left unspecified by the Scheme standard.

scheme> (if (< 5 4) 'ok)
=> <an-implementation-dependent-value>
scheme> (if (> 5 4) 'ok)
=> ok

If we are to re-implement flistp in Scheme, we have to be explicit about the return values. Both implementations shown below are correct:

scheme> (define (flist? alist)
           (if (null? alist)
	        #f
	        (list? (car alist))))

scheme> (define (flist? alist)
          (and (not (null? alist))
               (list? (car alist))))

scheme> (if (flist? '()) 'yes 'no)
=> no
scheme> (if (flist? '(1 2 3)) 'yes 'no)
=> no
scheme> (if (flist? '((1 2) 3)) 'yes 'no)
=> yes

Note: The Scheme naming convention is to end predicate names with a question mark (?). This convention is also followed in Clojure.

The following implementation of flist? is not portable because a Scheme implementation is free to use any value as the default of conditional expressions. It need not be #f.

;; This implementation is not portable.
(define (non-portable-flist? alist)
    (if (not (null? alist))
      (list? (car alist))))

When called with an empty list, this is how non-portable-flist?  behaves in Chez Scheme:

scheme> (if (non-portable-flist? '()) 'yes 'no)
=> yes

Scheme programs should be explicit about the values of all logical expressions. This is demonstrated again in the following re-implementation of the fsublist procedure:

scheme> (define (fsublist alist)
          (cond
           ((null? alist) #f)
           ((list? (car alist)) (car alist))
           (else (fsublist (cdr alist)))))

scheme> (fsublist '(1 2 3 4 5))
=> #f
scheme> (fsublist '(1 2 (3 4) 5))
=> (3 4)
scheme> (let ((s (fsublist '(1 2 3 4 5))))
          (or s 'no-sublists))
=> no-sublists
scheme> (let ((s (fsublist '(1 2 (3 4) (5)))))
          (or s 'no-sublists))
=> (3 4)

Clojure

Clojure treats both nil and false as logical false values. All other values, including the empty sequence, are treated as logical truths. Though false maps directly to Java’s Boolean/FALSE static object, an object constructed by a call to (Boolean. false) is considered to be logical true! So the key point to keep in mind is – all values other than the constants nil and false are true. Conditional expressions return nil as their default value. Clojure’s nil is the same object as Java’s null and the main reason for its existence is interoperability with the JVM.

Without further ado, let us re-implement the flist? function in Clojure. As Clojure has the more general concept of a sequence, which need not always be a list, we will call this function fseq?.

To help with the implementation of fseq? we need a function to check if an object is in fact a sequence, or can be converted to one. An object is converted to a sequence with a call to the seq function. But this will raise an exception if the conversion cannot be performed. We want to translate this exception into the boolean false value. This is the job of the helper function, which we call safe-seq. The code for both safe-seq and fseq? follows:

clojure> (defn safe-seq [obj]
           (try
            (seq obj)
              (catch Exception ex
                nil)))

clojure> (defn fseq? [aseq]
           (and (safe-seq aseq)
                (safe-seq (first aseq))))

clojure> (if (fseq? []) 'yes 'no)
=> no
clojure> (if (fseq? [1 2 3]) 'yes 'no)
=> no
clojure> (if (fseq? [[1 2] 3]) 'yes 'no)
=> yes

Safe-seq also comes-in handy for re-implementing fsublist. (I renamed this function as fsubseq in Clojure).

clojure> (defn fsubseq [aseq]
           (when (safe-seq aseq)
             (if (safe-seq (first aseq))
               (first aseq)
               (fsubseq (rest aseq)))))

clojure> (fsubseq [1 2 3 4 5])
=> nil
clojure> (fsubseq [1 2 [3 4] 5])
=> [3 4]
clojure> (if-let [s (fsubseq [1 2 3 4 5])] s 'no-subseqs)
=> no-subseqs
clojure> (if-let [s (fsubseq [1 2 [3 4] [5]])] s 'no-subseqs)
=> [3 4]

Conclusion

This post explained how logical values are represented in various Lisps and some of the reasons behind those design decisions. Which Lisp got it right is debatable. While Common Lisp favored efficiency and tradition, Scheme valued clarity and elegance. (If I were to design a language, I would choose a path between Scheme and Clojure.)

I hope, after reading this post, you must be in a better position to appreciate the following quote from Abelson and Sussman:

It’s remarkable how much energy in the standardization of Lisp dialects has been dissipated in arguments that are literally over nothing: Should nil be an ordinary name? Should the value of nil be a symbol? Should it be a list? Should it be a pair?

So let the arguments continue. The hapless novice can be left alone, still looking confused!

References

  1. Common Lisp HyperSpec
  2. R7RS
  3. The Evolution of Lisp (pdf), by Richard P. Gabriel
  4. Clojure Docs

Syntactic abstractions

The previous post explained higher-order functions and the abstractions they enable us to build. The programming techniques we discussed there can be applied in any functional language. This post describes a kind of abstraction that can be built only in Lisp. I am referring to Lisp’s ability to abstract over its own syntax.

If you have programmed in a language like C, Java or Python, you realize how “sacred” the idea of syntax is – those rigid, inviolable rules established by high-ranking language lawyers. But once in a while we do feel that if the language had such and such an operator or control construct, our life would’ve been easier. For instance, consider a Java programmer trying to iterate over a table in a relational database and  do something with the data in each row:

String sql = "SELECT name, salary FROM employee WHERE salary > 1000";
Statement s = new Statement(sql);
ResultSet r = dbconnection.executeQuery(s);
while (r.next()) {
   String employeeName = r.getString("name");
   double employeeSalary =  r.getDouble("salary");
   doSomething(employeeName, employeeSalary);
}

After repeatedly typing in the same pattern of code many times over, our Java programmer starts to wish for a built-in language construct specially designed for iterating over database rows. This is the language extension he has in mind:

String sql = "SELECT name, salary FROM employee WHERE salary > 1000";
for_each_row (dbconn, sql, String employeeName = name,
              double employeeSalary = salary) {
  doSomething(employeeName, employeeSalary);
}

The for_each_row construct will enable him to program the database from a higher level, in a declarative style. He just specifies what data he wants to fetch, establish some local variable bindings for them and do his work with those values. The compiler recognizes for_each_row as a special construct and emits all the lower-level code required to access and bind the variables.

We all know this is just wishful thinking! Application programmers are not allowed to change the language just like that. They are expected to solve their problems while staying within the boundaries established by the language designers. Well, not so if you are programming in Lisp!

Lisp elevates the status of application developers to that of language designers. If you think that adding a new syntactic extension to the language will make your program cleaner, shorter and faster, you just go ahead and add it.

Expressions and the rules of evaluation

Before we delve into extending Lisp with new syntax, we should get a high-level overview of how Lisp programs are encoded and interpreted. Lisp programs consist of expressions of two types – atomic and compound. An atomic expression (or atoms) consists of a value that cannot be split any further. An integer literal like 23 is an example of an atom. The rules for evaluating an atom is listed below:

  1. If an atom is a literal, like the number 23, just return the value as-is.
  2. If the atom is a symbol representing the name of a variable, fetch and return the value associated with that variable. (The variable name will be mapped to a value in an in-memory store, usually known as the environment).

Note: Atomic values are also known as scalars in other languages.

Compound expressions are formed by delimiting a list of expressions within parenthesis. They are also known as combinations and they denote function application. The following are all examples of combinations:

(+ 2 3)
(* 10 (+ 2 3))

These are the rules followed by a Lisp interpreter for evaluating a combination:

1. Evaluate each expression in the combination
2. Apply the function (i.e, the value of the left-most expression, known as the operator) to the other subexpressions (arguments or operands).

Lisp also allow expressions to be quoted. This is done by prefixing the expression with the quote character (‘) or with a call to the quote operator. Quoted expressions are not evaluated by the interpreter, instead their literal representation is returned.

The following session at the Clojure REPL demonstrates all the evaluation rules we discussed so far:

user> 23 ; an atom
23

;; a combination with + as operator and 2 and 3 as operands.
user> (+ 2 3)
5

;; another combination with * as operator and 10 and
;; the value of the combination `(+ 2 3)` as operands.
user> (* 10 (+ 2 3))
50

user> (def x 100)
user> x ; an atom that names a variable.
100
user> 'x ; the same atom, quoted
x
user> '(+ 2 3) ; quoting turns-off evaluation.
(+ 2 3)
user> (quote (+ 2 3)) ; same as '(+ 2 3)
(+ 2 3)
user> (quote x) ; same as 'x
x

As we noted earlier, the call to quote behaves differently from a normal function call. It appears that quote gets the whole expression passed to it, unevaluated. This is because quote is an operator specially recognized by the interpreter/evaluator. Most Lisps have a small set of such operators with unique evaluation rules. These operators are known as special forms.

The evaluation rules for atoms, function calls and special forms sums up the behavior of a Lisp interpreter. It is this amazing simplicity in representation and evaluation that makes Lisp a language extensible to the core.

Note: Though we explained the evaluations rules in the context of an interpreter, they apply equally well for a compiler.

Macros

Now we have enough background to understand the syntax-level extension facility offered by Lisp. Let us begin with a very simple but realistic syntactic extension. Imagine you want to define an operator that evaluates its body only when some condition is false. In Clojure you can use the built-in if-not or when-not operators for this, but you feel that the code will be more readable if you can write something like – (unless this-is-true do-this). It is possible to define unless as a higher-order function as shown by the following program:

(defn unless
  [condition consequent]
  (when-not condition (consequent)))

;; Example usage:
(unless (< 2 1) #(println "ok"))
;;-> ok
(unless (< 1 2) #(println "ok"))
;;=> nil
(unless (< 2 1) (fn [] (println "ok") 100))
;;-> ok
;;=> 100

Note: In the code samples, ;;-> denotes the result of a side-effect, like printing to the standard output and ;;=> marks the value of evaluating an expression.

The problem with this definition is that the users of unless have to wrap the consequent expression in a function literal. Otherwise it will be evaluated when unless is called, no matter what the condition is. This is because all the arguments are evaluated before the function call itself. In other words, the evaluation rules for function call is different from special forms. An argument passed to special forms are evaluated only when its value is really needed by the operator. The good news is that we can add our own special forms to extend the Lisp interpreter or compiler! These user-defined special forms are known as macros. A macro is introduced to the Clojure compiler with a defmacro definition. Let us rewrite unless as a macro:

(defmacro unless
  [condition consequent]
  `(when-not ~condition ~consequent))

(unless (< 2 1) (println "ok"))
;;-> ok
(unless (< 1 2) (println "ok"))
;;=> nil

The unless macro behaves more like a built-in operator, we can pass a raw expressions in the  consequent part. We are also able to avoid the runtime cost of creating and calling a function. Let us spend some more time understanding the special treatment given to a macro by the compiler.

A macro is essentially a function that is called by the compiler. Consider the expression (unless (< 2 1) (println “ok”)). When the compiler detects that this is a call to a macro, it asks the Lisp interpreter to kick-in and evaluate the body of unless with the arguments (< 2 1) and (println “ok”), just like it would evaluate a function call. Note that the value returned by unless is a quasiquoted list (a list prefixed by the backtick character (`)). A quasiquoted expression is similar to a quoted expression, in that the evaluator is turned-off and the expression is returned literally. But a quasiquoted expression can contain “escaped” or unquoted sub-expressions. The evaluator will evaluate these unquoted sub-expressions and replace them with their values. (Clojure uses the tilde (~) character for unquoting expressions).

It will be easier to understand the difference between quote and quasiquote by playing around a bit in the REPL:

user> (def a 10)
user> (list a a)
(10 10)
;; the quote turns-off the evaluation of the
;; elements in the list.
user> '(a a)
(a a) 

;; A quasiquote without any escaped sub-expressions
;; has the same effect as a quote.
user> `(a a)
(a a)
user> `(~a a)
(10 a)
user> `(~a ~a)
(10 10)

So in our example, the evaluator replaces ~condition and ~consequent with the lists (< 2 1) and (println “ok”) respectively. This results in the final expression (when-not (< 2 1) (println “ok”)). The compiler then proceed to replace the call to unless with this expression. This is as good as typing the when-not expression directly into the program. This phase of compilation when the macro is “called” to return some auto-generated code is known as “macro expansion”. Macro expansion happens only once in the life-time of a macro call. The expanded code can be executed multiple times when the program runs, without any additional overhead.

Exercise 1: In Clojure, the built-in function macroexpand can be called to find out the expansion of a macro. Use this function to return the expansion of the call (unless (< 2 1) (println “ok”)). Find out why the resulting expansion is different from the template code we provided in the body of unless. Also figure out the use of macroexpand-1 and macroexpand-all. These functions will come in handy for debugging complex macros.

Our current implementation of unless has a limitation – it can accept only a single expression in the consequent part. Let us fix this by taking advantage of a macro’s ability to accept an arbitrary number of arguments. These arguments are all packaged into a list and passed to the macro. This list has to be introduced as a parameter by preceding it with an ampersand (&). Before changing unless, let us look at a simpler example. The following program defines a macro that can merge an arbitrary number of values into a single vector.

(defmacro into-vec
  [a & args]
  `[~a '~args])

(into-vec 1 2 3 4)
;;=> [1 (2 3 4)]

This first version of the into-vec macro does not do exactly what we want. We want the argument list to be “spliced” into the resulting expression. This can be achieved by using the unquote-splice (~@) operator:

(defmacro into-vec
  [a & args]
  `[~a ~@args])

(into-vec 1 2 3 4)
;;=> [1 2 3 4]

Now we know how to make unless accept more than one expression in the consequent part. Just define it to take an arbitrary number of arguments after condition and unquote-splice those into the body of when-not:

(defmacro unless
  [condition & consequent]
  `(when-not ~condition ~@consequent))

;; Example usage:
(unless (< 2 1)
(println "hey")
(println "there!")
(+ 2 1))
;;-> hey
;;-> there!
;;=> 3

When to use macros

We can use both higher-order functions and macros to define custom control structures, but macros have some advantages here. First of all, macros can save a few keystrokes, because they can get rid of explicit function literals. Secondly, there may be some performance advantage, as macros avoid a function call at runtime by directly injecting the code into the call-site.

Some programs may want a piece of code, like a frequently performed expensive math calculation, to be highly optimized. What is the best way to optimize a computation? By not doing it! Well, to be fair, by not doing it at runtime. If we can pre-compute the result at compile-time, why not do that and insert the final result into the program? Macros can help with compile-time computations. In the following example, we define such a macro. It does some checks to see if it has all the information needed to perform the computation at compile-time itself. If that is possible, the computation is executed and the result is returned to the compiler. If not enough information is available to do the computation at compile-time, the macro will return the code that can do the computation later at runtime:

(defmacro fast-hypot
  [x y]
  (if (and (number? x) (number? y))
    (Math/hypot x y)
    `(Math/hypot ~x ~y)))

(macroexpand-1 '(fast-hypot 123.22 145.67))
;;=> 190.7954855335943
(macroexpand-1 '(fast-hypot a 145.67))
;;=> (java.lang.Math/hypot a 145.67)

Functions are the natural building blocks of Lisp, their implementation is highly optimized and they have first-class status in the language. Too many macro calls tend to bloat the final program generated by the compiler by having the same code copied to multiple locations. If a syntactic extension to the language makes it cleaner, faster and easier to maintain, go for macros. If you have to define a custom language to solve a particular problem, you may have to depend a lot on macros. In all other situations, stick to functions. So the guiding principal is – use functions whenever you can and use macros when you have to.

Macro caveats

Macros are vulnerable to certain types of bugs that do not usually occur with normal functions. This section throws light on some of those issues.

Variable capture

Variable capture occurs when a symbol in the expanded macro body ends up referring to a variable from another context. If the variable capture is unintentional it can lead to subtle bugs. In the next program, we define a macro that will capture a variable from the context it is called.

(def x 100)
(defmacro prnx
 []
 `(println ~'x))

(prnx)
;;-> 100
(let [x 200] (prnx))
;;-> 200

The macro prnx has a bug if the macro writer intended it to always print the value of the global variable x. This simple macro highlights one way a capture can occur – by means of free variables. A variable is free in an expression if that expression does not create a binding for it. The prnx macro do not bind the variable x in its body nor in its parameter list. This opens up x to obtain a value from the context in which prnx is called and may lead the macro to behave in unintended ways. If you want to avoid a variable from being captured, make sure it does not occur free in the macro body.

Let us try to write a macro that do not have any free variables and thus avoid variable capture. For this I decided to implement a slightly more complicated macro – a control structure that imitates the behavior of the for loop found in most imperative languages. Here is the first version of our for loop:

(defmacro for-loop
  [var-name start-from loop-until & body]
  `(let [~'end ~loop-until]
     (loop [~var-name ~start-from]
       (when (< ~var-name ~'end)
        (do ~@body
            (recur (inc ~var-name)))))))

The for-loop construct seems to work under all normal circumstances:

(for-loop x 0 3 (println x))
;;-> 0
     1
     2

But when we use the symbol end for the loop variable, a subtle bug raises its ugly head to the surface:

(for-loop end 0 3 (println end))

A call to macroexpand-1 reveals why the macro is not working as expected:

(macroexpand-1 '(for-loop end 0 3 (println x)))
;;=> (clojure.core/let [end 3]
       (clojure.core/loop [end 0]
         (clojure.core/when
           (clojure.core/< end end)
             (do (println x)
                 (recur (clojure.core/inc end))))))

The problem is the hard-coded symbol end we used to name a local variable. The variable name passed to the macro by the user is shadowing this variable. This means that just avoiding free variables is not enough to get rid of variable capture. We also need to ensure that the local variable names bound in the macro body are unique across the system. The function gensym can help us here. It returns a new symbol that is guaranteed to be unique. Let us rewrite the for-loop macro using gensym:

(defmacro for-loop
  [var-name start-from loop-until & body]
  (let [end (gensym)]
    `(let [~end ~loop-until]
       (loop [~var-name ~start-from]
         (when (< ~var-name ~end)
(do ~@body
(recur (inc ~var-name))))))))

(for-loop x 0 3 (println x))
;;-> 0
     1
     2
(for-loop end 0 3 (println end))
;;-> 0
     1
     2

Note that the first let expression is not part of the code template returned by the macro. It is not quasiquoted. So it will be evaluated during compile-time, binding the variable end to a unique symbol value. This symbol is used in the code template to ensure that no name clashes occur. Now, having to write this extra code for generating local symbol names can be tedious if the macro has lots of them. So Clojure offers us a shortcut. You can suffix a variable name with the hash (#) character and the Clojure compiler will consistently replace that name with a unique symbol. This replacing will happen as long as the name occurs within a quasiquoted expression. This facility is demonstrated below:

user> (let [a# 1] a#)
1
user> '(let [a# 1] a#)
(let [a# 1] a#)
user> `(let [a# 1] a#)
(clojure.core/let [a__2875__auto__ 1] a__2875__auto__)

Now we are ready to write the final, correct version of our for-loop macro:

(defmacro for-loop
  [var-name start-from loop-until & body]
  `(let [end# ~loop-until]
     (loop [~var-name ~start-from]
       (when (< ~var-name end#)
         (do ~@body
             (recur (inc ~var-name)))))))

Tidbit: Macros in Scheme do not have the variable capture problem because the macro system is “hygienic”. The macro expander takes care of properly renaming variables locally bound by the macro body. If the macro refers to any free variable, the expander makes sure that the reference seen by the macro will always be the one when the transformer was specified.

Now you may wonder if there is a way to fix the broken prnx macro. We can take advantage of the Clojure namespace system to force prnx to refer to the global variable we intended. We just qualify the free variable with the namespace that it belongs to.

user> (def x 100)
#'user/x
user> (defmacro prnx
        []
        `(println ~user/x))

user> (prnx)
100
user> (let [x 200] (prnx))
100

Multiple evaluations

While reading the definition of the for-loop macro, some of you might have thought why I have introduced the extra variable end#. Why not directly check the value of the loop-until argument to determine when to exit the loop? Let us rewrite the macro without the extra local variable and examine the resulting behavior.

(defmacro for-loop
  [var-name start-from loop-until & body]
  `(loop [~var-name ~start-from]
     (when (< ~var-name ~loop-until)
       (do ~@body
            (recur (inc ~var-name))))))

The problem with this definition is that the expression passed to loop-until will be evaluated each time the loop is executed. This is evident from the following REPL session:

user> (for-loop x 0 (do (println "expensive computation....") 3)
         (println x))
expensive computation....
0
expensive computation....
1
expensive computation....
2
expensive computation....

If there is no other reason, you should unquote and evaluate the arguments only once, bind the results to local variables and refer to those variables in the rest of the macro body. This was what the earlier definition of for-loop was doing and it did suffer from this “multiple-evaluation” problem.

The order in which macro arguments are evaluated can also become an issue, especially if the argument expressions perform side-effects. You can avoid this problem by sticking to pure functional programming as much as possible. The macro expansions should also be purely functional. Expander code should depend on nothing but the expressions passed to it as arguments and should not perform any side-effects other than returning a value.

Conclusion

It is the unique nature by which Lisp programs are encoded and interpreted that makes it an extensible language. This amazing extensibility has enabled Lisp to be a great survivor. When new programming paradigms emerged, older languages died out. But Lisp simply adapted to the changing environment and moved on. It is this adaptability and flexibility that makes learning Lisp not only fun but also a safe investment!

Exercise 2: At the beginning of this post we talked about an extension to the Java language for making relational database access easier. Design and implement a similar extension as a Clojure macro.

Suggested reading

1. On Lisp – everything you need to know about macros.
2. The Art of Meta-Object Protocol – explains in great detail an object-oriented extension developed for Common Lisp, providing profound insights on the possibilities of syntactic abstractions.
3. The Forth programming language also has an extensible compiler. Stating Forth is a great tutorial on the language (or on any language!).

Download

A solution to Exercise 2.

Functional abstractions

Lisp is the earliest programming language to treat functions as first class entities. Functions in Lisp have the same status as other types of data like strings and numbers – they have a literal representation, they can be passed around as data, they can be embedded in other data structures and new functions can be created dynamically as the program executes. Functions are also the primary means of abstraction in Lisp.

This post is about the versatility and power of first class functions. We start from the very basics. We will learn how to generate new functions as the program runs. We will use functions to abstract control flow – something that can be done concisely and efficiently only by first-class functions. We will also use functions to build abstractions in the more traditional sense – data structures that can hide the details of their implementation. We give an accurate definition of “higher-order programming” and explain how it eases the development of generic software components.

Note: The sample code is in Clojure but can be easily ported to any modern Lisp. Some of the functions that we write may have efficient native implementations in your favorite Lisp – please consult the language manual.

Basics

Most languages provide a built-in facility, in the form of special syntax, to define functions. For example, this is how you would define a function in JavaScript:

function add2(n) {
  return n + 2
}

Instead of special syntax, Lisps have operators called special forms that are used for doing compile-time stuff like introducing a variable name into the program. Most Lisps have a special form for defining and naming functions. In Clojure it is known as defn (for define function).

Here is the add2 function rewritten in Clojure:

(defn add2
  [n]
  (+ n 2))

Now we can call add2 from another function or directly from the REPL:

(add2 10)
;;=> 12

Note: In the code examples ;;=> is used to identify results of evaluating an expression and ;;-> to identify values produced by a side-effect, like printing a value to the standard output.

We can “see” the internal representation of the add2 function by typing its name at the REPL. This is possible because a function is just another object recognized by the language:

add2
;;=> #<user$add2 user$add2@515d06af>

Like literal strings and numbers, we can write literal functions. A function literal in Lisp is known as a lambda expression. Clojure have the special form fn for introducing function literals. Fn takes a vector of parameters and zero or more expressions which become the body of the function. The expression shown below is equivalent to the add2 function we defined earlier:

(fn [n] (+ n 2))

A function literal can be invoked by placing it in the function call position:

((fn [n] (+ n 2)) 10)
;;=> 12

Function literals are so prevalent in Lisp programs that Clojure has a shorter notation for them. This is the #() form which allows for the argument list to be omitted. The parameters are referred to by their position prefixed by %, i.e, the first parameter is referred in the body as %1, the second parameter is referred as %2 and so on. The % symbol without the parameter position will refer to the only parameter of a single argument function.

Let us rewrite the previous example using the shorter notation:

(#(+ % 2) 10)
;;=> 12

Now that we can write function literals, we can do anything with them we would normally do with other types of data. Functions can be passed around as arguments, they can become return values or they can be packaged into data structures. At the bare minimum, we can bind the function object to a variable name:

;; This is the same as our first defn of `add2`.
(def add2 #(+ % 2))

Tidbit: Clojure and Scheme have a single namespace (or binding environment) for all types of variables, i.e if we redefine add2 the reference to the function object will be lost. Common Lisp, on the other hand, treats variables bound to functions specially. They are bound in a dedicated namespace. So we can have a function named add2 and an integer variable named add2 in the same program. A Lisp with a single namespace is known as a Lisp-1. Clojure and Scheme belong to this category. Common Lisp is a Lisp-n as there are many namespaces.

Functions as arguments

Once we have functions as first class objects, we can pass them as arguments to other functions. Many built-in Lisp functions take functional arguments, two of the most frequently used are apply and map.

The first argument of apply must be a function object and the last argument must be a list (or in Clojure, the more general sequence). Apply prefix all but the first argument to this list. It then calls the function, passing it the list of arguments.

(apply + 1 2 [3 4 5])
;;=> 15

In the next program, apply is used to define a function that return the sum of all positive even numbers from a sequence:

(defn sum-pos-even
  [xs]
  (apply + (remove #(or (neg? %) (odd? %)) xs)))

(sum-pos-even [1 2 3 4 5])
;;=> 6

(sum-pos-even [1 -2 3 4 5])
;;=> 4

Programmers frequently want to do “something” to a list of things and get back a list of results. The function map is designed for this purpose. The “something” that needs to be done to each element is represented as a function. For example, if we want to add 2 to all numbers from 1-5, we call map as shown below:

(map add2 [1 2 3 4 5])
;;=> (3 4 5 6 7)

Map takes an arbitrary number of lists/sequences for processing. The function passed to map should accept as many arguments as there are lists. In the next example, we define the function zip2. It takes two sequences and return the sequence of corresponding pairs.

(defn zip2
  [xs ys]
  (map #(list %1 %2) xs ys))

(zip2 [:a :b :c] '(1 2 3))
;;=> ((:a 1) (:b 2) (:c 3))

Functions as return values

Function calls can result in function values. This naturally leads to functions that act as “generators” of functions. In the following program we define the function make-sort which can be configured with a comparison operation to return a new sorting routine.

(defn make-sort
  [cmp]
  #(sort cmp %))

(def reverse-sort (make-sort >))

(reverse-sort [1 2 3 4 5])
;;=> (5 4 3 2 1)

(reverse-sort [2 3 1 4 2])
;;=> (4 3 2 2 1)

(def sort-by-first (make-sort #(< (first %1) (first %2))))
(sort-by-first [[10 2] [3 5] [8 1]])
;;=> ([3 5] [8 1] [10 2])

Note: If you want to sort any type of data that implements the Java Comparable interface, call make-sort with the compare function:

(def sort-by-first (make-sort #(compare (first %1) (first %2))))

(sort-by-first [["x" 2] ["d" 5] ["a" 1]])
;;=> (["a" 1] ["d" 5] ["x" 2])

Functions as data structures

The function returned by make-sort gets a reference to the cmp argument. This reference is preserved across calls. This is possible because the function packages and holds on to the environment it was defined in. All variable bindings active at the time of calling make-sort will be perpetually available to the new function. In short, its defining environment is “closed over”. Such functions are thus known as closures. Closures can be used to simulate objects with local state. In the next example, we use closures to define a simple point object with two properties – the x and y locations:

(defn make-point
  [x y]
  #(case %
     :xloc x
     :yloc y))

(def p1 (make-point 10 20))
(def p2 (make-point 100 340))
(p1 :xloc)
;;=> 10

(p2 :yloc)
;;=> 340

(defn distance
  [point1 point2]
  ; `sqrt` and `pow` are static methods defined
  ; in the Java Math class.
  (Math/sqrt
   (+ (Math/pow (- (point2 :xloc) (point1 :xloc)) 2)
      (Math/pow (- (point2 :yloc) (point1 :yloc)) 2))))

(distance p1 p2)
;;=> 332.41540277189324

The main purpose of abstraction in programming is to help structure systems in a modular way. Then much of the program can be written independent of the implementation details of data objects being manipulated. A complex number is an example of a data object that can have multiple internal representations. It can be represented in rectangular form (real part and imaginary part) or polar form (magnitude and angle). Object oriented programs will depend on interfaces or abstract base classes to accommodate multiple representations of complex numbers in the same system. It is possible to build an equally powerful abstraction using closures, as demonstrated by the next program.

(ns complex)

(defn make-rectangular
  [real imag]
  (let [magnitude (Math/sqrt
                    (+ (Math/pow real 2)
                       (Math/pow imag 2)))
        angle (Math/atan2 imag real)]
    #(case %
       :real real
       :imag imag
       :magnitude magnitude
       :angle angle)))

(defn make-polar
  [magnitude angle] ; angle in radians
  (let [real (* magnitude (Math/cos angle))
        imag (* magnitude (Math/sin angle))]
    #(case %
       :magnitude magnitude
       :angle angle
       :real real
       :imag imag)))

(defn add
  [c1 c2]
  (make-rectangular
    (+ (c1 :real) (c2 :real))
    (+ (c1 :imag) (c2 :imag))))

(defn sub
  [c1 c2]
  (make-rectangular
    (- (c1 :real) (c2 :real))
    (- (c1 :imag) (c2 :imag))))

(defn mul
  [c1 c2]
  (make-polar
    (* (c1 :magnitude) (c2 :magnitude))
    (+ (c1 :angle) (c2 :angle))))

(defn div
  [c1 c2]
  (make-polar
    (/ (c1 :magnitude) (c2 :magnitude))
    (- (c1 :angle) (c2 :angle))))

(defn repr
  "Return a map representation of a complex number."
  [c]
  {:real (c :real)
   :imag (c :imag)
   :magnitude (c :magnitude)
   :angle (c :angle)})

The operations – add, sub, mul and div – are not concerned with the actual representation of complex numbers. They can work with multiple representations that respond to a basic set of messages.

The following REPL session demonstrates the usage of the complex number type:

user> (clojure.main/load-script "complex.clj")
user> (use '[complex :as c])

user> (def p (c/make-polar 56 0.47))
user> (def r (c/make-rectangular 49.90, 25.42))
user> (c/repr p)
{:real 49.92782413893842, :imag 25.361631981227823, :magnitude 56, :angle 0.47}
user> (c/repr r)
{:real 49.9, :imag 25.42, :magnitude 56.00166426098424, :angle 0.47115425605142663}

user> (c/repr (c/add (make-rectangular 3 2) (make-rectangular 1 4)))
{:real 4, :imag 6, :magnitude 7.211102550927978, :angle 0.982793723247329}

user> (c/repr (c/mul p (make-rectangular 3 2)))
{:real 99.06020845435961, :imag 175.94054422156032, :magnitude 201.9108714259834, :angle 1.0580026035475676}

Higher-order programming

In the previous sections, we learned important programming techniques involving first class functions. We have explored functions that take other functions as arguments, function-building-functions and functions that close-over their local state. These programming techniques are collectively known as higher-order programming. The name comes from the concept of order of a function. A function that take no function arguments is of first-order, a function that takes at-least one first-order function as argument is of second-order and so on. Higher-order programming simply means functions can be of any order.

One interesting implication of higher-order programming is that it enables us to build abstractions to control program flow. This is achieved by exploiting a function’s ability to delay the execution of any program statement. Here is a customized version of the if expression. Our version of if will execute its consequent part only if the test expression returns a positive integer.

(defn ifpos
  [test consequent alternative]
  (if (pos? test) (consequent) (alternative)))

(ifpos (+ 0 1) #(println "hey!") #(println "bye!"))
;;=> hey!

(ifpos (+ 0 -1) #(println "hey!") #(println "bye!"))
;;=> bye!

We can also build custom looping constructs like the one shown below:


(defn times
  [n dothis]
  (when (pos? n)
    (loop [i 0]
      (when (< i n)
       (dothis i)
       (recur (inc i))))))  

(times 3 #(println %))
;;-> 0
     1
     2

As I said in the introduction, the ability to specify efficient control abstractions in a compact way is a speciality of higher-order programming.

Higher-order abstractions also tend to be extremely generic. This enable us to apply the solution to a specific problem in many different contexts. As a simple example, think about a function to find the sum of all integers in a sequence.

(defn sumseq
  [xs]
  (if (seq xs)
    (+ (first xs) (sumseq (rest xs)))
    0))

(sumseq [1 2 3 4 5])
;;=> 15

The function has two constants in its definition – the number zero (0) and the plus (+) function. Zero is the neutral element for the plus operation. (Any number plus zero is that number itself). If we abstract out these two entities and make them the function’s parameters, then the function becomes more general, making possible combinations of any neutral element and operation. Let us call this new function fold-right because it “folds” a sequence into a single value. The right prefix denotes the function’s associativity.

(defn fold-right
  [xs opr n]
  (if (seq xs)
    (opr (first xs) (fold-right (rest xs) opr n))
    n))

(fold-right [1 2 3 4 5] + 0)
;;=> 15

(fold-right [1 2 3 4 5] * 1)
;;=> 120

Conclusion

Lisp has first-class functions and the ability to manipulate programs as data. This makes it a programming language of unlimited possibilities. In the context of Lisp, “abstractions” has a wider meaning. It is not just about data abstractions, but also about the ability to abstract over control flow and syntax. This post has just skimmed over data and control abstractions. We didn’t even mention “syntactic abstractions” until now!  Let that be the topic of a future post.

References

  1. Concepts, Techniques, and Models of Computer Programming
  2. Structure and Interpretation of Computer Programs