Introduction
Le langage Kappa est le langage utilisé par E. Kounalis pour son cours d'algorithmique de seconde année.
L'idée est de montrer dans ce sujet une formalisation possible du langage Kappa.
La seconde idée est de permettre de modifier la spécification si cela ne vous plaît pas...
Voir aussi:
TerRo1 -
DebatNommageK -
DrK
Définition(s)
Le langage Kappa est un langage de programmation fonctionnel, comprenant des élément de langage de
ProgrammationLogique, notamment l'unification.
A la manière d'un langage de
ProgrammationLogique, un programme en Kappa
est composé de clauses, pouvant commencer par des
guardes (des conditions
d'exécution d'une clause). Une fois les différentes guardes évaluées, on essaye d'exécuter les instructions suivant les guardes vraies.
Un contexte sert à initialiser des variables, tableaux ou listes.
Règles
- Un programme est composé de clauses.
- La guarde est unique pour chaque clause.
- La partie gauche d'une clause peut ou non contenir une guarde.
- Une guarde est composée d'une expression booléenne.
- La signification des gardes ne dépend pas de leur ordre. Une conséquence est que les gardes doivent être mutuellement exclusives. Une ambiguïté se traduira par une erreur de 'compilation'. Les guardes doivent être analysées syntaxiquement pour en sortir les éléments redondants, afin de ne les calculer qu'une seule fois.
- La partie gauche est optionnelle.
- La partie droite peut contenir un contexte.
Grammaire
(Pour l'instant ce n'est qu'une ébauche - non précise)
Il faut penser à ajouter la forme
T[i <-> j]
Donc,
a priori on supprime la partie sur les
when
.
Ensuite les listes s'écrivent sous la forme
'(1 2 3) <=> 1::2::3::nil
programme ::= clause programme
|
clause ::= partie_gauche = partie_droite.
| partie_droite.
partie_gauche ::= guarde fonction
| fonction
guarde ::= when expr_bool,
partie_droite ::= contextes fonction
| fonction | expression
contextes ::= contexte, contextes
| contexte
contexte ::= nom := expression
nom ::= variable | variable [expression] | variable . variable
fonction ::= variable(arguments)
arguments ::= argument, arguments
| argument
argument ::= fonction | contexte | expression | nom
Mots-clefs et ponctuation réservée
Mot | Utilisation |
when | annonce un contexte |
:= | affectation dans les contexte |
. | découper une liste/tableau en plusieurs éléments afin de les nommer |
[ et ] | accès style tableau |
, | séparation des affectations dans un contexte |
( et ) | appel de fonction avec passage d'arguments |
Types et structures de données
Le langage est, je crois, statiquement typé, vu que les variables ne sont affectées qu'une seule fois. Il faut voir si l'on va devoir exiger une cohérence dans les règles, notamment pour la valeur de retour...
Il faudrait peut-être préciser les opérations sur les nombres: réels, entiers, complexes, tests (
number?
,
exact?
...), etc.
Il y a 4 types:
- Les nombres (exemple:
a
, b
, machin
, pgcd
)
- Les symboles (exemple:
'a
, 'ok
, 'pas-ok
)
- Les tableaux (exemple:
<y, a, b, c>
, <r, g, d>
)
- Les listes (exemple:
a . b . C
, a . b . @
)
Les deux derniers types peuvent être manipulés de la même manière. Toutefois, à la déclaration (qui se situe dans les guardes), on peut spécifier si l'on veut utiliser l'un ou l'autre type de données, et ainsi utiliser ses caractéristiques (accès en temps constant, etc).
On pourra ainsi indifféremment accéder au troisième élément d'une
structure non scalaire (trouver un bon mot de vocabulaire... peut-être
composée), avec la syntaxe
t[3]
.
Une autre syntaxe existe pour la vision 'liste': E.Kounalis utilise la notation
x . L
, où
x
est le premier élément et
L
le reste. Il y a ambiguïté avec un
a . b
où
a
et
b
sont les deux seuls éléments d'une structure. On va force le programmeur à terminer la liste par le symbole fin de liste (notons le
@
pour moment.
()
ferait plus 'Scheme', mais fait des ambuguïtés, peut-être rattrapable au niveau typage, avec un appel de fonction.
%
pourrait aussi convenir) . Ainsi, le deuxième exemple s'écrit
a . b . @
.
Il est possible d'avoir une structure composite, c'est à dire contenant plusieurs éléments différents. Un arbre binaire
(vecteur 1, (vecteur 2, 3, 4), (vecteur 5, 6, 7))
s'écrirait donc sous la forme:
<1, <2, 3, 4> <5, 6, 7>>
ou même
'arbre . <1, <2, 3, 4> <5, 6, 7>>
(qui est une structure de listes & de tableaux).
On pourrait utiliser des chaînes de caractères à la place des symboles. Comme expliqué dans ETOS, cela pose des problèmes de performances, car un
eq?
suffit à comparer deux symboles, alors qu'il faut un
strcmp
en
O(n)
pour arriver au même résultat avec des chaînes de caractères.
Grammaire mise à jour
Une nouvelle version des ces fichiers est disponible.
J'ai ajouté en annexe un fichier .ps et le .tex contenant le grammaire du langage.
Je ne suis pas certain de l'associativité des opérateurs (il se peut que j'ai inversé gauche ou droite).
Ce document constitura une partie du document final (manuel du langage).
--
RodasCyril - 01 Mar 2004
Annexes
to top