We were negotiating with the Pentagon, we had a blue screen of death. That was the last straw. When you're holding the moon for ransom, you value stability in an application.
Steve

Intro

Steve was speaking of operating systems, but his words apply to any clockwork. When lives are on the line, lives you want to destroy, will your laser deathray malfunction? This guide provides tools and techniques for making digital superweapons more robust, more efficient, more deadly.

Declarative

This guide uses the declarative Haskell programming language to illustrate concepts that increase software stability and speed. Haskell is free; open source and community driven; available for major operating systems including Windows, Mac OS X, and Linux; and pure, functional, lazy, type-safe, algebraic, inferential, and parallel. These last attributes will be explained later. For now, focus on installing Haskell Platform.

Haskell Platform
http://hackage.haskell.org/platform/

When Haskell Platform finishes, open a terminal (e.g. Command Prompt, Terminal.app, xterm) and enter ghci. Let's begin with the number of the beast.

$ ghci
Prelude> 666
666
Prelude> 666 + 111
777
Prelude> let x = 111 in 666 + x
777

The let expression clarifies computation by creating local nicknames for more complicated expressions.

Prelude> let x = 1 * 100 + 1 * 10 + 1 * 1 in 666 + x
777

As a declarative language, Haskell manipulates expressions, eventually reducing expressions to values. A simple let can be quite devious.

Prelude> let 2 + 2 = 5 in 2 + 2
5

Or substitute your doublethink here. Indeed, 2 + 2 ≠ 5. Haskell is not asserting that they are equal, rather, Haskell is creating a named expression, 2 + 2, that expands to the expression 5 within the let expression. By evaluating the expression 2 + 2 outside the let, the proper answer is revealed.

Prelude> 2 + 2
4

Pure

So, Lone Star, now you see that evil will always triumph because good is dumb.
Dark Helmet

If GHCi is the devil's playground, GHC is the devil's workshop. GHC is The Glorious Glasgow Haskell Compilation System. Like GCC, GHC converts source code into executable machine code. Unlike C, however, Haskell lends itself to powerful optimizations, enabling advanced techniques such as infinite data structures and memoization.

