11 juin 2010 à 13 h 30 
Préambule
Il est conseillé de faire l’échauffement avant d’attaquer les autres parties du TD. Vous avez ensuite le choix entre les tours de Hanoï (très simple) ou les engrammes (peu compliqué). Bien entendu, vous pouvez faire les deux si vous le souhaitez.
É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 », « <= », « 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
ou
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 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).
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 « >base ( n radix — str) » 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é deux plots a et b, renvoie le 3è
partial ( a b -- a b' ) ! Étant donné 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. Cependant, la version actuelle a un bug : “2 primes-upto” renvoie le vecteur “V{ 2 3 }” et contient une valeur en trop. En attendant que cela soit corrigé, on pourra écrire un wrapper “(primes-upto) ( n — seq )” qui traite différemment le cas particulier où on lui passe la valeur 2 sur la pile.
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 :
La bibliothèque de factor permet aussi très facilement de créer des parsers ! Je me permets de montrer un exemple pour les engrammes dans la mesure où ça ne va pas trop à l’encontre de l’esprit du TP (Sam n’a pas fourni de lien vers ce vocabulaire) : http://paste.factorcode.org/paste?id=1723
Bon courage :p
Tout à fait. C’est juste que pour le premier TD, je voulais limiter le nombre de pistes proposées :)