Articles | nklein software

HTML + JS + LISP. Oh My. March 20th, 2012
Patrick Stein

I started a Javascript + HTML application some time back. I decided that I wanted to get some Lisp on. So, it was time to pull out Hunchentoot, CL-WHO, and Parenscript.

It’s been awkward slogging so far. I still don’t have a good user-model of when exactly I need to wrap something in a (cl-who:str ...) or when Parenscript will expand my macro rather than convert it into a function call or how I managed to get the cl-who:*attribute-quote-char* to finally stick for a few REPLs.

The other half of the awkwardness is that I started writing the application in idiomatic javascript with prototype-based objects.

function MyClass () {
this.myfirst = undefined;
this.myarray = [ ];
}

MyClass.prototype.mymethod = function (arg1, arg2) {
this.myfirst = arg1;
this.myarray.push(arg2);
};

This makes for some awkward javascript when converted directly into Parenscript because:

The method mymethod() will try to return the result of Array.push() (which, technically, is fine, but not really the intent of the method).
Almost every statement on the Lisp side ends up wrapping just about everything in (parenscript:chain ...). (Edit: Of course, I discovered right after posting this that the dot is left untouched in the Parenscript symbol conversion, so I can do (this.myarray.push arg2) instead of (parenscript:chain this my array (push arg2)). I’m certainly pleased with the brevity, but it pegs my something’s fishy here, Batman meter.)
I have an aversion to using any package other than COMMON-LISP, so everything is way clunkier than all of the tutorials and examples online.

I think that I’m going to scratch all of the Javascript and Parenscript code that I have right now and start over with a mindset of How would I do this if it were just in Lisp? Now, what extra hoops do I need to get Parenscript to make usable Javascript? rather than How would I do this in Javascript? Oh, and then, how can I make Parenscript say exactly that? And, I may bite the bullet and (use-package ...) both CL-WHO and Parenscript.

The Anti-Cons February 27th, 2012
Patrick Stein

Motivation

I no longer remember what led me to this page of synthetic division implemented in various languages. The author provides a common lisp implementation for taking a list representing the coefficients of a polynomial in one variable $x$ and a number $\alpha$ and returning the result of dividing the polynomial by $(x-\alpha)$ .

The author states: I’m very sure this isn’t considered Lispy and would surely seem like an awkward port from an extremely Algol-like mindset in the eyes of a seasoned Lisper. In the mood for the exercise, I reworked his code snippet into slightly more canonical lisp while leaving the basic structure the same:

(defun synthetic-division (polynomial divisor)
(let* ((result (first polynomial))
(quotient (list result)))
(dolist (coefficient (rest polynomial))
(setf result (* result divisor))
(incf result coefficient)
(push result quotient))
(let ((remainder (pop quotient)))
(list :quotient (nreverse quotient) :remainder remainder))))

From there, I went on to implement it using tail recursion to get rid of the #'setf and #'incf and #'push:

(defun synthetic-division-2 (polynomial divisor)
(labels ((divide (coefficients remainder quotient)
(if coefficients
(divide (rest coefficients)
(+ (* divisor remainder) (first coefficients))
(list* remainder quotient))
(list :quotient (reverse quotient) :remainder remainder))))
(divide (rest polynomial) (first polynomial) nil)))

What I didn’t like about this was the complexity of calling the tail-recursive portion. If I just called it like I wished to (divide polynomial 0 nil) then I ended up with one extra coefficient in the answer. This wouldn’t do.

The Joke

There’s an old joke about a physicist, a biologist, and a mathematician who were having lunch at an outdoor cafÃ©. Just as their food was served, they noticed a couple walk into the house across the street. As they were finishing up their meal, they saw three people walk out of that very same house.

The physicist said, We must have miscounted. Three must have entered before.

The biologist said, They must have pro-created.

The mathematician said, If one more person enters that house, it will again be empty.

The Anti-Cons

What I needed was a more-than-empty list. I needed a negative cons-cell. I needed something to put in place of the nil in (divide polynomial 0 nil) that would annihilate the first thing it was cons-ed to.

I haven’t come up with the right notation to make this clear. It is somewhat like a quasigroup except that there is only one inverse element for all other elements. Let’s denote this annihilator: $\omega$ . Let’s denote list concatenation with $\oplus$ .

