Saturday, June 13, 2009

Oh, those pesky semi-colons!

I have a great fascination on the origin of things, whether it is the current set of books I am reading about early American history1, or the various nostalgic videos on the beginnings of Microsoft, or even the posts by Andy Hertzfield on the early beginnings of the Mac. C is a language that has that same nostalgic appeal to me as well. It's the pre-pre cursor to C#, the language I actually get paid to write in. In life's continual twists, I am now on a team that has some applications that interface with C and C api's. Most people I mention this to reply, "ugh.. you have to learn C?!?!?" But to me, it's something to learn and since C is the predecessor to C#, it scratches my itch for learning about the origin of things.
On a recent trip to my local public library there is a shelf for free books, and to my amazement, there was a copy of Problem Solving & Program Design in C. Sarcasm aside, I couldn't understand why it was still there for my taking. In the chapter on arrays, there is a simple program on writing a stack, I added a print function to this program to list all the elements.
This code compiles, but when I ran it, I only saw the last element in the array. Hmmm...strange. I fooled around a little adding some extra printlines, check some other code snippets and I can't find what is going on!
Eventually, after a day or so, what was wrong was I had a semi-colon at the end of my for loop declaration. The C compiler accepted this code as valid code and when my program ran, the for loop looped over itself, never proceeding into my brackets until i <= *size was actually true, then only printed the 3rd element in my array!
To me, there are several thoughts I took away from this little problem.
  • What a great lesson to enforce really reading your code before you execute.
  • An increased appreciation for the C# compiler to not let me even make that mistake in C#. (The compiler gives you a warning.)
I would love to see what comments, if any, others have on the merits of learning C, really learning C, when your primary programming language is C#. Personally, I see merits in knowing/learning this language if not for the only habit to slow down and really read my code.

1If your looking to get a nice start on early American History, I suggest the following:
  • John Adams by David McCullough
  • 1776 by David McCullough
  • Benjamn Franklin by Walter Isaacson
  • Founding Brothers by Joseph Ellis
These authors have written several additional books, but these are great primers on the subject.

Thursday, April 30, 2009

Haskell - Lists

