[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

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