CS计算机代考程序代写 Haskell compiler python Java concurrency c/c++ Elixir chain c++ interpreter scheme matlab C/CPS 506

C/CPS 506
Comparative Programming Languages Prof. Alex Ufkes
Topic 6: Type systems, pure functional with Haskell

Notice!
Obligatory copyright notice in the age of digital delivery and online classrooms:
The copyright to this original work is held by Alex Ufkes. Students registered in course CCPS 506 can use this material for the purposes of this course but no other use is permitted, and there can be no sale or transfer or use of the work for any other purpose without explicit permission of Alex Ufkes.
© Alex Ufkes, 2020, 2021 2

Course Administration
© Alex Ufkes, 2020, 2021
3
Elixir assignment due March 19

Today
© Alex Ufkes, 2020, 2021
4
Type systems:
• Static VS dynamic • StrongVSweak Intro to Haskell
• Purefunctional
• TypinginHaskell

Type System
• A set of rules that assigns a property called type to constructs of a program.
• These constructs include variables, functions, expressions, etc.
The whole point is to reduce bugs.
© Alex Ufkes, 2020, 2021
6
• •
For example, if a pattern of 32 bits has been encoded using 2s complement, we don’t want to read it using IEEE 754 And we can do this in many languages!

• The 2s comp bit pattern was read as an IEEE 754 double.
• (The integer constant was deliberately
picked to produce a bit pattern that
would yield 1.000000 as double)
Declare large 64-bit integer
© Alex Ufkes, 2020, 2021 7
Print as int, print as double

© Alex Ufkes, 2020, 2021
8
• •
• •
Type Checking
Clearly, type checking isn’t performed in the context of a printf statement in C++
Think of type checking as trying to fit puzzle pieces together. Does the output type of a function match the variable we’re trying to store it in?
Do the input arguments to a function match the types indicated in the parameter list?
If no, will we allow implicit conversion?

Static VS Dynamic
When are types checked?
Statically typed languages perform type checking at compile time
• Checked while converting source code to machine (or byte) code Dynamically typed languages perform type checking at run-time
• Checked on the fly while instructions are being executed. Statically Typed languages: C/C++, Java, Haskell, Rust
Dynamically Typed languages: Python, Smalltalk, Elixir
© Alex Ufkes, 2020, 2021 9

Static Type Checking
© Alex Ufkes, 2020, 2021
10

• In dynamically typed languages, every operation knows the types for which it is valid.
• Providing invalid arguments or operands will yield a run-time error which may or may not be recoverable
• Such things can be anticipated and mitigated in various ways, such as verifying type explicitly
© Alex Ufkes, 2020, 2021 11

Dynamic Type Checking
factorial: n | fac |
fac := 1.
n isInteger
ifTrue: [1 to: n do:
[:a | fac := fac*a.].
^fac
]
ifFalse: [
^’Bad input’
].
• In Java, the parameter would be defined as int
• Compile error if arg isn’t int, or can’t be implicitly cast as an int.
• Of course, polymorphism in Java complicates this.
• Still statically typed.
© Alex Ufkes, 2020, 2021
12

© Alex Ufkes, 2020, 2021
13
• • •
• • •
Dynamic Type Checking…?
#(1 2 3 4) + 18.2
Does Smalltalk have type errors in the strict sense? Different objects understand different messages.
A “type error” occurs when an object doesn’t have a method to handle a particular message.
“Type” errors in Smalltalk are as a result of not finding a method (DNU, Did Not Understand).
Above, the error occurs because the Array class doesn’t have an instance method for symbolic operator #+ Smalltalk enthusiasts debate this.

