New (To Me) Languages – Haskell

In the movie Hoosiers, if I remember correctly, the basketball coach holds up a basketball and declares that it represents all there is know about basketball. He then makes a dot on it with a marker and declares that the dot to represents how much his team knows about basketball. Cut the dot in half, and that’s how much I feel I know about Haskell. However, even at the most fundamental levels of understanding there are some interesting concepts that differentiate Haskell from the industry standard and “popular” languages.

What are some of the basic concepts and features of Haskell that I think make it an interesting language? It is purely functional, has higher order functions, has lazy evaluation, and has type inference. Disclaimer: things get a bit technical below; you’ve been warned!

Purely Functional

One axis used to categorize programming languages is imperative v. functional.

A purely imperative language is focused entirely on managing and manipulating state and doesn’t have any notion of functions (think Turing machines). A purely functional language is focused entirely on application of functions and has no way of changing state; there is no assignment operator (think lambda calculus).

The popular languages tend be more imperative than functional in nature. Languages such as C, Java, & Python do have functions (or methods on objects) which in theory would allow highly functional programs to be constructed; however, the programmer will likely be fighting the language to do so. Certainly the idiomatic usage in such languages is to modify variables or structures or fields in objects (i.e. state) in a certain sequence.

Haskell is purely functional. No assignment operator, no state, just function application over arguments.

So, what exactly does this get you? Why expend the effort to go through a paradigm shift? The most compelling reason, in my opinion, is that it allows the programmer to have better control over the complexity of the program. In a system that has n side effecting components (such as global variables), the number of possible interactions between the components is on the order of n squared. In a purely functional language, there are no side effects. This relieves the programmer from the task of tracking interactions, which are often buried underneath layers of logic.

The idea of being side effect free is closely related to referential transparency. Referential transparency means (more or less) that a function applied to a certain set of arguments will ALWAYS return the same result; that is, a side effect of the function cannot change its result. Interestingly, referential transparency ties into what I think is the second most compelling reason to use a purely functional language: because all functions are referentially transparent, the language implementation is free to evaluate functions anywhere (that is, on a different processor or core) and it can always safely cache the results of a function. Thus, parallelism comes somewhat for free, at least from the programmer’s perspective.

Higher Order Functions

A language has higher order functions when functions are ‘first class citizens’, that is, functions can be passed as arguments to other functions and returned as results. Or stated another way, functions are really just another value that on which programs can operate. For those with background with Scheme or Common Lisp (or really any Lisp) higher order functions will be old hat, complete with lexical closures. C supports about 75% of the concept via function pointers; it lacks the ability to define anonymous functions (commonly known as lambda functions) and the ability to define functions at run time. However, function pointers create a bit of a syntactic mess, at least in my opinion. For example, compare this C prototype:

int (*func(int (*)(int)))(int);

with the analogous line in Haskell:

func :: (Int -> Int) -> (Int -> Int)

Even you can’t read either, hopefully you’ll agree that the latter has less noise.

Java can model higher order functions with objects, interfaces, and anonymous classes, and can probably even get you part way to lexical closures. The cost there is lines and lines of code to do so.

Of course I’ve been rambling on about language support before touching on why this is a useful thing, especially if it is isn’t annoying to use. Higher order functions allow decoupling and composition and as a result yield a powerful abstraction tool. As an example, suppose you need a function that adds one to each element of a sequence of numbers. In C (C99) one would likely write something along the lines of:

int arr[] = {1, 2, 3, 4, 5};
 
        for (int index = 0; index < sizeof(arr)/sizeof(arr[0]); index++) {
                arr[index] += 1;
        }

The code that does the adding is embedded inside of (and thus coupled with) the code that does the iterating. Higher order functions allow you to break this apart into two functions that can be combined: the first is a function that takes a numeric argument and returns the argument plus one (i.e. the adding step). The second is a function that takes a function and a list (array) as arguments and returns a list which contains the results of the supplied function applied to each element (i.e. the iterating step). This common function is called map in Common Lisp and Haskell. The pattern of the above ‘for’ loop has been abstracted and given a name, allowing the programmer to think and work at a higher level of abstraction.

Here’s the Haskell code that does the same task as the C code using higher order functions:

map (\x -> x + 1) [1, 2, 3, 4, 5]

The

(\x -> x + 1)

is a lambda function (i.e. anonymous function) whose result is one more than its argument, x.

Lazy Evaluation

Yet another axis of categorization applied to languages is eager v. lazy evaluation of function arguments. Strict v. non-strict evaluation and applicative v. normal order evaluation are (as far I can tell) aliases for the same concept.

An eager language completely evaluates function arguments before evaluating the body of the function. A lazy language does exactly the opposite, function arguments are evaluated after the function body, or possibly not at all, if the argument doesn’t appear in the function body. In other words, an eager language does as much work as possible before calling a function; a lazy language does as little work when (and if) it is absolutely needed.

As an example, the following C program will always result in a divide by zero error (or equivalent):

int f(int a, int b) {
  return a;
}
 
int main() {
   f(5, 1/0);  //<-- division by zero
 
  return 0;
}

The execution:

$ ./divzero
Floating point exception

The same function f in Haskell:

f :: Int -> Int -> Int
 
f x y = x

The execution:

Main> f 5 (1 `div` 0)
5

The division by zero is never executed because it doesn’t appear in the function body.

And to show that I’m not pulling a fast one:

Main> f (1 `div` 0) 5
 
Program error: divide by zero

