PLE lecture notes -- Haskell

Focal points

• Typing: implicit types, polymorphism, type-classes
• Functional style: currying, non-strictness, pattern matching
• Functional ideology

Values

Booleans

True or False

Characters

e.g. 'a'

Integers

e.g. 5

Functions

The backslash replaces Scheme's "lambda". Free variables are lexically scoped. Application is juxtaposition.

\n -> n + 1           -- the successor function
succ = \n -> n + 1    -- bind "succ" to the successor function
succ n = n + 1        -- sugar for above; similar to Self
\a -> \b -> a + b     -- the make-adder function
(\a -> \b -> a + b) 1 -- another version of the successor function

Heterogeneous tuples

(5, 'a', succ)

Homogeneous lists

[1, 2, 3]
1:2:3:[]    -- same thing, using explicit "cons" operator ':' and nil '[]'
[1..3]      -- also the same thing (Haskell is heavily sugared)

Types

          True :: Bool
           'a' :: Char
             5 :: Int
          succ :: Int -> Int
       [1,2,3] :: [Int]
(5, 'a', succ) :: (Int, Char, Int -> Int)

Implicit types

fact n = if (n == 0) then 1 else n * fact (n-1)

• n is being compared to 0, so it must be an Int
• fact sometimes returns 1, so its return type must be Int

Polymorphism

duplicate x = (x, x)

duplicate 1
duplicate ['a','b','c']

Type-classes

class Eq a where
  (==) :: a -> a -> Bool 

Instantiating a type-class means labeling an existing type, e.g. Int, as belonging to that class, and providing implementations of the class methods, e.g.

instance Eq Int where
  x == y = intEq x y

Now we can declare polymorphic functions only over types which support equality:

duplicate :: (Eq a) => a -> (a, a)
duplicate x = (x, x)

Whereas a -> (a, a) was an untyped type-function, that could take any type as argument, (Eq a) => a -> (a, a) is a typed type-function, whose arguments are themselves typed (by type classes). Haskell's '=>' corresponds using the '<' operator in Sather for restricting the parameters of parameterized types.

Haskell thus supports object-orientation based on traits. The data held by a value is defined by its type, but the operations on the value are defined by functions in an instance declaration (the traits). Furthermore, traits are themselves typed, by type-classes.

Non-generality

Functional style

Currying

 
(define (make-linear-xform a)
  (lambda (b)
    (lambda (x) 
      (+ (* a x) b))))

(((make-linear-xform 2) 3) 3)   ; prints 9

linear-xform a b x = (a * x) + b

linear-xform 2 3 3              -- prints 9
f = linear-xform 2 3            -- currying
f 3                             -- prints 9

Even operators, which are just infix functions, can be curried:

succ = (+1)
succ 2                          -- prints 3
double = (*2)
double 3                        -- prints 6

Currying prevents awkward Scheme constructions like (lamdba (y) (f x y)) when you really just want to say f x. This is known as eta reduction (a term from the lambda calculus).

Non-strictness

Like currying, delayed evaluation in Haskell is implicit. All functions in Haskell execute before their arguments are fully evaluated. This is known as non-strictness. In particular, Haskell is lazy, meaning that it postpones argument evaluation to the last possible moment: when the argument is used in the function. This mirrors the semantics of delay and force. (In contrast, the Id language is non-strict but eager: arguments evaluate in parallel with the function.)

For example,

const1 x = 1     -- function which always returns 1
const1 (1/0)     -- prints 1; the division never happens

ones = 1:ones    -- infinite list of 1s
                 -- ':' is just an infix function; it is lazy, too
take 10 ones     -- prints [1,1,1,1,1,1,1,1,1,1]
                 -- "take n list" returns the first n elts of list

Thus non-strict languages use names in the style of commands, not tags (as defined in the linguistics lecture). A name is bound to an arbitrary computation, which is executed when the name's value is needed (lazy evaluation) or concurrently (eager evaluation). A name cannot be rebound to something else; it "means" the result of that computation. For example, in English we use the noun phrase "the list containing 1 followed by the contents of the same list" to denote what in Haskell we called ones. Just as this noun phrase only means the infinite list of ones (it makes no sense to "rebind" it), the ones variable also cannot be rebound.

Declarative syntax

Pattern matching

x, y = 1, 2
def sum_pair((a,b)):
  return a + b
sum_pair((1,2))        # prints 3

(x, y) = (1, 2)
sum_pair (a,b) = a + b
sum_pair (1,2)         -- prints 3

For example, by using argument patterns we can define several versions of a function, as long as they have the same type. Here are two implementations of list length:

len1 x = if (x == []) then 0 else (1 + len1 (tail x))

len2 [] = 0
len2 (h:t) = 1 + len2 t

Guards

sign1 x = if (x < 0) then -1 else if (x == 0) then 0 else 1

sign2 x | x < 0  = -1
sign2 x | x == 0 = 0
sign2 x | x > 0  = 1

fact n | n == 0 = 1
fact n | n >  0 = n * fact (n-1)

Haskell even lets us make definitions like

fact 0 = 1
fact (n+1) = (n+1) * fact n

Sweet tooth

Computers can do a lot of things; sometimes what they do is well described as solving equations. However, traditional mathematics has no representations for I/O, naming environments, sequentiality, and time, which are all important in programming. No wonder languages based on math, such as Haskell, have poor support for these, much less any capability for reflection, i.e. representing how the language itself operates.

Functional ideology

• Closures: Neither Python nor Self support anonymous, lexically scoped, heap-allocated closures.
• Static typing: Sather requires programs to statically typecheck; a function cannot return more than one type.

When evaluation has no side-effects, the evaluation process becomes easier to understand. Conceptually, the evaluator is just applying rewrite rules to the syntactical form of the expression. For example:

• Wherever you see (fact n), textually replace it with if (n == 0) then 1 else n * fact (n-1).
• Whenever you see a == b, where a and b are values, replace it with True or False.
• Whenever you see if True then x else y, replace it with x.
• And so on, until no more rules can be applied. Then you are done.

One advantage of functionalism, then, is that it is easier to reason about programs, and therefore make them more efficient. Remember, compilation is like decryption: it's not the possibility that counts, it's the work factor. Functional languages promise to have a smaller work factor for the most difficult optimizations. A good example is parallelism: when expressions cannot have side-effects then it is always safe to run them in parallel. In 6.847, you will learn about a (mostly) functional language called Id where programs run well on both sequential and massively parallel hardware. Declarative programming in general tends to make more things implicit, which puts a burden on the compiler but allows programs to automagically become more efficient as the compiler improves. Hence functional programs can have a longer life span.

Another possible advantage is the new programming style born by the restriction. Functional programming goes even further than static typing in making it hard to make errors. However, this is not strictly a linguistic issue; it is a matter of style. It's just that functional languages happen to be best at functional style, by supporting pattern matching and non-strictness, because they're forced to.

Breakfast cereal analogy

• Sather is raisin bran
• Haskell is frosted flakes

• Integers, Booleans, characters, lists (Sather uses arrays), tuples, functions
• Static typechecking; type-functions, type inheritance

1. Implicit types
2. Implicit currying
3. Implicit lazy evaluation
4. Implicit selectors and conditionals, i.e. pattern matching

1. Must declare type classes to do overloading
2. Functions cannot take a variable number of arguments, optional arguments, or keyword arguments
3. Strict variables must be annotated; implicit laziness implies explicit strictness
4. Patterns must be linear: no repeated variables to enforce equality