C
C++
Alain Chillès – 祁冲 Ada
Python
Java
Théorie des langages de programmation
Pr
L
g
o
ep
l
o
ro
je
ParisTech Shanghai Jiao Tong 上海交大–巴黎高科卓越工程师学院
Pascal
18 octobre 2016 – 2016年10月18日 –丙申年九月十八
Lisp
APL
Fortran
t (V)
Forth
1
Plan
C
Projet
Compilation d’une fonction LAC Compilation d’une structure conditionnelle
C++ Lisp
Ada
Traitement des chaînes de car
Python Prolog
Java Forth
s Compilation d’une déclaration
actère
Pascal
APL
Fortran
2
Position du problème
Soit les fonctions définies par
LC
1 : incr 1 + ;
x x+1 x+2
Python
Java
Forth
AC
2
3 : 2+. incr incr . ;
C++
et
Ada
x+14 x+15 APL
Prolog
Elle vont être définies dans la table des symboles par
x+3
x+4
x+5
x+6
x+7
x+8
x+9
n2 t2 c Pascal
x + 10
?
4
105
110
99
114
1
1
11y
a
l
i
n
c
r
n1
t1
x+1 Lisp
x+11 x+12
x + 13
x + 16
x + 17
x + 18
x + 19
3
50
43
46
1
1
0
z
a
l
2
+
.
n1 t1 n2 c Fortran
3
Position du problème
C
et en machine virtuelle par
Python
Java
y P+ 3 c2
rolog
y
y+1
y+2
y+4 y+5
y+6
y+7
y+8
y+9
1
c1
1
c3 1
y
c1 est le Cfa de (lit)
ycc
Forth Ada
43
où
c2 estleCfade+ C++
c3 est le Cfa de (fin)
c4 estleCfade. On a donc
Lisp
z=y+5 APL
Pascal
Fortran
4
Plan
C
Projet
Python Prolog
Java Forth
Compilation d’une fonction LAC Compilation d’une structure conditionnelle
C++ Lisp
Ada
Pascal
Traitement des chaînes de car
s Compilation d’une déclaration
actère
APL
Fortran
5
Comment coder en machine virtuelle les … if… [else…] then
C
La syntaxe en LAC est
Python
Java
Prolog
ou
On rappelle que le type renvoyé doit être calculable !
< cond > if < sivrai > then
Dans le premier cas, < sivrai > et < sifaux > doivent avoir le C++
Ada
même type !
Dans le deuxième cas, < sivrai > doit ne rien renvoyer !
Il faut aussi être capable de gérer les conditions imbriquées, et ne pas se tromper sur le then et le else !
Lisp APL
< cond > if < cond′ > if < action1 > else < action2 > then…
Forth
Pascal
Fortran
6
Conditionnelle en machine virtuelle
Python
Java
Forth
Le codage en machine virtuelle est facile
LC
1
AC Prolog … 0= if 1 else 2 then …
x
x+1
x+2
x+3
Ada
x+4 x+5 x+6
x+7
x+8
x+6
c3
1cx+8
4
c3
2
…c1 c2 … C++
où
c1 est le Cfa de 0=
c2 est le Cfa de if APL c3 est le Cfa de (lit)
Lisp
Pascal Fortran
c4 est le Cfa de else
7
Conditionnelle dans la table des symboles
Clairement, les types sont
C++
Lisp
APL
sont pas bien organ
piles).
Fortran
Python
Java
Il faut signifier que if, else et then ne sont utilisables que C
pendant la compilation !
Prolog
if else then
(b −−)
( −− )
( −− ) Ada
Forth
Notons que then n’est même pas codé dans la machine virtuelle ! (Si cela vous manque, vous pouvez toujours créer
une fonction qui ne fait rien !)
Il doit y avoir une erreur sémantique, si les if, else et then ne
isés e
ntre
eux (on vide alors toutes les
Pascal
8
Plan
C
Projet
Python Prolog
Java Forth
Compilation d’une fonction LAC Compilation d’une structure conditionnelle
C++
Compilation d’une déclaration
Traitement des chaînes de car
Lisp
APL
Fortran
Ada
actère
s
Pascal
9
Les chaînes de caractères
C
Python Prolog
Java Forth
À la compilation
LAC
1 : essai ( — ) ” Bonjour” count type ;
C++
Ada
Pascal
À l’exécution
LAC
1 ” Bonjour” count type
Lisp
APL
Fortran
10
Utilisation des chaînes en mode compilé
Python
C
où
Java
Pas
de problème, cela donne en machine virtuelle
x+4 x+5 x+6 x+7 Prolog
114 c2 c3 c4 Forth
x
x+1
x+2
x+3
x+8
x+9
x + 10
x + 11
x + 12
1
c1
6
66
111
110
106
111
117
x est le Cfa de essai
C++
chaîne de caractères
c2 est le Cfa de count
c3 est le Cfa de type
c1 est le Cfa d’une fonction (
c4 est le Cfa de (fin)
Lisp
Ada
Pascal
APL
Fortran
str) q
ui
indique qu’arrive une
11
Utilisation des chaînes en mode interprété
C
Python Prolog
Java Forth
Où mettre la chaîne tant que l’on en a besoin ?
Comment mettre les chaînes sans qu’elles se superposent ?
LAC C++
Ada
1 ” Bonjour” ” Alain !” catenate
Pascal
APL
Fortran
Lisp
12
Plan
C
Projet
Python Prolog
Java Forth
Compilation d’une fonction LAC Compilation d’une structure conditionnelle
C++
Compilation d’une déclaration
Traitement des chaînes de car
Lisp
APL
Fortran
Ada
actère
s
Pascal
13
Déclaration (non demandé, mais intéressant)
Python
LAC
Java Forth
Ada
C
1 2 3 4
defer u \ Déclaration de u Prolog
: v ( n — v[n])
dup 0= if drop 1 else dup 1- u 2 * swap 1-
→ recurse – then ;
(u) ( n — u[n]) C++
5 6
7
8
:
dup 0= → then;
if drop 1 else dup 1- u swap 1- v + Pascal
’ (u) is u Lisp
APL
9 10
\ Résolution de la déclaration
1
14
u
.
Fortran
14
Problèmes posés
Python
achine virtuelle ? Aucun ! C
où
Java
Forth
En m
x x+1 x+2 Prolog
1
c1
c2
x estleCfadeu C++
Ada
c1 est le Cfa d’une fonction d’erreur qui dit que la fonction n’est pas définie (et vide les piles !)
c2 est le Cfa de la fonction (fin)
À la résolution de la déclaration, on remplace tout simplement c1
par le Cfa de la fonction (u)
Lisp
APL
Fortran
Pascal
15
Compléments
Python
Java
C
Les fonctions ’ et is ne fonctionnent qu’en mode interprété. Elles sont définies de la manière suivante :
Prolog
exécutée), elle est donc du type
( − − ad ) Ada
est donc du type
Forth
’ trouve le Cfa de la fonction qui suit (et qui n’est donc pas
C++
′
is trouve le Cfa de la fonction qui suit (et qui n’est donc pas exécutée) et remplace c1 par l’adresse qui est sur la pile. Elle
Lisp
is (ad−−) APL
Fortran
Pascal
16
Problèmes posés Python En table des symboles ? Beaucoup !
Java
Comment déterminer le type de u ? C
Comment en déduire les types de v et (u) ?
reconnaissance de types.
Forth
Remarque
Prolog
on est ramené à résoudre une système d’équations lors de la
C++
L
APL
s nombres et types de paramètres en entrée et en sortie.
Ada
Dans l’exemple donné, la séquence dup 0= if drop 1 else permet de dire que v nécessite au moins un paramètre de type
entier, et renvoie sur le haut de la pile au moins un objet de
type entier.
Pascal
La séquence u 2 * permet de dire que u renvoie au moins un paramètre de type entier (sur le haut de la pile).
i
s
p
La séquence ’ (u) is u permet de dire que u et (u) ont les
m
etc.
êm
e
Fortran
17
Résolution du système
Python
Java
m1 + 1 m1 + 1
Au départ, on a n entrées pour u et (u) et n sorties, et m 121
entrées pour v et m2 sorties. Calculons d’abord m1, m2, n1 et n2. C
Prolog
Instruction
Nombre de paramètres
m1 ≥ 1 Forth
Déduction
dup 0= if drop
entier
C++
m1 − 1
m1 Ada
m1 m2 =m1 etentier
Pascal
1
On peut en déduire que (pour v)
m1 ≥ 1, et le premier paramètre (haut de la pile) est de type
APL
Fortran
entier ;
m2 = m1, et le premier paramètre (haut de la pile) est de type
Lisp
entier.
18
Résolution du système (suite)
C
else dup 1-
u
2 * swap 1- recurse
Python
Java
Nombre de paramètres
Déduction
m1 Prolog
m1 + 1 m1+1−n1+n2 m1−n1+n2
n1 ≤m1+1etentier Forth
m1−n1+n2 ≥0etentier m m−n+n=m,n≥n
Ada
2 112121
etm =−n +n +m
2122
Instruction
C++
On peut en déduire que
n1 = n2 et n1 ≤ m1 + 1 ;
Pascal
le premier paramètre d’entrée de u est de type entier ;
Lisp
APL
le premier paramètre de sortie de u est de type entier ;
par symétrie (même travail sur (u)), on obtient m1 ≤ n1 + 1.
Ce n’est pas suffisant !
Fortran
19
Solution ?
Python
Java
C
Prendrelasolutionminimale(icim =m =n =n =1);
1212
changer la déclaration, en donnant n1 et n2 (ce qui permet de
Prolog
Forth Ada
garder la place dans la table des symboles et de remplir les
types au fur et à mesure des utilisations).
C++
LAC
1 \ n1 n2 defer
2
3 1 1 defer u
APL
Fortran
Ce problème ne se pose pas en cas de non typage dynamique des
Lisp
fonctions !
Pascal
20