# 程序代写代做代考 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

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

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 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