fouine — Syntaxe du langage

Cœur du langage fouine.
• expressions arithmétiques : constantes entières (y compris négatives), somme, soustraction, multiplication ;

• parenthèses ouvrantes et fermantes, construction begin.. end. Les sauts à la ligne sont possibles.

• construction let .. in
Deux exemples : let a = 3 in 2*a + a*a   et     let f x = x*x in f (f 3).

• identificateurs de variables : ils commencent par une lettre minuscule ; après, n’importe quoi en termes de chiffres et de lettres (majuscules ou minuscules) ; let oO0Oo = 0 marche, par exemple ;

• fonctions : on peut déclarer une fonction avec let f x z = .. ou avec let f = fun x -> fun z -> .. (ou un mélange des deux approches) ; on autorisera aussi fun a b c -> ...
On peut appliquer les fonctions comme dans f s t.
On peut utiliser une fonction directement sans la nommer (« fonctions anonymes ») let x = (fun x -> x) a in ...

la fonction fonction prInt. On ajoute une construction spéciale au langage, pour pouvoir faire de l’affichage et ainsi voir ce que font les programmes. Cette construction s’appelle prInt, c’est une fonction qui affiche son argument entier, va à la ligne, et renvoie pour valeur ce même argument.
Voici un petit exemple :

# 2 + prInt (1+2);;
3
- : int = 5

En Caml (mais pas en fouine), on peut définir prInt comme suit :

# let prInt x = print_int x;print_newline(); x;;
val prInt : int -> int =

On se restreindra à des usages simples de prInt ; en particulier, on ne passera pas la fonction prInt à une fonction.

NB : fouine n’est pas IMP, le petit langage vu en théorie de la programmation (pour ceux qui ont suivi ce cours) : il ne fait pas sens de séparer les expressions arithmétiques et les commandes, car « tout est expression » en fouine.

Analyse syntaxique, priorités etc. Le comportement de Caml sert de référence. La principale difficulté est le traitement des applications lorsqu’une fonction est appliquée successivement à plusieurs arguments.

Vous n’avez en particulier pas le droit d’imposer à l’utilisateur d’ajouter davantage de parenthèses que ce qui est demandé en Caml.

Voici quelques exemples illustratifs :

# let add x y = x+y;;
val add : int -> int -> int =
# 3 + add 2 3;;
- : int = 8
# let k = 3 + (fun x -> x + 1) 5;;
val k : int = 9
# let k = 3 + fun x -> x + 1 5;;
Characters 12-28:
let k = 3 + fun x -> x + 1 5;;
^^^^^^^^^^^^^^^^
Error: This expression should not be a function, the expected type is int

Syntaxe, au-delà du cœur.

if then else, uniquement avec des tests entre entiers ;
opérateurs à prendre en compte : > >= < <= = <> pour comparer des entiers,  not && || entre booléens
NB2 : en fouine, tout est expression, et 27 est une expression au même titre que (fun x -> 1+2*x) 9.
NB3 : if then else, mais pas de if then tout court.

• La construction let.. in : formes dérivées

–  ne pas nommer : vous devez autoriser l’utilisation du caractère « souligné » tout seul, dans des expressions de la forme let _ = ... in

Cette utilisation sert à ne pas nommer une expression que l’on évalue (on l’utilise généralement lorsqu’on fait des effets de bord — affichage à l’écran, écriture dans un fichier, mise à jour de référence ..).

NB : dans le type des expressions de votre interprète, il faut avoir une seule construction pour let.. in.

  – let.. in « en surface » : un programme est de la forme let x1 = e1 in let x2 = e2 in … let xn = en in e. Les déclarations des xi sont dites « en surface ». Un let.. in qui se trouve dans l’un des ei n’est pas en surface.

L’écriture ci-dessus suppose que e n’est pas à son tour un let.. in (sinon on aurait pu « développer » davantage). Dans ce cas, tout let.. in que contient e n’est pas non plus en surface.

Pour les let.. in « en surface » uniquement, on peut remplacer un in « in » par « ;; » (le double point virgule).

[ version « rendu 3 » : vous pouvez regarder, ou ignorer jusqu’au rendu 3

si l’utilisateur saisit une expression de la forme
let x = e1 in e2
il a le droit de l’ecrire
let x = e1;;
e2
et **dans ce cas**, le remplacement peut egalement etre fait, recursivement, dans e2. ]

• construction let rec (en deux mots), pour définir des fonctions récursives (pas de message d’erreur si la fonction n’est pas récursive). On ne s’intéressera qu’à des définitions récursives de fonctions. Les diverses écritures pour les fonctions seront acceptées (let rec f = fun x ->, et aussi let rec f x y z = .., ou encore let rec f = fun x y z -> ..)

 

Exécution des programmes fouine.

• Dans la version « de base », un programme fouine peut renvoyer un entier, une fonction ou un booléen.

En l’absence d’utilisation de prInt, un programme ne fait rien de visible (tout comme en Caml, à partir du moment où l’on n’utilise pas l’interprète mais le compilateur).

• Plutôt que de décrire formellement la sémantique opérationnelle de fouine, on adopte l’approche “lancez le programme avec Caml, cela vous donnera le comportement attendu”. Vous pouvez interagir avec les encadrants si vous avez des doutes sur un point précis.

Pour lancer le programme avec Caml, vous devrez insérer la définition let prInt x = print_int x; print_newline(); x au début.

Typiquement, de petits programmes comme let a = prInt 5 in a + prInt 7 ou let f x y = x*y in f (prInt 3) (2+prInt 2) vous permettront de vérifier que vous implémentez les choses comme il faut.

Affichage d’un programme fouine

Vous devez programmer une fonction qui affiche un programme fouine. Afficher le programme saisi en entrée ne donne pas nécessairement le même programme, car il se peut que des transformations élémentaires soient appliquées au passage (par exemple, let f x =.. remplacé par let f = fun x -> ..). Il faudra toutefois que le programme affiché soit accepté par Caml, en supposant que l’on ait défini la fonction prInt comme ci-dessus.

Les erreurs que ne connaı̂t pas Caml.
En Caml, un programme est typé, ce qui permet d’éviter d’exécuter des programmes absurdes comme 3 + (fun x -> x+1). Pas de typage en fouine, par conséquent certains programmes exploseront lors de l’exécution.

Réfléchissez à la gestion de ces erreurs (appelées dynamiques), et proposez une solution satisfaisante. Cela peut aller de messages d’erreur un peu explicatifs dans certains cas (quand une addition fait intervenir une fonction, par exemple) à des choses plus sophistiquées, où l’on indique d’où vient l’erreur
dans le code source.