Sam Danielson

As part of my effort to seek enlightenment through Haskell I’ve made some music. It’s actually sort of neat creating a waveform that when played through a DA resembles something other than white noise. This isn’t controlling a sequencer – it’s just composing functions to make make a sound representation. It’s a lot like naive ray tracing where all objects are considered for each pixel in that for each sample I sum the waveforms for all notes, many of which are zero since a note only plays for a short duration and is otherwise silent.

Notes are made by transforming a sound frequency Signal (Double -> Double) with pitch and amplitude Shifters (Signal -> Signal). For the note envelope I create a signal that represents amplitude and modulate the sound signal with the amp combinator, which is a Modulator (Signal -> Signal -> Signal).

One thing missing from this implementation is the ability to write (signal = signal1 + signal2). I now would write (signal t = signal1 t + signal2 t,) since a signal is a function over time. mauke in #haskell (irc.freenode.net) was helpful but I still don’t understand why some things work the way they do so I chose not to write a (+) instance for signals until I understand it better. The following will play a few measures of Mozart’s something something as I remember it. I forgot what it’s called but it’s in C and it’s popular.

Here’s an ogg vorbis of the output: mozart.ogg

And the illiterate Haskell.

-- Compile and listen as follows
-- ghc -o mozart mozart.hs && ./mozart | mplayer -v -rawaudio rate=16000:channels=1:samplesize=1 -demuxer rawaudio -

import System.IO
import Data.Char

type Signal = Double -> Double
type Shifter = Signal -> Signal
type Modulator = Signal -> Signal -> Signal

main :: IO ()
main = putStr . toBytes . take 200000 . sample 16000 $ sound

sound :: Signal
sound = ampc 0.35 . shifterSum song . pitchc (440 * hstep ** 3 * 2 * pi) $ wave

song :: [Shifter]
song = zipWith (\e p -> amp e . pitchc p) (lhEnvs ++ rhEnvs) (lhPitches ++ rhPitches)

wave :: Signal
wave = flange (\x -> sin (x * 2)) sin

lhPitches :: [Double]
lhPitches = map (* (1/2)) $ [du,so,me,so,du,so,me,so,re,so,fa,so,du,so,me,so] ++
                            [du,la,fa,la,du,so,me,so,re,so,fa,so,du,so,me,so]
lhBegins :: [Double]
lhBegins = take 32 $ toTempo [1..]

-- Applies 0.1 second duration to left hand begin times
-- resulting in a list of complete amplitude envelopes
-- for each note.
lhEnvs :: [Signal]
lhEnvs = map (pianoEnv 0.1) lhBegins

rhPitches :: [Double]
rhPitches = [du,me,so,ti/2,du,re,du,  la,so,du*2,so,fa,me]
rhBegins :: [Double]
rhBegins = toTempo [1,5,7,9,12,12.5,13, 17,21,23,25,28,29]
rhEnvs :: [Signal]
rhEnvs = map (pianoEnv 0.5) rhBegins

-- attack decay sustain release to resemble a piano
-- apply duration and begin for complete envelope signal
pianoEnv :: Double -> Double -> Signal
pianoEnv = env 0.005 0.05 0.4 0.7

-- eigth note tempo
tempo = 160
toTempo :: [Double] -> [Double]
toTempo ts = map (\t -> 60 * t / tempo) ts

-- Sums list of signal shifters and mutes the original signal
shifterSum :: [Shifter] -> Shifter
shifterSum xs = foldr (shifterAdd) (const . const 0) xs

shifterAdd :: Shifter -> Shifter -> Shifter
shifterAdd a b input t = a input t + b input t

-- 1        b
--         / \c_____d
--        /          \
-- 0 ___a/            \e___   Makes an amplitude envelope for a note
--
-- Will div by zero in some cases.
env :: Double -> Double -> Double -> Double -> Double -> Double -> Signal
env attack decay sustain release duration begin t
    | t < a || t >= e = 0
    | t < b           = (t - a) / attack
    | t < c           = 1 - (1 - sustain) * (t - b) / decay
    | t < d           = sustain
    | t < e           = sustain - sustain * (t - d) / release
    where a = begin
          b = a + attack
          c = b + decay
          d = c + duration
          e = d + release

