« Paradigmes et langages non classiques 2014

Ce TD permet de manipuler et d’approfondir les différents concepts abordés lors du premier cours Haskell.

Calculatrice RPN

Une calculatrice RPN travaille avec une pile. Les opérations (par exemple l’addition) travaillent avec les valeurs au sommet de la pile et les y remettent. Le but de cet exercice est de factoriser un maximum de code et de limiter la duplication.

Types de base

Le mot-clé “type” permet de déclarer un alias de type. Par exemple, le type chaîne est défini comme :

type String = [Char]

Définir un type Stack comme étant équivalent à une liste d’entiers courts (Int). Définir un type Operator représentant une fonction travaillant sur la pile. Un tel opérateur prend une pile en paramètre, utilise certaines valeurs et renvoie la nouvelle pile.

Fonctions

Définir ensuite une fonction parseOp ayant comme signature :

parseOp :: String -> Operator

qui, lorsqu’on lui passe les valeurs "+", "-", "*", fait ce qu’on attend intuitivement (la division entière en Haskell est la fonction div).

parseOp doit également reconnaître les opérateurs "dup", "swap", "drop" qui, respectivement, duplique le sommet de la pile, échange les deux valeurs au sommet de la pile, efface l’élement au sommet de la pile. "depth" renvoie le nombre d’éléments dans la pile au moment de l’appel, "pick" renvoie le n-ième élément de la pile.

De plus, si on passe une chaîne contenant un entier à parseOp, l’entier correspondant doit être ajouté au sommet de la pile. Pour cela, on pourra utiliser la fonction read qui permet, entre autres, de transformer une chaîne en une entité pour tous les objets de la classe de types Read.

Faire ensuite une fonction eval qui prend une pile et une liste [Operator] et appliquent les opérateurs à la suite. La signature d’eval sera donc:

eval :: Stack -> [Operator] -> Stack

Le lecteur astucieux remarquera qu’en fait, eval n’est pas spécifique aux piles, mais consiste à appliquer à une donnée initiale tous les opérateurs présents dans une liste et à renvoyer la donnée finale, et que la signature peut donc être dé-spécialisée en :

eval :: a -> [a -> a] -> a

En utilisant Hoogle, le moteur de recherche spécialisé Haskell, on trouvera le module à importer pour utiliser hFlush. De la même manière, on trouvera probablement une fonction existante permettant de séparer une chaîne de caractères en ses différents composants, ce qui sera utile pour implémenter parse dont la signature est à deviner. On pourra tester les opérations à l’aide du programme principal suivant :

repl :: Stack -> IO ()
repl stack = do
  putStr "> "
  hFlush stdout
  line <- getLine
  newstack <- return $ eval stack (parse line)
  putStrLn $ show $ reverse newstack
  repl newstack
main = repl []

Nombres de Peano

Les nombres de Peano permettent de représenter les entiers non-négatifs. 0 est défini comme Zero, 1 comme le successeur de Zero, 2 comme le successeur du successeur de Zero, etc. Définir, avec data, un type Peano comme étant un type avec deux constructeurs, Zero (qui ne prend pas d’argument) et Succ (qui prend un nombre de Peano). On souhaite que le type Peano puisse être une instance de la classe Num. Pour cela, il faut définir les opérations suivantes: +, -, *, signum (qui renvoie 0, 1 ou -1 selon le signe du nombre passé en argument, ou plutôt Zero ou Succ Zero vu qu’on n’a pas de nombre négatif), abs et fromInteger. La déclaration d’instance ressemblera donc à:

instance Num Peano where
  a + b = ...
  a - b = ...

On souhaite également que les nombres de Peano soient regardables : on les instancie donc avec la classe Show et on implémentera une méthode show.

Retour sur l’interpréteur RPN

Modifier l’interpréteur RPN pour qu’il utilise les nombres de Peano définis ci-dessus. On instanciera aussi la classe Read pour pouvoir saisir des nombres de Peano plus facilement.

Modifier ensuite l’interpréteur RPN afin qu’il utilise n’importe quel type qui appartient aux classes de types Integral et Read (Show sera aussi nécessaire pour pouvoir implémenter l’interpréteur).

Annexe

