Fourier Transforms in JavaScript September 2nd, 2009
Patrick Stein

In preparation for a study group on Numeric Photography, I started toying with what language to use for the coding projects.

Feature shopping

My inclination, of course, was to go with Lisp. Part of the goal of the assignments, however, was to make interactive web applications for each assignment and a gallery at the end of the completed assignments. I experimented a bit with Armed Bear Common Lisp. The hurdles that I would need a user to go through to use my application safely were too great. The user would have to edit their own java.policy file to give my applet permission. If I wanted to let the user do that with a single click or something, I would have to spring for a $200/year code-signing cert.

My next choice then was stand-alone Lisp applications. Rather than online, interactive applications, I would have downloadable ones. Not ideal, but doable. The big hurdle here is crafting a GUI to run the application. The GUI wouldn’t be too terrible thanks to an interesting concept that Dirk Gerrits pointed out: Immediate Mode GUIs. I have already implemented the buttons from this tutorial in OpenGL under SBCL.

Late one night, I remembered Parenscript. It is a Lisp-like language that compiles to Javascript. Parenscript was a little bit more its own thing and a little bit less Lisp than I had wanted. But, it got me thinking. What can you do in Javascript these days?

I searched for image processing javascript. The first hit was Pixastic. It is a library of basic image processing functions that you can run on any image on your page. At its heart, it uses the Canvas element that is available on Safari, Firefox, and Opera. So, I figured, why not? If I can get an FFT working in Javascript, then there is nothing keeping me from implementing all of the assignments in Javascript. Yes, Javascript is awful, but it’s a dream compared to Java. The new Javascript debugging features in Safari are quite useful, too.

Success

Below is a simple example of what I have working. When you first load the page, you see an image of my son and my dad at the Pittsburgh Zoo. This image is actually loaded in a hidden image and copied into a visible canvas. You are seeing the canvas.

If you press the FFT button and wait for it, you will see a representation of the 2-D Discrete Fourier Transform of the image. Really, the DFT output is complex numbers. The representation is just the magnitude of the complex numbers. The actual complex numbers are kept around in a variable so that when you hit the IFFT button, it has enough information to actually reconstruct the image. So, the FFT button works from the pixels in the canvas. The IFFT button works from the data generated with the last FFT. So, unfortunately, you cannot meaningfully FFT-FFT-IFFT-IFFT here. It is interesting, but not meaningful.

Also, I was trying to add a text box here so that you could use your own image, but I am not getting it right. You’re going to have to wait until I finish the whole assignment.




You need a browser that supports the Canvas tag.
Firefox, Safari, and Opera should all work.



UI Paradigm from Scratch August 28th, 2009
Patrick Stein

I’m not fond of MVC and yet I know of nothing better. What would I want in an alternative?

Most UI toolkits claim to follow the model-view-controller paradigm if they make any such claim at all. In my experience though, they either mush together the controller and view, or the model and view, or all three. As such, there isn’t an opportunity to have the same information represented in multiple places within the interface. Instead, you have repeated information that is synchronized through a complex scaffolding of change listeners. Yuck.

Target platform

First, I should mention why I want such a thing. I am planning to participate in a study group centered around this MIT OpenCourseWare course in Numeric Photography. I’ve done plenty of digital imaging in my day. The assignments for this course though seem to center on novel user interfaces to digital imaging and artistic value of the end results. The original course was all done as Java applets. I considered using Armed Bear Common Lisp to try to write Lisp code that interacted with the user through a Java applet. My initial tests on this went poorly since the ABCL code wants to read and write from your .abclrc and such. I toyed with code signing and permission granting on it, but wasn’t too satisfied with how easily someone else would be able to use it. Plus, I wasn’t too keen on doing so much Java.

So, I want to start with as few dependencies as possible for standalone Lisp applications. If I could keep the dependencies down to a GUI library of my own crafted atop cl-opengl and cl-png, that would be great. I suspect that I will have to throw in zpb-ttf at some point to get text into the UI, too.

Toolkit Structure

I am going to use the example of a simple checkbox. At its heart, a checkbox is simply a boolean value. The meat or logic of the code doesn’t have to care whether the checkbox is visible or enabled or being clicked or has recently changed. The meat of the code only has to know if it is checked or not. It would be nice if I could get away with just having a boolean anywhere in my code. However, some things will need to be triggered when the boolean changes. As such, I am going to need some setter/getter artifice around the boolean. So, let’s make a structure with a single boolean slot.

