Une variante Lisp complète, typée statiquement, est-elle possible?

Une variante Lisp complète, typée statiquement, est-elle possible? Est-il même logique que quelque chose comme ça existe? Je crois que l’une des vertus d’un langage Lisp est la simplicité de sa définition. Le typage statique compromettrait-il ce principe fondamental?

Oui, c’est très possible, bien qu’un système de type HM standard soit généralement le mauvais choix pour la plupart des codes Lisp / Scheme idiomatiques. Voir Typed Racket pour un langage récent qui est un “Full Lisp” (plus similaire à Scheme, en fait) avec un typage statique.

Si tout ce que vous vouliez, c’était un langage de type statique ressemblant à Lisp, vous pourriez le faire assez facilement, en définissant un arbre de syntaxe abstrait qui représente votre langue, puis en mappant cet AST aux expressions S. Cependant, je ne pense pas que j’appellerais le résultat Lisp.

Si vous voulez quelque chose qui a des caractéristiques Lisp-y en plus de la syntaxe, il est possible de le faire avec un langage typé statiquement. Cependant, il existe de nombreuses caractéristiques de Lisp qui sont difficiles à obtenir. Pour illustrer cela, jetons un coup d’oeil à la structure de la liste elle-même, appelée les inconvénients , qui forme le bloc de construction principal de Lisp.

Faire appel à une liste, bien que (1 2 3) ressemble à une liste, est un peu trompeur. Par exemple, ce n’est pas du tout comparable à une liste typée statiquement, comme la std::list ou Haskell de C ++. Ce sont des listes chaînées à une dimension où toutes les cellules sont du même type. Lisp permet heureusement (1 "abc" #\d 'foo) . De plus, même si vous étendez vos listes de types statiques à des listes de listes, le type de ces objects nécessite que chaque élément de la liste soit une sous-liste. Comment représenteriez-vous ((1 2) 3 4) en eux?

Les consp Lisp forment un arbre binary, avec des feuilles (atomes) et des twigs (conses). De plus, les feuilles d’un tel arbre peuvent contenir n’importe quel type de Lisp atomique (non contre)! La flexibilité de cette structure est ce qui rend Lisp si efficace pour gérer le calcul symbolique, les AST et la transformation du code Lisp lui-même!

Alors, comment modéliser une telle structure dans un langage typé statiquement? Essayons-le dans Haskell, qui possède un système de type statique extrêmement puissant et précis:

 type Symbol = Ssortingng data Atom = ASymbol Symbol | AInt Int | ASsortingng Ssortingng | Nil data Cons = CCons Cons Cons | CAtom Atom 

Votre premier problème sera la scope du type Atom. De toute évidence, nous n’avons pas choisi un type Atom suffisamment flexible pour couvrir tous les types d’objects que nous souhaitons explorer. Au lieu d’essayer d’étendre la structure de données Atom comme indiqué ci-dessus (ce que vous pouvez clairement voir est fragile), supposons que nous ayons une classe de type magique Atomic qui distingue tous les types que nous voulions créer atomiquement. Ensuite, nous pourrions essayer:

 class Atomic a where ????? data Atomic a => Cons a = CCons Cons Cons | CAtom a 

Mais cela ne fonctionnera pas car cela nécessite que tous les atomes de l’arbre soient du même type. Nous voulons qu’ils puissent différer d’une feuille à l’autre. Une meilleure approche nécessite l’utilisation des quantificateurs existentiels de Haskell:

 class Atomic a where ????? data Cons = CCons Cons Cons | forall a. Atomic a => CAtom a 

Mais maintenant, vous arrivez au cœur du problème. Que pouvez-vous faire avec des atomes dans ce type de structure? Quelle structure ont-ils en commun avec Atomic a ? Quel est le niveau de sécurité garanti avec un tel type? Notez que nous n’avons ajouté aucune fonction à notre classe de type, et il y a une bonne raison: les atomes ne partagent rien en commun dans Lisp. Leur supertype en Lisp est simplement appelé t (ie top).

Pour les utiliser, il vous faudrait des mécanismes pour forcer dynamicment la valeur d’un atome à quelque chose que vous pouvez réellement utiliser. Et à ce stade, vous avez essentiellement implémenté un sous-système typé dynamicment dans votre langage typé statiquement! (On ne peut s’empêcher de noter un corollaire possible de la dixième règle de programmation de Greenspun .)

Notez que Haskell prend en charge un tel sous-système dynamic avec un type Obj , utilisé en conjonction avec une classe Dynamic et une classe Typeable pour remplacer notre classe Atomic , qui permet de stocker des valeurs arbitraires avec leurs types et de les forcer à les types. C’est le genre de système que vous devez utiliser pour travailler avec des structures Lisp dans leur intégralité.

Ce que vous pouvez également faire, c’est aller dans l’autre sens et intégrer un sous-système de type statique dans un langage essentiellement dynamic. Cela vous permet de bénéficier d’une vérification de type statique pour les parties de votre programme qui peuvent tirer parti d’exigences de type plus ssortingctes. Cela semble être l’approche adoptée, par exemple, dans la forme limitée de vérification de type précise de CMUCL.

Enfin, il y a la possibilité d’avoir deux sous-systèmes distincts, typés dynamicment et statiquement, qui utilisent une programmation de type contrat pour faciliter la transition entre les deux. De cette façon, le langage peut prendre en charge les utilisations de Lisp où la vérification de type statique serait plus une entrave qu’une aide, ainsi que des utilisations où la vérification de type statique serait avantageuse. C’est l’approche adoptée par Typed Racket , comme vous pourrez le voir dans les commentaires qui suivent.

Ma réponse, sans grande confiance, est probablement . Si vous regardez un langage comme SML, par exemple, et comparez-le avec Lisp, le kernel fonctionnel de chacun est presque identique. En conséquence, il ne semble pas que vous ayez beaucoup de mal à appliquer une sorte de saisie statique au cœur de Lisp (application de fonction et valeurs primitives).

Votre question dit cependant que l’approche basée sur le code en tant que données est un problème. Les types existent à un niveau plus abstrait que les expressions. Lisp n’a pas cette distinction – tout est “plat” dans la structure. Si nous considérons une expression E: T (où T est une représentation de son type), et que nous considérons cette expression comme étant une simple donnée, alors quel est exactement le type de T ici? Eh bien, c’est gentil! Un type est un type d’ordre supérieur, alors allons-y et disons quelque chose à ce sujet dans notre code:

 E : T :: K 

Vous pourriez voir où je vais avec cela. Je suis sûr qu’en séparant les informations de type du code, il serait possible d’éviter ce type d’auto-référentialité des types, mais cela rendrait les types peu “lisp” dans leur saveur. Il y a probablement plusieurs façons de contourner cela, même si ce n’est pas évident pour moi, ce serait la meilleure.

EDIT: Oh, alors avec un peu de googler, j’ai trouvé Qi , qui semble être très similaire à Lisp sauf qu’il est typé statiquement. Peut-être que c’est un bon sharepoint départ pour voir où ils ont apporté des modifications pour obtenir la saisie statique.