Published on

Test de plusieurs moteurs de script pour l'embarqué

Authors
  • Name
    Anthony Rabine

Utiliser un langage de script sur une cible embarquée va permettre d'apporter une flexibilité fonctionnelle à un firmware fixe. Comparons quelques solutions techniques pour notre usage : dans une boîte à histoires.

Contexte

Le développement de la boîte à histoire open source m’inspire. La boîte commerciale dont elle est inspirée utilise un tout petit fichier binaire pour gérer le script des histoires, en réalité uniquement des embranchements et des indications de fichier image et audio.

Je souhaite quelque chose de plus puissant afin d’offrir plus de possibilités à ma boîte. En réfléchissant un peu, on en revient toujours à deux choix :

Implémenter un langage de script dans le microcontrôleur ; les histoires seront donc écrites en script avec des appels systèmes pour utiliser le matériel de la boîte (affichage, son, boutons)

Implémenter une machine virtuelle interprétant du byte code qui a été compilé sur une machine hôte, à partir d’un langage haut niveau.

Nous allons, dans cet article, effectuer un panorama de ces solutions.

Usage prévu dans OST (OpenStoryTeller)

Il est prévu de fournir un logiciel de création graphique d’histoires ou de scénarios. Dans cette optique, l’utilisateur utilisera des noeuds à relier pour former un graph à l’instar des Blueprints de l'éditeur Unreal Engine.

Dans l’idéal, ce que j’imagine, est que chaque bloc va générer une fonction dans le langage à choisir (c’est le but de cet article) et l’ensemble du projet un script qui sera exécuté par le microcontrôleur.

Mais potentiellement, je ne suis pas obligé de passer par un langage de script intermédiaire. Je pourrais tout à fait imaginer générer un code machine directement ! Par contre c’est sûr, cela sera plus simple à déboguer.

Un autre usage serait de pouvoir générer un script d’histoire (simple) directement depuis la boîte à histoire.

Donc, les éventuelles conclusions de cet articles seront basées sur mon usage propre. D’autres conclusions pourront être tirées dans des contextes différents.

Utiliser un langage de script embarqué

Utiliser un langage de script au sein du microcontrôleur permet donc d’apporter une variabilité de comportement dynamique à un logiciel embarqué fixe.

Vers quel langage se tourner ? On pourrait en créer un de toutes pièces, mais utiliser un standard permet à plus de développeurs d’utiliser notre création.

Dans une première approche, nous allons sélectionner des vieux langages : en effet, ceux-ci tournaient sur de vieux ordinateurs, lents selon nos critères d’aujourd’hui mais désormais plus proches des microcontrôleurs d’aujourd’hui. La RAM est néanmoins toujours un soucis dans l’embarqué, il faudrait faire attention à son usage.

Je ne connais pas la plupart de ces vieux ancêtres, cela me fera l’occasion d’apprendre les bases de chacun de ces langages, de comprendre leur philosophie et de compléter ma culture générale !

Langage de script, les critères de choix :

  • Propose des opérateurs et fonctions de base : conditions, boucles, fonctions/routines, arithmétique simple
  • Pouvoir charger des fichiers sur la carte SD et/ou en streaming
  • Inclusion d’autres fichiers ?
  • Cible mini 128Ko ROM 64 Ko RAM
  • Pas d’allocation dynamique de mémoire
  • Peu de variables nécessaires
  • Interaction avec le C simple et prévue : pouvoir appeler du code C simplement (API existante)
  • Pas besoin de classes, au contraire
  • Facile à intégrer : un ou deux fichiers sources, pas plus, sinon je ne prends pas
  • Utilisant uniquement la librairie standard C (pas d’appels systèmes Linux)
  • Facilité de redirection du printf
  • Licence MIT, BSD, Apache ou similaire (pas GPL)
  • Performance : pas de besoin particulier car le script fera appel à une API en C s’occupant de tous les appels au matériel (audio, images, réseau). Les script ne seront donc que des machines à état flexibles

(GW) BASIC

Le langage semble simple: une ligne, une instruction (en gros) ; un espèce d’assembleur qui fonctionnerait avec des variables au lieu des registres et une facilité pour écrire des formules mathématiques.

Le GW Basic est également un peu multimédia, on peut jouer de la musique par exemple, mais ce genre de fonctions ne m’intéresse pas pour mon usage.

Voyons ce que donnent quelques implémentations :

https://github.com/kevinboone/PMBASIC : Utilise du malloc, pas vraiment une “petite” implémentation.

https://github.com/adamdunkels/ubasic : une implémentation du célèbre Adam Dunkels, plus maintenue malheureusement et elle utilise des malloc

https://github.com/alexo-git/embedded-basic : une implémentation légère du Basic (sans le GW) mais il est basé sur une implémentation plus simple : https://github.com/jwillia3/BASIC

