core_concepts
Core concepts in functional programming¶
Copyright (c) 2022, G. Hennequin.
Copyright By PowCoder代写 加微信 powcoder
In this introduction, we are going to cover some really basic things about functional programming (FP). If this looks too easy, do not worry, it will get complicated soon enough 😁.
Learning objective ─ the goal of this section is to get a quick overview of functional programming in OCaml. We will learn about functions, types, let-bindings, operators… but we will learn just enough to get a reasonable sense of how FP works. We will later cover each of these topics (and more!) in greater depth as part of dedicated lectures.
To navigate the notebooks in this course, use the ← and → arrows to fold or unfold each subsection.
1. Basics: what is a function?¶
Let us begin with a couple of examples of functions we know, namely “mathematical functions”, and then generalize the notion of a function.
Example 1 You are probably already familiar with $x \mapsto \sin(x)$
This function, as many other functions you know ($x \mapsto -x$, or $x \mapsto \tanh(x)$, or …), takes a single number as input, and outputs a single number. In this course, we will describe this using the following notation:
sin : number -> number
Example 2 The square root function: $x \mapsto \sqrt{x}$.
This one only accepts positive inputs, and returns positive outputs, so we can write:
sqrt : positive_number -> positive_number
Example 3 The modulus of a complex number, $z \mapsto | z |$
This function takes a complex number, and outputs a positive real number:
modulus: complex_number -> positive_number
Now, a complex number can be represented as a pair of real numbers (real and imaginary parts). So we could just as well write this as:
modulus: (number * number) -> positive_number
Example 4 As a final example, consider the function that converts a complex number expressed in Cartesian coordinates, to its corresponding polar representation. This function takes a pair $(x,y)$, and returns a pair $(r, \theta)$:
cartesian_to_polar : (number * number) -> (positive_number * number)
We could go on and on, giving yet more examples of functions that you know. What do they have in common?
They have an input domain, i.e. a set of acceptable inputs, or “arguments”
They have an output domain (sometimes called “co-domain” in mathematics), which is the kind of things they compute and return
They do NOT modify the state of your world. Evaluating sin(x) cannot change anything else in your program. This might sound silly, but this feature called “immutability” is a hallmark of functional programming and really sets this paradigm apart from so-called “imperative” programming (e.g. C, python, …).
Note that the transformation from input to output can be arbitrarily complex!
For example, you could consider the function that takes a picture, and returns the name and age of each person in the picture. This function would have the form of
f : image -> list_of (text * integer_number)
Key message: functional programming is all about writing functions and composing them into more complex functions.
In this course, we will begin by writing really simple functions, which are in fact readily available as part of the standard library or other third-party libraries. We will then progress to writing more sophisticated algorithms. Bear in mind, though, that it is in the real world that OCaml shines, as it enables robust and massively scalable software design in areas as diverse as web front-ends (e.g. Facebook messenger) and backends (web servers, databases), systems (scripting, unikernels, etc), scientific computing (e.g. in my lab), crypto-currencies (e.g. Tezos), finance, formal logic (e.g. theorem proving), meta-programming (e.g. reasoning about programs), and many other areas!
For function composition to be an effective way of expressing computations, we need to be able to specify complex input and output domains, which programmers also call TYPES. Before we are ready to learn about functions in more depth, we first need to learn more about types.
2. Expressions, types and values¶
2.1 Your first OCaml program¶
From the 4 examples above, you can see that we rely on “primitive types” (e.g. numbers, positive numbers, …) to build “composite types” which are new types made from old ones (e.g. pairs of numbers). In this course, you will learn that functional programming very much relies on the ability to construct your own types for expressing the kind of data that your functions will manipulate.
It is now time to write our very first OCaml program 🏆:
Pro Tip: Use Shift+Enter to execute a code cell.
(we start easy 😀).
What happened here? We just wrote 6, and OCaml tells us – : int = 6 which means the following:
“this expression evaluates to something that you haven’t given a name to (-), which has type int (integer number), and is equal to 6”.
Please remember this terminology, which we will re-use throughout the course.
In an OCaml code cell, you will be typing in so-called “expressions”, which will become more and more complex as we learn more.
The OCaml interpreter evaluates each expression, to compute its value, along with its type.
2.2 Primitive types¶
Type int was an example of a primitive type, which OCaml already know how to represent internally. Now try the following:
“hello from Cambridge”
So that’s already 5 primitive types, which are also called “native types” which OCaml already knows about. Later, we will learn about several additional native types.
Note that OCaml automagically recognises the type of expressions: you don’t need to tell OCaml explicitly that 6 is an integer number or that ‘a’ is a character! This is called “type inference”, and you will progressively understand how powerful that is, as we go along.
Finally, here is one more primitive type, called unit:
This type is called unit has only one possible value, which is denoted by (), i.e. the “empty expression”. It is the type of “nothing”. You will see how it is used later.
2.3 Composite types¶
We will dedicate a whole lesson to composite types, because they are so important! For now, let us simply build up appetite by learning about the simplest composite type: tuples. Tuples let you represent “collections of types”. Here is an example of a 2-tuple, also known as a “pair”:
Tuples are also sometimes called “product types” (a name that comes from the mathematics of sets / ensembles). For this reason, OCaml uses the * notation (which, for types, does NOT mean integer multiplication!). Thus, a N-tuple is a type of the form type1 * type2 * … * typeN.
Here are a couple more examples (beware the parentheses!):
1, 8, “house” (* that is a 3-tuple *)
1, (8, “house”) (* that is a pair, where the second element is itself a pair;
it is NOT a 3-tuple *)
(1, 8), (“house”, false) (* that is a pair of pairs, NOT a 4-tuple *)
Exercise 2.2 / A
What is the type of the following expression:
(true, (3, false)), “weird”?
(* type your solution here *)
Exercise 2.2 / B
Construct an expression that has the following type: string * (unit * float).
(* type your solution here *)
2.4 Defining your own types¶
Type definitions ─ Importantly, OCaml lets us define our own types using the keyword type, and give them names:
type t = bool * string
Here, we have defined a type called t which can now be used to represent pairs made of abool and a string values. Note that we didn’t have to define this type to be able to use bool * string values, but it is sometimes convenient to rename such types. Later, you will learn how to define “truly new types”, i.e. types that are not mere combinations of existing types.
3. Let-bindings: giving names to values.¶
3.1 Top-level bindings¶
In order to build more interesting programs, we need to be able to give names to values, otherwise we simply cannot re-use them! OCaml does this through so-called let bindings:
let x = true
Notice how OCaml now tells us val x : […] — this means “I now hold a value called x in memory”.
You can override any let binding previously established:
The name x has now be re-bound to value 5 (of type int) and so now the name x no longer denotes the value true.
The point of let-bindings is to be able to reuse previously computed values in other expressions. For example, we can re-use the x value in this new expression:
let y = 2 * x
The * operator denotes integer multiplication (more on this later!).
2 * x is a simple example of an expression which OCaml can evaluate (here, giving a value of 10).
Exercise 3.1 / A
Bind the value “hello from” to some name of your choice.
Then re-use that name to construct the value “hello from Cambridge”. You may use the ^ operator, which denotes string concatenation.
(* write your solution here *)
Use Ctrl-L to autoformat your code. It will fail if there is a syntax error.
The let-bindings we have written so far are called top-level bindings, because the value gets bound to the name everywhere else in your program (in particular, you can use those names in any function ─ we’ll get to this soon).
3.2 Local bindings¶
OCaml also lets you write local let-bindings, which are only used in the current expression. The syntax is slightly different:
let [name] = [expr] in [another expr]
let x = 5 (* top-level binding *)
let x = 6 in
x + 1 (* local let binding *)
What do you think is x bound to, now? Check: 👇
x got bound to 6 only locally in the expression that follows the in keyword, i.e. x + 1, so the previous top-level binding remains active at the top level.
(* two local let bindings *)
let x = 6 in
let z = 3 in
And what do you think z is bound to? Check: 👇
z was only bound locally inside the expression bound to y above, and therefore it is not available in the top level.
Here is another example: what do you think the following expression evaluates to? 👇
(let x = 3 in
* ((let x = 2 in
OCaml evaluates such expressions by recursively evaluating each sub-expression until the final value becomes determined.
let x = 5 in
let y = x * x in
Exercise 3.2 / A
Using only two * multiplications, compute x to the power of 4.
let x_power_4 =
let x = 5 in
(* type the rest of your solution below *)
4. Boolean operators and conditional expressions¶
Recall: a value of type bool can only be true or false. Much of the internal logic of computer programs relies on the ability to perform operations on values of type bool using not, and, or, and the ability to construct conditional expressions.
let a = true
let b = not a
(* || means “or” *)
let c = if a || b then 5 else 6
(* && means “and” *)
let d = if a && b then 3 else 4
Notice how if [expr1] then [expr2] else [expr3] requires:
expr1 to be of type bool (i.e. true or false)
expr2 and expr3 to have the same type. This is because otherwise, OCaml wouldn’t know what type to attribute to the result, before actually evaluating it. OCaml is a so-called statically typed language, meaning that the type of any value must be determined statically at compile time, not dynamically at run time.
Thus, OCaml will complain with useful error messages if you make those mistakes:
if 5 = 6 then “three” else “something else”
if true then true else “false”
Static typing, coupled with type inference and polymorphism (more on this later!) is what gives OCaml programmers a very strong sense of “if it compiles, it is likely going to do what I intend”.
5. Functions, at last!¶
5.1 Defining simple functions¶
Now that we know how to manipulate expressions and make sense of their types, we are ready to learn about functions.
In OCaml, functions can be defined in several ways. One possible way is as follows:
let double x = 2 * x
Notice how OCaml interprets this as a new value of type int -> int. This is a special kind of type, called an arrow type (because of the arrow in the middle).
Key message ─
In functional programming languages, functions are typed values, just the same as integers, floats, and strings!
We say that functions are “first-class citizens”.
Now that we have defined the double function, we can actually use it!
Note that contrary to many other programming languages, arguments are given right after the function name, with a space in between, without parentheses. The reason for this will become clear in a moment.
There is another way of defining functions:
let double = (fun x -> 2 * x)
(the two ways are completely equivalent; in fact, if you try to auto-format the cell above, it will rewrite the definition of double using the first way!)
This alternative way of writing functions highlights the fact that (fun some_argument -> some_output) is an OCaml expression like any other.
Can you guess what the following expression evaluates to?
(fun x -> 2 * x) 10
This example shows that we can define and use functions without even giving them a name! Such anonymous functions we will used very often.
With all you have learned so far, you know enough to be able to define a function of 2 arguments. Give it a try and write the function $f(x,y) = x^2 + y^2$.
Exercise 5.1/A
Write a function f that takes two arguments, and returns the sum of their squares.
One obvious solution is to use, in fact, a single argument, of the “pair” type:
let f (x, y) = (x * x) + (y * y)
Here, (x,y) is a value of type int * int, and is considered a single argument.
But Ocaml has a better way of dealing with multiple arguments:
let f_better x y = (x * x) + (y * y) (* or let f_better = fun x y -> … *)
This function has type int -> int -> int. This is quite different from (int * int) -> int! But this enables a super useful feature of most functional programming language: partial evaluation. Observe the following:
f_better 2 3 (* this should be 2*2 + 3*3 = 4 * 9 = 13 *)
let g = f_better 2
Here g corresponds to a partial evaluation of the function f_better: it is still awaiting the second argument! Hence the int -> int type.
This behaviour will prove useful in many ways. In particular, partial evaluation facilitates a lot of useful optimizations. Imagine that we want to compute (x * x) + (y * y) for a single value x=2 and a million different values y = 1, 2, 3, …., 1_000_000. How many multiplications would you perform if you were to use f? The answer is two million.
Consider this slight tweak to f_better instead:
let f_better x =
let x_squared = x * x in
fun y -> x_squared + (y * y)
let g = f_better 3
This function computes the same as before, but the partial evaluation let g = f_better 2 allows us to compute x_squared = x * x once and for all. By applying g to the million different values of y, we are now performing only 1_000_001 multiplications, instead of 2_000_000. Thus, we will be done roughly twice as fast.
Note that such an optimization would be more difficult if we had used let f (x, y) = […], which cannot be partially evaluted. Here, OCaml has an edge over many other programming languages.
When writing functions of multiple arguments, think carefully about potential partial evaluation use cases, and “pull out” whatever computation does not depend on later arguments (above, we “pulled out” the computation of x * x).
5.2 Pure vs. impure functions¶
So far, we have been learning about so-called pure functions, which take their inputs, compute their outputs, and do not modify anything else about your program whatsoever. How could they? We haven’t even introduced the notion of a “variable” that could be modified. All the values we have manipulated so far are called immutable values, i.e. you can give them a name (and rename them at the top level) but they cannot be modified internally. For example:
let add_one x = x + a
let result = add_one 5
The function add_one uses the let binding let a = 1 and forms a “closure” in which a is replaced by 1. Re-using the name a to denote 3 does not modify the value of a in that closure. Hence, the result is 6.
OCaml is a hybrid language which does allow you to switch to a more imperative way of programming when convenient, and so in principle you are allowed to use mutable data types such as a reference (which C programmers would call a “pointer”):
let r = ref 0
(don’t worry too much about the {…} notation, we’ll learn about this later). Here, r is an int ref, which you should understand as a box that contains a int value, which can be replaced by another int value. This can be done via the := operator:
To read what’s “in the box”, use the ! notation:
Although OCaml does let you use mutable data, for pedagogical reasons we will KEEP AWAY from this (almost) entirely in this course! At times, you will find that some programs are perhaps more easily expressed using imperative programming, so bear in mind that OCaml allows you to switch if you ever need to in the future.
Some OCaml functions have unit return type. For example, the init function in the Random module of the standard library has this type:
Random.init
In other words, this is a function that takes an int, and returns nothing 🤔. What use could one have for such a function?
Such a function is likely “impure”, i.e. it is a function that modifies the state of the world. For example:
let r = ref “Hello”
let f () = r := “Hi”
Here, f () returns nothing (unit), but modifies the state of the world, by modifying what’s in the r box…
You can imagine how such “impure” functions can create a big mess in your code: if a function is allowed to change other parts of your programme, you need to be very careful about keeping track of these modifications, or else things can go very wrong. It’s even worse if you are using third-party library functions that you did not even write yourself, so you are not even sure what they might modify. And it’s getting really bad when using mutable data in the context of a multi-threaded parallel programme, when different processes might make these modifications asynchronously in an order that you can’t easily control.
Pure functional programming frees you from having to think of modifications made to values you hold in memory. It eliminates a very large number of potential bugs.
Having said that, there are some functions with unit return type that you can use fairly safely: these are functions that modify the state of the world in a part that you don’t really care much about, i.e. what’s printed on your screen:
#require “fp” (* we will often load this library which I have made for this course *)
Fp.Utils.print_msg (* this function has ‘unit’ return type;
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com