1.2 Elements of ProgrammingYouTube↗  IA↗(long shot)
Education  1.3K views 6 likes 0 dislikes   11 Sep 2017
Functional Programming Principles in Scala 1.3K subscribers N/A YouTube↗


Please select the problem
You must specify your email and describe the problem in detail
Describe your problem in detail if it's not obvious

Click to Play Video Click to Play Video
So in this week, we are going to do some Scala programming.
Cette semaine, nous allons faire de la programmation en Scala.
We're going to take the first steps into this new programming language and into
Nous allons faire les premiers pas dans ce nouveau langage de programmation
functional programming in general. A lot of the material in this session will
et dans la programmation fonctionnelle en général. Beaucoup de matériel dans cette session
look very easy to you because it's familiar.
paraîtra sans doute très facile pour vous dû à sa familiarité.
But there are also some things that are fundamental, in particular, the former
Mais nous allons aussi voir des choses fondamentales, en particulier
model of evaluation that we call the substitution model, which will be very
le modèle d'évaluation formel que nous appelons le modèle de substitution, qui sera très
important for the sessions later on. So, it's good to pay a little attention.
important pour la suite. Il serait donc utile de suivre attentivement cette session.
Okay, let's get into it. Every non-trivial language provides
Chaque langage non-triviale possède
primitive expressions that represents the simplest elements of the language.
des expressions primitives qui représentent les éléments plus simples de ce dernier.
And then some ways to combine expressions and ways to abstract expressions.
De plus, il contient des façons de combiner et de faire des abstractions sur ces expressions.
Abstraction means that we introduce a name for an expression and then further on we
Par abstraction, nous entendons le fait d'introduire un nom pour une expression, que nous pouvons par la suite
can reference the expression by its name. One way to approach functional programming
utiliser pour nous référer à l'expression en question. Une façon d'approcher la programmation fonctionnelle
is to see it a little bit like a calculator.
est de la voir comme une calculatrice.
In fact most functional languages have an interactive shell.
Plusieurs langages fonctionnels possèdent un interpréteur interactif.
That's also sometimes called a REPL, which stands for read, eval, print, loop, and in
Cela s'appelle également parfois une REPL (read, eval, print, loop).
that shell you can type expressions, and it will respond with the results of
la REPL evalue les expressions données par un utilisateur et imprime leur resultat.
evaluating these expressions. In Scala you can start the REPL simply by
En Scala, vous pouvez commencer la REPL en
typing Scala. So if you write Scala here, Then you get
tapant "scala". Si vous écrivez "scala" ici, vous obtenez
the ripple, that assumes that you have a standard Scalar distribution.
la REPL, qui suppose que vous avez une distribution standard de Scala.
That's actually not a requirement for this course.
Pour ce cours vous n'aurez pas besoin de cela.
For the course, we ask you to install SVT, the Scala build tool instead.
Nous vous demandons d'installer SBT, l'outil de génération de Scala.
From the SVT, you can also get the ripple simply by typing SVT consol.
Depuis SBT, vous pouvez également obtenir l'ondulation tout simplement en tapant "sbt console".
It's the same REPL, so it doesn't matter whether you start that with Scala and SVT
Cette REPL a le même fonctionnement que celle lancée avec "scala".
consol. Once you're on the REPL, you can type an
Dans la REPL, vous pouvez taper une
expression like 42. You can also define values.
expression comme 42. Vous pouvez également définir des valeurs.
Such as radius = ten. Enter REPL, in each case, respond.
Comme par exemple "def radius = 10". Dans chaque cas la REPL répond avec,
If you have an expression, with the expression's type, in this case that is
en présence d'une expression, son type, par exemple nous avons
INT, and the expression's value. If you do have a definition like radius,
"Int", et sa valeur. En présence d'une définition,
it would just give you the type of the definition.
la REPL vous donnerait juste le type de la définition.
You can also define floating point numbers.
Vous pouvez également définir des nombres à virgule flottante.
And afterwards you can refer To what you have defined before.
Vous pouvez vous référer à ce que vous avez défini avant.
Now, let's have a look at evaluation. You have seen how that these expressions
Regardons comment marche l'evaluation. Vous avez vu comment ces expressions
were evaluated. How exactly did that happen?
ont été évalués.
Well. The rules are well known from simple
Les règles pour l'evaluation sont connues pour de l'algèbre simple.
algebra. To evaluate a non-primitive expression, we
Pour évaluer une expression non primitive, nous
typically take the left most operator, subject to the rules of precedence.
prenons généralement l'opérateur le plus à gauche, en prenant en considération les règles de précédence.
We evaluate the operands of that operator. Typically left before right.
Nous évaluons les opérandes de cet opérateur. Généralement de gauche à droite.
And we apply the operator to the operands. What about evaluating a name?
Qu'en est-il de l'évaluation d'un nom?
Well, that's evaluated by replacing it with the right hand side of its
Un nom est évalué en le remplaçant par le côté droit de sa définition.
definition. We applied these steps one by one, until
Nous appliquons ces étapes une par une,
finally, the evaluation process results in a value.
jusqu'à ce que le processus d'évaluation résulte en une valeur.
And for the moment the value is just a number, later on, we also consider other
Pour l'instant la valeur est un nombre, mais nous considérerons d'autres sortes de
kinds of values. So let's see an example, here's the
valeurs par la suite. Regardons un exemple.
evaluation of the arithmetic expression, two times pi times radius.
Voici l'évaluation de l'expression arithmétique "2 pi radius".
What's happening there, first thing we do is we look up the name pi and we get its
Nous obtenons d'abord la définition du nom pi,
definition, 3.14159. Then we perform the arithmetic operation
3,14159. Puis, nous effectuons l'opération arithmétique
on the left. Then we look up the radius evaluate radius
sur la gauche. Puis nous cherchons la définition de "radius", qui évalue à
yielding ten, and finally, we perform the final multiplication, yielding the result.
10, et finalement nous effectuons la multiplication qui nous donne le résultat.
Definitions can also have parameters. For instance, we can define a square
Des définitions de fonctions peuvent également contenir des paramètres. Par exemple, nous pouvons définir une fonction
function by writing def square. Then comes the parameter x of type double,
qui retourne le carré d'un nombre, en écrivant "def square". Le paramètre x de type double vient ensuite.
and then comes the right hand side, x times x.
puis vient la partie de droite, x x.
The right hand side refers to the parameter x.
Le côté de droite fait référence au paramètre x.
And the p evaluation then would yield the expected square of two, would give four, a
L'évaluation donnerait les résultats attendus, 4 et 81.
square of five times four would give 81, We can, of course, also have,
Nous pouvons, bien sûr, ont aussi,
parameterized definitions that refer to parameterized functions as in the sum of
définitions paramétrées qui font référence aux fonctions paramétrées, comme la fonction qui
squares function here, that takes two parameters, x and y of type double, and it
effectue la somme des carrés, qui prend deux paramètres, x et y de type double,
computes the square x and square y and sums them.
et calcule le carré de x, le carré de y et leur somme.
We've seen in the last slide that function parameters come with a type, and this type
Dans le slide précédent nous avons vu que les paramètres de fonctions viennent avec un type.
is given after the parameter name and a colon in Scala.
En Scala c'est indiqué après le nom du paramètre et un deux-points.
So you would write x colon double y colon int.
Vous pouvez écrire x:Double, y:Int
You can also give the return type of a function that follows after the parameter
Vous pouvez aussi donner le type de retour d'une fonction, qui suit
list. The permative types are written as in
la liste des paramètres. Les types primitives ressemblent ceux de Java
Java, but they are capitalized. So, int for example, is a 32-bit integer,
, seulement la première lettre est majeure. Ainsi, Int est un entier de 32 bits,
double is a 64-bit, 40-point number, and Boolean represents a Boolean type bit
double est un nombre 64-bit, 40 points et Boolean représente un bit de type booléen,
value true and false. Now, how are function applications
à valeur true et false. Comment évalue-t-on les applications
evaluated? In fact, they are evaluated in a way that
de fonction ? De manière très similaire aux opérateurs.
is very similar to operators. We first evaluate all function arguments
est très semblable aux opérateurs. Nous évaluons d'abord les arguments de la fonction,
going from left to right. We then replace the function application
allant de gauche à droite. Nous remplaçons ensuite l'application de la fonction
by the function's right hand side, and at the same time, we replace the former
par le côté droit de la fonction et en même temps, nous remplaçons les
parameters of the function by the actual arguments.
paramètres de la fonction par les arguments.
Let's see how this works in an example. We start with sum of squares of three and
Regardons comment cela marche. Voici la somme des carrés de 3 et
two + two. The two + two gets rewritten to a value,
2+2. 2+2 est remplacé par sa valeur
four, and we and, we have sum of squares three, four.
4. Nous avons maintenant la somme des carrés de 3 et 4.
Then we take the definition of sum of squares, that was square of x plus square
Puis nous prenons la définition de la somme des carrés, qui était la carré de x plus carré
of y, and we replace the application by this right hand side, where at the same
de y, et nous remplaçons l'application par ce côté droit, et en
time we replace the parameters x and y by the actual arguments three and four.
même temps nous remplaçons les paramètres x et y par les valeurs 3 et 4.
We then repeat the process with the square applications.
Ensuite, nous répétons le processus avec l'application de carré.
The square of three becomes three times three.
Carré de 3 devient 3 3 :
The right turn side of square where three replaces the promidence.
Le côté droit de carré, oû l'on remplace le paramètre par 3.
We get an arithmetic simplification, and we do the same thing for the right hand
Nous obtenons une simplification arithmétique (9), et nous faisons de même chose pour la partie droite,
operators yielding the final value 25. This scheme of expression evaluation is
ce qui donne finalement 25. Ce schéma d'évaluation de l'expression est
called the substitution model. The idea underlying this model is that all
appelé "le modèle de substitution". L'idée fondamentale du modèle est que
evaluation does is reduce an expression to a value.
l'objectif de l'évaluation est de réduire une expression à une valeur.
And that reduction can be expressed by a sequence of simple rewriting steps that
Cette réduction peut être exprimée par une séquence de réécritures simples,
rewrite the expression term itself until it is a value, very similar to what you
qui réécrivent l'expression jusqu'à ce qu'il en résulte une valeur. C'est très semblable à ce que l'on ferait
would do in algebraic simplification. Simple as it is, this model is very
avec des expressions algébriques. Aussi simple qu'il puisse paraître, ce modèle est très
powerful. In fact it has been shown that it can
puissant. En fait, il a été démontré qu'il peut
express every algorithm, so it's equivalent to what you would call a Turing
exprimer tout algorithme, et donc est équivalent à ce que l'on appellerait une machine de Turing.
machine. This has been shown a long time before
En fait cela avait été établi bien avant la
functional programming, in fact, a long time before computers by a logician called
programmation fonctionnelle. Bien avant même les ordinateurs! Par un logicien appelé
Alonzo Church in the lambda calculus. He did that in the thirties of the last
Alonzo Church, avec une théorie appelé le lambda-calcul. Cette théorie a été établi dans les 1930.
century. You might have come across lambda calculus
Vous avez probablement vu le lambda-calcul dans un cours
in theoretical computer science, and if you did, then you know how to make the
d'informatique théorique; si oui, vous verrez sans doute le
connection to this model. If you didn't, don't worry.
lien avec ce modèle. Si non, ce n'est pas grave!
We won't need the theory for following the course.
Nous n'aurons pas besoin de cette théorie pour le cours.
What's important though is to know that number calculus as a model, and the
Ce qui est important cependant est de savoir que le lambda-calcul et le modèle de substitution
substitution model, can be applied only to expressions that do not have a side
s'appliquent seulement aux expressions qui n'ont pas d'effets de bord.
effect. Now, what is a side effect?
Qu'est-ce qu'un effet de bord ?
A typical side effect would be an expression called.
Un effet de bord typique est l'expression
C++ where c is a variable. And evaluating this expression means that
c++, où c est une variable. Et l'évaluation de cette expression signifie que
you return the old value of c, and at the same time you increment the value.
vous retournez l'ancienne valeur de c, tout en incrémentant sa valeur.
So, at the next time you return the value, you would return the value one larger than
La prochaine fois que vous retournez la valeur, vous retournez une valeur plus grande qu'avant.
before. Turns out there's no good way to represent
Il se trouve qu'il n'y a pas de manières élégantes de représenter
this evaluation sequence by a simple rewriting of this term.
la séquence d'évaluation par une simple réécriture de ce terme.
You need something else, like store, where the current value of the variable is kept.
Nous avons besoin de plus, comme par exemple un registre qui contient la valeur actuelle de la variable.
In other words the expression C++ has a side effect on the current value of the
En d'autres termes l'expression c++ a un effet de bord sur la valeur actuelle de la
variable. And that side effect cannot be expressed
variable. Et cet effet de bord ne peut être exprimé par
by the substitution model. So one of the motivations for ruling out
le modèle de substitution. Une des motivations pour se défaire
side effects in function programming is that we can keep to the simple model of
d'effets de bord dans la programmation fonctionnelle est que nous avons un modèle simple
evaluation. Once we have the substitution model,
d'évaluation. Avec le modèle de substitution,
another question comes up. Does every expression reduce to a value in
une autre question se pose. Chaque expressions se réduit-elle à une valeur
a finite number of steps? In fact, the answer is no.
un nombre fini d'étapes ? Et bien non.
Here's a counter example. Let's write simple function def loop int
Voici un contre-exemple. Voici la fonction "def loop : Int = loop"
equals loop. And that's then called, referred to the
Le côté de droite se réfère a lui-même.
name loop. What would happen.
Mais que se passe-t-il?
Well, according to our model we have to de evaluate that name which happens by
Selon notre modèle nous évaluons l'expression en remplaçant
replacing the name by its right hand side. The right hand side is looped again.
le nom par son côté de droite. Ce qui fait une boucle.
So we have reduced the name to itself and this can go on ad infinitum.
Nous avons donc réduit le nom à lui-même, ad infinitum.
Another way to visualize this reduction sequence is by starting with the loop and
Une autre façon de visualiser cette séquence de réductions est de commencer par "loop"
then reducing to the same term again. We've seen that the Scala interpreter
et de réduire au même terme. Nous avons vu que l'interprèteur de Scala
reduces function arguments to values before rewriting the function application.
réduit les arguments d'une fonction avant de réecrire la fonction par son application.
That's not the only possible reduction strategy.
Ce n'est pas la seule stratégie de réduction possible.
Alternatively, one could apply the function to unreduced arguments.
Alternativement, on pourrait appliquer la fonction aux arguments non réduites.
For instance, we could start with some of squares three, two plus two, and then go
Par exemple, nous pourrions commencer avec la somme des carrés de 3 et 2+2 et ensuite
on as follows. We keep the right hand side.
procéder comme suit. Nous gardons le côté de droite.
We don't reduce it to four and we simply pass it as an expression to the square
Nous ne le réduisons pas à 4, mais le passons simplement comme une expression
function. We then simplify the right hand side as
à la fonction carré. Nous simplifions ensuite le côté de droite comme
before. And then do the same thing again, pass the
avant. Puis la même chose de nouveau, nous passons
expression, two plus two to this occurrence of square, that gives two plus
l'expression 2+2 à cette occurence de carré ce qui donne
two twice in the multiplication. We then simplify the two further steps to
(2+2) (2+2) Nous simplifions ensuite deux étapes pour finalement
arrive at the final result, 25. Now you've seen two ways to evaluate the
parvenir au résultat final, 25. Vous avez vu deux façons d'évaluer la
same expression. The first evaluation strategy is known by
même expression. La première stratégie d'évaluation est appelée
core by value. The second is known as core by name.
appel-par-valeur. La seconde est appelée appel-par-nom.
An important theorem, in fact, of lambda calculus is that both strategies reduce to
Un théorème important du lambda-calcul est que les deux stratégies se réduisent à
the same final value as long as the reduced expression consists of pure
la même valeur, tant que la réduction de l'expression se compose de fonctions
functions and both evaluations terminate. Call-by-value has the advantage that every
pures et que ces deux évaluations se terminent. Call-by-value a l'avantage que chaque
function argument is evaluated only once. Call-by-name has the advantage that a
argument de fonction est évaluée une seule fois. Appel par nom a l'avantage qu'un
function argument is not evaluated at all if the corresponding parameter is not used
argument de fonction n'est pas du tout évalué si le paramètre correspondant n'est pas utilisé
in the evaluation of the function's body. Here's a question, say you're given the
dans l'évaluation du corps de la fonction. Voici une question: on vous donne la
following function definition: Def test of x and y equals x times x.
la définition de la fonction : "def test(x, y) = x x".
For each of the following function applications, indicate which evaluation
Pour chacune des applications suivantes, fonction, indiquez quelle stratégie
strategy is fastest, by which we mean, has the fewest reduction steps.
d'évaluation est la plus rapide, qui a le nombre d'étapes de réduction le plus petit.
That's for test of two three then test of three plus four eight.
Voici les cas: test(2,3), test(3+4, 8),
Test seven two times four, then finally, test three plus four, two times four.
test(7, 2<i>4) et finalement test(3+4, 2<i>4).</i></i>
Let's see how we would answer this question.
Voici comment répondre.
I have the test function here and I have the calls that I want to compare here.
J'ai la fonction test ici et j'ai les appels que je veux comparer ici.
Let's start with the first one, test two, three.
Commençons avec le premier, test(2,3).
How would that evaluate? Well, test two three, we take the
A quoi ça évalue? test(2,3) nous prenons la
definition of test, x times x. So, that would give two times two and that
définition d'un test, x x. Ce qui donnerait 2<i>2</i>
would reduce to four. And in fact that would reduce to four on
qui se réduit à 4. En fait cela se réduirait
their both evaluation strategies, both core by name and core by value because we
à 4 dans les 2 stratégies, parce que
have started with already evaluated arguments so there's no choice in the
nous avons commencé avec des arguments déjà évalués. Donc il n'y a pas de choix
matter. So here the answer would be, they are,
dans ce cas. La réponse est donc que les 2 stratègies
they have the same complexity. Let's do the next one.
ont la même complexité. Faisons le prochain.
Test three plus four eight. And I call by value, we have to evaluate
test(3+4, 8). Avec la stratégie "call-by-value" il faut évaluer
the arguments. So we get test.
les arguments. Nous obtenons
7,8. And that gives us seven times seven.
test(7, 8). Ce qui donne sept fois sept.
And the final result. Where it's under called by name we get
Et le résultat final. Quand c'est appelé par nom, nous obtenons
three plus four times three plus four. That reduces to seven times three plus
(3+4) (3+4). Cela réduit à 7 (3+4)
four. Seven times seven and 49.
7 7 et 49.
In one step more than in the core by value version.
Une étape de plus que la stratégie d'appel-par-valeur.
So core by value, has the advantage here. Let's look at the third example.
Ici l'avantage est à l'appel-par-valeur. Regardons le troisième exemple.
Test. Of seven and two times four.
test(7, 2<i>4)</i>
Here with call by value, we would get test of seven and eight.
Ici avec l'appel-par-valeur, nous obtenons test(7,8).
Finally, seven, seven. And the final, whereas with call by name,
Enfin, 7<i>7 et le résultat final. Avec appel-par-nom</i>
we would get seven. Times 749.
nous obtiendrions 7<i>7 et 49.</i>
So in this case, we have avoided the unnecessary computation for the second
Dans ce cas, nous avons évité le calcul inutile pendant du 2me
argument and the call by name is faster. The fourth example, test three plus four
argument et l'appel-par-nom est plus rapide. Le quatrième exemple, test(3+4, 2<i>4)</i>
two, two times four combines the evaluation of the second and third
combine l'évaluation du 2me et 3me cas
example. So it comes at no surprise that it's again
Ce n'est pas une surprise qu'une fois de plus,
a draw, that core by value and core by name, reduces the same number of steps
nous avons un match nul.
Similar videos:

3.4 Evaluation and Operators
Functional Programming Principles in Scala
788 views 3 likes 0 dislikes 11 Sep 2017100% match

1.6 Blocks and Lexical Scope
Functional Programming Principles in Scala
819 views 7 likes 0 dislikes 11 Sep 2017100% match

4.1 Polymorphism
Functional Programming Principles in Scala
1.3K views 7 likes 0 dislikes 11 Sep 2017100% match

1.1 Programming Paradigms
Functional Programming Principles in Scala
1.7K views 16 likes 0 dislikes 11 Sep 2017100% match

1.3 Evaluation Strategies and Termination
Functional Programming Principles in Scala
850 views 6 likes 0 dislikes 11 Sep 2017100% match

3.5 How Classes Are Organized
Functional Programming Principles in Scala
711 views 2 likes 0 dislikes 11 Sep 2017100% match

2.1 Tail Recursion
Functional Programming Principles in Scala
2.5K views 19 likes 0 dislikes 11 Sep 2017100% match

1.4 Conditionals and Value Definitions
Functional Programming Principles in Scala
775 views 3 likes 0 dislikes 11 Sep 2017100% match

3.1 Functions and Data
Functional Programming Principles in Scala
1.2K views 2 likes 0 dislikes 29 Sep 2017100% match

2.5 Scala Syntax Summary
Functional Programming Principles in Scala
759 views 2 likes 0 dislikes 11 Sep 2017100% match

1.5 Example, square roots with Newton's method
Functional Programming Principles in Scala
843 views 2 likes 1 dislikes 11 Sep 2017100% match

2.4 Example, Finding Fixed Points
Functional Programming Principles in Scala
750 views 1 likes 0 dislikes 11 Sep 2017100% match

2.3 Currying
Functional Programming Principles in Scala
1.1K views 8 likes 1 dislikes 11 Sep 201742% match

3.2 More Fun With Rationals
Functional Programming Principles in Scala
766 views 3 likes 0 dislikes 29 Sep 201731% match

Functions
CS50
90.9K views 0 likes 0 dislikes 26 Sep 201226% match










2.2 Higher Order Functions
Functional Programming Principles in Scala
1.5K views 5 likes 0 dislikes 11 Sep 201725% match

Recursion
CS50
91.1K views 0 likes 0 dislikes 10 Sep 201325% match










3.4 Class Hierarchies
Functional Programming Principles in Scala
1.2K views 2 likes 0 dislikes 11 Sep 201722% match


Settings Privacy About Contact Donate