sample :: Double -> Signal -> [Double]
sample rate signal = [signal (t / rate) | t <- [0..]]

-- yuck
toBytes :: [Double] -> [Char]
toBytes = fmap $ chr . clamp 0 255 . (\n -> truncate $ (n + 1) * 127)

clamp min max x
    | x < min = min
    | x > max = max
    | otherwise = x

pitchc :: Double -> Signal -> Signal
pitchc mult input t = input (t * mult)

ampc :: Double -> Signal -> Signal
ampc mult input t = mult * (input t)

amp :: Modulator
amp control input t = (control t) * (input t)

-- only works for control where d/dt = 0
pitch :: Modulator
pitch control input t = input (t * control t)

flange :: Modulator
flange ff w t = w (t + ff t)

hstep = 2 ** (1/12)
du = hstep ** 0
re = hstep ** 2
me = hstep ** 4
fa = hstep ** 5
so = hstep ** 7
la = hstep ** 9
ti = hstep ** 11

Write yourself a Scheme in 48 Hours

This is the most excited I’ve been since I learned how to make a character bounce around the screen on my C64! Learning a new programming style is hard: big programs are difficult to understand and small programs have too little to tweak. How do I learn from a ten line tutorial or a one-hundred line program? The ten line tutorial doesn’t do anything interesting and forces me to write new code to grow. OTOH, one-hundred lines of Haskell usually do something neat but I can’t begin to untangle how. For everyone there is a threshold of complexity, the understanding of which enables creating more complex things. Once this threshold is achieved a person can bootstrap their learning as an autodidact. Below it there is neither enough knowledge to guide their study or test their knowledge for correctness.

My capacity for understanding is often far lower than the bootstrapping threshold and my learning stalls as I fumble through tutorials gaining one small bit of knowledge without correlation until one day things begin to click into place. I then wonder how I learned in eight hours what had stumped me for eight months and feel profound appreciation for the wizards that understood it first. It’s like I was blind and they could see, and now through some miracle I also see. It’s real sight too, not just a description in words but the real sunrise seen for the first time by the formerly blind. In this case the misfitting pieces were the static algebraic types, monads, type classes, currying, and lazy evaluation of Haskell. It’s quite a bit to swallow just as the more familiar loops, conditional statements, functions, and variables once were. Many of these things are interdependent and cannot be understood separately. Jonathan Tang begins small and works from the ground up to a larger program, explaining each change so every line’s purpose is thoroughly understood. The culmination is a very small but capable scheme interpreter that is larger than what I would have understood without my building it. It is a perfect demonstration of the building-block technique of instruction I learned and used as a flight instructor.

Mr. Tang put the pieces together concisely. Wow.

Xmonad is an awesome window manager and these are my complements as a fanatical user. The thing I love about Xmonad is that it just seems to get everything right. Wmii, my first favorite tiling WM, really got me interested and I found no fault with it until I used Xmonad.

Internally Xmonad manages focus with a zipper data structure. Though there are more naive approaches used in early versions it’s clear from maintainer Don Stewart’s blog that a lot of thought went in to my sanity as a user. The sorted order provided by the zipper allows for completely automatic management of my windows. For me, the order reduces my workspace to essentially one dimension. In Wmii I used vim key-bindings to move focus up/down/left/right. In Xmonad I use only two keys for this. In every other window manager Alt+Tab is a total pain due to the random order of the windows or the fact that they need to be manually sorted. Xmonad always inserts and deletes windows in a way which preserves order as if I were inserting or deleting lines from a text file. Better, Xmonad can be extended with, among other things, algorithms to arrange windows based on this order. There are tabbed, grid, and circular layouts to name a few. One interesting extension even arranges windows in a Fibonacci spiral.

