Le langage SpecialK

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

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

• AlgosKounalis.zip: TPs et formules de cours de Kounalis tapés par Antoine Perroud

• grammaireK.ps: La grammaire du langage K

• grammaireK.tex: Le fichier source pour modifications