It Seemed Like a Good Idea at the Time Coding, Mostly

20Aug/109

Announcing the UCL Portability Libraries

I spent the last year learning Haskell, and it is a very cool language. That said, I get the feeling that it also gains a gigantic competitive advantage from cabal-install and HackageDB. Package repositories and install tools for languages are not a new thing, but it was Hackage that made me realize how effectively a common package infrastructure can help to raise the popularity of a language.

And here's the thing: to a sufficiently fuzzy approximation, all the R6RS Schemes out there are interchangeable. They all offer a foreign function interface with roughly the same capabilities, they all offer the ability to launch and control subprocesses, and just about anything else can be built up from there. All of the cool things that can be built from these primitives, there is no fundamental reason they can't be portable.

So in April I started working on a set of portability packages, followed by an install tool, followed by a web-based package upload and browsing interface. And now it's all sufficiently done that I feel like I should release it.

So here you go.

Caveats

It supports Ikarus, Larceny, Mosh, Racket, and Ypsilon, at least on my machine.

The install tool could certainly use more features, like a package upgrade ability, code precompilation for the various Schemes, and complex version constraints on packages. The web interface is horrible code, and I'm just happy it seems to work as well as it does.

But what I am proud of are the simple but extensible package format, with myriad available extension points for new features, the simple repository format which allows anyone to start serving up packages if they don't like my offering, and the libraries which allow FFI and process manipulation to operate identically across Schemes.

Similar Projects

This code doesn't exist in a vacuum, and there are other projects whose scope overlaps with mine.

The most noticeable, to me, is Marco Maggi's Nausicaa, a gargantuan library distribution for R6RS Schemes. I regret to say that I have no experience using it, but the sheer number of libraries is impressive. I would like nothing more than to see some of those libraries available through UCL Install at some point.

The only other R6RS package manager that I have heard of is Dorodango. It does not seem to have been officially released yet, and if I understand the documentation correctly, it only supports Ikarus and Ypsilon at this time. It does have an upgrade command, unlike UCL Install at this point.  I envy the awesome choice of name, and I look forward to seeing what the author does with this one in the future.

Finally we come to Snowfort, an older attempt at a Scheme packaging system. I do not believe it is R6RS compatible, as it defines its own module system, and it appears to have no FFI or other portability layers, so I believe packages are limited to pure Scheme code. I would like to look at either manually or automatically porting some of these packages at some point, if the authors are amenable.

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)
Tagged as: , 9 Comments
11Apr/100

My Experience With STM32 Microcontrollers

For some reason, I never talk much about my embedded development projects, which is odd considering the large amount of time that I spend on them. I started learning embedded development stuff back in my sophomore year of high school with the AVR line of microcontrollers.

My Prototype Remote Controller

My Prototype Remote Controller

In my junior-senior year (it's a long story) I designed and built an embedded device to control NXT robots for the FTC robotics competition. I still have the original breadboarded prototype lying around.

But this post isn't about that, I was just providing some background information.

This year, IEEE@WashU has decided to build a light-up dancefloor, similar to the old one, but split into a set of modular 2-by-2-foot tiles for easier maintainability, upgradeability, and not-exploding-people-ability. Also it will have pressure sensing.

We were originally planning to run the floor with an ATMega at the center coordinating everything. Unfortunately, our first try at the inter-module communications was prone to noise issues. After much deliberation, we chose a scheme using ordinary UART signalling carried over LVDS between modules, with direct connections between neighboring modules. Unfortunately, that meant we needed a chip with 4 high-speed UARTs.

We ended up settling on the STM32 line of ARM chips, specifically the STM32F105. It has 5 UARTs, of which all are capable of 2.25 Mbaud. Also it has on-board ADC functionality, and runs nearly 4x as fast as an AVR at top speed. So it's a pretty nice chip overall.

The first big problem was packaging. Most AVR chips come in a DIP package, which is nice and friendly for hand-soldering. The STM32F105, on the other hand, comes in a QFP-64 package, which is quite a bit less friendly. For prototyping, I soldered one to a breakout board by hand. It worked, sporadically, for about half a week, but I'm pretty sure my poor soldering is to blame for the failure, either due to bad electrical connections or thermal damage.

But from what I was able to infer about the operation of a non-damaged chip, the STM32 line should be pretty fun to work with.

  • Like the AVR, it has extremely minimal requirements for external components. I ran it with power, JTAG, two blinky LEDs, and nothing else connected.
  • The STM32F10x Standard Peripheral Library contains a lot of useful functionality already implemented, although the function naming conventions are pretty ugly.
  • On-chip debugging is always worth it. AVR chips can do this too, but I never really bothered using it. Now that I've tried it on the STM32, I don't think I could bear blinky-LED debugging any more.
  • Lots of fun features:
    • 4x higher clock speed than AVR.
    • Two 16-channel ADCs
    • Two 12-bit DACs
    • Unique 96-bit device signature

Aside from the soldering issue, I believe that the STM32 line of microcontrollers is exceptionally hobbyist friendly, and should be pretty fun to work with once I get some non-damaged chips hooked up.

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)
15Dec/090

