PLNC 2010 Site pédagogique de l'unité d'enseignement INF355 (Paradigmes et Langages Non Classiques) de Télécom ParisTech. |
 25 juin 2010 à 13 h 30  Samuel Tardieu dans TDCalculatrice 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 (comme en Factor).
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 l’opérateur préfixe « 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.
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
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), « 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 le classe « Show » et on implémentera une méthode « show ». Ils font également partie de « Integral », « Real » et « Enum ».
Retour sur l’interpréteur RPN
Modifier l’interpréteur RPN pour qu’il utilise les nombres de Peano. Pour cela, il faudra rendre les nombres de Peano membres de la classe « Read », et adapter le type de la pile.
24 juin 2010 à 23 h 14 Samuel Tardieu dans Corrigé
module Cours1 where
-- Importation explicite du prélude en excluant certaines constructions :
-- - Maybe et tous ses constructeurs
-- - repeat
import Prelude hiding (Maybe(..), repeat)
-- Équivalence entre opérateurs et fonctions. Par exemple, (+) est la
-- fonction correspondant à l'addition et `f` ci-dessous est la version
-- opérateur de la fonction f.
x `f` y = x*2 + y*3
g x y = x*2 + y*3
x +!+ y = x*2 + y*3
-- Liste infinie de factorielle.
facts :: [Integer]
facts = 1 : (zipWith (*) [1..] facts)
-- Application partielle de !! qui permet de récupérer le n-ième
-- élément d'une liste.
fact :: Int -> Integer
fact = (facts !!)
-- Définition de la suite de Fibonacci.
fibos :: [Integer]
fibos = 1 : 1 : (zipWith (+) fibos (tail fibos))
-- Fonction constante qui, en application partielle, retourne toujours
-- la même chose lorsqu'elle est finalement appliquée.
c :: a -> b -> a
c x _ = x
-- Fonction qui fait la même chose avec son deuxième argument. J'y ajoute
-- une seconde définition s' qui utilise la fonction identité.
s :: a -> b -> b
s a b = c b a
s' :: a -> b -> b
s' _ = id
-- Équivalent de la fonction prédéfinie flip qui inverse l'ordre des
-- arguments d'une fonction en prenant deux.
fl :: (a -> b -> c) -> b -> a -> c
fl f x y = f y x
-- Lambda.
add = \ x y -> x+y
-- Nouveau type de données, affichable.
data B = T | F deriving (Show)
-- Ce type peut être utilisé pour des comparaisons en fournissant ==.
instance Eq B where
T == T = True
F == F = True
_ == _ = False
-- Type option similaire à ce qu'on avait fait en Factor.
data Maybe a = Just a | Nothing
deriving (Show)
fromJust :: Maybe a -> a
fromJust (Just x) = x
fromJust Nothing = error "empty Maybe"
app :: Maybe a -> (a -> Maybe b) -> Maybe b
app (Just x) f = f x
app Nothing _ = Nothing
-- Maybe est également un Monad si on fournit les bonnes fonctions.
instance Monad Maybe where
return = Just
fail _ = Nothing
(Just x) >>= f = f x
Nothing >>= _ = Nothing
-- Incrémentation de n'importe quel type de Monad si on utilise minc
-- avec la fonction bind (>>=).
minc :: (Monad m, Num a) => a -> m a
minc = return.(1+)
-- Utilisation de do.
mcomplex :: (Monad m, Num a) => m a -> m a
mcomplex x = do
v <- x
return $ (v+1)*2
-- En appliquant cette fonction à deux listes, on obtient le produit
-- cartésien. Si on l'applique à deux Maybe, on obtient un Maybe.
mpair :: Monad m => m a -> m b -> m (a,b)
mpair x y = do
xx <- x
yy <- y
return $ (xx,yy)
-- Utilisation d'une fonction normale à l'intérieur d'un monad en la
-- liftant. Ici, nous avons un exemple avec deux paramètres et avec
-- un seul.
liftm2 :: Monad m => (a -> b -> c) -> m a -> m b -> m c
liftm2 f x y = do
xx <- x
yy <- y
return $ xx `f` yy
liftm :: Monad m => (a -> b) -> m a -> m b
liftm f = (>>= return.f)
-- Traduction d'un do en applications successives de >>= et >>.
toto = do
x <- [1,2,3]
return 3
return (x*2)
--[1,2,3] >>= (\x ->
-- return 3 >> (return (x*2)))
-- Utilisation du monad IO.
helloworld :: IO ()
helloworld = do
putStrLn "Hello"
putStrLn "World"
-- Répétition deux fois d'une chaîne saisie par l'utilisateur.
repeat :: IO ()
repeat = do
s <- getLine
putStrLn s
putStrLn s
-- Exemple de structure avec création de fonction automatique
-- permettant d'extraire les données.
data Person = Person { first :: String,
last :: String }
deriving (Show)
-- State monad. On veut garder un état implicite tout en manipulant
-- le contenu du monad avec les fonctions monadiques traditionnelles.
data SM s a = SM {runSM :: s -> (s,a)}
-- Bien entendu, le state monad est un monad.
instance Monad (SM s) where
return a = SM $ \s -> (s,a)
(SM x) >>= f = SM $ \ s ->
let (s', r) = x s
(s'', r') = runSM (f r) s'
in (s'', r')
-- Récupération du contenu de l'état en le liftant dans le monad.
get :: SM s s
get = SM $ \s -> (s,s)
-- Remplacement de l'état en ignorant l'état initial.
put :: s -> SM s ()
put s = SM $ \_ -> (s, ())
-- Modification de l'état. C'est équivalent à
-- change f = do
-- v <- get
-- put $ f v
-- mais l'écriture avec >>= est plis simple et plus lisible.
change :: (s -> s) -> SM s ()
change f = get >>= (put.f)
-- Exemple d'une fonction factorielle qui ajoute à un état
-- numérique le nombre de multiplications effectuées.
fact' :: (Num t, Ord t) => t -> SM Int t
fact' n = if n < 3
then return n
else do
temp <- fact' $ n-1
change (+1)
return $ n * temp
-- Extraction de l'état.
state :: SM s a -> s -> s
state m i = fst $ runSM m i
-- Extraction du contenu.
content :: SM s a -> s -> a
content m i = snd $ runSM m i
-- Illustration de let, where et de la différence de scoping entre
-- les deux.
ff x = let y = x+1
in y * 2
gg x = y * 2
where y = x+1
hh x | x >= 3 = x * temp
| otherwise = seq temp x
where temp = hh (x-1)
18 juin 2010 à 13 h 30 Samuel Tardieu dans TDAujourd’hui, nous allons nous intéresser au client IRC de Factor ainsi qu’à ses possibilités d’analyser des expressions selon une grammaire EBNF.
Client IRC
En s’inspirant de la documentation du client de chat IRC, créez un client qui :
- se connecte sur le serveur « irc.freenode.net » et rejoins le channel « #inf355″ ;
- récupère les messages envoyés sur le channel et puisse réagir à ces messages ;
- salue les gens qui rejoignent le channel en envoyant « Bienvenue XXX » où XXX est le pseudonyme (nickname) du nouvel arrivant ;
- répondre « Pong XXX » à celui qui envoie « Ping » sur le channel.
Vous éviterez d’utiliser des variables nommées (qu’elles soient locales ou dynamiquement scopées). La pile est largement suffisante pour cette utilisation.
Vérifiez que vous pouvez ajouter des fonctionalités au client connecté au serveur sans couper la connexion. Idéalement, un client ne devrait jamais se déconnecter une fois connecté. Vous pourrez notamment intercepter les exceptions liées au traitement des messages (s’il y en a) et afficher un message d’erreur sur le terminal et continuer le traitement plutôt que de laisser le client se déconnecter.
Pour dialoguer avec votre robot, vous devrez également vous connecter sur IRC. Vous pouvez utiliser un de ces clients (j’utilise WeeChat pour ma part).
Grammaire EBNF
En vous inspirant de la documentation des grammaires EBNF disponibles en Factor, créez une grammaire permettant à votre robot IRC de répondre à certaines requêtes provenant du channel IRC.
Votre robot devra notamment être en mesure de répondre aux questions suivantes :
- « Quelle est la factorielle de NNN ? » où NNN est un nombre.
- « Comment t’appelles-tu ? »
- « Quel est mon pseudo ? » ou « Quel est mon nick ? »
- « Quelle est la somme de MMM et NNN multipliée par OOO ? » où MMM, NNN et OOO sont des nombres. On reconnaître également « le produit de », « ajouté à », « à laquelle on soustrait », « auquel on soustrait », etc.
- « Calcule 1+2*3-(7+10) » ou n’importe quelle expression mathématique parenthésée
Toutes ces fonctionalités devront être implémentées dans un vocabulaire séparé et testées avec des tests unitaires.
18 juin 2010 à 11 h 05 Samuel Tardieu dans Cours
IN: inf355.cours2
USING: accessors arrays assocs combinators.smart continuations
destructors fry infix io kernel locals make math namespaces
sequences ;
TUPLE: demo quot ;
: call-demo
quot>> call ;
: add-gen
[ [ + ] 2curry ]
[ [ - ] curry ] bi* compose ;
: add-gen2
'[ _ _ + _ @ ] ;
SYMBOL: myvar
:: delta
b b * a c * 4 * - ;
:: delta2
[infix sq(b)-4*a*c infix] ;
:: delta3
a b c 3array :> tab
[infix sq(tab[1])-4*tab[0]*tab[2] infix] ;
:: example1
a b :> c d ;
: example2
[let :> a :> b a b + ] ;
: example3
[let :> a a + ] ;
: delta4
swapd [ sq ] [ 4 * ] [ * - ] tri* ;
TUPLE: myclass < disposable ;
M: myclass dispose*
drop "Object disposal" print ;
: test-dispose
myclass new-disposable
[ |dispose "Code execution" print ] with-destructors
"End of code execution" print
;
MIXIN: monad
SYMBOL: current-monad
: with-monad
[ current-monad ] dip [ current-monad get ] compose with-variable ; inline
GENERIC: fail*
GENERIC: return*
GENERIC# >>=* 1
ERROR: failure ;
: fail
current-monad [ fail* ] change ;
: return
current-monad [ return* ] change ;
:: >>=
current-monad [ quot >>=* ] change ;
: telsdata
H{ { "Sam" "0661" }
{ "Julien" "0991" } } ;
: tels
telsdata at [ return ] [ fail ] if* ;
TUPLE: maybe
{ set boolean initial: f }
data ;
: just
[ maybe new t >>set ] dip >>data ;
: nothing
maybe new ;
: from-maybe
dup set>> t assert=
data>> ;
INSTANCE: maybe monad
M: maybe fail*
drop nothing ;
M: maybe return*
drop just ;
M: maybe >>=*
over set>>
[
[ from-maybe ] [ call ] bi* current-monad get
] [
drop
] if ;
INSTANCE: sequence monad
M: sequence fail*
{ } swap like ;
M: sequence return*
[ 1array ] [ like ] bi* ;
M: sequence >>=*
[ call current-monad get ] curry map concat ;
: do
[ [ >>= ] each ] curry with-monad ;
: do*
[ '[ [ @ return ] [ 2drop fail ] recover ] ] map do ;
11 juin 2010 à 13 h 30 Samuel Tardieu dans TDPréambule
Il est conseillé de faire l’échauffement avant d’attaquer les autres parties du TD. Vous avez ensuite le choix entre les tours de Hanoï (très simple) ou les engrammes (peu compliqué). Bien entendu, vous pouvez faire les deux si vous le souhaitez.
Échauffement
Définir la fonction « fact » calculant la factorielle d’un nombre. Cette fonction devra retourner 1 pour un paramètre inférieur ou égal à 0.
Rappels du cours : on pourra utiliser les mots « dup », « <= », « if ». Les blocs de code (similaires à des « lambda » sans arguments) sont délimités par des crochets « [ ... ] ». Les crochets doivent être considérés comme des mots isolés, il faut donc mettre des espaces de manière idoine.
Rappels sur le système de module
Dans Factor, on peut définir les mots qui suivront dans un vocabulaire différent en écrivant :
IN: vocab
Pour utiliser un vocabulaire particulier (et en voir les mots), on peut faire
USE: vocab
ou
USING: vocab1 vocab2 ... vocabN ;
Lorsqu’un mot n’est pas visible mais est connu, l’environnement proposera généralement d’importer automatiquement les différents modules où un tel mot est défini.
Il est possible d’encadrer certains mots de « <PRIVATE » et « PRIVATE> ». Dans ce cas, ils seront créés dans un vocabulaire dont le nom sera dérivé du nom du vocabulaire courant auquel sera ajouté « .private ». L’accès depuis le vocabulaire courant est automatique, mais ne seront pas automatiquement visible depuis d’autres vocabulaires (à moins que le vocabulaire privé soit explicitement utilisé, ce qui est un signe évident de mauvaise pratique).
Tours de Hanoï
On souhaite faire un programme permettant de résoudre le problème des tours de Hanoï. N tours sont empilées sur le plot 1, et on souhaite les faire arriver sur le plot 3 qui est initialement vide, le plot 2 l’étant aussi. À aucun moment une tour ne peut être placée sur une tour plus petite qu’elle.
Pour savoir où créer son premier vocabulaire, voir l’article « Creating a vocabulary for your first program » dans la documentation de Factor. Le vocabulaire devra se trouver dans la ressource « work » et s’appeler « hanoi ».
Affichage d’un mouvement
Faire un mot « move ( a b — str ) » renvoyant la chaîne de caractères « a vers b ». Par exemple, « 1 2 move » renverra « 1 vers 2 ».
On pourra utiliser « >base ( n radix — str) » pour transformer un entier en chaîne de caractères. On minimisera les répétitions de code en utilisant « bi@ ». On cherchera dans la documentation comment joindre ensemble deux chaînes deux caractères avec un séparateur, les chaînes étant elles-même des tableaux de caractères.
Au même endroit que le vocabulaire « hanoi », créer un fichier « hanoi-tests.factor » contenant un ou plusieurs tests unitaires pour la fonction « move ». On pourra s’inspirer de l’article
« Testing your first program » de la documentation de Factor.
Pour tous les mots définis par la suite, on écrira des tests unitaires.
Algorithme
La signature de « hanoi » est :
hanoi ( d a n -- )
où « d » est le plot de départ (entre 1 et 3), « a » le plot d’arrivée (entre 1 et 3) et « n » le nombre de tours empilées.
Chercher un algorithme récursif permettant de résoudre le problème des tours de Hanoï.
On pourra définir les mots suivants si on a besoin :
other ( a b -- o ) ! Étant donné deux plots a et b, renvoie le 3è
partial ( a b -- a b' ) ! Étant donné deux plots a et b, renvoie les deux plots a et o
! où o est le résultat de other appliqué sur a et b
Définir le mot principal « hanoi » avec la signature donnée ci-dessus. De plus, le mot « print » affiche une chaîne de caractères suivie d’un retour à la ligne. Le mot « move » défini précédemment sera également utile.
Vérifier que le programme fonctionne en appelant
1 3 3 hanoi
Cela doit afficher
1 vers 3
1 vers 2
3 vers 2
1 vers 3
2 vers 1
2 vers 3
1 vers 3
Créer des tests pour le programme « hanoi ». On pourra utiliser « with-string-writer » pour rediriger temporairement la sortie par défaut vers une chaîne de caractères.
Refactorisation du code
Éventuellement, refactoriser le vocabulaire en vérifiant à chaque étape que les tests unitaires fonctionnent toujours. Si de nouveaux mots sont créés à cette occasion, il ne faut pas oublier de rajouter de nouveaux tests unitaires.
N’oubliez pas qu’il est possible de tester les mots privés. Ne laissez visible que ce qui est nécessaire.
Engrammes
Les engrammes sont un système de numérotation exotique basé sur les facteurs premiers sortis de l’esprit torturé de Natacha Kerensikova. Le but de cette partie du TD est de concevoir un système de codage de nombres classiques sous la forme d’un engramme, puis un système de décodage d’engrammes sous la forme de nombres classiques.
Génération d’engrammes
Écrire un mot « >engramme ( n — str ) » qui génère un engramme sous la forme d’une chaîne de caractères. On pourra, pour créer des mots mutuellement récursifs, utiliser la syntaxe « DEFER: word » qui déclare que le mot « word » sera défini plus tard dans le vocabulaire.
On pourra utiliser le vocabulaire « math.primes.factors », et notamment son mot « group-factors », pour décomposer un nombre entier en facteurs premiers et leurs puissances associées. Le mot « primes-upto » pourra également être utile. Cependant, la version actuelle a un bug : « 2 primes-upto » renvoie le vecteur « V{ 2 3 } » et contient une valeur en trop. En attendant que cela soit corrigé, on pourra écrire un wrapper « (primes-upto) ( n — seq ) » qui traite différemment le cas particulier où on lui passe la valeur 2 sur la pile.
Rajouter des tests unitaires avec les exemples donnés par Natacha dans la page décrivant les engrammes.
Décodage d’engrammes
On veut écrire un mot « engramme> ( str — n ) » qui transforme un engramme codé sous forme de chaîne en nombre classique. Pour cela, on pourra par exemple décoder le chaîne à l’aide d’un mot « parse ( str — engramme ) » qui retourne un nombre (0 ou 1) ou un tableau contenant lui-même d’autres nombres ou tableaux. Ensuite, en surchargeant « >integer » sur les tableaux, on pourra transformer cette structure en nombre.
Si un engramme est mal formé, on souhaite générer l’exception « malformed ». Pour cela, on peut la déclarer à l’aide de « ERROR: malformed ; ». Cela définit le mot « malformed » comme levant l’erreur associée (et ne contenant aucun champ).
Mots utiles
On pourra éventuellement avoir besoin des mots suivants pour réaliser ce codage et décodage d’engrammes :
10 juin 2010 à 23 h 05 Samuel Tardieu dans Cours
Voici un lien vers la documentation de certains mots utilisés :
IN: inf355.cours1
USING: accessors io kernel math sequences ;
: square dup * ;
: cube dup square * ;
: myvec V{ } clone ;
: mean
[ sum ] [ length ] bi / ;
: mean'
dup sum swap length / ;
: fact
dup 2 > [
[ 1 - fact ] [ * ] bi
] when ;
: print-parity
[ "it was " ] dip odd?
"odd" "even" ? append print ;
: rev
dup length 2 >= [
unclip
[ rev ] [ suffix ] bi*
] when ;
: mysum
0 [ + ] reduce ;
TUPLE: person { first initial: "John" } { last initial: "Doe" } ;
C: <person> person
TUPLE: student < person { grade initial: 0 } ;
TUPLE: course name teacher { students initial: { } } ;
: <course>
{ } course boa ;
: add-student
[ suffix ] curry change-students ;
: add-named-student
0 student boa add-student ;
GENERIC: name
M: person name
[ first>> ] [ last>> ] bi
" " glue ;
M: student name
call-next-method "The small " prepend ;
PREDICATE: good-student < student
grade>> 10 >= ;
M: good-student name
call-next-method " (and great!)" append ;
TUPLE: teacher < person office ;
UNION: university-member student teacher ;
GENERIC: reverse-name
M: university-member reverse-name
[ last>> ] [ first>> ] bi " " glue ;
MIXIN: graded
GENERIC: grade
GENERIC: final-grade
M: graded grade drop 20 ;
M: graded final-grade grade ;
M: student grade grade>> ;
M: good-student final-grade call-next-method 20 + 2 / ;
INSTANCE: teacher graded
INSTANCE: student graded
M: number grade ;
INSTANCE: number graded
4 juin 2010 à 15 h 10 Samuel Tardieu dans Cours
package net.rfc1149.cours2
import scala.actors.{Actor,Futures,Scheduler,TIMEOUT}
import Futures._
// Demonstration of object unbuilding using unapply.
// This will be used for pattern matching.
object TripleOf {
def apply(n: Int): Int = 3 * n
def unapply(n: Int): Option[Int] =
if (n % 3 == 0) Some(n/3) else None
}
// Simple matching returning a boolean, no possibility of variable unification
object IsDouble {
def unapply(n: Int): Boolean = n % 2 == 0
}
// Definition of a container case class
case class Triple(n: Int)
// Singleton
case object Error
// Simple actor case
class Poor extends Actor {
def act = println("I am an actor")
}
case object Die
// Rich actor with differenciation based on received message.
// react and reactWithin do not return, hence the loop.
// In reactWithin, the timeout is signalled by sending
// TIMEOUT.
class Rich extends Actor {
def act = {
loop {
react {
case Die => println("I am gonna die"); exit; println("I am not here")
case s: String => println("I received a scenario for " + s)
case i: Int => {
val n = i * 2
println("I received some cash ($" + i + ") but I want $" + n)
reply(n)
}
}
}
}
}
// Simple mutex with P and V operations. A Die operation
// stops the mutex.
case object P
case object V
case object Ok
class Mutex extends Actor {
def act = {
loop {
react {
case P => {
reply(Ok)
react {
case Die => exit
case V =>
println("Waiting people " + mailboxSize)
}
}
case Die => exit
}
}
}
// Synchronous call
def p = this !? P
// Asynchronous calls
def v = this ! V
def die = this ! Die
}
// Message prioritization example
case object Alarm
case object Info
class Toto extends Actor {
def act = {
loop {
reactWithin(0) {
case Alarm => println("Alarm")
case TIMEOUT =>
react {
case Alarm => println("Alarm")
case Info => println("Info")
}
}
}
}
}
object Utils {
// "actor" is a shortcut to create a new actor from
// a block of code. Let's reimplement it ourselves.
def myActor(f: => Any) = {
val a = new Actor {
def act = f
}
a.start
a
}
}
object cours2 extends Application {
println("")
val x = future { println("Starting computation"); Thread.sleep(3000); 40 + 2 }
println("Future created: " + x)
println("Creating a poor actor")
val a = new Poor
a.start
println("Started the poor actor " + a)
println("Creating a rich actor")
val r = new Rich
r.start
println("Started the rich actor " + r)
r ! "Stargate Universe"
val expectedSalary = (r !! 1000000)
r ! Die
println("expectedSalary: " + expectedSalary)
println("expectedSalary: " + expectedSalary())
println("Future value: " + x())
println("Future value: " + x())
println("")
}
// Old main program, commented out to avoid having
// multiple ones.
object cours21 { // extends Application
println("")
println("Hello, world!")
// Matching examples. The typecast prevents Scala
// from statically resolving the type and complaining
// about impossible matches.
(Error: Any) match {
case IsDouble() => println("This is a double of some integer") // () are mandatory here
case Triple(n) => println("Simple triple " + n)
case Error => println("I got an error")
case TripleOf(n) => println("I got the triple of " + n)
case s: String => println("I got a string: " + s)
case i: Int => println("I got an int: " + i)
case (a, b) => println("I got a " + a)
}
println("")
}
4 juin 2010 à 13 h 30 Samuel Tardieu dans TDDans la continuation du cours d’aujourd’hui, nous allons maintenant jouer avec les acteurs Scala et le pattern matching (à travers les « case class » ou « unapply ») pour coder le comportement des clients d’une auberge. Les différents personnages seront codés en utilisant des acteurs séparés. On pourra, à la fin, y rajouter un soupçon de XML.
Les personnages
- Le chef cuisinier : il dispose d’un certain nombre de recettes qu’il communiquera à chaque serveur qui lui demandera. À la demande d’un serveur, il peut aussi cuisiner une de ces recettes, et cela prend un certain temps. Une fois le plat terminé, il le confie à un serveur afin qu’il l’apporte au client qui l’a commandé. Il n’y a qu’un seul chef dans l’auberge.
- Le serveur : après avoir acquis la liste des plats auprès du chef, il la transmet aux clients qui lui demandent. Lorsqu’un client commande un plat, il le commande auprès du chef. Lorsqu’un chef lui demande de livrer un plat, il l’apporte au client. Il peut y avoir plusieurs serveurs.
- Le client : après avoir demandé à un serveur la liste des plats, il en choisit un (avec un petit temps de réflexion) qu’il commande à un serveur (qui peut être différent de celui qui lui a apporté le menu) après un petit temps de réflexion. Lorsqu’il reçoit son plat, il le mange (ce qui prend un certain temps) et il quitte l’auberge. Les clients arrivent à un rythme indéterminé dans l’auberge.
Ce qu’il faut faire
- Coder les différents acteurs du système.
- Afficher des traces de chaque action effectuée par les acteurs (envoi ou réception de message).
- Simuler l’arrivée des clients dans l’auberge.
- Pour trouver un serveur disponible, vous pouvez écrire un chef des serveurs, unique, qui renvoie tour à tour l’identité de chaque serveur à solliciter. Cela revient à avoir quelqu’un qui surveille la salle et la cuisine et qui prévient un serveur qu’on a besoin de lui.
- Lire, depuis un fichier XML, la liste des recettes disponibles et le nombre de serveurs à utiliser. Ci-dessous se trouve une illustration de ce que pourrait contenir ce fichier.
<auberge>
<serveurs>2</serveurs>
<recettes>
<recette>Dinde aux marrons</recette>
<recette>Bœuf bourguignon</recette>
<recette>Morilles aux truffes</recette>
<recette>Pâtes au jambon</recette>
<recette>Sauté de veau sauce Télécom</recette>
</recettes>
</auberge>
30 mai 2010 à 23 h 35 Samuel Tardieu dans AdministratifVoici quelques idées de projets pour cette année. N’hésitez pas à en proposer d’autres ou à adopter un projet (en postant un commentaire). Tous les langages non-mainstream et non-jouet sont envisageables.
Application pour Android en Scala
À l’instar de HarassMe, on développera une application pour Android en Scala. L’application devra, avec l’aide de sbt, utiliser les bibliothèques Android, et disposer de tests fonctionnels natifs et de tests tournant sur l’appareil. L’utilisation d’API publiques est recommandée, par exemple un interfaçage avec thetvdb.com pour une application qui donne la liste des épisodes de séries (mais toute autre application est la bienvenue).
Si l’application proposée est particulièrement ambitieuse ou implique une communication entre utilisateurs distants (jeu multi-joueurs par exemple), elle pourra être réalisée en binôme.
Il est important de bien séparer les différentes fonctionnalités afin de permettre la réutilisation d’un maximum de composants dans de futures applications.
Réplication des fonctionnalités de distribution et de supervision d’Erlang en Scala
Scala s’est inspiré d’Erlang pour le modèle de communication entre threads utilisant les acteurs. Mais Erlang va beaucoup plus loin, en offrant notamment :
- la communication entre processus se trouvant sur des noeuds distants et l’envoi de messages de manière indifférenciée entre processus locaux et processus distants
- l’utilisation d’un serveur de noms pour pouvoir nommer les processus
- un framework de supervision permettant de détecter et relancer automatiquement les processus défaillants selon le modèle de développement « laisser les processus défaillants crasher, ils seront relancés si le besoin s’en fait sentir » plutôt que le « rattraper et traiter l’exception à tout prix »
- un framework de logging permettant d’enregistrer la trace des défaillances de l’application
- un framework (OTP) permettant de coder facilement des processus serveurs et des machines à états : seules les fonctions de callback sont à fournir par l’utilisateur, la partie répétitive et compliquée à implémenter correctement étant fournie par la bibliothèque OTP
Ce projet, s’il est réalisé de manière complète (avec documentation et tests) peut être réalisé par un binôme. Je tiens le livre « Erlang Programming » (de Cesarini & Thompson) à la disposition des personnes intéressées.
Jeu de rôle en réseau multi-langages
Le but de ce projet est de développer un jeu de rôle multi-joueurs accessible par le réseau en mode texte (en s’y connectant avec « telnet » par exemple). Le jeu doit comprendre des commandes (« north », « look at sign », etc.) et générer des descriptions, des réponses et des actions. Il doit être possible d’y coder le comportement des PNJ (personnages non-joueurs) et des objets dans différents langages de programmation, et les différents programmes doivent pouvoir tourner sur des machines séparées. Les différents langages devront communiquer en utilisant par exemple les Protocol Buffers de Google. Le joueur devra pouvoir stocker des objets dans son inventaire, ces objets étant représentées sous la forme de callbacks permettant de rappeler le module approprié.
On devra utiliser au minimum trois langages non-classiques différents. Le jeu peut être réalisé seul ou en binôme.
26 mai 2010 à 07 h 30 Samuel Tardieu dans TDDans ce TD, nous allons mettre en œuvre les concepts illustrés par Alexandre lors du cours de la semaine dernière. On pourra consulter la documentation en ligne de Scala, ainsi que le livre Programming Scala disponible également en ligne.
Pour faire le TD, vous aurez besoin d’installer sbt (simple build tool). Une fois ceci fait, récupérez le fichier contenant le squelette de l’application, déplacez vous dans le répertoire « td1″ après extraction et lancez « sbt ». Il faudra lancer la commande « update » pour récupérer les bibliothèques de test.
Le code devra être placé dans un ou plusieurs fichiers localisés dans « src/main/scala/ ». Vous pouvez voir les tests dans « src/tests/scala/Tests.scala ». Ces tests sont écrits dans un DSL fourni par le paquetage « scalatest ». Un certain nombre de tests sont écrits, il vous faudra les décommenter au fur et à mesure.
Tout le code devra se situer dans le paquetage « net.rfc1149.td1″ (voir la directive au début du fichier « src/main/scala/td1.scala »).
isOdd/isEven
Implémenter des fonctions « isOdd » et « isEven » prenant en paramètre un « Int » et retournant un « Boolean » (dont vous devinerez aisément ce qu’elles font) et testez les avec la commande « test » de « sbt ». Ces fonctions devront être placées dans l’objet « TD1″ (rappelons qu’il n’existe pas de méthodes statiques en Scala).
Classe paramétrée ExtSeq
Faire une classe « ExtSeq » paramétrée par un type « T » prenant comme argument de constructeur un « Seq[T] » (une séquence abstraite d’objets de type T). Cette classe devra implémenter les méthodes « any » et « all » prenant chacune une fonction transformant un objet de type « T » en « Boolean ». Un tel type se décrit comme « T => Boolean » en Scala. Les méthodes doivent respectivement vérifier si au moins un élément respecte la condition passée en argument, et si tous les éléments respectent cette condition.
Un objet de même nom que la classe devra fournir une fonction « toExtSeq » déclarée comme implicite permettant de transformer un « Seq[T] » en « ExtSeq[T]« .
Décommenter les tests et tester. Si la fonction implicite « toExtSeq » est bien visible directement, on pourra appliquer les fonctions « all » et « any » à tous les types de séquences, par exemple les listes (fonctionalité « Pimp my library »).
myWhile/doWhile
Implémenter dans l’objet « TD1″ une fonction « myWhile » prenant en paramètre un booléen « par nom » (c’est-à-dire non évalué) dont la signature en Scala se note « => Boolean » ainsi qu’une fonction sans paramètre et retournant n’importe quoi (le résultat sera ignoré) à appeler tant que la condition est vraie. Tester.
Implémenter une classe « ExtCond » (et son objet associé pour une conversion implicite d’un « => Boolean » en ce type) qui fournit une méthode « doWhile » qui fera la même chose que précédemment (mais ne prendra bien sûr que l’action en paramètre). Tester.
Complex
Implémenter un type « Complex » prenant en paramètre deux doubles (les parties réelles et imaginaires). On utilisera une « case class » pour bénéficier de certains automatismes comme la définition correcte de l’égalité ou la déconstruction pour l’utilisation dans le cadre du pattern matching. L’affichage, par la surcharge de la méthode « toString », devra être naturel, par exemple « 1.2″ ou « -3.4+5.6i » ou encore « -3.0i ». Tester l’affichage.
Implémenter la fonction « reciprocal » renvoyant le conjugué, ainsi que l’addition entre complexes. Tester.
Autoriser à l’aide d’une fonction implicite les opérations avec les « Double ». Tester.
Rajouter les autres opérations (-, /, *, abs, etc.) ainsi que des primitives de tests unitaires.
Les N reines
Implémentez dans l’objet TD1 (ou changez le nom dans le driver de test) une fonction avec la signature suivante :
def solveQueens(numberOfQueens: Int, f: List[(Int, Int)] => Unit): Unit qui appelle la fonction « f » avec chaque liste de paires représentant une solution au problème des « numberOfQueens » reines. On pourra utiliser si nécessaire les constructions suivantes :
- « A to B » (où « A » et « B » sont des entiers) : liste des entiers entre A et B (compris)
- « toList », s’appliquant à une séquence et la transformant en liste
- « head »/ »tail »/ »last » qui s’appliquent à une liste et donnent respectivement le premier élément, tous les éléments sauf le premier et le dernier élément
- « foreach » pour parcourir une liste et exécuter des actions
- « return » pour sortir prématurément d’une fonction
- « for » (voir cette documentation sur les compréhensions)
- Les fonctions « :: » et « ::: » des listes. On remarquera qu’en Scala les opérateurs terminant par un « : » sont recherchés dans l’opérande de droite plutôt que dans celui de gauche.
Il est permis à ce stade de regretter l’opérateur angélique que nous avions implémenté en Scheme. Notons que Scala 2.8.0 appportera les continuations sous la forme d’un plugin, mais que celles-ci sont délimitées et que l’implémentation de « amb » serait donc non triviale.
|
|
Commentaires récents