CMSC-16100

Honors Introduction to Programming, I

Autumn Quarter, 2015

Home Policies Lectures Notes Labs

---

Piazza

Lecture 1: Introduction

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.

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. [MacOS X users: make sure you end up with ghci 7.10.2 -- at writing, the installation via MacPorts only provides 7.8.3, and the version difference matters.] Today's lab will include an install party—if you have a laptop, bring it to lab.

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. But let's start by understanding the principal mode of interaction during program development: you fire up the ghci interpreter, and present it with a sequence of expressions to be evaluated.

Let's look at a few examples....

First, some simple arithmetic:

$ ghci # we're invoking ghci from the shell's command line > 3+4 7 > 3*2+1 7 > 3+2*1 5 > (1+2) * 3 9 > 3 ^ 2 * 5 45 >

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.,

> 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. 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 usually necessary to put negative literals in parentheses, e.g.,

> (-1) * (-2) 2

The evaluation process in Haskell is driven by substitution. We will use ==> to indicate the simplification of an expression via a 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!

We can introduce names for particular values:

> let rate = 10 > let time = 20 > let distance = rate * time > distance 200

Here we've used let <var> = <expr> in the interpreter to define new values. This is good enough if we want to compute the distance travelled for a single rate and time, but what if we want to do a lot of distance calculations? In this case, we'd do better to modify our definition of distance by abstracting on the variables rate and time, and so defining a function, which we then evaluate at different arguments:

> let distance rate time = rate * time > distance 10 20 200 > distance 20 30 600

Let's take this apart. The let distance part tells the interpreter that we're going to be defining (or binding) the name distance. The rate time which follow indicate that distance is a function that takes two arguments, which we're going to give the names rate and time respectively, the = separates the binding's template from the body of the function we're defining, and then finally rate * time specifies that body.

As before, we can think of evaluation as a sequence of substitutions, e.g.,

> distance 10 20 ==> 10 * 20 ==> 200

In the first step, we substitute the first argument 10 in for rate, and the second argument 20 in for time in the body of the distance function, and then continue as before.

If you have previous programming experience, there are some surprises lurking here. You might be surprised a bit at the syntax, expecting distance(rate,time) whether out of analogy to standard mathematical notion or traditional programming languages. Oddly enough, you can do this in Haskell too, but it defines a slightly different function:

> let distance2(rate,time) = rate * time > distance2(10,20) 200

Admittedly, the difference may not be immediately obvious! But at a practical level, if we try to mix-and-match definitions and calls we're in for a surprise, in that both

> distance(10,20)

and

> distance2 10 20

will result in impressively long, and for the novice somewhat scary, error messages.

Understanding the difference between distance and distance2 gets at a fundamental feature of Haskell. The function distance appears to take two arguments. This isn't actually the case. In Haskell, all functions are curried, which is to say, they only ever take one argument. In this case, distance takes the argument rate. The result of evaluating this is another unary function that takes the time argument. Here, the syntax of application includes the convention that application associates to the left, thus distance 10 20 can be fully parenthesized as (distance 10) 20. The term "currying" honors the inventor of the lambda calculus, a mathematical theory of functions, Haskell Curry. And yes, Haskell does too.

So now, consider distance2. In this function, the two arguments rate and time get packaged into a tuple, which you can think of as a box that contains slots for two different values. The tuple, even though it contains two distinct values, is only a single value, hence, distance2 is also unary, as all Haskell functions must be. Unsurprisingly, there exist Haskell functions curry and uncurry which can swizzle back and forth between curried and (binary) uncurried functions. Thus:

> uncurry distance (10,20) 200 > curry distance2 10 20 200

Again, this may seem a bit surprising, as curry and uncurry are functions that take functions as arguments, and return functions as results. This gets us back to our description of Haskell as being (among other things) a functional language. This term might lead you to think that there's something fundamentally special about functions in functional languages. You'd be wrong, what's “special” about functions in functional languages is that they're not special! Functions are just values, and like integers and floating point numbers and other kinds of values we'll encounter later, can be defined, used, passed as arguments, and created as the result of evaluating functions, just like other values.