(defclass checkbox ()
  ((value :initarg :value :type (member nil t)))
  (:default-initargs :value nil))

Let’s call this the Checkbox Base.

This is all that most of my application will need to know. Somehow there is a checkbox. It is either checked or not.

How is the checkbox state presented in the interface? It could be drawn on the screen as a little box that either contains a check or not. It could be drawn as a menu item that either has a check beside it or not. It could be reflected in the state of some LED somewhere. It could be presented in hundreds of web browsers across the company as either a green box or a red box. Let’s call each of these a Checkbox Representation.

Somehow, each of these Checkbox Representations has to be notified when the value changes. If I am willing to also include a dependency on Cells (which hasn’t been touched since May of 2005), then I can get this kind of notification for free.

(defclass checkbox ()
  ((value :initform (c-in nil) :accessor checkbox-value)))

(defclass checkbox-as-colored-box ()
  ((checkbox :initarg :checkbox :type checkbox :reader checkbox)
   (color :cell t :initform (c? (if (checkbox-value (checkbox self))
                                    :green
                                    :red)))))

(def-c-output color ((self checkbox-as-colored-box))
  (redraw-checkbox-as-colored-box new-value))

Any time the value of the checkbox changes, the color of the checkbox-as-colored-box will change and the trigger to redraw-checkbox-as-colored-box will be invoked with the new color value.

If I don’t use Cells, then I have to create a layer around the checkbox that tracks who needs to be notified when the value changes. Let’s call this a Checkbox Monitor. It is very tempting to fold this right into the checkbox. After all, when the checkbox changes, the monitor has to know. For a slightly better division of functionality, one might make monitored-checkbox a subclass of checkbox:

(defclass monitored-checkbox (checkbox)
  ((listeners :initform nil)))

In this way, UI components can register with the monitored-checkbox, but the main application never has to notice that the checkbox has the weird methods for adding listeners and such. With an appropriate :around or :after method, the checkbox code doesn’t even have to know if it is part of a monitored-checkbox. It would be nice if the code didn’t have to know this at instantiation time, but I’m not seeing an obvious way around that without Cells.

With Cells, each representation could monitor the Checkbox Base. Without the Cells-type approach, there can really only be one Monitor per Base. (Technically, there could be more, but they could only be through a direct inheritance chain… you could wrap the Monitor with a Monitor2 and that with a Monitor3, etc. But, you wouldn’t want to try to instantiate a Monitor123 or anything like that.) For now, let’s explore the non-Cells case.

The idea so far is that you can create a Checkbox Monitor which is a subclass of Checkbox Base. Then, you can create some Checkbox Representations and register them with the monitor. The meat of your code can think of it as a Checkbox Base.

How is it toggled? There are a variety of ways that could happen. Someone could hit a global hot-key that toggles the checkbox. Someone could select a menu item that toggles the checkbox. Someone could mouse click on a representation of that checkbox. My application could receive an event from a remote source like a secondary display, a database, or a filesystem that toggles the checkbox. Someone could hit the space bar or the enter key while a representation of that checkbox has keyboard focus.

I am not sure we need to create a class hierarchy around changing the checkbox. We can simply call the setter on the checkbox. The monitor will catch it and notify everyone who needs to know. Further, the checkbox itself will be set for anyone who needs to passively query (rather than needing to track its every change).

The big question then is can we enable or disable the checkbox? This would have to either be a property of the Checkbox Base (which doesn’t seem right to me) or a joint effort spanning all places that wish to toggle the checkbox (which also doesn’t seem right). Fortunately, I think we can use multiple-inheritance and more :around methods to take care of this.

(defclass checkbox ()
  ((value :initform nil :type (member nil t) :accessor checkbox-value)))

(defclass monitor ()
  ((listeners :initform nil)))

(defclass enabler ()
  ((enabled :initform t :type (member nil t) :accessor control-enabled)))

(defclass enabled-checkbox-monitor (enabler monitor checkbox)
  ())

(defmethod (setf checkbox-value) :around (new-value checkbox)
  (when (control-enabled checkbox)
    (call-next-method)))

Is this any better than the status quo? I’m not sure. I will have to write more code to find out.

Alternatives to MVC? August 26th, 2009
Patrick Stein

