Chapitre 1 : Introduction - LACIMblondin/files/inf2160/hiv2018/introduction.pdf · I Xmonad:...

Chapitre 1 : Introduction

Alexandre Blondin Masse

Departement d’informatiqueUniversite du Quebec a Montreal

10 janvier 2018Paradigmes de programmation

INF2160

A. Blondin Masse (UQAM) 10 janvier 2018 1 / 47

Table des matieres

1. Presentation du cours

2. Paradigmes de programmation

3. Rappels mathematiques

4. Le langage Haskell

5. Fonctions et types

6. Listes et tuples

Table des matieres

6. Listes et tuples

Informations generales

Trimestre Hiver 2018Titre du cours Paradigmes de programmation

Sigle INF2160Horaire Mercredi, de 14h00 a 17h00

Departement InformatiqueEnseignant Alexandre Blondin Masse, professeur

Coordonnateur Roger Villemaire, professeurBureau PK-4525

Telephone 5516Courriel blondin_masse.alexandre@uqam.ca

Page web http://lacim.uqam.ca/˜blondin

Description du cours (1/2)

I Presenter les concepts fondamentaux de langages deprogrammation modernes.

I Comprendre les possibilites et limites des divers types delangages.

I Familiariser l’etudiant avec differents paradigmes deprogrammation et favoriser l’acquisition de nouvellestechniques et strategies de programmation.

I Etude des paradigmes de programmation fonctionnel etlogique.

Description du cours (2/2)

Revue des principes de programmation fonctionnelle :

I Strategies d’evaluation des arguments.

I Polymorphisme et deduction des types.

I Fonctions d’ordre superieur.

I Efficacite et optimisation.

Revue des principes de programmation logique.

I Forme clausale de la logique du premier ordre etclauses de Horn.

I Unification et resolution.

I Le probleme de la negation.

Formule pedagogique et prerequis

I Ce cours comporte une seance obligatoire de laboratoire(2 heures).

I 1 heure de laboratoire = 1 heure de moins perdue a lamaison!

I Tres importante pour se familiariser avec les outils :editeur de texte, interpreteur, Git pour la remise destravaux pratiques, etc.

I Prealables :

I INF1130 Mathematiques pour informaticien ouMAT1060 Mathematiques algorithmiques;

I INF2120 Programmation II.

Modalites d’evaluation

I Examen intra (30%);

I Examen final (30%);

I Travail pratique 1 (Haskell) (20%);

I Travail pratique 2 (Prolog) (20%).

I Penalite de 2% par heure de retard pour les travauxpratiques;

I Doivent etre remis par l’intermediaire de la plateformeGitLab.

References

I Learn You a Haskell for Great Good!, par Miran Lipovaca,disponible en ligne.

I Real World Haskell, par Bryan O’Sullivan, Don Stewart etJohn Goerzen, disponible en ligne.

I Purely Functional Data Structures, par Chris Osaki,disponible en ligne.

I Programming in Prolog, par William F. Clocksin etChristopher S. Mellish, Springer.

I Prolog: A Tutorial Introduction, par James Lu et Jerud J.Mead, disponible en ligne.

Table des matieres

6. Listes et tuples

Plusieurs paradigmes

(source: Wikipedia)

Paradigmes populaires

I Imperatif (C, Pascal, ...): les instructions sont executeessuccessivement et modifient l’etat courant duprogramme;

I Fonctionnel (Haskell, Common Lisp, Scheme, ...):combinaison de fonctions pures, d’ordre superieur,sans effet de bord;

I Objet (Java, C++, Smalltalk, etc.): des entites (lesobjets) interagissent entre elles, selon certaines regles;

I Logique (Prolog, ...): les problemes sont modelises par desregles logiques, desquels on peut faire de l’inference.

