Archive for the ‘Lisp’ Category

A krevitch to snork your flads: the lost ~U format directive

October 7, 2010

Preparing for my upcoming ILC talk led me to some old Common
Lisp email archives where I came across this proposal from Guy
Steele:

Date: 11 June 1982 2233-EDT (Friday)
From: Quux
To: bug-lisp at MIT-AI, bug-lispm at MIT-AI, common-lisp at SU-AI
Subject:  Proposed new FORMAT operator: ~U("units")

Here's a krevitch that will really snork your flads. ~U swallows an
argument, which should be a floating-point number (an integer or ratio
may be floated first). The argument is then scaled by 10^(3*K) for
some integer K, so that it lies in [1.0,1000.0). If this K is suitably
small, then the scaled number is printed, then a space, then a
metric-system prefix. If not, then the number is printed in
exponential notation, then a space. With a :, prints the short prefix.

Examples:

 (FORMAT () "~Umeters, ~Uliters, ~:Um, ~:UHz" 50300.0 6.0 .013 1.0e7)
  =>  "50.5 kilometers, 6.0 liters, 13.0 mm, 10.0 MHz"

And you thought ~R was bad!

Later he made this small addition:

Date: 12 June 1982 1119-EDT (Saturday)
From: Quux
To: bug-lisp at MIT-AI, bug-lispm at MIT-AI, common-lisp at SU-AI
Subject:  More on ~U (short)

I forgot to mention that the @ flag should cause scaling by powers of 2^10
instead of 10^3:

(format () "~Ubits, ~:Ub, ~@Ubits, ~:@Ub" 65536 65536 65536 65536)
  =>  "65.536 kilobits, 65.536 Kb, 64.0 kilobits, 64.0 Kb"

--Q

Lisp implementors/maintainers poll

October 5, 2010

I’m working on my talk for the upcoming ILC. If you are the implementor or maintainer of a Common Lisp system, I’d love to know if you were involved in the standardization of Common Lisp either in the pre-ANSI period or on the ANSI committee. If you could drop me an email or leave a comment here, telling me who you are and saying whether you were or were not and what implementation you work on, that’d be a huge help. (If you were, please let me know if it was pre-ANSI, ANSI, or both.)

Whither Lispbox?

April 16, 2010

When I wrote Practical Common Lisp, in order to provide a semi-standard environment for people to play with Common Lisp I created Lispbox, a customized version of Matthew Danish and Mikel Evins’s Lisp in a Box. Like Lisp in a Box, Lispbox combined Emacs, SLIME, and a Common Lisp implementation into a single, easily installable hunk of bits.

At the time, my goal was just to make a single version that could be installed on GNU/Linux, OS X, and Windows that would contain the libraries needed to run the example code from PCL in a predictable environment. (For instance, Lispbox removes implementation-specific packages from the CL-USER package use list so that the behavior of different Lispboxen would be more consistent.)

At the time I had dreams of continuing to work on Lispbox and make it something more than just a bike-with-training-wheels for new Lispers. At the very least I hoped to be able to continue to build and distribute new versions of it as Lisp implementations were updated, etc. As it turns out, I’ve completely failed to do either of those things.

Somewhere along the line, I registered the lispbox.com domain but never did anything with it. My registration is going to expire in about a week and since I’m pretty obviously not going to be doing anything with Lispbox myself, I’m not going to renew it. But I would be happy to let someone take over the project.

All the code needed to build Lispboxen is available as a Google code project. And people other than me have in fact succeeded in building working Lispboxen from it. If you are interested in doing something with Lispbox, please email me. I’ll be happy to set you up as a contributor on the Google code project and to answer questions about how things work. And if anyone wants to really take it over, I’d be more than willing to officially pass the baton.

Not that Skef Wholey!

September 21, 2009

Whoops! Turns out that Jamie Zawinski suffered a slight brain glitch during our Coders at Work interview when recounting his time as a high-schooler working in Scott Fahlman’s CMU AI Lab. He said:

But there were some really entertaining characters in that group. Like the guy who was sort of our manager—the one keeping an eye on us—Skef Wholey, was this giant blond-haired, barbarian-looking guy. Very intimidating-looking. And he didn’t talk much. I remember a lot of times I’d be sitting there—it was kind of an open-plan cubicle kind of thing—working, doing something, writing some Lisp program. And he’d come shuffling in with his ceramic mug of beer, bare feet, and he’d just stand behind me. I’d say hi. And he’d grunt or say nothing. He’d just stand there watching me type. At some point I’d do something and he’d go, “Ptthh, wrong!” and he’d walk away. So that was kind of getting thrown in the deep end. It was like the Zen approach—the master hit me with a stick, now I must meditate.

However, as Jamie emailed to tell me yesterday, and Skef Wholey emailed me about today, Skef Wholey was not the giant, blond-haired bare-footed hacker who supervised a young Zawinski. Skef, it turns out, is 5’8” and has dark brown hair. Jamie’s giant supervisor was another guy named Rob MacLachlan.

Skef also tells me that Rob did carry a ceramic beer mug but as far as Skef recalls it held coffee, not beer. Skef also described Rob as “substantially more articulate, particularly in matters of coding and in Computer Science in general” than someone who’d just say “Ptthh, wrong!” and walk away. To be fair, Jamie did say, elsewhere in the interview, about Skef/Rob, “Well, he wasn’t completely a cave man. He would actually tell me things, too.”

My apologies to Skef for the case of mistaken identity.

Coders at Work due out in just over a month

August 4, 2009

I just learned that my new book, Coders at Work is due to go to the printers on August 17th and should hit bookstore shelves about a month after that and, as I understand it, copies ordered from Amazon might show up even a bit earlier. I’m quite pleased with how it turned out and hope every programmer everywhere buys at least one copy!

Meanwhile I’m thinking about what’s next. The world of Lisp books seems to be exploding, with Conrad Barski’s Land of Lisp due out later this year and O’Reilly finally dropping their anti-Lisp policy to publish a book by Nick Levine. Meanwhile Practical Common Lisp continues to sell well. Perhaps a 2nd edition or sequel to Practical Common Lisp is in order. I also have several other non-Lisp book ideas bouncing around my head. We’ll see.

P.S. If you are a blogger or book reviewer interested in a sneak peek at Coders at Work, email me and I may be able to hook you up.

Practical Common Lisp Japanese translation

August 4, 2008

I was recently notified – somewhat to my suprise – that the Japanese publisher Ohmsha is publishing a Japanese translation of Practical Common Lisp which should now be avaliable in bookstores and on amazon.co.jp. I had known that there was a small group working on a translation but hadn’t realized they had found a publisher. My thanks to those translators and to Masako Omata at Franz who, as I understand it, did a fair bit of work to make it all happen. I got my copy in the mail the other day. Looks good though I can’t say much about the quality of the translation other than that it seems to contain quite a number of Japanese characters. I’ll be interested to hear from any Japanese readers what they think of it.

Bomb me—please!

September 19, 2007

I wrote Practical Common Lisp because I felt that Common Lisp needed a new introductory book that could ease folks raised on other languages into Common Lisp and then show them what it’s really all about. Based on emails from readers, reviews on Amazon, word of mouth in the Lisp world, and the fact that the online version of PCL is the top hit when you Google for “lisp book”, I’ll say I succeeded tolerably well. So imagine my dismay when someone pointed out to me today the Google results for “lisp tutorial”.

The top hit is a page which apparently hasn’t been updated since around 1999 and isn’t really a tutorial anyway, so much as a large list of links including a link to the Hyperspec when it was hosted at harlequin.com.1 The next few “lisp tutorial” hits are — with all due respect — exactly the sort of dated, dry tutorials that inspired me to write Practical Common Lisp in the first place and to do a deal with Apress to allow me to keep it online even after the dead tree version was published. Practical Common Lisp doesn’t appear anywhere, as far as I can tell, in the results for “lisp tutorial”.

With that in mind I did a small bit of search engine optimization today to make sure that the phrase “Common Lisp tutorial” appears on the main page of the Practical Common Lisp web site. If you also think Lisp might be better served if PCL was at least one of the results returned to a would-be Lisper searching for a Lisp tutorial you can help out: if you have a web page where it would be reasonable to do so, consider linking to the url http://www.gigamonkeys.com/book/ with a link text of “lisp tutorial” or “common lisp tutorial”. Yes, I’m asking you to participate in a Google bombing. But it’s for a good cause. Think of the children.

