Reasons to Recommend Common Lisp

On Reddit, /u/rhabarba asks: Should I learn (Common) Lisp? Here’s my reply:

I am a technical writer and “hobbyist” programmer who does some unofficial programming at work to automate documentation things. To give you a sense of my language background, I enjoy programming in Perl, Python, Scheme, and Common Lisp.

Reasons to recommend Common Lisp include:

  • In many ways, it’s a superset of the other languages I mentioned: you can “script” with regular expression and filesystem support, and you can also write larger programs using built-in OO that’s still more advanced than the built-in Perl or Python stuff.
  • Multi-paradigm: you can write code in whatever style you want to solve your problem. You only use OO if you want to, you’re not forced by the language. Functional style is there for you, especially via libraries. You can also be imperative and bash as much state as you want. Almost any type of code you might want to write can be (probably has been?) written in Common Lisp. There’s a lot of room to grow as you learn more.
  • Dynamic, interactive, and inspectable: redefine almost anything on the fly at the REPL, watch those changes get picked up by the rest of your system as it runs. This is true for running web servers, whatever. The debugger and inspector available via SLIME in Emacs is also better than anything else I’ve used in other languages.
  • Multiple good implementations to choose from; there are several fast “native” compilers, several portable interpreter-based implementations. If you write portable code you can run on many different implementations, so you can mix and match depending on what’s easiest to install or use for your needs.
  • Quicklisp lets you install any of 1200* libraries, very easily. You’ve got all the basics: HTTP clients and servers, JSON, XML, and Markdown parsers, and lots more advanced stuff too.
  • 25 year old code that does advanced, weird, or just cool things still works fine. It just runs way faster now.
  • Good books: ‘Paradigms of Artificial Intelligence Programming’ by Peter Norvig, ‘Object-Oriented Programming in Common Lisp’ by Sonya Keene, and many others.

Finally, I have been able to write programs to do “harder” things in Lisp than I have in other languages, even though I’m not really a programmer or “engineer” or whatever title you prefer. I think the simple list data structure is a great way to bootstrap a prototype of your program, and it encourages data-structure thinking rather than “stringy” thinking as some languages do. That said, I use a lot of languages to get my work done, so it’s not a religion or anything.

Good luck!

The Sentinel File Pattern

In this short essay I’ll describe the “sentinel file” pattern, which I recently used when writing a command-line tool to use at $WORK for interacting with our web API.

The essence of the sentinel file pattern is that you use a certain file’s last-modified time as a record against which you compare other time-based values.

It is useful in many contexts, such as software builds; in the context of web APIs, it can be used to track whether you will need to reauthenticate with the API before you fire off a bunch of API calls.

The recipe is essentially this:

  • Update a sentinel file F‘s timestamp at time T.
  • When you are about to take an action such as make an API call, see if the current time, T’, is greater than the timeout value of your web API, V, plus the sentinel file’s existing timestamp T.

We can translate this into Scheme as follows (this is scsh, to be exact), where:

;; F = sentinel-file
;; T = (file-last-mod sentinel-file)
;; T' = (time)
;; V = api-timeout-value

(define (sentinel-expired? sentinel-file)
   (> (time)
      (+ (file-last-mod sentinel-file) api-timeout-value)))

Note that TIME and FILE-LAST-MOD are part of the scsh POSIX API.

This pattern is much more efficient than storing some kind of “am I logged in?” value in a JSON/YAML/XML/s-expression config file that has to be read in and parsed on every invocation and written out from time to time.

I debated whether to write about this simple technique at all because it seems like an old trick that many people know. However, I’m going to assume that I am not unique, and that there are lots of people out there who could benefit from using this technique when the right situation arises.

The Debugger is a Notebook

penrose-tiling-based-modular-origami.jpg

My style of programming has changed since the ODB. I now write insanely fast, making numerous mistakes. This gives me something to search for with the ODB. It’s fun.

– Bil Lewis, creator of the Omniscient Debugger

I. Programmers and Poets