There’s plenty of fud floating around about the inextensibility of purely functional programs but Xmonad proves otherwise, at least for Haskell’s case. I feel like a dog watching TV when viewing the source but I do know this; the extensions manage a variety of state and the code is concise. Oh, and the whole thing runs in a memory image a little larger than an instance of bash.

Special thanks to Spencer Janssen for authoring the project. Xmonad is doing everything just right so my Archlinux machine is polished like a Macintosh, only more useful.

Yes! Arch is great. For more detail read on.

Arch's Appeal

The main difference between Arch and Unbuntu is that Arch is designed to be molded whereas Ubuntu is a complete desktop/server distro. Like Ubuntu, most things were configured and worked upon install. Unlike Ubuntu, Arch does not have a default desktop environment although XFCE4 could be considered well supported. Arch will appeal to users who wish to start with a minimal system and a package manager, adding bit by bit until the system is tweaked to their desire.

Ubuntu's Appeal

Ubuntu is for those who just don't want to mess with it - giving users the choice of a server, or a Gnome / KDE / XFCE desktop. There is also a minimal (alternate) Ubuntu installer for those who want more control. I wont say Ubuntu 'wins' here or anywhere because it's apples and oranges. Yes - Arch vs. Ubuntu is a stupid comparison but if you're like me and you can't help but type X vs. Y into Google before doing anything then maybe identifying some differences isn't so bad. In short, Arch maintains bleeding-edge, occasionally broken, packages with no release cycle whereas Ubuntu needs upgrading (breaking) every six months. Ubuntu is good software with target markets. Arch is good software.

Package Management

Arch uses a rolling release cycle where major releases consist of a snapshot. For a personal computer, avoiding Ubuntu's six month upgrade cycle is a definite benefit. On the other hand it could cause breakage occasionally, which is why I still prefer Ubuntu (LTS) for my server. Arch packages tend to be more bleeding-edge from what I can tell browsing the repository. For example, the packaged version of GHC in Ubuntu 7.10 is 6.6.1 while Arch will install 6.8.1.

Pacman, the Arch package manager, is similar to apt. One thing I really like is that headers are bundled with library binaries. This makes sense since headers have a tight coupling to the code they describe. They can also be used as documentation when man pages are weak. With Ubuntu I had the option of not installing headers but that proved to be sort of a PITA when compiling or building a new development system. Ruby gems also uses gcc occasionally and it's nice to avoid the search for *-dev packages. pacman -S imagemagick && gem install rmagick just worked.

Post Install

Everything is installed, configured, and working as per the normal Ubuntu setup. Arch requires a few extra steps to get a desktop environment installed. Here's a few examples.

Xorg

Unfortunately I had to configure X. I say, 'unfortunately', because I hate configuring X. Best to just install Ubuntu on another partition and copy the xorg.conf. Currently I'm using the open-source ATI drivers since I couldn't get the proprietary ones to install properly. I'll be working on that later.

Sound

Running alsaconf asked a few questions and my sound card worked. Easy.

Suspend and Resume

Suspend and resume with swap and ram work great using the pm-utils package. I had to configure the resume scripts to run alsactl restore to get sound working after a restore but other than that it was configured perfectly upon install.

CPU Frequency Scaling

Ubuntu Forums had a great post on this topic. Since it's dealing with the kernel it works on Arch too. http://ubuntuforums.org/showthread.php?t=248867

In Total

I'll be using Arch for the foreseeable future, maybe even contributing if I'm ever capable of fixing something. The documentation on their wiki is outstanding and the community has momentum. In general, Ubuntu is great for the automated installation and configuration of everything to include the kitchen sink. Arch is great for a lightweight and fast system with a rolling release cycle and bleeding-edge software.

Toying with the Nokia 770 has been teaching me more than I ever wanted to know about C, gcc, and the other things we do to write software for handhelds. I had known about the existence of garbage collectors for C and C++ but had always assumed they worked similar to GObject. A GObject programmer must call g_object_ref() and g_object_unref() to manipulate the reference count of each object on the heap. When the count reaches zero the space is reclaimed. A Boehm GC, rather, can function as a drop-in replacement for malloc() and free(). To my amazement the free() procedure isn’t required at all and can be replaced with a noop. The word “automagically” doesn’t even annoy me in this case since the Boehm GC is quite a trick. It can determine when an object on the heap is no longer required by comparing places where pointers usually live with it’s internal book. For example, a function that calls malloc usually sets a pointer on the stack to the allocated memory. When the stack shrinks the reference is gone and the dead memory can be automatically freed.

