Factor : TD 1

« Paradigmes et langages non classiques 2014

Ce TD permet de manipuler et d’approfondir les différents concepts abordés lors du premier cours sur Factor.

Échauffement

Définir la fonction fact calculant la factorielle d’un nombre. Cette fonction devra retourner 1 pour un paramètre inférieur ou égal à 0. Rappels du cours : on pourra utiliser les mots dup, <= et if. Les blocs de code (similaires à des « lambda » sans arguments) sont délimités par des crochets [ … ]. Les crochets doivent être considérés comme des mots isolés, il faut donc mettre des espaces de manière idoine.

Rappels sur le système de module

Dans Factor, on peut définir les mots qui suivront dans un vocabulaire différent en écrivant :

IN: vocab

Pour utiliser un vocabulaire particulier (et en voir les mots), on peut faire

USE: vocab

USING: vocab1 vocab2 ... vocabN ;

Lorsqu’un mot n’est pas visible mais est connu, l’environnement proposera généralement d’importer automatiquement les différents modules où un tel mot est défini. Il est possible d’encadrer certains mots de <PRIVATE et PRIVATE>. Dans ce cas, ils seront créés dans un vocabulaire dont le nom sera dérivé du nom du vocabulaire courant auquel sera ajouté .private. L’accès depuis le vocabulaire courant est automatique, mais ces mots ne seront pas automatiquement visible depuis d’autres vocabulaires (à moins que le vocabulaire privé soit explicitement utilisé, ce qui est un signe évident de mauvaise pratique en dehors des tests).

Tours de Hanoï

On souhaite faire un programme permettant de résoudre le problème des tours de Hanoï. N tours sont empilées sur le plot 1, et on souhaite les faire arriver sur le plot 3 qui est initialement vide, le plot 2 l’étant aussi. À aucun moment une tour ne peut être placée sur une tour plus petite qu’elle. Pour savoir où créer son premier vocabulaire, voir l’article Creating a vocabulary for your first program dans la documentation de Factor. Le vocabulaire devra se trouver dans la ressource work et s’appeler hanoi.

Affichage d’un mouvement

Faire un mot move ( a b — str ) renvoyant la chaîne de caractères « a vers b ». Par exemple, 1 2 move renverra « 1 vers 2 ». On pourra utiliser string>number pour transformer un entier en chaîne de caractères. On minimisera les répétitions de code en utilisant bi@. On cherchera dans la documentation comment joindre ensemble deux chaînes deux caractères avec un séparateur, les chaînes étant elles-même des tableaux de caractères. Au même endroit que le vocabulaire hanoi, créer un fichier hanoi-tests.factor contenant un ou plusieurs tests unitaires pour la fonction move. On pourra s’inspirer de l’article Testing your first program de la documentation de Factor. Pour tous les mots définis par la suite, on écrira des tests unitaires.

Algorithme

La signature de « hanoi » est :

hanoi ( d a n -- )

où d est le plot de départ (entre 1 et 3), a le plot d’arrivée (entre 1 et 3) et n le nombre de tours empilées. Chercher un algorithme récursif permettant de résoudre le problème des tours de Hanoï. On pourra définir les mots suivants si on a besoin :

other ( a b -- o )       ! Étant donnés deux plots a et b, renvoie le 3è
partial ( a b -- a b' )  ! Étant donnés deux plots a et b, renvoie les deux plots a et o
                         ! où o est le résultat de other appliqué sur a et b

Définir le mot principal hanoi avec la signature donnée ci-dessus. De plus, le mot print affiche une chaîne de caractères suivie d’un retour à la ligne. Le mot move défini précédemment sera également utile. Vérifier que le programme fonctionne en appelant

1 3 3 hanoi

Cela doit afficher

1 vers 3
1 vers 2
3 vers 2
1 vers 3
2 vers 1
2 vers 3
1 vers 3

Créer des tests pour le programme hanoi. On pourra utiliser with-string-writer pour rediriger temporairement la sortie par défaut vers une chaîne de caractères.

Refactorisation du code

Éventuellement, refactoriser le vocabulaire en vérifiant à chaque étape que les tests unitaires fonctionnent toujours. Si de nouveaux mots sont créés à cette occasion, il ne faut pas oublier de rajouter de nouveaux tests unitaires. N’oubliez pas qu’il est possible de tester les mots privés. Ne laissez visible que ce qui est nécessaire.

Engrammes

Les engrammes sont un système de numérotation exotique basé sur les facteurs premiers sortis de l’esprit torturé de Natacha Kerensikova. Le but de cette partie du TD est de concevoir un système de codage de nombres classiques sous la forme d’un engramme, puis un système de décodage d’engrammes sous la forme de nombres classiques.

Génération d’engrammes

Écrire un mot >engramme ( n -- str ) qui génère un engramme sous la forme d’une chaîne de caractères. On pourra, pour créer des mots mutuellement récursifs, utiliser la syntaxe DEFER: word qui déclare que le mot word sera défini plus tard dans le vocabulaire. On pourra utiliser le vocabulaire math.primes.factors, et notamment son mot group-factors, pour décomposer un nombre entier en facteurs premiers et leurs puissances associées. Le mot primes-upto pourra également être utile. Rajouter des tests unitaires avec les exemples donnés par Natacha dans la page décrivant les engrammes.

Décodage d’engrammes

On veut écrire un mot engramme> ( str -- n ) qui transforme un engramme codé sous forme de chaîne en nombre classique. Pour cela, on pourra par exemple décoder le chaîne à l’aide d’un mot parse ( str -- engramme ) qui retourne un nombre (0 ou 1) ou un tableau contenant lui-même d’autres nombres ou tableaux. Ensuite, en surchargeant >integer sur les tableaux, on pourra transformer cette structure en nombre. Si un engramme est mal formé, on souhaite générer l’exception malformed. Pour cela, on peut la déclarer à l’aide de ERROR: malformed ;. Cela définit le mot malformed comme levant l’erreur associée (et ne contenant aucun champ).

Mots utiles

On pourra éventuellement avoir besoin des mots suivants pour réaliser ce codage et décodage d’engrammes, ou du vocabulaire peg.ebnf qui permet d’écrire très facilement un parseur :