Slang.

From John Badcock's:

Slang.
A Dictionary
of
the Turf, the Ring, the Chase, the Pit, of Bon-Ton,
and the
Varieties of Life,
Forming the Completest and Most Authentic
Lexicon Balatronicum
Hitherto Offered to the Notice of
the Sporting World,
For elucidating Words and Phrases that are necessarily, or purposely,
cramp, mutative, and unintelligible, outside their
respective Spheres.
Interspersed with
Anecdotes and Whimsies,
with Tart Quotations, and Rum-Ones;
with Examples, Proofs, and Monitory Precepts,
Useful and Proper for
Novices, Flats, and Yokels.

Computational Thinking

Alan Jacobs linked to this article recently (PDF):

http://www.cs.cmu.edu/afs/cs/usr/wing/www/publications/Wing06.pdf

I agree with much of what Wing says. I think the article is motivated by a general trend in Computer Science higher education that amounts to CS departments failing to "attract" good students. On the other hand it remains true that computational thinking applied to many other fields (essentially science in general) continues to be the foremost innovation for that field. Wing gets the distinction right that it isn't about programming. The example I always use is that cellular biology must be concerned with how cells communicate and act on each other. This problem has it's theoretical underpinnings in computer science. Not on using computers to run simulations on how cells might communicate (while that can be an interesting thing to study), but on answering questions like "What ways can discrete objects communicate?"

So why, given the importance of computational thinking to so much of science, is Computer Science failing to attract good students who want "go on to a career in medicine, law, business, politics, any type of science or engineering, and even the arts."? In my experience the public perception of CS is that it is all about programming or all about computer hardware. Computer Scientists most important body part is their fingers because that works the keyboard right? The cultural stereotype that gets assigned to Computer Scientists is the geek or nerd. As a consequence people who identify with that stereotype (for whatever reason) see themselves as cast in the role of Computer Scientist regardless of their ability or desire to reason well computationally. The ETS's major field test reports (pdf) that only 28% of CS seniors have an overall GPA above 3.5. Only 36% have that high a GPA in their major. Mathematics comes in at 47% and 43%.