shsel – runtime selection of unix shells

In an ordinary SSH login, the shell selection mechanism is boring. You automatically get a single shell, and the only way I know to change said shell requires writing to /etc/passwd. Using chsh isn't even a possibility unless you're already in an interactive shell, and sometimes I want to create accounts on my machines that simply don't have that level of access.

So I wrote shsel, a handy little tool which allows me to specify multiple shells a user can choose from at login time. It's simple, weighing in at 100 lines exactly, and allows only the execution of very specific commands read from a configuration file. It's nothing fancy, but I was unable to find any combination of existing tools that would achieve the desired result, so it's nice to have a new program to add to my bag of tricks.

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)
Tagged as: , , No Comments
6Nov/092

Solving Logic Grid Puzzles in Haskell

The Zebra Puzzle is a decades-old exercise in deductive logic. Unfortunately, I lack the patience to sit down and solve this kind of puzzle. So in this post, we're going to cheat by teaching Haskell to solve it for us.

> import Data.Maybe
> import Control.Monad

We will take our cue from this solution written in SWI Prolog, and encode our puzzle as a set of constraints that our solving code must satisfy.

An 'entry' is a single entity in the solution. In the Zebra puzzle, these are going to be the individual houses. For maximum generality, we're just going to represent all the properties of the entries with strings.

An answer to the puzzle is a collection of several entities which together satisfy all of the rules set forth in the puzzle description.

> type Entry  = [String]
> type Answer = [Entry]

I was going to explain the rule types at this point, but the explanation ended up being a lot harder to understand than just looking at the rules for this puzzle, so we'll do that instead.

The first four rules simply teach our solver about numbers. After these rules are satisfied, the entries in the solution will be numbered one through five.

> rules =
>   [ Follows  [ "1", "",        "",       "",       "",       ""              ]
>              [ "2", "",        "",       "",       "",       ""              ]
>   , Follows  [ "2", "",        "",       "",       "",       ""              ]
>              [ "3", "",        "",       "",       "",       ""              ]
>   , Follows  [ "3", "",        "",       "",       "",       ""              ]
>              [ "4", "",        "",       "",       "",       ""              ]
>   , Follows  [ "4", "",        "",       "",       "",       ""              ]
>              [ "5", "",        "",       "",       "",       ""              ]

Then we specify all of the clues that make up the puzzle itself. These are given in order, so it should be easy to see the correspondence with the clues listed in the wikipedia article

>   , Literal  [ "",  "England", "",       "",       "Red",    ""              ]
>   , Literal  [ "",  "Spain",   "Dog",    "",       "",       ""              ]
>   , Literal  [ "",  "",        "",       "Coffee", "Green",  ""              ]
>   , Literal  [ "",  "Ukraine", "",       "Tea",    "",       ""              ]
>   , Follows  [ "",  "",        "",       "",       "Green",  ""              ]
>              [ "",  "",        "",       "",       "Ivory",  ""              ]
>   , Literal  [ "",  "",        "Snails", "",       "",       "Old Gold"      ]
>   , Literal  [ "",  "",        "",       "",       "Yellow", "Kools"         ]
>   , Literal  [ "3", "",        "",       "Milk",   "",       ""              ]
>   , Literal  [ "1", "Norway",  "",       "",       "",       ""              ]
>   , Adjacent [ "",  "",        "",       "",       "",       "Chesterfields" ]
>              [ "",  "",        "Fox",    "",       "",       ""              ]
>   , Adjacent [ "",  "",        "",       "",       "",       "Kools"         ]
>              [ "",  "",        "Horse",  "",       "",       ""              ]
>   , Literal  [ "",  "",        "",       "Juice",  "",       "Lucky Strike"  ]
>   , Literal  [ "",  "Japan",   "",       "",       "",       "Parliaments"   ]
>   , Adjacent [ "",  "Norway",  "",       "",       "",       ""              ]
>              [ "",  "",        "",       "",       "Blue",   ""              ]

Unfortunately, one drink and one animal are missing from the rules as stated, so here we just inform the solver "someone drinks water" and "someone owns a zebra"

>   , Literal  [ "",  "",        "",       "Water",  "",       ""              ]
>   , Literal  [ "",  "",        "Zebra",  "",       "",       ""              ]
>   ]