The main benefit, for me anyway, is that I can write consing functions in C. Any linked list implementation has a foreach method. Foreach is easy because it doesn’t have to keep the return value of its lambda argument. Map, filter, and almost every other good thing that comes from functional programming requires consing up a new list. Allocating the right amount of memory for each return value is doable. The difficult part is the bookeeping required to later free all the unreferenced lists. A functional program might map, filter, then reduce in a single line as it takes the GC for granted. Manual allocation is a better fit for building fewer, less disposable structures. I’m not sure I’ll use map that much with C but it would be a good way to test-drive the Boehm GC.

There has to be a catch. I’m still wide eyed that the Boehm GC even works. It might be a sign that Mozilla and X, the two biggest hogs on my system, use it.

This is awesome: aduni.org

There are twelve courses complete with video lectures, handouts, problems, and exams. So far I’ve had time to view the first six lectures in Theory of Computation covering regular grammars, finite state machines, context-free grammars, pushdown machines, Chomsky Normal Form, and a whole bunch of things I’ve forgotten. I can’t yet wield lex or yacc like a pro but understanding some of the rigor behind scanning and parsing really opens the door to some neat things. Other courses cover discrete math, probability, networks, algorithms, memory, pipelining, object orientation, web programming, artificial intelligence, and of course the “Structure and Interpretation of Computer Programs”.

Shai Simonson is an excellent lecturer. In a way it’s like watching Jeopardy but instead of trying to guess the correct answer-question, I try to guess what Shai will write next on the blackboard. I’m sure the other courses are just as interesting but I’ve only skimmed their contents as of yet. The materials are licensed under Creative Commons.

It is often stated that it is a good idea to exclude code or functionality from templates. I have seen more than a few articles on the web entirely about how to approach this goal and the solutions are usually somewhat ad-hoc or arbitrarily restrictive. Some projects even seek to build a template language on top of the base language. We are typically left with the impression that there are no rules, or even good guidelines, by which to judge the amount of functionality performed by the template. Code seems like a necessary evil. We need it, but too much is bad and how much is a black art. Here is a simpler definition of a template: templates are pure functions.

A pure function obeys the following rules.

1. The function always evaluates the same result value given the same argument value(s). The function result value cannot depend on any hidden information or state that may change as program execution proceeds, nor can it depend on any external input from I/O devices. This is known as referential transparency.
2. Evaluation of the result does not cause any semantically observable side effect or output, such as mutation of mutable objects or output to I/O devices.

The singular purpose of a template is to transform it’s input into something viewable. If output does not depend entirely on input then the template is doing something it shouldn’t. This is boring and obvious to experienced functional programmers but, hey, we’re not all experienced functional programmers. Despite the theoretical simplicity there’s always a catch in the real world.

Automatic loading of composed objects muddies the pure function perspective. In this contrived example there is a user model composed of an address model with a street attribute e.g. user.address.street. The common practice, at least in rails, is to build a template which accepts the user model as input and chains to attributes of associated models. Does the output of a template using object chaining depend only on input? That depends on whether or not the requisite models were loaded before evaluating the template. If template evaluation caused a database hit then the output would partially depend on what was in the database at that time, breaking the pureness of the template. Automatic object loading is a hidden complexity that speeds development. Associations should be preloaded during production with a database join to prevent superfluous queries, a practice consistent with templates as pure functions.

There is no need to create a non Turing-complete subset of a language to build a proper template, nor is there a need to eliminate code from a template. The mantra that code doesn’t belong in templates is harmful and wrong. Templates may contain any code so long as the template remains a pure function.

