A Different Look at the Mandelbrot Set May 14th, 2009
Patrick Stein

When you see pictures of the Mandelbrot set you are seeing the results of iterating a function over and over.

For the Mandelbrot set, you take a complex number c. You square it and add the original number. You take that, square it, and add the original. You do this a number of times. If the value stays relatively close to zero, the number is in the Mandelbrot set. If the value takes off away from zero, the number is not in the Mandelbrot set. Typically, one colors in the parts of the picture that aren’t in the Mandelbrot set with some color that indicates just how fast it hightailed it out of there.

I wanted to try something different. I wanted to see what the iteration process looks like. So, I threw together some code using Lisp with cl-opengl.

fibersThe first visualization that I coded was to start with tiny patches of the complex plane. From each patch, I would extrude it up out of the plane and over to its next iteration. The picture at the right is (IIRC) a patch with side-length one half centered at i with either 25 or 36 patches tiled in that area. As you can see, this isn’t a wholly satisfying picture of what’s going on.

The other idea that I had was to show the progress through iterations as an animation. This is a bit more interesting to look at until some of the patches start overflowing my floating point numbers or get too big for my clipping region. This is an area of side-length one centered at the origin with four-hundred patches. Here is a movie of that flow.

Finding Better Polynomials May 12th, 2009
Patrick Stein

Some time ago, I wrote a small domain-specific language for finding polynomials given their value or the value of their derivatives at particular points.

It occurred to me shortly after writing that code that I could easily extend it to include the value of its integral over a certain range. I didn’t get to tackling that right away, and that was a Good Thing. In the intervening time, it occurred to me that I could extend it to moments as well.

So, are you looking for a polynomial that is zero at both zero and one, has a derivative of zero at one, has a second derivative of negative one at one, whose integral from zero to one is one, and whose mean (first moment centered at zero) on the interval zero to one is one fourth?

(polynomial-to-string
  (calculate-polynomial-subject-to
    (value :at 0 :equals 0)
    (value :at 1 :equals 0)
    (derivative :at 1 :equals 0)
    (nth-derivative 2 :at 1 :equals -1)
    (integral :from 0 :to 1 :equals 1)
    (mean :from 0 :to 1 :equals 1/4)))

Well, that would be f(x) = \frac{149}{4}x - 163x^2 + 265x^3 - 190x^4 + \frac{203}{4}x^5. (For some reason though, gnuplot thinks f(x) = -1, so no graph for you…)

Here is the source file.

graph
Edit: I realized that gnuplot was off by one because it was truncating the fractions. So, I just changed the 4’s in the denominators to 4.0’s and Bob’s your uncle.

 

Code Clarity Revisited May 11th, 2009
Patrick Stein

In an earlier post, I showed a simple loop written in several programming languages. The loop had to sum the weights of each items in a list. Dmitry pointed out a much clearer loop in Lisp using the (loop …) construct.

(loop for item in item-list sum (weight item))

I then twiddled for the better part of an hour trying to find the clearest way to do weighted random choice with Lisp (loop …). This is the best that I have come up with:

(loop
   with total = (loop for item in item-list sum (weight item))
   with thresh = (random total)
   for item in item-list
   if (minusp (decf thresh (weight item)))
     return item)

The biggest pedagogical obstacle in the above is the (decf …) which decrements the variable in place by the given amount and returns the new value of the variable. What I really wanted to do was this:

(loop
   with total = (loop for item in item-list sum (weight item))
   for item in item-list
   tracking item
   as thresh downfrom (random total) by (weight item))

That fails on multiple fronts, however.

  • There is no tracking keyword in (loop …). I can sum or maximize or collect items, but I cannot keep track of the last one that I saw. I had hoped to use the finally keyword, but its value isn’t returned from the loop.
  • Lisp requires that the decrement amount in the by of a downfrom be greater than zero. As such, I have to filter out any items that have zero weight. Feh. I can do that. I would rather not. But, I can do that.
  • Lisp only evaluates the by expression once. It does not evaluate it each time through the loop.

I am still learning all of the ins and outs of (loop …). Today, I learned as many outs as ins. Feh.

Twin Cities Lisp Group Starting Up May 9th, 2009
Patrick Stein

(defmeeting tc-lisp
   "Twin Cities Lisp Group Inaugural Meeting"
  :date    '(9 June 2009)
  :time    '((6 :pm) . (8 :pm))
  :venue   "Common Roots Cafe"  
  :address "Corner of 26th and Lyndale in Minneapolis, MN")

Complete details on Robert Goldman’s page. Here is an introduction to the first talk (by John Maraist):

NST: A Unit Test Framework for Common Lisp

In this talk we will introduce the Lisp unit test framework NST. SIFT developed NST for internal use on a number of ongoing Lisp projects, and we believe that the system is now mature enough to release more broadly. In this talk we will review the notion of a unit test, and introduce the use of NST in Lisp project development. NST’s implementation makes interesting use of a number of Lisp features—macro expansion, compile-time execution, metaobject protocols—and we will discuss its current implementation as well as the lessons we learned along the way.

There is also mailing list, and more information about the Common Roots Cafe.

Programming When Clarity Counts May 5th, 2009
Patrick Stein

In my previous post, I wrote some code in Perl because I wanted the code to be clear and obvious. Wait? What? Who uses Perl when they want clarity?

Perl

I admit: I was surprised myself. Seriously, I tried several other languages first. Let’s just focus on the first loop here. Here’s the Perl again for reference:

my $total = 0.0;
foreach my $item ( @list_of_items ) {
    $total += weight( $item );
}

Objective C

The actual code that I was attempting to explain was in Objective C with the NeXTStep foundation classes. I couldn’t imagine that anyone would want to try to understand it:

double total = 0.0;
NSEnumerator* ee = [itemList objectEnumerator];
Item* item;
while ( ( item = (Item*)[ee nextObject] ) != nil ) {
    total += [item weight];
}

C

My first attempt for the article was to write it in C using an array of items.

double total = 0.0;
unsigned int ii;
for ( ii = 0; ii < itemCount; ++ii ) {
    total += weight( itemArray[ ii ] );
}

That’s not too terrible. There is, however, a great deal of syntax and code devoted to handling the array including an extra variable to track its length. Beyond that, the loop counter is of little use to someone trying to understand the concept.

C++

My next go was C++. My hope was that iterators would make the looping less painful. C++ iterators, however, are the very model of pain.

double total = 0.0;
std::list< Item* >::const_iterator it;
for ( it = itemList.begin(); it != itemList.end(); ++it ) {
    total += weight( *it );
}

This requires the reader to wade through a syntactic thicket to get the iterator into the picture at all. It also requires a certain comfort with pointers that one wouldn’t have coming from another language.

Java

My next attempt was Java. I hate Java. It may not be terrible for this code with the new looping constructs that came in Java 1.5. Alas, I quit coding it before I made it through this first loop.

Lisp

Of course, I wanted to code this in Lisp:

(let ((total (reduce #'+ list-of-items :key #'weight)))
   ...)

That would be perfectly clear to someone who has used Lisp or Scheme. Alas, not everyone has.

So… Perl…

If you want to write the Perl code, you have to understand the difference between scalars and arrays. To read the code, however, you don’t have to grok that distinction to see what’s going on. I didn’t try it in Python. Maybe it would be clear to a wider audience. I may have to try it next time.

Updates In Email

Email:

RSS Feeds

l