Ecrire un interprète Haskell en Haskell

Un exercice de programmation classique consiste à écrire un interpréteur Lisp / Scheme en Lisp / Scheme. La puissance de la langue complète peut être mise à profit pour produire un interprète pour un sous-ensemble de la langue.

Existe-t-il un exercice similaire pour Haskell? Je voudrais implémenter un sous-ensemble de Haskell en utilisant Haskell comme moteur. Bien sûr, cela peut être fait, mais existe-t-il des ressources en ligne à consulter?

J'explore l'idée d'utiliser Haskell comme langage pour explorer certains des concepts d'un cours sur les structures discrètes que j'enseigne . Pour ce semestre, j'ai opté pour Miranda , une langue plus petite qui a inspiré Haskell. Miranda fait environ 90% de ce que j'aimerais qu'elle fasse, mais Haskell fait environ 2000%. :)

Mon idée est donc de créer un langage qui a exactement les fonctionnalités de Haskell que j'aimerais et qui interdit tout le reste. Au fur et à mesure que les élèves progressent, je peux "activer" de manière sélective diverses fonctionnalités une fois qu'ils maîtrisent les bases.

Des «niveaux de langage» pédagogiques ont été utilisés avec succès pour enseigner Java et Scheme . En limitant ce qu'ils peuvent faire, vous pouvez les empêcher de se tirer une balle dans le pied alors qu'ils maîtrisent encore la syntaxe et les concepts que vous essayez d'enseigner. Et vous pouvez offrir de meilleurs messages d'erreur.

J'adore votre objectif, mais c'est un gros travail. Quelques indices:

• J'ai travaillé sur GHC, et vous ne voulez aucune partie des sources. Hugs est une implémentation beaucoup plus simple et plus propre, mais malheureusement, elle est en C.

• C'est une petite pièce du puzzle, mais Mark Jones a écrit un beau document appelé Typing Haskell in Haskell qui serait un excellent point de départ pour votre frontal.

Bonne chance! Identifier les niveaux de langue pour Haskell, avec des preuves à l'appui de la classe, serait d'un grand avantage pour la communauté et certainement un résultat publiable!

Il existe un analyseur Haskell complet: http://hackage.haskell.org/package/haskell-src-exts

Une fois que vous l'avez analysé, supprimer ou interdire certaines choses est facile. J'ai fait cela pour tryhaskell.org pour interdire les déclarations d'importation, pour prendre en charge les définitions de niveau supérieur, etc.

Analysez simplement le module:

parseModule :: String -> ParseResult Module

Ensuite, vous avez un AST pour un module:

Module SrcLoc ModuleName [ModulePragma] (Maybe WarningText) (Maybe [ExportSpec]) [ImportDecl] [Decl]    

Le type Decl est étendu: http://hackage.haskell.org/packages/archive/haskell-src-exts/1.9.0/doc/html/Language-Haskell-Exts-Syntax.html#t%3ADecl

Tout ce que vous avez à faire est de définir une liste blanche - des déclarations, importations, symboles, syntaxe disponibles, puis suivez l'AST et lancez une "erreur d'analyse" sur tout ce dont vous ne voulez pas qu'ils soient encore au courant. Vous pouvez utiliser la valeur SrcLoc attachée à chaque nœud dans l'AST:

data SrcLoc = SrcLoc
     { srcFilename :: String
     , srcLine :: Int
     , srcColumn :: Int
     }

Il n'est pas nécessaire de réimplémenter Haskell. Si vous souhaitez fournir des erreurs de compilation plus conviviales, analysez simplement le code, filtrez-le, envoyez-le au compilateur et analysez la sortie du compilateur. Si c'est un "ne peut pas correspondre au type attendu a contre inféré a -> b" alors vous savez que c'est probablement trop peu d'arguments pour une fonction.

À moins que vous ne vouliez vraiment passer du temps à implémenter Haskell à partir de zéro ou à jouer avec les internes de Hugs, ou une implémentation stupide, je pense que vous devriez simplement filtrer ce qui est passé à GHC. De cette façon, si vos élèves veulent prendre leur base de code et passer à l'étape suivante et écrire du vrai code Haskell à part entière, la transition est transparente.

Voulez-vous construire votre interprète à partir de zéro? Commencez par implémenter un langage fonctionnel plus simple comme le calcul lambda ou une variante lisp. Pour ce dernier, il y a un très joli wikibook appelé Écrivez-vous un schéma en 48 heures donnant une introduction cool et pragmatique aux techniques d'analyse et d'interprétation.

L'interprétation manuelle de Haskell sera beaucoup plus complexe car vous devrez gérer des fonctionnalités très complexes comme les classes de types, un système de type extrêmement puissant (inférence de type!) Et l'évaluation paresseuse (techniques de réduction).

