Lecture 1: Introduction

\( \newcommand{\abs}[1]{\left\lvert#1\right\rvert} \newcommand{\ceiling}[1]{\lceil#1\rceil} \)

Administrivia

Please note all of the information found on the course Home Page and Policies Page, which are included here by reference. Note specifically the policy on Academic Honesty, as every year there are CS students who get this wrong, and suffer significant academic consequences. Don't be one of them. Also note "How to succeed in CMSC-16100 (and College)" on the course home page.

Getting started

You should set up the Glasgow Haskell system. The easy way is to download your platform specific Haskell Platform installer from http://hackage.haskell.org/platform, and follow the instructions. Chose the "Download Full." If you pursue programming in Haskell, you may want to consider minimal downloads in the future, but it would be a complication now. Today's lab will include an install party—if you have a laptop, bring it to lab.

Homework Standards, v. 1.0

Haskell

Haskell is a lazy pure functional language. We'll get around to defining these terms in due course, but suffice it to say that this is not your father's FORTRAN, nor even the Java or C++ you might have learned in High School. In traditional procedural programming language, programs are compiled (i.e., translated) into a sequence of instructions for manipulating memory; whereas in functional languages, computation can be conceived of as the more familiar process of disciplined substitution. Thus, programming in Haskell often feels like “programming with mathematics.”

Our decision to teach Haskell may seem peculiar, idiosyncratic, and perhaps even iconoclastic. Students who favor languages that are more familiar to them, and more important in the here-and-now commercially, often feel that way. We don't want to get into a debate over our choices today, but instead will lay out our priorities, and ask you to suspend disbelief. A useful metaphor, drawn from hockey (this is a hockey town), is “skating to where the puck is going to be.” Time and again, we have seen features, concepts, and even idioms of Haskell taken up by more traditional languages. Learning Haskell today will prepare you for the commercially important languages of tomorrow.

Let's start by understanding a principal mode of interaction during program development: you fire up the ghci interpreter, and present it with a sequence of expressions to be evaluated. One of the nice things about programming is that we get to extend the language of expressions, to describe computations of specific interest to us, but Haskell comes with a lot built in.

Arithmetic expressions

Arithmetic expressions are built out of traditional infix notation, with the precedences you'd expect, and allows the use of parentheses to allow other groupings of the operands. We start by invoking ghci from the command line. (Note that bold blue indicates the user's contribution to the interaction.)

$ ghci GHCi, version 8.2.1: http://www.haskell.org/ghc/ :? for help Prelude> 3+4 7 Prelude> 3*2+1 7 Prelude> 3+2*1 5 Prelude> (1+2)*3 9 Prelude> 3^2 * 5 45 Prelude>

This is all pretty standard. Arithmetic expressions follow the standard algebraic notion and precedence rules, with * used for multiplication, and ^ for exponentiating by an integral power. There is also a ** form of exponentiation that works with floating-point powers, e.g.,

Prelude> 2 ** 0.5 1.4142135623730951

There are some major details being swept under the rug here. The most important is that Haskell has a strict type system, and the distinction between various integer and floating point types is important, and will require greater care later on. But one of the really nice aspects of Haskell is that it does type inference, which for the present means that we can muddle along for a bit before we have to get serious about types. A second detail is the format of the number

0.5

Haskell has a very powerful and flexible parser, but it comes with a couple of quirks that affect simple arithmetic input. The leading zero in 0.5 is not optional; .5 is not valid Haskell syntax. It is also usually necessary to put negative literals in parentheses, e.g.,

> (-1) * (-2) 2

The evaluation process in Haskell, as noted earlier, is driven by substitution, a/k/a term rewriting, a process whereby subexpressions of a given expression are replaced by with other expressions. We will use ==> to indicate the simplification of an expression via a single substitution step:

3 ** 2 + (4 * 5) ==> 9 + (4 * 5) ==> 9 + 20 ==> 29

Easy enough! But is this useful? Surely programming languages are more than command line calculators! Unsurprisingly, Haskell also provides a large number of functions, as well as symbolic constants for commonly used mathematical functions and values, e.g.,

Prelude> log pi 1.1447298858494002

Here, log is the natural logarithm function, and pi is the mathematical constant $\pi = 3.14159\ldots$. Note that Haskell does not require that the arguments to a function be parenthesized, even if there are more than one, e.g., if we wanted logarithms base 10, we might use the logBase function:

Prelude> logBase 10 pi 0.4971498726941338

simply writing the two arguments to logBase one after the other. By the way, if you're a bit rusty on logarithms, don't panic! They're just an example, and not something that we're going to dwell on. One thing to be wary of, is that we don't wrap the arguments in parentheses and separate them by commas, as in typical mathematical notation, or as used by more traditional languages. We'll have more to say about this later.

Simple definitions, and Haskell source files

Of greater interest, we can define our own functions. This will require a more complicated interaction. In particular, we define new functions in a Haskell source (.hs) file, which we prepare using a text editor. In particular, assume we want to add a function for squaring a number. We'll edit a new file, e.g., Definitions.hs, consisting of a definition of the squaring function:

-- | Function definitions for CMSC 16100 Lecture 1 module Definitions where -- | Square a number. square x = x ^ 2

There's a lot going on in those three lines.

The first line is a comment, i.e., text that is intended for human readers, and isn't interpreted by Haskell. Comments are important, but also tricky. They're great for explaining things, but because the compiler doesn't try to interpret comments, they can easily become out-of-date, and so misleading. This isn't a reason not to comment, though. It is a reason to think about code that you're working on, and in particular to consider comments as well as code, updating the former whenever you update the later. Haskell has two styles of comments: the -- introduces a comment that extends through the end of the line, while {-- and --} delimit comments that may extend a fraction of a line, or many lines. One difference between Haskell and many other languages is that delimited comments nest, i.e., it is possible to use delimited comments to comment out code that includes other delimited comments.

There's something else going on here, the inclusion of a space followed by a vertical bar in the comments. Comments like this are used by the Haddock program (one of the tools in the Haskell toolchain) to build very nice HTML documentation, like this.

Programmers often struggle with how many comments to include. Too few, and it's difficult to figure out what the code does. Too many, and the code itself becomes difficult to find, and its structure more difficult to perceive. For now, adopt the discipline of including a Haddock-style comment for every top-level definition (including the module) as above, and add other comments where the code isn't self-explaining. If you can't write a sensible comment for a function, it's an indication that you haven't thought out clearly what that function is supposed to do, and that's always a red-flag.

The next line is a module declaration. Modules group related functions together. We're not going to dwell on modules this lecture, but we note that module names must begin with a capital letter, and the convention that files are named after the module they contain. Conventions make our lives easier, as they enable us to make reliable predictions about how things work. As we'll soon see, the module declaration will have a minor, but visible effect on our interaction.

Finally, the third line contains the definition itself. Note that ordinary function names must begin with lower-case letters, as must variables. This definition can be thought of as a template, in which expressions that take the form of the left-hand side of the equality symbol are replaced by the right-hand side. Note that we're only defining square, and that x is a variable that represents for the first argument to square function.

To use these definitions, we have to load them, which can be done either at the ghci prompt,

Prelude> :l Definitions [1 of 1] Compiling Definitions ( Definitions.hs, interpreted ) Ok, 1 module loaded. *Definitions>

or at the command line when we start ghci,

elrond $ ghci Definitions GHCi, version 8.2.1: http://www.haskell.org/ghc/ :? for help [1 of 1] Compiling Definitions ( Definitions.hs, interpreted ) Ok, 1 module loaded. *Definitions>

Note that we can (but are not required to) elide the .hs extension. Note also that the module name now appears in the ghci prompt, just in case you forget what code you're running. The * has a significance, but can be safely ignored for now. Now that we've loaded our definition, we can use it:

*Definitions> square 10 100 *Definitions> square 10 + square 20 500

The second example above illustrates one of the most important rules of Haskell syntax: function application binds more tightly than infix operations. In time, this will become instinctive.

Of course, it is in the nature of programming that we test our code, and as we do so, we sometimes add functionality (via new definitions), or fix bugs (yes, they happen). We might want to experiment with alternative definitions, for any of a number of reasons, including increased generality, better clarity, and better performance. For example, we might decide we prefer a different definition of square. No problem. We edit our source file, and replace the earlier definition of square with a new one,

square x = x * x

and then reload the code, using :r at the ghci prompt.

*Definitions> :r [1 of 1] Compiling Definitions ( Definitions.hs, interpreted ) Ok, 1 module loaded. *Definitions>

Our new definition doesn't seem to make an observable difference (and indeed, it would be shocking if it did).

*Definitions> square 10 100 *Definitions> square 10 + square 20 500

Moreover, we can use our definition in other code we write, e.g.,

-- | Function definitions for CMSC 16100 Lecture 1 module Definitions where -- | Compute the length of the hypotenuse of a right triangle with -- sides of length a and b. hypotenuse a b = sqrt (square a + square b) -- | Square a number. square x = x * x -- | Sum from a to b inclusive.

We reload the code to take advantage of our new definitions:

> :r Ok, modules loaded: Definitions. > hypotenuse 3 4 5.0 >

There are a couple things to notice here. We're eliding the module name in the interactive prompt here and henceforth, and the format of the answer is 5.0 and not 5. We'll have more to say about that in the next lecture.

One thing that's not obvious from this discussion is that the order of definitions in the source file is arbitrary. We didn't need to define square before we used it in the definition of hypotenuse.

One lesson you might take away from this is that if the complier doesn't care, you shouldn't either. That would be the wrong lesson. Programming is a form of communication, not just with the machine, but with human readers, your future self included. You should use the things the compiler doesn't care about, e.g., comments and the order of definitions, to organize your program into a kind of story that is better able to communicate with the reader. In the case of this short source file, the order of definitions doesn't matter much, but is not a purely arbitrary choice. If we view the purpose of the module as defining the hypotenuse function, putting the definition of hypothesis first reflects top-down design, i.e., the practice of problem solving by decomposing a problem into simpler subproblems, which are solved later. If, on the other hand, we define square first, we're thinking in a bottom-up way, in which we build an incrementally more powerful toolkit which, through directed growth, eventually includes the functionality we're looking for.

There are practical advantages to both approaches. A top-down design identifies the tools you need, and so can direct a bottom-up implementation. A bottom-up implementation is facilitates test-driven development, a programming discipline in which you design and implement tests for your code, before you write that code.

But our point here isn't to dwell on programming methodology just yet, but rather to focus on the organization of source files. In this, a coherent point of view can be very helpful, and it makes it easier for the reader to predict where specific definitions are to be found. There are good arguments to be made for both top-down and bottom-up organizations, and no universal best choice, but it is always better to make a choice and stick with it, than to let your source files become a hodgepodge of definitions that don't tell a story. In this particular case, we're actually not following a top-down discipline (extrapolating from two data-points can be misleading!), but instead we're following an organizational discipline common to modules that contain a large number of only loosely-related functions: alphabetical order.

*Exercise 1.1 The law of cosines is a generalization of the Pythagorean Theorem, which allows us to compute the length c of the third side of a triangle, given the lengths of the two other sides a and b, and the included angle γ.

Write a Haskell script file (Cosines.hs) that includes a function law_of_cosines which takes three arguments: a, b, and gamma, and returns the length of c.

Some notes:

Your code should contain an appropriate module declaration, and Haddock-style comments for the module and law_of_cosines function.

Guarded definitions

So far, our ability to define functions has been limited to simple definitions. There is a huge step up in programming power that comes with choice, the ability to define a function in different ways, depending on the value of its inputs. Consider the absolute value function of mathematics, usually defined as:

$$ \abs{x} = \begin{cases} x, & \hbox{if $x \geq 0$}\\ -x, & \hbox{otherwise}. \end{cases} $$

This definition can be translated into Haskell as follows:

abs x | x >= 0 = x | otherwise = -x

In this style of definition, there is a sequence of guarded expressions, each introduced by a vertical bar. Note that whitespace is syntactically significant, and follows block-indentation rules, which are best learned by example. Each of the vertical bars must be indented, and by the same amount. The guarded equation consists of two pieces, separated by an equality symbol. The first piece, the guard, is a boolean expression. We'll have more to say about boolean expressions in a bit. The second piece is an ordinary Haskell expression. When the evaluator attempts to simply an expression which is defined by cases, it evaluates each of the guards in turn, and uses the expression that corresponds to the first guard that's true.

We can use the following relational operators with numbers:

Haskell Math English
== $=$ equality
/= $\not=$ inequality
< $<$ less than
<= $<=$ less than or equal
> $>$ greater than
>= $>=$ greater than or equal

The only real surprise here (for people with prior programming experience) is the use of /= for inequality rather than the C-family's !=. Note that otherwise is defined to be True, so as a guard, it always succeeds. One nuance of guarded equations is the possibly that none of the guards will hold. This is an error, which can be avoided if the last guard is otherwise, and indeed, you should look at any set of guarded equations that doesn't end with otherwise with some skepticism. What does the last test accomplish?

Returning to our discussion of abs, Haskell is perfectly happy to accept our definition above, but isn't quite so happy when we try to use it:

> abs 10 <interactive>:1:1: error: Ambiguous occurrence ‘abs’ It could refer to either ‘Prelude.abs’, imported from ‘Prelude’ at Definitions.hs:3:8-18 (and originally defined in ‘GHC.Num’) or ‘Definitions.abs’, defined at Definitions.hs:14:1

One of the simple facts of life is that complier error messages are often scary, because they're designed by language experts for language experts. But if we take a deep breath, we can see what the problem is. There are actually two definitions of abs in scope, one that comes from the automatically included Prelude module, and our new definition in the Definitions module. There are a couple of solutions to this problem. We could specify which one we want to use, by following the syntax shown in the error message, i.e.,

> Definitions.abs 10 10

Or we could “hide” the definition in the Prelude by an explicit import of the Prelude module with a hiding clause, i.e.,

-- | Function definitions for CMSC 16100 Lecture 1 module Definitions where import Prelude hiding (abs) -- | The absolute value function. abs x | x >= 0 = x | otherwise = -x -- | Compute the length of the hypotenuse of a right triangle with -- sides of length a and b. ...

The explicit import of Prelude is rare in practice—it most often comes up in pedagogical examples early on, as it does here.

This one change, the introduction of guarded equations, makes a big difference in the expressive power of the language. Consider the problem of summing the natural numbers from 1 to 10:

$$1 + 2 + \ldots + 10 = \sum_{i=1}^{10} i.$$

An often useful, if somewhat surprising problem solving technique is generalization, i.e., solving a more general problem than the one that we're asked to consider. This often leads us to consider recursive solutions to a problem, i.e., solutions where our definition refers to itself in one or more subcases. For example, we can define

$$\sum_{i=a}^b i = \begin{cases} a + \sum\limits_{i = a+1}^b i, &\hbox{if $a \geq b$}\\ 0, &\hbox{otherwise} \end{cases} $$

which translates into Haskell as

-- | Sum from a to b inclusive. sum a b | a <= b = a + sum (a + 1) b | otherwise = 0

This runs into the same problem we had with abs, i.e., an attempt to re-define a pre-defined function. We'll deal with that as before, adding sum to the hiding clause.

Let's deal with the more basic conceptual problems associated with recursion.

Do circular definitions make sense? The answer's a bit ambiguous: sometimes. We can easily write functions that are ill-defined, e.g.,

-- | The undefined function: evaluate and die. loop = loop

As the comment and the name of the function suggests, loop creates an “infinite loop,” i.e., a computation that twiddles its thumbs, rewriting loop as loop ad infinitum. Ill-defined functions typically result in non-terminating computations or run-time errors.

Yet we've seen how a recursive definition enabled us to define a useful function, through a definition that involves multiple equations via guards, and is guaranteed to “bottom out” in an equation that doesn't involve a self reference. Our analysis is that $b-a$ must be decreasing by $1$ with each recursive call, and so must eventually become negative. In the case of real $a$ and $b$, the argument relies on the Archimedean property of the real numbers.

For this class, formal proofs of termination aren't required, but you should have a good informal understanding of why your code works. For recursive functions, the analysis is usually based on one of the arguments decreasing in value/complexity in such a way as to guarantee that the circular references are on “simpler” arguments, and that after finitely many such simplifications, we'll arrive at a non-circular “base” case.

*Exercise 1.2 The greatest common divisor function $\gcd$ satisfies the following equality: $$ \gcd(a,b) = \begin{cases} a,&\hbox{if $b=0$}\\ \gcd(b,a \mathop{\mathrm{mod}} b), & \hbox{otherwise} \end{cases} $$ Use this equality to define the gcd function.

As before, you should define your function within a sensibly named module, and provide Haddock style comments for both the module and the function.

Note that gcd is predefined in the Prelude, so you'll have to do something about that.

if ... then ... else ...

Guarded equations are useful when we define a function, but sometimes, it's convenient to have conditionals within expressions. Haskell provides this through a simple if ... then ... else ... construct, e.g.,

abs x = if x >= 0 then x else -x

Note that there are several different ways this code can be indented.

The if ... then ... else ... construct can become cumbersome when there are multiple tests involved, cf., the $\mathrm{collatz}$ function defined as follows:

$$ \mathrm{collatz}(n) = \begin{cases} 1, &\hbox{if $n=1$} \\ 1+\mathrm{collatz}(n/2), &\hbox{if $n$ is even} \\ 1+\mathrm{collatz}(3n+1), &\hbox{otherwise} \end{cases} $$

A translation of this into Haskell using the if ... then ... else ... construct is cumbersome:

collatz n = if n == 1 then 1 else if even n then 1 + collatz (div n 2) else 1 + collatz (3 * n + 1)

Note here that we use the div function rather than /. This is not accidental, but a full explanation will have to wait until Friday's lecture on types.

It would be nice if Haskell provided an expression-level multi-way if, a more direct analogy to guarded expressions. In fact, ghc does, but only via a language extension, a topic for another day.

There is a curiosity associated with the collatz function: How do we know whether or not it's total? After all, the argument to recursive calls isn't necessarily decreasing, cf., $3n+1$ clause. In fact, we don't. It is not known whether or not the function we've defined above is total on domain of positive natural numbers. This is a celebrated open problem of mathematics.

Exercise 1.3 Implement the collatz function using guarded equations.

Exercise 1.4 Implement the sum function using if ... then ... else ....

Exercise 1.5 If you have a mathematical turn of mind, you may find the optional lecture on Peano Arithmetic interesting.