fml

Un petit langage de la famille ML implémenté de zéro en F#. Lexer, parseur, système de types et évaluateur - une chaîne complète du code source au résultat.

TL;DR

Un petit langage de la famille ML construit de zéro en F# : un lexer, un parseur, un système de types et un évaluateur - le chemin complet du texte source jusqu'au résultat. La partie la plus difficile est le système de types.

Aperçu

fml est un petit langage de programmation de la famille ML, construit de zéro en F#. Il a quatre maillons qui, ensemble, mènent du texte source au résultat : un lexer, un parseur, un système de types et un évaluateur. Chacun fait une chose, mais le plus intéressant et le plus difficile est le système de types.

Son propre langage est un projet qui enseigne l'humilité. Ce n'est pas un seul problème mais toute une séquence où la sortie d'une étape est l'entrée de la suivante, et une erreur à une étape précoce revient avec une force doublée trois pas plus loin. C'est justement pour cela que c'est un si bon exercice de pensée sur les systèmes.

Le texte source doit être découpé en jetons, les jetons rangés en un arbre, l'arbre vérifié du point de vue des types, et enfin exécuté. C'est une chaîne où l'on ne peut tricher à aucune étape, car la suivante l'attrape aussitôt - ou, pire, ne l'attrape pas, et l'erreur ne surgit qu'à la fin sous forme de résultat incompréhensible.

Cette dépendance entre les étapes est à la fois la difficulté et la beauté du projet. Chaque maillon se comprend séparément, mais ce n'est qu'ensemble qu'ils forment quelque chose qui exécute réellement un programme. Concevoir les frontières entre eux pour qu'elles soient propres, c'est la moitié du chemin.

Des types qu'on n'a pas à écrire

Dans un langage de la famille ML, le système de types est la partie la plus intéressante. Vous n'avez pas à écrire les types à la main - le compilateur les déduit de la façon dont vous utilisez les valeurs. Vous écrivez une fonction ordinaire, et le langage découvre lui-même quel type elle a et veille à ce que vous ne l'utilisiez jamais en contradiction avec lui.

example.fml · fsharp

let rec map f xs =
  match xs with
  | [] -> []
  | x :: rest -> f x :: map f rest

map (fun n -> n + 1) [1; 2; 3]

À noter

Nulle part dans ce code nous n'avons écrit un seul type, et pourtant le langage sait que map a le type (a -> b) -> liste a -> liste b. C'est l'inférence de types - l'une des plus belles choses que l'on puisse écrire à la main, et en même temps l'une des plus exigeantes.

Quatre étapes du texte au résultat

Tout le chemin se décompose en quatre étapes aux rôles clairement partagés. Le texte devient des jetons, les jetons un arbre, l'arbre reçoit des types, et enfin il est calculé. Les incompatibilités de types surgissent à la troisième étape, avant l'exécution, et non pendant.

Lexer

le texte source devient un flux de jetons.

Parseur

les jetons se rangent en un arbre syntaxique.

Système de types

chaque expression reçoit un type, et les incompatibilités surgissent ici, pas à l'exécution.

Évaluateur

l'arbre est calculé jusqu'à un résultat.

La chaîne du compilateur

Étape	Entrée	Sortie
Lexer	texte source	jetons
Parseur	jetons	arbre syntaxique
Système de types	arbre	arbre typé
Évaluateur	arbre	résultat

Le résultat : un langage ML écrit dans un langage ML

Ce qui en sort est un langage petit mais complet qui exécute réellement un programme - du premier caractère dans un fichier jusqu'au résultat calculé. F# était ici le choix naturel, car il appartient lui-même à la famille ML, et écrire un langage ML dans un langage ML a quelque chose d'agréablement récursif. C'est un projet après lequel le mot "compilateur" cesse d'être une abstraction.

Plus de projets

D'autres réalisations de la même catégorie - découvrez comment nous abordons des défis similaires.

Vous avez un projet similaire ?

Contactez-nous - le devis est gratuit et arrive sous une heure.