(** Interpréteur BF (partie 2) *) (** Pour rappel, voici les instructions de BF. Les deux dernières sont ce qu'on veut supporter en plus maintenant. | Instruction | Action | |-------------|-------------------------------------------------------------------------------------------------------| | `>` | Avance d'une case mémoire | | `<` | Recule d'une case mémoire | | `+` | Incrémente la valeur de case mémoire courante | | `-` | Décrémente la valeur de case mémoire courante | | `,` | Lit un caractère de l'utilisateur et le stocke dans la case mémoire courante | | `.
Exemples
(** Interpréteur BF pur *) (* On repart de la même base qu'avant *) type memory_command = | MoveLeft (* caractère '<' *) | MoveRight (* caractère '>' *) | Increment (* caractère '+' *) | Decrement (* caractère '-' *) type io_command = | Write (* caractère '.' *) | Read (* caractère ',' *) type control_command = | LoopBegin (* caractère '[' *) | LoopEnd (* caractère ']' *) type command = | Memory of memory_command | IO of io_command | Control of control_command let command_to_string : command -> string = function | Memory MoveLeft -> "<" | Memory MoveRight -> ">" | Memory Increment -> "+" | Memory Decrement -> "-" | IO Write -> ".
(** Un interpréteur BF (partie 1) *) (** Nous allons développer un interpréteur BF (https://fr.wikipedia.org/wiki/Brainfuck). Référez-vous à la page Wikipédia pour avoir une introduction complète au langage. Dans cette première partie, nous allons ignorer les instructions `[` et `]`. Dans les grandes lignes : en BF, on manipule des cases mémoires avec les instructions suivantes : | Instruction | Action | |-------------|------------------------------------------------------------------------------| | `>` | Avance d'une case mémoire | | `<` | Recule d'une case mémoire | | `+` | Incrémente la valeur de case mémoire courante | | `-` | Décrémente la valeur de case mémoire courante | | `,` | Lit un caractère de l'utilisateur et le stocke dans la case mémoire courante | | `.
(** Génération procédurale avec des BSP ==================================== Nous allons développer un simple algorithme de génération procédurale basé sur la partition binaire de l'espace (https://fr.wikipedia.org/wiki/Partition_binaire_de_l%27espace), *binary space partitioning* (BSP) en anglais. Cela peut par exemple être utile pour générer des niveaux dans des jeux vidéos. La génération qu'on va faire est typiquement utile pour générer des niveaux de donjons dans un Roguelike, par exemple (https://en.wikipedia.org/wiki/Roguelike). *) (** Notre génération procédurale est basée sur la partition de l'espace binaire, il nous faut donc une représentation pour les arbres binaires : *) type 'a tree = | Leaf of 'a | Node of 'a tree * 'a tree (** Il sera nécessaire d'accéder aux feuilles de ces arbres, on définit donc une fonction qui nous donne accès à toutes les feuilles.
(** Cette fonction nous sera utile *) let rec replicate (n : int) (x : 'a) : 'a list = if n = 0 then [] else x :: (replicate (n-1) x) (** Nous allons implémenter ici le jeu 2048 (https://play2048.co/), avec une interface utilisateur dans le terminal. Structures de données --------------------- Dans le jeu 2048, on déplace des tuiles annotées avec des nombres. On va simplement représenter chaque tuiles par un nombre.
(** Exemple repris de plzoo/miniprolog *) (** Syntaxe ======== On souhaite unifier des *termes*, définis comme suit. On introduit des alias de types pour distinguer des variables et des constantes. *) type variable = string type constant = string type term = | Var of variable (** les variables sont des termes écrits en majuscules, par exemple X *) | Const of constant (** les constantes sont des termes écrits en minuscules, par exemple, x *) | Compound of constant * term list (** un terme composé est par exemple f(X, y) *) (** Substitutions ============= On va utiliser des environnements pour dénoter les substitutions voulues.