Code examples will be saved in .hs plain text files with hard tabs for indentation and run in the terminal using runhaskell. Shebangs (#!...) are optional; they allow Unix-based systems like Mac OS X and Linux to run programs in the short form ./goodbye.hs.

goodbye.hs

#!/usr/bin/env runhaskell

greeting :: String
greeting = "Goodbye " ++ "World!"

main :: IO ()
main = do
	putStrLn greeting

Example

$ runhaskell goodbye.hs 
Goodbye World!

The program goodbye.hs performs two computations. The outer computation main is a nonpure computations, printing a string to the terminal. The inner computation greeting is a pure computation, concatenating two strings together. The difference is that the pure computation merely transforms data while the nonpure computation has the side effect of writing to the stdout I/O stream. Haskell isolates pure code from nonpure code for clarity and utility: pure code can be optimized in a variety of ingenius ways.

Lazy

Do you seriously think I would explain my master stroke to you if there were even the slightest possibility you could affect the outcome?
Ozymandias

By default, Haskell uses lazy evaluation; it performs computations only when it needs to. This may seem like wasteful procrastination, but it's actually a deliberate effort towards optimization.

fib.hs (memoized)

#!/usr/bin/env runhaskell

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

main :: IO ()
main = let fib 30 = 832040 in do
	putStrLn (show (fib 30))

Example

$ time runhaskell fib.hs 
832040

real	0m0.285s
user	0m0.228s
sys	0m0.054s

This program runs rather quickly because Haskell skipped calculation. If Haskell knows that fib(30) is 832040, it doesn't need to actually calculate fib(30). If we remove the memoization let fib 30 = 832040, the program takes much longer to run.

fib.hs (full calculation)

#!/usr/bin/env runhaskell

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

main :: IO ()
main = do
	putStrLn (show (fib 30))

Example

$ time runhaskell fib.hs 
832040

real	0m5.924s
user	0m5.813s
sys	0m0.064s

Another use of lazy evaluation is infinite data structures.

Infinite

Gee, Brain, what do you want to do tonight?
The same thing we do every night, Pinky: Try to take over the world!
Pinky and the Brain

The RSA algorithm based on prime numbers powers every online transaction in the world. To conquer the primes would conquer RSA and then, the world.

sieve.hs

#!/usr/bin/env runhaskell

sieve :: (Integral a) => [a] -> [a]
sieve ns = n : sieve ns'
	where
		n = head ns
		ns' = filter ((/= 0) . flip rem n) ns

primes :: (Integral a) => [a]
primes = sieve [2..]

main :: IO ()
main = do
	putStrLn (show (take 10 primes))

Example

$ runhaskell sieve.hs 
[2,3,5,7,11,13,17,19,23,29]

The primes function uses the Sieve of Eratosthenes algorithm to enumerate the infinite list of prime numbers. Haskell doesn't need to know all the prime numbers, just specifically requested primes. In this case, the program takes the first 10 primes and prints them. Requesting all the primes results in Haskell returning just that.

$ ghci
Prelude> :load sieve.hs 
[1 of 1] Compiling Main             ( sieve.hs, interpreted )
Ok, modules loaded: Main.
*Main> primes
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,
107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,
223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,
337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,
457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,
593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,
719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,
857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,
...

This is not useful. While Haskell encourages infinite data structures, one must be careful to only use finite pieces of the structures. And one must use the right piece; Haskell cannot calculate the last prime, because there is no last prime; the list goes on forever.

*Main> last [1, 2, 3]
3
*Main> last primes
...

Type-Safe

When life gives you lemons, you clone those lemons and make SUPER lemons.
Scudworth

Haskell is strictly typed: every expression has a type, determined at compile time. The variable x cannot be an integer one minute and a string the next. This is also known as type-safety. As with lazy evaluation, it's a blessing in disguise. Type safety increases robustness without sacrificing flexibility. Haskell does this with algebraic data types, pattern matching, type inference, and type classes.

The example programs so far explicitly state the types of the expressions involved. In the Goodbye World program, the greeting is a String formed by concatenating two other Strings, and main is an action returning nothing at all, IO (). If main were expected to return the greeting after printing it, main would have the type IO String.

goodbye.hs (explicit types)

#!/usr/bin/env runhaskell

greeting :: String
greeting = "Goodbye " ++ "World!"

main :: IO ()
main = do
	putStrLn greeting

Haskell can intelligently determine many types automatically. This is known as type inference. If the type signatures are ommitted, the program will still compile and run as before.

goodbye.hs (no type signatures)

#!/usr/bin/env runhaskell

greeting = "Goodbye " ++ "World!"

main = do
	putStrLn greeting

Example

$ runhaskell goodbye.hs 
Goodbye World!

Pattern matching works well with type-safety, as used in the Fibonacci program. The fib function is defined by three patterns. The first two patterns, fib 0 and fib 1, are base cases. The last pattern, fib n is the general recursive case; it is used whenever fib is applied to a value that is not 0 or 1. Because fib n is monotonically decreasing, the recursive calls will always reduce to one of the two base case patterns, eventually returning a single value.

fib.hs (minimal)

#!/usr/bin/env runhaskell

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

main :: IO ()
main = do
	putStrLn (show (fib 30))

It would be redundant to add new patterns, but they could aid in memoization.

fib.hs (extended)

#!/usr/bin/env runhaskell

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib 2 = 1
fib 3 = 2
fib 4 = 3
fib 5 = 5
fib 6 = 8
...
fib 30 = 832040
fib n = fib (n - 1) + fib (n - 2)

main :: IO ()
main = do
	putStrLn (show (fib 30))

Records

Target the Reavers. Target the Reavers! Target everyone! Somebody fire!
Operative

The closest thing Haskell has to objects is records. Records encapsulate data in a form more manipulable than objects, but records do not include methods. Functions are already defined by their data structures; they are already semantically bundled and there is no need to labor the point by using object.method() syntax when function record will do.

laser.hs

#!/usr/bin/env runhaskell

data Target
	=  Fool String
	| Crowd Integer
	| TheMoon
	deriving (Eq, Ord, Show)

fireOn :: Target -> String
fireOn (Fool s) = s ++ " blasted!"
fireOn (Crowd n) = show n ++ "'s murdered!"
fireOn TheMoon = "How did you miss a shot like that?"

Example

$ ghci
Prelude> :load laser.hs 
[1 of 1] Compiling Main             ( laser.hs, interpreted )
Ok, modules loaded: Main.
*Main> fireOn (Fool "Jerry")
"Jerry blasted!"
*Main> fireOn (Crowd 100)
"100's murdered!"
*Main> fireOn TheMoon 
"How did you miss a shot like that?"

The laser program declares a data type Target with three constructors. A target is either a Fool String, a Crowd Integer, or TheMoon. Pattern matching in the fireOn function is used to unpack the target and determine which of the three constructors was used. Then fireOn acts on the specific constructor, blasting fools, murdering crowds, and somehow missing the moon.

No matter which constructor was used, Haskell derives how to compare two targets for equivalence, how to order targets in a list, and how to transform targets into strings for printing.

*Main> :m + Data.List
*Main Data.List> sort [Crowd 50, Crowd 40, TheMoon, Crowd 60, Fool "Ava"]
[Fool "Ava",Crowd 40,Crowd 50,Crowd 60,TheMoon]

Fools come before Crowds come before TheMoon in laser striking priority. In other languages, one would have to write custom compareTo and toString functions. In Haskell, deriving (Eq, Ord, Show) automatically generates basic functionality for any given data type.

Functions can be composed together and used as arguments for other functions.

*Main Data.List> let shout = unwords . take 2 . words . fireOn 
*Main Data.List> shout TheMoon 
"How did"

Robust

Haskell refuses to fireOn anything but Fools, Crowds, and TheMoon, because the function is only defined for these. Haskell will not compile code that attempts to fireOn Henchmen or MeeMaw, because these are not valid targets. Furthermore, for any valid target, Haskell will always faithfully fireOn the target, because Haskell has no null. Every expression is of a certain type and can never change type. As seen in the laser program, this by no means limits Haskell's expressiveness, nor does it encumber the programmer. Type-safety increases clarity, robustness, and flexibility, affording the evil genius more time for plotting the demise of his foes.

Resources

This is only the beginning, Haskell has much darkness to explore.

Parallel Processing with Haskell
http://www.yellosoft.us/parallel-processing-with-haskell

Learn You a Haskell for Great Good!
http://learnyouahaskell.com/

Real World Haskell
http://book.realworldhaskell.org/read/