So we have three kinds of rules, for which we'll need a data definition. By now it should be self-evident how each of these work

> data Rule = Literal  Entry
>           | Adjacent Entry Entry
>           | Follows  Entry Entry
>           deriving (Show)

At this point, we have a nice, declarative specification of what a solution will look like, and we need to write the code to solve for it. The key to solving the puzzle efficiently is to realize that each rule is effectively describing some small portion of a possible answer, with empty strings representing unknown values. What we need next is a way to expand a rule into a list of all those answers that it represents

> expandRule :: Int -> Rule -> [Answer]
> expandRule n (Literal   a ) = [ expand n [ a ] x | x <- [0 .. n - 1] ]
> expandRule n (Follows  a b) = [ expand n [a,b] x | x <- [0 .. n - 2] ]
> expandRule n (Adjacent a b) = concat [e $ Follows a b, e $ Follows b a]
>   where e = expandRule n
>
> expand :: Int -> [Entry] -> Int -> [Entry]
> expand n rs@(r:_) x = replicate x blank ++ rs ++ replicate (n - x - 1) blank
>   where blank = replicate (length r) ""

As we go about solving the puzzle, we will at all times have a collection of answers the solver currently knows to be possible, and a set of answer fragments resulting from expanding the rule we're currently trying to satisfy. What we need is a way to test every possible combination of the old answers with the new answer fragments.

Our solution will make use of the nondeterminism monad, called the "list" monad by the unenlightened. As we iterate over the rules, we will expand each one in turn, test every possible combination with the old answers, and then filter out the impossible ones.

At first, this will cause a combinatorial explosion of possible answers, but as new rules are added, we will eventually reach a point where each additional rule manages only to decrease the number of possible solutions, until there is only one remaining.

> applyRules :: Answer -> [Rule] -> [Answer]
> applyRules answer rules = foldM applyRule answer rules
>   where applyRule a r = catMaybes [overlay a x | x <- expandRule (length a) r]

From the definition of applyRules, it is clear that our overlay operation needs to have type Answer -> Answer -> Maybe Answer. If any two answers are both defined and different from each other, we return Nothing, and otherwise we return the most defined of the two fields.

> overlay :: Answer -> Answer -> Maybe Answer
> overlay old new = sequence $ zipWith overlay' old new
>   where overlay' old new = sequence $ zipWith overlay'' old new
>         overlay'' "" ""  = Just ""
>         overlay'' "" n   = Just n
>         overlay'' o  ""  = Just o
>         overlay'' o  n
>           | o == n       = Just o
>           | otherwise    = Nothing

Before any constraints are applied, the answer is entirely undefined, so the process of solving consists simply of applying all the rules to an initial empty answer, and seeing what results. In this case, there is only one answer, but removing one or more rules from the list can make other solutions equally valid.

> main = showAnswers . applyRules emptyAnswer $ rules
>   where emptyAnswer = replicate 5 . replicate 6 $ ""
>         showAnswers = mapM_ $ mapM_ print

To see how each additional rule changes the set of possible answers, you can try something like "mapM_ print . applyRules emptyAnswer . take ## $ rules" in GHCi, for all the numbers between 1 and 20.

(This post is Literate Haskell, meaning that it can be copied and pasted in its entirety into a *.lhs file, and then run with runhaskell)

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)
Tagged as: , 2 Comments
14Oct/0919

Brian’s (Purely) Functional Brain

