Cours 1 : Introduction aux langages de programmation, Représentation des entiers

Jean Goubault-Larrecq / Juliusz Chroboczek

Introduction aux Langages de Programmation

NB:

Th de la courbe de Jordan : si $𝛤$ est une courbe fermée injective : il y a deux composantes connexes dans le plan : une bornée, l’autre pas bornée. (très difficile à cause des courbes de Peano)

Pb de la mouche : une ligne de chemin de fer fait 125km de long, deux trains vont se croiser depuis des points A et B.

cf John Baez

Styles de langages :

  • Impératifs : C, etc…
  • Fonctionnels : CamL, Haskell, etc…
  • Orienté Objet Attention : ce ne sont que des styles : on peut faire du fonctionnel dans la plupart des langages impératifs, et vice versa (C, CamL, Python)

Ex:

int fact(int n)
{
  int i, r;
  for(i=1; i <= n; i++) r *= i;
  return r;
}

let rec facto n = match n with
0 -> 1
|_ -> n * facto (n-1);;

NB:

  • C++ : à la base, langage POO de C; mais mnt : indépendant
  • OCamL <- Objective C, autre langage POO à partir de C

Ligne de commande : cat : commande pour concaténer un fichier (en pratique, affiche le contenu).

Ex :

cat "Contenu fichier 1" > fichier1 cat "Contenu fichier 2" > fichier2

cat fichier1 fichier2

cat fichier1 fichier2 > fichier3

which commande

Ex : which cat

Pq s’affiche comme ça ? Fichier est plein d’octets : ∃ un mécanisme qui lit les octets et les décode avec une table bas niveau (manipule les registres)

Compilation en C : gcc

Ex :

gcc cat.c -o mycat

Fichier mycat dont le contenu est incompréhensible pour nous mais pas pour la machine

ls -al : liste les fichiers avec permissions

Ex:

  • -rwx read, write, execute

Il y a un langage intermédiaire entre le C et le langage binaire :

gcc -S cat.c

⟹ fichier cat.s modifié dans le répertoire courant : il décrit ce que doit faire le programme binaire en assembleur.

TDs

EX1

a)

  • Fortran IV (ou 1966) (Formula Translator)
  • Impératif
  • Affiche “Hello World”
PROGRAM HELLO
WRITE(6,1)
FORMAT 12HELLO, WORLD
STOP
END
  • WRITE(6,1) : écris dans le sdtout numéro 6 ce qu’il y a à la ligne 1
  • 12H : 12 caractères (H comme le nom de l’inventeur, ayant fondé l’ancêtre d’IBM)
  • STOP : arrête-toi
  • END : programme se termine
  • Particularité : parallélisation améliorée, développé chez IBM

b)

  • Fortran IV (ou 1966) (Formula Translator) (créé en 1954)
  • Impératif

  • Calcule $10!$

  • FORMAT I8 : I = entier, 8 = sur 8 caractères

  • CONTINUE : opération vide (pass en python) : ne rien faire

  • DO 1 I=1,10 boucle pour I allant de 1 à 10 les instructions qu’il y a dans la ligne suivant jusqu’à la ligne 1.
  • ` ` : 7 espaces introductifs où sont les instructions normales, à moins qu’il y ait un label (numéro introductif)
  • 72 caractères par ligne : taille d’une ligne dans la carte perforée où étaient inscrits les caractères.

c)

  • Langage : COBOL (1957)
  • Pour l’informatique de gestion (affichage de formulaire, impression, etc…)

d)

  • BASIC (1970)
  • Idée de base : un FORTRAN mais plus simple (inventé par des statisticiens de la côte Ouest des USA)
  • Microsoft : au début = toute petite boîte (1976) : font un interprète BASIC pour ces machines ⟹ font fortune car Apple, etc… l’utilisaient.
  • Toutes les lignes sont numérotées
  • PAS le Visual Basic ++ de Microsoft

e)

  • Langage : Common LISP (1960), créé par le mathématicien McCarthy
  • Langage pas typé
  • i 1 (+ i 1) : pour i partant de 1, dont la nouvelle valeur sera i+1 (après l’instruction parallèle sur j)
  • (>= i n) j si i >= n, retourner j
  • concurrent : Lanage Scheme (LE langage fonctionnel de référence pour l’éducation en USA du Nd)
  • Il y a tout les styles possibles : impératif, fonctionnel, …
  • Raison du succès : trop de langages différents ⟹ appel d’offre international des USA (entreprise) pour uniformiser tout ⟹ ADA perce (par un fr). MAIS : plein de gens n’aime pas l’ADA : utilise le concurrent Common LISP à la place (notamment pour l’IA).

f)

  • Langage : Scheme (1973-80)
  • Introduction de la portée lexicale (le premier à la faire) : langage lexical = un langage dans lequel on a un espoir de comprendre ce qu’on a écrit.
  • Labo d’idées étranges : primitives délirantes faites en Scheme. Son inventeur compile le langage dans le “style de continuation” : primitive extrêmement efficace (appelée ‘call with current continuation’ : permet de faire énormément de trucs (revenir en arrière (avant qu’un bug se déclenche, etc…) : rend possible le voyage dans le passé, dans un programme : fait une copie de toute la pile et tous les registres, et la passe en argument à la fonction appelée, qui peut donc revenir dans un état antérieur))

