INTRODUCTION TO OCAML
slides copyright 2017, 2018, 2019, 2020 Author David Walker, updated by Amy Felty permission granted to reuse these slides for non-commercial educational purposes
Alonzo Church, 1903-1995 Princeton Professor, 1929-1967
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.”
2
Alonzo Church, 1903-1995 Princeton Professor, 1929-1967
In 1936, Alonzo Church invented the lambda calculus. He called
Greatest technological
it a logic, but it was a language
understatement of the 20th
of pure functions — the world’s
century?
first programming language. He said:
“There may, indeed, be other applications of the system than its use as a logic.”
3
Vastly Abbreviated FP Geneology LCF Theorem
Prover (70s) Edinburgh ML
LISP (50s-now)
Scheme (70s-now)
Racket (00s-now)
untyped
Coq (80s – now)
dependently typed
4
Miranda (80s)
Haskell (90s – now)
lazy
Standard ML (90s – now)
Caml (80s-now)
OCaml (90s – now)
Scala F# (00s – now) (now)
call-by-value typed, polymorphic
Vastly Abbreviated FP Geneology LCF Theorem
Prover (70s) Edinburgh ML
LISP (50s-now)
Scheme (70s-now)
Racket (00s-now)
untyped
Coq (80s – now)
dependently typed
5
Caml (80s-now)
Miranda (80s)
Haskell (90s – now)
lazy
Standard ML (90s – now)
OCaml (90s – now)
Scala F# (00s – now) (now)
call-by-value typed, polymorphic
Functional Languages: Who’s using them?
map-reduce in their data centers
Scala for
correctness, maintainability, flexibility
F# in Visual Studio
mathematicians
Haskell to synthesize hardware
Erlang for concurrency, Haskell for managing PHP
Coq (re)proof of 4-color theorem
Haskell
for specifying equity derivatives
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/
6
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
– …
7
A Functional Review
8
Thinking Functionally
In Java or C, you get (most) work done by changing something
commands modify or change an existing data structure (like pair)
In ML, you get (most) work done by producing something new
temp = pair.x; pair.x = pair.y; pair.y = temp;
let
(x,y) = pair
in (y,x)
you analyze existing data (like pair) and you produce new data (y,x)
9
pure, functional code:
• outputs are everything!
• output is function of input
• data properties are stable
• repeatable
• parallelism apparent
• easier to test
• easier to compose
• outputs are irrelevant!
• output is not function of input • data properties change
• unrepeatable
• parallelism hidden
• harder to test
• harder to compose
Thinking Functionally imperative code:
temp = pair.x; pair.x = pair.y; pair.y = temp;
let (x,y) = pair in (y,x)
10
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, ….
11
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
12
Running OCaml
• OCaml comes with compilers:
– “ocamlc”–fastbytecodecompiler
– “ocamlopt”–optimizing,nativecodecompiler
– “ocamlbuild”–anicewrapperthatcomputesdependencies(notused in this course)
• And an interactive, top-level shell (interpreter):
– usefulfortryingsomethingout,andfordebuggingsmallprograms – “ocaml”attheprompt
– Youwilllikelyusethismostofthetime.
• And many other tools
– e.g.,debugger,dependencygenerator,profiler,etc.
• We will use it via VCL. You may want to try to install it yourself. – SeeOCaml.org
13
Editing OCaml Programs • Many options:
– Emacs
• what I’ll be using in class, 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.
14
AN INTRODUCTORY EXAMPLE (OR TWO)
15
OCaml Compiler and Interpreter
• Demo:
– emacs
– .ml files
– writing simple programs: hello.ml, sumTo.ml
– ocaml interpreter – ocamlc compiler
16
A First OCaml Program
hello.ml:
print_string “Hello CSI 3120!!\n”;;
17
A First OCaml Program
hello.ml:
a function
no parens. normally call a function f like this:
f arg
(parens are used for grouping, precedence only when necessary)
a program
can be nothing more than
just a single expression (but that is uncommon)
18
print_string “Hello CSI 3120!!\n”
its string argument enclosed in “…”
A First OCaml Program
hello.ml:
print_string “Hello CSI 3120!!\n”
interpreting and playing with hello.ml:
Current versions of OCaml on website are 4.05 to 4.11 (depends on OS)
$ ocaml
OCaml Version 4.05.0
# 3 + 1;;
– : int = 4 #
the OCaml interpreter
19
A First OCaml Program
hello.ml:
print_string “Hello CSI 3120!!\n”
interpreting and playing with hello.ml:
Current versions of Ocaml on website are 4.05 to 4.08 (depends on OS)
$ ocaml
OCaml Version 4.05.0
# 3 + 1;;
– : int = 4
# #use “hello.ml”;; hello CSI 3120!!
– : unit = ()
#
the OCaml interpreter
20
A First OCaml Program
hello.ml:
print_string “Hello CSI 3120!!\n”
interpreting and playing with hello.ml:
Current versions of Ocaml on website are 4.05 to 4.08 (depends on OS)
$ ocaml
OCaml Version 4.05.0
# 3 + 1;;
– : int = 4
# #use “hello.ml”;; hello CSI 3120!!
– : unit = ()
# #quit;;
$
the OCaml interpreter
21
A First OCaml Program
hello.ml:
print_string “Hello CSI 3120!!\n”
compiling and running hello.ml:
$ ocamlc hello.ml
$
the OCaml compiler
22
A First OCaml Program
hello.ml:
print_string “Hello CSI 3120!!\n”
compiling and running hello.ml:
$ ocamlc hello.ml
$ ocaml
#
OCaml Version 4.05.0
the OCaml compiler
23
A First OCaml Program
hello.ml:
print_string “Hello CSI 3120!!\n”
compiling and running hello.ml:
$ ocamlc hello.ml
$ ocaml
OCaml Version 4.05.0
# #load “hello.cmo”;;
Hello CSI 3120!!
#
the OCaml compiler
24
A Second OCaml Program
sumTo.ml:
a comment (* … *)
(* 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()
25
A Second OCaml Program the name of the function being defined
sumTo.ml:
(* 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()
the keyword “let” begins a definition; keyword “rec” indicates recursion
26
A Second OCaml Program
sumTo.ml:
(* 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()
result type int
argument named n with type int
27
A Second OCaml Program
sumTo.ml:
(* 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 conditional statement
in OCaml
28
A Second OCaml Program
Each branch of the conditional statement constructs a result
sumTo.ml:
(* 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()
construct the result 0
construct
a result using a recursive
call to sumTo
29
A Second OCaml Program
sumTo.ml:
(* 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()
print the result of calling sumTo on 8
print a new line
30
A Second OCaml Program (New Version) Additional
newSumTo.ml:
comment
(* 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()
31
A Second OCaml Program (New Version)
newSumTo.ml:
deconstruct the value n using pattern matching
(* 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()
data to be deconstructed appears between
key words “match” and “with”
32
A Second OCaml Program vertical bar “|” separates the alternative patterns
newSumTo.ml:
(* 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()
_
deconstructed data matches one of 2 cases:
(i) the data matches the pattern 0, or (ii) the data matches the variable pattern n
33
A Second OCaml Program
Each branch of the match statement constructs a result
newSumTo.ml:
(* 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()
as before, construct the result 0
as before, construct
a result using a recursive
call to sumTo
34
OCAML BASICS:
EXPRESSIONS, VALUES, SIMPLE TYPES
35
Terminology: Expressions, Values, Types
• Expressions are computations
– 2 + 3 is a computation
• Values are the results of computations
– 5isavalue
• 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
36
Some simple types, values, expressions
Type: Values:
int -2, 0, 42
float 3.14, -1., 2e12 char ’a’, ’b’, ’&’ string “moo”, “cow” bool true, false unit ()
Expressions:
42 * (13 + 1)
(3.14 +. 12.0) *. 10e6 int_of_char ’a’
“moo” ^ “cow”
if true then 3 else 4 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
37
Expression:
Not every expression has a value
42 * (13 + 1) evaluates to 588
(3.14 +. 12.0) *. 10e6 int_of_char ’a’
“moo” ^ “cow”
if true then 3 else 4 print_int 3
↦ 151400000. ↦ 97
↦ “moocow”
↦ 3
↦ () 1 + “hello” does not evaluate!
38
OCAML BASICS:
CORE EXPRESSION SYNTAX
39
Core Expression Syntax The simplest OCaml expressions e are:
• values
• id
• e1ope2
• ide1 e2 …en
• letid=e1 ine2
• if e1 then e2 else e3
• (e)
• (e:t)
numbers, strings, bools, … variables (x, foo, …) operators (x+3, …) function call (foo 3 42) local variable decl.
a conditional
a parenthesized expression an expression with its type
40
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, fxyz
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.)
41