Metal music

Sometimes I write metal music and record my creations. This is one of those times!

I thought human implantation would be a brutal topic for a metal song, so I wrote one.

wetware
lyrics

I love my cry-baby wah wah pedal. Also thanks to the audacity and hydrogen teams. Go go GNU power!

Enjoy :)

EDIT: This song has been described as a coming together of Ian Curtis, Killing Joke, Machine Head, Muse and the Pet Shop Boys. Is this complimentary?

Anyway, this mix is intended for big bass systems or good head-phones. I mix not the bass for shitty laptop speakers.

It's quite strange I find actually - if the bass is loud it sounds great on laptops, but overwhelming on stereos. So for more macho systems, the song needs to be more of a pussy as regards bass. I'm sure there's a paradox in there somewhere.

Jason Wright

Jason died last week. We used to hang out in Garmouth and Lhanbryde. He was a really cool person, was excellent company, and a really funny chap. He used to roll really long cigarettes; that made me laugh. He liked computers and he was a funky drummer and guitarist. We made some music once, I still have a cd. I haven't seen him in a long time but I will still miss him. So funkiness to you, Jason and goodbye.

Wooo

Delve type checked a simple polymorphic function today -
Polymorphism in Delve is similar to polymorphism in an untyped language like ruby.

In Ruby, you can define a method which takes an object and accesses one of its members - even if no such object is in scope.

In Delve, such a function can be defined, but constraints are imposed on its arguments. They must possess that member for the type checker to accept the program.

This approach differs fundamentally with Haskell. With Haskell, the function writer must be responsible for writing code that uses a given type class, or function - it must be defined.

In Delve all the responsibility is on the function caller, who must ensure his arguments have the appropriate type. It's strongly typed ruby/python/smalltalk :)

I've been ranting about it for a while, but now it's really happening! Wooo!

Actually I feel really unproductive. Since August, I've written 6.3K lines of code for the Delve VM and compiler. The last week I was off to Aberdeen, and now it's just testing, testing, testing. I'm confirming it works, and fixing little bits when I need to, but I haven't written more than 100 lines in the past two weeks.

Must work more...

hashing within a range

It is trivial to define a function which given a range of numbers R and the number of bits in the hash B, produces a hashing algorithm to hash strings which have a length within R into a hash of size B.

Here is such a trivial function, in pseudocode*:

make_hash( R , B ) =
   // the longest possible string as input
   Longest = max( R )
   // if the number of bits is greater or equal to the number of bits in the string
   if B >= Longest * 7 then
      // Compute a hash from the given hash H and the string with first character C, and rest S
      hash( H , C : S) =
         // Shift H 7 bits to the left
         Shifted_H = H << 7
         // recurse, ORing C with the shifted hash
         hash( S , Shifted_H | C )
      hash( H , _ ) = H
      // Use curried application to give an initial hash of 0
      return hash( 0 )

What would be nice would be a hashing function which is optimal like this, for values within the range - but when a string has a length that is not in the range, the algorithm has a chance of producing a non unique hash for it. The further the length of the string is from the range, the lesser the chance of the algorithm producing unique hash, given the string.

I theorize that it is possible for strings of lengths beyond the range to have a unique hash, in some situations, and not in others. To take a simple example, in the range [ 1 .. B / 7 ], any value not in the range cannot have a unique hash - there are not enough bits! However in the range [ 1 .. ( B - 1 ) / 7 ] with there are some bits left over, so it is possible.

* That's some weird pseudo-code. Uppercase variables like Erlang? Bitwise operators like C? Guards like Haskell? Curried function application? Someone implement it!

Hash (algorithms, not the sticky kind)

Consider Dan Bernstein's hashing algorithm:

unsigned long
hash(unsigned char *str)
{
   unsigned long hash = 5381;
   int c;

   while (c = *str++)
   hash = ((hash << 5) + hash) + c;

   return hash;
}

