Cool Blog Title Goes Here

Object Relational Impedance Mismatch Thought

2011-04-07T09:15:00.001-07:00

Stop trying to make a serialized form of data the same thing as the "live" data. Serialized data is a recipe for the live data, not the same thing.

Solving a problem can be easier when you realize the question was incorrect to begin with.

I don't think of programs running in memory to be the same thing as the source code I wrote either. There's too many steps between my fingers, the disk, the compiler, and the OS that can make this assumption horribly wrong.

I realize that having the code eventually tell the computer to do what you mean is the point of a language, but we can't be naive to the way computers actually work, if we want to understand why this assumption can be dangerous and break down.

I feel this is a similar situation for ORMs. Perhaps the best way to code is not to pretend an ORM can be perfect.

I believe this is one of the things NoSQL will have taught us when we're all ready to jump on the next "new hawtness"

The D2 Programming Language

2010-12-14T09:01:00.001-08:00

Just began looking at this one last night. It's available, with source, from Digital Mars (http://www.digitalmars.com/d/2.0/), and it's quite interesting.

It is definitely a general purpose programming language, and addresses many areas where people want to pull out their hair with C++. It seems it can directly compete with Go (Google's programming language), in the areas of concurrency, has a system of generics and is what I would call a "more than complete" language :-).

It's actually pretty big, and many people might claim that you don't have to understand what you don't use. That's only true if you're the only one authoring code in this language, or have a set of restrictions to a subset of the language that you go by.

Go, on the other hand, is pretty small, and fairly simple. One can understand the entire language fairly quickly by just reading the specification. It's quick to learn, the tools are quick, and the code runs reasonably fast.

D2, at least with the Digital Mars compiler, is pretty fast too. It can be executed as a "script" of sorts, making it nice for system administrative tasks where you often need the source to be right there.

Both languages seem to do quite well at achieving their stated goals and philosophies, and I expect them both to become more important to know as time goes on.

I hope to see both grow in popularity in the not too far off future.

Dave

Goroutines vs function literals (closures)

2010-11-28T19:18:00.000-08:00

Goroutines are a kind of heavy way to deal with a situation where you just want some kind of lazy evaluation. Say I would like to process a file line by line and the basic guts of it looks like this with a goroutines:


func lineStreamer (out chan <- string) {
 file, err := os.Open("/usr/share/dict/words", os.O_RDONLY, 0666)
 if err != nil {
  panic("Failed to open file for reading")
 }
 defer file.Close()

 reader := bufio.NewReader(file)
 for {
  line, err := reader.ReadString(byte('\n'))
  if err != nil {
   break
  }
                // Do something interesting here perhaps other than returning a line
  out <- line
 }  
 close(out)
}

This greatly simplifies the act of opening the file, dealing with bufio, and gives me an interface I can just read lines from (or processed lines from) on a channel. But it seems kind of slow, running at about 2.04 to 2.07 seconds on my macbook pro with no runtime tuning. If I raise GOMAXPROCS to 2 I'm getting between 1.836 seconds to 1.929 seconds. GOMAXPROCS at 3 is getting me fairly regular 1.83 seconds.

This got me thinking about how I'd so something like this in other languages. I don't think I'd need coroutines to do it in Scheme for example, as I could do some delay/force thing to get stuff evaluated in chunks.

This led me to the following, possibly non-idiomatic version of a Go program using function literals.


type Cont func()(string, os.Error, Cont)  // string, error, and a function returning the next

func lineStreamer (file *os.File, reader *bufio.Reader) (string, os.Error, Cont) {
 line, error := reader.ReadString(byte('\n'))
 return line, error, func () (string, os.Error, Cont){
  return lineStreamer(file, reader)
 } 
}

To evaluate all the lines I can do something like the following:


 s,err,next := lineStreamer(file, reader)

 for err == nil{
  fmt.Printf("%s", s)
  s,err,next = next()
 }

And my run times are down to about 1.2 seconds.

I guess my question is, is this idiomatic or not.

OMG C++?

2010-06-01T23:31:00.000-07:00

I had an interesting problem to solve involving some code that was essentially driven this way:

while(getline(cin, string) {
   // process string
}

A coworker of mine suggested that this would only process a line at a time, which it will, but I was wondering if it was reading a line at a time as well as just serializing activity based on lines read. In essence I wondered if the input was buffered for cin.

On my platform I'm testing with, Mac OS X Snow Leopard, it appears that no buffering is really going on.

Here's some code to show what I mean:


void show_stats () {
    if (in) {
        cout << "Stream is broken or closed\n" << endl;
    }
    else {
        cout << "Availble bytes buffered: " <<cin.rdbuf()->in_avail() << endl;
    }
}

This looks at cin's underlying streambuf implementation and looks to see if there's any available bytes in the buffer. When there's no bytes in the buffer, the istream calls on the internal streambuf's "underflow" function to go get more data, and adjust the buffer for some number of "put back bytes".

What I found was that at no point was I seeing any buffered input coming in for cin, so I decided to write my own streambuf and subsequent istream classes to deal with both buffering and any file descriptor (unix pipe, socket, file etc).


#include <cstdio>
#include <cstring>
#include <streambuf>
#include <unistd.h>
#include <iostream>
#include <errno.h>

class fd_inbuf_buffered : public std::streambuf 
{
protected:
  int fd;
  const int bSize;
  char * buffer;

public:
  fd_inbuf_buffered (int _fd, int _bSize=10) : fd(_fd), bSize(_bSize) 
  {
    buffer = new char [bSize];
    // The get pointer should not be at the beginning of the buffer, because
    // it limits the ability to do put back into the input stream should 
    // there be a need to.  Ideally that situation does not come up, but we 
    // leave room for 4 bytes, by pointing all 3 locations to 4 beyond the 
    // beginning of the buffer.
    // 4 was the size used in an implementation in Josuttis' "The C++ Standard Library"
    setg(    buffer + 4,  // beginning of putback area
            buffer + 4,  // read position
            buffer + 4); // end position
  }

  ~fd_inbuf_buffered ()
  {
    delete [] buffer;
  }

protected:
  // Underflow is what fills our buffer from the fd.
  // if we don't override this, we get the parent, which just returns EOF.
  virtual int_type underflow ()
  {
    //read position before end of buffer
    if (gptr() < egptr())
    {
        return *gptr();
    }
    
    int numPutback = gptr() - eback();

    //must limit the number of characters previously read into the putback
    //buffer... 4 maximum

    if (numPutback > 4)
    {
        numPutback = 4;
    }
    // Copy up to the putback buffer size characters back into the putback
    // area of our buffer.
    std::memcpy (buffer + (4 - numPutback), gptr() - numPutback, numPutback);

    // read new characters
    int num;
retry:
    num = read(fd, buffer + 4, bSize - 4);
    if (num == 0)
    {
        return EOF;
    }
    else if (num == -1) {
        switch (errno) {
            case EAGAIN:
            case EINTR:
                goto retry;
        }
    }

    //reset buffer pointers
    setg(buffer + (4 - numPutback), buffer + 4, buffer + 4 + num);

    return *gptr();
  }
};


struct fd_istream : public std::istream
{
protected:
  fd_inbuf_buffered buf;
public:
  explicit fd_istream (int fd, int bufsz) : buf(fd, bufsz), std::istream(&buf) {}
};

Now I can declare an istream like so:


fd_istream my_cin(0, 1000);

Where 0 is the numeric file descriptor for stdin and 1000 is the buffer size in bytes.

Because I went with the standard IOStream library, as opposed to just writing C style IO directly, I can use it in the same way I'd use any istream. I can use it with iterators or algorithms from the standard library, and I can even use it with getline as you can see below.


void show_stats () {
    if (!my_cin) {
        cout << "Stream is broken or closed\n" << endl;
    }
    else {
        cout << "Availble bytes buffered: " << my_cin.rdbuf()->in_avail() << endl;
    }
}

int main  () {
    string line;
    while (getline(my_cin, line)) {
        cout << line << endl;
        show_stats();
    }
    show_stats();
}

In an example run, such as "cat /usr/share/dict/words | ./a.out" I see something like the following:


Availble bytes buffered: 12
Pinacoceras
Availble bytes buffered: 0
Pinacoceratidae
Availble bytes buffered: 980
pinacocytal
Availble bytes buffered: 968
pinacocyte
Availble bytes buffered: 957
pinacoid
Availble bytes buffered: 948
pinacoidal
Availble bytes buffered: 937
pinacol
Availble bytes buffered: 929
pinacolate
Availble bytes buffered: 918

showing how the buffer grows each time I make it read a certain number of bytes, and flows back down to 0. At 0 it calls underflow again, and I can get more data if available or when I hit EOF, I return that from underflow, causing the stream to terminate.

This stream will work for pipes, sockets and files as long as the file descriptor is provided to the constructor. Now because I have a putback buffer size of at least 4, I will have to have allocated at least 4 bytes in my streambuf to make room for the pointers to work properly. There are possibly better ways to deal with it, but for demonstration purposes, this works nicely.

C++ isn't always so bad after all. It just depends on how it's written.

Not usually a fan of IDEs... but

2010-05-31T10:15:00.000-07:00

I'm thinking of trying to use Leksah as my primary Haskell development environment on the Mac. I like that they seem to be willing to incorporate Yi as their editing environment to some extent, and I'd like to see where that goes.

PLT Scheme is easy

2010-05-26T21:06:00.000-07:00

Lots of nice frameworks too. A friend showed me some code he was working to use the Twitter APIs over http to look at people's tweets (if they're not protected).

I thought this was cool, it was 7 lines of code. So I thought I'd wrap it up in a GUI.

Keep in mind I'm NOT a GUI programmer by trade, and that this was my very first venture into PLT GUI programming. It's easy to pick up, and now I've got something hideous that works.

#lang scheme/gui (require net/url xml)
(define (u screenname) (string->url (string-append "http://api.twitter.com/1/statuses/\
user_timeline.xml?screen_name=" screenname)))
(define (f v) (match v (`(text ,_ . ,v) `(,(string-append* v)))
                (`(,_ ,_ . ,v) (append-map f v)) (else '())))
(define g (compose f xml->xexpr document-element read-xml))
;(call/input-url (u "omgjkh") get-pure-port g)

(define dialog (new dialog% 
                    [label "Twitter Screen Name Activity Grabulatrixatronulator"]
                    [width 600]
                    [height 100]))

(define textfield (new text-field% [parent dialog] [label "Enter a Screen Name"]))
(send textfield set-value "omgjkh")
(display (send textfield get-value))
(newline)

(define newframe (new frame% 
                      [label "Results"]
                      [width 1000]
                      [height 600]
                ))
(define tf (new text-field% [parent newframe] [label ""] [min-height 500]))

(define (appender los) 
  (cond ((null? los) "")
        (else (string-append (car los) "\n" (appender (cdr los))))))

(new button% [parent dialog]
                    [label "GITERDUN"]
                    [callback (lambda (button event) 
                                (let ((text (appender (call/input-url (u (send textfield get-value)) get-pure-port g))))
                                  (display text)
                                  (newline)
                                  (send tf set-value text)
                                  (send dialog show #f)
                                  (display "here")(newline)
                                  (send newframe show #t)
                                  (display "here2")(newline)))])
                                                  
(send dialog show #t)

Current Plan 9 Environment... and loving it!

2010-05-26T11:48:00.000-07:00

I've got a Plan 9 CPU server running in VMWare Fusion on Mac OS X Snow Leopard. I ran into a few problems with the setup of this as VMWare Fusion's emulation of IDE disks didn't agree much with Plan 9. Changing to SCSI disks made all the difference in the world.

I followed and updated a little the Plan 9 wiki's instructions on setting up a CPU/Auth server, and then used it with drawterm, a unix program that works like a little Plan 9 terminal to connect to CPU servers, and all was good.

There's a project out there called vx32 which implements a sandboxing/virtualization in userspace library that has been used for a port of the Plan 9 kernel. I grabbed the latest Mercurial snapshot of this code base, and compiled it (after patching it up so Snow Leopard didn't complain about the deprecated ucontext.h stuff), and now I have a Plan 9 kernel (almost, it's not 100% the same) running as a terminal to connect to my Fusion CPU server.

So, now what? Well I may take a crack at the port of the Go language to Plan 9... when I get time to do this again.

Developing for the iPhone

2010-05-19T09:17:00.000-07:00

The last time I used Objective-C, it wasn't 2.0. As such, I'm needing to brush up quite a bit on my skills. I'm not used to having the compiler generate my properties for me, or the dot syntax etc.

I'm also not a big fan of mixing garbage collection with no garbage collection, I feel that's a recipe for disaster, however I'm going to cautiously proceed anyway.

I will say that the Xcode tools have shown immense improvement since the last release. I wasn't a fan of them at all, and I was surprised that my muscle memory for emacs keybindings isn't wasted completely in the Xcode editor.

If I can keep my interest level high in this area, I may just splurge for that 99 dollar license to deploy applications.

No more Facebook for me.

2010-05-17T20:29:00.001-07:00

I decided I didn't want to be a part of their product...

Thoughts on Lazy Evaluation...

2010-05-10T12:50:00.001-07:00

... I'll do it later.

Stuff...

2010-05-10T08:36:00.000-07:00

So I got an iPad. I've had it about one month. I've been paying a lot of attention to the talk about how it doesn't do Flash, why it doesn't do Flash, how Apple is committing war crimes against humanity by disallowing applications authored in 3rd party tools etc etc.

As a developer who's spent a good bit of time working on different projects that scale from tiny little machines, to medium sized computers to giant supercomputing clusters (yes, I've been on several of the top 10 of the top500 list, writing software to squeeze performance out of them) I can tell you that flexible tool chains, great documentation, and great support do not always go hand in hand.

My opinion on that is that it's a bit sad that I won't be writing and running Haskell code on a non-jailbroken i(Phone|Pod|Pad) but that that's not a deal breaker for most people. Cocoa is a nice framework, with many years behind it making it great. Objective-C is a pretty cool language, (though I feel they should have kept it simpler, no garbage collection, all this automatic atomic update stuff can be confusing etc). Grand Central Dispatch and the libdispatch stuff is powerful, even in a raw C programming context, though some folks I know don't think it's well served to use it outside the realm of Objective-C. Having suffered programming with threads and locks, (even implementing my own locks on certain platforms) I'd say that this is a big step forward in thinking about concurrency and parallelism by means of organizing program code at a low level.

Yes, when you buy Apple's stuff, it's a bit more about doing things "their way" than doing things "your way". The limits Apple places on the hardware it supports with its operating systems, or the limits placed on programmers via the tool chains, are all really there for 2 reasons (in my opinion).

1. It keeps Apple from losing control of its own platform.

2. Apple can focus their engineering and support efforts on making a product that seemingly "just works" with all supported stuff, because the space of stuff to support is a lot smaller!

To me, neither of these things are inherently "evil", as some folks might like to convince you.

I should note I've used my iPad every day since I got it at least one time/day. To pay for it I began selling some of the stuff I intend not to need anymore, such as my old iPod touch, and my old laptop. So far it's been a great trade!

Just a thought or two on strictness

2010-04-14T07:46:00.001-07:00

I've noticed that a lot of times when it comes to profiling programs in any language, that it is often surprising where the big cost centers are. Maybe it's just due to experience, but a lot of times I at least feel like I'm not as surprised in imperative languages when I recognize a cost center or my tool chain does. With functional languages, I'm often surprised that certain implementations of functions are as costly as they are, while others are not. This is even more true in "lazy" functional languages like Haskell.

When you're dealing with strict evaluation by default, you can basically just read the program top down and get a good idea for what happens when, and how data much a particular chunk of code ought to be using, and for the most part you'll get this right with experience.

With a language like Haskell, sometimes, all bets are off unless you know very well how a particular library of functionality is implemented. There's both strict and non-strict versions of Control.Monad.State for example. The non-strict version almost requires you to read the code, then think about how much stuff can be deferred to the last minute, and realize that those little deferred computations will have to be evaluated later. This can not only change the order of evaluation and thusly the data size of your program, but can also change the behavior a great deal.

Data.Map has operations within it for update that will be deferred (non-strictly evaluated) and some that are strict. It's important to read the documentation.

My advice to beginners is to try to understand strictness vs non-strictness (often called laziness) in Haskell as early as possible. It will give you great leverage to expressing some really beautiful solutions to problems, and save you from pulling all of your hair out or suffering any existential crises when trying to figure out why a program doesn't do what you thought.

All of that said, it's pretty easy for me to see why some people will decide that non-strict functional programming languages are not for them. It certainly takes a little mind bending to see the value in it if all you've ever done is imperative or strict functional programming, but I promise you the value is truly there. I also find that by challenging myself to learn how to think in these new paradigms I am simultaneously strengthening my understanding of the older paradigms a good deal more, so give it a shot and don't give up! There's help out there for you.

NineP is on hackage!

2010-02-20T16:54:00.000-08:00

I'm excited about it. There's still work to be done, but now I think there's a good chance to get a lot more feedback about the module as it's in experimental, and hopefully we can get some of these folks interested in distributed systems to use this nice, simple protocol.

9ph package for cabal/hackage

2010-02-19T20:35:00.001-08:00

The 9ph code repository now has a fully cabalized module, and I'm waiting on a response to get permission to upload stuff to Hackage. This will be my first shared contribution to the Haskell community, though all I've done is create a simple test program and some of the administrative work around wrapping this code up. If anyone likes this, the credit should go to Tim.

I've got some ideas for enhancements, and ways to make a nice server/client API on top of this lovely encoding/decoding library that Tim created on top of the very excellent binary package for Haskell and the lovely Applicative module.

9ph works!

2010-02-08T22:37:00.000-08:00

Finally, since last September, I've gotten around to messing with 9ph again. That's the 9P2000 implementation in Haskell that Tim Newsham basically wrote and sent to me to play around with.

I had started such a project on my own at one point, but Tim totally beat me to it, and rather than just re-implement the wheel, I figured I'd check out what he'd done and checked it in.

Today, I wrote a function that runs an IO program yielding a socket that's connected to a local 9P2000 server (or error'd out actually) running on 127.0.0.1:6872. From there I was able to create messages for Tattach, Topen, and Tread, and could explore the errors and successes of the server I was talking to.

For my experiments I just used the Inferno operating system with

"styxlisten -A 'tcp!*!6872' export /"

This just exports the local / namespace that the process running the styxlisten command can see to the world on TCP protocols listening on port 6872.

This library should be enough to write scripts for what is quickly becoming my favorite X11 window manager (if you must use one) wmii. wmii actually exposes a bit of functionality via a 9P server that you can mount from v9fs, Inferno, or any other 9P client. It'd be nice to be able to write some Haskell to configure wmii I figured, so this might be my first use for this library.

I'm hoping to get back to this again before long. This was good progress. I'm going to check in on Tim and see if he's got any more updates he feels he'd like to push. If not I'll just work from this fork.

Iteratee

2010-02-03T14:41:00.000-08:00

Iteratee really looks promising on paper, and people using it seem to think it's really great. I've been put off a bit by what looks like a rather complex interface, but decided last night to take a crack at it.

What I've written below is an iteratee wrapper around "cat /etc/passwd" output using runInteractiveCommand.

module Main where

import Control.Monad.Trans

import Data.Iteratee.Base

import Data.Iteratee.Base.StreamChunk (ReadableChunk (..))

import Data.Iteratee.IO.Handle

import System.Process

import System.IO

-- For some reason this signature is wrong, but I'm not sure why...

--handleDriver :: (MonadIO m, ReadableChunk s el) => IterateeG s el m a -> Handle -> m a

handleDriver iter h = do

result <- enumHandle h iter >>= run

liftIO $ hClose h

return result

main :: IO ()

main = do

(_, outp, _, _) <- runInteractiveCommand "/bin/cat /etc/passwd"

handleDriver (stream2list :: IterateeG [] Char IO String) outp >>= putStrLn

handleDriver just runs enumHandle with an iteratee (in my case stream2list) over the Handle, in blocks (not character by character) that are specified by the implementation, returning the result. That result is then printed to stdout by putStrLn.

This is a little bit like interact for Handle in that I could have used something more advanced than stream2list to process the result of "/bin/cat /etc/passwd".

I'm not too excited about the fact that I got the type signature on handleDriver wrong, and I'm also a little bit put off by the type signature on stream2list.

So what's the difference between this approach and an interact-like styled approach? For one iteratees work like the function that's supplied to a fold operation over a collection of data. In this case the collection is being produced dynamically via the enumerator. The iteratees themselves work like little parsers that can be composed in a monadic sense. Errors in IO and termination of a stream get propagated automatically up through the system nicely.

Why is lazy IO then not so great? Look at the signature for interact:

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

Interact is a function that takes a function of String to String and produces IO. This means it, ostensibly consumes all the input on stdin, applies the provided function to convert the whole String to a String, then prints that string to stdout. Now it doesn't have to read the whole of input in one shot, because of lazy evaluation. Strings are [Char], and the list structure in Haskell is non-strict in its construction. It's like pausing the construction of that list to do some processing on it, and going back to it with coroutines, except that the system is doing it behind the scenes.

What happens in interact when an error occurs? How does the pure function of type (String -> String) even know about exceptions in the processing? This is where iteratee is an improvement on traditionally lazy IO.

Let's assume we wanted to write a lazy version of interact for a handle called hInteract.

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

I believe this function could be used safely as follows:

withFile "/etc/passwd" ReadMode ((flip hInteract) id)

withFile uses bracket internally to ensure that hClose is called on the handle and all seems well. I don't think we necessarily understand how resources get used. Oleg, the father of Iteratee, posts this message a few years back explaining more of the benefits of Iteratee.

However, it seems that there is now a new lazy IO mechanism available that is safe. I've not had any time to check into this, but I plan to in the next coming days.

Having written an Expect-like Monad, I'm interested in the aspects of error handling and precise resource control, because the code I'm writing really needs to be able to run to as close to forever as I can get.

When types and definitions aren't enough.

2010-01-15T09:49:00.000-08:00

Was in #haskell on freenode a bit this morning, and someone mentioned something about how they were not exactly excited about the new rules for code formatting on if-then-else expressions.

I mentioned that I try to avoid if-then-else and case as much as possible by using types like Maybe that have 2 kinds of constructors, namely Nothing and "Just a" (for Maybe a).

I said that I can use the MonadPlus instance for Maybe a to get a lot of what is available in if-then-else clauses.

let x = someExpression

in if x == Nothing

then 9

else fromJust x

could be written as

let x = someExpression

in fromJust $ x `mplus` Just 9

mplus is defined for Maybe as evaluating the first parameter, and if it is not Nothing, it returns it, otherwise it will return the second parameter. It's essentially an "or" operator.

However, someone pointed out that there's absolutely no requirement for mplus to be written this way. It can still live up to all the rules and restrictions of MonadPlus by short-circuiting evaluation on the second argument instead of the first. Sure, it's sort of a de-facto first then second sequencing of evaluation, but it is not as safe as say "if-then-else".

I wonder now about the Applicative module as well, and specifically Alternative for the Maybe class.

I could just as easily write

let x = someExpression

in fromJust $ x <|> Just 9

But do we fall into the same trap of no guarantees? Is there a rule in Applicative enforcing the short-circuit of the first argument before the second?

Much code is written in the Applicative style for Parsec, so I really hope this is well defined.

What's Missing in the Haskell Community?

2010-01-11T07:08:00.000-08:00

Documentation is often sighted as possibly the #1 item that needs to be improved with respect to Haskell. It depends on what modules we use, but I have to agree. It's quite difficult to uphold the claim that you don't need to understand Category Theory in order to employ a Monoid or Monad, but when you run into Monoid instances like "endo" and don't know what to make of it because the documents don't really describe how to use it, you're probably going to suffer in that that implementation of Monoid is likely useful for some kind of programming that you want to do, and you'll end up struggling with a solved problem. Some people have been stepping up to improve the documentation, and that's really wonderful, but I think there's still some work to be done there.

The best way to learn Haskell in general for me has been to get the great books that are available out there. Real World Haskell is freely available online. (But please support the authors and get a copy if you're finding it useful). Search for Haskell on Amazon.com and you'll find that the reviews are a really good guide to picking which ones might be right for you. If you're really new to the language. Dr. Graham Hutton's book is outstanding. There's even been a series on MSDN's channel 9 walking through the chapters of this book, explaining how to solve some problems and think like a functional programmer.

To keep up to date with Haskell developments, reddit has been invaluable. You'll find blog posts, updates about new Haskell packages, and general community news and related discussion topics there.

So what's still missing?

I can tell you that over the years I've been messing around with Haskell, trying to understand how it works, why it's appropriate for certain kinds of problem solving, and to really get a good appreciation of why people seem to really like it so much, that I feel like the community has been pretty amazing with respect to fueling the flames of curiosity.

Where I think we might be needing a little more help is in the following areas of Haskell.

Explaining where laziness or non-strict evaluation is an advantage over strict evaluation. Perhaps this requires learning to think about the code we write differently, in much the same way it can be a leap to get to recursive programming, I feel this might be a slightly wider gap to cross mentally. (But then again maybe I'm just getting old... )

Show more examples of unintended data-growth or space leakage due to the lack of strict evaluation. In languages like C, you're in direct control of when memory is allocated or deallocated. This is generally considered a "bad thing" for a lot of tasks, including systems programming if you are signed up with the Go camp. A side effect of non-strict by default seems to be that you have to understand how the code you're writing will be evaluated from a bit of a wider view than you might need to care about malloc and free, or new or delete. It seems that unless you've somehow been taught how to recognize the patterns that could cause a a space leak, you're basically doomed to run into some sharp corners that others already seem to understand how to avoid.

Real World Haskell has a great chapter on optimization, but perhaps it's time for an "Optimizing Haskell" book too? There's lots of good advice scattered all over the web, and the experts are not shy to offer you help should you ask. Sometimes I think it's difficult to even ask the right questions when you're confused though, and I suspect this may turn some folks off to Haskell.

L4 and Plan 9 or Inferno or both?

2010-01-06T23:39:00.001-08:00

Some folks already started in on a Plan 9 port to L4 it seems (PDF), but I'm not sure how far they've gotten with it. I've been sort of peeping at L4 on and off for a long time now, and OKL4 has been successfully shipped in a few ARM phones, successfully being used to host Linux and a Qualcomm OS that drives the phone's radios and such. Neat stuff.

Been wondering if Plan 9 or Inferno and L4 are really a good marriage and what benefits could be added by leveraging Plan 9's namespace based resource management and L4's powerful IPC mechanisms.

As I've had a little more spare time lately, I've been digging around looking into L4 again, and I'm interested in exploring some ideas a little more deeply.

There's a few different implementations of L4 to look at...

OKL4 is now basically an ARM only platform in it's latest releases. Fiasco is a Pentium targeted L4 implementation that has a userland implementation that might be fun to work with (Fiasco-UX), and Pistachio is still being worked by at least a few people, with the latest changes coming in as of yesterday. Pistachio also supports a lot of architectures.

I'm tempted to play with each of these, but my problem has always been one of focus when it comes to these spare time projects as free time for me is usually at a premium.

Tim Newsham has been following the seL4 stuff, and OKL4 is migrating towards those APIs. His vote is I shoot for OKL4, so I believe that's where I'm going to start. There's a good community around that implementation, and a commercial pressure to keep things working nicely.

But as they say, talk is cheap... Let's see what I learn.

(UPDATE!)

Looks like a lot of progress was made by others who have already started this work!

Mouse editing... useful but not popular?

2009-12-16T08:10:00.000-08:00

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

2009-12-14T06:37:00.000-08:00

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?

2009-11-28T21:14:00.000-08:00

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

2009-11-11T06:14:00.001-08:00

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

2009-10-22T20:54:00.000-07:00

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!

2009-10-15T08:11:00.000-07:00

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

Nice!

I don't really know what to say..

2009-10-14T19:58:00.000-07:00

...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

2009-10-06T18:08:00.000-07:00

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

2009-10-05T14:27:00.001-07:00

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

2009-10-04T10:51:00.001-07:00

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...

2009-09-14T21:36:00.000-07:00

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

2009-09-10T23:31:00.001-07:00

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

2009-09-08T10:21:00.001-07:00

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?

2009-09-07T17:08:00.000-07:00

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

2009-09-07T14:36:00.001-07:00

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

2009-09-04T00:16:00.001-07:00

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?):

Create a channel of integers
Start a process that puts onto the channel from step 1 all the numbers from [2,N]
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.
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

2009-09-01T11:55:00.001-07:00

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...

2009-08-31T19:43:00.000-07:00

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

2009-08-25T18:55:00.000-07:00

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

2009-08-20T07:47:00.001-07:00

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

2009-08-18T19:53:00.000-07:00

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

2009-08-10T12:49:00.001-07:00

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

2009-07-14T16:53:00.000-07:00

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

2009-07-14T16:41:00.001-07:00

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

2009-07-08T09:10:00.000-07:00

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

2009-06-03T14:59:00.000-07:00

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

2009-06-01T21:48:00.001-07:00

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

2009-05-28T19:52:00.001-07:00

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.

2009-05-22T15:58:00.000-07:00

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

2009-05-20T13:50:00.000-07:00

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