Penny

Is it just me, or does the new back of the penny look like Lincoln taking a dump?

Politics, Death, and the End of Free Speech

For anyone that has been following American politics lately it can be overwhelming. There are more minor scandals than any average person has time to hear about, much less do anything about. I've come to the conclusion that it's the political version of a document dump. If you are unfamiliar with the term "document dump", it's a tactic used by big company lawyers when they are forced to provide some document, then they'll bury it in entire rooms full of mostly unrelated documents for the opposing lawyers. It's one of those loopholes in the law that most people don't care about, since everyone hates lawyers anyway. Whatever it is that the politicians are up to, it probably is major. For one thing Obama seems to have no intention of stopping warrantless wiretapping, or ending the war, the sort of things that typical Democrat voters really expected. Instead DoJ keeps up their appeals, and Striker gets re-deployed. You might think that the health care reform is where the effort is going, but most representatives haven't taken the time to read it, and Obama doesn't seem to care that his speaches about health care aren't anything like what is in the bill. They don't care that the cancer survival rates in places with universal care are 25% lower, they want control, and power. And more than anything, they want to control the media, with the media they can get re-elected, and get revenge on political opponents. Unfortunately for us the internet is part of what politicians consider the media, I'm sure it'll be a target.

Haskell Variables

The Haskell community seems to have an aversion to anything imperative. IMO this has led to a fair amount of confusion, in particular about variables. A majority of people that learn Haskell are at least somewhat familiar with imperative languages, and almost all other languages rely heavily on mutable variables. When asking about variables the Haskell beginner is usually referred to let/in or where, but those are definition conveniences, not variables.

So one of the things that happens is heavier reliance on recursion, the values passed to the function can change like a variable, but they're still parameters. Which leads to encapsulating values in a state monad, and then passing the monadic values around.

What is a monad? That is where most people get very confused. Mathematically a monad is different than how it is implemented in Haskell! In Haskell a monad is really just a data type pointer. So you have something like IO Integer and it's a pointer to an Integer. Unfortunately the IO monad has no good constructor, you need to use IOArray, IORef, TVar or some other monad to create a variable. For now let's stick to using IORef since it's intended for this.

module Main where

import Data.IORef

main = do
-- a new variable called var
   var <- newIORef (1::Integer)

-- the contents of var
   a <- readIORef var

-- add one to var
   modifyIORef var (+1)

-- the contents of var
   b <- readIORef var

-- set var to 3
   writeIORef var 3

-- the contents of var
   c <- readIORef var

   putStrLn $ show a
   putStrLn $ show b
   putStrLn $ show c

This is how variables are done in Haskell, with the following caveat: in general IORef isn't thread safe. So you might rather use something like:

module Variables (Variable, newVar, setVar, getVar, modVar, showVar) where

import Control.Monad
import Control.Concurrent
import Control.Concurrent.STM

type Variable a = TVar a

-- initialize a new variable
newVar :: a -> IO (Variable a)
newVar value = atomically $ newTVar value 

-- get the value of a variable
getVar :: Variable a -> IO a
getVar pntr = atomically $ do
   value <- readTVar pntr 
   return value 

-- set the value of a variable
setVar :: Variable a -> a -> IO a
setVar pntr value = atomically $ do
   writeTVar pntr value
   return value

-- apply a function to a variable
modVar :: Variable a -> (a -> a) -> IO a
modVar pntr fn = atomically $ do
   value1 <- readTVar pntr
   let value2 = fn value1
   writeTVar pntr value2
   return value2

-- a show function for a variable (for GHCI)
showVar :: (Show a) => Variable a -> IO ()
showVar pntr = do
   value <- atomically $ readTVar pntr
   putStrLn $ show value

This is thread safe on top of TVar. Variables.hs
So using this we'd have:

module Main where

import Variables

main = do
-- a new variable called var
   var <- newVar (1::Integer)

-- the contents of var
   a <- getVar var

-- add one to var
   modVar var (+1)

-- the contents of var
   b <- getVar var

-- set var to 3
   setVar var 3

-- the contents of var
   c <- getVar var

   putStrLn $ show a
   putStrLn $ show b
   putStrLn $ show c

Which is almost the same as using IORef, but thread safe.

Ternary Trees

I ran across an interesting data structure, the ternary tree. Unlike binary trees, a ternary tree splits three ways at every branch. I went ahead and implemented it in Haskell. It should be able to store dictionary type data, or variable name-value look ups.

The basic idea is that a tree consists of branches, leafs, leafy branches, and stubs. Having a leafy branch allows for words to be prefixes of other words, as in the example.

Methods

newTrie a b :: (Ord a) => [a] b -> Trie a b
Create a tree from a single word [a] and associate a value b with it.