Dynamic Type Checking
defmodule UserMath do
def fib(n) when not is_integer(n) or n < 0 do :error end def fib(0), do: 0 def fib(1), do: 1 def fib(n), do: fib(n-2) + fib(n-1) def fac(n) when not is_integer(n) or n < 0 do :error end def fac(0), do: 1 def fac(n), do: n*fac(n-1) end © Alex Ufkes, 2020, 2021 14 Static: • Reliably find errors at compile time. • Code will execute faster if types are assumed to be correct at run time. • Type-specific optimization can be performed at compile time. • I.e., integer arithmetic is faster than floating point Dynamic: • Compilers run faster • Interpreters can dynamically load new code o Smalltalk, MATLAB, iex • Easier code reuse Static VS Dynamic Advantages? Disadvantages? © Alex Ufkes, 2020, 2021 15 Static VS Dynamic Advantages? Disadvantages? • There is much disagreement among programmers about just how much of a problem type errors are in the grand scheme of things. • Does the added cost of developing in a statically typed language make sense if type-related bugs are but a tiny fraction? • Of the type-related bugs that occur, what proportion of those would have been solved by a type checker anyway? • They aren’t perfect after all. © Alex Ufkes, 2020, 2021 16 Strong VS Weak Typing © Alex Ufkes, 2020, 2021 17 Strong VS Weak (or Loose) Refers to how strict statically typed languages are at compile time There is actually no universally accepted definition of what constitutes strong or weak typing Of strongly typed languages: © Alex Ufkes, 2020, 2021 18 1974: “Whenever an object is passed from a calling function to a called function, its type must be compatible with the type declared in the called function." Compatible is open to interpretation. Is float compatible with double? Integer with short integer? Strong VS Weak (or Loose) Refers to how strict statically typed languages are at compile time © Alex Ufkes, 2020, 2021 19 1974: 1977: “Whenever an object is passed from a calling function to a called function, its type must be compatible with the type declared in the called function." “In a strongly typed language each data area will have a distinct type and each process will state its communication requirements in terms of these types." Parameter lists, return types, etc. Strong VS Weak (or Loose) To what degree does a statically typed language allow implicit type conversion? • C is weakly typed. • Happy to perform all manner of implicit conversion without warning or error. © Alex Ufkes, 2020, 2021 20 Strong VS Weak (or Loose) In C, pointer arithmetic can be used to completely bypass the type system: • We’re using pointer arithmetic to read the first 2 bytes of an int as a short. • This can be done with any two types. • We can read the rightmost 4 bytes of a double as an int, etc. • We can treat memory any way we want © Alex Ufkes, 2020, 2021 21 Strong VS Weak (or Loose) C++ will give warnings where C did not, but still compiles and runs in this case: © Alex Ufkes, 2020, 2021 22 Strong VS Weak (or Loose) Java will throw compile errors when a loss of precision occurs: • No implicit truncation from floating point to integer • Floating point constants are double precision • Need to indicate single precision explicitly © Alex Ufkes, 2020, 2021 23 Java will throw compile errors when a loss of precision occurs: Careful! Loss of precision does not only occur when going from floating point type to integer type! int is 32 bits two’s complement. float is a 23-bit mantissa and an 8 bit exponent. 32-bit: 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 Mantissa (23 bits) © Alex Ufkes, 2020, 2021 24 sign bit Exponent (8 bits) Imprecision of Floating Point • Integers are represented precisely. The integer 42 is exactly 42. • The single-precision (32 bits) floating point value 0.1 is actually 0.100000001490116119384765625 • Double-precision (64 bit) floating point values are more accurate, but still not perfect. But why? • Floating point values exist on an infinite continuum. • Between any two floating point values are an infinite number of additional floating point values. • Integers are discrete. Between any two integers are a finite number of integers. © Alex Ufkes, 2020, 2021 25 Imprecision of Floating Point • A double-precision float is represented using 64 bits. • A finite number of bits cannot represent an infinite number of floating point values. 0100101110000010100010100001010100011010101011000110001110000011 • There are 2^64 ways to arrange 64 bits. A large number to be sure, but certainly not infinite. © Alex Ufkes, 2020, 2021 26 Infinite Integers? But there are an infinite number of integers! • 100% correct. We can’t represent every possible integer either. • Rather, there is a range. A standard 32-bit integer has a range of −2,147,483,648 to 2,147,483,647. • Every integer within this range is represented precisely. • Anything outside this range can’t be represented using 32 bits • If we try, we overflow. © Alex Ufkes, 2020, 2021 27 © Alex Ufkes, 2020, 2021 28 © Alex Ufkes, 2020, 2021 29 Functional Programming © Alex Ufkes, 2020, 2021 30 © Alex Ufkes, 2020, 2021 31 Functional Programming © Alex Ufkes, 2020, 2021 32 Functional Programming Higher-order functions: • Can return functions or accept them as arguments. First class functions: • Can be passed as arguments, returned as values. • Think of them as values, just like integers or floats Pure Functions: © Alex Ufkes, 2020, 2021 33 • • Functions that have no side effects. No interaction with world outside of local scope Easier to verify correctness, thread-safe when no data dependency is present. Pure function Impure function © Alex Ufkes, 2020, 2021 34 Functional Programming Strict (eager) VS. non-strict (lazy) evaluation: • Strict: evaluate function arguments before invoking the function. • Lazy: Evaluates arguments if their value is required to invoke the function. © Alex Ufkes, 2020, 2021 Elixir largely performs strict evaluation (some exceptions, recall Stream, Range) 35 Functional Programming Strict (eager) VS. non-strict (lazy) evaluation: • Strict: evaluate function arguments before invoking the function. • Lazy: Evaluates arguments if their value is required to invoke the function. https://www.haskell.org/ A great intro to Haskell syntax © Alex Ufkes, 2020, 2021 36 Haskell: Functional Programming cranked up to 11 © Alex Ufkes, 2020, 2021 37 History © Alex Ufkes, 2020, 2021 38 • Named after logician Haskell Curry • In the late 80s, interest in lazy functional languages was growing • There was a strong consensus to define an open standard for such languages • • • History Haskell 1.0 was defined in 1990 o Continued with version 1.1, 1.2, 1.3, etc. o Culminated with Haskell 98 Haskell 2010 was published in July 2010 o Contained uncontroversial features previously enabled via compiler flags Next version being worked on – Haskell 2020 o Though progress seems to have stalled o Perhaps it should be called Haskell 202X © Alex Ufkes, 2020, 2021 39 Features Purely Functional: • Every function is pure • Even side-effect inducing operations are produced by pure code • No statements, only expressions • Cannot mutate variables (local or global) • Supports pattern matching • Side effects are handled using monads © Alex Ufkes, 2020, 2021 40 Features Statically Typed: • Every expression has a type o Determined at compile time • Types composing an expressions must match o If not, compile error Type Inference: © Alex Ufkes, 2020, 2021 41 • • Types don’t have to be written out explicitly o Though you can if you want They will be inferred at compile time Features Lazy Evaluation: • Functions don’t evaluate their arguments • Control constructs written as functions • Easy to fuse chains of functions together • Computation never takes place unless a result is used. Concurrency: © Alex Ufkes, 2020, 2021 42 • • GHC (Haskell compiler) includes high performance parallel garbage collector Light-weight concurrency library Haskell in Industry? https://wiki.haskell.org/Haskell_in_industry © Alex Ufkes, 2020, 2021 43 © Alex Ufkes, 2020, 2021 44 Notable companies that use or have used Haskell: • Nvidia • AT&T • Ericsson • Facebook • Google • Intel • Microsoft Typically Haskell is used on specialized internal projects or research. Not necessarily company-wide. © Alex Ufkes, 2020, 2021 45 Installing Haskell: https://www.haskell.org/ Neat! © Alex Ufkes, 2020, 2021 46 © Alex Ufkes, 2020, 2021 47 © Alex Ufkes, 2020, 2021 48 • Interactive shell, just like Elixir. • Haskell’s is better! © Alex Ufkes, 2020, 2021 49 Hello, World! putStrLn == System.out.println() putStr == System.out.print() • Define a main function. • When executing a Haskell program, main is the entry point • Just like C or Java Execute main function © Alex Ufkes, 2020, 2021 50 Compiling Haskell Notepad++ features Haskell syntax highlighting! © Alex Ufkes, 2020, 2021 51 Compilation is similar to gcc As with Elixir, we will play around in the interactive shell until it becomes tedious. © Alex Ufkes, 2020, 2021 52 Literals & Arithmetic Operator precedence is as expected © Alex Ufkes, 2020, 2021 53 Division yields floating point Literals & Arithmetic Like Elixir, can omit brackets on function calls ^ can be used for exponentiation © Alex Ufkes, 2020, 2021 54 Representation error, no escaping it. Tuples • Like Elixir, Haskell supports tuples. • They need not contain the same types. There are built in functions for accessing first and second elements. Great for coordinates. © Alex Ufkes, 2020, 2021 55 fst and snd only work on pair tuples! © Alex Ufkes, 2020, 2021 56 Lists Must be homogeneous: Integer literals get inferred as floating point © Alex Ufkes, 2020, 2021 57 Characters do not Lists Elements can be added to the beginning of a list with the cons ( : ) operator In fact, when we write [1, 2, 3] the compiler is actually doing 1:2:3:[] [1, 2, 3] notation is syntactic sugar. © Alex Ufkes, 2020, 2021 58 Build a list using cons operator and an empty list Lists & Tuples Tuples can be heterogeneous, lists must be homogeneous. However! We can have lists of tuples, where each tuple is heterogeneous. © Alex Ufkes, 2020, 2021 59 Lists & Tuples Tuples can be heterogeneous, lists must be homogeneous. However #2! • In a list of tuples, each tuple must have the same format: © Alex Ufkes, 2020, 2021 60 Strings Strings are simply lists of chars: We can cons chars into an empty list to form a string We can concatenate strings using the ++ operator © Alex Ufkes, 2020, 2021 61 Strings Concatenate multiple types? Java lets us... © Alex Ufkes, 2020, 2021 62 Strings show() and read() functions Convert non-string argument to string Read numeric value from a string (like sscanf in C) © Alex Ufkes, 2020, 2021 63 Error when no numeric value is present Operations on Lists • In functional programming, computation is done in large part by operating on lists. • We saw the hd, tl, |, and Enum in Elixir. • Haskell has a similar set of operations. Three primary list-processing functions: map, filter, foldr (and foldl) © Alex Ufkes, 2020, 2021 64 Head & Tail Same as Elixir: • Head returns the first element • Tail returns the rest, as a list • Note boundary cases: o Single element lists o Empty lists © Alex Ufkes, 2020, 2021 65 map Similar to Elixir’s Enum.map • First class function, does what name suggests. • Alphabeticalcharactersareupped,everything else is left the same. Recall: map operates on lists, but a string is just a list of characters © Alex Ufkes, 2020, 2021 66 map Similar to Elixir’s Enum.map © Alex Ufkes, 2020, 2021 67 Map takes two arguments: A function, and a list of values to which the function is to be applied. filter “Remove” items from a list based on some criteria: © Alex Ufkes, 2020, 2021 68 Function List foldl, foldr Replaces the cons operator with some other function. This takes some explaining. Recall that the list: [1, 2, 3, 4, 5] Is actually seen as: 1:2:3:4:5:[] By the compiler. © Alex Ufkes, 2020, 2021 69 foldl, foldr Replaces the cons operator with some other function. This takes some explaining. Recall that the list: [1, 2, 3, 4, 5] Is actually seen as: 1:2:3:4:5:[] By the compiler. • foldr in effect replaces the cons operator with another function of our choosing. © Alex Ufkes, 2020, 2021 70 • • This is similar to Enum.reduce in Elixir. The empty list is replaced with some initial value. foldl, foldr Replaces the cons operator with some other function. This takes some explaining. • foldr in effect replaces the cons operator with another function of our choosing. • • This is similar to Enum.reduce in Elixir. The empty list is replaced with some initial value. foldr (+) 0 [1, 2, 3, 4, 5] Three arguments: function, initial value, list © Alex Ufkes, 2020, 2021 71 foldl, foldr Replaces the cons operator with some other function. This takes some explaining. foldr (+) 0 [1, 2, 3, 4, 5] foldr (+) 0 1:2:3:4:5:[] 1 + 2 + 3 +4 + 5 + 0 15 © Alex Ufkes, 2020, 2021 72 foldl, foldr © Alex Ufkes, 2020, 2021 73 foldr to perform factorial! foldl VS foldr foldr is right associative. Meaning: foldr (+) 0 [1, 2, 3, 4, 5] 1 + 2 + 3 + 4+5+0 Is actually: (1 + (2 + (3 + (4 + (5 + 0))))) Doesn’t matter for addition, but subtraction... © Alex Ufkes, 2020, 2021 74 foldl VS foldr foldr is right associative. Meaning: foldr (-) 1 [4, 8, 5] 4–8-5-1 Is actually: (4 - (8 - (5 - 1 ))) 0 © Alex Ufkes, 2020, 2021 75 foldl VS foldr foldl is left associative. Meaning: foldl (-) 1 [4, 8, 5] 1-4–8-5 Is actually: (((1 - 4) – 8) - 5) -16 © Alex Ufkes, 2020, 2021 76 foldl VS foldr © Alex Ufkes, 2020, 2021 77 List declaration: Can be written: Specify interval: List Generation Syntactic sugar: list = [1, 2, 3, 4, 5, 6, 7, 8, 9] list = [1..9] list = [1,3..9] = [1,3,5,7,9] Interval is discerned from difference between first two elements © Alex Ufkes, 2020, 2021 78 Infinite Lists? © Alex Ufkes, 2020, 2021 79 Try it, but be ready to interrupt Infinite Lists? © Alex Ufkes, 2020, 2021 80 Why? How? Haskell is lazy! • We bind x to the expression to generate an infinite list. • We don’t have to evaluate this list to do so! • Displaying the list, however, requires evaluation. Infinite Lists? • Finding the length of the list requires counting the elements. • Be ready to interrupt. • Grab first three elements of list • Doesn’t matter if infinite, we’re only evaluating first three items © Alex Ufkes, 2020, 2021 81 Infinite Lists? We’re allowed to perform operations on a finite subset of an infinite list. • zip “zips” two lists together into tuples. • If one list is finite, the other can be infinite. © Alex Ufkes, 2020, 2021 82 Types in Haskell Statically Typed: • Haskell uses static type checking. • Every expression is assigned a type. • If a function’s arguments aren’t the expected type, a compile error occurs. Type Inference • Like Python, and unlike Java, we need not specify type. • It is inferred by the context: X = “Hello”, X is a string. • However, we can explicitly specify types. • Good practice when we know what types we want; compiler will give errors upon type mismatch. © Alex Ufkes, 2020, 2021 83 Types in Haskell :t can be used to reveal type: • 1 is instance of Num type class. • 1.0 is instance of Fractional type class. • ‘a’ is a Char • “Hello” is a [Char] • [Char] = String • t is a Bool © Alex Ufkes, 2020, 2021 84 Num p => p ?
Type Variables:
• p is a type variable whose value can be any type in typeclass Num (Integer, Float, etc.)
• Haskell is free to treat 7 as it sees fit, so long as it does so in a way that adheres to the operations defined in type class Num.
© Alex Ufkes, 2020, 2021
85

