Transcript ppt

Introduction to Programming in
Haskell
Koen Lindström Claessen
Programming
• Exciting subject at the heart of computing
• Never programmed?
– Learn to make the computer obey you!
• Programmed before?
– Lucky you! Your knowledge will help a lot...
– ...as you learn a completely new way to
program
• Everyone will learn a great deal from this
course!
Goal of the Course
• Start from the basics, after
Datorintroduktion
• Learn to write small-to-medium sized
programs in Haskell
• Introduce basic concepts of computer
science
The Flow
Do not break the
flow!
You prepare
in advance
I explain
in lecture
Tuesdays,Fridays
You learn
with exercises
Mondays/Tuesdays
You put to practice
with lab assignments
Submit end of each week
Exercise Sessions
• Mondays or Tuesdays
– Depending on what group you are in
• Come prepared
• Work on exercises together
• Discuss and get help from tutor
– Personal help
• Make sure you understand this week’s
things before you leave
Lab Assignments
• Work in pairs
– (Almost) no exceptions!
• Lab supervision
– Book a time in advance
– One time at a time!
• Start working on lab when you have understood
the matter
even this
• Submit end of each week
week!
• Feedback
– Return: The tutor has something to tell you; fix and
submit again
– OK: You are done
Getting Help
• Weekly group sessions
– personal help to understand material
• Lab supervision
– specific questions about programming
assignment at hand
• Discussion forum
– general questions, worries, discussions
Assessment
• Written exam (3 credits)
– Consists of small programming problems to
solve on paper
– You need Haskell ”in your fingers”
• Course work (2 credits)
– Complete all labs successfully
A Risk
• 7 weeks is a short time to learn
programming
• So the course is fast paced
– Each week we learn a lot
– Catching up again is hard
• So do keep up!
–
–
–
–
Read the text book each week
Make sure you can solve the problems
Go to the weekly exercise sessions
From the beginning
Course Homepage
• The course homepage will have ALL up-todate information relevant for the course
–
–
–
–
–
Schedule
Lab assignments
Exercises
Last-minute changes
(etc.)
Or Google for
”chalmers introduction
functional
programming”
http://www.cs.chalmers.se/Cs/Grundutb/Kurser/funht/
Software
Software = Programs + Data
Data
Data is any kind of storable information. Examples:
•Numbers
•Maps
•Letters
•Video clips
•Email messages
•Mouse clicks
•Songs on a CD
•Programs
Programs
Programs compute new data from old data.
Example: Baldur’s Gate computes a sequence of screen
images and sounds from a sequence of mouse clicks.
Building Software Systems
A large system may contain many millions of lines of code.
Software systems are among the most complex artefacts ever
made.
Systems are built by combining existing components as far as
possible.
Volvo buys engines
from Mitsubishi.
Bonnier buys
Quicktime Video from
Apple.
Programming Languages
Programs are written in programming languages.
There are hundreds of different programming languages, each
with their strengths and weaknesses.
A large system will often contain components in many
different languages.
which language
should we teach?
Programming Languages
Scheme
Lisp
C
BASIC
C++
Haskell
Java
C#
ML
Python
csh
Curry
O’CaML
JavaScript
Perl
bash
Erlang
Lustre
VHDL
Ruby
Prolog
Mercury
PostScript
Esterel
SQL
Verilog
PDF
Programming Language Features
dynamically
typed
statically
typed
type
inference
higher-order
functions
real-time
immutable
datastructures
polymorphism
overloading
parameterized
types
lazy
concurrency
high
performance
reflection
type
classes
Haskell
pure
functions
object
oriented
unification
backtracking
distribution
virtual
machine
compiler
metaprogramming
C
Java
interpreter
Teaching Programming
• Give you a broad basis
– Easy to learn more programming languages
– Easy to adapt to new programming languages
• Haskell is defining state-of-the-art in programming
language development
– Appreciate differences between languages
– Become a better programmer!
Industrial Uses of Functional
Languages
Intel (microprocessor
verification)
Hewlett Packard (telecom event
correlation)
Ericsson (telecommunications)
Carlstedt Research &
Technology (air-crew
scheduling)
Hafnium (Y2K tool)
Shop.com (e-commerce)
Motorola (test generation)
Thompson (radar tracking)
Microsoft (SDV)
Jasper (hardware verification)
Why Haskell?
•Haskell is a very high-level language (many details taken
care of automatically).
•Haskell is expressive and concise (can achieve a lot with a
little effort).
•Haskell is good at handling complex data and combining
components.
•Haskell is not a high-performance language (prioritise
programmer-time over computer-time).
A Haskell Demo
• Start the GHCi Haskell interpreter:
> ghci
___
___ _
/ _ \ /\ /\/ __(_)
/ /_\// /_/ / / | |
/ /_\\/ __ / /___| |
\____/\/ /_/\____/|_|
GHC Interactive, version 6.6.1, for Ha
http://www.haskell.org/ghc/
Type :? for help.
Loading package base ... linking ... done.
Prelude>
The prompt. GHCi is ready for input.
GHCi as a Calculator
Prelude> 2+2
4
Prelude> 2-2
0
Prelude> 2*3
6
Prelude> 2/3
0.666666666666667
Type in expressions, and
ghci calculates and prints
their value.
Multiplication and division
look a bit unfamiliar – we
cannot omit multiplication,
or type horizontal lines.
2
3
X
Binding and Brackets
Prelude> 2+2*3
8
Prelude> (2+2)*3
12
Prelude> (1+2)/(3+4)
0.428571428571429
Multiplication and division
”bind more tightly” than
addition and subtraction – so
this means 2+6, not 4*3.
We use brackets to change
the binding (just as in
mathematics), so this is 4*3.
This is how we write
1+2
3+4
Quiz
• What is the value of this expression?
Prelude> 1+2/3+4
Quiz
• What is the value of this expression?
Prelude> 1+2/3+4
5.66666666666667
Example: Currency Conversion
• Suppose we want to buy a game costing €53
from a foreign web site.
Prelude> 53*9.16642
485.82026
Exchange rate: €1 =
9.16642 SEK
Price in SEK
Boring to type 9.16642 every
time we convert a price!
Naming a Value
• We give a name to a value by making a
definition.
• Definitions are put in a file, using a text
editor such as emacs.
> emacs Examples.hs
The UNIX prompt,
not the ghci one!
Haskell files
end in .hs
Do this in a separate
window, so you can
edit and run hugs
simultaneously.
Creating the Definition
Give the name
euroRate to the
value 9.16642
variable
Using the Definition
The prompt
changes – we
have now
loaded a
program.
Load the file
Examples.hs into
ghci – make the
definition
available.
Prelude> :l Examples
Main> euroRate
9.16642
Main> 53*euroRate
485.82026
Main>
We are free to make use
of the definition.
Functional Programming is based on
Functions
• A function is a way of computing a result
from its arguments
• A functional program computes its output as
a function of its input
– E.g. Series of screen images from a series of
mouse clicks
– E.g. Price in SEK from price in euros
A Function to convert Euros to SEK
A definition –
placed in the
file
Examples.hs
A comment – to help us understand
the program
-- convert euros to SEK
sek x = x*euroRate
Function name –
the name we are
defining.
Name for the
argument
Expression to
compute the
result
Using the Function
Main> :r
Main> sek 53
485.82026
Reload the file to make the new
definition available.
Call the function
Notation: no brackets!
C.f. sin 0.5, log 2, not f(x).
sek x = x*euroRate
x = 53
While we evaluate
the right hand side
53*euroRate
Binding and Brackets again
Main> sek 53
485.82026
Main> sek 50 + 3
461.321
Main> sek (50+3)
485.82026
Main>
Different!
This is (sek 50) + 3.
Functions bind most
tightly of all.
Use brackets to recover
sek 53.
No stranger than writing
sin  and sin ( + )
Converting Back Again
-- convert SEK to euros
euro x = x/euroRate
Main>
Main>
53.0
Main>
49.0
Main>
217.0
:r
euro 485.82026
euro (sek 49)
sek (euro 217)
Testing the
program: trying it
out to see if does
the right thing.
Automating Testing
• Why compare the result myself, when I
have a computer?
The operator == tests whether
two values are equal
Main> 2 == 2
True
Yes they are
Main> 2 == 3
No they aren’t
False
Main> euro (sek 49) == 49
Note: two equal signs
True
are an operator.
Let the computer check
the result.
One equal sign makes
a definition.
Defining the Property
• Define a function to perform the test for us
prop_EuroSek x = euro (sek x) == x
Main> prop_EuroSek 53
True
Main> prop_EuroSek 49
True
Performs the same
tests as before – but
now we need only
remember the
function name!
Writing Properties in Files
• Functions with names beginning ”prop_”
are properties – they should always return
True
• Writing properties in files
– Tells us how functions should behave
– Tells us what has been tested
– Lets us repeat tests after changing a definition
• Properties help us get programs right!
Automatic Testing
• Testing account for more than half the cost
of a software project
• We will use a tool for automatic testing
import Test.QuickCheck
Add first in the file of
definitions – makes
QuickCheck available.
Capital letters must
appear exactly as they do
here.
Running Tests
Main> quickCheck prop_EuroSek
Falsifiable, after 10 tests:
3.75
It’s not true!
The value for which
the test fails.
Main> sek 3.75
34.374075
Main> euro 34.374075
3.75
Looks OK
Runs 100
randomly
chosen tests
The Problem
• There is a very tiny difference between the
initial and final values
Main> euro (sek 3.75) - 3.75
4.44089209850063e-016
e means
£ 10
-16
• Calculations are only performed to about 15
significant figures
• The property is wrong!
Fixing the Problem
• The result should be nearly the same
• The difference should be small – say
<0.000001
Main> 2<3
True
Main> 3<2
False
We can use < to see whether one
number is less than another
Defining ”Nearly Equal”
• We can define new operators with names
made up of symbols
x ~== y = x-y < 0.000001
With arguments
x and y
Define a new
operator ~==
Which returns True
if the difference
between x and y is
less than 0.000001
Testing ~==
Main> 3 ~== 3.0000001
True
Main> 3~==4
True
What’s wrong?
x ~== y = x-y < 0.000001
OK
Fixing the Definition
• A useful function
Main> abs 3
3
Main> abs (-3)
3
Absolute value
x ~== y = abs (x-y) < 0.000001
Main> 3 ~== 4
False
Fixing the Property
prop_EuroSek x = euro (sek x) ~== x
Main> prop_EuroSek 3
True
Main> prop_EuroSek 56
True
Main> prop_EuroSek 2
True
Name the Price
• Let’s define a name for the price of the
game we want
price = 53
Main> sek price
ERROR - Type error
*** Expression
*** Term
*** Type
*** Does not match
in application
: sek price
: price
: Integer
: Double
Every Value has a Type
• The :i command prints information about a
name
Main> :i price
price :: Integer
Main> :i euroRate
euroRate :: Double
Integer (whole number) is
the type of price
Double is the type of real
numbers
Funny name, but refers to
double the precision that
computers originally used
More Types
The type of truth values, named
after the logician Boole
Main> :i True
True :: Bool -- data constructor
Main> :i False
False :: Bool -- data constructor
The type of a function
Main> :i sek
sek :: Double -> Double
Type of the result
Main> :i prop_EuroSek
prop_EuroSek :: Double -> Bool
Type of the argument
Types Matter
• Types determine how computations are
performed
Specify which type to use
Main> 123456789*123456789 :: Double
1.52415787501905e+016
Correct to 15 figures
Main> 123456789*123456789 :: Integer
15241578750190521
Hugs must know the type of
each expression before
computing it.
The exact result – 17 figures
(but must be an integer)
Type Checking
• Infers (works out) the type of every
expression
• Checks that all types match – before
running the program
Our Example
Main> :i price
price :: Integer
Main> :i sek
sek :: Double -> Double
Main> sek price
ERROR - Type error
*** Expression
*** Term
*** Type
*** Does not match
in application
: sek price
: price
: Integer
: Double
Why did it work before?
Certainly works to say 53
What is the type of 53?
Main> sek 53
485.82026
Main> 53 :: Integer
53 can be used with several
53
types – it is overloaded
Main> 53 :: Double
53.0
Main> price :: Integer
Giving it a name fixes
53
the type
Main> price :: Double
ERROR - Type error in type annotation
*** Term
: price
*** Type
: Integer
*** Does not match : Double
Fixing the Problem
• Definitions can be given a type signature
which specifies their type
price :: Double
price = 53
Main> :i price
price :: Double
Main> sek price
485.82026
Always Specify Type Signatures!
• They help the reader (and you) understand
the program
• The type checker can find your errors more
easily, by checking that definitions have the
types you say
• Type error messages will be easier to
understand
• Sometimes they are necessary (as for price)
Example with Type Signatures
euroRate :: Double
euroRate = 9.16642
sek, euro :: Double -> Double
sek x = x*euroRate
euro x = x/euroRate
prop_EuroSek :: Double -> Bool
prop_EuroSek x = euro (sek x) ~== x
What is the type of 53?
Main> :i 53
Unknown reference `53'
Main> :t sek 53
sek 53 :: Double
Main> :t 53
53 :: Num a => a
If a is a numeric type
:i only works for
names
But :t gives the type (only)
of any expression
Then 53 can have type a
Main> :i *
infixl 7 *
(*) :: Num a => a -> a -> a -- class
member
Then * can have type a->a->a
What is Num exactly?
Main>
:i Num
A ”class” of types
-- type class
...
class (Eq a, Show a) => Num a where
(+) :: a -> a -> a
With these
(-) :: a -> a -> a
operations
(*) :: a -> a -> a
...
-- instances:
instance Num Int
Types which belong to
instance Num Integer
this class
instance Num Float
instance Num Double
instance Integral a => Num (Ratio a)
Examples
Main> 2 + 3.5
5.5
2, +, and 3.5 can all work on
Double
Main> True + 3
ERROR - Cannot infer instance
*** Instance
: Num Bool
*** Expression : True + 3
Sure enough,
Bool is not in the
Num class
A Tricky One!
Main> sek (-10)
-91.6642
Main> sek -10
ERROR - Cannot infer instance
*** Instance
: Num (Double -> Double)
*** Expression : sek - 10
What’s going on?
Operators Again
Main> :i +
infixl 6 +
(+) :: Num a => a -> a -> a
-- class member
Main> :i *
infixl 7 *
(*) :: Num a => a -> a -> a
-- class member
The binding power (or precedence) of an operator
– * binds tighter than + because 7 is greater than 6
Giving ~== a Precedence
Main> 1/2000000 ~== 0
ERROR - Cannot infer instance
*** Instance
: Fractional Bool
*** Expression : 1 / 2000000 ~== 0
Wrongly interpreted as
1 / (2000000 ~== 0)
Instead of
(1/2000000) ~== 0
Giving ~== a Precedence
• ~== should bind the same way as ==
Main> :i ==
infix 4 ==
(==) :: Eq a => a -> a -> Bool
-- class member
infix 4 ~==
x ~== y = abs (x-y) < 0.000001
Main> 1/2000000 ~== 0
True
Summary
• Think about the properties of your program
– ... and write them down
• It helps you understanding
– the problem you are solving
– the program you are writing
• It helps others understanding what you did
– co-workers
– customers
– you in 1 year from now
Cases and Recursion
Example: The squaring function
• Example: a function to compute
-- sq x returns the square of x
sq :: Integer -> Integer
sq x = x * x
Evaluating Functions
• To evaluate sq 5:
– Use the definition—substitute 5 for x
throughout
• sq 5 = 5 * 5
– Continue evaluating expressions
• sq 5 = 25
• Just like working out mathematics on paper
sq x = x * x
Example: Absolute Value
• Find the absolute value of a number
-- absolute x returns the absolute value of x
absolute :: Integer -> Integer
absolute x = undefined
Example: Absolute Value
• Find the absolute value of a number
Programs must often
choose between
• Two cases!
– If x is positive, result is x
– If x is negative, result is -x
alternatives
-- absolute x returns the absolute value of x
Think of the cases!
absolute :: Integer -> Integer
These are guards
absolute x | x > 0 = undefined
absolute x | x < 0 = undefined
Example: Absolute Value
• Find the absolute value of a number
• Two cases!
– If x is positive, result is x
– If x is negative, result is -x
-- absolute x returns the absolute value of x
absolute :: Integer -> Integer
Fill in the result in
absolute x | x > 0 = x
each case
absolute x | x < 0 = -x
Example: Absolute Value
• Find the absolute value of a number
• Correct the code
-- absolute x returns the absolute value of x
absolute :: Integer -> Integer
>= is greater than
absolute x | x >= 0 = x
or equal, ¸
absolute x | x < 0 = -x
Evaluating Guards
• Evaluate absolute (-5)
– We have two equations to use!
– Substitute
• absolute (-5) | -5 >= 0 = -5
• absolute (-5) | -5 < 0 = -(-5)
absolute x | x >= 0 = x
absolute x | x < 0 = -x
Evaluating Guards
• Evaluate absolute (-5)
– We have two equations to use!
– Evaluate the guards
• absolute (-5) | False = -5
• absolute (-5) | True = -(-5)
absolute x | x >= 0 = x
absolute x | x < 0 = -x
Discard this
equation
Keep this one
Evaluating Guards
• Evaluate absolute (-5)
– We have two equations to use!
– Erase the True guard
• absolute (-5) = -(-5)
absolute x | x >= 0 = x
absolute x | x < 0 = -x
Evaluating Guards
• Evaluate absolute (-5)
– We have two equations to use!
– Compute the result
• absolute (-5) = 5
absolute x | x >= 0 = x
absolute x | x < 0 = -x
Notation
• We can abbreviate repeated left hand sides
absolute x | x >= 0 = x
absolute x | x < 0 = -x
absolute x | x >= 0 = x
| x < 0 = -x
• Haskell also has if then else
absolute x = if x >= 0 then x else -x
Example: Computing Powers
• Compute
(without using built-in x^n)
Example: Computing Powers
• Compute
(without using built-in x^n)
• Name the function
power
Example: Computing Powers
• Compute
(without using built-in x^n)
• Name the inputs
power x n = undefined
Example: Computing Powers
• Compute
(without using built-in x^n)
• Write a comment
-- power x n returns x to the power n
power x n = undefined
Example: Computing Powers
• Compute
(without using built-in x^n)
• Write a type signature
-- power x n returns x to the power n
power :: Integer -> Integer -> Integer
power x n = undefined
How to Compute power?
• We cannot write
– power x n = x * … * x
n times
A Table of Powers
n
power x n
0
1
1
x
2
x*x
3
x*x*x
• Each row is x* the previous one
• Define power x n to compute the nth row
A Definition?
power x n = x * power x (n-1)
• Testing:
Main> power 2 2
ERROR - stack overflow
Why?
A Definition?
power x n | n > 0 = x * power x (n-1)
• Testing:
– Main> power 2 2
– Program error: pattern match failure: power 2 0
A Definition?
First row
of the
table
power x 0 = 1
power x n | n > 0 = x * power x (n-1)
• Testing:
– Main> power 2 2
–4
The BASE CASE
Recursion
• First example of a recursive function
– Defined in terms of itself!
power x 0 = 1
power x n | n > 0 = x * power x (n-1)
• Why does it work? Calculate:
– power 2 2 = 2 * power 2 1
– power 2 1 = 2 * power 2 0
– power 2 0 = 1
Recursion
• First example of a recursive function
– Defined in terms of itself!
power x 0 = 1
power x n | n > 0 = x * power x (n-1)
• Why does it work? Calculate:
– power 2 2 = 2 * power 2 1
– power 2 1 = 2 * 1
– power 2 0 = 1
Recursion
• First example of a recursive function
– Defined in terms of itself!
power x 0 = 1
power x n | n > 0 = x * power x (n-1)
• Why does it work? Calculate:
– power 2 2 = 2 * 2
– power 2 1 = 2 * 1
– power 2 0 = 1
No circularity!
Recursion
• First example of a recursive function
– Defined in terms of itself!
power x 0 = 1
power x n | n > 0 = x * power x (n-1)
• Why does it work? Calculate:
– power 2 2 = 2 * power 2 1
– power 2 1 = 2 * power 2 0
– power 2 0 = 1
The STACK
Recursion
• Reduce a problem (e.g. power x n) to a
smaller problem of the same kind
• So that we eventually reach a ”smallest”
base case
• Solve base case separately
• Build up solutions from smaller solutions
Powerful problem solving strategy
in any programming language!
Counting the regions
• n lines. How many regions?
remove
one line ...
problem is
easier!
when do
we stop?
The Solution
• Always pick the base case as simple as
possible!
regions :: Integer -> Integer
regions 0
=1
regions n | n > 0 = regions (n-1) + n
Course Text Book
The Craft of Functional Programming (second
edition), by Simon Thompson. Available at
Cremona.
An excellent book which goes well beyond this
course, so will be useful long after the course is
over.
Read Chapter 1 to 4 before the laboratory
sessions on Wednesday, Thursday and Friday.
uses Hugs
instead of
GHCi
Course Web Pages
Updated almost
daily!
URL:
http://www.cs.chalmers.se/Cs/Grundutb/Kurser/funht/
•These slides
•Schedule
•Practical information
•Assignments
•Discussion board