Il est possible de tester, en installant le paquetage Haskell QuickCheck, les nombres de Peano (s’ils sont dans un module de même nom) avec le code suivant :

module CheckPeano where

import Control.Monad
import Peano
import Test.QuickCheck

instance Arbitrary Peano where
	arbitrary = liftM toEnum $ choose (0, 10)
	shrink (Succ a) = [a]
	shrink Zero = []

-- Run only if you accept "S(S(Z))" as an input
prop_showread p = read (show p) == p
        where types = p :: Peano

-- Run only if you accept "SSZ" as an input
prop_showread_noparen p = read (filternot (`elem` "()") $ show p) == p
        where types = p :: Peano

filternot p = filter (\x -> not $ p x)

prop_eq p = p == p
        where types = p :: Peano

prop_neq p = p /= Succ(p)
	where types = p :: Peano

prop_gt p1 p2 = (toInteger p1 > toInteger p2) == (p1 > p2)
	where types = p1 :: Peano

prop_comm_add p1 p2 = p1 + p2 == p2 + p1
        where types = p1 :: Peano

prop_comm_mul p1 p2 = p1 * p2 == p2 * p1
        where types = p1 :: Peano

prop_add_sub p1 p2 = (p1 + p2) - p1 == p2
        where types = p1 :: Peano

prop_mul_div p1 p2 = p1 /= Zero ==> (p1 * p2) `div` p1 == p2
        where types = p1 :: Peano

prop_abs p = p == abs(p)
        where types = p :: Peano

prop_signum p = signum p == if p == Zero then Zero else Succ Zero
        where types = p :: Peano

prop_to_integer p = (toInteger p) + 1 == (toInteger (Succ p))
         where types = p :: Peano

prop_from_integer i = i >= 0 ==> Succ (fromInteger i) == fromInteger (i+1)
         where types = i :: Integer

main = do
        quickCheck prop_showread
        quickCheck prop_showread_noparen
        quickCheck prop_eq
        quickCheck prop_neq
        quickCheck prop_gt
        quickCheck prop_comm_add
        quickCheck prop_comm_mul
        quickCheck prop_add_sub
        quickCheck prop_mul_div
        quickCheck prop_abs
        quickCheck prop_signum
        quickCheck prop_to_integer
        quickCheck prop_from_integer

Pour tester la calculatrice RPN, on pourra utiliser :

module CheckRPN where

import RPN
import Data.List
import Test.QuickCheck

prop_dup s = length s > 0 ==> case s of (x : _) -> parseOp "dup" s == x : s
         where types = s :: [Integer]
prop_drop s = length s > 0 ==> parseOp "drop" s == tail s
         where types = s :: [Integer]
prop_swap s = length s >= 2 ==> case s of (a : b : xs ) -> parseOp "swap" s == b : a : xs
         where types = s :: [Integer]
prop_depth s = parseOp "depth" s == (fromIntegral $ length s) : s
         where types = s :: [Integer]
prop_pick s = length s >= 2 && (fromIntegral (head s) < length s - 1) && head s >= 0 ==>
              case s of (d : xs) -> parseOp "pick" s == (genericIndex xs d) : xs
         where types = s :: [Integer]
prop_add s = length s >= 2 ==> case s of (b : a : xs) -> parseOp "+" s == (a+b) : xs
         where types = s :: [Integer]
prop_sub s = length s >= 2 && fromIntegral (s !! 1) >= fromIntegral (s !! 0) ==>
             case s of (b : a : xs) -> parseOp "-" s == (a-b) : xs
         where types = s :: [Integer]
prop_mul s = length s >= 2 ==> case s of (b : a : xs) -> parseOp "*" s == (a*b) : xs
         where types = s :: [Integer]
prop_div s = length s >= 2 && fromIntegral (s !! 0) /= 0 ==>
             case s of (b : a : xs) -> parseOp "/" s == (a `div` b) : xs
         where types = s :: [Integer]

main = do
        quickCheck prop_dup
        quickCheck prop_drop
        quickCheck prop_swap
        quickCheck prop_depth
        quickCheck prop_pick
        quickCheck prop_add
        quickCheck prop_sub
        quickCheck prop_mul
        quickCheck prop_div