Typeclasses?
Haskell tries to keep types as generic as possible
• If we explicitly declare a variable as integer, it can’t be passed to a function requiring float.
• However, if we generically infer it to be a Num, it can be used anywhere any other member of Num is allowed.
© Alex Ufkes, 2020, 2021
86

Types in Haskell
We can explicitly indicate types:
• Use :: to assign a type
• My advice for you is to start by letting
the inference engine figure it out.
• At this point, it knows better than you.
© Alex Ufkes, 2020, 2021
87

Types in Haskell
We can explicitly indicate types:
When defining a name, can indicate type explicitly:
© Alex Ufkes, 2020, 2021
88

Type Classes
Type polymorphism and type variables:
Recall: Overloading
• In languages like C++, the == operator is
overloaded to work with many different types.
• Numeric type equality and string equality are
performed differently.
• In general, if we want to compare two values of
type α, we use an α-compare
• α is a type variable, because its value is a type.
© Alex Ufkes, 2020, 2021
89

Type Classes
Consider the equality (==) operator:
Takes two parameters, each of the same type (call it α), and returns a Boolean
This operator may not be defined for all types, just some. Thus, we can associate == with a specific type class containing those
types for which == is defined.
This type class is called Eq in Haskell.
© Alex Ufkes, 2020, 2021
90