So about a week ago I came across an interesting post in which the author implemented the Brian's Brain cellular automaton in 67 lines of Clojure. Not about to let my favorite language be outdone, I thought I'd see how well Haskell would do with the same task.

Then I was kept horribly busy for a week by schoolwork, so a couple of days ago I started playing around with the problem. The results? Not too shabby!

So first of all, we'll be needing some imports. Since (for some odd reason) Haskell requires all imports up front, and since this blog post is supposed to be Literate Haskell, you'll have to just trust me that we'll need these for now:

> import Data.Array             -- Used to store the world state for processing
> import System.Random          -- Used to generate the initial random world
> import Control.Monad          -- Used for some fancy looping constructs
> import Control.Concurrent     -- Used to fork the quit event handler
> import Graphics.UI.SDL as SDL -- Used to draw the pretty pictures
> import Control.Parallel.Strategies

Cells can be either On, Dying, or Off:

> data Cell  = Off | Dying | On deriving (Eq, Enum)

For convenience, let's define some constants:

> worldX   = 90                -- The horizontal size of the world
> worldY   = 90                -- The vertical size of the world
> cellSize = 8                 -- The overall size of a cell
> border   = 1                 -- The border width between cells
> screenX  = worldX * cellSize -- The horizontal size of the world, in pixels
> screenY  = worldY * cellSize -- The vertical size of the world, in pixels
> fillSize = cellSize - border -- The size of the filled area in each cell

Cells progress from On to Dying to Off, and they turn on only when they have exactly two live neighbors.

> stepCell (On,    _) = Dying  -- Live cells always start to die
> stepCell (Dying, _) = Off    -- Dying cells always turn off
> stepCell (Off,   2) = On     -- If a dead cell has 2 live neighbors, turn on
> stepCell (Off,   _) = Off    --   Otherwise, just stay turned off

Since we know from the rules that we'll need the ability to count a cell's live neighbors, let's get that out of the way next.

> getPeers world (x,y) = (world ! (x,y), length . filter (== On) $ neighbors)
>   where neighbors    = [getCell x y | x <- [x-1 .. x+1], y <- [y-1 .. y+1]]
>         getCell x y  = world ! (clip worldX x, clip worldY y)
>         clip max val | val <  1  = clip max $ val + max - 1
>                      | val > max = clip max $ val - max + 1
>                      | otherwise = val

So now we have all the pieces to progress from one world state to the next. For each position in the array, we need to look up all its neighbors, count the live ones, and then pass that data to the stepCell function. The helper function indexArray creates an array of cell indices. We map over this array to generate new values for each cell.

The `using` parArr rwhnf  is some Haskell magic which causes the array to be evaluated in parallel:

> indexArray x y = listArray ((1,1),(x,y)) [(a,b) | a <- [1..x], b <- [1..y]]
> stepWorld w    = newWorld `using` parArr rwhnf
>   where newWorld = fmap (stepCell . getPeers w) $ indexArray worldX worldY

Now we have all we need to run a simulation, but it's not quite enough if you insist on getting some pretty pictures. For my fancy display purposes, I happen to like SDL.

The main function initializes SDL, generates a random initial state, produces an infinite list of future world states from that, and then draws each of the states in turn:

> main = do rng <- newStdGen
>           SDL.init [SDL.InitVideo]
>           SDL.setCaption "Brian's Purely Functional Brain" "Brian's Brain"
>           surface <- SDL.setVideoMode screenX screenY 24 [SDL.DoubleBuf]
>           forkIO . forever $ waitEvent >>= \e -> when (e == Quit) quit
>           mapM (drawWorld surface) (iterate stepWorld $ world rng)
>   where world = listArray ((1,1),(worldX,worldY)) . map toEnum . randomRs (0,2)

And our world drawing function is positively boring. We map over each combination of X and Y values, draw each one, and then flip the resulting image on-screen:

> drawWorld s w = do sequence [draw x y | x <- [1..worldX], y <- [1..worldY]]
>                    SDL.flip s
>   where draw x y = SDL.fillRect s (Just rect) . color $ w ! (x,y)
>           where rect        = SDL.Rect (scale x) (scale y) fillSize fillSize
>                 scale n     = (n - 1) * cellSize
>                 color On    = SDL.Pixel 0x00FFFFFF
>                 color Dying = SDL.Pixel 0x00888888
>                 color Off   = SDL.Pixel 0x00000000

