Non, ça ne donne pas de gain de temps du tout (et on en perd même dans certains cas, en gros dès qu'on veut un accès arbitraire) mais c'est fonctionnel pur (contrairement à un tableau) donc utilisable sans problème dans tous les langages fonctionnels, et l'usage pour le BF est relativement adapté.
C'est aussi une structure persistente, ce qui permet de faire des "sauvegardes" peu chères des états précédents, ce qui peut être utile dans d'autres contextes comme la concurrence (si on veut faire des opérations atomiques).
OK, je vois. Mais pour la sauvegarde, sauvegarder la position dans le tableau (un entier tout bête) n'est pas très cher non plus, si ? (désolé si j'embête avec mes questions).
Avec un Zipper, tu implémentes aussi une mémoire infinie beaucoup plus facilement qu'avec un tableau (et de façon beaucoup moins chère, puisque quoi qu'il en soit, aller à gauche et à droite sont en O(1), ce qui n'est pas le cas pour le tableau).
zulon > non, parce que si tu modifies le tableau ensuite, ta sauvegarde n'a plus de sens. Enfin il te reste une position mais tu n'as plus "l'état" de la mémoire à l'instant qui t'intéressait, ce que permet de faire facilement et efficacement un zipper.
asmanur > oui, c'est bien pour une mémoire infinie, par contre on se fait humilier pour les mémoires cycliques
Ceci dit je pense que dans l'absolu la mémoire infinie est un meilleur choix que la mémoire cyclique, donc on s'y retrouve.
Ah d'accord, j'avais mal compris. Tout s'explique . Mais vu qu'en BF "traditionnel" le tableau où sont stockées les instructions n'est jamais modifié...
Je parlais de l'utilisation d'un zipper pour la mémoire.
Pour le code, effectivement ça a moins de sens, il vaudrait mieux stocker une liste dont on dépile les éléments.
C'est d'ailleurs une suggestion plutôt amusante, je vais voir si je peux faire quelque chose.
Edit : voilà
let (* refutable *) right (left, curr::right) =
(curr::left, if right = [] then [0] else right)
let left = function
| (prev::left, right) -> (left, prev::right)
| ([], right) -> ([], 0::right)
let (* refutable *) curr (_, curr::_) = curr
let (* refutable *) apply f (left, curr::right) = (left, f curr :: right)
let single x = ([], [x])
let id x = x
let rec bf code mem = match code with
| [] -> ()
| '['::tl -> (fun code' -> bf code' mem)
(let rec skip level k = function
| [] -> failwith "boucle non fermee"
| ']'::tl when level = 0 -> (k, tl)
| c::tl ->
let level_change = match c with
| '[' -> 1 | ']' -> -1
| _ -> 0 in
skip (level + level_change) (fun li -> k (c :: li)) tl in
let k, tl' = skip 0 id tl in
if curr mem = 0 then tl' else k code)
| hd::tl -> (fun change -> bf tl (change mem))
(match hd with
| '<' -> left | '>' -> right
| '+' -> apply ((+) 1) | '-' -> apply ((+) (-1))
| ',' -> apply (fun _ -> read_int ())
| '.' -> apply (fun c -> print_char (char_of_int c); c)
| _ -> id)
| '['::tl -> (fun code' -> bf code' mem)
(let rec skip level k = function
| [] -> failwith "boucle non fermee"
| ']'::tl when level = 0 -> (k, tl)
| c::tl ->
let level_change = match c with
| '[' -> 1 | ']' -> -1
| _ -> 0 in
skip (level + level_change) (fun li -> k (c :: li)) tl in
let k, tl' = skip 0 id tl in
if curr mem = 0 then tl' else k code)
En manque de where ?
Sinon j'ai du mal à piger, pour les boucles, t'es sur que ça boucle ? J'ai l'impression que le test est fait qu'une seule fois, lors de la rencontre du '[' et donc que le code est exécuté une fois au maximum.
mario> ton code semble faux, il te manque un test dans ']', faut tester la case courante avant de repartir en arrière (à moins que tu le fasses dans '[' ... ce qui fait que quand t'as un ']' tu pars chercher le '[' pour repartir chercher le '] correspondant ...)
edit : c'est d'ailleurs précisément ça qui m'a amusé au départ
mario56 > ton code n'est pas très intéressant, car c'est une simple traduction, avec des trucs laids au début, et un style d'indentation lourdingue, de la version PHP. Tu devrais essayer de chercher quelque chose qui illustre un peu mieux les qualités (de ton langage.
Boarf, non, je pense que par rapport aux zippers on voit pas trop la différence. Si ça te fait pas rire, un accumulateur et List.rev_append (et ça, ça sera même plus performant que les zippers, parce qu'on stockera beaucoup moins de code useless).
Moi je m'étonne ne pas avoir vu d'implémentations utilisant une liste doublement chainée circulaire pour la mémoire. Ptet que j'vais faire ça cette aprem.
Boarf, non, je pense que par rapport aux zippers on voit pas trop la différence. Si ça te fait pas rire, un accumulateur et List.rev_append (et ça, ça sera même plus performant que les zippers, parce qu'on stockera beaucoup moins de code useless).
Sauf que tu dois te taper le parsage des [] à chaque itération non ?
(Je veux dire de la merde par rapport aux /vrais parsers/, bien sur :p)
let right = Dllist.next
let left = Dllist.prev
let curr = Dllist.get
let apply f li = Dllist.set li (f (curr li)); li
let single x = Dllist.of_enum (Enum.init 30000 (fun _ -> x))
(ocamlfind ocamlc -package extlib -linkpkg ...)
asmanur :
Oui, mais tu notes que je peux utiliser le code actuel pour parser, en changeant la manière dont j'utilise la continuation. Mais bien sûr, la méthode avec des flots est plus élégante.
J'en sais rien, mais c'est assez lent (mais pas trop) donc c'est cool. Pour vérifier que ton truc marche bien il faut tester sur d'autres choses avant.
Au niveau des optimisations, je suis en train de bosser sur quelques séquences qui se retrouvent à plusieurs endroits et qui sont optimisables. Il y a en particulier:
1) [-] qui remet l'octet pointé à 0
2) [>+<-] qui additionne le contenu d'une case avec ce qui est dans sa voisine de gauche (+= en C) et met a zéro le contenu de la case de gauche
3) Des variantes sur le même thème de cette dernière séquence.
4) Les suites de caractères identiques.
J'ai pris comme base le code de Mattex (disponible ici) et j'y ait ajouter la première optimisation en parcourant une première fois tout le code pour faire des remplacement avant de l'interpréter. Sur le code affichent les carrés jusqu'à 10'000 je passe de 0.140s à 0.120s.
L'optimisation est donc intéressante.
Intéressant. Je pense qu'avec ce raisonnement on peut même exprimer toutes les boucles "pures" et "statiques" (ne se déplaçant pas entre les tests) comme une fonction des valeurs d'entrée des cases concernées, ce qui donnerait un fort gain de perf (en généralisant ton optimisation).
On pourrait commencer par les boucles non imbriquées, c'est sans doute le plus abordable. Comme transformer une boucle BF pure et statique en une fonction de la valeur de la case de test ?
vous croyez serieusement que vous pourrez faire l'operation inverse en un temps correct ? (bon, mon temps de calcul est en grosse partie du a l'optimisation en taille finale : la recherche du point fixe, mais j'ai quand meme de serieux doutes quand aux perfs...)
Tant que le programme ne dépend pas d'une entrée de l'utilisateur (i.e. si il n'y a pas de ","), alors son comportement complet est entièrement connu à la compilation. Dans l'absolu il est donc possible de comprendre son fonctionnement et de le remplacer par une suite de "printf" sans aucun branchement ni accès mémoire.
Ca doit pouvoir se faire mais sans aide ça dépace mes capacités pour l'implémentation d'un tel traducteur.
[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.
Python c'est bon, mangez-en.