Vous devriez donc définir un tout petit sous-ensemble de Haskell avec lequel travailler, puis peut-être commencer par étendre l'exemple de schéma étape par étape.

Une addition:

Notez que dans Haskell, vous avez un accès complet à l'API des interpréteurs (au moins sous GHC), y compris les analyseurs, les compilateurs et bien sûr les interprètes.

Le package à utiliser est hint (Language.Haskell. *) . Je n'ai malheureusement ni trouvé de tutoriels en ligne à ce sujet ni essayé par moi-même, mais cela semble assez prometteur.

créer un langage qui a exactement les fonctionnalités de Haskell que j'aimerais et qui interdit tout le reste. Au fur et à mesure que les élèves progressent, je peux "activer" de manière sélective diverses fonctionnalités une fois qu'ils maîtrisent les bases.

Je suggère une solution plus simple (comme pour moins de travail) à ce problème. Au lieu de créer une implémentation Haskell où vous pouvez désactiver les fonctionnalités, enveloppez un compilateur Haskell avec un programme qui vérifie d'abord que le code n'utilise aucune fonctionnalité que vous interdisez, puis utilise le compilateur prêt à l'emploi pour le compiler.

Ce serait similaire à HLint (et aussi un peu son contraire):

HLint (anciennement Dr. Haskell) lit les programmes Haskell et suggère des changements qui, espérons-le, les rendent plus faciles à lire. HLint facilite également la désactivation des suggestions indésirables et l'ajout de vos propres suggestions personnalisées.

• Mettez en œuvre vos propres "suggestions" HLint pour ne pas utiliser les fonctionnalités que vous n'autorisez pas
• Désactivez toutes les suggestions HLint standard.
• Faites en sorte que votre wrapper exécute votre HLint modifié dans un premier temps
• Traitez les suggestions HLint comme des erreurs. Autrement dit, si HLint "se plaint", le programme ne passe pas à l'étape de compilation

Baskell est une implémentation pédagogique, http://hackage.haskell.org/package/baskell

Vous pouvez commencer par choisir, disons, le système de types à implémenter. C'est à peu près aussi compliqué qu'un interpréteur pour Scheme, http://hackage.haskell.org/package/thih

La série de compilateurs EHC est probablement le meilleur pari: elle est activement développée et semble être exactement ce que vous voulez - une série de petits compilateurs / interprètes de calculs lambda aboutissant à Haskell '98.

Mais vous pouvez également regarder les différents langages développés dans les types et langages de programmation de Pierce , ou l'interpréteur Helium (un Haskell paralysé destiné aux étudiants http://en.wikipedia.org/wiki/Helium_(Haskell) ).

Si vous recherchez un sous-ensemble de Haskell facile à implémenter, vous pouvez supprimer les classes de type et la vérification de type. Sans classes de type, vous n'avez pas besoin d'inférence de type pour évaluer le code Haskell.

J'ai écrit un compilateur de sous-ensemble Haskell auto-compilant pour un défi Code Golf. Il prend le code de sous-ensemble Haskell en entrée et produit du code C en sortie. Je suis désolé qu'il n'y ait pas de version plus lisible disponible; J'ai soulevé les définitions imbriquées à la main dans le processus de l'auto-compilation.

Pour un étudiant intéressé par l'implémentation d'un interpréteur pour un sous-ensemble de Haskell, je recommanderais de commencer par les fonctionnalités suivantes:

• Évaluation paresseuse. Si l'interprète est en Haskell, vous n'aurez peut-être rien à faire pour cela.

• Définitions de fonction avec des arguments et des gardes correspondant au modèle. Ne vous souciez que des variables, des inconvénients, des nil et des _modèles.

• Syntaxe d'expression simple:

  • Entiers littéraux

  • Littéraux de caractères

  • [] (néant)

  • Application de fonction (associative à gauche)

  • Infix :(contre, droit associatif)

  • Parenthèse

  • Noms de variables

  • Noms de fonction

Plus concrètement, écrivez un interpréteur qui peut exécuter ceci:

-- tail :: [a] -> [a]
tail (_:xs) = xs

-- append :: [a] -> [a] -> [a]
append []     ys = ys
append (x:xs) ys = x : append xs ys

-- zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
zipWith _ _      _      = []

-- showList :: (a -> String) -> [a] -> String
showList _    []     = '[' : ']' : []
showList show (x:xs) = '[' : append (show x) (showItems show xs)

-- showItems :: (a -> String) -> [a] -> String
showItems show []     = ']' : []
showItems show (x:xs) = ',' : append (show x) (showItems show xs)

