Exercice 1. Écrivez les fonctions Scheme suivantes : - (p arg1 arg2...) La fonction p prend un nombre quelconque de paramètre. Elle imprime chaque paramètre à tour de rôle avec la fonction display sur la sortie standard. Par exemple: (p "j'ai " (* 2 2) " pommes") imprime "j'ai 4 pommes" Note: c'est une fonction très pratique pour le déboguage! - (multimap fonction liste1 liste2...) La fonction multimap est la variante générale de la fonction prédéfinie map qui permet d'appliquer une fonction à plus d'un paramètre sur autant de listes d'arguments. Par exemple: (multimap cons '(1 2 3) '(11 22 33)) => ((1 . 11) (2 . 22) (3 . 33)) - (flatten liste) La fonction flatten prend une liste en paramètre. Cette liste peut contenir d'autres listes à un niveau d'imbrication quelconque. La fonction flatten retourne une liste à un seul niveau contenant toutes les valeurs non-liste contenues dans la liste. (flatten '((1 2) (((3)) 4) 5)) => (1 2 3 4 5) Exercice 2. Écrire en Scheme une version simplifiée de la fonction "read" de Scheme en utilisant l'approche par descente récursive. Exercice 3. Pour cet exercice vous devez modifier le compilateur miniscm pour y ajouter des nouvelles opérations et optimisations. Ajoutez les opérations bitwise-and, bitwise-ior, et bitwise-xor qui font respectivement le et-logique, ou-logique, et ou-exclusif logique "bit-à-bit" des deux paramètres. Ajoutez l'opération arithmetic-shift qui prend deux paramètres, les entiers x et y, et qui retourne x décalé de y bits. Le décalage est à gauche lorsque y est positif, et vers la droite lorsque y est négatif. Par exemple : (arithmetic-shift 8 2) ==> 32 (arithmetic-shift 8 -2) ==> 2 (arithmetic-shift 7 2) ==> 28 (arithmetic-shift 7 -2) ==> 1 (arithmetic-shift 6 2) ==> 24 (arithmetic-shift 6 -2) ==> 1 (arithmetic-shift 5 2) ==> 20 (arithmetic-shift 5 -2) ==> 1 (arithmetic-shift 4 2) ==> 16 (arithmetic-shift 4 -2) ==> 1 (arithmetic-shift 3 2) ==> 12 (arithmetic-shift 3 -2) ==> 0 (arithmetic-shift 2 2) ==> 8 (arithmetic-shift 2 -2) ==> 0 (arithmetic-shift 1 2) ==> 4 (arithmetic-shift 1 -2) ==> 0 (arithmetic-shift 0 2) ==> 0 (arithmetic-shift 0 -2) ==> 0 (arithmetic-shift -1 2) ==> -4 (arithmetic-shift -1 -2) ==> -1 (arithmetic-shift -2 2) ==> -8 (arithmetic-shift -2 -2) ==> -1 (arithmetic-shift -3 2) ==> -12 (arithmetic-shift -3 -2) ==> -1 (arithmetic-shift -4 2) ==> -16 (arithmetic-shift -4 -2) ==> -1 (arithmetic-shift -5 2) ==> -20 (arithmetic-shift -5 -2) ==> -2 (arithmetic-shift -6 2) ==> -24 (arithmetic-shift -6 -2) ==> -2 (arithmetic-shift -7 2) ==> -28 (arithmetic-shift -7 -2) ==> -2 (arithmetic-shift -8 2) ==> -32 (arithmetic-shift -8 -2) ==> -2 Ajoutez l'opération integer-length qui calcule le nombre de bits significatifs dans un entier. Par exemple : (integer-length 8) ==> 4 (integer-length 7) ==> 3 (integer-length 6) ==> 3 (integer-length 5) ==> 3 (integer-length 4) ==> 3 (integer-length 3) ==> 2 (integer-length 2) ==> 2 (integer-length 1) ==> 1 (integer-length 0) ==> 0 (integer-length -1) ==> 0 (integer-length -2) ==> 1 (integer-length -3) ==> 2 (integer-length -4) ==> 2 (integer-length -5) ==> 3 (integer-length -6) ==> 3 (integer-length -7) ==> 3 (integer-length -8) ==> 3 Le site http://graphics.stanford.edu/~seander/bithacks.html contient un bon nombre d'algorithmes qui pourraient être utiles pour ces opérations et d'autres. L'implantation de ces opérations doit fonctionner dans le cas général, c'est à dire pour tout(s) paramètre(s) valide(s), et lorsque les paramètres sont connus dynamiquement à l'exécution du programme. Puisque miniscm ne traite pas les grands entiers, dans le cas de arithmetic-shift on s'intéresse à calculer les 32 bits inférieurs du vrai résultat lorsque celui-ci est plus grand que ce qui est représentable avec 32 bits. Les exercices suivants sont optionnels. Exercice 4. Ajoutez au compilateur miniscm une optimisation pour l'opération arithmetic-shift lorsque le deuxième paramètre est une constante connue à la compilation. Exercice 5. Ajoutez aussi au compilateur miniscm une optimisation pour l'opération de multiplication lorsque l'un des deux paramètres est une constante connue à la compilation qui est une puissance de deux. Cela vous demandera d'écrire une fonction qui détermine si un entier est une puissance de deux (voir le site mentionné ci-dessus).