Becoming Patient in Writing Programs

People say writing Lisp will change the way you think, and most often that is referring to the sorts of paradigms that Lisp programs typically follow. After having programmed some non-trivial Lisp, you will more easily see things like code-data duality, functional patterns, expression-oriented programming, and so forth. But I’d like to mention one thing that a lot of people don’t think of regarding Lisp syntax. (Below, when I say “Lisp”, I mean any Lisp-like language: Scheme, Clojure, Common Lisp, and heaven forbid, Emacs Lisp.)

Those damn parens, they’re everywhere! But, as has been explained in many places, even in a previous post, Lisp’s syntax puts everything on just about equal footing. Barring a few outliers, like quotes, everything in Lisp looks the same.

The advantages of this are pretty well outlined: you know, metaprogramming and such. But one thing I don’t think is discussed often is the way it makes you think about programs.

In C, Java, or even up and coming languages like Haskell, the syntax very directly affects how you end up solving a problem. At least, that is what I have observed with most people. The tendency of many is to reduce the amount they type. In C, one might prefer to just use arrays as opposed to linked lists because linked lists requires having these extra functions and syntaxes, whereas arrays can use things like brackets to access elements and so forth.

In Lisp, for better or for worse, most everything looks the same. A function call, an array access, some control flow… all of it looks like `(this and this)`.

Array Access
C   : x[i]
Lisp: (aref x i)

Function Call
C   : f(x)
Lisp: (f x)

Arithmetic
C   : a/2 + b*c + sqrt(d)
Lisp: (+ (/ a 2) (* b c) (sqrt d))

Conditional Branching
C   : (a == b) ? x : y
Lisp: (if (= a b) x y)

C   :
    if (a == b) {
        doThis(a);
        return x;
    } else if (c == d) {
        doThat(b);
        return y;
    } else {
        return z;
    }
Lisp:
    (cond
      ((= a b) (do-this a) x)
      ((= c d) (do-that b) y)
      (t       z))

As a result, in my experience, you’re less prone to think about and implement a solution that otherwise might look ugly or inelegant in C or Haskell.

Many people don’t like this fact, and think it leads to verbosity. It is common in Lisp for code to be somewhat verbose; fully parenthesized syntax, spelled out names, and small functions lead to that.

By learning Lisp, it’s something you will probably come to appreciate, and will certainly affect the way you write programs in the future. Programs I write in PHP even have changed as a result.

To give a concrete example of what I am talking about, here is a short and simple implementation of a specific Markov chain written in Ruby to emulate a particular person’s pattern of writing a sequence of “:D” emoticons. (You may need to scroll this code horizontally.)

copter = { "^"=>{ ":"=>39, "D"=>1}, ":"=>{ "D"=>168, ":"=>12, "\n"=>8}, "D"=>{ ":"=>137, "D"=>14, "\n"=>32}}; loop { s = ""; char = "^"; while true; next_char = copter[char].map { |c, count| [c]*count }.flatten.sample; char=next_char; s << char; break if next_char == "\n"; end; puts s; sleep 1 }

While certainly a quick hack (and intended to be so), it shows that the particular implementation favors a shorter syntax. I wrote something relatively equivalent in Lisp. In Lisp, it’s not so easy to write one-liners, and if you do end up writing something short and hacky, usually you have the urge to clean it up. Here is my equivalent-in-functionality one-off hack written in Common Lisp (source):

;;; Utilities