The model-view-controller paradigm dominates the UI toolkit world. I should say, it dominates the talk about the UI toolkit world. Most UI toolkits have very poor separation between the model, the view, and the controller. For most UI toolkits, a text input field can only have one controller and one view. Further, all of the aspects of the controller, the view, and the model are accessed through the text input field object.

I tried to google around for “model view controller” alternatives and “model view controller” rethinking. The only alternative that I saw was DDP (data driven presentation). Data driven presentation seems like someone took the model-view-controller paradigm and collapsed the view state into the model. This makes for a somewhat nicer entity-relationship diagram because then the controller never has to speak directly to the view, it can just twiddle the data.

I don’t think data driven presentation is a real alternative to model-view-controller. It is a slight repackaging of something that’s never been packaged right before, to my knowledge.

I don’t really like the model-view-controller paradigm very much. I would love to hear about alternative approaches to representing the same control in multiple places in an application. Alas, in the absence of an alternative, I have been trying to think about how to do model-view-controller right.

Let’s try a checkbox

What is the model for a checkbox? At its simplest, a checkbox is either checked or not. It is a simple boolean value. The checkbox doesn’t exist in a vacuum though. It probably needs a list of listeners that want to be notified when the checkbox is toggled. So, the checkbox model is two things: a simple state and an initiator of state-change events.

Does the model have a label? I say, No. If the model had a label, then I cannot display it in two different places with two different labels. If it is going to have any sort of label at all in the model, it should merely be a label indicator. Let’s imagine that I am making an interface that is English on the left side of the dialog box and Spanish on the right side. If I am truly separating model from view, then I should be able to use the same checkbox model on both halves of the screen. I cannot keep the text label in the model unless one of my views knows how to translate. If one of my views is going to know how to translate, then both of them should. Me, I don’t think that either should.

What is the view for a checkbox? A checkbox view at its simplest is just an indicator showing whether the box is checked or not. It might be a rendering of the box on your screen either empty or containing a checked mark of some sort. It might be a rendering of the box on a remote screen. It might be the little Caps Lock light on your keyboard. It might be a green table cell on a web page.

Does the view have a label? I don’t know. It makes more sense here than in the model, but does it belong here? Suppose there is some event elsewhere that makes me want to change the label. Suppose my label was include all images. Then, suppose someone adds a sound file into the document, and I want to change the label to include all images and sounds. I have to track down all of the views and update them. I would still have to do this if the label were a separate entity apart from the checkbox. So, the question is, should it be a separate entity?

What is the controller for a checkbox? For a checkbox rendered to the screen, the controller has to recognize mouse clicks in the same area that the view is in. Either the controller has to moved around lock-step with the view so that it has the same geometry, or the controller has to know enough about the view to tell whether a mouse event hit it. Similarly, if the checkbox has focus, pressing the space bar or the enter key should probably toggle the checkbox. The view has to know if it has focus so that it can render itself to appear focused. The controller has to know if it has focus to know whether to care about the key press.

It is tempting to combine the controller into the view. It definitely simplifies the geometry and focus questions. Those become shared information. There are other possible controllers for the checkbox, too, though. Maybe the checkbox has a global hot-key. Maybe there is some menu item that uses the same checkbox model (though a good menu item will also act as a view of the checkbox model, so it really is a combination view and controller again).

Is enabled a property of the model or the view or the controller? I say, not the model. Of course, this is thorny. Suppose that my checkbox isn’t relevant at this point in my application. I should disable it. However, I have to update all of the views attached to this model instead of just updating the model. Feh. Of course, I also have the option of disabling just some of the views. For example, if my application supported multiple users watching, but only a single one editing, then I would need to disable this checkbox in every window except the one on the editor’s desktop.

Is focus a property of the model or the view or the controller? It shouldn’t be part of the model. If I am displaying the same model to two different desktops, there is no reason that the two users should have to synchronize which control they are using. Heck, what’s to say that the second user even has all of the controls that the first user has?

Where we are

The controller and view definitely need to know about the model. The controller and view both need to know about focus. The controller and view both need to know about enabled. The model needs to be able to tell all of its views that they are stale. For items that are going to be taking mouse input, the controller definitely has to know where the view is being rendered.

The fact that the controller and view both need to share the focus and enabled information (as well as caret position and selection range and such for other types of controls) indicates that there should be another entity in this paradigm that both the controller and view can refer to. There is both a model of the item and a model of how that item is to be presented—a model and a presentation model, if you will. If there are two users sharing the same text input field, then the GUI should have the choice of sharing the presentation model across users so that they both have the same caret position and selection range or allowing them each their own presentation model so that they each have their own caret position and selection range. It is further complicated by the fact that you may want to share the caret position and selection range without sharing the focus or enabled settings.

