Who Won? May 28th, 2015
Patrick Stein

The web comic XKCD recently published the following tournament bracket featuring match-ups like ORSON WELLS vs. H.G. WELLS and VAN HALEN vs. VAN MORRISON vs. VAN WILDER.

XKCD Tournament

So, who won? It seems probable to me that XKCD’s author Randall Munroe has in mind some way to decide these matches. If he published how the matches were to be decided, I missed it. However, based on some previous XKCD comics like Geohashing and Externalities, I think it’s a safe guess that it involves hashing.

So, how could we decide this? We could take the hash of each name and then in each match, the largest hash value wins. That, however, has the unfortunate side effect that the winner of the tournament would be the same regardless of the organization of the brackets.

I opted to decide the match between OSCAR DE LA RENTA and OSCAR DE LA HOYA by taking the SHA3-512 hash of the strings OSCAR DE LA RENTA vs. OSCAR DE LA HOYA and OSCAR DE LA HOYA vs. OSCAR DE LA RENTA. The winner is the one whose name appeared first in the string with the smallest hash value. For three and four person contests, I used all permutations of the players involved (separated by vs. ).

The winner? RYAN ADAMS beat out BILL PAXTON in the final.

The code for this project was a breeze thanks to #'ALEXANDRIA:MAP-PERMUTATIONS and my TRACK-BEST library. Here is a the meat of the whole thing which uses an evaluation function (here, it’s SHA3-512 of the vs. separated player list) and a way to compare the evaluations (here, a simple #'ARRAY-LESSP) and runs through all of the players.

(labels ((rank-one-match (players depth)
           (track-best:track (first players)
                             (funcall eval-permutation players depth)))

         (find-winner (players depth)
           (track-best:with-track-best (:order-by-fn compare-permutations)
             (alexandria:map-permutations (lambda (players)
                                            (rank-one-match players depth))
                                          players))))
  ...)

Here is the full source file for the tournament: tourney.lisp. Here is a text description of the whole tournament. And, here is a graphic with the outcomes of all of the matches.

final-bracket

Struggling to Keep the Faith April 11th, 2015
Patrick Stein

Six years ago, I wrote about how the choice of programming language dramatically affects the way in which I write code. In that post from six years ago, I said:

In Lisp, I will pull something out into a separate function if it makes the current function more self-contained, more one idea. In C++, I will only pull something out into a separate function if I need the same functionality in multiple places.

At the moment, I’m getting paid to write in C++ for the first time in two years (technically, I suppose I did write some small C++ sample code in my previous job, too). I am struggling at the moment to make my C++ functions as small as I would have made them if I were writing in Lisp.

There are obvious barriers to this imposed by C++. While one of the projects at my work is converting a large swath of code to C++11, my project is still stuck on C++98. This means that I can’t use lambda functions, auto, or for-each style for loops and that I can’t get away with letting the compiler figure out my template types in almost any situation.

For instance, I have one function that is about twenty lines of comments and ten lines of code comprising exactly three statements. Three statements took ten lines of code because when you want to use a pointer to a member function in a std::count_if call, you need to jump through about a hundred characters of declarations and syntax to turn the pointer to a member function of one argument into a regular function of two arguments (using std::mem_fun1_t) and another pile of characters to turn it into a regular function of one parameter again (using std::bind1st). And, I spent nearly an hour trying to glark the type I’d have had to declare in one of the intermediate steps to turn those three statements into four instead. I gave up.

bool MyClass::attemptToFrob( item_t& item )
{
  return item.frob( _frobRetryCount, _frobTimeoutValue );
}

bool MyClass::frobAllOfMyItems()
{
  return performItemOperationOnAllItems( &MyClass::attemptToFrob );
}

bool MyClass::performItemOperationOnAllItems(
                bool (MyClass::*op)(item_t&)
              )
{
  std::mem_fun1_t<bool,MyClass,item_t> binOp(op);
  unsigned int successes = std::count_if( _items.begin(),
                                          _items.end(),
                                          std::bind1st( binOp, this ) );
  return ( _items.size() == successes );
}

In C++11, I’d have written the function as two statements, only one of which had to span more than one line to stay under 80 columns. In C++0X, I’d at least have been able to auto an intermediate statement to hold the result of std::bind1st that I couldn’t manage to satisfy myself.

I really believe that trying to keep the functions down to three or four lines with at most one conditional is a goal that goes a long way toward readability. But, man, it sucks for writability when you’re stuck in a strongly-typed language with a compiler that isn’t at all interested in helping you out with that.

And, a pet peeve here while I’m already ranting about C++…. Am I right in believing that neither C++98, C++0X, C++11, or C++14 have any way to iterate over the keys of a std::map or to wrap a function of one argument that takes a pair and just uses the first half of the pair to invoke the original function? Something like this:

template <class R, class T, class U>
class call1st {
public:
  call1st( R (*fn)(T) ) : _fn(fn) {};
  R operator ( std::pair<T,U>& p ) { return (_fn)(p.first); };
private:
  R (*_fn)(T);
};