Update: Based on the first couple folks I’ve seen providing links to the PCL website (thanks, guys!) I must not have made myself quite clear enough. The name of the game in a Google bombing is for everyone to use the same text for the link. If you want to play along, your HTML should look like this:

<a href="http://www.gigamonkeys.com/book/">Common Lisp tutorial</a>
        

or

<a href="http://www.gigamonkeys.com/book/">Lisp tutorial</a>
        

1. Harelequin doesn’t exist anymore. The canonical home of the Hyperspec is at Lispworks which is now two spin-offs removed from Harlequin: Global Graphics bought Harlequin and spun off Xanalys which in turn, in 2005, spun off Lispworks.

Compiling queries without EVAL

July 27, 2007

Gary King recently blogged a question about whether a use of EVAL he had recently made in some Common Lisp code was legit. This caught my eye because I suspect this question came up while Gary was working on a project that I once worked on. Anyway, since he asked, the short answer is, “No. The old rule that if you’re using EVAL you’re doing something wrong is still true.” A slightly longer answer follows.

The problem Gary set out to solve is that he’s got a a bunch of chunks of text coming out of some sort of database and he wants to query them with logical expressions like this one:

(or 
 (and "space" "mission")
 (and (or "moon" "lunar") "landing"))
        

These expressions are obviously not Lisp but rather a query language where the logical operators AND and OR (and presumably other ones like NOT) have their usual logical meaning and literal strings should evaluate to true if the text we’re matching against testing contains the string and false if not. Thus the expression above would match text containing the words “space” and “mission” or either of “moon” or “lunar” along with “landing”. Gary considered, and rejected, writing “a simple recursive evaluator to deal with ands and ors”. Instead he wrote some code to munge around expressions like the one above into a form that he could EVAL. In other words, instead of writing his own interpreter he just munged his code into a form that Lisp could interpret for him. Which is okay. Except for the rule that if you’re using EVAL you’re doing something wrong.

What he should have done is written a compiler. Luckily Common Lisp comes with a Lisp compiler built in so all we have to do to write our own compiler is translate our source language into Lisp. Here’s how I’d do it.

First define a function that takes a query expression and returns two values, an equivalent expression with all string literals replaced with GENSYM’d variable names, and an alist of the strings and the corresponding GENSYM’d names. In this phase we also detect if the same literal string appears more than once so we only generate a single binding for each unique string.