Haskell's preference for curried over uncurried functions may seem odd at first, but there are common Haskell programming idioms based on partial evaluation, i.e., (curried) multi-ary functions in which one or more arguments have been specialized, i.e., given a constant value, e.g.,

> let distanceAtRate10 = distance 10 > let distanceAtRate20 = distance 20 > distanceAtRate10 20 200 > distanceAtRate20 20 400

This raises the question of, “What to do if we want to specialize the second argument of a binary function?” For now, our best solution is to define another function directly, rather than via partial evaluation, e.g.,

> let distanceForTime10 rate = distance rate 10 > distanceForTime10 10 100

We'll develop a better solution in one of the exercises.

One issue that we haven't talked about yet is the precedences of function application vs. ordinary binary operations. Fortunately, there's an easy story to tell: application binds more tightly than infix operations. Thus, e.g., if we wanted to know how far we've gone after going 13 MPH for 3 hours, followed by going 10 MPH for 1 hour (a fair approximation of Professor Kurtz biking, Tour de France material he's not!), you could do

> distance 13 3 + distance 10 1 49

On the other hand, if you wanted to compute the effect of going 12 MPH for 2 hours before lunch, and 2 hours afterwards, you might naturally express this as

> distance 12 (2+2) 48

Note here that not using parentheses will give the wrong answer:

> distance 12 2+2 26

Haskell doesn't try to read your mind, and it doesn't care about the number of spaces used to separate tokens in an expression. It cares about precedence, and again, application binds more tightly than infix operations.

Having gotten this far, let me note that there are serious limitations associated with working as we have been by entering the definitions of functions one at a time via ghci's read-eval-print loop, so this is not the way we'll usually work. Instead, we'll put our definitions in Haskell source .hs files, and load them with ghci, or later compile them with ghc.

A Haskell source file is a plain text file that (mostly) contains definitions. For example, consider the following file, Hypotenuse.hs:

-- Hypotenuse.hs -- Define a function for computing the length of the hypotenuse -- of a right triangle, using the pythagorian theorem. square x = x * x hyp x y = sqrt ( square x + square y )

A Haskell source file is a different kind of linguistic environment than the ghci prompt. This is most immediately relevant in terms of the let keyword, which has a somewhat different syntax and somewhat different role. What this means is that you shouldn't use let in Haskell source files until you understand its proper syntax and role within that context. One major issue with let is that each use of the let keyword introduces a new lexical layer, making it difficult to define mutually recursive functions, and forcing orderings among the functions we define. This is not the case with Haskell source files. Thus, it is not necessary to define square before using it in hyp, i.e., the order of definitions could be interchanged without changing the meaning of the source.

Comments are introduced by a double hyphen --, and run to the end of the line. We can also use {- and -} for nested, delimited comments.

Function and variable names must start with a lower-case letter, and can consist only of alphabetic characters, digits, and the apostrophy ('). [Haskell was developed by mathematically inclined computer scientists, and mathematicians like to use primed variables.] The variable _ is considered to be a lowercase letter for the purpose of these rules, but _ by itself has a special role, i.e., that of an anonymous variable. Thus,

one _ = 1

defines a function that takes one argument (which it ignores!) and always returns 1. This can result in non-intuitive behavior, and we'll learn more about this later.

Also, whitespace matters when used for indentation. We'll talk about rules later, but for now: (1) mimic my use of whitespace, and (2) don't use tabs!! [N.B., many text editors provide an option that interprets tabs on input as the relevant number of spaces—such options can be very useful.]

We can use a Haskell source file in a number of different ways...

$ ghci Hypotenuse

or

$ ghci Hypotenuse.hs

or

$ ghci Prelude> :l Hypotenuse [1 of 1] Compiling Main ( Hypotenuse.hs, interpreted ) *Main>

The significance of the name(s) before the > prompt is something that will become clear eventually.

Note: it is a bad idea to use non-alphanumeric characters in the name of a Haskell source file. It is a good idea to start the name of a Haskell script file with a capital letter.

A common way of working is to have your Haskell source file open one window in a text editor, and in another window with a terminal running ghci. As you make changes (e.g., adding new functions, fixing the definitions of old functions, etc.), you'll save the file, and then reload the file in ghci:

> :r [1 of 1] Compiling Main ( Hypotenuse.hs, interpreted ) >