A Currying Pipeline November 20th, 2010
Patrick Stein

I have been reading a great deal about Haskell and thinking a great deal about a networked Lisp game that I intend to work on soon. For the Lisp project, I will need to serialize and unserialize packets to send them over the network. I re-read the chapter on parsing binary files in Practical Common Lisp and started to think about how I could make readers and writers that worked on buffers. Thanks to the Haskell influence, I was also trying to do this serialization without side effects.

The Goal

I wanted to accomplish something like this without all of the SETF action and verbiage:

(let (vv)
  (setf vv (serialize 'real xx vv))
  (setf vv (serialize 'real yy vv))
  (setf vv (serialize 'real zz vv))
  vv)

The First Attempt

Well, also thanks to Haskell, my instinct was to make a CURRY-PIPELINE macro that gets called something like this:

(curry-pipeline nil
  (serialize 'real xx)
  (serialize 'real yy)
  (serialize 'real zz))

and expands into something like this:

(serialize 'real zz (serialize 'real yy (serialize 'real xx nil)))

Unfortunately, this changes the order of evaluation of xx, yy, and zz entirely. So, this was suboptimal. It also involved a fifteen-line macro with macro recursion and two conditionals.

Slightly Cleaner

My next attempt was about a ten-line macro with one conditional that turned it into a bunch of nested LET statements.

(let ((#:V-1 nil))
  (let ((#:V-1 (serialize 'real xx #:V-1)))
    (let (#:V-1 (serialize 'real yy #:V-1)))
      (let (#:V-1 (serialize 'real zz #:V-1)))
        #:V-1))))

Cleaner Still

Then, I realized that most of my simple examples would be simplest if I curried into the first argument instead of the last. (In fact, it would have even fixed my order of evaluation problem in the initial version.) And, I realized that I could abandon the nested LET if I used a LET*. Now, I have a six-line macro that I really like.

(defmacro curry-pipeline (initial &body body)
  (let ((vv (gensym "VARIABLE-")))
    (labels ((curry-and-store (line)
               `(,vv (,(first line) ,vv ,@(rest line)))))
      `(let* ((,vv ,initial)
              ,@(mapcar #'curry-and-store body))
         ,vv))))

So, here is an example that does one of those grade school magic tricks. Pick a number, multiply by five, add six, multiply by four, add nine, and multiply by five. Tell me the answer. I subtract 165 and divide by one hundred to tell you your original number.

(defun magic-trick (n)
  (let ((rube (curry-pipeline n
                (* 5)
                (+ 6)
                (* 4)
                (+ 9)
                (* 5))))
    (curry-pipeline rube
      (- 165)
      (/ 100))))

Back to the Original Problem

Now, my serialize functions can simply take a buffer and return a buffer which is the concatenation of the input buffer and the bytes required to encode the given value. The unserialize is not as nice since I will have to return both a buffer and a value, but I am sure I can work something out using a CONS as an accumulator. And, heck, it is going to kill my performance anyway if I really copy the buffer every time I want to add another item to it. I am probably going to ditch the functional aspect anyway. *shrug*

A New Tack

If you don’t like currying or need to have more control over where the accumulator goes in each step of the chain, you can still get the same kind of chaining if you require a declaration of the variable. And, it simplifies the macro:

(defmacro let-pipeline ((var initial) &body body)
  `(let* ((,var ,initial)
          ,@(mapcar #'(lambda (line) `(,var ,line)) body))
     ,var))

(defun magic-trick (n)
  (let ((rube (let-pipeline (r n)
                (* 5 r)
                (+ 6 r)
                (* 4 r)
                (+ 9 r)
                (* 5 r))))
    (let-pipeline (a rube)
      (- a 165)
      (/ a 100))))

From there, it is not too big of a leap to allow MULTIPLE-VALUE-BIND instead. To accomplish the unserialize, as I mentioned, I will need to track multiple values. I am now down to a four line macro:

(defmacro mv-pipeline ((vars call &rest rest-pipeline) &body body)
  `(multiple-value-bind ,vars ,call
     ,(if rest-pipeline
          `(mv-pipeline ,rest-pipeline ,@body)
          `(progn ,@body))))

Here is an easy to follow example that returns the first five Fibonacci numbers:

(mv-pipeline ((f0 f1) (values 0 1)
              (f2) (+ f1 f0)
              (f3) (+ f2 f1)
              (f4) (+ f3 f2))
  (list f0 f1 f2 f3 f4))

Now, my unserialize case might look something like this:

(defmethod unserialize ((type (eq 'vector)) buffer)
  (mv-pipeline ((xx buffer) (unserialize 'real buffer)
                (yy buffer) (unserialize 'real buffer)
                (zz buffer) (unserialize 'real buffer))
    (values (vector xx yy zz) buffer)))

Conclusion

Luckily, I am not paying myself based on lines of code per hour. Almost every time I have done more work, I have reduced the number of lines of code. I am reminded of this quote from Blaise Pascal: I have made this letter longer, because I have not had the time to make it shorter.

Won An “Award” November 19th, 2010
Patrick Stein

Early this year, I wrote a small start of a game for a 7-Day Lisp Programming Contest. I just got some hilarious please, give us information about you we can sell to third parties spam saying that my product has been granted the Famous Software Award.

There is an (apparently apocryphal) story that the World Series of Baseball was not meant to imply something global, but rather was to reflect that it was sponsored by the newspaper The New York World. In the present case, however, there is no implication that my software is famous. The company sponsoring the award has the word famous in its name.

Anyhow, I found it quite amusing that my half-a-game experiment with a one-button interface was being recognized for:

The Famous Software Award has been initiated by [Spammer’s URL Here] to recognize Famous Software, which come up with innovative and efficient ways to reflect the best relationship with users assuring their satisfacation.

The broken English there makes it tough to discern if they’re claiming that my famous software assures user satisfaction or if the Spammer company does. Either way, Go, me! 🙂

Installed Quicklisp November 17th, 2010
Patrick Stein

I installed Quicklisp tonight. It was super-simple. In about 1/2 an hour, I got slime up and running and installed all of the packages that I regularly use.

It installs itself in a quicklisp/ subdirectory of your home directory. I didn’t really want it cluttering up my normal ls output, so I moved it to .quicklisp/ and updated my .sbclrc to refer to this new path. It had to recompile everything when I loaded it next, but it handled it gracefully.

It took me less than a minute to get slime set up. This is an improvement of about five hours and fifty-nine minutes over the previous time that I set up slime.

I definitely give my two thumbs up for Quicklisp.

Thanks, Zach!

Making Fun Algebra Problems Funner October 29th, 2010
Patrick Stein

A month ago, a friend posted the following problem on Facebook. I just noticed it this week.
Drawing of a circle with radius r sitting on a line with two squares wedged against it. One square has side-length 1, the other side-length 2. There are six units between the squares.
The goal is to find the exact length of the radius r.

I love this kind of math problem.  It has a bunch of features that make it a great, toy math problem.

  • It looks like it’s going to be easy, but at the same time seems at a glance to not have enough information
  • It looks like a geometry problem but only requires that you know:
    • All radii of a circle have the same length
    • A radius to a point where a tangent line touches the circle is perpendicular to that tangent line
  • It requires only very basic algebra:
    • Pythagorean theorem
    • Solving quadratics
  • The numbers in the problem are small, non-zero integers

I spent the next 25 minutes and six pieces of paper working the problem. About 20% of the time that I spent was rechecking my work. Why did I bother rechecking my work on a toy problem?

Warning: Spoilers ahead. If you like this kind of problem, stop reading now and play with it first.

The problem with the problem

This problem failed to satisfy one of my other criterion for great, toy puzzle problems.

  • The answer is a small natural number (or the current year)

I am notorious for messing up signs when doing large algebra calculations. I had to check and recheck all of my work to make sure that I hadn’t done 5x - (3x - 2) and gotten 2x - 2 somewhere. If I had come up with an integer value for r, I’d have been done. Instead, the answer involved a half-integer plus a multiple of \sqrt{74}.

What? \sqrt{74}?!? Raise your hand if you’ve ever seen that written anywhere before this problem.

That’s what I thought.

So, I spent the next hour looking for a different set of numbers to put in for 1, 2, and 6 so that the radius r would come out to an integer. My approach was Brownian, at best. I threw Pythagorean triples at a wall until one stuck.

The sticky triple left me with [50,200,360] to put in place of [1,2,6]. So, I put the problem down for awhile.

The next time that I was in the car, I realized that the radius for the sticky triple was less than 200. That meant that the larger box was touching the upper half of the circle instead of the lower half. The circle had to overlap the box.

So, I was back to the drawing board. Of course, I’d have been back to the drawing board at some point anyway because that sticky triple violated both of my small numbers criteria.

Warning: If you want to play around with finding a set of numbers that work, do it before you read the following. There are even more spoilers ahead.

Infinitely many combinations to get an integer radius

When I next sat down to play (pronounced: /OBSESS/) with this problem, I quickly hit upon the following way to take any Pythagorean triple (a, b, c) and make a version of the above puzzle where the radius r is an integer.
Same sort of diagram as above except radius is c, boxes are height c-b and c-a, and some (a,b,c) triangles are drawn in

In fact, using a 3-4-5 triangle, it is obvious that had the distance between the blocks in the original problem been 7 instead of 6, the radius would have been a small natural number.

Now. Now, I had infinitely many ways to construct this problem so that the radius was an integer. But, did I have all of the ways?

All your configuration are belong to us

When looking at that last diagram, the first question that comes to mind (for me) is: Do I really need to use the same Pythagorean triple on the left and right triangles? The answer, of course, is No.

If I have two Pythagorean triples (a_1,b_1,c_1) and (a_2,b_2,c_2) and d is any (positive) divisor of both c_1 and c_2, then I can start with an a_1-b_1-c_1 triangle on the left and an a_2-b_2-c_2 triangle on the right. I can then scale up the left triangle by c_2/d and scale the right triangle up by c_1/d. Now, both triangles have the same hypotenuse.

This means that if the left block has height c_2 (c_1 - b_1)/d, the right block has height c_1(c_2 - b_2)/d, the distance between the two blocks is (c_2 a_1 + c_1 a_2)/d, and the resulting circle has radius c_1c_2/d.
A more general version of the previous diagrams

Does this cover all of the solutions? Could I possibly have non-integer a_1 and a_2 such that (c_2a_1 + c_1a_2)/d is still integer?

Well, for the problem to be formulated entirely with integers, we certainly need the hypotenuse of the right triangles to be an integer. Further, to make the blocks integer heights then both of the legs of the right triangles along the vertical radius must also be integer. So, if the triangle on the left had hypotenuse r, vertical leg b and horizontal leg a, then we know that a = \sqrt{r^2 - b^2} where both r and b are integers. Thus, a must be the square root of an integer.

It is easy to see that if a were a non-integer rational number, then its square would also be a non-integer rational number. So, either a is integer or it is the irrational square root of an integer.

So, can a be an irrational number? If a were an irrational number, then the horizontal leg of the other triangle would have to be some integer n minus the irrational a for the distance between the two blocks to be an integer. Let’s say the vertical leg of the triangle on the right is \beta. Just like b in the first triangle, \beta must be an integer. We also know that (n-a)^2 = r^2 - \beta^2. This, in turn, means that a = (\beta^2 + n^2 + a^2 - r^2) / (2n). The right hand side is clearly rational, so a could not have been irrational.

So, there you have it: all of the numbers that make this problem have all integers on the drawing and an integer answer.

Missing Lisping June 30th, 2010
Patrick Stein

I hope that by later in the month I will have time to participate in the 2010 International Lisp Games Expo.

Updates In Email

Email:

RSS Feeds

l