Space Station Lambda

Among the different ways to tackle iterative processes I consider to be the higher-order function route the one I use most often. Especially in conjunction with function composition and list predicates it makes great filtering-style code.

A problem that came up several times is interrupting the list processing at an arbitrary point. For example, how do I stop MAPCAR at the third item if I see it fit? Something like that:

(let ((i 0))
  (mapcar (lambda (x)
            (when (eql (incf i) 3)
              (STOP-HERE)))
    '(a b c d)))

Sometimes, one can take alternative routes using FIND or other functions. And there’s always LOOP, DOLIST, recursion and other solutions; after all we’re working in a language that really implements the “there’s more than one way to do it” paradigm.

Using TAGBODY and GO:

(tagbody (mapcar (lambda (x) (go X)) '(a b c)) X)

Using BLOCK/RETURN-FROM:

(block X (mapcar (lambda (x) (return-from X)) ‘(a b c)))

I originally posted another version using CATCH/THROW, but as pointed out in the comments this wasn’t all well for several reasons.

Delimited continuations with CL-CONT unfortunately won’t work.

A good alternative solution would be writing your own version of MAPCAR; this has the advantage of being able to return the partially processed list. But there’s the disadvantage of having to rewrite the whole family of mapping functions, though, so for quick prototyping or occasional usage I prefer the above solution.

If you have other neat solutions or see problems with this approach, please leave a comment.

Comments(16)

Printing the argument and return values of a set of nested or sequential expressions is a common debugging tactic.

In Common Lisp we can make use of a recursive macro instead of manually inserting printing statements. Specifically, we want our macro (let’s call it WALK for want of a better name since it’s a simple code walker) to print all the return values it encounters along its way:

(walk (list (+ 5 (* 3 3))
            "Welcome to earth, third rock from the sun!"))
 
(* 3 3) => 9
(+ 5 (* 3 3)) => 14
(LIST (+ 5 (* 3 3)) "Welcome to earth, third rock from the sun!")
  => (14 "Welcome to earth, third rock from the sun!")

The following macro does that job.

(defmacro walk (form)
    (etypecase form
       (atom ; terminating base case
         form)
       (cons
         `(let ((result (,(first form) ,@(mapcar (lambda (arg) `(walk ,arg))
                                               (rest form)))))
            (format t "~S => ~S~%" ',form result)
            result))))

Modifying the output so it prints

(* 3 3) => 9
(+ 5 9) => 14
(LIST 14 "Welcome to earth, third rock from the sun!")
  => (14 "Welcome to earth, third rock from the sun!")

instead is left as an exercise to the reader (bad puns come easily in English…), as is the addition of an optional DEPTH argument.

It would also be nice to make use of the pretty printer for appropriate indentation, but I have severe problems grokking it, so maybe someone familiar with this facility can help.

In other programming languages the same problem requires a bit more effort.

Comments(6)

The Daily Vim blog shows a bunch of ways to replace the time-consuming escape key with a faster binding. You can try all of them at once, if you’re not sure what suits you best.

Unfortunately the most attractive method — remapping CapsLock — is already assigned to the window manager on my box, so this one wasn’t really an option for me.

Comments(0)

This post has two parts, a social and a technical one. Scroll down to see the technical one if you don’t care about the former.

For me, Common Lisp offers two fundamental modes of programming, often mixing together.

The first mode is serious software development (by which I’m attempting to pay my rent right now). Everything needs to work here. Thread safety, correctness, safety over speed, enough speed nonetheless, pragmatism, … well, I guess you know the score.

The second mode is exploration and experiments. My last two posts on the randomization of sequences were just that, and collaboratively that. After all, my blog is neither a newspaper nor a research journal. Unfortunately some readers seem to have misunderstood this. I suppose this is partly owing to my usual portion of kidding hyperbole, like my stating that I were “allergic to consing” and had found an exceptionally “good solution”.

So, to make it clear: both of these posts were not about presenting a well-tested algorithm ready for public copy-and-paste, but something to think about — for you and for me.
Tagging the list’s elements with a random id beforehand, as in the solutions Paul and Phil came up with, is a very nice, solid and working solution. Unfortunately this one is also so straight-forward that it hasn’t much potential for intellectual stimulation (at least not for me), and that’s why I decided to pursue the idea with hash tables and memoization further.

Now for the technical part of this wrap-up: SEQRND works for all objects where EQ reliably points out differences. This definitely excludes literals (the will be constant-folded more often than not) but includes CLOS objects. SEQRND also was three times faster than Paul’s RANDOM-SHUFFLE on SBCL.

My personal bottom line is: use one of the solid algorithms all the time and rely on Fisher-Yates if you need the speed.

Comments(2)

In my post “Trivial Sequence Shuffling” from yesterday I showed a simple hack to shuffle a sequence.

For your convenience:

(defun seqrnd (seq)
  "Randomize the elements of a sequence. Destructive on SEQ."
  (sort seq #'> :key (lambda (x) (random 1.0))))

The only downside to this algorithm, I claimed, is its complexity, which is worse than that of a specialized sorting algorithm.

However that is not the only problem with it. The ensuing discussion (thanks for your comments, guys!) showed that I didn’t notice an allowance made by the standard: the :KEY function might be called more than once, and implementations seem to make use of this. And while it is allowed to return different keys for the same element (i.e. let the :KEY function be not a proper function, but a plain relation), the result will not be a discrete uniform random distribution, but a biased distribution depending on the intricacies of the sorting procedure.

In this post I’d like to show the alternatives proposed and my own amendment, which extends my original flawed solution.

Peter de Wachter proposed:

(defun better-shuffle (seq)
  (let ((tagged (mapcar (lambda (x) (cons (random 1.0) x)) seq)))
    (mapcar 'cdr (sort tagged #'> :key 'car))))

It’s not that I don’t like it at all (after all it’s a nice case study in functional programming!), but I’m allergic to the consing it produces. I also feel that it overcomplicates things.

Paul Khuong wrote something similar which looks a bit more elegant to me:

(defun random-shuffle (sequence)
  (map-into sequence #'car
            (sort (map 'vector (lambda (x)
                                 (cons x (random 1d0)))
                       sequence)
                  #'< :key #'cdr)))

The other approach (in Scheme) came from Phil Bewig (hope I got the indent right):

(define (shuffle x)
  (do ((v (list->vector x)) (n (length x) (- n 1)))
    ((zero? n) (vector->list v))
    (let* ((r (random n)) (t (vector-ref v r)))
      (vector-set! v r (vector-ref v (- n 1)))
      (vector-set! v (- n 1) t))))

Ah, sorry Phil, but that's not my kind of style :) Too much imperative stuff here, a data conversion and a DO loop. Somehow the name of Rube Goldberg comes to my mind...

The <Good Solution> (alluding to Mark Tarver's Qi blurb) involves a thing as natural as anything to a Lisp (and I include Scheme here) programmer: memoization.

While memoization, i.e. caching function results, is most often used in a performance context, we might also apply it here to make our function always return the same result for an object, thus imposing a total ordering on the list:

(defvar *random-id-ht* nil)
 
(defun initialize-memo ()
  (setf *random-id-ht* (make-hash-table :test #'eq)))
 
(defun consistent-random-id (obj)
  (multiple-value-bind (val found-p) (gethash obj *random-id-ht*)
    (if found-p val
      (setf (gethash obj *random-id-ht*)
            (random 1.0)))))
 
(defun seqrnd (seq)
  "Randomize the elements of a sequence. Destructive on SEQ."
  (initialize-memo) ; need to clear between runs
  (sort seq #'> :key (lambda (x) (consistent-random-id x))))

This is a scaled down version of a memoizer; you probably don't want to do this at home. A generalized memoizer takes about two screenfuls (talking 24 lines here). You can find generalized memoizers everywhere on the net, for example in the Cells utility library for Common Lisp.

One might argue that this solution is too complicated. I hold against that that memoization should be present in every serious functional programmer's toolbox, so it boils down to the function itself -- which is only marginally longer than the first attempt.

Comments(11)

I’m currently visiting my family, and an inevitable part of it is playing some good old games with my brothers. The hardware situation here is a bit peculiar, though; I need to play on two different machines, and only one of them has speakers.

Those speakers are built-in, too, so I can’t change them easily.
No problem, there’s ESD, right? Well. The Enlightened Sound Daemon might have deserved its name when it was released, but since then a bunch of years have passed and it didn’t show acceptable quality when I tried it here.

PulseAudio to the rescue! This modern solution runs even on Microsoft Windows (although not on the 9x series, it seems), has dead simple GUI tools and is the best thing since sliced bread. A real sports car.
Except, for some unknown reason, I couldn’t get it to work on one of the machines in question. No sliced bread for me, I guess.

But then I came across a real slick solution in the ALSA wiki: a sound server using Netcat and the out-of-the-box ALSA utilities aplay and arecord.

Setup is as simple as:

# on the server:
nc -u -l -p 9999 | aplay
 
# on the client
arecord -t wav -f cd | nc -u SERVER 9999

Now just set your recording source via alsamixer -Vc to “Mix” and adjust the output volume levels on client, server and speaker.

Made me slap my head ’cause I didn’t think of it myself.

Comments(0)

Here’s a quickie for the newbies among you:

(defun seqrnd (seq)
  "Randomize the elements of a sequence. Destructive on SEQ."
  (sort seq #'> :key (lambda (x) (random 1.0))))
 
(seqrnd (copy-seq "abcd")) ; need to copy the literal for the destructive operation
-> "dacb"

This also shifts the efficiency of the shuffle to the efficiency of your implementation’s sorting algorithm. Look for the Fisher-Yates shuffling algorithm if you’re really, really tight on resources; it does something akin to Bubble Sort to solve the problem.

Comments(17)