Haskell - Lists
Lists in Haskell are defined by square brackets, [].  In ghci, declaring a list is as simple as:
Prelude> [1,2,3]
[1,2,3]
Lists can be of any length, indeed you can type in the following (although I wouldn't recommend it!)
Prelude> [1,2, .. ]
[1,2,3,4,5,6,7,8,9,10,11,12....]
To create an empty list, type the following:
Prelude> []
[]
Lists must be all the same type, if we try to declare a list with the following, we will get an error
Prelude> [1,3,5,7,"nine"]

<interactive>:1:7:
No instance for (Num [Char])
arising from the literal `7' at <interactive>:1:7
Possible fix: add an instance declaration for (Num [Char])
In the expression: 7
In the expression: [1, 3, 5, 7, ....]
In the definition of `it': it = [1, 3, 5, ....]
What the interactive session is telling us here is there is a type incompatibility between Num and [Char] and suggests some possible fixes.
Operating on Lists
To concatonate two lists you use ++
Prelude> [1,2,3] ++ [4,5,6]
[1,2,3,4,5,6]
To add an element to a list use the cons operator :
Prelude> "Nate" : ["Bill","Ted","Stephen"]
["Nate","Bill","Ted","Stephen"]
List Comprehensions
List comprehensions are really a thing of beauty, although, the Haskell Wiki labels them as syntatic sugar.  I think they add an element of beauty and simplicity.  Comprehensions follow the basic syntax1:
[ e | q1 .., qn], n >=1
where the q1 qualifiers are:
  1. generators:  p <- e, where p is a pattern of type t and e is an expression of type t
  2. guards: an expression that evaluates to a bool
  3. local bindings: provide new definitions for use or subsquent generators or guards
Here's an example of how to generate a list of all even numbers between 1 and 50 using comprehensions:
Prelude> [ x | x <- [1 .. 50],even x]
[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50]
Granted, you can accomplish the same thing using arithimetic sequences:
[2,4 .. 50]

But take a look at how to solve Project Euler question #1 with list comprehensions:
Prelude> foldr (+) 0 [x | x <- [1 .. 999],x `mod` 3 == 0 || x `mod` 5 == 0]
Breaking down this line into parts,
Prelude> foldr (+) 0 [x | x <- [1 .. 999],x `mod` 3 == 0 || x `mod` 5 == 0]
x <- [1 .. 999] is a generator, it's using an arithimetic sequence to get all the numbers between 1 and 999.
Prelude> foldr (+) 0 [x | x <- [1 .. 999],x `mod` 3 == 0 || x `mod` 5 == 0]
x `mod` 3 == 0 || x `mod` 5 == 0 is a guard or predicate.  Only when this expressions is true is it "passed" to the new list.
Prelude> foldr (+) 0 [x | x <- [1 .. 999],x `mod` 3 == 0 || x `mod` 5 == 0]
x is the new list of all the numbers between 1 and 999 that satisfy the predicate.  Then, x becomes part of the last expression, the foldr function.
foldr, or reduce, applys the the operator + in this case to the seed value 0 and each element in the list.

Sunday, April 19, 2009

Learning Haskell

Why am I learning Haskell?
There are several different answers, but there are a few that stick out more than others.  While I was learning F# and making my way through ProjectEuler problems, I was getting frustrated with running into type issues.  Here I was looking at some beautiful, clean and consice code, and then watching it get all cluttered up with F#'s casting syntax.1
Another reason is when I finally solved a Euler problem and quite proudly submitted my solution, I would browse the other F# solutions and became dissapointed with what some others where submitting.  I was looking at F# syntax, but it was all procedural style.
F# is a great language and I really enjoy writing with it, and will continue.  However, I wanted to learn functional programming on a language that doesn't allow me to break the rules.
Getting Started with Haskell
I am using the GHC implementation, which can be downloaded here.  With the download you get three components:
  • ghci - an interactive interpreter
  • ghc - compiler
  • runghc - runs Haskell programs as scripts
My examples will be in ghci, but I'll note when I switch.  My development environment is a Mac, so the command window is the bash shell.
After installing Haskell, launch Terminal and type in ghci:
$ghci
GHCi, version 6.10.1: http://www.haskell.org/ghc/ :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
Prelude>

Once the ghci is loaded, we see several libraries being loaded, ghc-prim, integer and base. Details on these packages can be found here.
The Prelude> prompt means the prelude library is loaded, sort of shorthand for the prelude 98 standard.  Like other Unix shells, what you see for the prompt is configurable, but I"ll leave the default.
One of the more import things to remember when you are starting is, :? This will list commands available from the prompt.  To execute an operating system or shell command, type in :! So to see what directory you are, type in
Prelude> :!pwd
/Users/nathanhoellein/HaskellProjects

To change directories, you need the :cd command.
Prelude> :cd ./ch03//
Prelude> :!pwd
/Users/nathanhoellein/HaskellProjects/ch03

Another command that's interesting is
:browse
It lists all names loaded by module.
Interactive Haskell

The ghc interpreter functions just like the F# interactive console, you can type in code snippets and perform arithmetic, except you don't have to end each line with ;;.
You can perform calculations using infix or prefix syntax:
infix:
Prelude> 2 + 3
5

prefix
Prelude> (+) 2 3
5

Integers can be large, see what happens when you want to know what 2 ^ 100 is:
Prelude> 2 ^ 100
1267650600228229401496703205376

Whereas in F#, you have to use doubles and you get a little different output:
> 2.0 ** 100.0;;
val it : float = 1.2676506e+30

What I find pleasing is you can see F#'s roots, the keyword "it".
The "it" variable sort of holds on to the last expression that was evaluated.
Prelude> 2 ^ 100
1267650600228229401496703205376
Prelude> it
1267650600228229401496703205376

We see the same in F#:
> 2.0 ** 100.0;;
val it : float = 1.2676506e+30
> it;;
val it : float = 1.2676506e+30

Other arithmetic stuff within Haskell:
Prelude> 2 - (-8)
10
Prelude> 2 + (-8)
-6

And booleans:
Prelude> True || False
True
Prelude> True && False
False

Like basic algebra, order of operations matter:
Prelude> (1 + 3) ^ 4
256
Prelude> 1 + (3 ^ 4)
82

That's a nice start for now, next post I'll cover lists.

1 - Yeah, I know it's really the .Net runtime