Introducing Haskell
CSI3120 A
1
Programming Language Concepts
• Slides copyright
2017-2021
• Author David
Walker, updated by Amy
Felty
• permission granted
to reuse these slides for
non-commercial
educational purposes
Acknowled
gement
• An introduction to programming language concepts
• An introduction to OCaml
• Types and functional programming
• Inductive data types
• Polymorphic higher-order programming
• Data abstraction and modularity
• Mutable data and imperative programming
• Object-oriented programming
• Syntax and semantics
• Scope, procedures, and storage management
• Control in sequential languages
• Concurrent and distributed programming
• Combinators, pipelines, and scripting
• Semantics revisited
Overview of the course
Announc
ement
Change in lab – remote
Lab form – due Sept 25
(to be filled by student
who cannot aatend in
person class)
Midterm poll
In 1936, Alonzo Church invented
the lambda calculus. He called
it a logic, but it was a language
of pure functions — the world’s
first programming language.
He said:
“There may, indeed, be other
applications of the system than
its use as a logic.”
Alonzo Church, 1903-1995
Princeton Professor, 1929-1967
5
In 1936, Alonzo Church invented
the lambda calculus. He called
it a logic, but it was a language
of pure functions — the world’s
first programming language.
He said:
“There may, indeed, be other
applications of the system than
its use as a logic.”
Greatest technological
understatement of the 20th
century?
Alonzo Church, 1903-1995
Princeton Professor, 1929-1967
6
Vastly Abbreviated FP Geneology
LCF Theorem
Prover (70s)
Edinburgh ML
Miranda (80s)
Haskell
(90s – now)
Standard ML
(90s – now) OCaml
(90s – now)
Caml
(80s-now)
F#
(now)
LISP
(50s-now)
Scheme
(70s-now)
lazy
typed, polymorphic
untyped
Coq
(80s – now)
dependently
typed
call-by-value
Racket
(00s-now)
Scala
(00s – now)
7
Vastly Abbreviated FP Geneology
LCF Theorem
Prover (70s)
Edinburgh ML
Miranda (80s)
Haskell
(90s – now)
Standard ML
(90s – now) OCaml
(90s – now)
Caml
(80s-now)
F#
(now)
LISP
(50s-now)
Scheme
(70s-now)
lazy
typed, polymorphic
untyped
Coq
(80s – now)
dependently
typed
call-by-value
Racket
(00s-now)
Scala
(00s – now)
8
Functional Languages: Who’s using them?
F# in Visual Studio
map-reduce in their data centers
Erlang for
concurrency,
Haskell for
managing PHP
Haskell to
synthesize hardware
Scala for
correctness, maintainability, flexibility
www.artima.com/scalazine/articles/twitter_on_scala.html
www.janestreet.com/technology/
https://devblogs.microsoft.com/dotnet/tag/visual-f/
ai.google/research/pubs/pub62
www.haskell.org/haskellwiki/Haskell_in_industry
blogs.wsj.com/cio/2014/02/24/facebook-whatsapp-messaging-service-written-in-exotic-erlang/
Haskell
for specifying
equity derivatives
mathematicians
Coq (re)proof of
4-color theorem
9
http://www.artima.com/scalazine/articles/twitter_on_scala.html
http://www.janestreet.com/technology/
https://devblogs.microsoft.com/dotnet/tag/visual-f/
https://ai.google/research/pubs/pub62
http://www.haskell.org/haskellwiki/Haskell_in_industry
https://blogs.wsj.com/cio/2014/02/24/facebook-whatsapp-messaging-service-written-in-exotic-erlang/
Functional Languages: Join the crowd
• Elements of functional programming are showing up all over
– F# in Microsoft Visual Studio
– Scala combines ML (a functional language) with Objects
• runs on the JVM
– C# includes “delegates”
• delegates == functions
– Python includes “lambdas”
• lambdas == more functions
– Javascript
• find tutorials online about using functional programming
techniques to write more elegant code
– C++ libraries for map-reduce
• enabled functional parallelism at Google
– Java has generics and GC
– … 10
A Functional Review
11
Thinking Functionally
In Java or C, you get (most) work done by changing something
In ML, you get (most) work done by producing something new
temp = pair.x;
pair.x = pair.y;
pair.y = temp; commands modify or change an
existing data structure (like pair)
let
(x,y) = pair
in
(y,x)
you analyze existing data (like pair)
and you produce new data (y,x)
12
Thinking Functionally
imperative code:
• outputs are irrelevant!
• output is not function of input
• data properties change
• unrepeatable
• parallelism hidden
• harder to test
• harder to compose
pure, functional code:
• outputs are everything!
• output is function of input
• data properties are stable
• repeatable
• parallelism apparent
• easier to test
• easier to compose
temp = pair.x;
pair.x = pair.y;
pair.y = temp;
let (x,y) = pair in
(y,x)
13
OCaml Feature Overview
Small core based on the lambda calculus.
– Control is based on (recursive) functions.
– Instead of for-loops, while-loops, do-loops, iterators, etc.
• can be defined as library functions
– Makes it easy to define semantics
Supports first-class, lexically-scoped, higher-order procedures
– a.k.a. first-class functions or closures or lambdas
– first-class: functions are data values like any other data value
• like numbers, they can be stored, defined anonymously, …
– lexically-scoped: meaning of variables determined statically
– higher-order: functions as arguments and results
• programs passed to programs; generated from programs
These features also found in Racket, Haskell, SML, F#, Clojure, ….
14
OCaml Feature Overview
Statically typed: debugging and testing aid
– compiler catches many silly errors before you can run the code
• A type is worth a thousand tests (start at 6:20):
– https://www.youtube.com/watch?v=q1Yi-WM7XqQ
– Java is also strongly, statically typed
– Python, Javascript, etc. are all strongly, dynamically typed – type
errors are discovered while the code is running
Strongly typed: compiler enforces type abstraction
– cannot cast an integer to a record, function, string, etc.
– C/C++ are weakly-typed (statically typed) languages. The compiler
will happily let you do something smart (more often stupid).
Type inference: compiler fills in types for you
15
Running OCaml
• OCaml comes with compilers:
– “ocamlc” – fast bytecode compiler
– “ocamlopt” – optimizing, native code compiler
– “ocamlbuild” – a nice wrapper that computes dependencies (not used
in this course)
• And an interactive, top-level shell (interpreter):
– useful for trying something out, and for debugging small programs
– “ocaml” at the prompt
– You will likely use this most of the time.
• And many other tools
– e.g., debugger, dependency generator, profiler, etc.
• We will use it via VCL. You may want to try to install it yourself.
– See OCaml.org
16
Editing OCaml Programs
• Many options:
– Emacs
• what I’ll be using in labs, and what is available via VCL
• good support for OCaml with the Tuareg Emacs Mode
• powerful text editor, can run OCaml inside it
• (extensions written in elisp – a functional language!)
– OCaml IDE
• integrated development environment written in OCaml
• I haven’t used it, so can’t comment.
– Eclipse
• I haven’t tried it but others recommend it. See the information on
Brightspace added by TAs (in “Course Software” module, “Tips and
Advanced Alternatives” submodule).
– Sublime, atom
• I haven’t tried it, but many students have used it.
17
AN INTRODUCTORY EXAMPLE
(OR TWO)
18
OCaml Compiler and Interpreter
• Demo:
– emacs
– .ml files
– writing simple programs: hello.ml, sumTo.ml
– ocaml interpreter
– ocamlc compiler
19
A First OCaml Program
hello.ml:
print_string “Hello CSI 3120!!\n”;;
20
print_string “Hello CSI 3120!!\n”
A First OCaml Program
hello.ml:
a function its string argument
enclosed in “…”
a program
can be nothing
more than
just a single
expression
(but that is
uncommon)
no parens. normally call a function f like this:
f arg
(parens are used for grouping, precedence
only when necessary) 21
A First OCaml Program
$ ocaml
OCaml Version 4.05.0
# 3 + 1;;
– : int = 4
#
hello.ml:
interpreting and playing with hello.ml:
print_string “Hello CSI 3120!!\n”
the OCaml
interpreter
22
Current
versions of
OCaml on
website are
4.05 to 4.11
(depends
on OS)
A First OCaml Program
$ ocaml
OCaml Version 4.05.0
# 3 + 1;;
– : int = 4
# #use “hello.ml”;;
hello CSI 3120!!
– : unit = ()
#
hello.ml:
interpreting and playing with hello.ml:
print_string “Hello CSI 3120!!\n”
the OCaml
interpreter
23
Current
versions of
Ocaml on
website are
4.05 to 4.08
(depends
on OS)
A First OCaml Program
$ ocaml
OCaml Version 4.05.0
# 3 + 1;;
– : int = 4
# #use “hello.ml”;;
hello CSI 3120!!
– : unit = ()
# #quit;;
$
hello.ml:
interpreting and playing with hello.ml:
print_string “Hello CSI 3120!!\n”
the OCaml
interpreter
24
Current
versions of
Ocaml on
website are
4.05 to 4.08
(depends
on OS)
https://try.ocamlpro.com/
https://try.ocamlpro.com/
A First OCaml Program
print_string “Hello CSI 3120!!\n”
$ ocamlc hello.ml
$
hello.ml:
compiling and running hello.ml:
the OCaml
compiler
25
A First OCaml Program
print_string “Hello CSI 3120!!\n”
$ ocamlc hello.ml
$ ocaml
OCaml Version 4.05.0
#
hello.ml:
compiling and running hello.ml:
the OCaml
compiler
26
A First OCaml Program
print_string “Hello CSI 3120!!\n”
$ ocamlc hello.ml
$ ocaml
OCaml Version 4.05.0
# #load “hello.cmo”;;
Hello CSI 3120!!
#
hello.ml:
compiling and running hello.ml:
the OCaml
compiler
27
(* sum the numbers from 0 to n
*)
let rec sumTo (n:int) : int =
if n <= 0 then 0 else n + sumTo (n-1) let _ = print_int (sumTo 8); print_newline() A Second OCaml Program a comment (* ... *)sumTo.ml: 28 (* sum the numbers from 0 to n *) let rec sumTo (n:int) : int = if n <= 0 then 0 else n + sumTo (n-1) let _ = print_int (sumTo 8); print_newline() A Second OCaml Program the name of the function being defined the keyword “let” begins a definition; keyword “rec” indicates recursion sumTo.ml: 29 (* sum the numbers from 0 to n *) let rec sumTo (n:int) : int = if n <= 0 then 0 else n + sumTo (n-1) let _ = print_int (sumTo 8); print_newline() A Second OCaml Program result type int argument named n with type int sumTo.ml: 30 (* sum the numbers from 0 to n *) let rec sumTo (n:int) : int = if n <= 0 then 0 else n + sumTo (n-1) let _ = print_int (sumTo 8); print_newline() A Second OCaml Program a conditional statement in OCaml sumTo.ml: 31 (* sum the numbers from 0 to n *) let rec sumTo (n:int) : int = if n <= 0 then 0 else n + sumTo (n-1) let _ = print_int (sumTo 8); print_newline() A Second OCaml Program Each branch of the conditional statement constructs a result construct the result 0 construct a result using a recursive call to sumTo sumTo.ml: 32 (* sum the numbers from 0 to n *) let rec sumTo (n:int) : int = if n <= 0 then 0 else n + sumTo (n-1) let _ = print_int (sumTo 8); print_newline() A Second OCaml Program print the result of calling sumTo on 8 print a new line sumTo.ml: 33 (* sum the numbers from 0 to n precondition: n must be a natural number *) let rec sumTo (n:int) : int = match n with 0 -> 0
| n -> n + sumTo (n-1)
let _ =
print_int (sumTo 8);
print_newline()
A Second OCaml Program (New Version)
Additional
commentnewSumTo.ml:
34
(* sum the numbers from 0 to n
precondition: n must be a natural number
*)
let rec sumTo (n:int) : int =
match n with
0 -> 0
| n -> n + sumTo (n-1)
let _ =
print_int (sumTo 8);
print_newline()
A Second OCaml Program (New Version)
deconstruct the value n
using pattern matching
data to be
deconstructed
appears
between
key words
“match” and
“with”
newSumTo.ml:
35
(* sum the numbers from 0 to n
precondition: n must be a natural number
*)
let rec sumTo (n:int) : int =
match n with
0 -> 0
| n -> n + sumTo (n-1)
let _ =
print_int (sumTo 8);
print_newline()
_
A Second OCaml Program
deconstructed data matches one of 2 cases:
(i) the data matches the pattern 0, or (ii) the data matches the variable pattern n
vertical bar “|” separates the alternative patterns
newSumTo.ml:
36
(* sum the numbers from 0 to n
precondition: n must be a natural number
*)
let rec sumTo (n:int) : int =
match n with
0 -> 0
| n -> n + sumTo (n-1)
let _ =
print_int (sumTo 8);
print_newline()
A Second OCaml Program
Each branch of the match statement constructs a result
as before,
construct
the result 0
as before,
construct
a result
using a
recursive
call to sumTo
newSumTo.ml:
37
OCAML BASICS:
EXPRESSIONS, VALUES, SIMPLE TYPES
38
Terminology: Expressions, Values, Types
• Expressions are computations
– 2 + 3 is a computation
• Values are the results of computations
– 5 is a value
• Types describe collections of values and the computations
that generate those values
– int is a type
– values of type int include
• 0, 1, 2, 3, …, max_int
• -1, -2, …, min_int
39
Some simple types, values, expressions
Type: Values: Expressions:
int -2, 0, 42 42 * (13 + 1)
float 3.14, -1., 2e12 (3.14 +. 12.0) *. 10e6
char ’a’, ’b’, ’&’ int_of_char ’a’
string “moo”, “cow” “moo” ^ “cow”
bool true, false if true then 3 else 4
unit () print_int 3
For more primitive types and functions over them,
see the OCaml Reference Manual here:
https://ocaml.org/releases/4.11/htmlman/libref/Stdlib.html
40
Not every expression has a value
Expression:
42 * (13 + 1) evaluates to 588
(3.14 +. 12.0) *. 10e6 ↦ 151400000.
int_of_char ’a’ ↦ 97
“moo” ^ “cow” ↦ “moocow”
if true then 3 else 4 ↦ 3
print_int 3 ↦ ()
1 + “hello” does not evaluate!
41
OCAML BASICS:
CORE EXPRESSION SYNTAX
42
Core Expression Syntax
The simplest OCaml expressions e are:
• values numbers, strings, bools, …
• id variables (x, foo, …)
• e1 op e2 operators (x+3, …)
• id e1 e2 … en function call (foo 3 42)
• let id = e1 in e2 local variable decl.
• if e1 then e2 else e3 a conditional
• (e) a parenthesized expression
• (e : t) an expression with its type
43
A note on parentheses
In most languages, arguments are parenthesized & separated by commas:
f(x,y,z) sum(3,4,5)
In OCaml, we don’t write the parentheses or the commas:
f x y z sum 3 4 5
But we do have to worry about grouping. For example,
f x y z
f x (y z)
The first one passes three arguments to f (x, y, and z)
The second passes two arguments to f (x, and the result of applying the
function y to z.)
44