To take full advantage of the parallelism in this program, you'll need to compile with the threaded runtime and run it on multiple OS threads.

ghc -O3 -threaded --make BriansBrain.hs
./BriansBrain +RTS -N2

And then just sit back and watch the mesmerising patterns.

This code is available on Hackage and GitHub.

Pretty Colors

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)
15Sep/092

Haskell While Loop

In the past week, while working on three completely unrelated Haskell projects, I have found myself in need of a while loop. So I came up with this one:

-- | For some reason Control.Monad doesn't provide a 'while'
--   function, even though it has a 'forever' function.
while :: Monad m => m Bool -> m a -> m ()
while predicate action = do
    b <- predicate
    if b then action >> while predicate action
         else return ()

Hoogle shows no functions with that type signature, and I couldn't find anything in the documentation that seemed to fit the bill. This seems like a rather fundamental function for getting stuff done, is there something I'm missing?

EDIT: The most code-golfed version I have yet come up with is while p a = p >>= flip when (a >> while p a) can anyone improve on that?

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)
Filed under: haskell 2 Comments
24Aug/096

The Magic Dot

So, reading about functors the other day, I noticed something interesting. Specifically, I noticed that in the case of functions,

fmap

is equivalent to the composition operation. I think

fmap

is possibly the coolest function in all of Haskell, so it annoys me when it requires six characters just to use it as an infix operator.

So I present what is, character-for-character, the coolest Haskell trick I have seen so far:

import Prelude hiding ((.))
import Control.Monad.Instances
a . b = a `fmap` b
infixr 9 .

And now, all sorts of fun little tricks are possible, like replacing

"map succ $ [0..9]"

with

"succ . [0..9]"

, and replacing

"getLine &gt;&gt;= return . (+1) . read"

with

"(+1) . read . getLine"

And of course, the same function composition magic still works like always.  Maybe it's just me, but something this simple, elegant, and fun to use just makes me happy inside.

But finally, I have to ask: is there any way of specifically declaring that a module *replaces* the standard Prelude (or even better, individual elements of it)? It would be really nice to just type 

import Prelude.MagicDot

and not have to also bother with adding 

import Prelude hiding ((.))

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)
6Aug/090

Useful Shell Trick

Sometimes, when doing a bunch of data munging in the shell, I want to pass the contents of a file through a shell pipeline, and then directly out into the file again. Unfortunately, doing this the naive way will obliterate the file's contents.

So a while back, I saw a neat little utility called "sponge" which simply buffered data until it ended, and then output it. While useful, this wasn't a standard Unix tool, so I couldn't very well rely on having it available.

Well today, after literally minutes of searching, I have found a command that seems to work just as well:

tail -n +0

It outputs all lines in the input, beginning with line zero. Due, I suppose, to the way tail is implemented, it buffers all input before outputting anything.

Not exactly groundbreaking or anything, but a useful little trick to know when playing around in the shell.

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)
Filed under: Uncategorized No Comments
20Jul/090

Git Short URLs

I knew for a fact this feature existed, but even so it took me a half hour to track down the syntax for it. To prevent myself ever needing to do that again, I'm putting it here.

To create a nice, short URL abbreviation for git, such as myserver:<project>.git, put the following in ~/.gitconfig

[url "ssh://MY-SERVER/~/"]
    insteadOf = myserver:

That's all there is to it.

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)
Filed under: Note To Self No Comments
18Jul/091

Haskell Exceptions

Haskell's absolute worst feature, in my opinion, is its system of exceptions. I have yet to see a single use of exceptions that wouldn't be better served by the use of a "Maybe" or an "Either" type. Luckily, in a small nod to sanity, Haskell provides 'Control.Exception.Base.try', which returns an Either type, with the exception left, and the value right.

Once you have that, it becomes easy to implement some sane functionality for exception handling, such as my current favorite functions, defaultOnError and errorToMaybe:

defaultOnError :: a -> IO a -> IO a
defaultOnError d a = do tryValue <- try a
                        case tryValue of
                             Left  _ -> return d
                             Right v -> return v
errorToMaybe :: IO a -> IO (Maybe a)
errorToMaybe a = do tryValue <- try a
                    case tryValue of
                         Left  _ -> return $ Nothing
                         Right v -> return $ Just v
Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)