(I've yanked this from U of York's CS pages)

I've often wondered about this algorithm. It always striked me as strange as to why it shifts left by 5, rather than 8. I reckon the overlapping allows longer strings to be hashed, at the expense of uniqueness. This would also be why the hash is added to its shifted sibling.

However I randomly generated some input strings and hashed each one with this Haskell program, to see how many of the resultant hashes would collide. The answers surprise me:

import Data.Bits
import Foreign.C.Types
import Data.List

chr :: CULong -> Char
chr = toEnum . fromEnum

ord :: Char -> CULong
ord = toEnum . fromEnum

bhash :: String -> CULong
bhash = bhash' 5381
   where
   bhash' hs ( c : s ) = ord c + bhash' ((hs `shiftL` 5) + hs) s
   bhash' hs _ = hs

collide :: CULong -> IO ( )
collide n =
   let l = map bhash $ mk_syms n
       cols = length l - ( length $ nub l )
   in  print $ "There were " ++ show cols ++ " collisions"

mk_syms :: CULong -> [ String ]
mk_syms n = map mk_unique_sym [ 0 .. n ]

mk_unique_sym :: CULong -> String
mk_unique_sym = mk_unique_sym' [ ]

mk_unique_sym' :: String -> CULong -> String
mk_unique_sym' acc w =
   if w >= 26
      then
         mk_unique_sym' ( c8 : acc ) $ ( w `div` 26 ) - 1
      else ( chr $ 97 + w ) : acc
   where
   c8 :: Char
   c8 = chr $ ( w `mod` 26 ) + 97

GHCi, version 6.10.3: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main ( dan_hash.hs, interpreted )
Ok, modules loaded: Main.
*Main> collide 100
"There were 48 collisions"
*Main> collide 1000
"There were 888 collisions"
*Main> collide 10000
"There were 9861 collisions"
*Main> collide 100000
"There were 99769 collisions"

I'm assuming the high number of collisions are a property of my mechanical input, though its not surprising that the number of collisions increase as the input grows.

Tomorrow I think I might feed the words from the aligned hansards into it, to see if human speech fares better.

PS mk_unique_sym is what the Delve compiler uses to make unique names for new variables in intermediate code phase.
Also - the type checker has type checked a couple of expressions. I'm very happy - a full release should be soon :)
And then its time to rewrite the VM.... the work goes on.

distraction

My my, I've rather been distracted from this whole computer world. I blame my University course and life in general. Have at you, life!

However, I now have a small break - it's quite amusing because I don't think anyone else has a holiday at this time of year. So to everyone else - na na na na naaa na.

Have at you, everyone else.

I'm really embarressed - I've had the amusing complaint that my tagsoup parser handles not some of the xml data types, like our happy friend Mr CDATA. I've never actually used the thing - it was a half baked solution to the problem of gathering links in shpider. Sorry Mister! I'll fix it (soon).

I trekked up to Aberdeen a couple of times in the last few weeks. Lizzie has been transfered into second year Geography, which is good. However she lives in Hillhead which is amusing.

Our sleep was interrupted one night by the tumultuous yobbery of three freshers chanting xenophobic English football songs. They were followed closely by a throng of international students, whom they had apparently befriend. Weird as hell. Also, not a good demonstration of adapting to survive, on the part of the English football fans, considering their proximity to Tillydrone and other lovely places to live.

Delve delve delve. I've neglected you so! But really, it'll get done. Sooo many bugs, so many tests to pass.

But I've sworn to make the next release coherent - so I'd rather get it done properly, and let it take a while.

I visited Rory's flat while at Aberdeen, where I'd left my copy of the dragon book - so I starded reading the section on code generation and runtime systems again. I've concluded that it won't be so difficult to compile Delve into machine code.

However, due to the support for continuations, a lot of data, is going to have to go on the heap rather than stack - I don't want to have to make deep stack copies all the time.