Most of why I would want this would be more clear with lambdas instead. But, if there is still going to be crap in the language like std::mem_fun1_ref_t and such, why is there still no functional way (in the #include <functional> sense) to get to the members of a pair? Or, I am just missing something obvious?

Trying Clojure again? March 26th, 2015
Patrick Stein

EDIT: Indeed, as people on Reddit pointed out, installing Lein is simply downloading a script and running it. Installing CIDER from MELPA was also easy. The two, however, aren’t completely compatible at the moment because CIDER from MELPA wants nREPL 0.2.7 at least and Lein only pulls in 0.2.6 (even though, I believe the current is 0.2.10).

It has been five years since I last tried Clojure. I feel like I should try it again.

I don’t want to beat my head against Leiningen for even ten minutes this time. Is there some way to reasonably use Emacs + Clojure without have to install and configure CLASSPATHS and Mavens and Ants and JDKs?

It seems SWANK-CLOJURE has been deprecated in favor of CIDER. The CIDER doc says how to configure Leiningen or Boot for use with CIDER. Is there some way that I can avoid Leingingen and Boot? Or some way that I can click one ‘Install’ button and have Leiningen and Boot work?

Code That Tells You Why November 13th, 2014
Patrick Stein

A 2006 article by Jeff Atwood titled Code Tells You How, Comments Tell You Why showed up on reddit/r/programming today.

It makes a good point. However, it got me thinking that for cases like the binary-search example in the article, it might be nice to see all of the alternatives in the code and easily be able to switch between them.

One way to accomplish this in Lisp is to abuse the #+ and #- reader macros:

(defun sum-i^2 (n)
  #+i-wanted-to-do-this
  (loop :for i :to n :summing (* i i))

  #+my-first-attempt-was-something-like-this
  (do ((i 0 (1+ i))
       (sum 0 (+ sum (* i i))))
      ((> i n) sum))

  #+but-i-could-not-do-that-because
  "Some people find a do-loop to hard to read
    (and 'too' too hard to spell, apparently)."

  #-now-i-know-better-and-can-do-this
  (/ (* n (1+ n) (1+ (+ n n)) 6))

This is less than ideal for a number of reasons, including: one needs to make sure to pick “feature” names that won’t actually ever get turned on, the sense of + and - seem backwards here, and switching to a different alternative requires editing two places.

Another Lisp alternative is to abuse the case form:

(defun sum-i^2 (n)
  (case :now-i-know-better-and-can-do-this
    (:i-wanted-to-do-this
     (loop :for i :to n :summing (* i i)))

    (:my-first-attempt-was-something-like-this
     (do ((i 0 (1+ i))
          (sum 0 (+ sum (* i i))))
         ((> i n) sum)))

    (:but-i-could-not-do-that-because
     "Some people find a do-loop to hard to read
    (and 'too' too hard to spell, apparently).")

    (:now-i-know-better-and-can-do-this
     (/ (* n (1+ n) (1+ (+ n n)) 6)))))

This is better. No one can doubt which alternative is in use. It is only one edit to switch which alternative is used. It still feels pretty hackish to me though.

One can clean it up a bit with some macrology.

(defmacro alternatives (&body clauses)
  (flet ((symbol-is-***-p (sym)
           (and (symbolp sym)
                (string= (symbol-name sym) "***")))
         (final-clause-p (clause)
           (when (listp clause)
             (destructuring-bind (tag &body body) clause
               (when (and (symbolp tag)
                          (member (symbol-name tag)
                                  '("***" "FINAL" "BLESSED")
                                  :test #'string=))
                 body)))))
    (anaphora:acond
      ((member-if #'symbol-is-***-p clauses)
       (let ((clause (first (rest anaphora:it))))
         `(progn
            ,@(rest clause))))

      ((find-if #'final-clause-p clauses)
       `(progn
          ,@(rest anaphora:it)))

      ((last clauses)
       `(prog
          ,@(rest (first anaphora:it)))))))

With this macro, one can now rewrite the sum-i^2 function quite readably:

(defun sum-i^2 (n)
  (alternatives
    (i-wanted-to-do-this
     (loop :for i :to n :summing (* i i)))

    (my-first-attempt-was-something-like-this
     (do ((i 0 (1+ i))
          (sum 0 (+ sum (* i i))))
         ((> i n) sum)))

    (but-i-could-not-do-that-because
     "Some people find a do-loop to hard to read
    (and 'too' too hard to spell, apparently).")

    (now-i-know-better-and-can-do-this
     (/ (* n (1+ n) (1+ (+ n n)) 6)))))

If I wanted to try the my-first-attempt-was-something-like-this clause, I could stick a *** before that clause or change its name to *** or final or blessed, or I could move that clause into the last spot.

There is still an onus on the developer to chose useful alternative names. In most production code, one wants to clean out all of the dead code. On the other hand, during development or for more interactive code bodies, one might prefer to be able to see the exact “How” that goes with the “Why” and easily be able to swap between them.

(Above macro coming in well-documented library form, hopefully this weekend.)

Clozure Common Lisp on the Raspberry Pi April 8th, 2014
Patrick Stein

I finally ordered a Raspberry Pi last week. It arrived yesterday. Last night, I installed the Raspbian (Debian for Raspberry Pi) distro. Then, I followed Rainer Joswig’s excellent instructions on how to get Clozure Common Lisp running on the Raspberry Pi.

The only think that I would add to Rainer’s presentation is that Raspbian didn’t come with m4(1) out of the box, but it is needed when you make all to rebuild Clozure.

Hacks and glory await!

Also, Linux pro-tip: If you are thinking of renaming your only account on the machine, make sure you add the new name to a group with sudo privileges and make sure you get both /etc/passwd and /etc/shadow in the same sudo.

Edit: Rainer correctly points out that his article does say you will need to install m4 if you haven’t already. I just missed it.

RSS Feeds

l