I am afraid that I haven’t reached much conclusion here. I still don’t have answers or alternatives. Any references or suggestions would be greatly appreciated.

Casting to Integers Considered Harmful August 6th, 2009
Patrick Stein

Background

Many years back, I wrote some ambient music generation code. The basic structure of the code is this: Take one queen and twenty or so drones in a thirty-two dimensional space. Give them each random positions and velocities. Limit the velocity and acceleration of the queen more than you limit the same for the drones. Now, select some point at random for the queen to target. Have the queen accelerate toward that target. Have the drones accelerate toward the queen. Use the average distance from the drones to the queens in the i-th dimension as the volume of the i-th note where the notes are logarithmically spaced across one octave. Clip negative volumes to zero. Every so often, or when the queen gets close to the target, give the queen a new target.

It makes for some interesting ambient noise that sounds a bit like movie space noises where the lumbering enemy battleship is looming in orbit as its center portion spins to create artificial gravity within.

I started working on an iPhone application based on this code. The original code was in C++. The conversion to Objective C was fairly straightforward and fairly painless (as I used the opportunity to try to correct my own faults by breaking things out into separate functions more often).

Visualization troubles

uniform
The original code though chose random positions and velocities from uniform distributions. The iPhone app is going to involve visualization as well as auralization. The picture at the right here is a plot of five thousand points with each coordinate selected from a uniform distribution with range [-20,+20]. Because each axis value is chosen independently, it looks very unnatural.

gauss
What to do? The obvious answer is to use Gaussian random variables instead of uniform ones. The picture at the right here is five thousand points with each coordinate selected from a Gaussian distribution with a standard-deviation of 10. As you can see, this is much more natural looking.

How did I generate the Gaussians?

I have usually used the Box-Muller method of generating two Gaussian-distributed random variables given two uniformly-distributed random variables:

(defun random-gaussian ()
  (let ((u1 (random 1.0))
        (u2 (random 1.0)))
    (let ((mag (sqrt (* -2.0 (log u1))))
          (ang (* 2.0 pi u2)))
      (values (* mag (cos ang))
              (* mag (sin ang))))))

But, I found an article online that shows a more numerically stable version:

(defun random-gaussian ()
  (flet ((pick-in-circle ()
           (loop as u1 = (random 1.0)
                as u2 = (random 1.0)
                as mag-squared = (+ (* u1 u1) (* u2 u2))
                when (< mag-squared 1.0)
                return (values u1 u2 mag-squared))))
    (multiple-value-bind (u1 u2 mag-squared) (pick-in-circle)
      (let ((ww (sqrt (/ (* -2.0 (log mag-squared)) mag-squared))))
        (values (* u1 ww)
                (* u2 ww))))))

For a quick sanity check, I thought, let’s just make sure it looks like a Gaussian. Here, I showed the code in Lisp, but the original code was in Objective-C. I figured, If I just change the function declaration, I can plop this into a short C program, run a few thousand trials into some histogram buckets, and see what I get.

The trouble with zero

So, here comes the problem with zero. I had the following main loop:

#define BUCKET_COUNT 33
#define STDDEV       8.0
#define ITERATIONS   100000

  for ( ii=0; ii < ITERATIONS; ++ii ) {
    int bb = val_to_bucket( STDDEV * gaussian() );
    if ( 0 <= bb && bb < BUCKET_COUNT ) {
      ++buckets[ bb ];
    }
  }

I now present you with three different implementations of the val_to_bucket() function.

int val_to_bucket( double _val ) {
  return (int)_val + ( BUCKET_COUNT / 2 );
}

int val_to_bucket( double _val ) {
  return (int)( _val + (int)( BUCKET_COUNT / 2 ) );
}

int val_to_bucket( double _val ) {
  return (int)( _val + (int)( BUCKET_COUNT / 2 ) + 1 ) - 1;
}

As you can probably guess, after years or reading trick questions, only the last one actually works as far as my main loop is concerned. Why? Every number between -1 and +1 becomes zero when you cast the double to an integer. That’s twice as big a range as any other integer gets. So, for the first implementation, the middle bucket has about twice as many things in it as it should. For the second implementation, the first bucket has more things in it than it should. For the final implementation, the non-existent bucket before the first one is the overloaded bucket. In the end, I used this implementation instead so that I wouldn’t even bias non-existent buckets:

int val_to_bucket( double _val ) {
  return (int)lround(_val) + ( BUCKET_COUNT / 2 );
}

Numbers 30:2, for programmers July 20th, 2009
Patrick Stein

The role-playing game Paranoia was set in a dystopian future where a paranoid computer had seized control to protect us from Commie, mutant traitors. In the game, secret societies were strictly forbidden. As such, every character was a member of some secret society or other. One of those secret societies was the FCCCP: First Church of Christ, Computer Programmer. This, of course, tickled me. Heck, it still does.

Outside the world of role-playing games, there is a long tradition of analyzing sacred texts, pulling out every possible thread of meaning and applying those meanings to every aspect of life. I’ve been pondering a series of articles that combines the exegesis with the computer programming.

Well, this week’s sermon at our synagogue was about the verse Numbers 30:2:

If a man makes a vow to the LORD, or swears an oath to bind himself by some agreement, he shall not break his word; he shall do according to all that proceeds out of his mouth.

How could I sit there without pondering Programming by Contract? In fact, I would say that this verse goes much beyond just the contract. Every line of code makes promises. Are they promises the code can keep?

To ground the discussion, I dug around for a short function that I wrote more than a year ago. The following snippet of code takes two arrays: counter and maximum. The array elements of each are assumed to be integers. The arrays are assumed to be the same length. The value of the i-th entry in counter is assumed to be less than the i-th entry in maximum. If you think of an axis-aligned, n-dimensional cube with one corner at the origin and its opposite corner at the maximum, the goal is for counter to scan through every set of integer coordinates in the cube (well, including the faces that touch the origin, but not including the faces that touch the maximum). If every entry in maximum is b, then the result should be just like incrementing a base b number that is displayed least-significant digit first. If maximum were \left( 60, 60, 24, 7, 4 \right), the counter would count out the seconds in February (non-leap year).

(defun increment-counter (counter maximum)
  (unless (null counter)
    (let ((nn (length counter)))
      (let ((result (make-array nn :initial-contents counter)))
        (dotimes (ii nn nil)
          (when (< (incf (aref result ii)) (aref maximum ii))
            (return result))
          (setf (aref result ii) 0))))))

What promises does the above code make? The function name increment-counter is a pretty obvious promise. The function is going to increment some sort of counter. Given just the function name, what would we expect? I would expect that it takes a single argument, that argument is a reference to an integer, and that integer is incremented in place. I would be way off. Our promise is already on sketchy grounds. I’m not coming up with a particularly good name at the moment though: step-cube-walker? increment-n-dimensional-counter?

The function doesn’t increment the counter in place. Instead, it returns a newly allocated counter (or nil, if we’ve reached the end). The function declaration doesn’t make any promise that maximum will be left untouched, though Lisp doesn’t make it easy to declare that. Lisp usually handles that sort of thing by convention. The function declaration also makes no claim that the counter and maximum arguments should be arrays, let alone that they should be the same length. (Technically, the code only requires that maximum be an array. Counter can be any sequence. Further, maximum is allowed to be longer than counter, but cannot be shorter.)

Line 2 of the code doesn’t trust you to stop calling it when you’re already done. This is an interesting hedge, but not really an oath. It may rise to that level at some point though if enough code starts to depend on this utterance.

Lines 3 & 4 are the only uses of (a non-nil) counter. They work just fine for any sequence. As such, while this function always returns either nil or an array, it will accept any sequence as the counter.

Line 5 outright promises that the function is going to return nil. This is, of course, countermanded on line 7. I suppose this is akin to verses 3, 4, & 5:

[3] Or if a woman makes a vow to the LORD, and binds herself by some agreement while in her father’s house in her youth, [4] and her father hears her vow and the agreement by which she has bound herself, and her father holds his peace, then all her vows shall stand, and every agreement with which she has bound herself shall stand. [5] But if her father overrules her on the day that he hears, then none of her vows nor her agreements by which she has bound herself shall stand; and the LORD will release her, because her father overruled her.

Even though the loop on line five is released of its promise, it still feels like a cheap back door.

So, you can see that even in these eight lines of code, I have made many, many inadvertent promises. Hopefully, in future code, I will keep a more careful tongue.

Updates In Email

Email:

RSS Feeds

l