(defun running-totals (vec)
  "Compute the successive totals of the vector VEC."
  (loop :for i :across vec
        :sum i :into sum
        :collecting sum :into totals
        :finally (return (coerce totals 'vector))))

(defun find-greatest-lower-bound (n seq)
  "Find the position of the maximal element X of the sequence SEQ such
  that N <= X."
  (position-if (lambda (x) (<= n x))
               seq))

;;; Distributions

(defstruct distribution
  length
  sum
  pdf
  cdf)

(defun compute-distribution (tallies)
  "Create a new distribution from the histogram TALLIES."
  (make-distribution
   :length (length tallies)
   :sum (reduce #'+ tallies :initial-value 0)
   :pdf tallies
   :cdf (running-totals tallies)))

(defun distributed-random (distribution)
  "Compute a random number between 0 and the length of DISTRIBUTION
according to the distribution DISTRIBUTION."
  (let ((r (1+ (random (distribution-sum distribution)))))
    (find-greatest-lower-bound r (distribution-cdf distribution))))

;;; Markov Nodes

(defstruct markov-node
  vertex
  edges
  traversal-distribution)

(defun create-markov-node (vertex edge-list)
  "Create a new Markov node with the edges in EDGE-LIST. The edges
should be of the form

    (VERTEX COUNT)

where count is the absolute count of that vertex."
  (make-markov-node
   :vertex vertex
   :edges (map 'vector #'first edge-list)
   :traversal-distribution (compute-distribution
                            (map 'vector #'second edge-list))))

(defun select-random-edge (markov-node)
  "Select a random edge of MARKOV-NODE to traverse."
  (aref (markov-node-edges markov-node)
        (distributed-random (markov-node-traversal-distribution markov-node))))

;;; Markov Chains

(defstruct markov-chain
  transition-table)

(defun create-markov-chain (markov-nodes)
  "Create a new Markov chain from the list of nodes MARKOV-NODES."
  (loop :with ht := (make-hash-table)
        :for node :in markov-nodes
        :do (setf (gethash (markov-node-vertex node) ht)
                  node)
        :finally (return (make-markov-chain :transition-table ht))))

(defun list-to-markov-chain (list)
  "Convert a list LIST to a Markov chain."
  (loop :for (vertex . edges) :in list
        :collect (create-markov-node vertex edges) :into nodes
        :finally (return (create-markov-chain nodes))))

(defun get-node (vertex markov-chain)
  "Get the node corresponding to VERTEX in the Markov chain
MARKOV-CHAIN."
  (gethash vertex (markov-chain-transition-table markov-chain)))

(defun random-transition (vertex markov-chain)
  "Return a new vertex by randomly traversing from VERTEX in the
  Markov chain MARKOV-CHAIN."
  (let ((node (get-node vertex markov-chain)))
    (select-random-edge node)))

;;; Copter's Markov Chain

(defvar *copter-chain*
  (list-to-markov-chain `((#\^ (#\:        39)
                               (#\D         1))
                          (#\: (#\D       168)
                               (#\:        12)
                               (#\Newline   8))
                          (#\D (#\:       137)
                               (#\D        14)
                               (#\Newline  32)))))

(defun copterize ()
  "Create a random Copter string."
  (with-output-to-string (stream)
    (loop :for edge :=    (random-transition #\^  *copter-chain*)
                    :then (random-transition edge *copter-chain*)
          :until (char= edge #\Newline)
          :do (write-char edge stream))))

Yes, indeed, it is much more verbose, but in writing it, I didn’t think about verbosity or syntax whatsoever, and as a result, it came out to something much more beautiful, and in fact, reusable. This is not to say the Ruby code couldn’t be written in similar style, and this is not to say Ruby programmers universally write code as shown previously. Rather, it’s just to illustrate the human tendency to take shortcuts.

I am not saying syntactically short code doesn’t have it’s place. It certainly does, especially when you want to measure your time to complete a task from start to finish in seconds or minutes, and not minutes or hours. It has actually be the case for me personally where this style of writing code has caused me distress: during an interview. I was asked to write a “script” that monitored the output of some command-line program. In particular, the program measured certain statistics of one’s system, and output the statistics in columns (similar to that of top).

In Awk, Perl, Ruby, or related, such a program would probably have been no more than 10 or 20 lines. My Lisp program weighed in at about 40 lines, and was broken up into a structure similar to the program above. There was a function to parse individual lines into data that Lisp could understand (or reject a line if it was syntactically invalid), a function to create so-called “monitors” so that multiple checks could be composed simultaneously (e.g., check that memory doesn’t exceed $x$ and CPU percent doesn’t exceed $y$), a function to compose the monitors, an entry point, and so on.

While the program was very easy to reason about, very general, and very easy to extend, it was apparent in the end that the interviewer didn’t want this. They wanted a one-off hack, albeit a somewhat cleaned up one, that one would write in a production engineering or development/operations position on-the-fly just to check how things are running. The style of writing Lisp programs I described tends to not be so good for that.

In any case, when looking at software engineering in the large, the style seems to be much more beneficial than detrimental, only because much of software engineering is about writing maintainable code. Because of Lisp’s monotonous syntax, over time, you develop patience in writing programs.

Leave a Reply

  

  

  

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Before you post, please prove you are sentient.

what is 8 plus 5?