(defun translate (tree &optional bindings)
  (typecase tree
    (cons
     (multiple-value-bind (newcar newbindings)
         (translate (car tree) bindings)
       (multiple-value-bind (newcdr newbindings2)
           (translate (cdr tree) newbindings)
         (values (cons newcar newcdr) newbindings2))))
    (symbol (values tree bindings))
    (string 
     (let ((binding (assoc tree bindings :test #'equal)))
       (cond
         (binding (values (cdr binding) bindings))
         (t 
          (let ((sym (gensym)))
            (values sym (acons tree sym bindings)))))))))
        

With this function we can translate an expression like:

(or (and "a" "b") (and (or "c" "d") (or "a" "b")))
        

Into this expression:

(OR (AND #:G1 #:G2) (AND (OR #:G3 #:G4) (OR #:G1 #:G2)))
        

and this list of bindings:

(("d" . #:G4) ("c" . #:G3) ("b" . #:G2) ("a" . #:G1))
        

Now we just need to use those two values to build up a bit of Lisp. Gary’s solution was to build up an expression that he could EVAL. But it’s better to generate a LAMBDA expression because then we can compile it. Here’s the function:1

(defun make-lambda-expression (expr)
  (multiple-value-bind (tree bindings) (translate expr)
    (let ((string (gensym)))
      `(lambda (,string) 
         (let (,@(loop for (word . sym) in bindings collect
                      `(,sym (find-word-in-string ,word ,string))))
           ,tree)))))
        

If we pass the same expression to this function we get the following lambda expression back.

(LAMBDA (#:G9)
  (LET ((#:G8 (FIND-WORD-IN-STRING "d" #:G9))
        (#:G7 (FIND-WORD-IN-STRING "c" #:G9))
        (#:G6 (FIND-WORD-IN-STRING "b" #:G9))
        (#:G5 (FIND-WORD-IN-STRING "a" #:G9)))
    (OR (AND #:G5 #:G6) (AND (OR #:G7 #:G8) (OR #:G5 #:G6)))))
        

We could use FUNCALL to evaluate this expression which would at least get us out of using EVAL.2 But the real advantage of this approach is that we can compile this expression. Since Gary said he wanted to find all the strings in his database that match a given expression, he’s probably going to be evaluating his query once per string in his database. In that case it’s probably worth it to take a small up front hit in order to speed up the execution of the query since we’re going to be executing it many times. Luckily compiling a lambda expression is about as trivial as EVALing any other expression:

(defun compile-expression (expr)
  (compile nil (make-lambda-expression expr)))
        

This function, fed a query expression, returns a compiled function that takes a single string argument and returns true if the query expression matches and false if not. On Lisps with native compilers the returned function will be compiled down to machine code just the same as if we had written it by hand in our source code. We can FUNCALL this function such as in this code that collects all the strings returned by a cursor function that match the query expression:

(defun query-strings (query database)
  (loop with predicate = (compile-expression query)
     with cursor = (string-cursor database)
     for string = (next-string cursor)
     while string
     when (funcall predicate string) collect string))
        

We can also use the query function with all of Lisp’s higher-order-functions, such as REMOVE-IF-NOT:

(remove-if-not (compile-expression query) *all-strings*)
        

Now, one could argue that there’s a whole heck of a lot of difference between using EVAL and wrapping something in a lambda expression and compiling it — in both cases you can generate, and then evaluate, arbitrary Lisp code. But there is an important difference, namely that EVAL just evaluates — it takes some data and interprets it as Lisp and gives you an answer straight away whereas compiling a lambda expression gives you a function, something that can interact with the rest of your code, as an argument to higher-order functions, and so on. Or, if you don’t buy that, at least you avoid breaking the no EVAL rule.

Update: It hit me as I was brushing my teeth that while nicely avoiding EVAL, my first solution had a big problem — because all the FIND-WORD-IN-STRING calls are done in the LET before the boolean expression is evaluated we lose all the advantage of AND and OR’s short-circuiting behavior. That is, the generated code searches for all the strings and then combines the results of all those searches. Much better (and simpler) would be to implement TRANSLATE and MAKE-LAMBDA-EXPRESSION this way:

(defun translate (tree &optional (stringvar (gensym)))
  (typecase tree
    (cons
     (cons (translate (car tree) stringvar) (translate (cdr tree) stringvar)))
    (symbol tree)
    (string `(find-word-in-string ,tree ,stringvar))))

(defun make-lambda-expression (expr)
  (let ((string (gensym)))
    `(lambda (,string) ,(translate expr string))))
        

This has the slight disadvantage that if the same literal string appears in the pattern more than once, we will potentially search for it more than once. But that’s probably much less of an issue than the problem this code fixes. Obviously if we cared to, we could generate code that caches searches once they are done to get the best of both worlds. But I’ll leave that as an exercise for the reader.


1. This function generates calls to a helper function FIND-WORD-IN-STRING. Gary’s version was somewhat more complex but for the purposes of illustration this definition should do:

(defun find-word-in-string (word string)
  (search word string :test #'char-equal))
                

2. Gary’s solution was haired up a bit because he didn’t simply generate a LET form to EVAL but instead generated just the boolean expression and then wrapped the call to EVAL in a PROGV to establish dynamic bindings at run-time. Which, while sort of clever, was another sign from the gods that he had gone down a wrong path somewhere.

Practical Common Lisp going into 3rd printing

May 26, 2007

I just found out that Apress has decided it’s time for a third printing of Practical Common Lisp. If I recall correctly, the first printing was 5,000 copies, the second 3,000 more. New printings are called for when the publisher thinks they’re going to run out of copies to sell to distributors so this must mean I’m not crazy to dream of someday having a 10k-copies-sold party.

This also means now would be a good time, if you’ve read the book and noticed any errors that you’ve not emailed me about, to send a note. If you put “pcl errata” in the subject it’ll make my life a bit easier. Note, however, that this is just a new printing not a new edition. For a new printing we just fix minor typos and so forth so now is not the time to tell me that there should really be a chapter about how to connect to RDBMSes or what have you.


Follow

Get every new post delivered to your Inbox.