In this short essay I will explore some similarities between the way (some) programmers work when doing exploratory programming that can be fruitfully compared to the way poets write poems. I will also sprinkle in some attempts to make the case that a good debugger is core to the experience of composing a new program that you don’t understand very well yet, and compare that with the experience of writing a poem. I know a lot about the former because I am not a very good programmer, so many programs that explore computer science concepts are “exploratory” for me; I know a lot about the latter because I am a reasonably good poet who has written many poems (which is to say, that I have edited many poems, which is really more important).

This work is largely inspired by:

  • The experience of working an programs for SICP exercises and getting popped into the MIT Scheme debugger a lot! 1
  • Using the Scheme 48/scsh inspector a bunch while working on geiser-scsh
  • Writing a lot of poems

II. Generating {Program,Poem} Text

Computer program texts are compressed descriptions of computational processes designed to be experienced by computers and humans. Similarly, poems are compressed descriptions of cognitive and emotional processes designed to be experienced by humans.

Both artifacts strive to encapsulate something that was understood by the author(s) at one point in time and convey that understanding to a reader at another point in time (human or machine). In poetry world, there are a number of different ways to work. There are ostensibly some writers who think really hard for a moment and write a fully-formed sentence. Then they think for a few moments more and write down another fully-formed sentence. And so on.

In reality, there are very few poets who work this way. Most people work using an approximation of what Sussman beautifully describes as “problem-solving by debugging almost-right plans”. 2 This is actually how human beings create new things! As my professor told our writing workshop, “I can’t teach you how to write. I can only teach you how to edit your own work”. Few people write well, and fewer edit well. But in the end, writing and editing are actually the same thing. When you first edit a poem, you may correct minor errors in the text. The more important work is “running the program” of the poem in your head, reading it over and over, reciting it aloud, testing whether it achieves the aesthetic purpose you have set for it. You will add a pronoun in one place, and replace an adjective in another. You might remove the last line, or add another stanza entirely. Do this for long enough, and you may find the poem has changed substantially over the course of having been “debugged”. It may also achieve a goal that you didn’t know existed when you began writing it. I suspect there is something very similar at work when people are doing exploratory programming sessions.

III. Debugger as Crutch/Enabler

Debuggers are seen by some as a crutch. I agree that debuggers are a crutch. There’s a reason crutches were invented. Because without them, you would have to crawl along, dragging your broken leg behind you in the dirt. And we all have a “broken leg” of sorts when we’re working on a problem we don’t understand very well.

I’d like to propose a better metaphor for debuggers. The debugger is a notebook where you can sketch out different versions of your program. You may correct minor errors in a variable declaration, or change a parameter to a procedure. You might redefine an existing procedure as a higher-order procedure that replaces two or three more verbose ones. And so on. All inside the debugger!

A sufficiently powerful debugger will give you the freedom to sketch out an idea quickly, watch it break, and play around in the environment where the breakage occurred, reading variable bindings, entering new definitions, etc.

I think of this style of programming as “sketching in your notebook” because you don’t write poems by staring at a blank sheet of paper for two minutes and then carefully writing a fully-formed sentence. You have an initial idea or impulse, and then you express it as fast as you can! You write down whatever parts of it you can manage to catch hold of, since your brain is working and associating much faster than your pen can really capture. What you end up with is a pile of things, some of which you will discard, some of which are worth keeping just as they are, and some of which are worth keeping but non-optimal and will need to be rewritten. If you actually have an idea worth expressing, you are in much greater danger of not capturing something than you are of making a mess. You will always start by making a mess and then cleaning it up 3.

I submit that a sufficently powerful, expressive debugging environment is as necessary to the programmer as a pocket notebook to the poet.

Interesting Reads

These essays explore writing, debugging, and thinking in more depth:

(Image courtesy fdecomite under Creative Commons License.)

Footnotes:

1

For more information about how cool the MIT Scheme debugger is, see Joe Marshall’s informative blog post.

2

This technique is mentioned on his CSAIL page here. For more information, see the link to his paper elsewhere on this page.

3

You may enjoy an interesting essay with this title: Make a Mess, Clean it Up!

Make your own iterators in Scheme using closures

idle-machines

Introduction

