Mouse editing... useful but not popular?

This is just a bit of a rant, possibly about something people think is really trivial to talk about but I think there's something worth saying here.

I've been noticing a lot of blogs and people using tools claiming that never taking one's hands off the keyboard is a good thing. This seems to be generally accepted as a rule of thumb to follow, but I don't buy it.

There's window managers that abolish the mouse completely for X such as Xmonad and ratpoison. They certainly have their merits and people are adopting them and finding that they get more work done than in alternative window managers. All of that is fine, I'm not trying to take anything away from those people or those projects, I'd just like to challenge the premise that hardly ever using the mouse is always optimal.

A few examples to the contrary that I've found for myself:

Expose in Mac OS X allows me to quickly use my touchpad, or trackball/mouse to point at a location on my desktop and quickly see all my windows and nearly immediately point to the window I'm interested in. To me this is a lot more useful than memorizing which of many desktops I might have decided to put certain windows on, or tabbing through to cycle to the correct window, or possibly remembering what shortcut key goes to a particular window on the current desktop. Point and click is easy.

Still I've peers who don't like Expose and do everything they can to turn it off.

When editing text, GUI versions of Emacs allow me to sweep over text and use that as a copy command to move text around during editing sessions. This is not as powerful as the Acme editor from Plan 9, in that I can chord buttons on my trackball to cut and paste text to different locations without taking my hand off the mouse.

I will admit I'm a bit of an emacs junkie, for better or worse, and like my elisp based customizations I've become used to over the years do save me a bit of time for certain tasks. Those are nearly always keyboard accessible shortcuts, but again, this becomes a memorization process of those commands. That memorization and customization is initially a distraction from getting work done, but it does become habit after a short time, and then it feels very fluid. I still often find myself switching between Acme, Sam, and emacs depending on the sort of editing I'm doing.

I don't see how selecting text with arrow keys or control key combinations is ever faster than a mouse sweep and click. In fact while editing this blog I find myself taking my hands off the keyboard, pointing at a word or phrase to double click and change a word very quickly, much faster than if I had to press repetitions of keys and delete buttons to change text.

I'll also go ahead and admit that before I'd used Acme, and I mean really used it for a little while, I was in the camp of people who would have said that never removing the hands from the keyboard was faster without even questioning why that is.

My advice to people is to try some of these other editors, and see if you can understand where I'm coming from. The people who designed the editors that are mouse driven have written large amounts of code in their day, and they've certainly gained a lot of experience in knowing what annoys them during an editing session and wanted to make changes to make the process more comfortable for themselves.

Worst case scenario is you'll still think that keyboard-only is the way to go and you'll not really have lost anything but maybe have re-assured yourself that for your work environment, that's the best way for you to go. Maybe you'll learn a new way to work that you find is faster.

Also, there's a lot more reasons to really like Sam or Acme, but that's for another time.

Unemployed

Well the company I work for is in the process of restructuring, and most everyone has been laid off. Verari Systems was a fun place to work, and I got to do a few of the things that I've nearly documented here (except for anything they'd consider Intellectual Property). It's been a fun ride, and there's rumors floating around about people wanting to re-invigorate our technology into a new company.

I'm hoping I can play a part in that new company if it happens, but I'm not currently willing to wager on that.

Started interviewing at one company, and I've been working a contract that'll get me through the holiday season, but I'm currently on the market if there's anyone interested!

I'll post updates to my employment status here as things develop.

I'd also like to say that the outpour of support I've gotten from friends has been amazing, and that I'm so glad to have people like them in my life.

Lazy Programming, too much, too little?

Another Haskeller/Blogger wrote the following interesting article on how optional laziness doesn't always work out so well.

However I'm finding there's a lot of functions that don't make a ton of sense to my imperative, strictly trained programmer's mind to do in a lazy way by default.

foldl is a good example. Without strictness checking turned on in the compiler options for GHC, it can turn into a memory leak right away.

I find myself kind of hard pressed to come up with a good use for a lazy foldl where it isn't obvious that I'd rather have used foldl'.

Long running Haskell applications

I've been using Haskell in a serious way for about 2 years. Been using it in a professional sense about 1.5 years now in that, yes, I am one of the lucky ones that gets to use Haskell at work.

The ride has been pretty smooth most of the time, as I've found that the type system especially helps me to rule out certain classes of bugs, easily test rather large chunks of programs as they're pure. The interpreter allows experimentation and iteration of ideas that can then be composed into the final compiled programs. All of this gives me a good deal of confidence that the code I'm writing is correct to some degree up front, something I've come to expect from functional programming languages over the years and greatly appreciate.

However I've felt compelled to comment that things aren't always so smooth either. I spent the better part of a weekend and a Monday tracking down a space leak in a program that just was not allowed to leak space. I have a stack of a ReaderT StateT IO that I use to communicate with a device through a passthrough program that speaks CAN to a device for the purposes of creating a serial console connection where there is only a CAN bus. The Haskell program is responsible for the management of the data found at the other end o the serial connection and supports operations to the device through the serial channel via a simple text protocol while "forever" polling data on the serial endpoint.

What I had done was the equivalent of

pollerLoop :: Poller ()
pollerLoop = forever pollOnce

Where Poller is my monad stack.
pollOnce is defined as,

pollOnce :: Poller ()
pollOnce  = do
checkCommandChannel -- see if there's a pending command to run
executePoll

Yes, this application is multi-threaded. I have a logger thread, a thread watching standard input of the program for queries and issuing commands to the endpoint. I have a thread per Poller, and the ability to poll devices simultaneously.