-- fibs :: [Int]
fibs = 0 : 1 : zipWith add fibs (tail fibs)

-- main :: String
main = showList showInt (take 40 fibs)

La vérification de type est une fonctionnalité cruciale de Haskell. Cependant, passer de rien à un compilateur Haskell de vérification de type est très difficile. Si vous commencez par écrire un interpréteur pour ce qui précède, ajouter une vérification de type devrait être moins intimidant.

Vous pourriez regarder Happy (un analyseur de type yacc dans Haskell) qui a un analyseur Haskell.

Cela pourrait être une bonne idée - créez une toute petite version de NetLogo dans Haskell. Voici le petit interprète.

voir si l' hélium ferait une meilleure base sur laquelle s'appuyer que le haskell standard.

Uhc / Ehc est une série de compilateurs activant / désactivant diverses fonctionnalités Haskell. http://www.cs.uu.nl/wiki/Ehc/WebHome#What_is_UHC_And_EHC

On m'a dit qu'Idris avait un analyseur assez compact, je ne sais pas s'il est vraiment adapté à la modification, mais il est écrit en Haskell.

Le Programming Language Zoo d' Andrej Bauer a une petite implémentation d'un langage de programmation purement fonctionnel appelé "minihaskell". Il s'agit d'environ 700 lignes d'OCaml, donc très faciles à digérer.

Le site contient également des versions jouets de langages de programmation de style ML, Prolog et OO.

Ne pensez-vous pas qu'il serait plus facile de prendre les sources GHC et de supprimer ce que vous ne voulez pas, que d'écrire votre propre interpréteur Haskell à partir de zéro? De manière générale, il devrait y avoir beaucoup moins d'efforts impliqués dans la suppression de fonctionnalités que dans la création / l'ajout de fonctionnalités.

GHC est écrit en Haskell de toute façon, donc techniquement cela reste avec votre question d'un interprète Haskell écrit en Haskell.

Il ne serait probablement pas trop difficile de relier le tout de manière statique et de ne distribuer que votre GHCi personnalisé, afin que les étudiants ne puissent pas charger d'autres modules sources Haskell. Quant à la quantité de travail qu'il faudrait pour les empêcher de charger d'autres fichiers objets Haskell, je n'en ai aucune idée. Vous voudrez peut-être désactiver FFI aussi, si vous avez un tas de tricheurs dans vos classes :)

La raison pour laquelle il y a tant d'interpréteurs LISP est que LISP est fondamentalement un prédécesseur de JSON: un format simple pour encoder des données. Cela rend la partie frontale assez facile à manipuler. Par rapport à cela, Haskell, en particulier avec les extensions de langage, n'est pas le langage le plus facile à analyser. Voici quelques constructions syntaxiques qui semblent difficiles à obtenir:

• opérateurs avec priorité, associativité et fixité configurables,
• commentaires imbriqués
• règle de mise en page
• syntaxe de modèle
• do- blocs et désugaring au code monadique

Chacun d'entre eux, à l'exception peut-être des opérateurs, pourrait être abordé par les étudiants après leur cours de construction de compilateurs, mais cela détournerait l'attention de la façon dont Haskell fonctionne réellement. En plus de cela, vous ne voudrez peut-être pas implémenter directement toutes les constructions syntaxiques de Haskell, mais plutôt implémenter des passes pour vous en débarrasser. Ce qui nous amène au cœur du problème, jeu de mots bien intentionné.

Ma suggestion est d'implémenter la vérification de type et un interpréteur pour Coreau lieu de Haskell complet. Ces deux tâches sont déjà assez complexes en elles-mêmes. Ce langage, tout en restant un langage fonctionnel fortement typé, est beaucoup moins compliqué à gérer en termes d'optimisation et de génération de code. Cependant, il est toujours indépendant de la machine sous-jacente. Par conséquent, GHC l'utilise comme langage intermédiaire et y traduit la plupart des constructions syntaxiques de Haskell.

De plus, vous ne devez pas hésiter à utiliser l'interface de GHC (ou d'un autre compilateur). Je ne considérerais pas cela comme de la triche puisque les LISP personnalisés utilisent l'analyseur du système hôte LISP (au moins pendant le bootstrap). Nettoyer les Coreextraits et les présenter aux étudiants, avec le code d'origine, devrait vous permettre de donner un aperçu de ce que fait le frontend et des raisons pour lesquelles il est préférable de ne pas le réimplémenter.

Voici quelques liens vers la documentation de Coretel qu'utilisé dans GHC:

• System FC: contraintes d'égalité et coercitions
• GHC / En tant que bibliothèque
• Le Coretype