I recently bought a copy of Higher Order Perl (also known as HOP) by Mark Dominus. In chapter 4, he introduces iterators. At a high level, an iterator is a black box with an input funnel, an output funnel, and a big red “NEXT” button. You put something into the funnel at time T; then, at some later time T+n, you press the “NEXT” button and something useful comes out.

Iterators are useful in cases when you want to access a potentially huge list of things one at a time, but you don’t have access to a computer with infinite memory.

In this post we’ll look at a moderately useful iterator example; a directory walker that recurses down a directory tree on your file system. The implementation is given in Scheme (specifically, the scsh dialect); the code and the descriptions thereof are heavily inspired by Dominus’ excellent book. However, this post contains the work of an amateur. Any errors or omissions in the following code and explanations are mine.

Iterators are made with closures

In order to build a useful iterator, we need to have a basic understanding of closures. A closure is just a function packaged up with an environment. The environment allows us to store up state between function calls. As noted above, it’s easiest just to think of it as a little black box that we can pass around in our program.

In Scheme and Common Lisp, you build functions with LAMBDA. Here’s a very simple closure example in Scheme, translated from the first example given in HOP:

(define (upto m n)
  (set! m (- m 1)) ;needed since we don't have post-increment ($i++)
  (lambda ()
    (if (< m n)
        (begin (set! m (+ m 1)) m)
        #f)))

This is a function that returns a function (a closure). To use the closure returned by UPTO, assign it to a variable and call it whenever you want the next value. When the iterator is exhausted, it will return #f.

> (define 1to10 (upto 1 10))
> (1to10)
1
> (1to10)
2
...
> (1to10)
9
> (1to10)
10
> (1to10)
#f

A trivial file tree iterator

A more interesting and practical use of this technique is to walk a directory tree on your computer. In the Scheme procedure below, we take a list of directories and then build and return a closure that, when called, will walk the directory tree breadth-first, printing out the names of files as we go.

(define (dir-walk queue)
  (let ((file #f))
    (lambda ()
      (if (not (null? queue))
          (begin (set! file (car queue))
                 (set! queue (cdr queue))
                 (cond ((file-directory? file)
                        (let ((new-files (directory-files file)))
                          (set! queue (append queue (map (lambda (filename)
                                                           (string-append file "/" filename))
                                                         new-files)))
                          file))
                       ((file-regular? file) file)
                       (else #f)))))))

The important part to notice is the inner LAMBDA. This is where we create a closure by packaging up a procedure with an environment. The closure’s environment remembers the contents of the variable QUEUE in memory, so we can ask for the elements of QUEUE at our leisure.

Here it is running on my machine:

> (define dir-iter1 (dir-walk '("/Users/rloveland/Desktop/current/")))
> (dir-iter1)
"/Users/rloveland/Desktop/current/XProlog.jar"
> (dir-iter1)
"/Users/rloveland/Desktop/current/all-jira-issues.txt"
> (dir-iter1)
"/Users/rloveland/Desktop/current/automate-campaign-setup.txt"
> (dir-iter1)
"/Users/rloveland/Desktop/current/buflocal.scm"
> (dir-iter1)
"/Users/rloveland/Desktop/current/bundle.js"

Just for fun, here’s a version of the same function in Common Lisp. It’s essentially the same as the scsh version, save that it uses the nice CL pathname machinery instead of appending raw strings, and also makes use of the CL-FAD convenience library.

(defun dir-walk (queue)
  (let ((file nil))
    (lambda ()
      (if (not (null queue))
          (progn
            (setf file (car queue))
            (setf queue (cdr queue))
            (cond ((cl-fad:directory-pathname-p file)
                   (let ((new-files (cl-fad:list-directory file)))
                     (setf queue (append queue (mapcar #'(lambda (filename)
                                                           (merge-pathnames filename file))
                                                       new-files)))
                     file))
                  ((cl-fad:file-exists-p file) file)
                  (t nil)))))))

Usage is also essentially the same:

CL-USER> (defvar *tree-walker* (dir-walk '(#P"/Users/rloveland/Desktop/current/")))
*TREE-WALKER*
CL-USER> (type-of *tree-walker*)
FUNCTION
CL-USER> (funcall *tree-walker*)
#P"/Users/rloveland/Desktop/current/"
CL-USER> (funcall *tree-walker*)
#P"/Users/rloveland/Dropbox/current/.debuggerDefaults"
CL-USER> (funcall *tree-walker*)
#P"/Users/rloveland/Dropbox/current/.DS_Store"
CL-USER> (funcall *tree-walker*)
#P"/Users/rloveland/Dropbox/current/A"
CL-USER> (funcall *tree-walker*)
#P"/Users/rloveland/Dropbox/current/A.hi"
CL-USER> (funcall *tree-walker*)
#P"/Users/rloveland/Dropbox/current/A.hs"

A slightly less trivial file tree iterator

Listing out files and directories is nice, but not that useful. We’d like a way to see only those files and directories that have some interesting property.

This can be accomplished by passing in another argument to our DIR-WALK function: this argument will be yet another function that will test the current file to see whether it’s interesting to us. It’s pretty easy to change DIR-WALK to accept a function argument, INTERESTING?. This arbitrary function is used to check the file to see if we care about it.

This time around, when we build our internal queue, we use a call to FILTER to make sure that only interesting files get added.

(define (dir-walk* interesting? queue)
  (let ((file #f))
    (lambda ()
      (if (not (null? queue))
          (begin (set! file (car queue))
                 (set! queue (cdr queue))
                 (cond
                  ((file-directory? file)
                        (let ((new-files (directory-files file)))
                          (set! queue (append queue (filter interesting? (map (lambda (filename)
                                                           (string-append file "/" filename))
                                                         new-files))))
                          (if (interesting? file) file)))
                  ((interesting? file) file)
                  (else #f)))
          #f))))

And here it is in use; in this example, we pass an INTERESTING? function that asks for only files that are not marked as executable:

> (define dir-iter2 (dir-walk* (lambda (f) (file-not-executable? f)) '("/home/rml/Desktop/current")))
> (dir-iter2)
> (dir-iter2)
"/home/rml/Desktop/current/A.hi"
> (dir-iter2)
"/home/rml/Desktop/current/A.hs"
> (dir-iter2)
"/home/rml/Desktop/current/A.o"
> (dir-iter2)
"/home/rml/Desktop/current/ABBREV.xlsx"
> (dir-iter2)
"/home/rml/Desktop/current/AddInts.class"
> (dir-iter2)
"/home/rml/Desktop/current/AddInts.java"

Conclusion

There are still bugs and unexpected behavior in DIR-WALK*. For example, on the first call to the resulting iterator there is no result due to the one-armed IF. There are also strange things that happen if we want to filter out directories from our results, since we mix together the FILE-DIRECTORY? check and the INTERESTING? check inside the iterator. However, despite these small nits, it can still do useful work on my machine 1, and it’s a good enough example of using closures to build iterators.

Here’s hoping you’ll enjoy playing with closures and iterators in your own code!

(Image courtesy zeitfanger.at under a Creative Commons License.)

Footnotes:

1 In the grandest internet tradition, “It works on my machine” ™.

Why Libraries and Librarians are Amazing

mother-of-all-libraries-14

Libraries: because you cannot have a conscience without a memory.

For some time now I’ve been meaning to write about why libraries (and librarians!) are important. After all, I’m a child of the library. In particular, I’m a child of this library, where I spent many happy hours growing up. As the son of a blue-collar family that was anything but “bookish”, well, I don’t know where I’d be without libraries.

What follows are a collection of random thoughts (linky-blurbs, really) about the general amazingness of libraries and librarians:

  • Librarians fought, and are still fighting, surveillance-state idiocy like the PATRIOT Act.
  • On a lighter note, the Internet Archive also has this collection of classic MS-DOS games that you can play in your browser. When I saw titles like Street Fighter, Sim City, Donkey Kong, and Castle Wolfenstein in this list, I have to admit I kinda freaked out. The future is amazing. Growing up, I had to memorize my friends’ phone numbers! And now we have magic tiny emulated computers in our browser tabs.

See also:

Never trust a corporation to do a library’s job.

(Image courtesy Cher Amio under Creative Commons license.)

Why Markdown is not my favorite text markup language

origami-galerie-freising-tomoko-fuseThere are many text markup languages that purport to allow you to write in a simple markup format and publish to the web. Markdown has arguably emerged as the “king” of these formats. I quite like it myself when it’s used for writing short documents with relatively simple formatting needs. However, it falls a bit short when you start to do more elaborate work. This is especially the case when you are trying to do any kind of “serious” technical authoring.

I know that “Markdown” has been used to write technical books. Game Programming Patterns is one excellent example; you can read more about the author’s use of Markdown here, and the script he uses to extend Markdown to meet his needs is here. (I recommend reading all of his essays about how he wrote the book, by the way. They’re truly inspiring.). Based on that author’s experience (and some of my own), I know that Markdown can absolutely be used as a base upon which to build ebooks, websites, wikis, and more. However, this is exactly why I used the term “Markdown” in quotes at the beginning of this paragraph. By the time you’ve extended Markdown to cover your more featureful technical authoring use cases, it really isn’t “just” Markdown anymore. This is fine if you just want to get something done quickly that meets your own needs, but it’s not ideal if you want to work with a meaningful system can be standardized and built on.

Below I’ll address just a few of the needs of “industrial” technical writing (the kind that I do, ostensibly) where Markdown falls a little short. Lest this come off as too negative, it’s worth stating for the record that a homegrown combination of Markdown and a few scripts in a git repo with a Makefile is still an absolute paradise compared to almost all of the clunky proprietary tooling that is marketed and sold for the purposes of “mainstream” technical writing. I have turned to such a homebrewed setup myself in times of need. I’ve even written about how awesome writing in Markdown can be. However, this essay is an attempt to capture my thoughts on Markdown’s shortcomings. Like any good internet crank, I reserve the right to pull a Nickieben Bourbaki at a later date.

I. No native table support

If you are doing any kind of large-scale tech docs, you need tables. Although constraints are always good, and a simple list can probably replace 80% of your table usage if you’re disciplined, there are times when you really just need a big honkin’ table. And as much as I’m used to editing raw XML and HTML directly in Emacs using its excellent tooling to completely sidestep the unwanted “upgrade” to the Confluence editor at $WORK, most writers probably don’t want to be authoring tables directly in HTML (which is the “native” Markdown solution).

II. No native table of contents support

Yes, I can write a script myself to do this. I can also use one of the dozens of such scripts written by others. However, I’d rather have something built in, and consider it a weakness of the format.

III. Forcing the user to fall back to inline HTML is not really OK

Like tables, there are a number of other formatting and layout use cases that Markdown can’t handle natively. As with tables, you must resort to just slapping in some raw HTML. Two reasons why this isn’t so amazing are:

  • It’s hard for an editor to support well, since editing “regular” text markup and tag-based markup languages are quite different beasts
  • It punts complexity to thousands of users in in order to preserve implementation simplicity for a small number of implementors

I can sympathize with the reasoning behind this design decision, since I am usually the guy making his own little hacks that meet simple use cases, but again: not really OK for serious work.

IV. Too many different ways to express the same formatting

This has lead to a number of incompatibilities among the different “Markdown” renderers out there. Just a few of the areas where ambiguity exists are: headers, lists, code sections, and links. For an introduction to Markdown’s flexible semantics, see the original syntax docs. Then, for a more elaborate description of the inconsistencies and challenges of rendering Markdown properly, see Why is a spec needed?, written by the CommonMark folks.

V. Too many incompatible flavors

There are too many incompatible flavors of Markdown that each render a document slightly differently. For a good description of the ways different Markdown implementations diverge, see the Babelmark 2 FAQ.

The “incompatible flavors” issue will hopefully be addressed with the advent of the CommonMark Standard, but if you read the spec it doesn’t address points I, II, or III at all. This makes sense from the perspective of the author of a standards document: a spec isn’t very useful unless you can achieve consensus and adoption among all the slightly different implementations out there right now, and Markdown as commonly understaood doesn’t try to support those cases anyway.

VI. No native means of validation

There will of course be a reference implementation and tests for CommonMark, which will ensure that the content is valid Markdown, but for large-scale documentation deployments, you really need the ability to validate that the documentation sets you’re publishing have certain properties. These properties might include, but aren’t limited to:

  • “Do all of the links have valid targets?”
  • “Is every page reachable from some other page?”

Markdown doesn’t care about this. And to be fair it never said it would! You are of course free to use other tools to perform all of the validations you care about on the resulting HTML output. This isn’t necessarily so bad (in fact it’s not as bad as points I and II in my opinion, since those actually affect you while you’re authoring), but it’s an issue to be aware of.

This is one area where XML has some neat tooling and properties. Although I suppose you could do something workable with a strict subset of HTML. You could also use pandoc to generate XML, which you then validate according to your needs.

Conclusion

Markdown solves its original use case well, while punting on many others in classic Worse is Better fashion. To be fair to Markdown, it was never purported to be anything other than a simple set of formatting conventions for web writing. And it’s worth saying once more that, even given its limitations, a homegrown combination of Markdown and a few scripts in a git repo with a Makefile is still an absolute paradise compared to almost all of the clunky proprietary tooling that is marketed and sold for the purposes of “mainstream” technical writing.

Even so, I hope I’ve presented an argument for why Markdown is not ideal for large scale technical documentation work.

(Image courtesy Gerwin Sturm under a Creative Commons license.)

How to install Perlbrew on Fedora 20 and use it with (m)ksh

yen-bill-crane

This post details how to go about installing perlbrew on a Fedora 20 Linux system for a user whose default shell is in the ksh family, specifically mksh, which is the shell I use.

The instructions in each section can be used separately if you are just a Fedora user or just a (m)ksh user.

Installing Perlbrew on Fedora 20

If you try to install Perlbrew using the instructions on its website, Fedora barfs. Fortunately, the workaround you need is detailed in this Github issue. (Hint: read the whole thread and then do what wumpus says.)

Using Perlbrew with ksh or mksh

The perlbrew bashrc file uses a few “bashisms” (unnecessarily, I think, but it is a “bash” rc after all). I managed to hack them out and, instead of sourcing perlbrew’s default bashrc file, I now source a kshrc built by applying the patch below.

It’s working well for me so far under mksh, but feel free to leave a comment if it doesn’t work for you and I’ll try to help.

Happy Perlbrewing!

--- bashrc	2014-12-30 12:49:14.110446784 -0500
+++ kshrc	2014-12-30 13:15:58.750454519 -0500
@@ -1,6 +1,5 @@
 export PERLBREW_BASHRC_VERSION=0.72
 
-
 __perlbrew_reinit() {
     if [[ ! -d "$PERLBREW_HOME" ]]; then
         mkdir -p "$PERLBREW_HOME"
@@ -13,7 +12,9 @@
 }
 
 __perlbrew_purify () {
-    local path patharray outsep
+    path=
+    patharray= 
+    outsep=
     if [[ -n "$BASH_VERSION" ]]; then
         IFS=: read -ra patharray <<< "$1"
     fi
@@ -30,13 +31,13 @@
 }
 
 __perlbrew_set_path () {
-    export MANPATH=$PERLBREW_MANPATH${PERLBREW_MANPATH:+:}$(__perlbrew_purify "$(manpath)")
-    export PATH=${PERLBREW_PATH:-$PERLBREW_ROOT/bin}:$(__perlbrew_purify "$PATH")
+    export MANPATH=$PERLBREW_MANPATH:$MANPATH
+    export PATH=${PERLBREW_PATH:-$PERLBREW_ROOT/bin}:$PATH
     hash -r
 }
 
 __perlbrew_set_env() {
-    local code
+    code=
     code="$($perlbrew_command env $@)" || return $?
     eval "$code"
 }
@@ -64,8 +65,8 @@
 }
 
 perlbrew () {
-    local exit_status
-    local short_option
+    exit_status=
+    short_option=
     export SHELL
 
     if [[ $1 == -* ]]; then

(Image courtesy Japanexperterna.se under Creative Commons License.)