Advanced Programming 2018 – Introduction to (the course and) Haskell
Advanced Programming 2018
Introduction to (the course and) Haskell
Andrzej Filinski
andrzej@di.ku.dk
(Administrative info adapted from
slides by Ken Friis Larsen)
Department of Computer Science
University of Copenhagen
September 4, 2018
1 / 37
Today’s Menu
I General course information
I Course content and motivation
I Introduction to Haskell
2 / 37
What This Course Is About
The purpose of this course is to provide practical experience with
sophisticated programming techniques and paradigms from a
language-based perspective. The focus is on high-level programming
and systematic construction of well-behaved programs.
– http://kurser.ku.dk/course/ndaa09013u/2018-2019
3 / 37
http://kurser.ku.dk/course/ndaa09013u/2018-2019
The Languages We’ll Use
I Haskell: lazy, pure, statically typed, functional programming
I http://haskell.org/
I Erlang: eager, fail-safe, distributed programming
I http://erlang.org/
I (Pure) Prolog: declarative, logic programming
I SWI-Prolog (http://www.swi-prolog.org/)
I or GNU Prolog (http://www.gprolog.org/)
4 / 37
http://haskell.org/
http://erlang.org/
http://www.swi-prolog.org/
http://www.gprolog.org/
The Skills You Will Practice
I Use program structuring principles and design patterns, such as
monads, to structure the code so that there is a clear separation of
concerns.
I Use a parser combinator library to write a parser for a medium-sized
language with a given grammar, including changing the grammar so
that it is on an appropriate form.
I Use parallel algorithm skeletons such as map-reduce to write data
exploring programs.
I Implement simple concurrent/distributed servers using message
passing, with appropriate use of synchronous and asynchronous
message passing.
I Use program structuring principles and design patterns for making
reliable distributed systems in the presence of software errors.
I Write idiomatic programs in a logic programming language.
5 / 37
What We Hope You’ll Go Away With
I You can write correct, efficient, and maintainable programs
with a clear separation of concerns
I You can quickly acquaint yourself with advanced programming
techniques, from academic literature and/or technical
documentation
I You can use those techniques to solve challenging, realistic
problems
I You can give an assessment of your own code, based on a
systematic evaluation of correctness, selection of algorithms
and data structures, error scenarios, and elegance.
6 / 37
The Course Team
I Lecturers
I Andrzej
Haskell, Prolog
I Ken (course organizer)
Erlang, QuickCheck
I Teaching assistants
I Abraham
I Joachim
I Mathias
I Robert
I Troels
7 / 37
Online Information
I The course home page can be found in Absalon
I The home page for the course contains
I a detailed lecture plan
I (links to) reading materials
I assignments and exercises
I a forum for questions and discussion
I latest news and other important course information
I Slides may be uploaded some time after the lecture
I Keep an eye on the course home page throughout the block
I Lectures: Tuesday 9:15-11:00 and Thursday 10:15-12:00,
always in Aud. “Lille UP1”, DIKU.
I Labs: Thursday afternoons (2 hours) and Tuesdays after the
lecture (1 hour). See room assignments on Absalon.
8 / 37
How You Should Spend Your Time
I A typical week:
Attending lectures: 4 hours
Solving pre-lecture quizzes 0.25 hours
Reading (“preload” and “by-need”): 6 hours
Programming & documentation: 10–12 hours
Of which, ∼ 3 hours in lab sessions.
I We will try to provide open-ended exercises as inspiration for
how to work with the topics.
I The exercises are excellent preparation for the mandatory
assignments
I False economy to start directly on the assignment problems
I If you spend significantly less or more time on the course,
please let us know.
9 / 37
How You Should Spend Your Time
I A typical week:
Attending lectures: 4 hours
Solving pre-lecture quizzes 0.25 hours
Reading (“preload” and “by-need”): 6 hours
Programming & documentation: 10–12 hours
Of which, ∼ 3 hours in lab sessions.
I We will try to provide open-ended exercises as inspiration for
how to work with the topics.
I The exercises are excellent preparation for the mandatory
assignments
I False economy to start directly on the assignment problems
I If you spend significantly less or more time on the course,
please let us know.
9 / 37
Getting to the Exam
I Pass ≥ 4 out of 6 mandatory assignments:
I Assignment 0: Arithmetic Expressions (Haskell)
I Assignment 1: TBD interpreter (Haskell)
I Assignment 2: TBD parser (Haskell)
I Assignment 3: TBD (Prolog)
I Assignment 4: TBD (Erlang)
I Assignment 5: TBD (Erlang)
I We recommend that you seriously attempt them all
I But especially assignments 1, 3, and 5
I Normally published Tuesday, due Wednesday of following week
(at 20:00).
I Pair programming strongly encouraged (max 2 people)
I Do take turns as “driver” vs. “navigator”!
10 / 37
Exam
I One week take-home exam
I Typically ∼4 questions
I Each question is like an assignment
I Estimated ∼25 hours of work in total
I Strictly individual
11 / 37
Let’s Begin!
The purpose of this course is to provide practical experience with
sophisticated programming techniques and paradigms from a
language-based perspective. The focus is on high-level programming
and systematic construction of well-behaved programs.
– http://kurser.ku.dk/course/ndaa09013u/2018-2019
12 / 37
http://kurser.ku.dk/course/ndaa09013u/2018-2019
A Language-Based Perspective
Why would you learn a new
programming language?
13 / 37
A Language-Based Perspective
Different languages offer:
I Different levels of abstraction
I Contrast assembly, C, and Python
I Different assurances
I Static (compile-time) analyses
I Dynamic (run-time) checking
I Different programming models
I Functional vs imperative vs declarative programming
I Lazy evaluation vs eager evaluation vs proof search
I Message passing vs shared memory
I Different primitives, libraries, and frameworks
Exposure to variety makes you a more effective programmer, in any
language.
14 / 37
Why Haskell?
I Modern functional programming (FP) language
I Introduced ∼1990, but has been evolving continuously since
I Vibrant user and developer community
I Good cross-platform support
I Directly used in growing number of application domains
I Useful medium to present general programing abstractions and
principles
I Easier to explain many ideas in a functional setting
I Many FP concepts and techniques steadily diffusing into
“mainstream” languages
I Goal of course is not to make you Haskell experts
I “Program into a language, not in it.” –D.Gries
I Do exploit constructs and idioms of host language, but don’t let it
constrain your high-level thinking.
15 / 37
Haskell fundamentals
I Value-oriented (applicative) paradigm
I Will see others later in the course
I Main computation model: evaluation of expressions
I Not sequential execution of statements
I Though that can be accomodated as a special case
I Purely functional
I No hidden/silent side effects at all
I Strongly, statically typed
I Surprisingly many problems caught at compile time
I If you already know another typed functional language (SML,
OCaml, F#), today will be mainly a refresher
I Next time: Haskell-specific concepts and constructs
I If not, don’t panic!
I Basic concepts are really quite simple
16 / 37
Types
I Haskell (like Java, unlike C) is strongly typed.
I Types enforce abstractions, both language-provided and
programmer-defined.
I Cannot construct “ill-formed” values of a type
I No crashes/segfaults (“casting int to pointer”)
I No violation of data-structure invariants
I Cannot even observe interior structure of data values, except
through official API.
I No inspecting of heap/stack layout (“casting pointer to int”)
I No hidden dependencies on particular implementation
I Haskell (like C, unlike Python) is statically typed
I Only well-typed programs may even be run
I Type system is very flexible, normally unobtrusive
I A reported type error almost always reflects logical error in
program, not weakness/deficiency of type checker
I Once program type-checks, usually close to working
17 / 37
Types and values
I Types classify values.
I Notation: value :: type
I Usual complement of basic types, including:
I Integers: 3 :: Int, 43252003274489856000 :: Integer
I Floating point: 2.718281828 :: Double (Float rarely used)
I Booleans: True :: Bool
I Characters: ’x’ :: Char
I Strings: “new\nline” :: String
I Actually, type String = [Char] (list of characters)
I Compound types, including:
I Tuples: (2, 3.4, False) :: (Int, Double, Bool)
I Lists (homogeneous): [2,3,5,7] :: [Int]
I May be nested:
([(1, 2.0), (3, 4.0)], True) :: ([(Int, Double)], Bool)
18 / 37
Expression evaluation
I Expressions also have types
I The expression 2+2 :: Int evaluates to the value 4 :: Int
I Type safety: expression of a given type always evaluates to
value of that type.
I Or possibly a runtime error (e.g., div. by 0), or nontermination
I Far from trivial to show, given advanced features in Haskell’s
type system.
I Haskell implementations generally provide an interactive mode
I Traditionally called a read-eval-print loop (REPL)
I In Glasgow Haskell Compiler (GHC), invoked as ghci -W
I The -W enables useful warnings; omit at your peril!
I Ignore Prelude> in prompt for now.
I When using Stack, try alias ghci=’stack exec ghci — -W’
(or equivalent in your favorite shell).
19 / 37
Using the REPL environment
I Evaluate expressions:
> “foo” ++ “bar”
“foobar”
> head “foo”
’f’
> head “”
*** Exception: Prelude.head: empty list
I Can also typecheck expressions without evaluating:
> :type head “”
head “” :: Char
I Useful for debugging and experimentation, but not meant for writing
actual programs.
I Load a set of definitions from a file, then experiment interactively.
20 / 37
Expression forms
I Expressions are built up from
I Literals (atomic values): 42
I Constructors of compound values: [3,4]
I Constant and variable names (global or local):
pi, let x = 3 in x*x
I Function calls, prefix and infix: sqrt 4.0, 5 + 6
I Conditionals: if x > y then x else y
I Later generalized to case-expressions
I Large number of builtin constants and functions
I Most common ones are always available (standard prelude)
I Others must be imported from relevant module first
I Hoogle (haskell.org/hoogle/) is your friend!
I Can add own definitions:
I At top level (usually only one-liners)
> let courseName = “Advanced Programming”
> let wordCount s = length (words s)
I In separate file (next slide)
21 / 37
Definitions in separate file
I Slightly different syntax (no initial let).
I Should always include explicit types for all definitions
I Not formally required, but makes it much easier to understand
your code.
I Example: in file mydefs.hs
courseName :: String
courseName = “Advanced Programming”
wordCount :: String -> Int
wordCount s = length (words s)
I Can load from top-level loop
> :load mydefs.hs
> wordCount courseName
2
I Later: code in files should be organized into modules.
22 / 37
More about Haskell definitions
I Haskell syntax is indentation-sensitive!
I Always use spaces, not tabs!
I Configure your editor to insert spaces on tab-key presses
I Multiple definitions in a group must start at same level:
let f x = …
g y = …
in …
I Increase indentation to continue previous line
double x =
x + x
I All definitions (whether local or global) may be mutually recursive
isEven, isOdd :: Int -> Bool
isEven x = if x == 0 then True else isOdd (x – 1)
isOdd x = if x == 0 then False else isEven (x – 1)
23 / 37
More about Haskell functions
I Functions are values, too, but cannot be printed.
> :t wordCount
wordCount :: String -> Int
> wordCount
I Functions may have multiple arguments
addt :: (Int, Int) -> Int — tupled style
addt (x, y) = x + y
addc :: Int -> Int -> Int — curried style (preferred)
addc x y = x + y — [named for Haskell Brooks Curry]
I Functions may also take other functions as arguments
> map isOdd [2,3,5]
[False,True,True]
24 / 37
Anonymous functions
I Can construct functional values without naming them:
> map (\x -> x+3) [2,3,5]
[5,6,8]
I “\” pronounced “lambda” (here): ASCII approximation of “λ”.
I In fact, in typeset/pretty-printed Haskell code, you may see the
above rendered as “map (λx → x + 3) [2,3,5]”.
I Could define previous functions more explicitly as:
addt :: (Int, Int) -> Int — tupled style
addt = \p -> fst p + snd p
addc :: Int -> (Int -> Int) — curried style
addc = \x -> \y -> x + y
I Note: addc 3 actually returns the function \y -> 3 + y.
I addc 3 4 ‘ (\y -> 3 + y) 4 ‘ 3 + 4 ‘ 7.
25 / 37
Infix operators
I Haskell makes no fundamental distinction between functions
and operators, after lexing/parsing.
I Two syntactic classes of identifiers:
I Alphanumeric (prefix): any seq. of letters, digits, underscores
I … except a few reserved words, e.g., let
I Must start with lowercase letter
I Standard style: longName, not long_name
I Symbolic (infix): any seq. of special characters (!, #, $, +, …)
I Except a few reserved operators, e.g., ->.
I Must not start with a colon
I Can use any operator as (two-argument) function by enclosing
in parentheses: (+) 2 3 evaluates to 5.
I Conversely, can use any two-argument function as operator by
enclosing in backticks: 10 `mod` 4 evaluates to 2.
I Can specify desired precedence and/or associativity for
non-standard operators with infix{l,r,} keyword.
26 / 37
Polymorphism
I Functions (and other values) may be polymorphic
I Have type schemas, where some concrete types have been
replaced by (lowercase) type variables
dup :: a -> (a, a)
dup x = (x, x)
I Type system will automatically instantiate such types to match
use context:
I dup 5 evaluates to (5, 5)
I dup True evaluates to (True, True).
I …
I Sometimes polymorphism limited to certain classes of types:
I Numeric types: Int, Double, …
I (+) :: Num a => a -> a -> a
I 2 + 3 evaluates to 5
I 2.0 + 3.0 evaluates to 5.0
I “2” + “3” is a type error
I Equality types: almost all except functions
I (==) :: Eq a => a -> a -> Bool
I More about type classes (including defining your own) next time.
27 / 37
Working with lists
I Have already seen how to take apart tuples
I let add (x, y) = x + y
I let (q, r) = 10 `quotRem` 3 in …
I For lists, note that [3,4,5] syntax is actually syntactic sugar for
3 : (4 : (5 : []))
I [] :: [a] is sometimes called nil.
I (:) :: a -> [a] -> [a] is usually called cons.
I Any well-formed list (and there is no other kind!) is either
empty ([]) or of the form (h : t) for some h and t .
I Can define functions over lists by covering both possibilities:
myReverse :: [a] -> [a]
myReverse [] = []
myReverse (h : t) = myReverse t ++ [h]
28 / 37
Pattern matching, continued
I Can pattern match on several arguments at once
merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys) = if x<=y then x:merge xs (y:ys)
else y:merge (x:xs) ys
I In case of overlaps, first successful match is chosen
I ghci -W warns about uncovered cases
I Runtime error if matching fails
I Can also use case for pattern matching
case filter isOK attempts of
[] -> “no solutions”
[x] -> “one solution”
_ -> “several solutions”
(Again indentation is significant.)
I Wildcard pattern _ matches everything
29 / 37
Even more pattern matching
I Patterns must only bind variables at most once; this is illegal:
myElem :: a -> [a] -> Bool
myElem x [] = False
myElem x (x:ys) = True — note: x occurs twice
myElem x (_:ys) = myElem x ys
I But can write with explicit Boolean guard on pattern
myElem :: Eq a => a -> [a] -> Bool
myElem x [] = False
myElem x (y:ys) | x == y = True
myElem x (y:ys) = myElem x ys
I If guard evaluates to False, matching resumes with next case.
30 / 37
Programmer-defined data types
I Most non-trivial Haskell programs contain problem-specific type
definitions.
I Simplest kind: type aliases (abbreviations)
type Name = (String, String) — family & given name
I Types may be enumerations:
data Color = Red | Green | Blue
deriving (Show, Eq)
The deriving clause puts Color in respective type classes.
I Note: both type name and constructor names must start with
uppercase letter.
I Actually, Bool is just a predefined enumeration
data Bool = False | True
deriving (Show, Eq, …)
31 / 37
Value-carrying constructors
I Can associate extra data with some or all constructors:
data Figure = Point
| Disc Double — radius
| Rectangle Double Double — width, height
myFigure = Rectangle 3.0 4.0
I Define functions on datatype by pattern matching:
area :: Figure -> Double
area Point = 0.0
area (Disc r) = pi * r ^ 2
area (Rectangle w h) = w * h
(Note parentheses around non-atomic patterns)
32 / 37
Record notation
I Sometimes not obvious what constructor arguments represent.
I Simple solution: comments
I Alternative: named fields
data Figure = Point
| Disc {radius :: Double}
| Rectangle {width, height :: Double}
I Can use either positional or named style when constructing:
myFigure = Rectangle 3.0 4.0
myFigure = Rectangle {height = 4.0, width = 3.0}
I Can use field names to project out components
let a = width fig * height fig in …
I Note: runtime error if fig is not a Rectangle
I So normally use projections only for datatypes with exactly one
constructor
33 / 37
More datatypes
I Datatype definitions may be recursive:
data Figure = …
| Stack Figure Figure
I Then functions on them are normally also recursive:
…
area (Stack f1 f2) = area f1 + area f2
I Datatypes may be polymorphic:
data Tree a = Leaf a
| Node (Tree a) (Tree a)
myTree :: Tree Int
myTree = Node (Leaf 2) (Node (Leaf 3) (Leaf 4))
I Mutual recursion, possibly mixing type and data definitions:
data RoseTree a = RoseTree a (Forest a) — data, children
type Forest a = [RoseTree a] — zero or more trees
34 / 37
A few more built-in datatypes
I Have already seen lists:
data [a] = [] | a : [a] deriving …
Note: infix constructors start with colon
I … which is why infix operators must not.
I Always possible to tell visually whether a name occurring in
pattern is a constructor or a variable.
I Option (or “nullable”) types
data Maybe a = Nothing | Just a
Useful especially for function return types:
lookup :: Eq a => a -> [(a, b)] -> Maybe b
I Disjoint-union types:
data Either a b = Left a | Right b
So Maybe a is almost the same as Either () a
35 / 37
Types vs. sets (cf. Quiz 1 question 8)
I Every Haskell type a denotes a mathematical set S(a):
S(Bool) = {False,True}
S(Integer) = Z
S((a,b)) = S(a)× S(b) = {(x, y) | x ∈ S(a), y ∈ S(b)}
S(Either a b) = S(a) ] S(b) = {(1, x) | x ∈ S(a)} ∪ {(2, y) ∈ S(b)}
S(a -> b) = S(b)S(a) =
{f ⊆ S(a)× S(b) | ∀x ∈ S(a). ∃!y ∈ S(b). (a, b) ∈ f}
I Write |X | for cardinality (# of elements) of finite set X . Then
|A × B | = |A | · |B |, |A ] B | = |A |+ |B |, |BA | = |B ||A |.
I Particularly useful to keep in mind for (possibly unfamiliar)
Either type constructor.
I In Haskell, this correspondence is slightly complicated by
addition of undefined elements for most types.
I E.g., actually S(Bool) = {False,True,⊥}
I Due to lazy evaluation (next time)
36 / 37
Tasks for this week
I Install Haskell on your computer
I See Absalon page for details
I Talk to a fellow student about forming a group (two is max)
I Match-making event today, 12:00-14:00 in (UP1) 1-0-04
I Organized by your CS MSc student ambassadors
I Work on Exercise Set 0
I Start at lab session 11:00–12:00 today
I Attend lecture & labs on Thursday
I Pre-lecture quiz should be up later today, or tomorrow morning
I Use discussion forum on Absalon for questions outside of
lecture and lab hours
I Please open new discussion thread for each topic
I Solve Assignment 0, due 20:00 on Wednesday, next week
I Submission instructions being fine-tuned
37 / 37