**Quick Introduction to OCaml**
by ** ** with minor changes by ** **
Copyright By PowCoder代写 加微信 powcoder
1. OCaml: Basic Types, Literals & Expressions; Naming; Defining Functions
2. Structured Types
3. Recursive Types & Recursive Functions
4. Functions are Values
5. Imperative Features
6. The Module System
Like most programming languages, OCaml is text-based: OCaml source code is written out in text and is then processed by the computer to carry out the expressed computation. OCaml source code is stored in files with the `.ml` extension. OCaml code can either be compiled and executed as an application via a command shell or, under some circumstances, it can be executed by an interpreter either via a shell command or within an editor such as emacs or atom.
**Compilation**
The OCaml compiler `ocamlc` translates OCaml source code and produces a byte-code file that can be executed on OCaml’s virtual machine.
> ocamlc -o go myprogram.ml
Executing the `go` byte-code file fires up OCaml’s virtual machine to execute the code expressed in `myprogram.ml`.
For this course, compilation will involve multiple source files and libraries so the process is configured using the Dune build Manager command. Most often, you’ll compile with
> dune build bin/main.exe
> dune exec bin/main.exe
The `exec` command will automatically build if the sources haven’t been built yet so the above process can be expressed
> dune exec bin/main.exe
**Interpretation**
OCaml’s interpreter `ocaml` can be fired up from the Unix command line. It cycles through a loop: reading, evaluating, printing and then looping back. Interpretation loops of this kind are often referred to as REPLs. An interaction with OCaml’s REPL shell might look like:
– : int = 6
The hash-sign `#` is OCaml’s prompt and the trailing `;;` is the user’s signal to OCaml that they’d like the expression to be evaluated. The details are spelled out in problem set 0 for how to run the REPL in your editor, if you choose to use Atom or vscode.
—————-
## 1. Basic Types, Literals & Expressions; Naming; Defining Functions
In computing, it’s often useful to think of *types* as **sets**. For example, it’s often reasonable to think of the familiar type `int` as the set of integers `{…, -2, -1, 0, 1, 2, …}`. All programming languages provide a number of basic types that are built-in to the language. Most programming languages have ways to define new types. We’ll get to that topic later.
Virtually all programming languages have basic types `int` and `float` together with built-in operators (e.g., `+`, `-`, `*`, `/`, `mod`) that work on values of that type.
**The Type `unit`**
The `unit` type has exactly one value `()`.
– : unit = ()
That’s it. The `unit` type is very useful as we’ll see.
**The Type `int`**
– : int = 2
The numeral `2` is a *literal* expression of type `int`. OCaml’s REPL displays both the type of the expression as well as its value.
# (* This is a comment; ignored by OCaml *)
> Unfortunately, OCaml doesn’t have notation for a single-line comment. Comments must start with (* and end with *) one line or many.
– : int = 10
The expression `5 * 2` simplifies to the literal `10`. Expressions that can’t be further simplified are called *values*.
**Convention** Infix operators should have spaces on either side. So `5 / 2` is good, `5/2` is less good, and both `5 /2` and `5/ 2` are bad. Some coders prefer a style in which operators of lower precedence are surrounded by spaces while operators of higher precedence do not. For example, instead of
a * x + b * x + c
one might write:
a*x + b*x + c
but the former is preferred in this course.
**Integer Division**
– : int = 3
# 99 / 100;;
– : int = 0
Exception: Division_by_zero.
# 7 mod 5;;
– : int = 2
# max_int;;
– : int = 4611686018427387903
**The Type `float`**
– : float = 3.14
# 314e-2;;
– : float = 3.14
# 2.0 *. 3.14;; (* NB: The floating point operators: +., -, … end with a . *)
– : float = 6.28
# 7.0 /. 2.0;;
– : float = 3.15
# 2.0 ** 3.0;;
– : float = 8.0
# infinity;;
– : float = infinity
# 1.0 /. 0.0;;
– : float = infinity
# 1.0 /. 2;;
Error: This expression has type int but an expression was expected of type float
OCaml doesn’t provide implicit type conversions as most languages do. You’ll have to choose the right operator based on the types of the operands.
**Type Conversion**
Values of a new type can be obtained from values of an existing type using the built-in type conversion functions.
# truncate 3.14;;
– : int = 3
# float_of_int 1;;
– : float = 1.0
# int_of_float 1.9999;;
– : int = 1
It’s worth noting that the notation `truncate 3.14` represents an *application* or *call* of the built-in `truncate` function. You’ll also see function calls written parenthesized as `(truncate 3.14)`. You’re probably more familiar with function call syntax of the form `truncate(3.14)`. It turns out something is going on here. We’ll return to it later.
##### Infix & Prefix Notation for Operators
the operators `+, *, /, -, …` are usually written in *infix position*, i.e., the operator appears between the operands as in `2 + 3` . Infix operators can also be used in *prefix* *position* by enclosing them in parentheses. For example, one can write
# (+) 2 3;;
– : int = 5
One small catch is that the multiply operator `*` must be surrounded by spaces `( * )` so it isn’t confused with a comment.
# ( * ) 2 3;;
– : int = 6
This is also true for the exponentiation operator `**`.
Finally, notice that we can simply evaluate an operator as follows.
– : int -> int -> int =
The type of the `+` operator is `int -> int -> int` — this may look a little strange; we’ll explain it later.
The built-in operators are interpreted using the familiar PEMDAS order for the operators.
# 2.0 +. 3.14 *. 4.0;;
– : float = 14.56
# (2.0 +. 3.14) *. 4.0;;
– : float = 20.5600000000000023 (* NB: 15 decimal places for floats *)
**The Type `char`**
– : char = ‘M’
# Char.code ‘M’;;
– : int = 77
# Char.chr 77;;
– : char = ‘M’
The last two examples uses functions `code` and `chr` from the built-in `Char` library, part of the standard library that ships with OCaml. We’ll have more to say about libraries below.
**Heads Up** The string type and the bool type are built-in types but they’re actually a bit different than the base types shown above. For now we’ll ignore the difference.
**The Type `string`**
# “hello world!”;;
– : string = “hello world!”
# “hello” ^ ” world!”;; (* string concatenation *)
– : string = “hello world!”
# String.length “hello world!”;;
– : int = 12
**The Type `bool`**
– : bool = true
– : bool = false
# false || true;;
– : bool = true
# false && true;;
– : bool = false
# not (false && true);;
– : bool = true
**Relational Operators**
Values of the same type can be compared.
# ‘A’ = ‘A’;;
– : bool = true
# ‘A’ <> ‘A’;;
– : bool = false
# 3 >= 4;;
– : bool = false
# compare “Alice” “Alice”;;
– : int = 0
# compare “Al” “Alice”;;
– : int = -1
# compare “Alice” “Al”;;
– : int = 1
### Libraries
Like most programming languages, OCaml has libraries of code that can be used more or less off-the-shelf. The [Standard Library](http://caml.inria.fr/pub/docs/manual-ocaml/stdlib.html) comes with all implementations of OCaml. We’ve referred to the Standard Library’s **Char** and **String** modules already, there are many more: a **Random** module for working with random numbers, a **Printf** module for formatted printing and so on. It’s worth noting that OCaml’s Standard Library is pretty spare in comparison to standard library’s in other programming languages.
Symbols defined in library modules can be accessed by prefixing them with the module name.
# String.length “Alice”;;
– : int = 5
# Random.int 3;; (* equal chance of 0, 1 or 2 *)
– : int = 1
# Random.float 1.0;;
– : float = 0.432381
# Printf.sprintf “My friend %s is %d years old.” “Jasmine” 19;;
– : string : “My friend Jasmine is 19 years old.”
One can omit the module-name prefix by opening the module.
open Printf
sprintf “Hello %s” “world!”;;
It’s common to make an abbreviation or alias for a module name.
module P = Printf
P.sprintf “Hello %s” “world!”
**Pervasives**
Some library resources are used so, well, pervasively, in OCaml code, their definitions are housed in a module [Pervasives](http://caml.inria.fr/pub/docs/manual-ocaml/libref/Pervasives.html) that is opened automatically. Instead of requiring `Pervasives.min`, one can write simply `min`.
A few additional pervasive functions:
# let smaller = min 2 3;;
val smaller : int = 2
# floor 3.9999;;
– : int = 3
# abs (-3);;
– : int = 3
# abs_float (-2.0);;
– : float = 2.
Modules that are not part of the Standard Library need to be made known to the OCaml compiler. This can be done in a number of ways, we’ll come back to this topic later.
**Packages**
The world-wide OCaml community has developed many more library modules that provide functionality beyond the Standard Library. These libraries usually take the form of **packages** that implement complete applications or services. OCaml packages can be installed and managed by OCaml’s package manager [OPAM](https://opam.ocaml.org/).
#### Summary
– OCaml expressions are mostly familiar, being built-up from literals of base type, operators and parentheses;
– Like all functional programming languages, OCaml’s modus operandi is to simplify:
2 + 3 + 4 + 5 =>
5 + 4 + 5 ->
– A *value* is an expression that cannot be further simplified.
——————-
### Naming Values
In OCaml, values can be named using a `let`-expression. There are two basic forms:
let x = expr — top-level let
let x = expr1 in expr2 — let-in
The former makes the name `x` usable throughout the top-level. In the latter, the name `x` is only usable in the expression immediately after the `in` keyword: i.e., the expression `expr2`.
# let a = 3.0 . 2.0;; ( top level let *)
val a : float = 6.0
– : float = 6.0
# let b = 3.0 . 2.0 in b ** 2.0;; ( let-in *)
– : float = 36.0
Error: Unbound variable b
**Name Formation** Names in OCaml can be formed in the standard ways. names beginning with a lowercase letter are used for values and types; names beginning with an uppercase letter are used for module names, signature names or constructors. We’ll discuss these in the next section.
**Conventions**
1. **Name Formation**: OCaml coders tend to follow the standard conventions using either `camelCase` or `snake_case` for symbols.
2. **Cascaded `let-in` Expressions**: It’s very common to have a cascade of `let-in`-expressions as in
let x1 = expr1 in let x2 = expr2 in … let xn = exprn in expr
In this case we stack up the lets as follows:
let x1 = expr1 in
let x2 = expr2 in
let xn = exprn
#### Let-bindings Support Implicit and Explicit Typing
When introducing a name, one can choose to explicitly specify the expected type or to allow OCaml to infer the type for you. OCaml will infer the type of the right-hand side in any case. If you’ve guess wrong on your explicit type annotation, OCaml will let you know.
let x : string = “Hello” ^ ” ” ^ “World”;;
val x : string = “Hello World”
### Defining Functions
Functions are the main tool for packaging up computation in almost all programming languages. In this section we’ll introduce the basic form. In the next section we’ll discuss how to write functions in general. Functions have *definitions* and *uses*. A use of a function is often referred to in the standard way as a *call*. In functional languages function calls are often referred to as *applications*.
**Function Definitions** The two variations of the `let`-expression discussed earlier can be used to name a function value.
let functionName x1 … xn = expr1 — top-level
let functionName x1 … xn = expr1 in expr2 — let-in
The symbols `x1`, …, `xn` denote binding occurrences of *variables*. These occurrences are called *parameters* or *formal* *parameters*. Formal parameters usually govern applied occurrences or uses of the variables in the function *body* `expr1`.
**Notes**:
1. The variables `x1`, …, `xn` can be used only in `expr1`;
2. The function name `functionName` cannot be used in `expr1`, in the former case it can be used in the top-level and in the latter case it can be used only in `expr2`.
Function definitions are usually stored in text files with the **.ml** extension.
**Function Calls**
A function *call* or *application* has the form:
functionName expr1 … exprn or (functionName expr1 … exprn)
where each of `expr1`, …, `exprn` is an expression. How does a function do its job? As with the simple algebraic expressions, through simplification.
1. When a function call is evaluated, for each i = 1,..,n, `expri` is evaluated. This process may produce a value Vi, it may encounter an error or it may not stop (more on that later).
2. If for each i, the evaluation of `expri` produces a value Vi, the value Vi is plugged-in for `xi` in the function body (i.e., each occurrences of `xi` in `expr1` is *replaced* by value Vi).
3. Then the body of the function is simplified. If the body of the function has a value V, then V is the value of the function call.
**Example**: A doubling function for integers:
# let double n = n * 2;;
val double : int -> int
1. **Simplification**
double (2 + 2) => — simplification requires 3 steps
double 4 =>
double 3 + double (2 + 3) => — simplification requires 6 steps
3 * 2 + double (2 + 3) =>
6 + double (2 + 3) =>
6 + double 5 =>
6 + 5 * 2 =>
2. **The function denoted by** `double`. From its definition, OCaml has inferred that `double` is of the type `int -> int`, i.e., a function mapping integers to integers. It’s not unreasonable to think of `double` as an element of the *set* of functions from integers to integers, in particular, the element that is the set of input/output pairs:
double is { …, (-2, -4), (-1, -2), (0, 0), (1, 2), (2, 4), … }
3. **Explicit & Implicit Types** Other variations of `double` wherein the programmer explicitly specifies input/output types. All four definitions are the same.
let double (n : int) = n * 2 — specify input type
let double n : int = n * 2 — specify output type
let double (n : int) : int = n * 2 — specify both
**Example**: A min3 function that uses the pervasive two-argument `min` function to compute the minimum of 3 inputs.
# let min3 p q r = min p (min q r);;
val min3 : ‘a -> ‘a -> ‘a -> ‘a
min3 1 2 3 ->
min 1 (min 2 3) =>
min 1 2 =>
#### Polymorphism
The type of a function depends on its definition. For example, the identity function is trivial but it illustrates the point — there are no constraints on `x` in the function definition.
# let id x = x;;
val id : `a -> `a
OCaml will infer the most general possible type `’a -> ‘a`. The `’a` is a *type variable*.
# id “Hello”;;
– : string = “Hello”
# id 343;;
– : int = 343
We’ll have more to say about polymorphism later on.
## 2. Structured Types
In OCaml, new names for existing types and new types can be created and named using the `type` keyword.
### Sum Types
Sum types are one of the most important features of modern, typed functional programming languages. They’re sometimes called *variant* *types* and sometimes called *union types* or even *disjoint union types*. Variations and restricted forms of sum types have cropped up in many programming languages over the years.
# type fruit = Lemon | Apple | Lime | Banana;;
type fruit = Lemon | Apple | Lime | Banana
# let favorite = Banana;;
favorite : fruit = Banana
The symbols enumerated on the right: `Apple`, `Lemon`, `Lime` and `Banana` are *constructors* — they construct values of the sum type `fruit`. Constructors start with a capital letter and are separated with the “or” symbol `|`. We can think of the collection of them as a complete *enumeration* of the values of the type `fruit`.
Values of sum type are the basis of *dispatch* or branching. In OCaml, dispatch is based on *pattern matching*.
(* isCitrus : fruit -> bool *)
let isCitrus fruit =
match fruit with (* the expression between the keywords -match- *)
| Lemon -> true (* and -with- is the dispatch expression *)
| Apple -> false
| Lime -> true (* NB the “or” sticks lined up with the m in match *)
| Banana -> false
let isCitrus fruit = (* slightly more succinctly *)
match fruit with
| Lemon | Lime -> true
| _ -> false
> Thinking in terms of the underlying sets, we can understand the type `fruit` as denoting the 4-element set
> \{\mathtt{()}\}_0 + \{\mathtt{()}\}_1 + \{\mathtt{()}\}_2 + \{\mathtt{()}\}_3 = \{(0, \mathtt{()}), (1, \mathtt{()}), (2, \mathtt{()}), (3, \mathtt{()})\}
> where `(0, ())` represents `Lemon`, `(1, ())` represents `Apple` and so on. Since the value `()` is of the singleton type `unit`, we can simply ignore it, and effectively represent `Lemon` with just its injection tag 0, `Apple` with 1 and so on.
##### Exhaustive Matching
One of the important properties of OCaml’s `match` expression is that the compiler will warn the coder if the match expressions in their code fails to account for all of the summands. For example, writing `isCitrus` as follows (failing to match `Banana`) draws a specific compiler warning.
let isCitrus fruit =
match fruit with
| Lemon | Lime -> true
| Apple -> false
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
val isCitrus : fruit -> bool =
Exhaustive matching turns out to be extremely useful to every-day coders.
##### Constructors with Payloads
The sum type `fruit` is the simplest kind, commonly known as an *enumeration type* — all of the values of the type are explicitly enumerated symbolic names. In the more general case, the summands may carry payloads of data of one kind or another.
type number = Float of float | Int of int;;
# let pi = Float 3.14;;
val pi : number = Float 3.140000…
# let n = Int 14;;
val n : number = Int 14
# let (Int i) = Int (2 + 3);; (* pattern matching a let-binding *)
val i : int = 5
We can modify our `double` function to work on values of type `number`
(* double : number -> number *)
let double n =
match n with
| Int i -> Int (i * 2)
| Float f -> Float (f *. 2.0)
let (Int i) = double (Int 4);;
val i : int = 8
##### Notes
1. Note that the patterns in the match-clauses introduces variables `i` and `f` which can be used in the expressions on the right-hand sides of the respective `->`s.
2. It’s worth noting that most *dynamically typed* programming languages such as Python, JavaScript and the various dialects of LISP support operations on numbers. For example, in JavaScript there are no types `int` or `float`, only `number`. When an expression `2.0 + 5` is encountered in JS, well, b
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com