Cours 1

Plan

Programme de l'enseignement de l'informatique
Equipement informatique de l'X
MacIntosh et PC versus Unix
Mon activité à l'INRIA
Les ctp des groupes 1 et 11
Pascal - C - Caml
Programmes sans boucles (straight-line)
Un peu de syntaxe
Sequencement élémentaire
Graphique
Exercices
Couleurs

Programme de l'enseignement de l'informatique

On apprend les mécanismes fondamentaux de la programmation

10 PC d'enseignement + intro TD (un HC = pc6)
10 TD de programmation
1 HC (13 novembre), 2h
1 CC (6 janvier), 4h, coeff 10
1 projet info (500--1000 lignes), coeff 8
2 délégués info par promo
1 délégué par PC

Equipement informatique de l'X

Vax 9000, Digital, 50 mips, poly
10 alphas, 75 mips
12 suns IPX, 20 mips, voitures
17 hp 9000, 60 mips, poissons
32 terminaux X
5 PowerMac,
2 Silicon Graphics,
1 machine passerelle vers l'Internet, sil
PB 190, avec ThinkPascal et ThinkC, et émulateur terminal
PC Toshiba, avec TurboPascal et TurboC++, et émulateur terminal
phonenet, 230 kbit/s
ethernet, 10 Mbit/s
1 imprimante LaserWriter par salle, 2 sur Vax

Mac ou PC

Traitement de texte
Développement de programmes
Jeux

Unix

Communication
Traitement de texte (TeX, etc)
Développement de programmes

Mon activité à l'INRIA

Operating systems
Sémantique et lambda-calcul
Vlsi (CAO)
Graphique Interactif
Sémantique et compilation sur machine parallèle
lambda-calcul et join-calcul
pdt Comité des projets
coordinateur de Confer 1 et 2

Les CTP des groupes 1 et 11