Somehow Mathematics is able to attract thinking students while still getting a similar stereotyping from broader culture and I can't help but think that has to do with the seat it has a the education table as a first class member (never mind that the system at large fails to emphasize the important parts of mathematics). I like Wing's vision of a world where Computational Thinking has a place at that table (though I shudder to think of the tortures the education system could inflict in CS's name).

The man of action

To the Greeks the Private Realm was the sphere of life ruled by the necessity of sustaining life, and the Public Realm the sphere of freedom where a man could disclose himself to others. Today, the significance of the terms private and public has been reversed; public life is the necessary impersonal life, the place where a man fulfills his social function, and it is in his private life that he is free to be his personal self.

In consequence the arts, literature in particular, have lost their traditional principal human subject, the man of action, the doer of public deeds.

—W. H. Auden

More LINQ translation.

We will get to the second part of the last post later, but right now I wanted to post another quick "convert to Haskell from LINQ" entry this time from a post by Eric Lippert.

> import Control.Monad

Notice how similar this definition is to the C# version:

> data Tree = Node Tree Tree | Empty

In both version Node is the name of the constructor taking two arguments. Both cases make an immutable "object".

> instance Show Tree where
>   show Empty = "x"
>   show (Node l r) = "(" ++ show l ++ show r ++ ")"

The C# version's BinaryTreeString has a helper function doing the recursion, but it isn't really necessary (in the C# or Haskell). What the C# gains is the ability to side-effect on a StringBuilder directly rather than returning partial results.

> allTrees :: Int -> [Tree]
> allTrees 0 = [Empty]
> allTrees n = [Node l r | i <- [0..n-1]
>                        , l <- allTrees i
>                        , r <- allTrees (n - 1 - i)
>                        ]

This translates very directly from the LINQ code, each from statement becomes a statement with a <-. That's it! Testing we have:

> trees = mapM_ (putStrLn . show) (allTrees 4)

giving the output:

*Main> trees
(x(x(x(xx))))
(x(x((xx)x)))
(x((xx)(xx)))
(x((x(xx))x))
(x(((xx)x)x))
((xx)(x(xx)))
((xx)((xx)x))
((x(xx))(xx))
(((xx)x)(xx))
((x(x(xx)))x)
((x((xx)x))x)
(((xx)(xx))x)
(((x(xx))x)x)
((((xx)x)x)x)

In the comments we have several answers to the challenge the last of which translates to this:

> data ATree = ANode [ATree]

> instance Show ATree where
>   show (ANode [])   = "{}"
>   show (ANode xs) = "{" ++ (foldl1 (++) (map show xs)) ++ "}"

> allATrees :: Int -> [ATree]
> allATrees n = [ANode x | x <- h (n - 1)]
>   where h 0 = [[]]
>         h n = [(ANode l) : r | i <- [1..n]
>                              , l <- h (i - 1)
>                              , r <- h (n - i)
>                              ]

> aTrees = mapM_ (putStrLn . show) (allATrees 4)

Evaluating aTrees gives:

*Main> aTrees
{{}{}{}}
{{}{{}}}
{{{}}{}}
{{{}{}}}
{{{{}}}}

Note that this output is all strings of nested braces that are in a single outer pair of braces and are eight characters long. If we called allATrees's helper function h directly we would be removing the "single outer pair of braces" constraint. So h of n is of the same order as allTrees.

Solving Combinatory Problems with Haskell

Today my Visual Studio start page had a link to an interesting blog post by Octavio Hernandez and I couldn't pass up the opportunity to solve the problem with Haskell. Please note that this is not in anyway a commentary on language X is better than Language Y, rather looking at the same problem in many different languages is very helpful in understanding the problem itself better. I'll try and make this a literate Haskell post so you should be able to copy and paste the text into a text file with the ".lhs" extension and have everything run. So we begin by importing an operator that we will use later:

> import Data.List ((\\))

We will need a list of the digits.

> num = [1..9]


The first generation is all of the one digit numbers that satisfy n mod 1 == 0. That's an easy one, all of them satisfy that condition!

> m1 = num

We can see this in the C# version as from i1 in oneToNine without any where clause. The next step is to look at two digit numbers without repeating digits where n mod 2 == 0. So we write this:

> m2 = [n | a <- num
>         , b <- num \\ [a]
>         , n <- [a*10 + b]
>         , n `mod` 2 == 0
>         ]

This is a Haskell list comprehension and it can be read as "list ([) of n's (n) such that (|)...". Where the "..." is a series of conditions. The conditions are either pulling a value from a list (the ones with the left arrow <-), or are predicate statements. It will only use values that cause all the predicate statements to be true. We specifically have a being a digit. The second value b is using the list difference operator // which takes a list on the left and a list of values to remove on the right.

We will pause for a second and notice how similar this is to the mathematical statement:



If we run the code so far in ghci we can see that evaluating m2 gives us:

*Main> m2
[12,14,16,18,24,26,28,32,34,36,38,42,46,48,52,54,56,58,62,64,68,72,74,76,78,82,8
4,86,92,94,96,98]

Notice no digits repeat and all the numbers are even. Evaluating length m2 we see:

*Main> length m2
32

Since there are 9 digits (greater than 0) half of which are even (round down because 1 is odd) there should be four repeating digit even two digit number (22,44,66,88). Since we are not considering zero, there are nine possibilities for the first digit and four for the second (same as our repeats). This gives four times nine (36) minus our repeats (4) which equals 32. We now should be convinced that m2 is correct.

At this point we might be tempted to do the same thing for m3 but replacing our a to draw from m2. Instead we will capture the idea of that step in a more generic way. First we need a helper:

> toDigits a   = reverse $ h a
>    where h 0 = []
>          h a = a `mod` 10 : (h $ a `div` 10)

Back to ghci:

*Main> :t toDigits
toDigits :: (Integral a) => a -> [a]

This Haskell type shows that toDigits takes an Integral and gives a list of Integrals. It could be helpful to construct a sort of inverse to toDigits called fromDigits which could be defined as:

> fromDigits = foldl1 (\a b -> 10*a + b)

The details are not important, but it is helpful to notice that these two functions are nearly inverses of each other:

*Main> :t fromDigits . toDigits
fromDigits . toDigits :: Integer -> Integer
*Main> :t toDigits . fromDigits
toDigits . fromDigits :: [Integer] -> [Integer]

Here the . operator is composing the two functions.

*Main> fromDigits [1,2,3]
123
*Main> toDigits 123
[1,2,3]
*Main> (fromDigits . toDigits) 123
123

When we use fromDigits on a list with numbers larger than nine toDigits fails to be an inverse:

*Main> fromDigits [12,3]
123
*Main> toDigits 123
[1,2,3]
*Main> fromDigits [1,23]
33

This "failure" would still be useful in the case where only the first item in the list is greater than nine. In general it is nearly always instructive to try and construct an inverse function as it tells you quite a lot about your original function. You might observe similarities between fromDigits and n in m2. It turns out that there is another way to generalize n which we will come back to later.

Looking back at our definition of m2 we want to make that work for any step so we look for the parts that need to change. We know that we want to have a pull from the numbers from the previous step. And we know that we will be "modding" by a higher number each time. This implies two inputs to our step function which we will call ns and m respectively. We also have a problems that our helper function will fix for us. First the numbers from the previous step need to be split into digits for them to be subtracted from the pool of digits for b. So that becomes b <- num \\ (toDigits a). Now we can write our function down:

> step ns m = [n | a <- ns
>                , b <- num \\ (toDigits a)
>                , n <- [10*a + b]
>                , n `mod` m == 0
>                ]

We can test this out and see if it produces the next step:

*Main> let m3 = step m2 3
*Main> m3
[123,126,129,147,162,165,168,183,186,189,243,246,249,261,264,267,285,321,324,327
,342,345,348,369,381,384,387,423,426,429,462,465,468,483,486,489,528,543,546,549
,561,564,567,582,621,624,627,642,645,648,681,684,687,723,726,729,741,762,765,768
,783,786,789,825,843,846,849,861,864,867,921,924,927,942,945,948,963,981,984,987
]
*Main> length m3
80

I'll leave it as an exercise to the reader to determine if that is correct for m3.

We can now write out all the steps to get to m9 but we will now call them s1...s9 for steps one through nine:

> s1 = num
> s2 = step s1 2
> s3 = step s2 3
> s4 = step s3 4
> s5 = step s4 5
> s6 = step s5 6
> s7 = step s6 7
> s8 = step s7 8
> s9 = step s8 9

We can verify s9 is in fact the same result as the C# code gives:

*Main> s9
[381654729]

But we are not done yet! Writing out all the steps is repetitive. We will do a little bit of Haskell trickery to see how we can easily write this more simpily:

> s 1 = num
> s 2 = step (s 1) 2
> s 3 = step (s 2) 3
> s 4 = step (s 3) 4
> s 5 = step (s 4) 5
> s 6 = step (s 5) 6
> s 7 = step (s 6) 7
> s 8 = step (s 7) 8
> s 9 = step (s 8) 9

Here we used Haskell's pattern matching style of function definition to turn our s1 through s9 functions into a single function s that takes one parameter. All we had to do was add a few spaces and parentheses Now it should be clear how to collapse this down to two statements:

> s' 1 = num
> s' m = step (s (m-1)) m

We have s' 1 as the base case and s' m as the m^th case.

*Main> s' 9
[381654729]


Next time we will go further and look at some other ways to generalize this kind of problem.

Haskell

I've been learning more about Haskell and came across this paper:

http://conal.net/papers/beautiful-differentiation/beautiful-differentiation-long.pdf

Reading it made some things start clicking...

Drawing programs

I was playing around with some "Chrome Experiments" and came across a fun drawing program. I had to implement some aspects of a drawing program at work so I can appreciate something well made:

http://www.chromeexperiments.com/detail/sketchpad/

LaTeX Grapher

In an effort to equip my wife with the finest tools for being a math professor I've started to tackle the seemingly (to me) gaping hole in math document creation of quality two dimensional graph generation. Quality means vector graphics. Document creation means no one-offs, but instead something that is maintainable for the lifetime of said document. These requirements lead directly to something language driven and with enough features (and ability to add features in a consistent way) to handle anything we throw at it. The initial result is this:

http://latexgrapher.codeplex.com/

It's not ready for binary releases yet, but it will get there. Right now it requires .NET 3.5 (probably SP1). It can be compiled by Visual Studio C# 2008 Express Edition (free download). I will probably make a Silverlight version eventually, then you can use your web browser (and Silverlight plugin) to make graphs from Linux, Mac, or Windows. There will also eventually be a command line version that can be integrated into your desired build process.

What can it do now you ask? Here are a few examples.

Output	Code
	View (-3,-3),(5,5) f(x) = x^3/20 + 2 Shade f,(-2,3)
	View (-1,-3),(6,4) f(x) = x^2/5          | x < 2        3              | x == 2        x^2/5          | x < 4        -(x-2)^2/2 + 3 |                       : x = 2,4
	View (-1,-1),(11,11) f(x) = NaN          | x < 0        3            | x < 1        3+2*floor(x) | x < 4        10           |                     : x = 0,1,2,3,4
	View (-10,-10),(10, 10) > r = 5 > n = 5 > x0 = 2 > y0 = 3 > a(t) = t*pi/(2*n) > fx(t) = r*cos(a(t)) + x0 > fy(t) = r*sin(a(t)) + y0 > gx(t) = -(fx(t) - x0) + x0 > gy(t) = -(fy(t) - y0) + y0 Line    (gx(0),gy(0)),(fx(0),fy(0)) Segment (gx(1),gy(1)),(fx(1),fy(1)) Line    (gx(2),gy(2)),(fx(2),fy(2)) Segment (gx(3),gy(3)),(fx(3),fy(3)) Line    (gx(4),gy(4)),(fx(4),fy(4)) Segment (gx(5),gy(5)),(fx(5),fy(5)) Line    (gx(6),gy(6)),(fx(6),fy(6)) Segment (gx(7),gy(7)),(fx(7),fy(7)) Line    (gx(8),gy(8)),(fx(8),fy(8)) Segment (gx(9),gy(9)),(fx(9),fy(9)) g(x) = x

LaTeX in blogger.

I found a nice website that allows you to put LaTeX inline with blog posts and other things. For example:

 X = \{ x | x \in (1, 2) \}

All I had to do was add some javascript to my template.

Glacier Animal Identification Updates

It's that time again! Rebekah's family was in town a couple weeks ago and we took them to Glacier and really hit the jackpot for animal sightings. I thought I would start out with the new identifications by updating some of the animals already featured in this series:

Bighorn:

Rebekah was able to catch a video of some young bighorn practice their head crashing skills. We also got the chance to pick up a bighorn skull in the discovery center (there were lots of fun things in there). Their horns are really heavy, I'm glad they don't like to headbutt people.

Marmot:

As always the Marmots were not shy for attention. Once we reached Cracker lake we had one very curious hoary Marmot walk right in front of me posing every few seconds.




But not all the attention went to the marmot:

Moose:

We saw several moose with antlers this time on our scouting trip before Rebekah's family came.





Then when they came we saw one as we were hiking on the trail.





I'll have more updates soon with new animals!

Out of the blue.

Here is another stack from When Do I Get a Brownie:






“Drop the fire sword”

Time is of the essence when it comes to brownies.

When do I get a brownie?

So awhile back we were inspired by a blog and since the game either didn't have a name or we didn't remember it, we decided to call it “When do I get a brownie?” (A quote from Rebekah's mom). The game is kind of a visual telephone game where a phrase is interpreted as a picture, which is then interpreted again as a phrase. To play, each person (6-9 people is best) starts with as many blank squares of scrap paper as there are people. Each person then writes a phrase on the top piece of paper and passes their whole stack to the next person. When a player gets a stack they read the phrase and place that piece of paper on the bottom of the stack and draw a picture that represents the phrase. The stack is passed again and the player that gets the picture looks at it and then places it on the bottom of the stack and writes what phrase they think the picture represents. The game then ends when the stack gets back to the original phrase writer. Once everyone is finished the stacks are shared and much hilarity ensues.


While we were making Triple Chocolate Coffee Bean Cookies the other day we played “When do I get a brownie?” with four players passing the stacks two rounds (we also added a fifth stack to make it a little harder to remember which stack was the one you started with). Here is one of the stacks:



Cindy started out with “Wet socks are bad luck”.



Clara followed with some lovely wet socks (most certianly unlucky on their own) and a crossed out four-leaf clover.



Rebekah interpreted this as “Gym socks dripping with sweat are not a good luck charm.” A reasonable interpretation.



I then drew a charm necklace featuring a four-leaf clover, rainbow, gym socks (crossed out and dripping), fuzzy dice, and a pony (quite the charming necklace). My attention to detail here caused quite a backlog.



Cindy then interpreted that as “Charm bracelets should never have socks” (a truism I'm sure).



Clara then took the quick route with the impression of individual charms (one slightly detailed towards a four-leaf clover) an implies arrow and a no socks sign. I think I would have interpreted this one as “Beads imply no-sock-wearing hippy”.



Rebekah instead thought that that meant “Charm bracelets are not gym socks”.



I was still in the mindset of “necklace” so I quickly drew a charm necklace that only a geometry teacher could love not equaling socks. I'll post some of the funnier stacks so that all can enjoy.

Glacier Animal Identification VI

First let me say that these animals are most certainly wild and should never be directly approached. Always respect the animal's space.



While their name is misleading as they are part of the antelope rather than the goat family, the Mountain Goat is the certainly deserving of the mountain part of their name. They pretty much ignore other lifeforms and go about their business knowing that they could climb straight up a near by cliff and get out of harms way if needed. All the rest of the animals seem to know this too so they don't bother. Some eagles are a threat to the babies and the nannies will defend against such attacks. Here are a group of goats by the trail waiting out the wind:



When they are not getting blown around in the wind they seem to be fond of posing for pictures. This one even cooperated in trying to make the ledge look as precarious as it could:



Baby mountain goats are quite possibly the cutest creatures in Glacier (Rebekah has told me this).



Much of our time in Glacier is spent documenting baby mountain goats and their cuteness.







We have much much more, but really you just have to see them in person.

Update:The videos do not show up even though they show when previewing them in the editor. I assume this is a temporary issue that Blogger will figure out soon.

Glacier Animal Identification V

Bighorn Sheep are pretty much sheep with big horns. Their bodies are pretty big too, but they tend to be pretty docile creatures. They can get away for most any predator by using their excellent climbing skills and the rocky terrain.



We have some other pictures of bighorn but they are not on this computer, so we will post them later.

Where did July go?

We had an eventful July filled with a bunch of stuff. The Agony ride and the weeks leading up to it were excellent and fellowship filled. Our friend Jamie and my brother Travis were both there:


Rebekah had a crash in the morning (she hit my wheel from behind and went down), but she was fine and the scrapes and bruises are nearly gone already. After getting patched up on the road she insisted on riding the rest of that leg and went on to ride 171 total miles. Our new bikes performed excellently and Rebekah and I have been on three rides since.

Our new software at work is finally starting to take shape as it continues to occupy most of my time.

While we were in California for the Agony ride our plants all grew very nicely. We have two new avocado seeds sprouting and our existing plant has foot long leaves on the top. This weekend we are going back up to Glacier National Park to ride the Going to the Sun Road again.