I Concurrent (Erlang, Java, C#, ...): differente calculs sontfait en parallele, dans un ordre quelconque.

I etc.

Paradigme “visuel”

I Engouement pour la programmation visuelle;

I Permet d’initier differents types de public a laprogrammation.

Site: https://scratch.mit.edu/

Source de l’image: ici

Langages multiparadigmes

Programming language “paradigms” are a moribundand tedious legacy of a bygone age. Modernlanguage designers pay them no respect, so why doour courses slavishly adhere to them? This paperargues that we should abandon this method ofteaching languages, offers an alternative, reconcilesan important split in programming languageeducation, and describes a textbook that exploresthese matters.

— Shriram Krishnamurthi

I Exemple academique: Oz.

I But du cours: vous familiariser avec les paradigmesfonctionnels et logiques.

Table des matieres

6. Listes et tuples

Ensemble

I Un ensemble est une collection d’objets, appeleselements;

I Plusieurs facons de definir un ensemble:

I En extension;

I En comprehension;

I En francais.

I Plusieurs operations possibles: reunion (∪), intersection(∩), difference (−), difference symetrique (⊕), produitcartesien (×), etc.

I Plusieurs relations possibles: appartenance (∈), inclusion(⊆), etc.

Definition en extension

C = {rouge, vert , bleu}R = {(1, 1), (2, 2), (3, 3), . . .}N = {0, 1, 2, . . .}N∗ = {1, 2, 3, . . .}Z = {. . . ,−2,−1, 0, 1, 2, . . .}

3,−2

4, . . .

{0, 1, π, e,−1,−1

3, . . .

}Bool = {True,False}Char = {. . . ,’0’,’1’, . . . ,’9’, . . . ,’A’, . . . ,’Z’, . . .}

String = {"","a","pomme", . . .}

Definition en comprehension

C = {(r, g, b) ∈ N3 | 0 ≤ r, g, b ≤ 255}

Q ={ab

∣∣∣ a ∈ Z, b ∈ Z∗}

R+ = {x ∈ R | x ≥ 0}[a, b] = {x ∈ R | a ≤ x ≤ b}

R(x, y, w, h) = {(z, t) | x ≤ z ≤ x+ w, y ≤ t ≤ y + h}B(x, y, r) = {(z, t) | (z − x)2 + (t− y)2 ≤ r2}

Char = {c | c est un caractere unicode}String = {s1s2 · · · sn | n ∈ N, si ∈ Char pour i = 1, 2, . . . , n}

Definition textuelle

I Soit A = {0, 1}. Alors

I An est l’ensemble des chaınes binaires de longueur n;

I A∗ est l’ensemble des chaınes binaires (finies).

I L’ensemble LZ de toutes les listes d’entiers;

I L’ensemble LR de toutes les listes de nombres reels;

I L’ensemble C de toutes les couleurs;

I L’ensemble P de toutes les pages web;

I L’ensemble F de tous les comptes Facebook;

I etc.

Ensembles et types

I Tout type de donnees peut etre vu comme un ensemble;

I Une variable v de type T signifie simplement que v ∈ T ;

I Par exemple, en Java:

I int est l’ensemble des entiers (signes) representablessur 32 bits;

I double est l’ensemble des flottants (signes)representables sur 64 bits;

I Object est l’ensemble de tous les objets;

I ArrayList<Integer> est l’ensemble de toutes leslistes-tableau d’entiers;

I etc.

Fonction

I Une fonction est un triplet (A,B,G), ou

(i) A est un ensemble (fini ou infini), appele domaine;(ii) B est un ensemble (fini ou infini), appele codomaine;(iii) G ⊆ A×B est une relation, appelee graphe de f

telle que pour tout a ∈ A, il existe un unique b ∈ B telque (a, b) ∈ G.

I On utilise la notation:

f : A → Ba 7→ f(a)

I L’expression a 7→ f(a) est aussi appele regle decorrespondance.

Exemples

carre : Naturel → Naturelx 7→ x ∗ x

(+) : Reel× Reel → Reel(x, y) 7→ x+ y

length : Liste → NaturelL 7→ nombre d’elements dans L

chiffre : Char → Booleen

c 7→

{vrai , si c est un chiffre.

faux , sinon.

triee : Liste → ListeL 7→ L′ (la liste L apres tri)

Ensembles de fonctions

I Un ensemble peut meme contenir des fonctions:

FN→N = {f | f : N→ N}FChar→Booleen = l’ensemble des fonctions

de Char vers Booleen

I Un ensemble de fonctions peut aussi etre vu comme untype.

I Nous allons manipuler ces types tout au long de la session.

I Exemple: la fonction map:

map : FA→B × LA → LB(f, L) 7→ [f(L[i]) | i = 0, 1, . . . , |L| − 1]

I Plus concretement,

map(carre, [1, 10, 2]) = [1, 100, 4].

Fonctions recursives

I La fonction

numLeafs : Arbre → Naturel

a pour regle de correspondance

numLeafs(T ) =

0, si T est vide;

1, si T.gauche et T.droit sont vides;

numLeafs(T.gauche)

+numLeafs(T.droit), sinon.

I La recursivite est fondamentale en informatique, enparticulier en programmations fonctionnelle et logique.

Table des matieres

6. Listes et tuples

Historique

I Creation de Miranda, en 1985, un langage fonctionnel, aevaluation paresseuse;

I Devient rapidement tres populaire. Probleme? Modeleproprietaire.

I En 1987, a Portland, Oregon, formation d’un comite dontle but est d’etablir un standard, base sur les points fortsdes langages fonctionnels de l’epoque.

I 1990: Haskell 1.0, en l’honneur du logicien HaskellCurry.

I 1998: Haskell 98, premier standard durable.

I 2010: Revision majeure du standard.

I Aujourd’hui: Revisions annuelles.

Caracteristiques

I Base sur le lambda calcul;

I Langage interpretable;

I Langage compilable;

I Purement fonctionnel;

I Typage fort et statique;

I Evaluation paresseuse;

I Permet une grande genericite;

I Tres peu verbeux, par opposition a C/C++/Java.

I Tres efficace (compile en C).

Outils

I Compilateurs: GHC (utilise en classe), Hugs(developpement arrete);

I Documentation: Haddock;

I Installation/Distribution: Cabal (analogue aEasyInstall/Pip en Python et Gem en Ruby).

I Archive de paquets: Hackage.

Logiciels populaires

Plusieurs logiciels ont ete developpes en Haskell:

I Sigma: Pour lutter contre le spam (Facebook);

I Pandoc: Conversion de documents;

I Xmonad: Gestion des fenetres;

I Darcs: Systeme de controle de version (comme Git);

I etc.

Interpreteur

I Il suffit d’installer GHC;

I Puis dans un terminal, on entre ghci:

I Ensuite, on saisit des instructions apres l’invitePrelude>.

I Une affectation est faite a l’aide du mot reserve let.

Compilateur

I Il est egalement possible de compiler un programme:

I Considerons le programme suivant:-- Fichier Hello.hsmain = putStrLn "Hello, world!"

I Les lignes commencant par -- sont des commentaires;

I Le nom du fichier devrait commencer par une majuscule:preferer Hello.hs a hello.hs;

I L’extension est .hs;

I On compile (comme avec gcc!):ghc -o hello Hello.hs

I Puis on l’execute:./hello

Chargement d’un module

I Il suffit d’utiliser l’instruction:l <Fichier.hs>

I Prenons le fichier Fibo.hs suivant:-- Fibonacci (inefficace)fibo :: Integer -> Integerfibo 0 = 0fibo 1 = 1fibo n = fibo (n - 1) + fibo (n - 2)

Table des matieres

6. Listes et tuples

Fonctions

I Dans le lambda-calcul, tout est une fonction (meme lesconstantes);

I La syntaxe en Haskell est assez proche de celle desmathematiques.

I Fonction mathematique:

| · | : Reel → Reel

r 7→

{r, si r ≥ 0;

−r, sinon.

I En Haskell:

valeurAbsolue :: Double -> DoublevaleurAbsolue r

| r >= 0 = r| otherwise = -r

Declaration d’une fonction

I Lorsqu’on declare une fonction, la signature est tresimportante:

estCodePermanent :: [Char] -> Booltranslate :: (Float,Float) -> (Float,Float)somme :: Int -> Int -> Intmap :: (a -> b) -> [a] -> [b]

I Parfois, elle peut etre omise: le compilateur peut deduirele type, s’il n’y a pas d’ambiguıte.

Prelude> let somme a b = a + bPrelude> somme 3 811Prelude> :t sommesomme :: Num a => a -> a -> a

I Note: Num est la classe numerique (tres different desclasses en oriente-objet).

Regle de correspondance

I Il y a plusieurs facons de definir la regle decorrespondance.

I Par filtrage (pattern matching);

I Avec des gardes;

I A l’aide d’autres fonctions;

I En utilisant des variables/fonctions locales, a l’aidede where, let/in, case, etc.

I En informatique, definir une fonction = implementerune fonction:

Appeler/appliquer une fonction

I En mathematiques, on utilise la notation fonctionnelle(avec des parentheses).

I Par exemple, considerons la translation de vecteur (a, b):

Ta,b : R2 → R2

(x, y) 7→ (x+ a, y + b)

I Alors on ecrit T3,−4(1, 0) pour denoter le couple obtenu partranslation de vecteur (3,−4) du point (1, 0).

I En Haskell, on utilise plutot des espaces:-- Translation de vecteur (a,b)translate :: (Float,Float) -> (Float,Float) -> (Float,Float)translate (a,b) (x,y) = (x + a, y + b)

-- Application partielle d’une fonctiontranslate3m4 :: (Float,Float) -> (Float,Float)translate3m4 = translate (3,-4)

Table des matieres

6. Listes et tuples

Structures de donnees de base

I En Haskell, une structure de donnees fondamentale est laliste;

I Elle est identifiee par des crochets : [1,4,2];

I Une chaıne de caracteres est une liste :

Prelude> [’o’, ’u’, ’i’] == "oui"TruePrelude> :t "oui""oui" :: [Char]

I Plusieurs fonctions sont disponibles pour manipuler leslistes;

I En particulier, on en trouve dans le module Data.List:

Prelude> import Data.ListPrelude Data.List>

Homogeneite des listes

I Les elements d’une liste doivent etre de meme type:

Prelude> [1,’a’]<interactive>:3:2:

No instance for (Num Char) arising from theliteral ’1’

In the expression: 1In the expression: [1, ’a’]In an equation for ’it’: it = [1, ’a’]

I Utiliser des tuples ou des enregistrement pour deselements de type different.

Autres operations (1/2)

Prelude> [1,2] ++ [3,4,5] -- Concatenation[1,2,3,4,5]Prelude> ’a’:"llo" -- Cons"allo"Prelude> head "paradigme" -- Tete’p’Prelude> tail "paradigme" -- Reste"aradigme"Prelude> last "paradigme" -- Dernier element’e’Prelude> init "paradigme" -- Partie initiale

Autres operations (2/2)

Prelude> length "paradigme" -- Longueur9Prelude> reverse "paradigme" -- Renversement"emgidarap"Prelude> take 4 "paradigme" -- Prefixe"para"Prelude> drop 3 "paradigme" -- Suffixe"adigme"Prelude> maximum "paradigme" -- Element maximum’r’Prelude> elem ’i’ "paradigme" -- AppartenanceTruePrelude> ’i’ ‘elem‘ "paradigme" -- Notation infixeTruePrelude> replicate 10 ’e’ -- Repetition"eeeeeeeeee"

Intervalles

Prelude> [1..8][1,2,3,4,5,6,7,8]Prelude> [3,6..20][3,6,9,12,15,18]Prelude> [3,6..18][3,6,9,12,15,18]Prelude> [’m’..’r’]"mnopqr"

Listes infinies

I Etant un langage paresseux, on peut facilementrepresenter des objets infinis;

I Generalement, les listes infinies sont combinees avec desoperations qui les rendent eventuellement finies lors del’evaluation:

Prelude> cycle [1,2,3][1,2,3,1,2,3,1,2,3,1,2,3,...Prelude> repeat 8[8,8,8,8,8,8,8,8,8,8,8,8,...Prelude> take 4 (repeat ’a’)"aaaa"

Tuples

I On peut facilement regrouper des donnees (homogenes ounon) a l’aide de tuples:

Prelude> (3,4)(3,4)Prelude> (1,’a’)(1,’a’)Prelude> ("INF2160", "Paradigmes", "H2018")("INF2160","Paradigmes","H2018")

I Une fonction tres pratique, zip:

Prelude> zip "alpha" [1..5][(’a’,1),(’l’,2),(’p’,3),(’h’,4),(’a’,5)]Prelude> zip "fromage" (cycle [1,2,3])[(’f’,1),(’r’,2),(’o’,3),(’m’,1),(’a’,2),(’g’,3),(’e

’,1)]

Comprehension de liste

I On peut construire des listes en comprehension (commeen mathematiques!):

Prelude> [i * i | i <- [0..10]][0,1,4,9,16,25,36,49,64,81,100]Prelude> [replicate i ’a’ | i <- [0..5]]["","a","aa","aaa","aaaa","aaaaa"]Prelude> [i * i | i <- [0..10], odd i][1,9,25,49,81]

I On peut utiliser plusieurs variables, meme les imbriquer:

Prelude> [i * j | i <- [0..5], j <- [i..5]][0,0,0,0,0,0,1,2,3,4,5,4,6,8,10,9,12,15,16,20,25]Prelude> [[i * j | i <- [0..4]] | j <- [0..3]][[0,0,0,0,0],[0,1,2,3,4],[0,2,4,6,8],[0,3,6,9,12]]Prelude> [[i * j | j <- [0..3]] | i <- [0..4]][[0,0,0,0],[0,1,2,3],[0,2,4,6],[0,3,6,9],[0,4,8,12]]

Lecture

I Chaque semaine, une lecture est proposee;

I Elle est complementaire au contenu vu en classe;

I Cours d’aujourd’hui: sections 1 et 2 de Learn You aHaskell for Great Good!.

Chapitre 1 : Introduction - LACIMblondin/files/inf2160/hiv2018/introduction.pdf · I Xmonad:...

Documents

files.homo-galacticus.fr · Web viewIl est dédié tout particulièrement à la sagesse, au courage et à l’intégrité de ces Etres Supérieurs qui, à-travers des incarnations

DIVERSITE UNITE DES ETRES HUMAINS Place dans la progression : les acquis : - chaque individu présente les caractères de lespèce avec des variations qui

Techniques de Reformulation en Programmation …liberti/hdr.pdf · Techniques de Reformulation en Programmation ... Ces el´ ´ements, c’est `a dire param etres, vari-` ables, fonctions

Chapitre 1 : Les êtres vivants, différences et points ...profsvt71.e-monsite.com/medias/files/chapitre-1-les-etres-vivants... · Chapitre 1 : Les êtres vivants, différences et

Martines de Pasqually - Traité de la réintégration des etres

Architecture des ordinateurs - igm.univ-mlv.frigm.univ-mlv.fr/~pivoteau/ARCHI/COURS/archi_cours4.pdf · Lors de la conception d’une micro-architecture, plusieurs param etres entre

CHAPITRE 1 : DIVERSITE ET STABILITE GENETIQUE DES ETRES …alexandre.artus.free.fr/cours2017/troisiemes2017... · 2018. 8. 23. · Ce que je sais : • Tous les êtres vivants sont

Introduction à OpenCVwcours.gel.ulaval.ca/2018/h/GEL3014/default/5notes/presentiels/opencv-2018-2.pdfde OpenCV Installation Paramètres d’une caméra Acquisition et achage vidéo

Extrait de la publication…les ancêtres avaient reçu des Etres surnaturels les premières révélations culturelles. Et comme les sociétés traditionnelles n'ont pas, à propre-ment

marieheleneh.files.wordpress.com · Web viewDECLARATION SUR LA TRAITE DES ETRES HUMAINS. Cité du Vatican – Novembre 2013

CONFÉRENCE ENERGIE Rapport de mission Trak OWatts Bilan de consommation ETRES

labsolucafe.orglabsolucafe.org/projet1/resumeducoursdebiologiegenera... · Web viewRésumé du cours de biologie générale (Plantes, Animaux et Etres humains) Chapitre I : Réalités

Etres fantastiques, un patrimoine des Alpes en cinq volumes

LA REPARTITION DES ETRES VIVANTS DANS UN MILIEU AQUATIQUE

Etres vivants

Etres un délégué ACF c’est

26 mars 2015 Voici quelques informations et clefs pour organiser au mieux votre délégations Etres un délégué ACF c’est

SCIENCES - Mon cartable du netmoncartabledunet.fr/Archive-fichiers/Sciences/relations-etres... · La chaîne alimentaire est le résultat des interactions entre trois catégories

Identi cation automatique des param etres rh eologiques par … · Pour la géométrie de type SII, l'écoulement dans la zone de striction est caractérisé par une distribution

DIVERSIFICATION GENETIQUE ET DIVERSIFICATION DES ETRES VIVANTS