Only having one inverse-ish element means we have to give up associativity. For lists $a$ and $b$ , evaluating $(a \oplus \omega) \oplus b$ equals $b$ , but $a \oplus (\omega \oplus b)$ equals $a$ .

Associativity is a small price to pay though for a prettier call to my tail-recursive function, right?

The Basic Operations

For basic operations, I’m going to need the anti-cons itself and a lazy list of an arbitrary number of anti-conses.

(defconstant anti-cons 'anti-cons)

(defclass anti-cons-list ()
((length :initarg :length :reader anti-cons-list-length))
(:default-initargs :length 1))

(defmethod print-object ((obj anti-cons-list) stream)
(print-unreadable-object (obj stream)
(prin1 (loop :for ii :from 1 :to (anti-cons-list-length obj)
:collecting 'anti-cons)
stream)))

Then, I’m going to make some macros to define generic functions named by adding a minus-sign to the end of a Common Lisp function. The default implementation will simply be the common-lisp function.

(defmacro defun- (name (&rest args) &body methods)
(let ((name- (intern (concatenate 'string (symbol-name name) "-"))))
`(defgeneric ,name- (,@args)
(:method (,@args) (,name ,@args))
,@methods)))

I’m even going to go one step further for single-argument functions where I want to override the body for my lazy list of anti-conses using a single form for the body:

(defmacro defun1- (name (arg) a-list-form &body body)
`(defun- ,name (,arg)
(:method ((,arg anti-cons-list)) ,a-list-form)
,@body))

I need #'cons- to set the stage. I need to be able to cons an anti-cons with a normal list. I need to be able to cons an anti-cons with a list of anti-conses. And, I need to be able to cons something other than an anti-cons with a list of anti-conses.

(defun- cons (a b)
(:method ((a (eql 'anti-cons)) (b list))
(if (null b)
(make-instance 'anti-cons-list)
(cdr b)))

(:method ((a (eql 'anti-cons)) (b anti-cons-list))
(make-instance 'anti-cons-list :length (1+ (anti-cons-list-length b))))

(:method (a (b anti-cons-list))
(let ((b-len (anti-cons-list-length b)))
(when (> b-len 1)
(make-instance 'anti-cons-list :length (1- b-len))))))

Now, I can go on to define some simple functions that can take either anti-cons lists or regular Common Lisp lists.

(defun1- length (a) (- (anti-cons-list-length a))

(defun1- car (a) :anti-cons)

(defun1- cdr (a)
(let ((a-len (anti-cons-list-length a)))
(when (> a-len 1)
(make-instance 'anti-cons-list :length (1- a-len)))))

(defun1- cadr (a) (when (> (anti-cons-list-length a) 1) :anti-cons))
(defun1- caddr (a) (when (> (anti-cons-list-length a) 2) :anti-cons))

To give a feel for how this all fits together, here’s a little interactive session:

ANTI-CONS> (cons- anti-cons nil)
#<(ANTI-CONS)>

ANTI-CONS> (cons- anti-cons *)
#<(ANTI-CONS ANTI-CONS)>

ANTI-CONS> (cons- :a *)
#<(ANTI-CONS)>

ANTI-CONS> (length- *)
-1

Denouement

Only forty or fifty lines of code to go from:

(divide (rest polynomial) (first polynomial) nil)

To this:

(divide polynomial 0 (cons anti-cons nil))

Definitely worth it.

My Favorite Macro Patterns February 17th, 2012
Patrick Stein

I read Jorge Tavares’s article on Macro Patterns a few days ago.Â I was thinking about replying to mention a few of my favorites:

The with- pattern which makes sure a special variable is bound for the body and makes sure the tied resources are released at the end of the block.
Macros which collect content (usually into a special variable) so they can do something with the content at the end of the close of the macro.

Then, I was working on something tonight when I re-discovered a favorite pattern that I’d forgotten about: Putting multiple wrappers on the same body.

I am working on an HTML+JavaScript+CSS project. In the end, I need static files. But, I thought I would use the opportunity to really experience CL-Who, Parenscript, and CSS-Lite.

I have now made a macro called define-web-file which takes a CL-Who or Parenscript body and wraps it up as both a Hunchentoot handler and a write-to-file wrapper. Now, I can test interactively with Hunchentoot and generate the whole web application when I’m ready.

Dusting off my Growl Library December 21st, 2011
Patrick Stein

I’ve spent the last few hours dusting off my Common Lisp Growl client library. The last time I worked on it was before the Mac Growl Application supported GNTP (Growl Notification Transport Protocol).

Today, working on it, I’m not quite sure what’s up, but I am not succeeding in communicating with the server using encryption. I’ll have to look more closely. Last time that I worked on it, I extended Ironclad, but I never got those changes pushed fully into Ironclad’s main line. But, I think I’m using the same version of Ironclad that I was using when I tested against the Windows Growl Application. *shrug*

I’ve also run into a snag with the Callbacks. Essentially, your Lisp program could get a callback when the user has clicked on your Growl notification. This actually works except for the fact that I am calling READ-SEQUENCE into a buffer that is longer than the message. The server, I believe, is supposed to close the socket after the callback. But, it does not. So, I am stuck waiting for more bytes that will never come.

Now, I either have to do one of the following:

refactor it to use READ-LINE instead
switch from using USocket to using IOLib (and hope that :dont-wait works as expected)
extend USocket to support SOCKET-RECEIVE even on TCP sockets

Anyone have a preference?

If it quacks like a parabola… September 21st, 2011
Patrick Stein

I am working on a game idea that involves (special) relativistic mechanics instead of classical mechanics. Working out the details that I needed was easy enough if I assumed that:

ships had a maximum speed at which they could move relative to my base frame
ships could instantly go from stopped to maximum speed or vice-versa

I didn’t like those assumptions at all. So, I started playing with the equations for relativity. In classical mechanics, the rate-of-change of velocity equals the force you’re applying divided by your mass: $\frac{dv}{dt} = \frac{F}{m}$ .

In special relativity, your mass increases with velocity. So, that equation becomes: $\frac{d\left(\frac{v}{\sqrt{1-v^2}}\right)}{dt} = \frac{F}{m_0}$ (assuming units where the speed of light is 1 unit of distance per 1 unit of time and $m_0$ is your rest-mass).

For the purposes of this post, I’m going to assume the simplest initial conditions: you start motionless and at the origin. For ease of notation, let $a = \frac{F}{m_0}$ . Solving the above differential equation to get a formula for velocity and solving the resulting differential equation to get the distance $x$ you’ve travelled in my base frame by time $t$ , the answer comes out to: $x(t) = \frac{1}{a}\left(-1 + \sqrt{1+a^2t^2}\right)$ .

I have solved this problem at least thirty times in the past two months. Sometimes I used the simple initial conditions as above. Sometimes I did it in all of its gory details (including the messy case where the applied force is not aligned with the current velocity).

I got the same answer (well, plus the extra mess when I did the full-on problem) every way that I tried it.

So, why did I do it over and over again?

If this were classical mechanics, the end equation would have been $x(t) = \frac{1}{2}at^2$ . And, I know that for low velocities, the classical mechanics answer should be almost identical to the special relativity answer. And, there was no way that I thought $\frac{1}{a}\left(-1 + \sqrt{1+a^2t^2}\right) \approx \frac{1}{2}at^2$ .

I knew what the graph $x = \sqrt{a^2t^2}$ looked like when $t \ge 0$ . It is a straight line. It doesn’t look much like the parabola $x = \frac{1}{2}a t^2$ at all.

My assumption was that since $x = \sqrt{a^2t^2}$ was a straight line for $t \ge 0$ , then $x = \sqrt{1 + a^2t^2}$ would be a straight line shifted up one unit and bent (concave-down) a little bit like the graph of $x = \sqrt{at}$ is bent.

Boy was I wrong. Here is a plot of the two together (created with fooplot). The red line is the classical mechanics version. The black line is the relativistic version. Here, the force is such that the body is accelerating at a rate of the speed of light per second so they’ve already gotten up to around 28,000 miles per second before you can see any separation in the graphs here.

Definitely, I can see the resemblance. Now, to fix my intuition about square-roots.

nklein software

software development and consulting

HTML + JS + LISP. Oh My. March 20th, 2012
Patrick Stein