g)

  • Calcule factorielle 10
  • APL (A Programming Language): Langage vieux créé par Ken Iverson (1960)
  • Langage concis : plus illisible que Perl
  • Écrit avec un clavier spécial et une fonte spéciale
  • Langage J : version “démocratisée d’APL” (les caractère spéciaux peuvent être tapés avec un clavier normal (ex: “iota”))
  • Travaille sur des vecteurs et des matrices
  • $𝜄10$ : vecteur des entiers de 1 à 10
  • ’/’ : insertion de l’opérateur dans le vecteur

h)

  • Python

i)

  • Pascal
  • Assez proche de C
  • ’:=’ affectation
  • Son créateur : un professeur Suisse-Allemand (Wierth)
  • A deux conventions d’appel de fonctions : par valeur et par référence
  • Pour l’enseignement des languages des langages de programmation. À l’époque : tout le monde programmait en FORTRAN. Mais bcp de GOTO ⟹ Djikstra : écrit article "GOTO is harmful" : promeut les boucles while`

j)

  • C

k)

  • Haskell (1990) (open source): successeur du langage de Miranda (commercial : sans succès)
  • Langage fonctionnel
  • VS CamL : c’est un langage paresseux (par nécessité) (PAS en appel par valeur (comme Python, …)).

i.e (évaluation paresseuse): facto(3+1), ne calcule pas d’abord 3+1. Rentre dans factoriel, puis teste 3+1 à la place de n.

⟹ si f est une fonction qui a un argument, mais qui ne l’utilise pas : argument PAS appelé, même si ne termine pas

Ex: f(programme) = return 3;;

En Haskell : f(function while True) termine !

VS évaluation par valeurs (PAS paresseuse): plus rapide, car on n’alloue pas de la mémoire pour l’argument qu’on n’a pas encore exécuté (+ : il y a un ‘flag’ pour dire si on a déjà exécuté ou non l’argument (puis, si on le fait : on stocke la valeur dans espace réservé à côté du ‘flag’))

Évaluation paresseuse : permet de faire des beaux programmes.

Nbs de Hamming : nbs qui n’ont comme facteurs premiers que 3, 5, et 7.

Programme : retourner (énumérer, à chaque fois qu’on tape ‘return’) tous les nbs de Hamming dans l’ordre.

En Haskell (paresseux) : on crée des listes l3, l5, l7 des listes d’entiers.

l3 = 1 : map(3*l3)

on fait pareil pour l5, l7 : puis on ‘fusionne’ les trois listes infinies (on compare les têtes, et on prend la plus petite des trois).

Ex2: Programme qui prend des formules du premier ordre, et cherche des modèles finis (de cardinal $n$). Programme le plus efficace qui existe : écrit en Haskell

l)

  • CamL

m)

  • Standard ML : langage créé en labo au New Jersey

n)

  • Prolog
  • Ni fonctionnel, ni impératif, ni POO : langage logique
  • Langage qui backtrack naturellement : sait chercher et rebrousser chemin
  • Calcule la factorielle
  • fact(N,M) prédicat à deux paramètres : comment vérifier que M est la factorielle de N
  • N et M sont en relation ssi …
  • Dans les premiers Prolog : pas d’affection avec = : avant : 2+y=5 ⟶ réponse : YES. y = 3

o)

  • Bash : successeur du Shell
  • Jeu de mot avec “Born again Christian”, avec Shell
  • De plus : Bash veut dire “critiquer acerbement quelqu’un à propos de qch”

p)

  • FORTH : langage créé pour un observatoire, langage de quatrième génération
  • Calcule la factorielle
  • : : une fonction
  • Langage qui marche avec une pile, où on empile les arguments
  • Fonctionnel, en notation polonaise inverse (sauf pour le if)

q)

  • PostScript
  • Langage énormément utilisé : pour les imprimantes
  • Mais : un vrai langage
  • Pdf : c’est du PostScript en binaire compressé.

r)

  • Ada : du nom de Lady Ada Lovelace : première programmeuse au monde (calculabilité)
  • Langage qui vérifie tout le temps des types : type Positive ⟶ attention quand on fait -1 (déclenche exceptions)
  • Raison du crash de Ariane 5 : écrit en ADA. Le programme d’Ariane 4 avait été récupéré, code qui faisait des statistiques (pression, etc…) inutiles : ce code a été laissé en place, parce qu’on ne sait pas ce qui se passe si on touche. Pb : la fusée va plus vite qu’Ariane 4. Mais accélération horizontale dépasse la borne ⟶ valeur de l’exception pas gérée ⟹ -1 codé comme 4 000 000 000 ⟶ tourne que 4 000 000 000 de degrés au lieu de -1 degré.

Représentation des entiers

  • Nombres en base 2
  • Représentation alternative : coefficients : -1, 0 ou 1 ⟹ addition se fait en hardware en tps cst, contrairement au binaire
  • Processeur calcule sur 32 ou 64 bits (représentation sur une taille fixe)

Sur 32 bits : entiers non signés : de $0$ à $2^{32}-1$

⟹ on calcule modulo $2^{32}$

Sur 8 bits : de 0 à 255

Pour les entiers signés (relatifs) :

  • de -128 à 127

Sur 32 bits signés :

  • de $-2^{31}$ à $2^{31}-1$

⟹ En non signé :

2^7 = 128 = 1 000 000 0

127 = 0 111 111 1

signé :

-128 = 1 000 0000

-127 = 1 000 0001

⋯

-1 = 1 111 1111

0 = 0 000 0000

1 = 0 000 0001

⋯

+127 = 0 111 1111

⟹ en complément à 2 :

  • on tourne : 127+1 ⟶ -128
  • le premier bit = bit de signe

Leave a comment