[SOLVED] assembly ocaml Erlang interpreter Java flex prolog Haskell python distributed system compiler Excel data structure algorithm Advanced Programming 2018 Introduction to (the course and) Haskell

Advanced Programming 2018 Introduction to (the course and) Haskell

Advanced Programming 2018
Introduction to (the course and) Haskell

Andrzej Filinski
[email protected]

(Administrative info adapted from
slides by Ken Friis Larsen)

Department of Computer Science
University of Copenhagen

September 4, 2018

1 / 37

Todays 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 Well 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 Youll 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: 1012 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: 1012 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

Lets 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 dont 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, dont 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
line :: 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 Haskells

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
:6:1: No instance for (Show (String -> Int))

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) ysI In case of overlaps, first successful match is chosenI ghci -W warns about uncovered casesI Runtime error if matching failsI Can also use case for pattern matchingcase 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:0012: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