The poller includes an implementation of my little "expect" syntax which was based on a naive implementation of hGetChar and checking for a desired result or timing out eventually. The really data inefficient version is a real screamer, beating the heck out of my Parsec or even ReadP version, but because of the way I wrote it, with a lot of reversing and prefix checking and substring slicing into temporary areas, it's not useful for large input blocks over a long time frame.

Still it's so fast that it's appropriate for certain sections of code. I measured and verified this via space profiling to see the real runtime heap utilization (nice feature btw, I'd be dead without it right now I think).

So what's the problem you're probably thinking? Well it turns out that since part of my state in StateT is a Data.Map, and that all my polling and parsing of expect-passing blocks caused updates to a Map, coupled with the language's default laziness caused a bit of a "bomb" of PAP (Partial APplications of functions).

I had an ill-timed, project wise, discovery of a space leak.

I tried sprinkling $! and seq all over the place, rewriting big chunks of code that used Text.Regex.Posix, to use Parsec and only got incremental improvements. The growth problem still existed, and would eventually exhaust memory. This was a real problem as this was an application that was not supposed to stop when the other conditions of the management system were ok. It could run for months or even years!

I went through a whirlwind of emotions, and considered that perhaps I should be working a different job. Perhaps I could be a lion tamer? It turned out what I thought was a lion was really an anteater though... but that's literally a different story.

It turns out that by looping not inside the monad, but over the execStateT/runReaderT expression I could pull all the state out, and then re-inject it into another execStateT/runReaderT each poll, which forced the strictness I needed on all state data, made the system respond faster, and best of all, not crash!!!!

Diagrams below:

This first one is the "before" picture. It shows the data growth by cost center in my code. As you can see things are getting worse almost linearly as I poll.

This picture illustrates the result of pulling the state out of the Monad, and re-injecting it, forcing it to be evaluated. As you can see, I've got much more manageable memory utilization.

This final one shows the new algorithm running with 2 threads, one spawned a few seconds into the run. You can see the initial burst of the fast but inefficient "expect" algorithm, followed by a much more regular memory utilization pattern.

I'd like to thank all the folks on #haskell on FreeNode who gave me suggestions and hints to my vague problems regarding data growth and laziness vs strictness. Haskell's got a great user community and is probably one of the most helpful out there. One can learn a lot just asking questions of the right mentors as well as by reading haskell-cafe and the various blogs that are out there.

I'm hoping that this anecdote is useful to someone.

OOP maybe should have been called Oops

http://www.informit.com/articles/article.aspx?p=1327762

"Designing object-oriented software is hard—designing reusable object-oriented software is even harder. Experienced object-oriented designers will tell you that a reusable and flexible design is difficult, if not impossible, to get "right" the first time, and that multiple attempts at reuse with subsequent redesigns are normal."

Now there's a statement about Object Oriented Design I can agree with :-)

Yes I realize that Design Patterns tried to give a set of reusable designs to certain problem cases or environments, and that's all great and what not, but I think software design has to perhaps abstract these ideas even further into "modules of services".

It won't matter so much if you used a methodology like OOP or Functional Programming, or any old imperative approach, as long as the pieces are small and purposeful, and the code is written in a clear enough way, it should be fairly straightforward to adapt it to new situations.

That said...

I've been successful in having written a service in haskell that doesn't really use much in the way of any object oriented design. in fact, it's mainly done with monads, and an EDSL that looks a lot like "Expect". I've been able to tweak this EDSL to write the solution to the problem I'm solving in the language *I* want.

Due to the way the program is designed to work with an external program for getting communication done, it's isolated from the mechanisms of communication, and only implements the logic around parsing data and issuing commands.

This has proven to be very powerful in testing systems via various interconnects. I've used a bizarre combination of socat, hooked up to serial ports, that are looped back through to another program that uses a proprietary embedded serial streaming protocol back up into the Haskell code with exactly the same ease as launching an ssh client session or using socat straight across a serial line.

Tim Newsham strikes again!

Another, more cleaned up version of 9P in Haskell is here.

Nice!

I don't really know what to say..

...except that Tim Newsham is the man.

Out of the blue one day he totally writes up a very nice 9P implementation in Haskell that I started to look at, then ran out of time before I had to start working on other things. A few days ago I thought I'd get back to it, and it doesn't work out.

So a couple days ago he sends me *another* implementation of 9P in Haskell, but instead of just tackling straight 9P, he goes and does 9P.u too (Unix extensions involving fields for the stat message and such). But not only that, he adds an example client program that works with a 9p service running on the Google Android platform, reading sensor data from the phone.

Now that's cool... I need to try it against some of my Inferno service stuff.

More Y

Y is trivial to write in Haskell. The wikipedia entry on fixed point combinators shows that via some reduction operations you end up with a simple definition of: Y g = g (Y g)

To write this in Haskell is really straightforward:

let y g = g (y g)

Yes. Just that easy.

The type of the function y is now:

y :: (t -> t) -> t

That is to say y is a function, that takes a function that takes a type "t" and returns a type "t" and returns a type "t".

This form of type is consistent with being a fixed point calculator for functions. (see the top of that wikipedia article linked earlier for an explanation of a fixed point of a function).

Can this be used to compute a fibonacci function from a fibonacci step? You bet!

let fs = (\n -> (\x -> if x =< 1 then 1 else (n (x -1)) + (n (x - 2))))

Now just like before, in scheme, we can use this to try to manually unroll recursion via the "n" argument which is a function to be run next.

((fs (fs (fs (fs (fs undefined))))) 5)
8

So let's run it with Y

((y fs) 5)
8

or something larger

((y fs) 10)
89

Strictly speaking, writing trace in a pure functional language is not allowed, unless you break the rules. Debug.Trace.trace lets you do this, and since I'm tracing anyway...

let tracestep label = (\f -> (\g -> (\n -> let res = (f g) n in (Debug.Trace.trace (label ++ " " ++ (show res)) res))))

Can I still compose this with "y"?

((y (tracestep "fib" fs)) 5)
fib 1
fib 1
fib 2
fib 1
fib 3
fib 1
fib 1
fib 2
fib 5
fib 1
fib 1
fib 2
fib 1
fib 3
fib 8
8

Yes!

I was going to write about memoizing this as in the Scheme example, but I'm quite tired, and my wife and I watch So You Think You Can Dance, so that's what I'm going to do instead.

Some Scheme and Y

Y combinators are pretty cool. They allow for the definition of recursive code without needing support for self-reference directly.

You can find some good links about it here(javascript), here (wikipedia), and there's a ton of results for it if you search with google.

In a nutshell it's a fixed point combinator that can generate a recursive function from a function that is not defined recursively.

Take the following tried and true example of recursion, the factorial!

(define factorial
    (lambda (x) 
        (cond ((= x 0) 1)
                   (else (* x (factorial (- x 1)))))))

factorial is a function defined in terms of itself (references factorial).

What if this wasn't allowed in your language though? How could you write this?

Well if you had the Y combinator you could write a step of the factorial calculation and add an argument which would be the next operation to run after this step is complete.

(define factstep
  (lambda (next)
    (lambda (n)
      (if (= n 0) 1 (* n (next (- n 1)))))))

Now if you want to use factstep to compute factorials you must first pass in the "next" operation, which yields another function which takes the parameter to the factorial.

; factorial 1
((factstep 'blah) 1)

; factorial 3
((factstep (factstep (factstep (factstep 0)))) 3)

As you can see this gets really tedious without recursion.

Enter the Y combinator:

(define Y
  (lambda (le)
    ((lambda (f) (f f))
     (lambda (f)
       (le (lambda (x) ((f f) x)))))))

Looks like complete nonsense if you don't know how it is derived. There's many different websites that go into that, so I'm not going to. I'm looking for a practical use of this thing.

Well it turns out by applying Y to the function "factstep" you can create the factorial function you're after.

(define factorial (Y factstep))

Now (factorial 6) still yields 720. (Yes Y seems quite magical at this point if you don't understand it, so I suggest reading up on that if it is confusing to you)

So what good is this if we can just define functions recursively to begin with?

Well what if we want to weave in some other behaviors?

Let's look at a more interesting primitive recursive function like fibonacci.

(define fibstep
  (lambda (next)
    (lambda (n)
      (cond 
        ((<= n 1) 1)
        (else (+ (next (- n 1)) (next (- n 2))))))))

This is known to be horribly inefficient as it redoes a lot of the same work? Want to watch how inefficient it is? Ok, let's add a trace step.

(define tracestep
  (lambda (label f)
    (lambda (g)
      (lambda (n)
        (let ((res ((f g ) n)))
          (display label) (display " ") (display res) (newline)
          res)))))

This simply passes through the previous steps, stores an intermediate value, and prints it using a label that's passed in. Here's how to use it.

(define traced-fib (Y (tracestep "fib" fibstep)))

Now if we run it for say "traced-fib 6"

> (traced-fib 6)
fib 1
fib 1
fib 2
fib 1
fib 3
fib 1
fib 1
fib 2
fib 5
fib 1
fib 1
fib 2
fib 1
fib 3
fib 8
fib 1
fib 1
fib 2
fib 1
fib 3
fib 1
fib 1
fib 2
fib 5
fib 13
13

Look at all of those steps!!! Clearly this sucks, and if you try something like (traced-fib 100) you'll be waiting for a long time for completion. It expands it's "recursion" via Y like a bomb!

How can we improve on this? Well without modifying fibstep, we could add memoization, so first I'll make a global memoization table (forgive the possibly poor choice of data structures here)

Memoization is a technique to prevent computing the same value twice, which we're doing a lot above per the trace. (Again this has been explained on the web a lot. Googling around for why may prove enlightening)

(define memoization-table (make-vector 100 0))

This is a vector of 100 0s. I'm only going to memoize 100 values of this computation statically.

So now I'll write the memoization step.

(define memoize
  (lambda (f)
    (lambda (g)
      (lambda (n)
        (let ((ref (vector-ref memoization-table n)))
          (if 
           (= 0 ref)
           (let ((val ((f g) n)))
             (vector-set! memoization-table n val)
             val)
           ref))))))

The indexes of the memoization table are the results of f(i), where i is the ith fibonacci number. f(1) = 1, f(2) = 1, f(3) = 2, f(4) = 3... etc

Basically once we compute a value for i, we insert it in the table, so we can look it up again. if f(i) is 0, it means we have to compute it yet, but we'll only do it one time.

So how do I stack all of this up with Y?

(define traced-memo-fib (Y (memoize (tracestep "fib" fibstep))))

or if you don't want tracing

(define memo-fib (Y (memoize fibstep)))

Let's watch it run for 6 now

> (traced-memo-fib 6)
fib 1
fib 1
fib 2
fib 3
fib 5
fib 8
fib 13
13

How about something bigger?

> (traced-memo-fib 8)
fib 21
fib 34
34

It didn't have to compute up to 13, so it just did fib(7) and fib(8). If we reset the memoization table (reload the program) we can see all the steps again.

> (traced-memo-fib 8)
fib 1
fib 1
fib 2
fib 3
fib 5
fib 8
fib 13
fib 21
fib 34
34

Compare this to the unmemoized fibonacci:

> (traced-fib 8)
fib 1
fib 1
fib 2
fib 1
fib 3
fib 1
fib 1
fib 2
fib 5
fib 1
fib 1
fib 2
fib 1
fib 3
fib 8
fib 1
fib 1
fib 2
fib 1
fib 3
fib 1
fib 1
fib 2
fib 5
fib 13
fib 1
fib 1
fib 2
fib 1
fib 3
fib 1
fib 1
fib 2
fib 5
fib 1
fib 1
fib 2
fib 1
fib 3
fib 8
fib 21
fib 1
fib 1
fib 2
fib 1
fib 3
fib 1
fib 1
fib 2
fib 5
fib 1
fib 1
fib 2
fib 1
fib 3
fib 8
fib 1
fib 1
fib 2
fib 1
fib 3
fib 1
fib 1
fib 2
fib 5
fib 13
fib 34
34

Yikes! That's a lot of waste there.

What I've been able to do with Y is write steps of a computation in near isolation of each other, and then compose them with Y to form a useful function (arguably... it's just fibonacci) to optimize and augment behaviors by weaving them together.

Now I'm not sure what this means for Y in terms of practicality, but it's kind of neat. Obviously one has to obey certain rules to use Y compositionally, but it's totally possible for some classes of problems. I'm not sure how my coworkers would react to my using this in any sort of production code. Could anyone read it? :-)

Ah well, that's why this blog is just stuff that interests me.

A few random thoughts

In conversations with people, it occurs to me that the concept of Functional Programming really scares some folks off. I feel this is the effect of the object oriented paradigm having been shown to be the almighty hammer and the whole world to be a nail. Shame on us.

It's interesting to note that people often know more functional programming than they may even know. Take the C++ STL for example. It's all in generic algorithms that apply an outer-most layer of an algorithm, requiring the coder to specify the smaller steps that make the outer-most algorithm mean anything useful at all. In C even, we have qsort and mergesort as standard calls. These are a great start to addressing the "who needs Functional Programming?" question.

The Standard C Library's qsort is a well documented and useful sort function with some very interesting properties, or no one would even care about putting it into a library. Implementing it correctly the first time, from memory is not likely to happen, so to save us time the library has implemented all of the tricky outer-logic for us, requiring us only to provide a pointer to a function that implements the comparison function that will be used to determine if one item in the collection being sorted is less than, greater than, or equal to another item.

I do not think anyone can argue that this is not a very powerful concept. With this, one can create an arbitrarily complex data type, and as long as one can specify the comparison criteria, one can "implement" qsort, without doing the heavy lifting. Isn't that what OOP was supposed to provide? Is this not the same re-use goal we all want in libraries to begin with?

Note that this means one can also "lie" to qsort about what value should come before the next, and by simply making the compare function return the swapped values for a less than comparison for the value returned for greater than, one can reverse sort a collection (descending order vs ascending order), again without writing all the outer-most, and more complex qsort code.

How great is that?

STL and C++ standard libraries let one define the "allocation" step for geting more memory as a separate "policy" from the rest of the code. I've written my own C++ compliant allocators that allow for getting memory from "mmap" instead of malloc, and then run benchmark tests against each just for fun. The algorithms for the collections are the same code, and the only difference is dropping in a template parameter for the allocation class. This, even though it's C++, is not solely the domain of OOP languages. In fact, Functional Programming is meant for this kind of flexibility.

Is there any wonder now why people claim that Functional Programming is about managing complexity by thinking about operations rather than the data?

I've written a good bit of Erlang code over the last 2 years, and there's no mutable variables (sort of) in that language, so in order to do a replace of a value in a list, I have to basically emit an entirely new list with the value in question updated. Well I could have written all the code to do that myself using primitive recursion, and subtraction until a value for an index reaches 0 or 1 and then changing the value in question, and appending the rest of the list to it, but with functions like "foldl" and "foldr" that's not necessary. I can just write the "guts" of the algorithm, and let the collection traversal of the list be handled by a well-defined, and reusable function. Sure for lists this may seem a trivial operation, but consider that one could use a fold function over a tree in a few different traversal orders, and I think one can begin to see the power of this approach.

If all of that evidence doesn't turn one on to at least appreciating Functional Programming, perhaps just looking at the sheer growth in popularity of well respected software institutions, and the application of Functional Programming to mission critical software could convince one to give it a second look.

Get by with a little help from my friends...

I've had two random people express an interest in the 9P in Haskell stuff I've been thinking about, for similar reasons. Tim Newsham went as far as to write a bunch of code for encoding/decoding of 9P messages to ByteStrings and mailed it to me.

I'm not 100% sure it's 100% correct, but it looks darned good, and far cleaner than what I'd written, so I've used it in place of mine at the 9ph project page.

I've attempted to port my version test code (sends a 9p version message to a styx server on Inferno) to see if that works, but I'm not sure that the string type is being handled properly for the TVersion message, where it must be prefixed by a little endian encoded 16 bit integer for the protocol version being negotiated ("9P2000" in our case).

Still 9P in Haskell looks like it will be useful for several folks, and I'm glad for that, even if I don't get mine done.

Prime Sieves again

Well I've been playing with libdispatch quite a bit lately now. Apple just open sourced it here, and I hope linux/BSD folks figure out how to adopt it, because it's really cool!

I took my pipe based CSP-like prime sieve, and at the prodding of my friend Kevin at Apple, rewrote it so that the blocks themselves contain the "message" and the queues contain the context I'm interested in. This is in contrast to the pipe fd's being an event source to fire a block, and the fd itself having the context once it was an event source object.

This meant re-structuring the code a bit, and capturing the value I would have written to the pipe in the block's closure. To do so I opted to make a function as such

// Runs a block asynchronously on a queue
void run_block (dispatch_queue_t q, int cur_num) {
  dispatch_async(q, 
   ^{
     struct context * ctx = (struct context *) dispatch_get_context(q);
     
     if (cur_num == LAST) {
       if (ctx->has_spawned == 1) {
         run_block(ctx->neighbor, cur_num);
       }
       dispatch_release(q);
     } 
     else if (cur_num == ctx->mynum) {
         printf("%d\n", cur_num);
     }
     else if (cur_num % ctx->mynum != 0) {
       if (ctx->has_spawned == 0) {
         ctx->neighbor = create_queue(cur_num);
         ctx->has_spawned = 1;
       }
       run_block(ctx->neighbor, cur_num);
     }
    
   });
}    

(Full source here)

I had someone tell me #define'ng MAX was bad, and I wanted it to be a command line argument anyway, so I made it so. (here)

Now this version runs pretty nicely, but all that block copying overhead is causing a lot of malloc'ng memory for const copies of contexts. Seems a waste. My friend Kevin pointed this out to me and said "try the async_f APIs".

These take a function pointer rather than a block. It's easy enough to convert this block to the function pointer form:

void worker (void * fctx) {
  int cur_num = (int) fctx;  // bad bad bad, but I don't care.
  dispatch_queue_t cur_q = dispatch_get_current_queue();
  struct context * qctx = (struct context *) dispatch_get_context(cur_q);
  
  if (cur_num == LAST) {
    if (qctx->has_spawned == 1) {
      dispatch_async_f(qctx->neighbor, (void *)cur_num, worker);
    }
    dispatch_release(cur_q);
  } 
  else if (cur_num == qctx->mynum) {
    printf("%d\n", cur_num);
  }
  else if (cur_num % qctx->mynum != 0) {
    if (qctx->has_spawned == 0) {
      qctx->neighbor = create_queue(cur_num);
      qctx->has_spawned = 1;
    }
    dispatch_async_f(qctx->neighbor, (void *)cur_num, worker);
  }
}

Now when I run my for loop it looks like this:

for (x = 2; x <= max; ++x) {
    dispatch_async_f(two_q, (void *)x, worker);
  }

What is very interesting to look at is the pipe version's performance, vs the block copy, vs the function pointer version.

Sieving all the primes from 2 to 9000 with the file descriptor version:
1.68s user 5.05s system 171% cpu 3.929 total

With block copy:
0.24s user 0.02s system 118% cpu 0.219 total

With function pointers:
0.06s user 0.02s system 78% cpu 0.098 total

It's hard to do a lot of sieving with the file descriptor version, because you have up your ulimit, and it hits the kernel a lot (see the system time of 5.05s, vs 1.68 user time!). To demonstrate how much faster the function pointer version is compared to the block version, we need a larger range.

Here's results for 2-90000

With block copy:
14.52s user 0.21s system 161% cpu 9.119 total

With function pointers:
2.66s user 0.15s system 130% cpu 2.156 total

Look at that speedup! Note how very little time is spent in the kernel making system calls.

Not too shabby.

One thing I did find out is that dispatch_async on a queue that has not set it's own target_queue to the main queue, will create a TON of threads. I had up to 179 at one point. Once I added the following line to the queue creation function I wrote, it stably stays at 4 threads:

  dispatch_set_target_queue(rv, dispatch_get_global_queue(0,0));

This was again advice given to me by my friend Kevin at Apple.

Thanks Kevin, this has been enlightening!

Last bug found

Kevin spotted this before I did, but I'm afraid it's not quite what he thought. I was using calloc to allocate a context for an event source, but part of that context was initialized after the block's context was created. This lazy initialization of the context caused me trouble in that I was writing a -1 to stdin (0, because I used calloc should have been stdin, but it was making ???? appear at the console).

At any rate the completed, and corrected code is here.

Kevin went on to inform me that I don't need the semaphore and task counter because I can just use groups and group synchronization on the dispatch_objects that are sources. He sent me some code, and I'll probably take a look at it, but for the purposes of demonstration I think this code is basically final. (Groups do make sense to use here however as there's less manual book keeping, and that's part of the advantage of libdispatch and GCD).

A simple solution?

Well that crash I caused is partially due to my own terrible error handling, and the fact that I didn't boost my ulimit for file descriptors (I am using a good bit of pipes in my process, but my per-user limit is ridiculously low!!!).

Upped the ulimit to 2048 from a pathetically low 256 and now I can get through a lot more prime numbers before barfing. (It's a laptop man! I'm the ONLY user...)

A rather big part of this is that I'm using pipes for communication between event sources, which fire off my blocks. There's exactly one pair of fd's for every prime I find, plus all the fds in use under my uname.

More libdispatch fun

Been playing with libdispatch of GCD from Snow Leopard for a few days now, and I'm having a heck of a time with a demo program I've been writing that's just not working for me yet.

In fact, today while trying to make the synchronization happier (and succeeded), I realized I'm getting some junk out on stdout. After trying to figure out exactly why this is happening by tweaking the code and rebuilding it, I managed to panic the kernel.

The code is still at lisppaste.

Adventures with libdispatch

Apple released Snow Leopard to the world last Thursday, and with it came this interesting piece of technology called Grand Central Dispatch. It totally changes the way C, C++, and Objective-C programmers will approach concurrency and threading if they were used to anything at all like pthreads.

Having built up a bit of a functional programming background for myself, I'm no stranger to new ways to do concurrent programming. Scheme has its ways. Haskell has a couple of ways (explicitly forkIO'ng sparks that might be run on threads, or data parallelism). Also, I've tinkered with such things as typed data channels in Limbo from the folks at Bell Labs (seemingly inspired by Newsqueak by Rob Pike and CSP itself).

When I first looked at Grand Central Dispatch from Apple, I was a bit puzzled by the API. There's queues, event sources, asynchronous dispatching, and this interesting feature they've added to their implementation C language (though some of my fellow 9fans have been somewhat outspoken against it) called blocks. Blocks are closures for C. If you want to know more about closures consult a good book on Scheme or a Scheme tutorial. (or Lisp!)

I'm more used to a CSP-like programming interface, and I wondered if I could port a rather famous demo in Newsqueak, and Limbo to this interface. It's a Prime Number Sieve (Pike?).

The algorithm may be explained as such (poorly?):

1. Create a channel of integers
2. Start a process that puts onto the channel from step 1 all the numbers from [2,N]
3. Start a process that reads from the channel all incoming numbers. The first number read is "special" and becomes that process's special number. This process prints it's number and creates another channel of ints, that it will feed all numbers that fail the test (incoming_number % my_special_num == 0). In this way it filters out all numbers that are multiples of it's special number.
4. Start another process and feed it the first number that passes through this filter.... the new process follows the same step 3 as above.

This creates us a sieve that only lets prime numbers escape.

A good animation of how one works is here.

My prose is rather lacking, so without further ado, here is the code I came up with to try to approach a prime number sieve, using pipes, and blocks, and libdispatch routines to concurrently schedule the sieve on my mac.

// David Leimbach
// September 4, 2009
//
// First, unclean attempt at a prime number sieve in C with libdispatch
//
// Special thanks to Kevin Van Vechten and Jordan Hubbard for guidance through this new API!
//
// Thanks to Apple for making Snow Leopard so affordable!

#include <dispatch/dispatch.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/uio.h>
#include %lt;unistd.h>

#define MAX 300

struct context
{
int mynum;
int has_spawned;
int writefd;
};

void setup_block(int read_fd) {
dispatch_source_t piperead;
struct context * ctx;
piperead = dispatch_source_create(DISPATCH_SOURCE_TYPE_READ, read_fd,
        0, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0));

ctx = calloc(sizeof(struct context), 1);

ctx->has_spawned = 0;

dispatch_source_set_event_handler(piperead,
        ^{
          int val;
          int fd[2];
          struct context * ctx = dispatch_get_context(piperead);

          read(read_fd, &val, 4);

          if (ctx->has_spawned == 0) {
     pipe(fd);
     ctx->writefd = fd[1];
     ctx->mynum = val;
     ctx->has_spawned = 1;
     setup_block(fd[0]);
     printf("%d\n", val);
          }
          else {
     if (val % ctx->mynum != 0) {
       write(ctx->writefd, &val, 4);
     }
          }
        });

dispatch_set_context(piperead, ctx);  // associate this state with this context
      
dispatch_resume(piperead);
}


