backend du compilateur pour un langage fonctionnel

Question

J'ai écrit un interpréteur pour un langage fonctionnel, que je tente d'amorcer en utilisant un compilateur. La langue a un système de type dynamique et utilise des listes, des nombres et des chaînes. Il est aussi fonctionnel et une fonction prend son argumenta comme une liste (comme perls @_, ou js arguments). Les fonctions sont de première classe et peuvent être imbriquées. Quelle langue dois-je cibler avec le compilateur, btw. Je pense que cibler un langage impératif typé statique, comme C serait difficile. La langue devrait soutenir le typage dynamique et la programmation fonctionnelle (js ne serais pas agréable - la langue doit avoir un compilateur lui-même, comme Common Lisp)

Answer 1

Vous ne avez pas besoin de soutien particulier de votre langue cible. La répartition dynamique peut être résolue en utilisant des versions génériques de vos fonctions (mais pensez à l'optimiser lorsque les types peuvent être inférés en toute sécurité), par exemple pour a + b vous pouvez générer un code comme generic_add(a, b), où generic_add est une fonction qui sélectionne une implémentation appropriée en fonction de informations de type à l'exécution.

Pour la partie fonctionnelle, il est trivial de l'éliminer en utilisant lambda lifting. Pour ce dernier, vous avez simplement besoin de construire des listes de variables libres et liées pour chaque noeud AST: la liste des variables libres est construite à partir des feuilles jusqu'à la racine, et une liste liée est construite dans la direction opposée. Pour chaque noeud lambda, vous soustrayez libre de bound, et construisez une nouvelle fonction de niveau supérieur qui prend à la fois les arguments explicites lambda et cette différence (c'est-à-dire, les variables capturées).

En outre, si vous souhaitez effectuer des optimisations ou si votre langage est supposé prendre en charge les suites, pensez à utiliser une transformation CPS.

Answer 2

Cibler des langages de bas niveau comme LLVM et C est très bien tant que vous êtes prêt à implémenter une répartition dynamique, des fermetures, etc. Cependant, puisque vous mentionnez JavaScript comme une cible possible (à l'exception du manque de compilateurs, même si JS est compilé par JIT dans les principaux navigateurs de nos jours), qu'en est-il de Scheme? C'est un langage fonctionnel d'ordre supérieur typé dynamiquement et qui a déjà des compilateurs de code natif: http://community.schemewiki.org/?scheme-faq-standards#implementations Le seul problème peut être qu'il est trop proche de votre langue source et votre compilateur (ou "traducteur", je pourrais dire) serait trop facile peut-être :-)

Si vous êtes prêt à cibler C, un bon point de départ peut être Marc tutoriel Feeley "Le schéma de 90 minutes au compilateur C":. http://churchturing.org/y/90-min-scc.pdf