Transcript document

Haskell A Perspective
Presented by Gábor Lipták
April 2011
Topics
•
•
•
•
•
•
Why?
Functional
Haskell highlights
Development
Concurrency approaches
Q&A
Why should you be interested (as a
Java, .Net, Ruby developer)?
• Knowing this different language will help you improve your
understanding and skills in your "main" language
• Research proving ground for features coming to your
language some while later (or to languages hosted on your
VM, F#, Scala, Clojure)
• Significant scaling (today)
• Fun:)
Scalability
Functional?
Programming with (mathematical) functions
In functional programming, programs are executed by
evaluating expressions, in contrast with imperative
programming where programs are composed of statements
which change global state when executed. Functional
programming typically avoids using mutable state.
Prelude> filter even [1..10]
filter :: (a -> Bool) -> [a] -> [a]
filter _ []
= []
filter p (x:xs) | p x
= x : filter p xs
| otherwise = filter p xs
Functional??
Object oriented: object method args
Functional: function args
Lambdas:
add' = (+)
test1add' = add' 3 5
test2add' = 3 `add'` 5
add'' = \x -> (\y -> x + y)
test1add'' = add'' 3 5
Purely Functional
• First class/Higher order functions
• Pure functions (no side effects)
o Immutable data
o Referential transparency (each call returns the same
result)
o Lazy evaluation
o Purity and effects (monads)
• Type system/Type inference
• Tail recursion
• Compositional/Declarative/Concise
• Lazy (vs. eager) evaluation
Purity (adapted from Caging the effects monster)
Introduction
Named after Haskell Brooks Curry, was an American
mathematician and logician. Two programming languages
named after him.
Lambda calculus is a formal system for function definition,
function application and recursion.
Prelude> 2^2500
3758280234548012036833624189723865048677365517592586770565238397822316814983377085357
327
2575265884433370245774952605776030922789135161776565190731096878023646469404331623656
214
67244164785911318325937291112215801805317492327775155799698990751422139691179948773438
020
4942162495440221452939078164756333953502477258490160766686298256791862284963616020887
736
58349501637901885230262474405073903820321888923861099058697067531432439211984822120754
44
0224333665547868565593896895856381265823772240377217022399914414660261857526515029364
722
80911018500320375496336749951569521541850441747925844066295279671872605285792552660130
702
Reserved Words
•
•
•
•
•
•
•
•
•
case
class
data
deriving
do
else
if
import
in
•
•
•
•
•
•
•
•
•
•
•
infix
infixl
infixr
instance
let
of
module
newtype
then
type
where
Polymorphically Statically Typed (type
inference)
Prelude> :t map
map :: (a -> b) -> [a] -> [b]
data Bool = False | True
data Roulette = Black | Red | Zero | DoubleZero
deriving (Eq, Ord, Show, Read, Bounded, Enum)
type PhoneNumber = String
type Name = String
type PhoneBook = [(Name,PhoneNumber)]
Eliminating easy to make errors during compile time.
Type Classes
square :: Num a => a -> a
square x = x *x
class Num a where
(*) :: a -> a -> a
instance Num Int where
a * b = mulInt a b -- mulInt is a primitive
class Increment a where
increment :: Num -> Num
instance Increment Int where
increment n = n + 1
Lazy (thunks)
numsFrom n = n : numsFrom (n+1)
squares = map (^2) (numsfrom 0)
take 5 squares => [0,1,4,9,16]
take 3 (sort xs)
Thunk represents an unevaluated expression.Storing and
evaluating thunks are costly.
Folds
foldr (+) 0 (1:2:3:[])
== 1 + foldr (+) 0 (2:3:[])
== 1 + (2 + foldr (+) 0 (3:[])
== 1 + (2 + (3 + foldr (+) 0 []))
== 1 + (2 + (3 + 0))
foldl (+) 0 (1:2:3:[])
== foldl (+) (0 + 1) (2:3:[])
== foldl (+) ((0 + 1) + 2) (3:[])
== foldl (+) (((0 + 1) + 2) + 3) []
== (((0 + 1) + 2) + 3)
Tail recursion (and accumulator)
my_sum :: [ Integer ] -> Integer
my_sum [] = 0
my_sum (x:xs) = x + my_sum xs
main :: IO ()
main = print (my_sum [1 .. 10000000])
my_sum :: [ Integer ] -> Integer
my_sum xs = my_sum' 0 xs
where
my_sum' acc [] = acc
my_sum' acc (x:xs) = my_sum' (acc+x) xs
main :: IO ()
main = print (my_sum [1 .. 10000000])
Pattern Matching and Guards
lucky :: (Integral a) => a -> String
lucky 3 = "Lucky Number!"
lucky x = "Sorry, you're out of luck!"
numberDesc :: (Integral) => a -> String
numberDesc number
| number < 0 = "negative"
| number > 0 = "positive"
| otherwise = "zero"
Higher order functions, currying
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
mapM :: Monad m => (a -> m b) -> [a] -> m [b]
mapM_ :: Monad m => (a -> m b) -> [a] -> m ()
map (+3) [1,5,3,1,6]
map (\(a,b) -> a + b) [(1,2),(3,5),(6,3),(2,6),(2,5)]
take5 :: [Char] -> [Char]
take5 = take 5
Monads (1)
Monad is a computation returning result of type a
Computations are pure during construction, and might
have side effects when running (lazy)
Monads (2)
instance Monad Maybe where
return x = Just x
Nothing >>= f = Nothing
Just x >>= f = f x
fail _ = Nothing
Prelude> Nothing >> Just 3
Nothing
Prelude> Just 3 >> Just 4
Just 4
Prelude> Just 3 >> Nothing
Nothing
Monads (3)
main :: IO ()
main = do
putStrLn "Hello, what is your name?"
name <- getLine
putStrLn ("Hey " ++ name ++ "!")
More than you care to read (just search for Monad tutorial :) In
particular look for parsing examples.
You become a real Haskell programmer only after publishing
your own Monad Tutorial :)
Development
Use your editor (vim,Emacs), Leksah, Eclipse, VisualStudio to
develop
Project structures are detailed at haskell.org
Use of types (and type signatures) helps to write correct code
Profiling (for space "leakage" ...)
Listing sparks/concurrency details when running
QuickCheck
Testing invariants in the code Lots of "clones" for other
languages
import Test.QuickCheck
take5 :: [Char] -> [Char]
take5 = take 5
main = do
quickCheck (\s -> length (take5 s) == 5)
quickCheck (\s -> length (take5 s) <= 5)
*Main> main
*** Failed! Falsifiable (after 1 test):
""
+++ OK, passed 100 tests.
Other tools
•
•
•
•
•
•
Build system: Cabal
Package repository: Hackage
Code search engine Hoogle
Code search engine Hayoo!
Haddock documentation tool
HUnit (from xUnit series)
Concurrency Approaches
• Explicit (lightweight) threads and STM (software
transactional memory)
• Semi-implicit (`par`, `pseq`) a "hint"
• Data parallel
Explicit threads
Not dissimilar to threads found in other languages, with same
benefits/drawbacks ...
• Non-deterministic by design
• Monadic: forkIO and STM
• forkIO :: IO () −> IO ThreadId
• forkOS :: IO () −> IO ThreadId
Software Transactional Memory
atomically :: STM a -> IO a
retry :: STM a
orElse :: STM a -> STM a -> STM a
...
newTVar :: a -> STM (TVar a)
readTVar :: TVar a -> STM a
writeTVar :: TVar a -> a -> STM ()
Emphasis on composition
Similar to database transactions
Semi-implicit
hard to ensure the right granularity
• Deterministic
• Pure: par and seq
infixr 0 `par`
infixr 1 `pseq`
par :: a -> b -> b
pseq :: a -> b -> b
equivalent to par a b = b
pseq a b = _|_ if a = _|_
= b otherwise
_|_ (read "bottom", non terminating expression).
Example
import Control.Parallel
cutoff :: Int
cutoff = 20
parFib :: Int -> Int
parFib n | n < cutoff = fib n
parFib n = p `par` q `pseq` (p + q)
where
p = parFib $ n - 1
q = parFib $ n - 2
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
main :: IO ()
main = print $ parFib 40
Dual core
$ time ./parfib.exe +RTS -N1
102334155
real 0m1.998s
user 0m0.015s
sys 0m0.015s
$ time ./parfib.exe +RTS -N2
102334155
real 0m1.337s
user 0m0.015s
sys 0m0.015s
Data parallel
(used in languages like High Performance Fortran)
• Deterministic
• Pure: parallel arrays
• Shared memory initially; distributed memory eventually;
possibly even GPUs
• mapP :: (a -> b) -> [:a:] -> [:b:]
• zipWithP :: (a -> b -> c) -> [:a:] -> [:b:] -> [:c:]
• filterP :: (a -> Bool) -> [:a:] -> [:a:]
• sumP :: Num a => [:a:] -> a
• import GHC.PArr
Final comments
• Very active community (Haskell Cafe and other mailing lists
with very good info to noise ratio)
• Great support for algorithms
• Lots of libraries (many of them are very specialised)
• Very wide use in academia, less outside
• Might be hard to find knowledgeable developers
Further information
haskell.org
Real World Haskell
Yet Another Haskell Tutorial
Learn You a Haskell for a Great Good!
http://tryhaskell.org/
HEAT (Haskell Educational Advancement Tool)
Haskell Cheat Sheet
The Monad.Reader (if you want to bend your mind :)
Simon Peyton-Jones (Principal Researcher at Microsoft)
Philip Wadler
Galois Multicore/Don Stewart
Microsoft Channel9Going Deep Lectures
Carnegie Mellon curriculum change
Q&A