Josmiley, à priori non, vu que le code et la mémoire d'exécution du programme sont totalement séparées. Mais on pourrait essayer d'explorer de ce côté là (qui pour métaprogrammation en BF ?).
J'ai déménagé sur Zeste de savoir — Ex-manager des modérateurs.
Non. Si le programme ne doit pas intéragir avec l'extérieur, c'est la même chose.
Si il interagit pas avec l'extérierur, il ne sert à rien : il produit un seul output et donc il n'est utilise de le lancer qu'une seule fois. Que ce soit fait à la compilation ou pas ça change rien.
Bon, j'ai travaillé un peu sur l'optimisation mais je ne suis pas allé aussi loin que je voulais. Je mets l'état actuel du truc ici au cas où ça intéresserait des gens.
C'est basé sur le parseur habituel et la préoptimisation de asmanur, mais j'ai un peu tout modifié donc le code n'est pas exactement identique. L'idée c'est de faire plusieurs passes de traduction, chacune effectuant des analyses plus sophistiquées sur le code. Je n'ai pas codé de sortie (mais vous avez vu sur ce topic que la sortie, c'est pas vraiment compliqué).
La première passe est évidemment le parsage du code BF en entrée.
type token =
| Manip of manip * int
| IO of bool
| Bracket of (token list)
and manip = Mem | Code
let parse stream : token list =
let rec parse acc stream =
let tok i = parse (i :: acc) stream in
let manip nature pos =
let num = if pos then 1 else -1 in
let acc' = match acc with
| Manip (n, i) :: rest when n = nature ->
Manip (nature, i + num) :: rest
| rest -> Manip (nature, num) :: rest in
parse acc' stream in
match stream with parser
| [< ' ('+' | '-') as c >] -> manip Mem (c = '+')
| [< ' ('<' | '>') as c >] -> manip Code (c = '>')
| [< ' ('.' | ',') as c >] -> tok (IO (c = '.'))
| [< ''['; code = parse []; '']' >] -> tok (Bracket code)
| [< >] -> List.rev acc in
parse [] stream
Cette passe est un peu particulière car le type renvoyé est proche de la représentation textuelle du programme, mais n'est pas sémantique. La deuxième passe est une simple traduction dans un type plus adapté aux transformations, basé sur celui d'asmanur :
type base_expr = [ `Mem of int | `Move of int ]
type naive_expr = [ base_expr | `Loop of naive_expr list ]
type 'expr statement =
| Expr of 'expr
| Print | Ask
| SLoop of ('expr statement) list
| Seq of ('expr statement) list
let rec map_exprs f = function
| Expr e -> Expr (f e)
| Print -> Print
| Ask -> Ask
| SLoop li -> SLoop (List.map (map_exprs f) li)
| Seq li -> Seq (List.map (map_exprs f) li)
let semantize tokens : naive_expr statement =
let check_pure = function
| Expr expr -> expr
| _ -> raise Exit in
let rec analyze = function
| Manip (nat, n) -> Expr (match nat with Mem -> `Mem n | Code -> `Move n)
| IO b -> if b then Print else Ask
| Bracket code ->
let code = List.map analyze code in
try Expr (`Loop (List.map check_pure code))
with Exit -> SLoop code in
Seq (List.map analyze tokens)
Vous notez que le type "statement" est paramétrique : les "expressions" sont définis comme les fragments 'purs', et c'est cette partie qu'on va optimiser par la suite. On peut donc décrire chaque passe optimisante comme le passage d'un type d'expression à un autre (et on utilise map_exprs pour en obtenir un passage d'un type de programme à un autre). Pour l'instant le type des expressions est simpliste, mais on remarque deux choses :
- il y a des variantes polymorphes, ça promet du fun pour plus tard
- on a deux structures de boucles différentes : les SLoop (statement loops), qui sont les boucles au contenu impur, et les `Loop, qui sont des boucles ne contenant que des expressions, donc pures et optimisables. La différenciation se fait dans le List.map check_pure, qui renvoie une exception si on ne lui donne pas que du code sans effets de bord.
La troisième passe ressemble à ce que faisait déjà asmanur : on compresse les opérations pures en un tout "modification des cases voisines + déplacement du pointeur". Pour cela on introduit le concept de 'a mem_image : c'est une "image de données relatives sur la mémoire", c'est à dire que ça associe des informations aux cases voisines du pointeur. Si on met (3, 2) dans une image mémoire par exemple, ça veut dire qu'on associe la valeur 2 à la case "pointeur + 3". Le sens de l'information stockée dépend de la passe d'optimisation concernée, mais pour l'instant ce sont des "int mem_image" qui représentent des incrémentations de valeur, comme le Add d'asmanur.
type 'a mem_image = (pos * 'a) list (* must be sorted by positions *)
and pos = int (* relative position : may represent a move *)
Pour manipuler les images mémoires on utilise deux fonctions : une fonction qui décale une image (par exemple si on avait "l'effet de telle séquence en partant de la position 0" et qu'on veut décrire le même effet, du point de vue de la position 2, il faut tout décaler), et une fonction qui combine deux images mémoires (c'est linéaire parce que les positions sont stockées en ordre croissant) :
let image_shift pos = List.map (fun (p, n) -> (pos + p), n)
let image_fusion merge ia ib =
let rec fusion = function
| ([], delta) | (delta, []) -> delta
| (x::xs, y::ys) ->
if fst x < fst y then x :: fusion (xs, y::ys)
else if fst x > fst y then y :: fusion (x::xs, ys)
else (fst x, merge (snd x) (snd y)) :: fusion (xs, ys) in
fusion (ia, ib)
On a notre premier type d'expression sophistiquée : elles stockent les "effets" de blocs de code, dans un format proche de celui d'asmanur : un couple image_mémoire * déplacement curseur.
type base_effect = [ `Effect of (int mem_image * pos) ]
type effect_expr = [ base_effect | `Loop of effect_expr list ]
La passe d'optimisation correspondante (on transforme toutes les opérations de base en effets, puis on concatène les effets consécutifs (seq)) :
let rec effect_analysis : naive_expr -> effect_expr = function
| #base_expr as base -> `Effect (base_effect_analysis base)
| `Loop code ->
let seq acc = function
| `Loop naive_exprs -> `Loop (List.map effect_analysis naive_exprs) :: acc
| #base_expr as base ->
let (curr_img, curr_shift) as curr_ef = base_effect_analysis base in
match acc with
| `Effect (prev_img, prev_shift) :: acc_tl ->
let combined_img =
image_fusion (+) prev_img (image_shift prev_shift curr_img) in
`Effect (combined_img, prev_shift + curr_shift) :: acc_tl
| _ -> `Effect curr_ef :: acc in
`Loop (List.rev (List.fold_left seq [] code))
and base_effect_analysis : base_expr -> (int mem_image * pos) = function
| `Mem n -> ([0, n], 0)
| `Move n -> ([], n)
Ensuite vient la deuxième phase d'optimisation, qui est plus proche de ce qu'a fait Nanoc. L'idée c'est que pour les boucles simples (pures et statiques), on peut définir la variation de contenu des cases voisines de la case de test (d'entrée de la boucle) en fonction de la seule valeur de cette case de test.
L'exemple évident est "[-]", qui ne fait que mettre la case de test à 0. De même, "[->+<]" met la case de test à 0, et rajoute dans la case +1 la valeur de la case de test. On peut aussi faire des choses plus sophistiquées comme "[---<->]" qui enlève dans la case -1 le tiers de la valeur de la case de test (si celle si est divisible par 3; sinon j'ai considéré que ça bouclait vers -oo, et donc que c'était invalide).
Pour représenter ces connaissances j'ai un nouveau type de données à mettre dans les images mémoires : au lieu de mettre seulement un nombre (de combien on incrémente la case machin), je met une "formule" qui peut dépendre de la valeur de certaines cases.
type formula =
| Const of int
| Var of pos * int (* pos, decrement *)
| Prod of formula * formula
Une formule est soit une constante, soit une fraction de la valeur d'une case donnée (par position relative) soit un produit des deux. Par exemple [--->++<] attachera à la case +1 la formule Prod (Const 2, Var (0, 3)) : à chaque décrément par 3, on rajoute 2.
Le code de récolte de cette information est simple, et ne prend pour l'instant en compte que les boucles "simples" c'est à dire celles qui ne contiennent pas elles-mêmes de boucles imbriquées (c'est à dire qu'elles continennet seulement une valeur `Effect, puisque s'il n'y a pas de sous-boucles toutes les valeurs ont été combinées en une seule dans la phase d'optimisation précédente) :
type unloop_effect = [ `Unloop of formula mem_image ]
type unloop_expr = [ base_effect | unloop_effect | `Loop of unloop_expr list ]
let rec loop_analysis : effect_expr -> unloop_expr = function
| #base_effect as base -> base
| `Loop [`Effect (image, 0)] ->
let decrement =
try - (List.assoc 0 image)
with Not_found -> failwith "infinite loop : stagnation" in
if decrement = 0 then failwith "infinite loop : stagnation"
else if decrement < 0 then failwith "infinite loop : infinite positive"
else
let unloop =
let loop_effect = function
| (0, _) -> Const 0
| (pos, v) -> Prod (Const v, Var (0, decrement)) in
List.map (fun ((pos, _) as case) -> (pos, loop_effect case)) in
`Unloop (unloop image)
| `Loop effects -> `Loop (List.map loop_analysis effects)
Une petite routine pour combiner toutes les optimisations :
let unloop_from_str str =
let parsed = parse (Stream.of_string str) in
let semantic = semantize parsed in
let effects = map_exprs effect_analysis semantic in
let unloop_effects = map_exprs loop_analysis effects in
unloop_effects
L'output est un peu moche (un volontaire pour coder un pretty-printer ?) mais on voit que ça marche à peu près. On remarque que la deuxième boucle, qui n'est pas statique, n'a pas été optimisée.
Avec ces informations, il est facile de produire un interpréteur qui se comporte de manière très performante sur les boucles pures statiques simples.
On pourrait continuer l'opération en combinant les formules. Ça devrait permettre de pouvoir gérer plusieurs boucles à la suite, voire peut-être même des boucles imbriquées.
Pour l'instant, la gestion des boucles infinies n'est pas satisfaisante : si un programme fait une boucle sur une case mémoire qu'il ne modifie jamais, l'optimisateur détecte une boucle infinie et s'arrête. C'est un bug parce qu'on peut avoir des programmes qui essaient de boucler sur une case vide (pas de bug) où qui sont fait pour tourner à l'infini (ie. générer toute la suite de fibonacci). Pour avoir un vrai interpréteur de Brainfuck il faudrait sans doute faire un peu plus attention à ces cas délicats.
Pour résumer, le code complet (pas commenté, désolé) :
type token =
| Manip of manip * int
| IO of bool
| Bracket of (token list)
and manip = Mem | Code
let parse stream : token list =
let rec parse acc stream =
let tok i = parse (i :: acc) stream in
let manip nature pos =
let num = if pos then 1 else -1 in
let acc' = match acc with
| Manip (n, i) :: rest when n = nature ->
Manip (nature, i + num) :: rest
| rest -> Manip (nature, num) :: rest in
parse acc' stream in
match stream with parser
| [< ' ('+' | '-') as c >] -> manip Mem (c = '+')
| [< ' ('<' | '>') as c >] -> manip Code (c = '>')
| [< ' ('.' | ',') as c >] -> tok (IO (c = '.'))
| [< ''['; code = parse []; '']' >] -> tok (Bracket code)
| [< >] -> List.rev acc in
parse [] stream
type base_expr = [ `Mem of int | `Move of int ]
type naive_expr = [ base_expr | `Loop of naive_expr list ]
type 'expr statement =
| Expr of 'expr
| Print | Ask
| SLoop of ('expr statement) list
| Seq of ('expr statement) list
let rec map_exprs f = function
| Expr e -> Expr (f e)
| Print -> Print
| Ask -> Ask
| SLoop li -> SLoop (List.map (map_exprs f) li)
| Seq li -> Seq (List.map (map_exprs f) li)
let semantize tokens : naive_expr statement =
let check_pure = function
| Expr expr -> expr
| _ -> raise Exit in
let rec analyze = function
| Manip (nat, n) -> Expr (match nat with Mem -> `Mem n | Code -> `Move n)
| IO b -> if b then Print else Ask
| Bracket code ->
let code = List.map analyze code in
try Expr (`Loop (List.map check_pure code))
with Exit -> SLoop code in
Seq (List.map analyze tokens)
type 'a mem_image = (pos * 'a) list (* must be sorted by positions *)
and pos = int (* relative position : may represent a move *)
let image_shift pos = List.map (fun (p, n) -> (pos + p), n)
let image_fusion merge ia ib =
let rec fusion = function
| ([], delta) | (delta, []) -> delta
| (x::xs, y::ys) ->
if fst x < fst y then x :: fusion (xs, y::ys)
else if fst x > fst y then y :: fusion (x::xs, ys)
else (fst x, merge (snd x) (snd y)) :: fusion (xs, ys) in
fusion (ia, ib)
type base_effect = [ `Effect of (int mem_image * pos) ]
type effect_expr = [ base_effect | `Loop of effect_expr list ]
let rec effect_analysis : naive_expr -> effect_expr = function
| #base_expr as base -> `Effect (base_effect_analysis base)
| `Loop code ->
let seq acc = function
| `Loop naive_exprs -> `Loop (List.map effect_analysis naive_exprs) :: acc
| #base_expr as base ->
let (curr_img, curr_shift) as curr_ef = base_effect_analysis base in
match acc with
| `Effect (prev_img, prev_shift) :: acc_tl ->
let combined_img =
image_fusion (+) prev_img (image_shift prev_shift curr_img) in
`Effect (combined_img, prev_shift + curr_shift) :: acc_tl
| _ -> `Effect curr_ef :: acc in
`Loop (List.rev (List.fold_left seq [] code))
and base_effect_analysis : base_expr -> (int mem_image * pos) = function
| `Mem n -> ([0, n], 0)
| `Move n -> ([], n)
type formula =
| Const of int
| Var of pos * int (* pos, decrement *)
| Prod of formula * formula
let rec map_formula f = function
| Const n -> Const n
| Var (p, n) -> Var (f p, n)
| Prod (a, b) -> Prod (map_formula f a, map_formula f b)
type unloop_effect = [ `Unloop of formula mem_image ]
type unloop_expr = [ base_effect | unloop_effect | `Loop of unloop_expr list ]
let rec loop_analysis : effect_expr -> unloop_expr = function
| #base_effect as base -> base
| `Loop [`Effect (image, 0)] ->
let decrement =
try - (List.assoc 0 image)
with Not_found -> failwith "infinite loop : stagnation" in
if decrement = 0 then failwith "infinite loop : stagnation"
else if decrement < 0 then failwith "infinite loop : infinite positive"
else
let unloop =
let loop_effect = function
| (0, _) -> Const 0
| (pos, v) -> Prod (Const v, Var (0, decrement)) in
List.map (fun ((pos, _) as case) -> (pos, loop_effect case)) in
`Unloop (unloop image)
| `Loop effects -> `Loop (List.map loop_analysis effects)
let unloop_from_str str =
let parsed = parse (Stream.of_string str) in
let semantic = semantize parsed in
let effects = map_exprs effect_analysis semantic in
let unloop_effects = map_exprs loop_analysis effects in
unloop_effects
Josmiley, à priori non, vu que le code et la mémoire d'exécution du programme sont totalement séparées. Mais on pourrait essayer d'explorer de ce côté là (qui pour métaprogrammation en BF ?).
Il y a d'autres langages de prog exotiques, qui ressemblent de loin au BF, où on peut modifier le code à la volée, genre le Befunge (c'est rigolo, et c'est facile d'écrire un interpréteur).
bluestorm : wow . Heureusement que tu expliques tout à côté .
Bluestorm: Intéressant. J'ai pas tout saisi sur la manière dont tu stockes les commandes plus avancées une fois que tu les à repérées dans le code. Tu as défini une structure du type "Opération-Combien-quelleDirection" ?
Je suis parti sur l'idée de définir la grammaire complète du langage afin de l'interpréter via Boost.spirit. Une fois l'arbre construit, il me semble a priori plus imple d'optimiser certaines séquences particulières.
En même temps Nanoc, construire l'arbre syntaxique du BF c'est facile non ? Je ne comprends pas de quoi tu parles parce que si c'est juste un arbre "modification case | déplacement pointeur | boucle d'instructions", ça n'est pas là que se situe la complexité de l'optimisation à mon avis.
Oui, cela ne devrait pas être trop dur. Mais je me demandais si la représentation en arbre n'était pas plus simple dans l'optique d'un élagage pour optimiser le programme.
heu...je ne suis pas sûr d'avoir bien compris le schmilblick.
dites-moi si je me trompe:
[ signifie:
-si l'octet pointé à cet instant vaut 0 sauter à l'instruction suivant le ] correspondant(en aval du code)
-si l'octet pointé à cet instant est different de 0, poursuivre l'execution
] signifie:
-si l'octet pointé à cet instant vaut 0, poursuivre l'exécution
-si l'octet pointé à cet instant est different de 0 sauter à l'instruction suivant le [ correspondant(en amont donc)
parce que j'ai tripoté mon code en long, en large et en travers mais ça fonctionne toujours pas
Intéressant, je vais tenter en Ti-Basic, mais je ne promet rien, ce sera peut-être très lent, vu la petite performance que peut fournir une calculatrice .
J'aimerais peut être faire un petit truc en c++, pour me faire progresser, mais j'aurais besoin d'un peu plus d'infos :
Quelle est la grammaire du brainfuck, en BNF ?
T'es en train d'essayer de sodomiser de petits insectes volants robocop. Et, au passage, ton arbre aura sûrement une tronche horrible.
Fais quelques recherches, tu verras que t'as vraiment pas besoin de tout ça pour interpréter du BrainFuck. C'est bien plus simple et efficace de parcourir directement le code, tu verras.
J'ai déménagé sur Zeste de savoir — Ex-manager des modérateurs.
Dans quel voie peut-t-on pousser la recherche alors ?
Si je me lance comme ça, je vais faire une traduction du code php de coucou747 !
Donc, en gros, je voulais faire comme ça :
1) On valide ou non la syntaxe de l'utilisateur, grâce à a grammaire
2) On execute le code
[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.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.