More experimenting with closures and iteration led to some interesting results. Due to some quirks with Ruby's scope rules there are a few gotcha's and some of my initial assumptions about how variables are bound were wrong. Hopefully this entry will serve to enlighten those who, like me, wondered about the mystical Ruby closure.

What are closures?

Closures are an stateful object created on the fly when a block of code with it's own scope becomes bound to variables in it's environment. Closures consist of two elements. The first is a reference to some executable code such a block, proc, or method. The second is the set of variables that are bound to the scope of the executable block. This code creates a closure bound to c: n = 2; c = lambda { n * n }; A closure is created any time a lambda references variables not local in scope. To be perfectly clear a closure is loosely:

struct Closure {
    void *function;
    void *function_arguments;
};

What problem do closures solve?

Read the rest of this entry

Today I found out that ruby closures are not function objects. When a proc or lambda is created the variables in local scope are bound and not copied. This means that if an outside method updates a variable the closure will see it, and if the closure updates a variable the method will see it. For example:

closures = []
for n in 0..7
  closures << lambda { n }
end
closures.map { |c| c.call } => [7, 7, 7, 7, 7, 7, 7, 7]

WTF you say? I did. Well, the variable n was updated outside the { n } closure. All eight closures will print 7 in this example since that was the last value of n. What if I need to keep a unique value of n for each closure? There’s a trick, make a functor. This is a slang functor, not the one from category theory. I still have no idea what those are. Here’s the solution:

def make_functor(n)
  lambda { n }
end

closures = []
for n in 0..7
  closures << make_functor(n)
end
closures.map { |c| c.call } => [0, 1, 2, 3, 4, 5, 6, 7]

Because make_functor’s argument (n) goes out of scope when make_functor returns it (n) can no longer be updated. This effect isolates the variable in the closure from the rest of the program and the variable n is not garbage collected because it is still referenced by the closure.

Now lets apply this to a real world problem. With the ruby-gnome2 library I am writing a class that displays a collection of ActiveRecord objects as an editable grid. Because ruby-gnome2 is a close match to the C bindings there is quite a bit of record keeping to do. Here is a loop that will add an “edited” signal handler to each column in a Gtk::TreeView. This code is buggy because n is shared between all closures created when signal_connect internally calls to_proc on the provided block. An edit to any cell will result in that change getting applied to only the cell in the last column since the loop exits with n on the last column. Talk about confusing the user!

for n in 0...NUM_COLUMNS
  renderer.signal_connect "edited" do |renderer, path, data|
    iter = @tree_store.get_iter path
    iter[n] = data
  end
end

Functors to the rescue!!!

def connect_edit_functor(renderer, n)
  renderer.signal_connect "edited" do |renderer, path, data|
      iter = @tree_store.get_iter path
      iter[n] = data
  end
end

for n in 0...NUM_COLUMNS
  connect_edit_functor(renderer, n)
end

Here we pass the needed variables to a method that will bind the signal handler and then gracefully let those variables go out of scope before the loop updates n. The result is that each instance of the signal handling closure now holds it’s own copy of n at the correct value. The correct column will therefore be referenced when a user edits a cell.

The description of right lines and circles, upon which geometry is founded, belongs to mechanics. Geometry does not teach us to draw these lines, but requires them to be drawn. —Isaac Newton, 1687

There is a pretty neat grease-monkey script many pilots use to browse the company website. It does syntax highlighting on some of the reports and also helps a person find good trips to pick-up or trade based on pay, overnight cities, etc. The same guy who wrote CCSMax is also hosting a logbook app for many pilots that scrapes flight time and other data from the company and puts it in the pilot’s logbook automatically.

The popularity of these and other mashups supports the idea that there is a need for a more semantic web but their implementation suggest that semantics is in the eye of the beholder. Rather than using an authoritative data definition, mashup services use regular expressions and other generally hackish ways to obtain data. Emphasis is placed on data interpretation instead of data definition.

In addition to ad-hoc consumption of data, ad-hoc submission has become widespread using XSS. It will be interesting to watch this evolve since XSS is usually considered a vulnerability.