Cette dernière implémentation fait également de l’allocation dynamique mais elle pourrait être facilement supprimée : elle est utilisée uniquement pour déclarer une variable avec DIM et pourrait être remplacée par un poll mémoire fixe.

zForth (langage : Forth)

J’ai testé plusieurs implémentations très minimales avant d’en retenir la seule qui répond à tous mes critères : zForth https://github.com/zevv/zForth

  • Licence MIT
  • Fichiers sources : un couple c/h
  • Pas d’allocation dynamique (une stack statique de travail)
  • Redirection du printf : une fonction à implémenter côté hôte
  • API C / extensible en C : très simple d’ajouter des fonctions C appelées en natif

Malheureusement, le langage Forth est très particulier. De part sa conception à base de stack, tout fonctionne selon une logique inversée. Autant pour les calculs, ça va, autant pour écrire une simple boucle, tout devient un enfer : votre code se complexifie à coup d’astuces pour ne pas perdre de variables (duplication notamment).

Le langage est très simple, presque élégant, mais relire un ancien algorithme vieux de quelques semaines vous imposera de dessiner la stack sur une feuille pour comprendre.

Le code source de zForth est vraiment très clair, simple et pourtant concis. Du très bon code.

C’est donc un 10/10 pour l’implémentation de zForth, mais je recale le langage. Il n’y aura donc pas d’autres implémentations testées.

Langage LISP

An fouillant sur github on trouve sans problème des implémentations de Lisp minimales. Par contre, beaucoup mois sans allocation dynamique de mémoire.

L’autre problème rencontré, que l’on a rencontré aussi avec Forth, est la compatibilité entre les différentes implémentations de Lisp.

Pour des calculs simples, normalement toutes les implémentations fonctionnent pareil. Mais pour une simple définition de fonction, c’est le drame. Par exemple, le code suivant ne s’exécute pas sur deux implémentations trouvées :

lisp
(defun add (a b) (+ a b))
(write(add 5 6))

Eh oui car le mot clé “defun”, c’est du Common Lisp ! (une implémentation libre, conforme à la norme ANSI Lisp). J’ai donc remarqué que la plupart des implémentations “petites” sont plutôt conformes au Lisp originel (et a priori, à Scheme) et parfois offrent des compatibilité via des macros en Lisp.

Ainsi, le code suivant semble être compatible avec beaucoup plus d’implémentations :

lisp
(define add (lambda (a b) (+ a b)))
(add 3 4)

Quelques mots sur les implémentations testées. Le compte Github de Robert van Engelen est riche en multiples implémentations dont un interpréteur en seulement 99 lignes de code C ! Celle qui nous intéresse est un peu plus grosse mais plus intéressante pour l’embarqué est celle-ci https://github.com/Robert-van-Engelen/lisp. Plus intéressante car plus performante, plus riche et plus extensible.

Voici ses caractéristiques

  • Licence BSD
  • Fichiers sources : OK (un source C ou C++ au choix)
  • Pas d’allocation dynamique
  • Redirection du printf NON
  • API C / extensible en C: non en pratique, car il faut modifier le code source de l’interpréteur. Bof quoi !

Langage TCL

Le langage TCL est assez simple dans son approche : le premier mot sur une ligne est une commande et le reste de la ligne sont les arguments, séparés par des espaces.

http://antirez.com/picol/picol.c.txt : l’auteur de Redis s’est fendu d’une implémentation en 3 heures, ggrrr encore du malloc, donc pas pour nous ! (ce n’est pas vraiment un projet utilisable, plus une démo)

http://runtimeterror.com/tech/lil/ : petite implémentation propre, mais utilise du malloc

https://github.com/msteveb/jimtcl : plutôt une grosse implémentation, beaucoup de fichiers et forcément du malloc, on oublie pour notre cas

https://github.com/howerj/pickle : lui est plus intéressant pour cibler les microcontrôleurs : l’implémentation tient sur deux fichiers et l’auteur propose un moyen d’utiliser un allocateur dynamique de mémoire alternatif. Voilà quelqu’un qui connaît bien l’embarqué. Le langage peut être étendu via une API, bref c’est (presque) parfait.

Il semble que le langage TCL provoque naturellement une consommation mémoire importante par sa grammaire très basée sur les chaînes de caractères (maths et structures de données). Donc, de base, ce n’est peut-être pas un bon choix pour l’embarqué.

Lua : Virtual Machine only ?

Utiliser Lua est très exitant : c’est un langage populaire, robuste car bien maintenu et “ancien”. Bien entendu, il est légèrement trop épais pour la gamme de processeur visée MAIS il est doté d’une fonction intéressante : il peut être compilé en bytecode. Donc, au lieu d’embarquer tout Lua, il suffirait d’embarquer uniquement la machine virtuelle.