void run_sieve(int writefd) {
int x;

for(x=2; x <= MAX; ++x)

   write(writefd, &x, 4);

   sleep(2); 

}  

int main () {

    int fd[2];

    pipe(fd);

    setup_block(fd[0]);    

    run_sieve(fd[1]);    

    return 0; 

}

 (Please forgive the code formatting, I'm having great difficulty with blogspot on this stuff with their editor)

Plan 9 machine running

Erik Quanstom's 9atom.iso build of 9load correctly finds my motherboard specifics and can install a Plan 9 system on my old machine making it such that I don't need to buy a new one. (hooray!)

In the process of figuring this all out, I learned that a Google SoC project "9null" can use Plan 9 to boot Plan 9 directly, rather than 9load which is a significant subset of plan 9 to boot plan 9.

Seems like this should just be easier for the smaller Plan 9 community to maintain. I've not tried 9null out yet, but I'm pretty anxious to give it a go.

This weekend looks like it might be a good time for some of those side projects.

EDSL done...

The expect embedded Domain Specific Language portion of my code has turned out to be quite the useful little sublanguage to flexibly write little scripts in for controlling, over various channels (ssh, telnet, local comm ports perhaps), devices.

I probably can't document too much about it here, as it's company IP, but I can tell you that building up an EDSL in Haskell is not near as difficult as I thought, at least in the case I've implemented. It's a matter of choosing the right Monad Transformer base, or writing your own (which could take a long time actually depending on how well you can wrap your head around the sequencing of the various actions you'd like to take). Also once you realize that the aggregation and sequencing of simpler actions can be used to build up more complex ones, you're pretty much golden and have learned to realize the full power of the Monad concept.

It's also one thing to see it, or even read about it, but the real eye-opening bit is when you actually implement one that's useful to you on your own. Then you almost want to beat your chest and proclaim you're the new king of the tribe.

I love a programming language that you can use to build specialized tools ,*very* quickly, that meet your immediate need.

My boss even almost threw me a curve ball on the way he thinks I should utilize this technique. Then I realized that what I'd written could most easily support the sort of idea he was after because I picked the right abstractions.

I'm very grateful that this technology even exists, as it is saving us a lot of time where I work, making progress on this sort of programming that otherwise seems a ton of work.

Haskell is definitely for the win today :-)

Haskell and DSLs

One of the great features of Haskell is the ability to write programs that execute in contexts that are separate from the rest of your program. Monads are one of those kinds of contexts, and a monad allows you to define exactly what happens when you sequence different expressions within a context. Using this, one can write little imperative DSLs (Domain Specific Languages) that execute along side the rest of your Haskell code.

There's DSLs for controlling "robots" in Hudak's Haskell School of Expression book. There's a DSL that is a "vintage basic". There's another one for controlling small realtime systems called Atom.

The possibilities seem endless.

I've been considering making one of these as a replacement for the old Unix program expect, or at least a subset of it that I'm interested in. Haskell's already got very strong regular expression libraries, and some of the best parser writing libraries I've seen. Having something like the expect syntax for interacting with remote services or devices would be excellent in conjunction with those other capabilities.

I found a tutorial online today about DSLs that seems pretty good. We'll see if I ever get to the point of implementing one.

Interesting Discussion

I've been talking Monads with folks on haskell-cafe as well as lazy-IO, and understanding strictness and where it sometimes needs to be sprinkled in to get the behavior desired from a lazy IO system.

This is sort of the price paid for wanting to completely separate one's pure data processing code from IO. The advantage of having this separation is of course in testing of code, in that pure code has referential transparency, meaning that you can call it any number of times you like, and as long as you provide the same X for input, you will always receive the same Y as a result.

By putting Input and Output operations into their own context of evaluation, we totally avoid certain classes of problems in software writing, so the effort seems worth it.

Needless to say it's been an interesting discussion, linked here.

Posixy stuff and Haskell

The GHC Haskell compiler and library set it comes with has a nice bit of POSIX functionality. Today, however, I found myself really wanting for a program that could popen a program, giving me back a pair of handles to communicate with the external program, and allow me to do Expect-like things with the interaction.

Essentially I need a bot. The bot needs to talk to a device that speaks SMASH CLP, and my initial thoughts were to write some Haskell code around the useful function interact, or rather, a close relative of interact.

Interact has the signature

interact :: (String -> String) -> IO ()

This just means that it takes a function which takes a String as input and produces a String as output, and the result of interact is an IO action that returns ().

What this gives me is the ability to process input strings, to produce output strings, which get read in and written out by the IO action that is the result of interact. It interleaves the pure functional processing around the input to create output.

The way it works is by calling the function getContents, which lazily reads all the input from stdin and processes it through the provided (String -> String) function, to produce output.

At first glance, this is not seemingly a very advantageous function, except when you take into account all the ways you can set up the IO before calling interact to get some nice behaviors.

For example, if one sets the handles for stdin and stdout to "LineBuffer" based buffers before calling interact, you can get linewise input by doing the following inside the (String -> String) processing function.

lineId = unlines . lines

The function lineId breaks up the lazy input string into lines, then re-assembles them by composing the function lines and unlines together.

The type of the function lines is:

lines :: String -> [String]

The type of the function unlines is

unlines :: [String] -> String

One would think that these two functions would just negate each other, and they do when combined as "unlines . lines" returning the original input to lines, however, if I add further behaviors to the function composition expression that operate on the [String] result of lines before running unlines I have the opportunity to work on each member of the list.

This gives me guaranteed linewise input evaluation of commands, and the ability to interpret line-oriented protocols, strings or what have you.

Now think of how useful interact can be?

Now, interact by itself is only dealing with stdin and stdout. Perhaps I want to open a connection to a remote service, or even a stream of in and out data. It is not terribly hard to write a relative to interact that can handle those sources of data.

hInteract :: Handle -> Handle -> (String -> String) -> IO ()

hInteract inp out f = hPutStr out . f =<< hGetContents inp

This function can take a handle for input, a handle for output, and a function of String -> String, and uses them to lazilly read input from the input handle, pushing data through the String -> String function, to finally output the result string to the output handle.

All of the interesting parts of this function are still contained in f.

The part that's kind of exciting now is that I don't have to limit myself to just line based input if I consider using functions like words and unwords.

I think I'm nearly ready to write an almost IO free, pure version of my Expect-like code bot in Haskell.

Keepin Busy

Been trying to get a handle on "nice looking Haskell" network code. I've got some tasks at work that might actually require me to do some network coding in Haskell so that feeds nicely into my 9p implementation in Haskell, but, at the same time, I'm very concerned about data sizes and understanding how Haskell programs garbage collect, and understanding the waxing and waning of data allocation sizes in a lazy language.

I've not revisited 9p in general in a while. Still hoping to get a native Plan 9 box up and running somewhere that I can play around with.

I do want to get back to this project though. Every once in a while, I look at things like Facebook's Thrift, or other RPC mechanisms that are meant to be language neutral, and I think "this could have been 9p". It's interesting to try anyway just to understand the limitations of one thing vs another.

Need a new machine

I recently posted to 9fans that I think I would like to get a new dedicated plan 9 box.

Here's my wish list:

• Small footprint
• Low power consumption
• Connection to a large amount of storage, perhaps a 1TB disk external if I can configure it as such.
• Good Plan 9 support
• Low cost

I'm finding people are migrating towards dual core Intel Atom boards. This seems like a reasonable start. SATA disks would be nice, and Solid State Disk (SSD) would be even better on the SATA interfaces. Sound support is really not needed, as I'm never in my office, and there's plenty of good USB sound devices out there it seems, like these Turtle Beach Audio Advantage Devices. So adding that later isn't going to be very difficult.

I was kind of disappointed recently to find my old trusty AMD box's CMOS battery was dead, and that I had to do a lot of interesting memory searching to remember some of the configuration I had in the BIOS to even get FreeBSD running again. Then when I tried to load a recent Plan 9 (new 9load based) it wouldn't even find anything to boot from but bios0 and fd0.

This machine's floppy drive is shot, and bios0 is the first hard disk in the machine, so that's not going to work when I'm trying to boot/install from a CD....

The key is I've got to get a low-cost machine... I just don't have a ton of money to throw around these days.

In the meantime I've been doing well with VMWare Fusion 2.x on Mac OS X to get a terminal server running. But I don't like using that for long term stuff.

One day, I might see what it would take to get Plan 9 ported to what seems like will be inevitable quad core ARM servers. Then perhaps I'll take a swing at a port. Plan 9 seems like a great OS for a platform such as that. Might be easier to get Inferno going though depending on the hardware.

Fun Distraction

As you can tell I like Plan 9. I recently have been trying to catch up with the latest developments in that OS. There's been a new USB driver, new 9load bootloader (which probably ought to be replaced with just the main kernel, and that is currently a summer of code project for google), and linuxemu.

That last one is really interesting. Apparently Russ Cox, and cinap_lenrek have each taken a swipe at making Plan 9 emulate Linux system calls. This is pretty cool in that we can now run a lot of linux programs directly on plan 9, and, in fact, are able to even run Debian complete with apt-get inside a little sandbox.

On top of that fgb actually ported an X11 server to APE (the POSIX compatibility layer for Plan 9) to use libdraw as a graphics backend. (it's called "equis"). Put that together with linuxemu and you can run Mozilla, Firefox, Opera etc, right in Plan 9.

I got some help getting it up and running from cinap, and after getting font files I was missing, I've got Mozilla up in Plan 9. I told him I was reasonably impressed with the speed, though he informed me that each Linux system call ends up being 4 on plan 9. I'm not sure what can really be done about that at the moment, but this instantly gives plan 9 users a capability they didn't have before - reasonable web browser access.

Now I wonder if when Google's Chrome OS comes out if we'll be able to use that and not need X at all....

Not quite dead

http://code.google.com/p/9ph/ is where I've stored what I've got so far for my 9p in Haskell implementation. It's incredibly larval, if not fetal at this point and doesn't do much.

In fact, I'm not even convinced I like what I've written at all so far, but it is true, that I can negotiate the TVersion/RVersion client-connect requests of a 9p2000 client to a 9p2000 server.

I've been having a very busy summer, full of family fun, and various work projects. I've been having to spend any of my extra time that does crop up on work related work as there's always more to do...

I'm still hopeful for this project, plus the new capabilities of cross compiling Haskell code from the JHC compiler to the iPhone (it can use a gcc backend that is the native iPhone compiler). If JHC would support more of GHC's capabiliteis, I'd be in business to do some interesting 9p related projects from the iPhone to varying Plan 9 or Inferno or any 9p2000 service.

It's rather exciting really. Especially when you consider how I'd really like to have a litghtweight IRC filesystem client (uses 9p2000) to my Inferno box, running on a Linksys router. Two lightweight systems running a distributed application with a sane protocol in between == beauty.

... I'll get there one day.

Success

Made progress on Tversion/Rversion comms. It works. It was a matter of using the correct decoder... big D'oh, on my part.

Next is the hard stuff.

And first I have business travel to contend with, for the first time in a while.

Progress

Sometimes I just need to RTFM closer.

I just discovered the problem in my 9P haskell lib is really just that the data portion of every 9p "s" message has it's own size header (16bit).

Tversion encode and send now works via Nine.hs as a client. I am able to get the Rversion reply back and verify that it is NOT Rerror, but only visually by inspecting a hex dump as my instance of "Binary" does not succeed in "get"ting the response appropriately.

Still, I consider this progress.

I've decided to call this little project 9ph for now, (9p in haskell)

Progress

With much help from folks on haskell-cafe, I've got a basic utility Haskell module under development (Nine.hs) for trying to make unauthenticated connections to Styx servers from Haskell.

So far it's not quite right, but I can marshall a little-endian encoded stream of a Tversion message (I think... need to debug on the Inferno side a bit too.)

More later, hopefully.

What I'm up to at least dreaming about doing.

For the last year or so I've been following and writing some code in the Haskell programming language, specifically using the GHC compiler, on Mac OS X, Linux and Windows. I've been using it in simulations at work for a remote computer hardware management system we've been developing, and it's been quite fruitful.

Also, we've been developing a management software package at work that deals with namespaces of resources rather than a static class library Object Oriented Model, which can become very difficult to design appropriately or extend as the needs of the organization, and our customers, evolve over time. We aimed to make a project that uses a very simple interface to complex management systems, and I think we're succeeding quite well.

On top of all of this I've also been coding in Erlang for a bit of time now (about 2 years and 1.5 of those professionally) and I've found that designing systems as if they're distributed from the get go really helps one fit into the new trendy SOA models everyone wants you to think about in industry these days (It's just client server architecture with a lot of marketing as far as I can tell).

I've also been using systems based on a distributed design like Plan 9 and Inferno as much as I can work them into my life these days. Sadly that seems to have fallen back to *only* the use of an IRC file system for Inferno - a cool concept, think about how the popular UNIX "screen" program works with sessions you can detach and re-attach to, but do it over a system-wide ubiquitous file system protocol (9p).

I've worked with 9p client libraries written in C, Python, Java and other languages, but I've yet to see on for Haskell or Erlang for that matter. Perhaps someone should do something about that... (perhaps I will, time is not something I have an abundance of for this stuff these days).

One thing I would love to be able to do is fire up an iPhone application that had an embedded 9p client, and connect to the irc file system and use it. Another interesting approach would be to try to implement the Octopus client on the iPhone OS, and just use that to connect to running programs on a centralized server.

These days I wish I could just take a paid sabbatical from work and do these things, as spare time is hard to come by.

Purpose

Just a notebook of stuff I'm trying to do in my spare time, mostly for fun.