Transcript Type Class

Advanced Programming
Languages
Lecture 1
NCCU CS Dept.
Fall 2005
Sept. 19, 2005
Topics
•
•
•
•
•
•
•
•
Haskell, Part 1
Lambda Calculus
Operational Semantics
Denotational Semantics
Polymorphism & Type Inference
Haskell, Pat 2 (Type classes, …)
Subtyping and OO
Research Papers
Reading Materials
• Lecture Notes from Prof. Johan Glimming
• Haskell
– Tutorial: A Gentle Introduction to Haskell
• SML lecture notes
• Other lecture notes
• Textbooks:
– B. Pierce, Type Systems and Programming
Languages, MIT Press, 2002
– Nielson’s, Semantics with Applications, Draft, 2005
• Papers
Haskell-based Textbooks
• Simon Thompson. Haskell: The Craft of Functional
Programming, Addison Wesley, 1999.
• Richard Bird. Introduction to Functional Programming Using
Haskell, second edition, Prentice Hall Europe, 1998.
• Paul Hudak. The Haskell School of Expression, Cambridge
University Press, 2000.
• H. C. Cunningham. Notes on Functional Programming with
Gofer, Technical Report UMCIS-1995-01, University of
Mississippi, Department of Computer and Information Science,
Revised January 1997.
http://www.cs.olemiss.edu/~hcc/reports/gofer_notes.pdf
Other FP Textbooks Of Interest
• Fethi Rabhi and Guy Lapalme. Algorithms: A Functional
Approach, Addison Wesley, 1999.
• Chris Okasaki. Purely Functional Data Structures, Cambridge
University Press, 1998.
Programming Language Paradigms
• Imperative languages
–
–
–
–
have implicit states
use commands to modify state
express how something is computed
include C, Pascal, Ada, …
• Declarative languages
–
–
–
–
have no implicit states
use expressions that are evaluated
express what is to be computed
have different underlying models
• functions: Lisp (Pure), ML, Haskell, …spreadsheets? SQL?
• relations (logic): Prolog (Pure) , Parlog, …
Orderly Expressions and
Disorderly Statements
{ x = 1; y = 2; z = 3 }
x= 3*x+2*y+z
y= 5*x–y+2*z
Values of x and y depend upon
order of execution of statements
x represents different values
in different contexts
Summary: Why Use Functional
Programming?
• Referential transparency
– symbol always represents the same value
– Equational reasoning (equals can be substituted by equals)
• easy mathematical manipulation, parallel execution, etc.
• Expressive and concise notation
• Higher-order functions
– take/return functions
– powerful abstraction mechanisms
• Lazy evaluation
– defer evaluation until result needed
– new algorithmic approaches
• Polymorphic Type systems
Why Teach/Learn FP and Haskell?
• Introduces new problem solving techniques
• Improves ability to build and use higher-level
procedural and data abstractions
• Helps instill a desire for elegance in design and
implementation
• Increases comfort and skill in use of recursive
programs and data structures
• Develops understanding of programming languages
features such as type systems
• Introduces programs as mathematical objects in a
natural way
Haskell: http://haskell.org/
• Haskell is a general purpose, purely functional
programming language.
• Started in 1987; current version Haskell 98 (2002 revised)
– Yale Univ. & Glasgow Univ.
– Chalmers Univ. (Sweden)
• Many free implementations:
– Hugs 98, a popular Haskell interpreter (written in C)
• Derived from Gopher, by Mark Jones
– GHC, the Glasgow Haskell Compiler
– …
• Good course websites:
– http://csit.nottingham.edu.my/~cmichael/Teaching/Feb05/G51FUN/
fun.html
– http://www.cs.chalmers.se/Cs/Grundutb/Kurser/d1pt/d1pta/external
.html
Haskell Timeline
Sept 87: kick off
Apr 90: Haskell 1.0
Aug 91: Haskell 1.1 (153pp)
May 92: Haskell 1.2 (SIGPLAN Notices) (164pp)
May 96: Haskell 1.3. Monadic I/O,
separate library report
Apr 97: Haskell 1.4 (213pp)
The Book!
Feb 99: Haskell 98 (240pp)
Dec 02: Haskell 98 revised (260pp)
A Short Tour to Hugs
Definitions
• Definitions
name :: type
e.g.:
size :: Int
size = 12 - 3
• Function definitions
name :: t1 -> t2 -> … -> tk -> t
function name
types of
arguments
e.g.:
exOr :: Bool -> Bool -> Bool
exOr x y = (x || y) && not (x && y)
type of result
Variable binders: x and y get their values from the argument
(Integer  Integer)  Integer  Integer
Technique: Accumulating parameter
“==“
Currying and Partial Evaluation
add :: (Int,Int) -> Int
add (x,y) = x + y
add' :: Int->(Int->Int)
add' x y = x + y
? add(3,4) => 7
? add (3, ) => error
? add’ 3 4 => 7
? add’ 3
add’ takes one argument and
returns a function
Takes advantage of Currying
(add’ 3) :: Int -> Int
(add’ 3) x = 3 + x
((+) 3)
Fold Right
Abstract different binary operators to be applied
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z []
=z
-- binary op, identity, list
foldr f z (x:xs) = f x (foldr f z xs)
sumlist :: [Int] -> Int
sumlist xs = foldr (+) 0 xs
concat' :: [[a]] -> [a]
concat' xss = foldr (++) [] xss
Using Partial Evaluation
doublePos :: [Int] -> [Int]
doublePos xs = map ((*) 2) (filter ((<) 0) xs)
• Using operator section notation
doublePos xs = map (*2) (filter (0<) xs)
• Using list comprehension notation
doublePos xs = [ 2*x | x <- xs, 0< x ]
Quicksort Algorithm
•
•
•
If sequence is empty, then it is sorted
Take any element as pivot value
Partition rest of sequence into two parts
1. elements < pivot value
2. elements >= pivot value
•
•
Sort each part using Quicksort
Result is sorted part 1, followed by pivot,
followed by sorted part 2
Quicksort in C
qsort( a, lo, hi ) int a[ ], hi, lo;
{ int h, l, p, t;
if (lo < hi)
{ l = lo; h = hi; p = a[hi];
do
{ while ((l < h) && (a[l] <= p)) l = l + 1;
while ((h > l) && (a[h] >= p)) h = h – 1 ;
if (l < h) { t = a[l]; a[l] = a[h]; a[h] = t; }
} while (l < h);
t = a[l]; a[l] = a[hi]; a[hi] = t;
qsort( a, lo, l-1 ); qsort( a, l+1, hi );
}
}
Quicksort in Haskell
qsort :: [Int] -> [Int]
qsort []
= []
qsort (x:xs) = qsort lt ++ [x] ++ qsort greq
where
lt
= [y | y <- xs, y < x]
greq = [y | y <- xs, y >= x]
qsort:: Ord a => [a]  [a]
Lazy Evaluation
Lazy Evaluation
Do not evaluate an expression unless its value is needed
iterate :: (a -> a) -> a -> [a]
iterate f x = x : iterate f (f x)
interate (*2) 1 => [1, 2, 4, 8, 16, …]
powertables :: [[Int]]
powertables = [ iterate (*n) 1 | n <- [2..] ]
powertables => [ [1, 2, 4, 8,…],
[1, 3, 9, 27,…],
[1, 4,16, 64,…],
[1, 5, 25,125,…], … ]
Prime Numbers: Sieve of Eratosthenes
Algorithm
1.
2.
3.
4.
Generate list 2, 3, 4, …
Mark first element p of list as prime
Delete all multiples of p from list
Return to step 2
primes :: [Int]
primes = map head (iterate sieve [2..])
sieve (p:xs) = [x | x <- xs, x `mod` p /= 0 ]
takewhile (< 10000) primes
Hamming’s Problem
Produce the list of integers
• increasing order (hence no duplicate values)
• begins with 1
• if n is in list, then so is 2*n, 3*n, and 5*n
• list contains no other elements
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, …
Hamming Program
ham :: [Int]
ham = 1 : merge3 [ 2*n | n <- ham ]
[ 3*n | n <- ham ]
[ 5*n | n <- ham ]
merge3 :: Ord a => [a] -> [a] -> [a] -> [a]
merge3 xs ys zs = merge2 xs (merge2 ys zs)
merge2 xs'@(x:xs)
|x<y
=
|x>y
=
| otherwise =
ys'@(y:ys)
x : merge2 xs ys'
y : merge2 xs' ys
x : merge2 xs ys
Parametric Polymorphism+Overloading
The list length function:
length :: [a] -> Int
length [] = 0
length (x : xs) = length xs + 1
What happens when overloaded operators
meet parametric polymorphism?
double_sum :: a -> a -> a ??? Too general
double_sum x y =
2*x + 2*y
double_sum :: int -> int -> int ??? Too restricted
One more Example:
The Membership function
• Testing membership of a list in Haskell (infix form)
x `elem` []
x `elem` (y:ys)
= False
= x==y || (x `elem` ys)
What should be the type for “elem”?
• elem :: a  [a]  Bool?
• Are all types comparable for equality?
Type Classes in Haskell
(Parametric Overloading)
• Not all types are comparable for equality. It should be a
constraint to the type of “elem”.
elem :: For all type a that support equality, a  [a]  Bool
• A Type Class is a collection of types that support certain
operations, called the methods of the class.
class Eq a where
(==) :: a -> a -> Bool
It state that a type a is an instance of the class Eq if there is
an (overloaded) operation ==, of the appropriate type,
defined on it
• So the type for “==“ is
Eq a => :: a -> a -> Bool
• So the type for “elem” should be
elem :: Eq a => a  [a]  Bool
Instance Declaration for Type Classes
• Instance declaration:
instance Eq Integer where
x == y = x `integerEq` y
The definition of == is called a method. The function
integerEq happens to be the primitive function that
compares integers for equality.
• Composite and User-defined types can be declared to be
instances, too.
instance (Eq a) => Eq (List a) where
lst1 == lst2
= …
Type Classes in Haskell, Cont’d
• Another example of Type class declaration in Haskell
class Num a where
(+), (-), (*)
:: a -> a -> a
negate
:: a -> a
…
• In Haskell, numeric literals such as 0, 1 are overloaded,
too:
double_sum x y =
2*x + 2*y
– Haskell infers double_sum is a (numerical) function:
Num a => a -> a -> a
– For all types a that is an instance of type class Num, from a to a.
Implementing Type Classes in Haskell
• Instance Declaration
instance Num Int where
(*) = IntMul
-- primitive fun in Prelude
(-) = IntSub -- primitive fun in Prelude
…
• The def. above is turn into a dictionary of methods:
NumIntDictionary
• Dictionary passing style via type inference
factorial n = …
is translated to
factorial NumDict n =
n (select ‘*’ from NumSict)
factorial (n (select ‘-’ from NumSict) 1)
Class Extension in Type Classes
• Class extension in Haskell:
class (Eq a) => Ord a
(<), (<=), (>=), (>)
max, min
where
:: a -> a -> Bool
:: a -> a -> a
Note the context in the class declaration. We say that
Eq is a superclass of Ord (conversely, Ord is a
subclass of Eq), and any type which is an instance of
Ord must also be an instance of Eq.