Mais, ce n’est pas aussi simple en réalité : le bytecode ne supporte pas la compilation croisée. Si vous compilez un programme Lua sur un PC x86-64 en bytecode, celui-ci ne sera pas compatible avec la VM embarquée sur un ARM par exemple. Le projet eLua semble un peu mort et vise à supporter un ensemble complet de fonctionnalités embarquée, pas uniquement la machine virtuelle.

De plus, Lua est quand même “assez” gourmand en RAM ; difficile de le faire rentrer dans un petit microcontrôleur 😦

Conclusion : solution abandonnée

Javascript

Il existe peu d’interpréteurs Javascript suffisamment optimisés pour l’embarqué.

## Espruino

Pourrait être un bon candidat mais offre un système complet avec des périphériques. Trop “gros”, le compilateur et VM n’est pas accessible séparément, dommage. Assurément, ce projet est intéressant pour le haut du panier des microcontrôleurs (Cortex M3/4 typiquement).

## Duktape

Je le connais bien pour l’avoir embarqué dans plusieurs applications.

## JerryScript

Un peu pareil que Espruino ; beaucoup, beaucoup de fichiers !

Autres

## Micro Python

Utiliser un langage populaire comme Python en embarqué semble séduisant... Mais les implémentations sont encore trop gourmandes pour notre besoin (et pas si simple à intégrer).

Wren

Prometteur, VM légère mais allocation dynamique. Le langage est assez nouveau.

JSON Virtual Machine

Prenons les pré-requis suivants :

On imagine un graph en JSON (objets “vertex” reliés entre eux par des “edges” formant une machine à état

Tous les objets de ce noeud sont spécifiques : (afficher une image, jouer un son)

On peut imaginer des noeuds spécifiques : calculs, embranchements

Si on possède tout cela, on est proche d’une machine virtuelle et d’un fonctionnement à la NodeRED : chaque noeud exécute quelque chose et possède un message d’entrée et un message de sortie.

De plus, parser du JSON est sûrement plus simple que parser un langage de script, moins souple (et encore) mais cela suffit pour notre application. De plus, il existe des formats à la JSON mais binaires, comme le BJson qui semblent un peu plus légers. En réalité, beaucoup d’implémentations de BJson par exemple utilisent de l’allocation dynamique, donc hors propos ici.

Le désavantage est que chaque type de bloc (noeud) doit être implémenté à l’avance, mais c’est le cas aussi avec les langages de script lorsqu’il s’agit d’appeler des fonctions externes au langage, comme afficher une image par exemple. De plus le matériel sur lequel tourne le script est limité par design donc toute folie n’est pas possible.

Essayons une implémentation super optimisée : https://github.com/zserge/jsmn

Ce décodeur JSON, en C, ne fait que le décodeur et n’utilise pas de malloc. Bien entendu, il faudra réserver des cases mémoire de travail à l’avance, en statique, et les histoires seront limitées. Mais ces limites peuvent être assez grandes ! Surtout que l’on peut jouer avec plusieurs fichiers si besoin.

Par exemple ce genre de diagramme décrivant une histoire :

image

Pourrait générer un fichier comme cela :

json
 {
     "version": 100,
     "story":
    [
        {
            "t": "s"
        },
        {
            "m": "36*4 + 2"
        },
        {
            "_comment": "show picture on screen, specify filename",
            "p": "poney.bmp"
        }
    ]
}

L’histoire est un tableau d’objets, chaque objet est une étape de l’histoire. Une action comme jouer un son ou une image. Lorsque l’action est terminée, on passe à la suivante. Pour créer des embranchements, il faudra nommer chaque étape.

Il s’avère après quelques tests que le code est très très simple, tant du côté du décodeur JSON que du code utilisateur. Un bon candidat !

Créer sa propre VM

L’idée est séduisante ; il existe plusieurs machines virtuelles légères, soit un CPU ou carrément une machine complète avec clavier, son et écran. C’est le cas de la très vieille machine virtuelle nomée Chip8 !

L’avantage : tout est optimisé aux petits oignons, le PC génère un binaire pour cette machine virtuelle qui sera interprétées par une machine virtuelle logées dans le microcontrôleur. Dans notre cas, c’est une bonne solution.

image

Le jeu Monkey Island est basé sur sur une machine virtuelle appelée SCUMM et un script décrivant les différentes scènes. Une bonne inspiration pour notre boîte à histoire ?

Conclusion

Difficile de conclure de manière générique. Selon tel ou tel usage, on pourrait prendre différentes décisions. Si on reste dans le très très embarqué et que l’on banni vraiment le malloc, alors le choix est assez restreint : seuls Forth et Lisp tirent leur épingle du jeu.

Dans mon cas, je n’ai rien trouvé de parfait, un projet bien maintenu et sans allocation dynamique, donc je vais probablement m’orienter vers un système à base de JSON ou de machine virtuelle.