Eq Type Class
(==) is defined for types in typeclass Eq
• (==) takes two args of type a, where a is a member of type class Eq
• It returns Bool
• If a concrete type, a, belongs to a certain type class, we say a is an instance of that type class.
• Int is an instance of Eq, for example.
© Alex Ufkes, 2020, 2021
91

Num Type Class
• This allows numeric values freedom to be an integer or floating point as the compiler sees fit.
• Num class contains all numbers, and certain operations over them such as addition.
© Alex Ufkes, 2020, 2021
93

Num Type Class
• p is a type variable
• The type of 5 isp, andpis a
member of type class Num
© Alex Ufkes, 2020, 2021
94

Show Type Class
Types that are members of the Show class have functions which convert their value to a String.
© Alex Ufkes, 2020, 2021
96

Function Types
head takes a list containing type a, and returns a value of type a
tail takes a list containing type a, and returns a list containing type a
© Alex Ufkes, 2020, 2021
97
a and b can be literally any type!

Function Types
putStrLn:
• Accepts String, returns IO action.
• -> indicates function
• String is input, IO() is output.
• More on IO actions later.
© Alex Ufkes, 2020, 2021
98
Same as [Char]

Functions in Haskell
As expected of a pure functional language, functions are central in Haskell
© Alex Ufkes, 2020, 2021
101
• •
If we’re compiling our code into an executable, we need a main.
If we’re using the GHCi shell, we don’t.