In closing, an interface should take care to draw only the lines required by the geometry of the data. A simple and correct transformation will ease consumption whether the mapping is XML, CSV, text, or SQL.

Wmii is the sweetest window manager. I tried it along with Ratpoisen and a couple other mouse killing WM’s one day. After weening myself off the gui power management and wireless icons in KDE this is kicking butt on the laptop. Windows are automatically tiled into views as they appear and you can tag windows to create new views. Floating windows are a little out of place but are handled well enough.

The main event loop and status bar are implemented in bash script. These scripts communicate with wmii through a Plan 9 filesystem interface, which is sort of like the proc filesystem. Performing io on this filesystem controls the window manager. If I want to change my status bar clock to quit showing seconds, I edit the status script. To add a keyboard shortcut for a custom command, I modify the event loop script.

For folks that want absolute minimalism there is dwm, a stripped down version of wmii. Configuration is done by editing a header file. wc *.{c,h} yeilds 2178 lines and it compiles in about 2 seconds so I suppose that’s not a big deal. I prefer wmii though because I think Plan 9 is a great idea. It’s sort of like a “live” XML config file for a running process that uses Unix paths instead of Xpaths.

I command you to try it. Wmii

PS. The default key shortcuts are very vi like. Very nice.

I have been designing a database schema for my pilot logbook program and I figured it wouldn’t hurt to peek at the one I have been using for over three years now, Logbook Pro, which stores it’s data in an MS Access file with the extension lbk. The file utility revealed that this was indeed an Access file but Kexi and Openoffice both crashed while trying to open it. Thus began the search, ending in MDB Tools.

Read the rest of this entry

I’ve been looking for a way to put my pilot logbook into a relational database so I can use sql for queries. The plan is to put sqlite and chicken scheme on a Nokia 770 . I’ll write some helper logic in scheme and use it to update my logbook after each flight. I figure it’s a good way to learn scheme if nothing else. My Nokia 770 is in the mail so for now I’m just trying to learn scheme on Ubuntu.

What follows is my distilled experience installing chicken with sqlite support.

Ubuntu feisty wants to install an old version of chicken. Most eggs want the latest chicken compiler so I had to get the source tree from here . I was getting strange errors from chicken-setup; “Error: unbound variable: required-chicken-version” when I had the old version installed.

Assuming a current install of sqlite3 this should all work.

$ wget http://www.call-with-current-continuation.org/chicken-2.6.tar.gz
$ tar -xzvf chicken-2.6.tar.gz
$ cd chicken-2.6
$ ./configure
$ make
$ sudo make install

$ mkdir ~/tmp
$ cd ~/tmp
$ sudo chicken-setup sqlite3

$ sqlite3 test.db
> create table memos(text, priority INTEGER);
> insert into memos values ('Tara is hot', 100);
> .quit

$ csi
> (require-extension sqlite3)
> (define db (sqlite3:open "test.db"))
> (sqlite3:first-row db "select * from memos" )

I don’t know enough scheme to figure out if ‘db’ is opening a new connection on each appearance. I require more reading so I’ll quit writing for now.

I learned a new trick today, brace expansion in bash. Here’s some examples.

There are some definite uses like this,

$ wget http://www.anoyingpages.com/page_{1..12}

and this,

$ rm {old,lame}.{c,h}

If you get a moment on some asshole’s console, this

$ mkdir {a..z}{a..z}{a..z}

This is kind of neat.

$ echo {go,pa}{th,ne}

This is my favorite so far.

$ factor {1..1024}

Mattz wrote that he designed Ruby with the intent of least surprise.

While tooling around with Liquid Templates I was surprised to learn that a method can begin with a capital letter. What a pleasant surprise. A little experimentation in irb provided more insight into allowable method names. Check it out.

irb(main):005:0> self.class.send :define_method, "Is this a funny name for a method?" do
irb(main):006:1* "Yes, but Ruby doesn't care." 
irb(main):007:1> end
=> #<Proc:0xb7cf1900@(irb):5>
irb(main):008:0> self.send "Is this a funny name for a method?" 
=> "Yes, but Ruby doesn't care." 

Crazy!