What makes lazy languages interesting to me is that they make using ‘infinite’ data structures straightforward. For example, in a lazy language there’s no problem working with the list of natural numbers, i.e. integers in the range [1..∞). This list is a first class value; it can be passed as an argument and returned as a result. The reason that a lazy language can do this is that it never evaluates the entire list, only the parts it absolutely needs when it absolutely needs them. As as example, the following Haskell takes the list of natural numbers, adds two to each element, then takes the first five elements:

Main> take 5 (map (+ 2) [1..])
[3,4,5,6,7]

C, Java, and Common Lisp are eager languages; Haskell is a lazy language. Of course, one can play tricks in (some of) the former languages to simulate laziness and Haskell provides an operator that can make evaluation of particular arguments strict. (Imposing strictness can be important because, as you may have guessed, laziness does impose some overhead.)

Type Inference

Yet more axes of language categorization categorize how the language’s type system works. Broadly, there are two axes, strong v. weak typing, and static v. dynamic typing. These axes are completely orthogonal (in my understanding and usage, at least).

A language is strongly typed if it ensures that values are of the appropriate type before carrying out an operation (note that this check may occur at runtime). It is weakly typed if an operation can be carried out regardless of the types, either the type is ignored or it is coerced automatically in some way.

A language has static typing if the types of values are checked to be correct prior to running the program. In a dynamic language, types are not checked until runtime (if they’re checked at all).

An example language in each of the four categories:

JavaScript (ECMAScript) is a weak dynamic language.
Common Lisp is a strong dynamic language.
C is a weak static language.
Java and C# are strong static languages.

Haskell is a strong static language; however, its static typing comes with an interesting twist. In the typical static language, the type of each variable is specified explicitly by the programmer when composing the program. For example, in C, you might write the following function that adds its arguments:

int add(int a, int b) {
  int c = a + b;
  return c;
}

Obviously you don’t need the variable c in this example; however, the point is that if it is there, you have to state its type.

In Haskell, this is not the case. Haskell will infer the types of function arguments based on information it ‘knows’.

For example, say you write a function f that takes a list and a function, applies the function to each element and then sums the resultant list.

f func list = sum (map func list)

Notice that there are no types anywhere in sight, yet Haskell can tell you the type signature of this function:

Main> :type f
f :: Num a => (b -> a) -> [b] -> a

Waving my hands at the details of what everything means in the above signature, I’ll try to point out the significant parts, and how Haskell might have inferred it. Haskell’s type system has type classes and type parameters. Type parameters (the letters a and b above) are analogous to Java’s generics; effectively they are a place holder for a type. (And by type, think integer, character, etc.) When the function is invoked, imagine each instance of b being replaced by the name of the type appropriate for that invocation. The same is true of a, however, a is constrained by its type class, Num, which means that a must be a numeric type, i.e. floating point, fixed width integer, etc.

The above signature is read as “f takes two arguments, the first argument is a function that takes an argument of type b and returns a result of type a, the second argument is a list of things all of type b. f returns a result of type a. a is some numeric type.”

So, how does Haskell know this? It looks down into the function body and deduces what types the arguments and result must have. In the example, Haskell can see that the result of the function is the result of sum, so it must be a numeric type. It also knows that the result of map must be a list that contains numeric types, because that is what sum requires. From that it deduces that result of the function argument, func must be a numeric type. The final deduction is that the second argument can be list of any type (because map requires a list) as long as the argument to func accepts that type.

So what good is all of that? One of the criticisms levied against static languages (especially from those in the dynamic language camp) is that the programmer ends up having to hold the hand of the language by explicitly declaring types everywhere. This is especially painful during initial development where types are often fluid. (Especially painful in a language like Java, which seems to be extra verbose.) Dynamic languages ease the pain by assuming programmer got it right and defer type checking until runtime, where a type error may lurk for some time until being unearthed. Haskell’s type inference essentially gives you the best of both worlds; the programmer doesn’t have to explicitly state types (benefit of dynamic languages) and the language will check types for correctness before runtime (benefit of static languages).

For more (and better) information

If this piqued your interest, a couple of places to learn more are realworldhaskell.org (which is an online book) as well as the video series based on the book Programming in Haskell found here. And of course there’s haskell.org

Final Thoughts

Clearly I lost control of this awhile ago. Oh well, I posted it anyways.

4 Comments

  1. Kendall
    Posted February 27, 2010 at 3:42 pm | Permalink

    I was expecting Haskell to be weak and dynamic when I started reading that section. I also thought C was going to be strong and static. But then I thought about it for awhile and I guess weak makes sense?

  2. Andy
    Posted February 27, 2010 at 7:07 pm | Permalink

    To Kendall, the fact that a malloc returns a (void *) is telling. It’s also one of the first things to be replaced when C++ was created.

  3. jachrispens
    Posted March 1, 2010 at 7:07 pm | Permalink

    Expanding a bit, C is weakly typed because it’ll allow a program to treat a chunk of memory as any type it wants, ignoring the type of the thing actually in memory. Sometimes this is done on purpose, e.g. type casts, sometimes not, e.g. accessing an array outside of its bounds.

    There are a number of places that take advantage of this capability (e.g. malloc) to provide manipulation of memory outside of types.

  4. jachrispens
    Posted March 1, 2010 at 11:11 pm | Permalink

    A timely example of what C type casts will let you do, courtesy of the programming reddit:

    http://gist.github.com/319075

    A char[] is cast to a function pointer and then executed.

    The above isn’t strictly conforming C99. However, gcc allows it and it works in the Linux memory model.

Post a Comment

Your email is never shared.