Functions in Haskell
Let’s start simple:
Define function called square that takes one argument x
square computes x*x, where x is the input argument
© Alex Ufkes, 2020, 2021
102

Functions in Haskell
Let’s start simple:
© Alex Ufkes, 2020, 2021
103
Invoke function square in the typical fashion

Functions in Haskell
• Based on what we’re doing in square and sum (multiplying and adding)…
• Haskell determined that input and output type should be instances of typeclass Num.
• (+) and (*) are both defined for all types in typeclass Num.
© Alex Ufkes, 2020, 2021
106

Haskell Modules
This is getting tedious to type interactively.
Let’s create a module!
• Similar to modules in Elixir
• We can load the module in GHCi
• Access its functions and expressions
© Alex Ufkes, 2020, 2021
107

Control Structures
if then else
• Brackets required around negative arguments
• Otherwise it thinks you’re subtracting 6 from f
© Alex Ufkes, 2020, 2021
112

Control Structures
if then else if then else
• Here we have a function named sign, that takes one argument x
• It returns:
o -1 if x is negative o 1 if x is positive
o 0 if x is 0
• If/else construct in Haskell is similar to most other languages.
• It must include a then and an else
© Alex Ufkes, 2020, 2021
113

Control Structures
if then else if then else
We can now format across multiple lines. HOWEVER: Indentation matters in Haskell!
© Alex Ufkes, 2020, 2021
114

Indenting in Haskell
Golden Rule:
Code which is part of some expression should be indented further than the beginning of that expression
https://en.wikibooks.org/wiki/Haskell/Indentation
© Alex Ufkes, 2020, 2021
117

Haskell Tutorials/References:
https://en.wikibooks.org/wiki/Yet_Another_Haskell_Tutorial http://cheatsheet.codeslower.com/CheatSheet.pdf
© Alex Ufkes, 2020, 2021 119

Related Posts