Pierre Weis, ctp, DR, INRIA,
implémenteur de Caml, livre sur Caml.
Cédric Fournet, vac, X-Ponts, MIT, Bull, Cambridge, INRIA
base de données, calcul distribué.
Georges Gonthier, (remplacement), ENS-Ulm, mdc, resp. PI, DR INRIA
Orsay, Sophia, Bell labs, INRIA; Esterel, lambda-calcul, calcul distribué.
Alexandre Frey (remplacement), X, Recherche, thèse avec Bourdoncle, ENSMP
analyse sémantique, sous-typage. (cf l'équipe enseignante)

Pascal ou C ou ML

C typé faiblement, conversions de type possibles
Pascal typé, types simples, pointeurs
C -> Unix
Portabilité
ML, fortement typé, fonctionnel, types généraux

Caml (INRIA) vient de ML (Milner, Edinbourg)

Date de Pâques

Lilius et Clavius en 16xx. (Knuth vol1, p.155)
Soit Y l'année, dont on cherche la date de Paques.
Supposons Y < 100000

[Golden number]
G = (Y mod 19) + 1
[Century]
C = Partie_Entière (Y/100) + 1
[Corrections]
X = Partie_Entière (3 C / 4) - 12,
Z = Partie_Entière ((8 C + 5) /25) -5
[Find Sunday]
D = Partie_Entière (5 Y / 4) - X -10
[Epact.]
E = (11 G + 20 + Z - X) mod 30.
Si E = 25 et G > 11, ou si E = 24, alors E := E + 1
[Find full moon]
N = 44 - E.
Si N < 21, alors N := N + 30
[Advance to Sunday]
N := N + 7 - ((D + N) mod 7)
[Get month]
Si N > 31, la date est (N - 31) AVRIL
Sinon, la date est N MARS.

Vérifier si ca marche pour 14250. Si pb lequel? (cf Knuth, vol 1)

Date de Pâques (en Pascal)

program Paques;
var
  G, C, X, Z, D, E, N: integer;
  date : array [1..8] of char;
begin
G := Y mod 19;
C := Y div 100 + 1;
X := 3*C div 4 - 12;
Z := (8*C+5) div 25 - 5;
D := 5*Y div 4 - X - 10;
E := (11 * G + 20 + Z - X) mod 30;
if ((E = 25) and (G > 11)) or (E = 24) then 
    E := E + 1;
N := 44 - E;
if N < 21 then
    N := N + 30;
N := N + 7 - (D+N) mod 7;

if N > 31 then
    date := "avril"
else
    date := "mars";

readln ('Année? :  ', Y);
writeln ('Paques', Y:5, ':  ', N:2, ' ', date);

end.

Date de Pâques (en Caml)

let paques () = 
  let y = read_int () in
  let g = (y mod 19) + 1 in
  let c = y /100 + 1 in
  let x = 3*c / 4 - 12 
  and z = (8*c+5) / 25 - 5 in
  let d = 5*y / 4 - x - 10 in
  let e = (11 * g + 20 + z - x) mod 30 in
  let e = if ((e = 25) & (g > 11)) or (e = 24) 
          then e + 1
          else e
  in
  let n =  44 - e in
  let n = if n < 21 
          then n + 30
          else n
  in
  let n = n + 7 - ((d+n) mod 7) in
  let (n, date) =
    if n <= 31 
    then (n, "mars") 
    else (n-31, "avril")
  in
  printf "%d %s %d\n" n date y
;;

Date de Pâques (en Caml)

let paques (y) = 
  let g = (y mod 19) + 1 in
  let c = y /100 + 1 in
  let x = 3*c / 4 - 12  and
      z = (8*c+5) / 25 - 5 in
  let d = 5*y / 4 - x - 10 in
  let e = (11 * g + 20 + z - x) mod 30 in
  let e = if ((e = 25) & (g > 11)) or (e = 24) 
          then e + 1
          else e
  in
  let n =  44 - e in
  let n = if n < 21 
          then n + 30
          else n
  in
  let n = n + 7 - ((d+n) mod 7) in
  if n <= 31 
    then (n, "mars") 
    else (n-31, "avril") 
;;

Vérifier modulo des nombres négatifs (par exemple paques (14250) peut donner le 42 avril. Ecrire un programme où on trouve la première année ou` se produit cette erreur (Knuth, vol1, p. 156)

Un peu de syntaxe

En ML, tout est des expressions. En Pascal, expressions et instructions sont différentes.

let x = e_1 in                 x: integer;
e_2                            x := e_1;
                               ... e_2 ...

let x = e_1 in                 x: integer;
let y = e_3 in                 y: integer;
e_2                            x := e_1; y := e_3;
                               ... e_2 ...

Et si x est utilisé dans e_2 ?? En ML, on a

let x = e_1 in                 let x = e_1 and
let y = e_3 in                     y = e_3 in
e_2                            ... e_2 ...

et un contro^le précis dans la portée des déclarations.

Autre notation (déclaration d'une paire, triplet, etc)

let (x,y) = (e_1, e_3) in   
e_2

Exemple: prendre le résultat de la paire paques(y) et l'imprimer.

Types élémentaires

Scalaires

Entiers int: -2^30 à 2^30 - 1
Booléens bool: true, false
Réels float: 2.3
Caractères char: `a`, `b`, etc. , `\n`, `\r`, etc
Attention: +. -. /. sont les opérations flottantes.

Unit unit: ()
Analogue de void de C,
type des expressions qui sont en fait des instructions.

Composite

Chaines de caractères string: "jolie chaine"
Tableaux int vect: [|1; 2; 3|]
Paires int * int: (1, 2)

Plus d'info en The core Caml Light language
http://pauillac.inria.fr/caml/man-caml/index.html

Fonctions

let f (x) = x + 1 in         function f(x, y: integer): integer;
e                               begin f := e end;

let f (x, y) = x + y in  
e

Même controle de portée que précédemment.

Fonctions int -> int: function (x) -> x+1
Fonctions int*int -> int: function (x,y) -> x+y
etc

Autres exemples

int_of_char est de type char -> int
char_of_int est de type int -> char
int_of_float est de type float -> int
float_of_int est de type int -> float

Attention, en Caml, les fonctions ont tendances à ne prendre qu'un argument curryfication.

let f (x) (y) = x + y in  
e

dont le type est int -> (int -> int). Et on supprime (pour le meilleur ou le pire) autant que possible de parenthèses.

let f x y = x + y in  
e

dont le type est

int -> int -> int}


Programme



Un programme est une suite de phrases (expressions ou définitions de
valeurs)

let f x = x + 1 ;;
let g x y = x + y ;;
let main () = printf "Hello tt le monde\n" ;; 


Le système répond en donnant les types et valeurs de chaque phrase.
On charge un fichier source (fait avec un éditeur de texte) par
l'instruction:

include "fichier.ml" ;;


S'il y a une erreur de syntaxe, on va à la ligne indiquée
par l'éditeur et on recommence.




Le programme doit commencer par la directive:

#open "printf" ;;


si on fait de l'impression formattée.


Un peu de controle dans le séquencement


begin e_1; e_2; ... e_n end;      idem

if e then e_1 else e_2            idem

match e with                      case e of
  | pat_1 -> e_1                    pat_1: e_1 ;
  ...                               ...
  | pat_n -> e_n                    pat_n: e_n;
                                   end;
try e with 
  | pat_1 -> e_1 
  ...
  | pat_n -> e_n

while e_1 do                      while e_1 do begin
  e_1; ...  e_n                         e_1; ...  e_n 
  done                                  end;

for i = e_1 to e_2 do             for i:=e_1 to e_n do begin
  e_1; ... e_n                          e_1; ...  e_n 
  done                                  end;



Pour sortir d'une boucle, on peut utiliser 

try 
   while true do
      ...
      raise Exit
      ...
   done
with
  Exit -> e_1





Bibliothèque graphique


value open_graph: string -> unit
value close_graph: unit -> unit
value clear_graph : unit -> unit
value size_x : unit -> int
value size_y : unit -> int
value rgb: int -> int -> int -> color
value set_color : color -> unit
value black : c
value magenta : color
value plot : int -> int -> unit

value point_color : int -> int -> color
value moveto : int -> int -> unit
value current_point : unit -> int * int
value lineto : int -> int -> unit
value draw_arc : int -> int -> int -> int -> int -> int -> unit
value draw_ellipse : int -> int -> int -> int -> unit
value draw_circle : int -> int -> int -> unit
value set_line_width : int -> unit

value draw_char : char -> unit
value draw_string : string -> unit
value set_font : string -> unit
value set_text_size : int -> unit

value text_size : string -> int * int
value fill_rect : int -> int -> int -> int -> unit



Au début du prograamme, on déclare l'utilisation de la librairie
graphique par la directive:

#open "graph" ;;




Exercices en TD




palette de couleurs (HSV ou RGB)
un pong avec raquette
faire la date de paques et répondre à Knuth






Demander en TD comment gérer les événements souris/clavier. Par
exemple

   let e = wait_next_event [Button_down; Key_pressed] in
     if e.keypressed then begin
        match e.key with

     end else
     if e.button then begin




Couleurs RGB / HSV


Il est plus simple de représenter les couleurs sur un disque
pris en coordonnées polaires h (hue), s
(saturation). Ce disque devient un cone si on fait intervenir
l'intensité lumineuse v. (cf 
http://cs.fit.edu/courses/cse4255/cse5255/davis/) 


On suppose h dans [0, 6], s dans [0,1], et v dans [0,1].


Les couleurs de l'arc-en-ciel correspondent à h.


Rouge h=0 ou h=6, Jaune h=1, Vert h=2, 

Cyan h=3, Bleu h=4, Magenta h=5.


Pour passer de HSV, couleurs de l'artiste, à RGB (Red Green Blue),
couleurs des écrans, on peut appliquer la transformation suivante
qui donne r, g, b dans [0,1].


i = Partie_Entière(h)

f = h - i 

Si i est pair, alors f := 1-f

m = v (1-s) 

n = v (1-sf)

Alors selon la valeur de i dans [0,6]
(r,g,b) = (v, n, m) si i=0 ou i=6 
          (n, v, m) si i=1 
          (m, v, n) si i=2 
          (m, n, v) si i=3 
          (n, m, v) si i=4 
          (v, m, n) si i=5 




Graphique en ThinkPascal




MoveTo (x, y),  Move (dx, dy)
LineTo (x, y), Line (dx, dy)
SetRect(r, g, h, d, b)
UnionRect(r1, r2, r)
FrameRect(r)
PaintRect(r)
EraseRect(r)
PenPat(pattern) avec white, black, gray, dkGray,ltGray 
PenMode(mode)  avec patCopy, patOr, patXor
PenSize(dx, dy)
Button
GetMouse (p), où p est le point (p.h, p.v)