insert :: Ord a => [a] -> b -> Trie a b -> Trie a b
Insert a word [a] and a value b into a tree. Insert will return an error if the word already is part of the tree.

lookup :: Ord a => [a] -> Trie a b -> Maybe b
Find the value b associated with a word [a].

map :: (b -> c) -> Trie a b -> Trie a c
Apply a function (b -> c) to all the values b in a tree.

toList :: Ord a => Trie a b -> [([a],b)]
Convert a tree to a list of word-value pairs.

fromList :: Ord a => [([a],b)] -> Trie a b
Convert a list of word-value pairs to a tree.

instance (Binary a, Binary b) => Binary (Trie a b)
An instance of binary for efficient storage of trees. Example: encodeFile "filename" tree

Ternary.hs

Haskell Raytracer

Lately I've been working on writing a ray tracer in Haskell.

Mathematically it's fairly complicated. In general what you do is substitute the formula for a ray into the formula for an object, then find the roots of the resulting equation. So for example if you have a sphere equation:

where Sr is the sphere radius,
and the ray equation:


where P is the starting point, and D is the direction.
Then you substitute the ray equation for the XYZ portions:

and then simplify:

Which is in quadratic form, so there's possibly two solutions. Note that if is normalized then so it can be omitted from the calculation. Once you have the roots T then you just pick the smallest that is in front of the ray starting point by at least epsilon, and convert that to the XYZ point.

sphereIntersect :: Vector -> Double -> Ray -> Maybe Hit
sphereIntersect loc radius ray@(pnt,dir) =
  let pl = pnt - loc
      b = 2*((x dir)*(x pl) + (y dir)*(y pl) + (z dir)*(z pl))
      c = (x pl)*(x pl) + (y pl)*(y pl) + (z pl)*(z pl) - radius*radius
      q = filter (>=epsilon) $ quadRootsIgnoreA b c
  in if (q == [])
      then Nothing
      else let ti = minimum q
               iPoint = evaluateRay ray ti
               iNorm = (iPoint-loc)/(toVector radius)
           in Just (iPoint, iNorm)

Of course you can't end with just spheres, there's planes, boxes, triangles, flat discs, cones, etc.

Transforms are complex too. Say for example that you'd like to declare a right cone frustum as:

cone {basePnt, baseRad, topPnt, topRad}

then you need to rotate and scale the ray along with the cone so that you can test against a standardized cone where you know the formula for the surface:
So you end up with pairs of 4x4 matrices describing the transform and it's inverse. Interestingly, once you get a list of transforms to be applied (translate, rotate, scale) they can be composed together into a single transform by matrix multiplication.

The intention is to get this heavy matrix calculation to run once per object, and then use the result transform in testing multiple ray intersects. In Object Oriented languages like C++ this would be done at construction of the object, in Haskell I'd like to partially apply an intersect function, and then use the resulting function on a ray... so: objectFn :: Ray -> Maybe Hit
All that is to be tested and implemented still.

Currently I'm working on torus, a torus-ray intersect results in a quartic equation:

So that requires a good quartic solver...

TomTom sued by Microsoft

The whole patent field has really gone around the bend. That any of the eight patents named in the Microsoft v. TomTom lawsuit were ever granted is legal insanity. Patents on: installing a computer in a car, installing wireless network support in a car, detecting when devices are plugged in to a computer, giving automated driving directions, panning a virtual map from a viewpoint, using flash memory, using both short and long file names. If you are counting that brings us to seven, the last one is a copy of the file name patent; that's right, it's just the same patent with a different number. None of these things are inventions in any real sense.
This is the sort of thing that has driven the economy into the second great depression. If the legal system continues to extort money in this manner then civilization may collapse.

Vista

The main computer here went kaput with a poof of smoke, so I took the opportunity to go without for the first time in years. There's always something on the internet that is entertaining in some manner, and I found myself replacing it with low quality TV shows. Eventually I ran out of fresh TV shows from the DVR and became startlingly bored. Then it became a great battle of procrastinators, who would give in and go buy a computer first? In the end I gave in first, using a birthday "gift" as an excuse, but I'm not fooling anyone, I'll be the one to use the new computer most.

Thus began the Vista woes, the Lexmark 3-in-1 printer isn't at all supported in Vista, and Lexmark basically is thumbing it's nose at customers, you can't get a Linux driver for it, you can't get a Vista driver, it might as well be a paperweight. Then re-installing programs has come up with dozens of paranoia firewall dialogs for each install. More startling, it's actually stalled the processor a few times... it's an AMD 1.8g quad core, so far I can't see much performance improvement from the old 1.8g Athlon. Thank goodness for backups, but all the registry is different, so it's password and number hunt week.