Effectivement, pour le registre ecx, c'est maladroit de ma part. J'ai édité mon code en le replaçant par le registre esi. J'ai aussi enlevé les pop ecx par la même occasion .
Pour la mémoire, c'est surtout si des données proviennent de l'utilisateur que ça devient complètement impossible à calculer si je comprends bien.
Sinon, au niveau de l'optimisation, j'ai pensé à enlever tous les épilogues, et prologues des fonctions putchar et getchar, et de remplacer les mov ecx, [esp+8] par directement mov ecx, esi, ce qui permet d'enlever les push esi.
Après, je n'ai pas trop d'idées pour optimiser davantage, mais il y a tout de même pas mal de code qui se répète dans le code généré.
EDIT : pour le frame pointer, tu parle de l'instruction call? C'est tout de même utile pour savoir ou retourner dans le code à la fin de la fonction, nan?
Sinon, comme optimisation, j'ai pensé mettre un place un buffer sur stdin au moins, histoire de limiter le plus possible les appels système à write. Mais je vois pas trop comment m'y prendre.
Pour la mémoire, c'est surtout si des données proviennent de l'utilisateur que ça devient complètement impossible à calculer si je comprends bien.
J'avais tendance à penser que ça simplifierait beaucoup les choses mais je réalise que j'assumais que les programmes fonctionnaient "bien". Prend par exemple le programme débile suivant : +[>+]. C'est une boucle infinie qui initialise toutes les cases à 1. Il ne prend pas d'entrée mais il utilise pourtant une quantité infinie de mémoire. Il y a une infinité de programmes de ce genre possible et il est tout simplement impossible de déterminer à coup sur (et a fortiori dans un temps raisonnable) si certains sont des boucles infinies ou juste très longs. C'est le problème de l’arrêt, encore une fois...
Citation : Tosh
Sinon, au niveau de l'optimisation, j'ai pensé à enlever tous les épilogues, et prologues des fonctions putchar et getchar, et de remplacer les mov ecx, [esp+8] par directement mov ecx, esi, ce qui permet d'enlever les push esi.
Après, je n'ai pas trop d'idées pour optimiser davantage, mais il y a tout de même pas mal de code qui se répète dans le code généré.
C'est probablement ce que tu appelle l'épilogue et le prologue que j'appelle la gestion du frame pointer, ce dernier désignant ebp quand il est utilisé pour sauvegarder esp au début d'une fonction.
Je pense que c'est assez difficile d'optimiser plus sans analyser un peu plus profondément le code bf (c'est pour ça que passer par gcc donne un code plus rapide d'ailleurs)
Citation : Tosh
Sinon, comme optimisation, j'ai pensé mettre un place un buffer sur stdin au moins, histoire de limiter le plus possible les appels système à write. Mais je vois pas trop comment m'y prendre.
Si c'est sur stdin c'est les appels à read que tu va économiser (je te conseille de faire les deux de toute façon). Pour comment s'y prendre, je pense que tu pourra trouver tout seul, réfléchit bien. Le compilo que j'ai posté plus haut gère ça, tu peux t'en inspirer (c'est de l'asm gnu par contre...).
Si c'est sur stdin c'est les appels à read que tu va économiser
Oui, autant pour moi...
Citation
Le compilo que j'ai posté plus haut gère ça, tu peux t'en inspirer (c'est de l'asm gnu par contre...).
Effectivement, je n'avais pas fais attention .
Après des tests comparatifs, ton compilateur est tout de même bien plus performant .
Sur l'ensemble de mandelbrot, je suis a environ 4.5s avec mon code, et 3.7s avec le tient.
Bon, si j'ai le temps, je tenterais d'implémenter ces tampons d'I/O pour voir ce que ça donne...
je sais que le sujet est un peu mort, cependant j'ai voulu essayer.
voila ma contribution: elle est en Ocaml, un langage déjà pas mal utilisé sur ce sujet, cependant j'ai voulu m'y mettre et je me suis dit que ce serait une bonne occasion. Surtout que vu les précédentes réponses, l'ocaml avait l'air pas mal pour le traitement d'un langage.
étant donné que c'est mon premier exercices, je pense qu'il y a beaucoup de chose a améliorer: n'hésitez pas à me dire quoi et comment.
enfin pour parler un peu de ce que j'ai fait, mon interpréteur gère tout les symboles bf sauf '[' et ']' à cause du retour en arrière que cela implique.
Pour la bande de mémoire, elle est semi infinie (à droite), si on va trop à gauche, l'interpréteur refuse sans donner de message. trop facile sinon .
et le code:
let rec display l =
match l with
| head::tail -> print_int head;
display tail;
| [] -> print_char ' ';
print_newline();
;;
let reverse l =
let rec aux l p =
match l with
|head::tail -> aux tail (head::p)
|[] -> p
in aux l []
;;
let parse p =
let rec aux pr l i len =
if i = (len-1) then
if (pr.[i] = '+' ||
pr.[i] = '-' ||
pr.[i] = '<' ||
pr.[i] = '>' ||
pr.[i] = '.' ||
pr.[i] = ',') then
(pr.[i]::l)
else
l
else
if pr.[i] = '+' || pr.[i] = '-' ||
pr.[i] = '<' || pr.[i] = '>' ||
pr.[i] = '.' || pr.[i] = ','
then
aux pr (pr.[i]::l) (i+1) len
else
aux pr l (i+1) len
in aux p [] 0 (String.length p)
;;
let read_char() =
let a = read_line()
in (int_of_char a.[0]);;
let rec exec p cPre cSui =
match p with
|head::tail ->begin
match head with
| '+' -> begin match cPre with
| h::t ->exec tail ((h+1)::t) cSui;
| [] -> exec tail [1] cSui
end
| '-' -> begin match cPre with
| h::t -> exec tail ((h-1)::t) cSui
| [] -> exec tail [0] cSui
end
| '>' -> begin match cPre with
|h::t -> exec tail t (h::cSui)
| [] -> exec tail [] cSui
end
| '<' -> begin match cSui with
|h::t -> exec tail (h::cPre) t
| [] -> exec tail (0::cPre) []
end
| '.' -> begin match cPre with
|h::t -> print_char (char_of_int h);
exec tail cPre cSui;
|[] -> exec tail cPre cSui
end
| ',' -> begin match cPre with
|h::t -> exec tail (read_char()::t) cSui
|[] -> exec tail [read_char()] cSui
end
| _ -> exec tail cPre cSui;
end;
| [] -> []
;;
let a = ".>.+++++++..+++.>.<<+++++++++++++++.>.+++.------.--------.>+.>.";;
let b = ",>,>,><<<.>.>.";;
exec (reverse (parse b)) [] [];;
print_newline();;
exec (reverse (parse a)) [72;101;32;10] [];;
(parse a) retourne une liste depuis une chaine, reverse la retourne (le début à la fin) et (exec p cPre cSui) execute le code p avec comme contexte courant et précédant cPre et comme suite de la bande cSui. pour l'exécution de a j'ai prérempli la bande pour éviter d'avoir des centaines de '+'.
Qui ça ? moi ? Désolé, je ne sais pas comment on indente en Ocaml, j'ai indenter d'une manière qui me permettait de relire et de comprendre rapidement mon code.
Enfin, si c'est mon seul point négatif, ça va encore.
heu... comment dire sans me faire lapider. quand je n'utilise pas vim, c'est nano mon éditeur de texte...
enfin, je vais voir a quoi ressemble le "tuareg mode".
et puis, au passage, dit moi dont ce qui ne va pas dans mon indentation: les begin et end sont alignés, les clause des match aussi, il y a une tabulation après un then...
Ouais bah utilise vim c'est très bien. Mais les tabulations c'est mal, c'est le mal.
Utilise des espaces à la place (en OCaml habituellement les gens indentent de 2 espaces).
pour le débat espace/tab, on a plus le temps aujourd'hui.
pour l'éditeur de texte, que j'utilise vim, emacs ou nano c'est pareil, je ne connais pas l'indentation en Ocaml.
enfin, puisque tu n'est pas capable de copier coller et d'indenter ni d'expliquer comment on indente en Ocaml, j'ai éditer mon message avec ton indentation. J'espère ne pas avoir à le refaire pour le prochain qui verra ce code.
Hedi
ps: je suis peut être un peu dur: j'essaie de t'égaler, dark
ta transformation string->liste est mauvaise. Ta transformation est itérative et pas récursive, c'est pour ça que tu es obligé de renverser ta liste (qui se comporte ici comme une pile) après coup. Au final tu parcours deux fois « le code source » alors qu'il suffirait de le parcourir une fois. Tu as d'ailleurs plusieurs façon de faire, une façon purement récursive, et une façon récursive terminale (comprendre: utiliser un algorithme itératif) en se servant de la possibilité de parcourir une chaîne de sa fin vers son début. Je te laisse regarder les deux premières fonctions à la fin de ce message. (À noter que la première est a priori plus lisible et surtout plus intéressante pour un débutant)
Il manque les boucles dans ton brainfuck
Transformer ta string en liste, c'est cool ça te permet de faire du filtrage de motif, mais est-ce vraiment intéressant pour ce que tu fais ? Je ne suis pas convaincu. Parcourir ta string directement (en te servant d'un index) aurait été plus rapide à coder et plus efficace (ce serait encore plus vraie si tu avais implémenté les boucles).
À part ça c'est cool, tu utilises un Zipper pour la mémoire. (moi j'aime bien les zippers)
Quoi qu'il en soit, je t'invite à lire cet article de lasts qui avait été posté en début de topic (mais qui est un peu passé à la trape) et qui traite de l'implémentation d'un brainfuck en ocaml: http://lasts.goldzoneweb.info/brainfuck.html
Bonne soirée
PS: Désolé si je t'ai vexé au fait, j'ai été un peu froid mais faut pas le prendre mal, c'est l'habitude.
EDIT: Oups, j'avais oublié le code :
(* La version récursive *)
let list_of_string s =
let rec aux i max =
if i = max then []
else s.[i] :: aux (succ i) max
in aux 0 (String.length s)
(* La version itérative *)
let list_of_string' s =
let rec aux acc i =
if i < 0 then acc
else aux (s.[i] :: acc) (pred i)
in aux [] ((String.length s) - 1)
Un peu de Java.
J'en ai pas vu beaucoup, et c'est sans doute normal, vu que ce langage ne se prête pas trop à ce genre de problèmes.
Je vous ai pondu ça en bon Java bien verbeux, avec des noms de variables bien longs, des méthodes et des commentaires Javadoc. Du Java, quoi.
package info.kisai.brainfuck;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
/**
* Interpréteur BrainFuck
* @author SpaceFox
*/
public class BrainFuck {
// Paramètres de la machine
private int tailleMemoire;
private int tailleValeur;
// Variables
private char[] programme;
private StringBuilder sortie = new StringBuilder();
private List<Character> memoire; // Liste pour pouvoir gérer une mémoire "infinie"
/**
* Constructeur unique.<br/>
* Initialise la mémoire et les tailles maximales.
* @param tailleMemoire la taille max de la mémoire, en cases. Aucune taille max si <code>null</code>.
* @param tailleValeur la taille max d'une case. Aucune taille max si <code>null</code>.
*/
public BrainFuck(Integer tailleMemoire, Integer tailleValeur) {
if (tailleMemoire == null) {
this.tailleMemoire = Integer.MAX_VALUE;
initMemoire(30000); // Purement arbitraire, sera augmenté si besoin
} else {
this.tailleMemoire = tailleMemoire;
initMemoire(tailleMemoire);
}
if (tailleValeur == null) {
this.tailleValeur = Character.MAX_VALUE;
} else {
this.tailleValeur = tailleValeur;
}
}
public void setProgramme(char[] programme) {
this.programme = programme;
}
public void setProgramme(String programme) {
setProgramme(programme.toCharArray());
}
/**
* Pour debug. Utile pour les versions étendues (verif de la transformation).
* @return le programme en brainfuck.
*/
public String getProgramme() {
return String.valueOf(programme);
}
/**
* Exécute le programme et renvoie le résultat sous forme de chaîne. Les entrées sont lues sur l'entrée passée en
* paramètre.
* @param entreeStream un flux d'entrée quelconque.
* @return le résultat du programme.
*/
public String execute(InputStream entreeStream) {
int longueurProgramme = programme.length;
int iInstruction = 0;
int pointeur = 0;
do {
switch (programme[iInstruction]) {
case '>':
pointeur = incrementePointeur(pointeur);
break;
case '<':
pointeur = decrementePointeur(pointeur);
break;
case '+':
memoire.set(pointeur, incrementeMemoire(pointeur));
break;
case '-':
memoire.set(pointeur, decrementeMemoire(pointeur));
break;
case '.':
sortie.append(getMemoireAt(pointeur));
break;
case ',':
memoire.set(pointeur, litEntree(entreeStream));
break;
case '[':
iInstruction = sautConditionnel(iInstruction, pointeur);
break;
case ']':
iInstruction = retourConditionnel(iInstruction, pointeur);
break;
// Autres cas --> ignorés (commentaires)
}
// Pour debug
// System.out.println(" instruction n°" + iInstruction + " " + programme[iInstruction] + " ==> pointeur "+ pointeur + " --> valeur " + Integer.valueOf(memoire.get(pointeur)));
iInstruction++;
} while (iInstruction < longueurProgramme);
return sortie.toString();
}
/**
* Récupère le caractère dans la mémoire. Initialise la mémoire jusqu'à ce pointeur si besoin.
* @param pointeur l'adresse de la case à récupérer.
* @return le contenu de cette case.
*/
private char getMemoireAt(int pointeur) {
if (pointeur > tailleMemoire) {
initMemoire(pointeur);
}
return memoire.get(pointeur);
}
/**
* Incrémente le pointeur de manière sécurisée.
* @param pointeur la valeur actuelle du pointeur.
* @return <code>pointeur + 1</code> ou <code>0</code> en cas de dépassement de la taille max de la mémoire.
*/
private int incrementePointeur(int pointeur) {
if (pointeur >= (tailleMemoire - 1)) {
return 0;
}
return pointeur + 1;
}
/**
* Décrémente le pointeur de manière sécurisée.
* @param pointeur la valeur actuelle du pointeur.
* @return <code>pointeur - 1</code> ou l'ID de la dernière cas de la mémoire en cas de pointeur déjà à 0.
*/
private int decrementePointeur(int pointeur) {
if (pointeur == 0) {
return tailleMemoire - 1;
}
return pointeur - 1;
}
/**
* Incrémente la valeur de la case mémoire de manière sécurisée.
* @param pointeur l'adresse de la case à incrémenter.
* @return <code>valeur + 1</code> ou <code>0</code> en cas de dépassement de la taille max d'une case.
*/
private char incrementeMemoire(int pointeur) {
char valeur = getMemoireAt(pointeur);
if (valeur >= (tailleValeur - 1)) {
return 0;
}
return (char) (valeur + 1);
}
/**
* Décrémente la valeur de la case mémoire de manière sécurisée.
* @param pointeur l'adresse de la case à décrémenter.
* @return <code>valeur - 1</code> ou le maximum possible d'une valeur en cas de valeur déjà à 0.
*/
private char decrementeMemoire(int pointeur) {
char valeur = getMemoireAt(pointeur);
if (valeur == 0) {
return (char) (tailleValeur - 1);
}
return (char) (valeur - 1);
}
/**
* Lit un caractère sur l'entrée.<br/>
* Un problème de lecture ne provoque pas d'erreur mais le caractère <code>0x0000</code>
* @param entreeStream le flux d'entrée sur lequel lire le caractère.
* @return le premier caractère de l'entrée, ou <code>0x0000</code> en cas d'erreur.
*/
private char litEntree(InputStream entreeStream) {
InputStreamReader entreeReader = new InputStreamReader(entreeStream);
char[] entree = new char[1];
try {
entreeReader.read(entree);
} catch (IOException e) {
entree[0] = 0;
}
return entree[0]; // La seule qui existe
}
/**
* Donne l'index de l'instruction suivante, selon le résultat du saut conditionnel.
* @param iInstruction l'index de l'instruction courante.
* @param pointeur le pointeur pour la condition
* @return l'index de l'instruction courante si la valeur à la case indiquée par le pointeur est différente de
* <code>0x0000</code>.<br/>
* L'index de l'instruction suivant le crochet fermant correspondant sinon.
*/
private int sautConditionnel(int iInstruction, int pointeur) {
if (getMemoireAt(pointeur) == 0) {
int nbCrochets = 1;
while (nbCrochets > 0) {
iInstruction++;
if (programme[iInstruction] == '[') {
nbCrochets++;
} else if(programme[iInstruction] == ']') {
nbCrochets--;
}
}
return iInstruction;
}
return iInstruction;
}
/**
* Donne l'index de l'instruction suivante, selon le résultat du saut conditionnel.
* @param iInstruction l'index de l'instruction courante.
* @param pointeur le pointeur pour la condition
* @return l'index de l'instruction courante si la valeur à la case indiquée par le pointeur est égale à
* <code>0x0000</code>.<br/>
* L'index de l'instruction suivant le crochet ouvrant correspondant sinon.
*/
private int retourConditionnel(int iInstruction, int pointeur) {
if (getMemoireAt(pointeur) != 0) {
int nbCrochets = 1;
while (nbCrochets > 0) {
iInstruction--;
if (programme[iInstruction] == ']') {
nbCrochets++;
} else if(programme[iInstruction] == '[') {
nbCrochets--;
}
}
return iInstruction - 1; // On retourne à celui d'avant
}
return iInstruction;
}
/**
* Initialise la mémoire (remplissage par des 0) jusqu'à la taille indiquée.<br/>
* Seule la partie entre la taille courante et la taille spécifiée est initialisée, pour pouvoir agrandir la mémoire
* en cas de "mémoire infinie".<br/>
* Cette méthode ne fait rien si la taille voulue est plus petite que la taille actuelle.
* @param taille la taille voulue pour la mémoire.
*/
private void initMemoire(int taille) {
if (memoire == null) {
memoire = new ArrayList<Character>(taille);
}
for (int i = memoire.size(); i < taille; i++) {
memoire.add(i, (char) 0);
}
}
}
Niveau performance, c'est totalement sous-optimisé : je mets quasiment une demi-seconde à cracher le texte de la GPL quand l'autre implémentation Java du topic (celle de injection18) le fait pratiquement instantanément.
A ce sujet, je me doutais qu'il y aurait une différence, mais pas à ce point. J'ai pas creusé "pourquoi", mais un facteur 400 ça me paraît quand même énorme...
Cela dit, la performance ultime n'était pas le but, mais plutôt la souplesse et la taille et la clarté du code (cela dit, y'a peut-être que moi qui le trouve clair ce truc ).
on peut choisir de manière arbitraire la taille de la mémoire (standard BF : 30000 cases) et la taille des cases (standard BF 256 valeurs).
Y'a aussi, la séparation des tâches : On se fout de comment on incrémente une valeur, la méthode l'incrémente. Bon sur un truc de cette taille y'a pas trop d'intérêt, mais c'est la philosophie qui est intéressante.
Du coup le truc est facilement extensible : on a besoin d'un code minimal pour faire des interpréteurs Spoon et Ook - en fait, juste les méthodes de transcription en BF.
Spoon :
package info.kisai.brainfuck;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* Interpréteur Spoon.
* @author SpaceFox
*/
public class Spoon extends BrainFuck {
public Spoon(Integer tailleMemoire, Integer tailleValeur) {
super(tailleMemoire, tailleValeur);
}
/**
* Convertit le programme Spoon (en mode texte) en Brainfuck et l'enregistre dans l'objet.<br/>
* Les caractères autres que "0" et "1" sont ignorés, ainsi que les éventuelles séquences invalides (normalement
* possibles seulement en début et fin de programme).
* @param spoon un programme Spoon
*/
@Override public void setProgramme(char[] spoon) {
List<Character> bf = new ArrayList<Character>();
Map<String, Character> correspondance = new HashMap<String, Character>();
correspondance.put("010", '>');
correspondance.put("011", '<');
correspondance.put("1", '+');
correspondance.put("000", '-');
correspondance.put("0010110", ',');
correspondance.put("001010", '.');
correspondance.put("00100", '[');
correspondance.put("0011", ']');
String cle = "";
for (char c : spoon) {
if (c == '0' || c == '1') {
cle += c;
if (correspondance.containsKey(cle)) {
bf.add(correspondance.get(cle));
cle = "";
}
}
}
// Si quelqu'un a une solution plus simple, la flemme de chercher ^^'
char[] bfChar = new char[bf.size()];
for (int i = 0; i < bf.size(); i++) {
bfChar[i] = bf.get(i);
}
super.setProgramme(bfChar);
}
}
Ook :
package info.kisai.brainfuck;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* Interpréteur Ook.
* @author SpaceFox
*/
public class Ook extends BrainFuck {
public Ook(Integer tailleMemoire, Integer tailleValeur) {
super(tailleMemoire, tailleValeur);
}
/**
* Convertit le programme Ook en Brainfuck et l'enregistre dans l'objet.<br/>
* On remarque que dans le "Ook" les seules différences entre les "symboles" sont dans la ponctuation, donc on ne
* tient compte que de celle-ci.<br/>
* Problème induit : S'il y a des commentaires avec les caractères ".", "?" ou "!" dans le programme, ils casseront
* l'interprétation.
* @param ook un programme Ook
*/
@Override public void setProgramme(char[] ook) {
List<Character> bf = new ArrayList<Character>();
Map<String, Character> correspondance = new HashMap<String, Character>();
correspondance.put(".?", '>');
correspondance.put("?.", '<');
correspondance.put("..", '+');
correspondance.put("!!", '-');
correspondance.put("!.", '.');
correspondance.put(".!", ',');
correspondance.put("!?", '[');
correspondance.put("?!", ']');
String cle = "";
for (char c : ook) {
if (c == '.' || c == '?' || c == '!') {
cle += c;
if (correspondance.containsKey(cle)) {
bf.add(correspondance.get(cle));
cle = "";
}
}
}
// Si quelqu'un a une solution plus simple, la flemme de chercher ^^'
char[] bfChar = new char[bf.size()];
for (int i = 0; i < bf.size(); i++) {
bfChar[i] = bf.get(i);
}
super.setProgramme(bfChar);
}
}
Et encore, j'ai fait ça à l'arrache, je suis sûr qu'on peut les optimiser.
Edit : Optimisation : à la ligne 116 du premier fichier, j'ai remplacé if(pointeur>memoire.size()){ par if(pointeur>tailleMemoire){ --> le programme va 2x plus vite.
Sinon, un petit coup de profiler me dit que je devrais jeter un oeil à ces foutues méthodes "retourConditionnel", "decrementeMemoire", "incrementeMemoire" et "sautConditionnel" qui sont appellées plus de 3 000 000 de fois chacune... Et je suis sûr que y'a moyen de très optimiser les sauts.
Edit 2010-08-18 : En fait mon "optimisation" ne fonctionne que grâce à un malentendu ^^' Par contre j'en ai trouvées de bien plus efficaces.
D'autre part, j'ai fait une coquille dans le calcul du temps : c'est pas x400 mais x2.5 le rapport entre les deux implémentations...
hedi07 > ton code m'a donné envi d'essayer d'implémenter un petit interpréteur sans prétention en caml.
J'ai cherché le moyen de représenter efficacement les boucles, et j'ai défini cette structure de données :
type expr =
| Pp
| Pm
| Pop
| Pom
| Print
| Read
| Block of bf
and bf = expr list
C'est une sorte d'ast tout simple, et quand on a réussit à convertir du brainfuck en cette structure de données, l'évaluation du code est facile et efficace :
let exec =
let pointeur = ref 0 in
let tbl = Array.make 30000 0 in
let incremente n () = pointeur := !pointeur +n in
let decremente n () = pointeur := !pointeur -n in
let get() = tbl.(!pointeur) in
let incremente_octet n () = tbl.(!pointeur) <- get()+n in
let decremente_octet n () = tbl.(!pointeur) <- get()-n in
let view () = print_char (char_of_int (get())) in
let read () = tbl.(!pointeur) <- int_of_char (Scanf.scanf "%c" (fun c -> c)) in
let rec exec_expr = function
| Pp -> incremente 1()
| Pm -> decremente 1 ()
| Pop -> incremente_octet 1()
| Pom -> decremente_octet 1()
| Print -> view()
| Read -> read ()
| Block code ->
if get() <> 0 then
begin
exec' code;
if get() <> 0 then exec_expr (Block code)
end
and exec' code = List.iter exec_expr code
in
exec'
Je n'ai pas utilisé un zipper parce que c'est moins performant (mais plus stylé certe :)).
Maintenant il faut convertir une chaine de caractères dans ma structure de donnée bf.
J'ai codé un parseur en une passe (sans conversion en liste de la chaine) tout à fait horrible, mais qui ne laisse pas passer du code invalide, et qui marche :
let parse =
let associations = [('>', Pp 1); ('<', Pm 1); ('+', Pop 1); ('-', Pom 1); ('.', Print); (',', Read)] in
let assoc_op char = List.assoc char associations in
(* Lis le code tant qu'il y a des opérateurs autres que [ et ] *)
(* utilisation : parse_op s i limit
=> s code brainfuck,
i la position à partir de laquelle on lit le code,
limit : position ou l'on s'arrete de lire
*)
let parse_op =
let rec parse_op' acc s i limit =
if i >= limit then (List.rev acc, limit)
else
match s.[i] with
| char when List.mem char ['>'; '<'; '+'; '-'; '.'; ','] ->
parse_op' (assoc_op char::acc) s (i+1) limit
| char when not (List.mem char ['['; ']']) ->
parse_op' acc s (i+1) limit
| _ -> (List.rev acc, i)
in parse_op' []
in
(* parse un block de code *)
let rec parse_block s i limit =
if s.[i] = '[' then
let r, ni = parse [] s (i+1) limit in
if ni < limit && s.[ni] = ']' then
([Block r], ni+1)
else
raise (UnclosedP i)
else
parse_op s i limit
(* Apelle parse_block tant qu'il y a des blocks à consommer *)
and parse acc s i limit =
if i >= limit then (acc, limit)
else
let c, ni = parse_block s i limit in
if ni = i then (acc , i)
else
parse (acc@c) s ni limit
in
let parse_code s =
let size = String.length s in
let c, s = parse [] s 0 size in
if s < size then raise (UnopenedP s)
else c
in
parse_code
Il fonctionne comme ça :
-parse_op "mange" la chaine jusqu'à trouver des crochets.
-parse block cherche un crochet ouvrant '[', puis appelle récursivement parse, puis vérifie qu'il y a bien un crochet fermant après ce qu'a mangé parse.
Si il n'y a pas de crochet ouvrant, alors parse_block appelle parse_op.
-parse appelle parse_block jusqu'a qu'il y ai quelque chose à faire.
Si parse_block ne fait rien de nouveau, ça veut dire que soit :
- On a parsé la chaine en entier (i >= limit)
- Soit on parsé tout l'intérieur d'une boucle, et dans ce cas la on renvoi ce qu'on a parsé.
- Soit il y a un crochet fermé qui n'a pas été ouvert (on déclenche alors une exception UnopenedP).
C'est un petit peu compliqué, y'a certainement moyen de simplifier ça, j'étais plus très net quand j'ai fait ça :d.
Par la suite, j'ai rajouté des optimisations, un rle ([Pp 1; Pp 1] devient [Pp 2]) et l'optimisation de la remise à zéro du pointeur octet [-].
let optimise code =
let add = function
| Pp n -> Pp (n+1)
| Pm n -> Pm (n+1)
| Pop n -> Pop (n+1)
| Pom n -> Pom (n+1)
| _ -> failwith "situation impossible"
in
let compare_type = function
| Pp _, Pp _
| Pm _, Pm _
| Pop _, Pop _
| Pom _, Pom _ -> true
| _ -> false
in
let rle code =
let rec rle' e = function
| [] -> if e <> Pp 0 then [e] else []
| elem::l when compare_type (e, elem) && List.mem elem [Pp 1; Pm 1; Pop 1; Pom 1] -> rle' (add e) l
| (Block code)::l ->
let r = Block (rle' (Pp 0) code) :: (rle' (Pp 0) l) in
if e <> (Pp 0) then e::r else r
| elem::l ->
let r = rle' elem l in
if e <> (Pp 0) then e::r else r
in
rle' (Pp 0) code
in
let rec razpo = function
| [] -> []
| Block [Pom 1]::l -> Razpo::(razpo l)
| Block code::l -> Block (razpo code)::(razpo l)
| e::l -> e::razpo l
in
razpo (rle code)
Cela nécessite de modifier un peu ma structure de données :
type expr =
| Pp of int
| Pm of int
| Pop of int
| Pom of int
| Print
| Read
| Razpo
| Block of bf
and bf = expr list
let exec =
let pointeur = ref 0 in
let tbl = Array.make 30000 0 in
let incremente n () = pointeur := !pointeur +n in
let decremente n () = pointeur := !pointeur -n in
let get() = tbl.(!pointeur) in
let incremente_octet n () = tbl.(!pointeur) <- get()+n in
let decremente_octet n () = tbl.(!pointeur) <- get()-n in
let view () = print_char (char_of_int (get())) in
let read () = tbl.(!pointeur) <- int_of_char (Scanf.scanf "%c" (fun c -> c)) in
let rec exec_expr = function
| Pp n -> incremente n()
| Pm n -> decremente n ()
| Pop n -> incremente_octet n()
| Pom n -> decremente_octet n()
| Razpo -> tbl.(!pointeur) <- 0
| Print -> view()
| Read -> read ()
| Block code ->
if get() <> 0 then
begin
exec' code;
if get() <> 0 then exec_expr (Block code)
end
and exec' code = List.iter exec_expr code
in
exec'
Ces modifications rendent l'évaluateur deux fois plus performant environ.
Pour finir le code complet :
type expr =
| Pp of int
| Pm of int
| Pop of int
| Pom of int
| Print
| Read
| Razpo
| Block of bf
and bf = expr list
let exec =
let pointeur = ref 0 in
let tbl = Array.make 30000 0 in
let incremente n () = pointeur := !pointeur +n in
let decremente n () = pointeur := !pointeur -n in
let get() = tbl.(!pointeur) in
let incremente_octet n () = tbl.(!pointeur) <- get()+n in
let decremente_octet n () = tbl.(!pointeur) <- get()-n in
let view () = print_char (char_of_int (get())) in
let read () = tbl.(!pointeur) <- int_of_char (Scanf.scanf "%c" (fun c -> c)) in
let rec exec_expr = function
| Pp n -> incremente n()
| Pm n -> decremente n ()
| Pop n -> incremente_octet n()
| Pom n -> decremente_octet n()
| Razpo -> tbl.(!pointeur) <- 0
| Print -> view()
| Read -> read ()
| Block code ->
if get() <> 0 then
begin
exec' code;
if get() <> 0 then exec_expr (Block code)
end
and exec' code = List.iter exec_expr code
in
exec'
exception UnclosedP of int
exception UnopenedP of int
let parse =
let associations = [('>', Pp 1); ('<', Pm 1); ('+', Pop 1); ('-', Pom 1); ('.', Print); (',', Read)] in
let assoc_op char = List.assoc char associations in
(* Lis le code tant qu'il y a des opérateurs autres que [ et ] *)
let parse_op =
let rec parse_op' acc s i limit =
if i >= limit then (List.rev acc, limit)
else
match s.[i] with
| char when List.mem char ['>'; '<'; '+'; '-'; '.'; ','] ->
parse_op' (assoc_op char::acc) s (i+1) limit
| char when not (List.mem char ['['; ']']) ->
parse_op' acc s (i+1) limit
| _ -> (List.rev acc, i)
in parse_op' []
in
(* parse un crochet ou apelle parse_op *)
let rec parse_block s i limit =
if s.[i] = '[' then
let r, ni = parse [] s (i+1) limit in
if ni < limit && s.[ni] = ']' then
([Block r], ni+1)
else
raise (UnclosedP i)
else
parse_op s i limit
(* Apelle parse_block tant qu'il y a des blocks à consommer *)
and parse acc s i limit =
if i >= limit then (acc, limit)
else
let c, ni = parse_block s i limit in
if ni = i then (acc , i)
else
parse (acc@c) s ni limit
in
let parse_code s =
let size = String.length s in
let c, s = parse [] s 0 size in
if s < size then raise (UnopenedP s)
else c
in
parse_code
let optimise code =
let add = function
| Pp n -> Pp (n+1)
| Pm n -> Pm (n+1)
| Pop n -> Pop (n+1)
| Pom n -> Pom (n+1)
| _ -> failwith "bad code"
in
let compare_type = function
| Pp _, Pp _
| Pm _, Pm _
| Pop _, Pop _
| Pom _, Pom _ -> true
| _ -> false
in
let rle code =
let rec rle' e = function
| [] -> if e <> Pp 0 then [e] else []
| elem::l when compare_type (e, elem) && List.mem elem [Pp 1; Pm 1; Pop 1; Pom 1] -> rle' (add e) l
| (Block code)::l ->
let r = Block (rle' (Pp 0) code) :: (rle' (Pp 0) l) in
if e <> (Pp 0) then e::r else r
| elem::l ->
let r = rle' elem l in
if e <> (Pp 0) then e::r else r
in
rle' (Pp 0) code
in
(* optimise la remise à zéro de l'octet pointé [-]*)
let rec razpo = function
| [] -> []
| Block [Pom 1]::l -> Razpo::(razpo l)
| Block code::l -> Block (razpo code)::(razpo l)
| e::l -> e::razpo l
in
razpo (rle code)
(* ocaml a besoin d'un truc comme ça dans sa librairie *)
let read_file file =
let c = open_in file in
let rec aux acc =
try
aux (acc^(input_line c))
with End_of_file -> acc
in
aux ""
let _ =
init();
let code = read_file "test.bf" in
let bf = optimise (parse code) in
exec bf
Bon, je me suis dit "mon implémentation elle marche, mais elle met 1m58 à sortir le programme Mandelbrot (trouvé dans ce forum) alors que bf met un peu plus de 10 secondes (Linux, même PC). Y'a sans doute moyen de faire mieux".
Donc, un coup de profiler, et un autre, et un autre, et qu'est-ce qu'on découvre ?
Des optimisations efficaces :
On perds un temps monstrueux à chercher le crochet correspondant à chaque fois qu'on en trouve un. C'est ridicule, puisque brainfuck n'est pas auto-modifiant (vu que programme et données sont dans deux espaces mémoire séparés) ; donc la correspondance entre crochets est fixe. Y'a qu'à la calculer avant de lancer le programme, et hop ! ça va beaucoup plus vite !
Les listes et maps pour gérer la mémoire et le programme, c'est très "objet", mais quand on passe son temps à ne se servir que de ça (des millions d'appels, j'exagère pas) c'est pas très rapide. Donc, on remplace la gestion par des tableaux, et hop c'est plus rapide ! En plus c'est pas vraiment plus compliqué, sauf peut-être la fonction d'initialisation de la mémoire (et encore).
Là on arrive un peu à la limite de la chose : le profiler me dit que je passe surtout du temps (environ la moitié) dans la méthode principale, qui contient surtout un switch...
Comment améliorer ça ?
En tirant partie des propriétés du langage.On va transformer un peu le truc : au lieu d'avoir une série d'instructions, on va avoir une série d'instructions avec un paramètre chacune.
Au lieu d'écrire "+" n fois de suite, on va avoir une instruction "+" avec comme paramètre n : au lieu d'ajouter 1 n fois, on ajoute n une fois, ce qui prends approximativement n fois moins de temps
Seules les instructions "+" "-" ">" et "<" peuvent se chaîner.
Du coup on profite des paramètres pour les crochets "[" "]" : quand on est dans ce cas, le paramètre n'est plus le nombre de fois où il faut répéter l'opération, mais l'emplacement du crochet correspondant.
On évite une structure en plus (mais ça ne change pas grand-chose en fait).On remarque que du coup, on a plus besoin que de 6 symboles au lieu de 8 :
"-"(n) revient à faire "+"(-n)
"<"(n) revient à faire ">"(-n)
On gagne pratiquement rien en performances, mais un peu en simplicité dans le code du "compilateur".
La perte de temps à compiler est très largement compensée par le gain en rapidité : sur un programme très lourd comme celui qui affiche la GPL (plus d'1Mo de code BF...) on gagne encore du temps.
Plus d'optimisations ?
Là, je pense qu'on arrive au bout de ce qu'on peut faire en restant sur un interpréteur Java.
On peut encore gagner quelques pourcents en supprimant la gestion de la mémoire circulaire (~ 10 %) et des cases de mémoire circulaires (~ 10% aussi)
Des optimisations qui n'en sont pas
On peut sans doute faire mieux avec le "compilateur", mais en même temps on s'en fout : il n'est appellé qu'une fois, et est déjà très très rapide : ~ 3 ms sur mandelbrot, et 35 ms pour les Mo de code source du programme qui affiche la GPL.
Les astuces à la con comme coller des "final" partout, ça sert strictement à rien (dans ce genre de programme en tous cas)
Les "inline" en Java non plus (c'est pour ça que j'ai laissé les méthodes dans le switch de la version optimisée : on ne gagne rien à déplacer le corps des méthodes dans le switch)
Les "modulo" au lieu des "if" pour gérer la mémoire circulaire. J'ai mis des modulo parce que avec +n c'est plus simple à gérer qu'avec un if.
Le programme
Les commentaires ne sont pas spécialement à jour !
package info.kisai.brainfuck;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
/**
* Interpréteur BrainFuck
* @author SpaceFox
*/
public class BrainFuck {
// Paramètres de la machine
private int tailleMemoire;
private int tailleValeur;
// Variables
private char[] programme;
private StringBuilder sortie = new StringBuilder();
private char[] memoireTab;
private int pointeurMaxMemoire;
private char[] programmeCompile;
private int[] parametresCompile;
/**
* Constructeur unique.<br/>
* Initialise la mémoire et les tailles maximales.
* @param tailleMemoire la taille max de la mémoire, en cases. Aucune taille max si <code>null</code>.
* @param tailleValeur la taille max d'une case. Aucune taille max si <code>null</code>.
*/
public BrainFuck(Integer tailleMemoire, Integer tailleValeur) {
if (tailleMemoire == null) {
this.tailleMemoire = Integer.MAX_VALUE;
initMemoire(30000); // Purement arbitraire, sera augmenté si besoin
} else {
this.tailleMemoire = tailleMemoire;
initMemoire(tailleMemoire);
}
if (tailleValeur == null) {
this.tailleValeur = Character.MAX_VALUE;
} else {
this.tailleValeur = tailleValeur;
}
}
public void setProgramme(char[] programme) {
this.programme = programme;
}
public void setProgramme(String programme) {
setProgramme(programme.toCharArray());
}
/**
* Pour debug. Utile pour les versions étendues (verif de la transformation).
* @return le programme en brainfuck.
*/
public String getProgramme() {
return String.valueOf(programme);
}
/**
* Exécute le programme et renvoie le résultat sous forme de chaîne. Les entrées sont lues sur l'entrée passée en
* paramètre.
* @param entreeStream un flux d'entrée quelconque.
* @return le résultat du programme.
*/
public String execute(InputStream entreeStream) {
compile();
int longueurProgramme = programme.length;
int iInstruction = 0;
int pointeur = 0;
do {
switch (programmeCompile[iInstruction]) {
case '+':
case '-':
memoireTab[pointeur] = incrementeMemoire(pointeur, parametresCompile[iInstruction]);
break;
case '>':
case '<':
pointeur = incrementePointeur(pointeur, parametresCompile[iInstruction]);
break;
case '.':
sortie.append(getMemoireAt(pointeur));
break;
case ',':
memoireTab[pointeur] = litEntree(entreeStream);
break;
case '[':
iInstruction = sautConditionnelComp(iInstruction, pointeur);
break;
case ']':
iInstruction = retourConditionnelComp(iInstruction, pointeur);
break;
// Autres cas --> ignorés (commentaires)
}
// Pour debug
// System.out.println(
// " instruction n°" + iInstruction
// + " " + programmeCompile[iInstruction]
// + " (" + parametresCompile[iInstruction]
// + ") ==> pointeur " + pointeur
// + " --> valeur " + Integer.valueOf(memoireTab[pointeur]));
iInstruction++;
} while (iInstruction < longueurProgramme);
return sortie.toString();
}
private void compile() {
final int tailleProg = programme.length;
programmeCompile = new char[tailleProg];
parametresCompile = new int[tailleProg];
// Compilation
int iProg = 0;
int iComp = 0;
int compteur = 0;
char instr;
char instrPrec = '\u0000';
while (iProg < tailleProg) {
instr = programme[iProg];
// Instructions cumulables
if ( (instr != instrPrec)
&& (instrPrec == '+' || instrPrec == '-' || instrPrec == '>' || instrPrec == '<')
) {
programmeCompile[iComp] = instrPrec;
parametresCompile[iComp] = compteur;
iComp++;
compteur = 0;
}
// Instructions à ajouter direct
if (instr == '['|| instr == ']' || instr == '.' || instr == ',') {
programmeCompile[iComp] = instr;
iComp++;
compteur = 0;
}
// Modif du compteur si besoin
if (instr == '+' || instr == '>') {
compteur++;
}
else if (instr == '-' || instr == '<') {
compteur--;
}
instrPrec = instr;
iProg++;
}
// Correspondances
for (int iCrochetOuvrant = 0; iCrochetOuvrant < tailleProg; iCrochetOuvrant++) {
if (programmeCompile[iCrochetOuvrant] == '[') {
int nbCrochets = 1;
int iCrochetFermant = iCrochetOuvrant;
while (nbCrochets > 0) {
iCrochetFermant++;
if (programmeCompile[iCrochetFermant] == '[') {
nbCrochets++;
} else if(programmeCompile[iCrochetFermant] == ']') {
nbCrochets--;
}
}
// Correspondance [ --> ]
parametresCompile[iCrochetOuvrant] = iCrochetFermant;
// Correspondance ] --> [
parametresCompile[iCrochetFermant] = iCrochetOuvrant;
}
}
}
/**
* Récupère le caractère dans la mémoire. Initialise la mémoire jusqu'à ce pointeur si besoin.
* @param pointeur l'adresse de la case à récupérer.
* @return le contenu de cette case.
*/
private char getMemoireAt(int pointeur) {
if (pointeur > pointeurMaxMemoire) {
initMemoire(pointeur);
}
return memoireTab[pointeur];
}
/**
* Incrémente le pointeur de manière sécurisée.
* @param pointeur la valeur actuelle du pointeur.
* @return <code>pointeur + 1</code> ou <code>0</code> en cas de dépassement de la taille max de la mémoire.
*/
private int incrementePointeur(int pointeur, int i) {
return ((pointeur + i) % tailleMemoire);
}
/**
* Incrémente la valeur de la case mémoire de manière sécurisée.
* @param pointeur l'adresse de la case à incrémenter.
* @return <code>valeur + 1</code> ou <code>0</code> en cas de dépassement de la taille max d'une case.
*/
private char incrementeMemoire(int pointeur, int i) {
return (char) ((getMemoireAt(pointeur) + i) % tailleValeur);
}
/**
* Lit un caractère sur l'entrée.<br/>
* Un problème de lecture ne provoque pas d'erreur mais le caractère <code>0x0000</code>
* @param entreeStream le flux d'entrée sur lequel lire le caractère.
* @return le premier caractère de l'entrée, ou <code>0x0000</code> en cas d'erreur.
*/
private char litEntree(InputStream entreeStream) {
InputStreamReader entreeReader = new InputStreamReader(entreeStream);
char[] entree = new char[1];
try {
entreeReader.read(entree);
} catch (IOException e) {
entree[0] = 0;
}
return entree[0]; // La seule qui existe
}
/**
* Donne l'index de l'instruction suivante, selon le résultat du saut conditionnel.
* @param iInstruction l'index de l'instruction courante.
* @param pointeur le pointeur pour la condition
* @return l'index de l'instruction courante si la valeur à la case indiquée par le pointeur est différente de
* <code>0x0000</code>.<br/>
* L'index de l'instruction suivant le crochet fermant correspondant sinon.
*/
private int sautConditionnelComp(int iInstruction, int pointeur) {
if (getMemoireAt(pointeur) == 0) {
return parametresCompile[iInstruction];
}
return iInstruction;
}
/**
* Donne l'index de l'instruction suivante, selon le résultat du saut conditionnel.
* @param iInstruction l'index de l'instruction courante.
* @param pointeur le pointeur pour la condition
* @return l'index de l'instruction courante si la valeur à la case indiquée par le pointeur est égale à
* <code>0x0000</code>.<br/>
* L'index de l'instruction suivant le crochet ouvrant correspondant sinon.
*/
private int retourConditionnelComp(int iInstruction, int pointeur) {
if (getMemoireAt(pointeur) != 0) {
return parametresCompile[iInstruction];
}
return iInstruction;
}
/**
* Initialise la mémoire (remplissage par des 0) jusqu'à la taille indiquée.<br/>
* Seule la partie entre la taille courante et la taille spécifiée est initialisée, pour pouvoir agrandir la mémoire
* en cas de "mémoire infinie".<br/>
* Cette méthode ne fait rien si la taille voulue est plus petite que la taille actuelle.
* @param taille la taille voulue pour la mémoire.
*/
private void initMemoire(int taille) {
char[] newMemoireTab = new char[taille];
if (memoireTab == null) {
memoireTab = new char[taille];
}
System.arraycopy(memoireTab, 0, newMemoireTab, 0, memoireTab.length);
// Initialisation du reste
for (int i = memoireTab.length; i < taille; i++) {
newMemoireTab[i] = 0;
}
memoireTab = newMemoireTab;
pointeurMaxMemoire = memoireTab.length - 1;
}
}
Le main qui va bien :
package info.kisai.brainfuck;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
/**
*
* @author SpaceFox
*/
public class Main {
public static void main(String[] args) {
BrainFuck bf = new BrainFuck(30000, 256);
Scanner scanner;
try {
File file = new File(args[0]);
scanner = new Scanner(file);
StringBuilder sb = new StringBuilder((int) file.length());
while (scanner.hasNextLine()) {
sb.append(scanner.nextLine());
}
bf.setProgramme(sb.toString());
} catch (FileNotFoundException ex) {
System.out.println(ex);
}
System.out.println(bf.execute(System.in));
}
}
Il n'est même pas spécialement plus long que l'ancienne version, et mets environ 23 secondes à calculer le mandelbrot. Soit mieux que 5x plus rapide (et toujours 2.3x plus lent que bf).
Et c'est là qu'on apprécie la puissance de l'objet : les programme Ook et Spoon profitent pleinement des améliorations sans avoir besoin de changer une ligne de code !
Et c'est là qu'on apprécie la puissance de l'objet : les programme Ook et Spoon profitent pleinement des améliorations sans avoir besoin de changer une ligne de code !
Excuse moi, mais ça n'a rien à voir avec la programmation orientée objet. La réutilisation dans ton cas vient du fait que tu traduis les programmes Ook et Spoon en des programmes BF avant de lancer l'implémentation BF dessus. Ça n'utilise aucune des spécificités de la POO et on peut le faire dans n'importe quel langage.
Le fait de traduire ça dans ton implémentation par l'héritage d'une classe et d'utiliser un effet de bord dans le constructeur pour changer le contenu du programme au vol est au mieux un idiotisme, probablement une lourdeur, et au pire un défaut de conception.
hedi07, robocop > ça fait sans doute doublon avec ce que vous avez déjà fait, mais j'ai écrit un sujet pour écrire un interprète BF en Caml Light, à faire en deux heures pour des débutants. Ça marche bien, ils arrivent en général à avoir l'interpréteur et le parseur fonctionnels à la fin de l'heure (donc tout sauf les questions d'optimisation de la fin) : http://bluestorm.info/tmp/tp6.pdf
Le sujet pourrait vous intéresser (structure du code, etc.).
Certes, la phrase était nulle, ça n'a effectivement rien à voir avec la POO.
Si, dans le sens où on peut utiliser Spoon et Ook comme des BrainFuck, ce qu'ils sont exactements (philosophie de la chose).
BrainFuck bf = new Ook();
bf.setProgramme("blabla");
Les possibilités d'application sont néanmoins très réduites
Par contre je vois pas le rapport avec un quelconque "effet de bord dans le constructeur" ?
Je suis d'accord que c'était pas la manière la plus propre ni la plus efficace (en même temps j'ai fait ça à l'arrache à 1h du mat en semaine) ; mais elle fonctionne et est cohérente :
- Les langages Spoon et Ook sont des Brainfuck (une autre écriture).
- setProgramme définit le programme. Qu'en interne il soit en représentation Ook ou Brainfuck ou Spoon ou n'importe quoi d'autre... de toutes façons il est réinterprété derrière.
Quoiqu'il en soit, c'est pas ce que je considère d'important dans mes posts ; c'était juste "pour le fun".
Par contre si t'as des commentaires à faire sur l'interpréteur et surtout sur sa version optimisée, je suis déjà plus intéressé
hedi07, robocop > ça fait sans doute doublon avec ce que vous avez déjà fait, mais j'ai écrit un sujet pour écrire un interprète BF en Caml Light, à faire en deux heures pour des débutants. Ça marche bien, ils arrivent en général à avoir l'interpréteur et le parseur fonctionnels à la fin de l'heure (donc tout sauf les questions d'optimisation de la fin) : http://bluestorm.info/tmp/tp6.pdf
Le sujet pourrait vous intéresser (structure du code, etc.).
Merci pour le lien, finalement je suis arrivé à quelque chose de très similaire de ce que tu proposes (en moins bien quand même :d). Enfin, y'a ptet pas dix milles façon de faire non plus.
Voilà qui est fort étrange.
J'ai fait une version qui "compile" en Java ; i.e. qui transforme le programme BrainFuck en programme Java, à partir de la "pseudo-compilation" de ma version optimisée.
Eh bien cette version "compilée" est deux fois plus lente que l'interpréteur optimisé, sans tenir compte du temps de compilation...
--
En fait c'est simple : au lieu d'avoir un code rapide pour tous les programmes, la compilation génère un trop gros fichier .java pour que ça ait un intérêt quelconque.
L'exemple ultime est le (très mauvais) programme qui affiche la GPL : le .java fait 7.05 Mo...
(Ce programme est horrible : je fais des + pour avoir le code du caractère, je l'affiche, je fais une boucle pour le réinitialiser à 0, je fais des + pour avoir le suivant, ... et ce pour tous les caractères de la GPL !)
Les + - > < à répétitions, aucun problème de gestion.
Par contre le coup des [-] à répétition dans le code "GPL" pour remettre à zéro l'unique case mémoire utilisée, c'était pas prévu que ce soit autant utilisé
Tiens, je vais implémenter leur détection dans mon code voir si on peut encore gagner des trucs.
Nettoyage du code avant compilation (pour éviter les interférences avec les caractères de commentaires).
Les tableaux programmes "compilés" font maintenant la taille réelle, et pas la taille du programme d'origine avec plein de cases vides.
Détection de la remise à 0 d'une case, pattern [-]
Détection de l'addition : m[1] = m[0] + m[1] et m[0] = 0 ; pattern [->+<]
Détection de la copie d'octet : m[1] = m[0] et m[0] = 0 ; pattern >[-]<[->+<]
Ces améliorations peuvent avoir (temps du programme complet : chargement + traitement + exécution + affichage) :
Aucune conséquence sur un code pathologique comme celui de la GPL, parce qu'on passe un temps "monstrueux" sur le pré-traitement qui enlève tout bénéfice de l'optimisation pourtant brutale (1,8 s)
Pratiquement aucune conséquence sur un code comme mandelbrot.b (20.9 secondes avant, 20.1 seconde maintenant) (utilise peu les cas
Des conséquences astronomiques sur un programme comme hanoi.br, qui utilise très massivement la réinitialisation d'une case (plusieurs dizaines de millions de fois, j'ai la fin d'attendre la fin du profiling) (26 s avant, 2 s maintenant, et 5 minutes 30 avec la première version présentée...)
Le code (d'une propreté douteuse) :
package info.kisai.brainfuck;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
/**
* Interpréteur BrainFuck
* @author SpaceFox
*/
public class BrainFuck {
// Paramètres de la machine
private int tailleMemoire;
private int tailleValeur;
// Variables
private char[] programme;
private StringBuilder sortie = new StringBuilder();
private char[] memoireTab;
private int pointeurMaxMemoire;
private char[] programmeCompile;
private int[] parametresCompile;
/**
* Constructeur unique.<br/>
* Initialise la mémoire et les tailles maximales.
* @param tailleMemoire la taille max de la mémoire, en cases. Aucune taille max si <code>null</code>.
* @param tailleValeur la taille max d'une case. Aucune taille max si <code>null</code>.
*/
public BrainFuck(Integer tailleMemoire, Integer tailleValeur) {
if (tailleMemoire == null) {
this.tailleMemoire = Integer.MAX_VALUE;
initMemoire(30000); // Purement arbitraire, sera augmenté si besoin
} else {
this.tailleMemoire = tailleMemoire;
initMemoire(tailleMemoire);
}
if (tailleValeur == null) {
this.tailleValeur = Character.MAX_VALUE;
} else {
this.tailleValeur = tailleValeur;
}
}
public void setProgramme(char[] programme) {
this.programme = programme;
}
public void setProgramme(String programme) {
setProgramme(programme.toCharArray());
}
/**
* Pour debug. Utile pour les versions étendues (verif de la transformation).
* @return le programme en brainfuck.
*/
public String getProgramme() {
return String.valueOf(programme);
}
/**
* Exécute le programme et renvoie le résultat sous forme de chaîne. Les entrées sont lues sur l'entrée passée en
* paramètre.
* @param entreeStream un flux d'entrée quelconque.
* @return le résultat du programme.
*/
public String execute(InputStream entreeStream) {
compile();
int longueurProgramme = programmeCompile.length;
int iInstruction = 0;
int pointeur = 0;
do {
switch (programmeCompile[iInstruction]) {
case '+':
case '-':
memoireTab[pointeur] = incrementeMemoire(pointeur, parametresCompile[iInstruction]);
break;
case '>':
case '<':
pointeur = incrementePointeur(pointeur, parametresCompile[iInstruction]);
break;
case '0':
resetMemoire(pointeur);
break;
case 'a':
addition(pointeur);
break;
case 'm':
copie(pointeur);
break;
case '.':
// sortie.append(getMemoireAt(pointeur));
System.out.print(getMemoireAt(pointeur));
break;
case ',':
memoireTab[pointeur] = litEntree(entreeStream);
break;
case '[':
iInstruction = sautConditionnelComp(iInstruction, pointeur);
break;
case ']':
iInstruction = retourConditionnelComp(iInstruction, pointeur);
break;
// Autres cas --> ignorés (commentaires)
}
// Pour debug
// System.out.println(
// " instruction n°" + iInstruction
// + " " + programmeCompile[iInstruction]
// + " (" + parametresCompile[iInstruction]
// + ") ==> pointeur " + pointeur
// + " --> valeur " + Integer.valueOf(memoireTab[pointeur]));
iInstruction++;
} while (iInstruction < longueurProgramme);
return sortie.toString();
}
private void compile() {
char[] progSansComm = preProcesseur(supprimeCommentaires());
final int tailleProg = progSansComm.length;
char[] progTmp = new char[tailleProg];
int[] paramTmp = new int[tailleProg];
// Compilation
int iProg = 0;
int tailleProgComp = 0;
int compteur = 0;
char instr;
char instrPrec = '\u0000';
while (iProg < tailleProg) {
instr = progSansComm[iProg];
// Instructions cumulables
if ( (instr != instrPrec)
&& (instrPrec == '+' || instrPrec == '-' || instrPrec == '>' || instrPrec == '<')
) {
progTmp[tailleProgComp] = instrPrec;
paramTmp[tailleProgComp] = compteur;
tailleProgComp++;
compteur = 0;
}
// Instructions à ajouter direct
if ( instr == '['|| instr == ']' || instr == '.' || instr == ','
|| instr == '0' || instr == 'a' || instr == 'm') {
progTmp[tailleProgComp] = instr;
tailleProgComp++;
compteur = 0;
}
// Modif du compteur si besoin
if (instr == '+' || instr == '>') {
compteur++;
}
else if (instr == '-' || instr == '<') {
compteur--;
}
instrPrec = instr;
iProg++;
}
// Correspondances
for (int iCrochetOuvrant = 0; iCrochetOuvrant < tailleProgComp; iCrochetOuvrant++) {
if (progTmp[iCrochetOuvrant] == '[') {
int nbCrochets = 1;
int iCrochetFermant = iCrochetOuvrant;
while (nbCrochets > 0) {
iCrochetFermant++;
if (progTmp[iCrochetFermant] == '[') {
nbCrochets++;
} else if(progTmp[iCrochetFermant] == ']') {
nbCrochets--;
}
}
// Correspondance [ --> ]
paramTmp[iCrochetOuvrant] = iCrochetFermant;
// Correspondance ] --> [
paramTmp[iCrochetFermant] = iCrochetOuvrant;
}
}
// Copie dans les tableaux généraux
programmeCompile = new char[tailleProgComp];
parametresCompile = new int[tailleProgComp];
System.arraycopy(progTmp, 0, programmeCompile, 0, tailleProgComp);
System.arraycopy(paramTmp, 0, parametresCompile, 0, tailleProgComp);
// System.out.println("Taille compilée : " + tailleProgComp);
}
/**
* Récupère le caractère dans la mémoire. Initialise la mémoire jusqu'à ce pointeur si besoin.
* @param pointeur l'adresse de la case à récupérer.
* @return le contenu de cette case.
*/
private char getMemoireAt(int pointeur) {
if (pointeur > pointeurMaxMemoire) {
initMemoire(pointeur);
}
return memoireTab[pointeur];
}
/**
* Incrémente le pointeur de manière sécurisée.
* @param pointeur la valeur actuelle du pointeur.
* @return <code>pointeur + 1</code> ou <code>0</code> en cas de dépassement de la taille max de la mémoire.
*/
private int incrementePointeur(int pointeur, int i) {
return ((pointeur + i) % tailleMemoire);
}
/**
* Incrémente la valeur de la case mémoire de manière sécurisée.
* @param pointeur l'adresse de la case à incrémenter.
* @return <code>valeur + 1</code> ou <code>0</code> en cas de dépassement de la taille max d'une case.
*/
private char incrementeMemoire(int pointeur, int i) {
return (char) ((getMemoireAt(pointeur) + i) % tailleValeur);
}
/**
* Lit un caractère sur l'entrée.<br/>
* Un problème de lecture ne provoque pas d'erreur mais le caractère <code>0x0000</code>
* @param entreeStream le flux d'entrée sur lequel lire le caractère.
* @return le premier caractère de l'entrée, ou <code>0x0000</code> en cas d'erreur.
*/
private char litEntree(InputStream entreeStream) {
InputStreamReader entreeReader = new InputStreamReader(entreeStream);
char[] entree = new char[1];
try {
entreeReader.read(entree);
} catch (IOException e) {
entree[0] = 0;
}
return entree[0]; // La seule qui existe
}
/**
* Donne l'index de l'instruction suivante, selon le résultat du saut conditionnel.
* @param iInstruction l'index de l'instruction courante.
* @param pointeur le pointeur pour la condition
* @return l'index de l'instruction courante si la valeur à la case indiquée par le pointeur est différente de
* <code>0x0000</code>.<br/>
* L'index de l'instruction suivant le crochet fermant correspondant sinon.
*/
private int sautConditionnelComp(int iInstruction, int pointeur) {
if (getMemoireAt(pointeur) == 0) {
return parametresCompile[iInstruction];
}
return iInstruction;
}
/**
* Donne l'index de l'instruction suivante, selon le résultat du saut conditionnel.
* @param iInstruction l'index de l'instruction courante.
* @param pointeur le pointeur pour la condition
* @return l'index de l'instruction courante si la valeur à la case indiquée par le pointeur est égale à
* <code>0x0000</code>.<br/>
* L'index de l'instruction suivant le crochet ouvrant correspondant sinon.
*/
private int retourConditionnelComp(int iInstruction, int pointeur) {
if (getMemoireAt(pointeur) != 0) {
return parametresCompile[iInstruction];
}
return iInstruction;
}
/**
* Initialise la mémoire (remplissage par des 0) jusqu'à la taille indiquée.<br/>
* Seule la partie entre la taille courante et la taille spécifiée est initialisée, pour pouvoir agrandir la mémoire
* en cas de "mémoire infinie".<br/>
* Cette méthode ne fait rien si la taille voulue est plus petite que la taille actuelle.
* @param taille la taille voulue pour la mémoire.
*/
private void initMemoire(int taille) {
char[] newMemoireTab = new char[taille];
if (memoireTab == null) {
memoireTab = new char[taille];
}
System.arraycopy(memoireTab, 0, newMemoireTab, 0, memoireTab.length);
// Initialisation du reste
for (int i = memoireTab.length; i < taille; i++) {
newMemoireTab[i] = 0;
}
memoireTab = newMemoireTab;
pointeurMaxMemoire = memoireTab.length - 1;
}
private char[] supprimeCommentaires() {
// System.out.println("Taille avec commentaires : " + programme.length);
char[] tmp = new char[programme.length];
int progTailleSansComm = 0;
for (char c : programme) {
if (c == '+' || c == '-' || c == '>' || c == '<' || c == '[' || c == ']' || c == '.' || c == ',') {
tmp[progTailleSansComm++] = c;
}
}
char[] retour = new char[progTailleSansComm];
System.arraycopy(tmp, 0, retour, 0, progTailleSansComm);
// System.out.println("Taille sans commentaires : " + progTailleSansComm);
return retour;
}
private char[] preProcesseur(char[] supprimeCommentaires) {
String str = new String(supprimeCommentaires);
// System.out.println("Avant préprocesseur : " + str);
// RAZ cellule
str = str.replaceAll("\\[-\\]", "0");
// Addition
str = str.replaceAll("\\[->\\+<\\]", "a");
// Déplacement
str = str.replaceAll(">\\[-\\]<\\[->\\+<\\]", "m");
// System.out.println("Après préprocesseur : " + str);
return str.toCharArray();
}
private void resetMemoire(int pointeur) {
memoireTab[pointeur] = 0;
}
private void addition(int pointeur) {
memoireTab[pointeur + 1] += memoireTab[pointeur];
memoireTab[pointeur] = 0;
}
private void copie(int pointeur) {
memoireTab[pointeur + 1] = memoireTab[pointeur];
memoireTab[pointeur] = 0;
}
}
PS : \o/ dans le cas des tours de Hanoï, mon code va 2x plus vide que l'implémentation bf !
J'ai regardé les pages de cette longue discussion et il ne me semble pas avoir vu d'interpréteur en Prolog. Ce grave manque est donc réparé.
J'utilise la base de données intégrée à Prolog pour simuler le tableau de valeurs (cell(N, V)).
Le parsing des instructions bf est fait à l'aide des DCG.
Ces DCG étudiant la chaine entrée, lisent caractère par caractère et "oublient" ce qui est lu. Il y a donc deux parties dans le code, une partie pour tout ce qui est hors boucle (bf : on lit puis on oublie), et une partie pour le contenu des boucles (bfmemo : on lit et on mémorise les commandes).
Le programme peut lire stdin, ou on peut lancer bf avec une string en argument.
Il plante après le calcul du carré de 97 (test Bluestorm) par dépassement de la pile.
J'ai ajouté à la fin quelques exemples de code.
:- dynamic ptr/1.
:- dynamic cell/2.
:- dynamic memo/2.
% le predicat qui lit stdin.
bfread :-
writeln('Tapez votre code entre quote ('') suivi d''un point'),
read(A),
atom_codes(A, L),
bf(L).
% le prédicat bf qui prend une chaine en argument
bf(L) :-
maplist(char_code, L1, L),
writef('%s\n', [L]),
retractall(ptr(_)),
retractall(cell(_,_)),
% pour la memorisation des codes de boucle
retractall(memo(_,_)),
% on cree le pointeur index dans le tableau, initialise a 0.
assert(ptr(0)),
% on cree le tableau de 30 000 valeurs initialisees à 0
forall(between(0, 30000, I), assert(cell(I, 0))),
bf(L1, _, _).
% le parsing des commandes hors boucle
bf(['>'|B]) -->
{incrptr},
bf(B).
bf(['<'|B]) -->
{decrptr},
bf(B).
bf(['+'|B]) -->
{incrcell},
bf(B).
bf(['-'|B]) -->
{decrcell},
bf(B).
bf(['.'|B]) -->
{putchar},
bf(B).
bf([','|B]) -->
{getchar},
bf(B).
% on rencontre un début de boucle,
bf(['['|B]) -->
{% on doit sauter au ']' suivant
carnull,
% on n'a pas besoin de mémoriser le saut
skip(B, 0, U-U, _T, B1)},
bf(B1).
% on rencontre un début de boucle,
bf(['['|B]) -->
{% ici on commence la boucle, il faut memoriser les caracteres lus
\+ carnull,
% on est au premier niveau d'imbrication de boucle
% on n'a pas de code de boucle a memoriser
asserta(memo(0, X-X))},
% utilisation des differences-listes
% pas de code mémorise, donc liste vide symbolisee par U-U en "ecriture dl".
bfmemo(B, U-U).
% tout caractere inconnu est considere comme commentaire donc oublie
bf([_|B]) -->
bf(B).
% quand c'est fini, c'est fini
bf([]) --> [].
% le parsing des commandes de boucle
% Il faut les mémoriser
bfmemo(['>'|B], T) -->
{incrptr,
append_dl(T, ['>' | U]-U, T1)},
bfmemo(B, T1).
bfmemo(['<'|B], T) -->
{decrptr,
append_dl(T, ['<' | U]-U, T1)},
bfmemo(B, T1).
bfmemo(['+'|B], T) -->
{incrcell,
append_dl(T, ['+' | U]-U, T1)},
bfmemo(B, T1).
bfmemo(['-'|B], T) -->
{decrcell,
append_dl(T, ['-' | U]-U, T1)},
bfmemo(B, T1).
bfmemo(['.'|B], T) -->
{putchar,
append_dl(T, ['.' | U]-U, T1)},
bfmemo(B, T1).
bfmemo([','|B], T) -->
{getchar,
append_dl(T, [',' | U]-U, T1)},
bfmemo(B, T1).
bfmemo(['['|B], T) -->
{% le caractere pointe est null, on saute
% et on memorise la partie sautee
carnull,
skip(B, 0, ['['|W]-W, SF, B1),
append_dl(T, SF, T1)
},
bfmemo(B1, T1).
bfmemo(['['|B], T) -->
{
% le caractere pointé est non null
\+carnull,
append_dl(T, ['['|U]-U, T1),
memo(N, _),
N1 is N+1,
% on debute une nouvelle boucle
% on memorise le debut de la precedente boucle
asserta(memo(N1, T1))
},
bfmemo(B, V-V).
bfmemo([']'|B], T) -->
{
% Si l'octet pointe est null, on continue
carnull,
% on recupere les donnees memorisees
memo(N, L),
% ici on n'est pas au niveau 0
N \= 0, !,
% on efface le niveau
retract(memo(N,L)),
append_dl(T, [']'|U]-U, T1),
append_dl(L, T1, T2)
},
% on continue en bfmemo
bfmemo(B, T2).
bfmemo([']'|B], _T) -->
{
% Si l'octet pointe est null, on continue
carnull,
% on recupere les donnees memorisees
memo(N, L),
% ici on est au niveau 0
N = 0, !,
% on efface tout
retract(memo(N,L))
},
% on continue en bf
bf(B).
bfmemo([']'|B], T) -->
{
% ici on repart au debut de la boucle
\+ carnull,
% on recree la liste des donnees à partir du debut de la boucle
append_dl(T, [']'|V]-V, T1-[]),
append(T1, B, T2)
},
bfmemo(T2, U-U).
% tout caractère inconnu est ignore
bfmemo([_C|B], T) -->
bfmemo(B, T).
% la concatenation des differences-listes, en temps constant !
append_dl(X1-X2, X2-X3, X1-X3).
% skip(Liste, Niveau SC, SR, LR)
% Permet le saut au ']' suivant
% Liste : la liste a travailler
% Niveau : niveau d'imbrication des []
% SC : dl-partie a sauter en construction
% SR : dl-partie a sauter resultat
% LR : Liste resultat restant a etudier
% on termine la recherche
skip([']'|B], 0, SC, ST, B) :-
append_dl(SC, [']'|U]- U, ST).
% on baisse d'un niveau d'imbrication
skip([']'|B], N, SC, ST, BF) :-
N1 is N-1,
append_dl(SC, [']'|U]- U, SC1),
skip(B, N1, SC1, ST, BF).
% on augmente le niveau d'imbrication
skip(['['|B], N, SC, ST, BF) :-
N1 is N+1,
append_dl(SC, ['['|U]- U, SC1),
skip(B, N1, SC1, ST, BF).
skip([A|B], N, SC, ST, BF) :-
append_dl(SC, [A|U]- U, SC1),
skip(B, N, SC1, ST, BF).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Les primitives du langage
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
incrptr :-
retract(ptr(N)),
N1 is N+1,
assert(ptr(N1)).
decrptr :-
retract(ptr(N)),
N1 is N-1,
assert(ptr(N1)).
incrcell :-
ptr(N),
retract(cell(N, V)),
V1 is (V+1) mod 256,
assert(cell(N, V1)).
decrcell :-
ptr(N),
retract(cell(N, V)),
V1 is V-1,
assert(cell(N, V1)).
putchar :-
ptr(N),
cell(N, V),
char_code(A, V),
write(A).
getchar :-
ptr(N),
retract(cell(N, _)),
read(A),
( number(A) -> number_codes(A, [V]); char_code(A,V)),
assert(cell(N, V)).
% la valeur courante est-elle nulle
carnull :-
ptr(N),
cell(N, 0).
% quelques prog d'exemples
bf_test :-
/*
writeln('Hello World !'),
L = "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++
.<<+++++++++++++++.>.+++.------.--------.>+.>.",
*/
/*
writeln('Addition'),
L = ",>++++++[<-------->-],[<+>-]<.",
*/
/*
writeln('Multiplication'),
L = ",>,>++++++++[<------<------>>-]<<[>[>+>+<<-]>>[<<+>>-]<<<-]
>>>++++++[<++++++++>-]<.>.",
*/
/*
writeln('Affiche le caractère entre'),
L = ",[.,]",
*/
/*
writeln('Mise en majuscule de la saisie'),
L = ",----------[----------------------.,----------]",
*/
/*
writeln('recherche du minimum de deux nombres'),
L = ",>,[->>+<<]+<[->>>[>>>>>+<<<<<->+<<]<[>]>>>>>[-<<->>>>>>>]<[>]<<<<<<]>[>>>>->]<<<<<<[-]>[-]>>[-]>.",
*/
writeln('Calcul des nombres de Fibonacci'),
L =">++++++++++>+>+[[+++++[>++++++++<-]>.<++++++[>--------<-]+<<<]>.>>[
[-]<[>+<-]>>[<<+>+>-]<[>+<-[>+<-[>+<-[>+<-[>+<-[>+<-
[>+<-[>+<-[>+<-[>[-]>+>+<<<-[>+<-]]]]]]]]]]]+>>>]<<<]",
/*
writeln('Test BlueStorm sur les carres '),
L = "+++++++++++++++++++++++++[>+++++<-]>[<+++++>-]+<+[>[>+>+<<-]++>>[<<+>>-]>>>[-]++>[-]+>>>+[[-]++++++>>>]<<<[[<++++++++<++>>-]+<.<[>----<-]<]<<[>>>>>[>>>[-]+++++++++<[>-<-]+++++++++>[-[<->-]+[<<<]]<[>+<-]>]<<-]<<-]",
*/
bf(L).
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Deuxième version, avec une analyse de la chaine d'entrée pour repérer les boucles et les extraire. Cela évite les problème de recopie de la version précédente et donne un programme plus simple mais qui plante toujours après le calcul du carré de 97.
Il va plus loin par contre pour le calcul des nombres de Fibonacci (il plante après le calcul d'un nombre de 41 chiffres).
Les boucles sont numérotées et remplacées par leur numéro dans le code :
Test BlueStorm
[+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,[,>,+,+,+,+,+,<,-,],>,[,<,+,+,+,+,+,>,-,],+,<,+,[,>,[,>,+,>,+,<,<,-,],+,+,>,>,[,<,<,+,>,>,-,],>,>,>,[,-,],+,+,>,[,-,],+,>,>,>,+,[,[,-,],+,+,+,+,+,+,>,>,>,],<,<,<,[,[,<,+,+,+,+,+,+,+,+,<,+,+,>,>,-,],+,<,.,<,[,>,-,-,-,-,<,-,],<,],<,<,[,>,>,>,>,>,[,>,>,>,[,-,],+,+,+,+,+,+,+,+,+,<,[,>,-,<,-,],+,+,+,+,+,+,+,+,+,>,[,-,[,<,-,>,-,],+,[,<,<,<,],],<,[,>,+,<,-,],>,],<,<,-,],<,<,-,]]
% le prédicat bf qui prend une string en argument
bf_etudie(L) :-
maplist(char_code, L1, L),
write(L1), nl,
% Analyse de la chaine pour en extraire les boucles/sous boucles
% le retour est la liste qui sera lancée au début.
retractall(code_boucle(_,_)),
retractall(num_boucle(_)),
assert(num_boucle(0)),
analyse(L1, 0, V-V, L2),
retractall(ptr(_)),
retractall(cell(_,_)),
assert(ptr(0)),
forall(between(0, 30000, I), assert(cell(I, 0))),
bf(L2).
% l'interpreteur est maintenant tres simple
bf(L) :-
maplist(bfcar, L).
% le parsing des commandes
bfcar('>'):-
incrptr.
bfcar('<') :-
decrptr.
bfcar('+') :-
incrcell.
bfcar('-') :-
decrcell.
bfcar('.') :-
putchar.
bfcar(',') :-
getchar.
% on rencontre un début de boucle,
bfcar(N) :-
% ici on commence une boucle, si le caractère pointé est non null
carnonnull,
code_boucle(N, L),
bf(L),
% une fois l'exécution de la boucle terminee
% on teste si on doit la refaire
bfcar(N).
% si le caractère pointe est null
% on termine tout simplement l'execution de la boucle
% en revenant au precedant bf.
bfcar(_).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Extraction des boucles/sous boucles de la chaine
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% analyse([L, N, T, R)
% L : la liste à étuider
% N : le numero de boucle etudiee
% T : Le code de la boucle
% R : la liste restant après la fin de la boucle
analyse([], 0, T-[], T).
% on rencontre une nouvelle boucle
analyse(['[' | B], N, TC, TF) :-
% on lit le numero de cette boucle
retract(num_boucle(NB)),
append_dl(TC, [NB | U]-U, T1),
% on creee le prochain numero
NB1 is NB + 1,
assert(num_boucle(NB1)),
analyse(B, NB, V-V, B1),
analyse(B1, N, T1, TF).
% la fin de la boucle est trouvee
% on enregistre son numero et son code
analyse([']' | B], N, TC-[], B) :-
assert(code_boucle(N, TC)).
% on s'assure que le caractre est valide
analyse([C | B], N, T1, BF) :-
member(C, [+, -, <, >, ',', '.']),
append_dl(T1, [C|U]-U, T2),
analyse(B, N, T2, BF).
% sinon on le saute tout simplement
analyse([_C | B], N, T1, BF) :-
analyse(B, N, T1, BF).
% la concaténation des differences-listes, en temps constant !
append_dl(X1-X2, X2-X3, X1-X3).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Les primitives du langage
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
incrptr :-
retract(ptr(N)),
N1 is N+1,
assert(ptr(N1)).
decrptr :-
retract(ptr(N)),
N1 is N-1,
assert(ptr(N1)).
incrcell :-
ptr(N),
retract(cell(N, V)),
V1 is (V+1) mod 256,
assert(cell(N, V1)).
decrcell :-
ptr(N),
retract(cell(N, V)),
V1 is V-1,
assert(cell(N, V1)).
putchar :-
ptr(N),
cell(N, V),
char_code(A, V),
write(A).
getchar :-
ptr(N),
retract(cell(N, _)),
read(A),
( number(A) -> number_codes(A, [V]); char_code(A,V)),
assert(cell(N, V)).
% la valeur courante est-elle nulle
carnonnull :-
ptr(N),
cell(N, V),
V \= 0.
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Ta version fait des effets de bord : tu construis un tableau indexé par des entiers, qui associe à des "numéros de boucle" une forme parsée de la boucle.
Je pense que tu pourrais reconstruire ton application : au lieu d'une première passe faisant des effets de bord pour stocker dans des variables globales des informations sur les boucles, tu pourrais faire une passe qui construit une deuxième représentation du code BF, plus adaptée, où les boucles sont considérées comme des données à part entière (qui contiennent elles-même du code, bien sûr), et donc avec les mêmes avantages que ta solution actuelle pour l'interprétation du code derrière.
Par exemple, tu pourrais t'inspirer de la représentation de 98111 (dans son code Haskell) :
--- Represent a brainfuck instruction
data Op = Add Integer -- A sequence of + or -
| Get -- .
| Move Integer -- A sequence of < or >
| Put -- ,
| Loop [Op] -- []
deriving (Eq, Show)
--- A brainfuck program, or a fragment of it
type Program = [Op]
Remarque : en Haskell, le type noté [t] est le type des listes d'éléments de type t. Ici Op désigne une opération brainfuck, et les boucles Loop [Op] contiennent donc des listes d'opération brainfuck.
Il a aussi remplacé les séquences de déplacements ou de modifications par des opérations plus atomiques (Add 3 pour +-++-++ par exemple), mais ce n'est pas nécessaire, je parlais spécifiquement du traitement des boucles.
J'ai suivi tes conseils et j'ai aussi compacté le code aussi, (+++ -> incrcell(3) par exemple, et les [-] sont remplacées par des raz).
J'arrive à une version nettement plus performante. Ton test s'arrête à 12769 (le carré de 113) avec true, je pense que c'est ce qui est voulu.
Le calcul des nombres de Fibonacci lui plante après le calcul d'un nombre de 132 chiffres.
Voici ce que donne le test sur les carrés
Test BlueStorm
[+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,+,[,>,+,+,+,+,+,<,-,],>,[,<,+,+,+,+,+,>,-,],+,<,+,[,>,[,>,+,>,+,<,<,-,],+,+,>,>,[,<,<,+,>,>,-,],>,>,>,[,-,],+,+,>,[,-,],+,>,>,>,+,[,[,-,],+,+,+,+,+,+,>,>,>,],<,<,<,[,[,<,+,+,+,+,+,+,+,+,<,+,+,>,>,-,],+,<,.,<,[,>,-,-,-,-,<,-,],<,],<,<,[,>,>,>,>,>,[,>,>,>,[,-,],+,+,+,+,+,+,+,+,+,<,[,>,-,<,-,],+,+,+,+,+,+,+,+,+,>,[,-,[,<,-,>,-,],+,[,<,<,<,],],<,[,>,+,<,-,],>,],<,<,-,],<,<,-,]]
% le prédicat brainfuck qui prend une string en argument
bf_etudie(L) :-
maplist(char_code, L1, L),
write(L1), nl,
% Analyse de la chaine pour compacter le code.
% Un code bf ne peut commencer par un crochet ouvrant !
L1 = [H | T],
passe_1(T, [H,1], V-V, L2),
% Analyse de la chaine pour en extraire les boucles/sous boucles
% le retour est la liste qui sera lancée au début.
passe_2(L2, U-U, L3, _),
% Analyse de la chaine pour certaines améliorations ponctuelles
% exemple (la seule pour le moment)
% boucle([decrcell(1)]) --> raz remise a zero d'une cellule
maplist(passe_3, L3, L4),
retractall(ptr(_)),
retractall(cell(_,_)),
assert(ptr(0)),
forall(between(0, 30000, I), assert(cell(I, 0))),
bf(L4).
bf(L) :-
maplist(call, L).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Compactage du code
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% passe_1([L, [C,N], TF, R)
% L : la liste à étudier
% [C, N] : caractère deja rencontre
% T : Le code compacte en construction
% Tf : le code compacte final
passe_1([], B, T, T1) :-
( B = [] -> append_dl(T, []-[], T1-[]);
code(B, Code),
append_dl(T, [Code]-[], T1-[])).
passe_1([C | T], B, TF, TR) :-
member(C, ['[', ']']), !,
(B = [H, N] ->
code([H, N], Code),
append_dl(TF, [Code, C|U]-U, TF1);
append_dl(TF, [C|V]-V, TF1)),
passe_1(T, [], TF1, TR).
passe_1([C | T], B, TF, TR) :-
\+member(C, [+, -, <, >, ',', '.']), !,
passe_1(T, B , TF, TR).
passe_1([H | T], [H, N], TF, TR) :-
N1 is N+1,
passe_1(T, [H, N1], TF, TR).
passe_1([H1 | T], [H2, N], TF, TR) :-
code([H2, N], Code),
append_dl(TF, [Code | U]-U, TF1),
passe_1(T, [H1, 1], TF1, TR).
passe_1([H | T], [], TF, TR) :-
passe_1(T, [H, 1], TF, TR).
code([+, N], incrcell(N)).
code([-, N], decrcell(N)).
code([>, N], incrptr(N)).
code([<, N], decrptr(N)).
code(['.', N], putchar(N)).
code([',', N], getchar(N)).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Extraction des boucles/sous boucles de la chaine
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% passe_2([L, T, TF, R)
% L : la liste à étudier
% T : Le code de la boucle en construction
% Tf : le code final de la boucle
% R : la liste restant après la fin de la boucle
passe_2([], T-[], T, []).
% on rencontre une nouvelle boucle
passe_2(['[' | B], TC, TF, BF) :-
passe_2(B, V-V, NTF, B1),
append_dl(TC, [boucle(NTF)|U]-U, T1),
passe_2(B1, T1, TF, BF).
% la fin de la boucle est trouvee
% on enregistre son numero et son code
passe_2([']' | B], TC-[], TC, B).
% on s'assure que le caractre est valide
passe_2([C | B], T, TF, BF) :-
% member(C, [+, -, <, >, ',', '.']),
append_dl(T, [C|U]-U, NT),
passe_2(B, NT, TF, BF).
% la concaténation des differences-listes, en temps constant !
append_dl(X1-X2, X2-X3, X1-X3).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Amelioration ponctuelle
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
passe_3(boucle([decrcell(1)]), raz) :- !.
passe_3(boucle(L), boucle(L1)) :-
maplist(passe_3, L, L1).
passe_3(V, V).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Les primitives du langage
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
incrptr(V) :-
retract(ptr(N)),
N1 is N+V,
assert(ptr(N1)).
decrptr(V) :-
retract(ptr(N)),
N1 is N-V,
assert(ptr(N1)).
incrcell(V) :-
ptr(N),
retract(cell(N, V1)),
V2 is (V1+V) mod 256,
assert(cell(N, V2)).
decrcell(V) :-
ptr(N),
retract(cell(N, V1)),
V2 is V1-V,
assert(cell(N, V2)).
raz :-
ptr(N),
retract(cell(N, _V)),
assert(cell(N, 0)).
putchar(V) :-
ptr(N),
cell(N, V1),
char_code(A, V1),
forall(between(1, V, _I), write(A)).
getchar(Nb) :-
ptr(N),
forall(between(1, Nb, _I),
( retract(cell(N, _)),
read(A),
( number(A) -> number_codes(A, [V]); char_code(A,V)),
assert(cell(N, V)))).
% on rencontre un début de boucle,
boucle(L) :-
% ici on commence la boucle, si le caractère pointé est non null
carnonnull,
bf(L),
% une fois l'exécution de la boucle terminee
% on teste si on doit la refaire
boucle(L).
% si le caractère pointe est null
% on termine tout simplement l'execution de la boucle
% en revenant au precedant bf.
boucle(_).
% la valeur courante est-elle nulle
carnonnull :-
ptr(N),
cell(N, V),
V \= 0.
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Bonjour ! (oui oui je suis content c'est mon premier post )
Bon j'apporte ma pierre à l'édifice en C++
Mon compilateur optimise les instructions successives(+++++ devient +=5) et les retours à zéro [-]
Le code est représenté comme un arbre, une boucle contient ses instructions. Pratique pour sauter une boucle quand la cellule vaut zéro (pour mandelbrot.bf, je suis passé de 80s à 40s...). Le code lui-même n'a pas de dépendances externes, j'utilise boost pour le timer, la barre de prog et les arguments de la ligne de commande, l'API Win32 (pour une seule fonction OutputDebugString, vive Visual C++ ). Je poste juste les 2 fichiers importants, j'ai envoyé le projet sur mediafire : lien
Je planche sur un système pour optimiser les boucles du type ++++[<+++++>-]
Les erreurs de syntaxe comme les boucles non fermées ou les ][ vicieux pour tester le compilateur arrêtent la compilation
Je ne contrôle pas les dépassements mémoire, ça fait gagner du temps et c'est le boulot du programme de pas dépasser les 30000 cases (bon j'ai triché j'en ai mis 32768)
J'ai testé les programmes de cette page et ils marchent (presque) tous.
Pour utiliser mon compilateur
Si vous êtes sous windows, pour régler le problème des accents
chcp 1252
Affiche l'aide
bfc -h
Exécute helloworld.bf
bfc -m parse helloworld.bf
Exécute helloworld.bf et redirige la sortie vers helloworld.txt
bfc -m parse helloworld.bf helloworld.txt
Exécute les tests
bfc -m tests
Le code est assez moche, j'ai rajouté les commentaires après coup. J'ai créé une classe "console_buffer" pour bufferiser la sortie standard qui est très lente sous Visual C++ (ou peut-être que chez moi). Sans cette classe, il faut 8secondes pour sortir la GPL, avec il faut que 85ms. J'ai aussi créé une classe "input_console_buffer" pour contrôler l'entrée standard, simuler les entrées clavier (pratique pour les tests)
Les tests justement sont pas terminés, je vérifie juste que le test n'a pas planté.
Micro$oft oblige, faut remplacer les #pragma once non supportés et les _getche() pour compiler ailleurs
Je poste pas tous les fichiers, les autres sont dans le zip
L'en-tête précompilé :
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include <sdkddkver.h>
//STL includes
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <exception>
#include <vector>
#include <queue>
//Windows-specific includes
#include <WinError.h>
#include <conio.h>
//Boost includes
#include <boost\filesystem.hpp>
#include <boost\program_options.hpp>
#include <boost\timer.hpp>
#include <boost\progress.hpp>
//Taille de la mémoire brainfuck
#define MEM_SIZE 32768
//Désactive le C4482 : extension non standard utilisée : enum 'enum' utilisé dans le nom qualifié
#pragma warning(disable:4482)
//Includes du programme
#include "console_buffer.h" //input_console_buffer et console_buffer
#include "BfOp.h" //BfOp : définit une opération brainfuck
#include "Parser.h" //Fonctions principales de l'interpréteur
#include "Tests.h" //Fonctions de test
L'en-tête de BfOp. Pas grand-grand chose d'intéressant
#pragma once
#include "stdafx.h"
class BfOp;
//Type d'opération brainfuck
enum eBfOpType {
Unknow = 0x00, //Opération inconue
Plus = 0x2B, //'+'
GetChar = 0x2C, //','
Minus = 0x2D, //'-'
PutChar = 0x2E, //'.'
Left = 0x3C, //'<'
Right = 0x3E, //'>'
LoopStart = 0x5B, //'['
LoopEnd = 0x5D, //']'
Root = -1, //Opération racine, contient toutes les autres opérations
ReturnTo0 = -2, //Remet à zéro l'octet pointé
Loop = -3 //Opération de boucle '[]'
};
//Représente un vector de pointeurs sur des BfOp
typedef std::vector<BfOp*> BfOpPVector;
//Représente une opération brainfuck
class BfOp {
private:
eBfOpType m_type; //Type de l'opération
int m_count; //Nombre de répétitions de l'opération. Non valide pour les retours à zéro, les boucles et les lectures de caractères
BfOp *m_parent; //Pointeur sur le parent de cette opération
BfOpPVector m_children; //BfOpPVector contenant les pointeurs des enfants de cet élément. Valid uniquement pour les boucles et l'opération Racine
public:
//Obtient le type de cet opération
eBfOpType type() const
{ return m_type; }
//Définit le type de cette opération
void setType(const eBfOpType newType)
{ m_type = newType; }
//Obtient le nombre de répétitions de cette opération
int count() const
{ return m_count; }
//Définit le nombre de répétitions de cette opération
void setCount(const int newCount)
{ m_count = newCount; }
//Incrémente le nombre de répétitions de cette opération
void countPlusPlus()
{ m_count++; }
//Obtient le pointeur sur le parent de cet élément
BfOp *parent()
{ return m_parent; }
//Définit le pointeur sur le parent de cet élément
void setParent(BfOp *newParent)
{ m_parent = newParent; }
//Obtient les enfants de cet élément
BfOpPVector &children()
{ return m_children; }
//Constructeur de la class
BfOp(eBfOpType Type, int Count, BfOp *Parent = NULL);
//Destructeur
~BfOp();
//Opérateur de sortie
friend std::ostream &operator<<(std::ostream &out, BfOp &obj);
};
La définition de BfOp. Pas grand chose d'intéressant non plus
#include "stdafx.h"
BfOp::BfOp(eBfOpType Type, int Count, BfOp *Parent) {
m_type = Type;
m_count = Count;
m_parent = Parent;
m_children = BfOpPVector();
}
BfOp::~BfOp() {
for (BfOpPVector::iterator i = m_children.begin(); i != m_children.end(); i++) {
delete (*i);
}
}
std::ostream &operator<<(std::ostream &out, BfOp &obj) {
switch (obj.m_type) {
case eBfOpType::Root:
for (BfOpPVector::iterator i = obj.m_children.begin(); i != obj.m_children.end(); i++) {
out << **i;
}
break;
case eBfOpType::Loop:
out << '[';
for (BfOpPVector::iterator i = obj.m_children.begin(); i != obj.m_children.end(); i++) {
out << **i;
}
out << ']';
break;
case eBfOpType::ReturnTo0:
out << "[-]";
break;
default:
for (int i = 0; i < obj.m_count; i++)
out << obj.m_type;
break;
}
out << std::flush;
return out;
}
Le fichier console_buffer.h, pour les classes console_buffer et input_console_buffer (tout est inline, je sais c'est mal)
#pragma once
#include "stdafx.h"
//Type de vidage de la mémoire tampon
enum console_buffer_autoflush_mode {
None = 0, //Le buffer doit être vidé manuellement
OnFull = 1, //Le buffer est vidé automatiquement quand il est plein
OnNewLine = 2, //Le buffer est vidé automatiquement lors de la rencontre d'un saut de ligne
OnFullNewLine = 3 //Le buffer est vidé automatiquement lorsqu'il est plein ou lors de la rencontre d'un saut de ligne
};
//Représente un buffer sur un flux de type FILE* (prévu pour stdout, stderr mais marche aussi pour les FILE*)
class console_buffer {
private:
char *m_buffer; //Le buffer lui-même
size_t m_cursor, m_bufferSize; //Emplacement du pointeur sur le buffer, Taille du buffer
console_buffer_autoflush_mode m_autoFlush; //Mode de vidage automatique du buffer
FILE *m_stream; //Flux bufferisé
//Réinitialise le buffer interne
void m_clearBuffer() {
for (size_t i = 0; i != (m_bufferSize - 1); ++i) {
m_buffer[i] = 0;
}
}
//Vide le buffer interne sur le flux
void m_flush() {
std::fprintf(m_stream, m_buffer);
m_cursor = 0;
m_clearBuffer();
}
public:
//Ajoute un caractère à la suite du buffer, et le vide si besoin
void putchar(const char value) {
switch (m_autoFlush) {
case console_buffer_autoflush_mode::None:
m_buffer[m_cursor] = value;
m_cursor++;
case console_buffer_autoflush_mode::OnFull:
m_buffer[m_cursor] = value;
if (m_cursor == (m_bufferSize - 2))
m_flush();
else
m_cursor++;
break;
case console_buffer_autoflush_mode::OnNewLine:
m_buffer[m_cursor] = value;
if (value == '\n')
m_flush();
else
m_cursor++;
break;
case console_buffer_autoflush_mode::OnFullNewLine:
m_buffer[m_cursor] = value;
if (value == '\n' || m_cursor == (m_bufferSize - 2))
m_flush();
else
m_cursor++;
break;
default:
return;
}
}
//Vide le buffer si nécessaire
void flush() {
if (!empty())
m_flush();
}
//Return true si le buffer est vide, sinon false
bool empty()
{ return m_cursor == 0; }
//Retourne le mode de vidage automatique
console_buffer_autoflush_mode autoFlush()
{ return m_autoFlush; }
//Définit le mode de vidage automatique
void setAutoFlush(console_buffer_autoflush_mode val)
{ m_autoFlush = val; }
//Constructeur
console_buffer(FILE *stream, size_t bufferSize, console_buffer_autoflush_mode autoFlushMode) {
m_stream = stream;
m_cursor = 0;
m_autoFlush = autoFlushMode;
m_bufferSize = bufferSize;
m_buffer = NULL;
m_buffer = new char[bufferSize];
m_clearBuffer();
}
~console_buffer() {
delete[] m_buffer;
}
};
//Représente un buffer sur l'entrée console. Permet de mettre en attente des caractères
class input_console_buffer {
private:
std::queue<char> m_chars; //File d'attente des caractères
size_t m_chars_size; //Taille de la file d'attente. Plus rapide que std::queue<char>.size()
public:
//Rajoute un caractère à la file d'attente
void putchar(const char value)
{ m_chars.push(value); m_chars_size++; }
//Rajoute une chaîne de caractères à la file d'attente
void putstring(const char *value) {
size_t sLen = strlen(value);
for (size_t i = 0; i != sLen; i++)
putchar(value[i]);
}
//Obtient un caractère de la file d'attente, ou si aucun caractère disponible, l'obtient de l'entrée standard
char getchar() {
if (m_chars_size == 0)
return _getche();
else {
char val = m_chars.front();
m_chars.pop();
m_chars_size--;
return val;
}
}
//Constructeur par défaut
input_console_buffer() {
m_chars = std::queue<char>();
m_chars_size = 0;
}
};
Les fonctions principales de l'interpréteur
#pragma once
#include "stdafx.h"
//Vérifie que le caractère x est un de ces caractères : +-<>.,[]
#define VALIDBFOP(x) (x == eBfOpType::Plus || x == eBfOpType::Minus || x == eBfOpType::Left || x == eBfOpType::Right || x == eBfOpType::PutChar || x == eBfOpType::GetChar || x == eBfOpType::LoopStart || x == eBfOpType::LoopEnd)
//Espace de nom de l'analyseur
namespace Parser {
//Compile et exécute le code contenu dans source, redirige la sortie du code vers outputFileName (sortie standard si "stdout")
//Affiche les messages d'avancement du compilateur si verbose = true. inputBuffer permet le contrôle de l'entrée standard
void main(std::istream &source, std::string &outputFileName, bool verbose = true, input_console_buffer &inputBuffer = input_console_buffer());
//Compile et exécute le code contenu dans source, redirige la sortie du code vers outputFileName (sortie standard si "stdout")
//Affiche les messages d'avancement du compilateur si verbose = true. inputBuffer permet le contrôle de l'entrée standard
void main(const char *source, std::string &outputFileName, bool verbose = true, input_console_buffer &inputBuffer = input_console_buffer());
//Compile le code contenu dans source, mesure le temps nécessaire à la compilation avec cTimer, retourne le résultat de la compilation
//dans rootNode et affiche les messages d'avancement si verbose = true.
void compile(std::istream &source, boost::timer &cTimer, BfOp &rootNode, bool verbose);
//Exécute le code contenu dans rootNode, redirige la sortie vers outputFileName, mesure le temps nécessaire à l'exécution avec cTimer
//La mémoire brainfuck est fournie par memory, affiche les message d'avancement si verbose = true et inputBuffer permet de contrôler l'entrée standard
void exec(std::string &outputFileName, boost::timer &cTimer, BfOp &rootNode, unsigned char *memory, bool verbose, input_console_buffer &inputBuffer);
//Exécute une opération brainfuck item et ses descendants en utilisant la mémoire memory et sont pointeur memoryCursor, redirige la sortie
//vers output et obtient l'entrée standard depuis inputBuffer
inline void execItem(unsigned char *memory, unsigned short &memoryCursor, BfOp *item, console_buffer &output, input_console_buffer &inputBuffer);
}
Et enfin leurs définitions. J'ai déjà expliqué, et le code est commenté (bon courage quand même)
#include "stdafx.h"
#ifdef _DEBUG
#include <windows.h>
#endif
using namespace std;
namespace Parser {
void main(std::istream &source, std::string &outputFileName, bool verbose, input_console_buffer &inputBuffer) {
unsigned char *memory = NULL; //Pointeur sur la mémoire de l'analyseur brainfuck
try {
boost::timer cTimer = boost::timer(); //Chronomètre pour la mesure des performances
BfOp rootNode(eBfOpType::Root, 1); //Opération racine. Contient tout le code
compile(source, cTimer, rootNode, verbose); //Compile le code en entrée
#ifdef _DEBUG //Si débuggage, le code est réécrit dans la sortie de débuggage pour vérifier l'exactitude de la compilation
ostringstream s(ios::out);
s << "----BF Code Dump----" << endl;
s << rootNode << endl;
OutputDebugString(s.str().c_str());
#endif
memory = new unsigned char[MEM_SIZE]; //Alloue la mémoire brainfuck
exec(outputFileName, cTimer, rootNode, memory, verbose, inputBuffer); //Exécute le code
delete[] memory; //Désalloue la mémoire brainfuck
} catch (runtime_error ex) {
cerr << "Erreur : " << ex.what() << endl; //Affiche le message de l'erreur
if (memory != NULL) //Vide la mémoire brainfuck allouée
delete[] memory;
throw ex; //Propage l'exception
}
}
void main(const char *source, std::string &outputFileName, bool verbose, input_console_buffer &inputBuffer) {
std::stringstream src(source, ios::in | ios::out);
main(src, outputFileName, verbose, inputBuffer);
}
void compile(std::istream &source, boost::timer &cTimer, BfOp &rootNode, bool verbose) {
BfOp *lastOperation = NULL, *item = NULL, *currentParent = &rootNode; //Pointeurs sur la dernière opération brainfuck, l'élément en cours d'analyse et le parent actuel de item
unsigned int cLine = 1, cCol = 0; //Informations de position dans le fichier. Permet le positionnement des erreurs de syntaxe
if (verbose)
cerr << "Début de la compilation..." << endl;
stringstream err(ios::in | ios::out); //Flux des messages d'erreur
source.seekg(0, ios::end); //Mesure la longueur du flux pour afficher la barre de progression boost
boost::progress_display *prg = NULL;
if (verbose)
prg = new boost::progress_display(source.tellg());
source.seekg(0, ios::beg);
while (!source.eof()) { //Tant que l'on est pas à la fin du fichier
signed char cOp = source.get(); //On lit un caractère
cCol++; //Mise à jour des informations de position
if (VALIDBFOP(cOp)) { //Si le caractère lu est une instruction brainfuck
if (lastOperation == NULL || lastOperation->type() != cOp) { //Si aucune opération précédente ou si le type de cette opération est différent du précédent
item = new BfOp((eBfOpType)cOp, 1, currentParent); //Construit l'opération et obtient son pointeur
lastOperation = NULL; //Réinitialise la dernière opération
if (item->type() == eBfOpType::LoopEnd) { //Si c'est une fin de boucle
currentParent->setType(eBfOpType::Loop); //On modifie le type du parent actuel pour définir que c'est une boucle
if (currentParent->children().size() == 1 && currentParent->children()[0]->type() == eBfOpType::Minus) //Optimise les retours à zéro [-]
currentParent->setType(eBfOpType::ReturnTo0);
currentParent = currentParent->parent(); //Remonte d'un niveau
if (currentParent == NULL) { //Si le parent est NULL, on est remontés trop haut, donc il y a une erreur de syntaxe
stringstream err2(ios::out);
err2 << "Erreur de syntaxe Ln " << cLine << " Col " << cCol << " : ']' innatendu";
if (verbose)
putchar('\n');
throw runtime_error(err2.str());
}
} else if (item->type() == eBfOpType::LoopStart) { //Si c'est un début de boucle
currentParent->children().push_back(item); //On rajoute la boucle au parent actuel
currentParent = item; //On descend d'un niveau
} else { //Si c'est une autre opération
currentParent->children().push_back(item); //On rajoute cette opération au parent actuel
lastOperation = item; //Cette opération devient la dernière opération
}
} else { //Si cette opération et l'opération précédente ont le même type
if (lastOperation->type() == eBfOpType::GetChar) //Plusieurs lectures de l'entrée standard successives sont inutiles. On informe l'utilisateur
err << "Avertissement : Plusieurs opérations ',' successives Ln " << cLine << " Col " << cCol << endl;
else
lastOperation->countPlusPlus(); //On augmente le nombre de répétitions de la dernière opération
}
} else if (cOp = '\n') { //Mise à jour des informations de position
cLine++;
cCol = 0;
}
if (verbose) //Mise à jour de la barre de progression
++(*prg);
}
if (currentParent != &rootNode) { //Si le niveau actuel n'est pas le niveau racine il y a une erreur de syntaxe
stringstream err(ios::out);
err << "Erreur de syntaxe Ln " << cLine << " Col " << cCol << " : ']' manquant";
throw runtime_error(err.str());
}
if (verbose)
cerr << "Compilation terminée en " << (unsigned long)(cTimer.elapsed() * 1000.0) << "ms" << endl; //Temps de compilation
fprintf(stderr, err.str().c_str()); //Affiche les avertissements
}
void exec(std::string &outputFileName, boost::timer &cTimer, BfOp &rootNode, unsigned char *memory, bool verbose, input_console_buffer &inputBuffer) {
if (verbose)
cerr << "Début de l'exécution du programme..." << endl;
for (int i = 0; i < MEM_SIZE; i++) //Initialise la mémoire
memory[i] = 0;
//Redirige la sortie standard si nécessaire
FILE *outFile = NULL;
if (outputFileName != "stdout")
outFile = freopen(outputFileName.c_str(), "w", stdout);
unsigned short memoryCursor = 0; //Pointeur sur la mémoire brainfuck
console_buffer buffer = console_buffer(stdout, 0x4000, console_buffer_autoflush_mode::OnFullNewLine); //Intialise le buffer de sortie standard
cTimer.restart(); //Redémarre le chrono
Parser::execItem(memory, memoryCursor, &rootNode, buffer, inputBuffer); //Exécute l'élément racine et ses descendants
unsigned long elapsedMs = (unsigned long)(cTimer.elapsed() * 1000.0); //Temps d'exécution
buffer.flush(); //Vide le buffer de sortie standard
if (outFile != NULL) { //Ferme le fichier si il y a eu une redirection de la sortie standard
fclose(outFile);
outFile = freopen("CON", "w", stdout);
}
if (verbose)
cerr << "\nExécution terminée en " << elapsedMs << "ms" << endl;
}
void execItem(unsigned char *memory, unsigned short &memoryCursor, BfOp *item, console_buffer &output, input_console_buffer &inputBuffer) {
//Aucun contrôle n'est fait ni sur les additions-soustractions, ni sur les déplacements mémoire
//La mémoire fait 32768 cases. Si le programme tente d'accéder à la 32768ème case, le compilateur
//s'arrêtera.
int size; //Taille des enfants
switch (item->type()) {
case eBfOpType::Plus: //Opération +
memory[memoryCursor] += item->count();
break;
case eBfOpType::GetChar: //Operation ,
output.flush(); //Vide la sortie standard avant de demander un caractère
memory[memoryCursor] = inputBuffer.getchar();
break;
case eBfOpType::Minus: //Opération -
memory[memoryCursor] -= item->count();
break;
case eBfOpType::PutChar: //Opération .
for (int i = 0; i != item->count(); i++) //Affiche item->count() fois le caractère actuel
output.putchar(memory[memoryCursor]);
break;
case eBfOpType::Left: //Opération <
memoryCursor -= item->count();
break;
case eBfOpType::Right: //Opération >
memoryCursor += item->count();
break;
case eBfOpType::Root: //Opération racine
size = item->children().size();
for (int i = 0; i != size; i++) {
Parser::execItem(memory, memoryCursor, item->children()[i], output, inputBuffer);
}
break;
case eBfOpType::ReturnTo0: //Opération [-]
memory[memoryCursor] = 0;
break;
case eBfOpType::Loop: //Opération boucle
size = item->children().size();
while (memory[memoryCursor] != 0) {
for (int i = 0; i != size; i++) {
Parser::execItem(memory, memoryCursor, item->children()[i], output, inputBuffer);
}
}
break;
}
}
}
Voilà. Hésitez pas à critiquer (surtout que je suis sûr que ya beaucoup de choses à revoir)
( deuxième fois que je tape ce (long) message, plantage de janrain, impossible de me reconnecter avec mon compte google. Et la sauvegarde ne contenait que 3 lignes )
EDIT : Je vais faire une version en VB.NET, pour comparer les performances. Ca doit faire mal...
la taille du ruban n’est limitée que par la mémoire de la machine ;
elle détecte les mésappariements des crochets avant l’exécution ;
elle est capable de lire le code depuis une indirection avec l’argument « - » ;
malheureusement ; elle ne s’exécute que sur un système POSIX, car elle a besoin de lire /dev/tty pour la capacité précédente, des modifications minimes sont requises sinon ;
elle s’exécute relativement rapidement ;
la gestion des erreurs est convenable ;
le code est difficilement lisible et n’est pas commenté.
Et le code :
bf.h
/*
* Copyright (c) 2010, 2011, Paul Bazin
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials
* provided with the distribution.
* * Neither the name of the author nor the names of its
* contributors may be used to endorse or promote products
* derived from this software without specific prior written
* permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
* AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
* USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
* DAMAGE.
*/
#ifndef H_BF
#define H_BF
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define REAL_SIZ 256U
struct data
{
char* buf;
long p;
long up_lim;
long down_lim;
size_t size;
};
static char* buf_code(const char*, size_t**);
static int move_pointer(struct data*, char);
#endif /* H_BF */
bf.c
/*
* Copyright (c) 2010, 2011, Paul Bazin
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the following
* disclaimer in the documentation and/or other materials
* provided with the distribution.
* * Neither the name of the author nor the names of its
* contributors may be used to endorse or promote products
* derived from this software without specific prior written
* permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
* AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
* USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
* DAMAGE.
*/
#include "bf.h"
int main(int argc, char** argv)
{
int r=-1;
size_t i=0;
char* code;
struct data dt;
const char* input;
size_t* match;
if (argc != 2)
exit(2);
if (argv[1][0] == '-' && !argv[1][1])
input = NULL;
else
input = argv[1];
code = buf_code(input, &match);
dt.p = REAL_SIZ/2;
dt.up_lim = 0;
dt.down_lim = 0;
dt.size = REAL_SIZ;
dt.buf = calloc(REAL_SIZ, 1U);
if (code && dt.buf)
{
r=0;
while (code[i] != '\0')
{
switch (code[i])
{
case '+':
dt.buf[dt.p%(long)dt.size]++;
break;
case '-':
dt.buf[dt.p%(long)dt.size]--;
break;
case '>':
if (move_pointer(&dt, (char) 1))
{
free(code);
free(dt.buf);
exit(-1);
}
break;
case '<':
if (move_pointer(&dt, (char) 0))
{
free(code);
free(dt.buf);
exit(-1);
}
break;
case '.':
putchar(dt.buf[dt.p%(long)dt.size]);
break;
case ',':
dt.buf[dt.p%(long)dt.size] = (char) getchar();
break;
case '[':
if (!dt.buf[dt.p%(long)dt.size])
i = match[i];
break;
case ']':
if (dt.buf[dt.p%(long)dt.size])
i = match[i];
}
i++;
}
putchar('\n');
}
free(code);
free(match);
free(dt.buf);
return r;
}
static char* buf_code(const char* src, size_t** match)
{
char* code=NULL;
FILE* fd;
src ? (fd = fopen(src, "r")) : (fd = stdin);
if (fd)
{
int c;
size_t i=0;
size_t k=0;
size_t brackets=0;
while ((c=fgetc(fd)) != EOF)
if (strchr("+-><.,[]", c))
{
i++;
if (c == '[')
{
k++;
brackets++;
}
else if (c == ']')
{
if (!k)
{
k++;
break;
}
else
k--;
}
}
if (k)
{
fclose(fd);
fputs("brackets mismatch\n", stderr);
exit(1);
}
else
{
rewind(fd);
code = malloc(i+1U);
*match = malloc(i * sizeof **match);
i = 0;
if (code && *match)
{
size_t* p = malloc(brackets * sizeof *p);
if (p)
{
while((c=fgetc(fd)) != EOF)
if (strchr("+-><.,[]", c))
{
code[i++] = (char) c;
if (c == '[')
*p++=i-1;
else if (c == ']')
{
(*match)[i-1] = *--p;
(*match)[*p] = i-1;
}
}
free(p);
code[i] = '\0';
}
}
else
{
free(*match);
free(code);
code=NULL;
}
if (fd != stdin)
fclose(fd);
else
if (!(stdin=freopen("/dev/tty", "r", stdin)))
{
free(*match);
free(code);
code=NULL;
}
}
}
return code;
}
static int move_pointer(struct data* dt, char forward)
{
int r=0;
if (forward)
{
dt->p++;
if (dt->p > dt->up_lim)
dt->up_lim = dt->p;
}
else
{
dt->p--;
if (dt->p < dt->down_lim)
dt->down_lim = dt->p;
}
if ((size_t) (dt->up_lim - dt->down_lim) >= dt->size)
{
char* tmp = realloc(dt->buf, dt->size+=REAL_SIZ);
if (tmp)
{
size_t i;
dt->buf = tmp;
for (i=dt->size-(REAL_SIZ+1U); i < dt->size; i++)
dt->buf[i] = '\0';
}
else
r=-1;
}
return r;
}
Vous pouvez trouver une archive de cet interpréteur ici.
L’intégralité du code est sous la nouvelle licence BSD, donc ce n’est pas très restrictif et vous pouvez en faire à peu près ce que vous voulez.
Note : si vous utilisez le makefile que je fournis, les éventuels warnings indiquant du code n’étant pas exécuté sont dus à l’optimisation agressive (option -O3). Et oui, si l’on arrive à la ligne 42, match est forcément initialisé (par un déréférencement, mais initialisé quand même).
À quoi ça sert de s'embêter à parser des paramètres en ligne de commande pour lire dans un fichier ? Le shell gère déjà ça très bien, tu peux lire juste dans stdin et faire un ./foo < fichier quand nécessaire.
[Atelier tous langages] Codez un interpréteur de Brainfuck
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !
Le crayon la gomme et le papier sont les meilleurs outils du programmeur !