Affichage des articles dont le libellé est science. Afficher tous les articles
Affichage des articles dont le libellé est science. Afficher tous les articles

mardi 23 juin 2009

Les promesses de la programmation fonctionnelle

Disclaimer : Je me permets un post cours et un peu dans l'urgence pour vous proposer un document qui risque de ne pas être éternellement disponible librement... Si le lien ci-dessous ne vous permet pas d'accéder à la version PDF (ici) de cet article, c'est qu'il est trop tard... Désolé.

Juste un petit message pour signaler la publication récente d'un article (scientifique) qui me semble intéressant, à propos de programmation fonctionnelle :

The Promises of Functional Programming,
de Konrad Hinsen (CNRS Orléans)
L'auteur axe sa réflexion autour des qualités de ce type de langages, s'attardant sur la famille "LISP - Clojure" (dans laquelle il inclut implicitement Erlang, pour ceux qui se demanderaient où le placer...) et "ML" ; à savoir robustesse et compacité du code et surtout facilité de parallélisation, un aspect aujourd'hui crucial en calcul scientifique (domaine de l'auteur).

J'espère reparler rapidement ici de programmation fonctionnelle, mais sous un angle un peu particulier, puisque je ne pratique aucun langage fonctionnel à proprement parler...

Bonne lecture !

mercredi 1 avril 2009

Algorithme naïf de cryptage d'entrée

Je vous propose aujourd'hui un petit algorithme dans le domaine de la cryptographie, implémenté en Ruby. Comme vous allez le voir, il s'agit d'un algorithme à clef secrète générée aléatoirement au moment du chiffrement. Cette méthode est assez peu intéressante pour la plupart des applications de cryptage (transfert de message notamment) de par le fait que la clef doit être transmise afin que le destinataire puisse décrypter le message. Dans ce cadre, on utilise plus volontiers la cryptographie asymétrique (RSA, etc...), ou, pour des raisons de performances, une méthode symétrique dont la clef est cryptée de façon asymétrique.


En revanche, cet algorithme me semble utilisable pour un autre genre d'applications : de façon locale, afin de crypter une réception de donnée par exemple.

Contexte

Plusieurs hypothèses tout d'abord. La donnée à recevoir peut être accédée par morceaux (bits, lettres, chiffres, lignes, pages, etc...). On ne connait pas à priori sa taille. On suppose également que l'on peut pareillement accéder à un nombre important de données similaires.



Principe : Se fondre dans la masse

Le coeur de la méthode consiste à noyer l'information que l'on souhaite recevoir (notée A dans la suite, data dans le code) la recevant par morceaux, au milieu d'une foule d'autres informations similaires, de façon aléatoire.
Pour cela, on construit des "cycles" de taille aléatoire, dont seuls certains index (aléatoires eux-aussi) contiennent des parts de données intéressantes. La clé consiste en la liste des cycles utilisées (plus simplement, la liste des couples [occurences de part de A, taille du cycle]).

Le code

Dans mon implémentation en Ruby, j'applique l'algorithme à un tableau. L'input dummies correspond donc à une liste de données. La sortie est la paire [données cryptée, clé]

Cryptage :



A noter que je clone l'entrée data afin que la méthode soit non destructive sur celle-ci.

Décryptage :



On décrypte par morceau correspondant chacun à un cycle de la clef.

Exemple :

Pour tester cette méthode :



Ce qui donne un résultat du genre (pour rappel, la clef est profondément aléatoire...) de celui-ci.


Conclusion

Encore une fois, il s'agit d'une méthode naïve, à utilité limitée (je suis un grand débutant en crypto). Cependant, pour un usage local, elle me semble adaptée, bien que probablement peu performante en terme de vitesse (celle-ci étant conditionnée par l'ampleur des cycles et le nombre d'occurrences par cycle, ici en dur).
J'ai du mal à me figurer de grosses failles dans cet algorithme, si ce n'est pour ce qui est de l'utilisation de la randomisation : 1/ sa complexité étant dans l'absolue aléatoire, elle ne peut être calculée que par majoration dans le meilleur des cas (le meilleur des cas en crypto étant en fait le pire des cas en algorithmique), 2/ des failles existent sur des implémentations standards des méthodes random (présence de cycles, etc... Des méthodes plus abouties existent cependant, notamment celles utilisant des propriétés physiques du matériel informatique, comme la température par exemple).

Notes :
1/ Crédit photo : Jan Chipcase
2/ Ceci n'est pas un poisson d'Avril. J'aime pas cette tradition de clampes.

dimanche 8 février 2009

Atlas du monde réel

Il y a de nombreuses façons de représenter le monde qui nous entoure. Traditionnellement, un carte représente le monde en tant qu'espace "physique" (ou plus exactement, une de ses projections) le plus fidèlement possible en termes de surfaces et distances.
Un cartogramme tente lui de représenter le monde en fonction d'une variable donnée : PIB d'un pays, densité de la population, taux d'accès à une ressource, etc. Pour ce faire, il déforme les surfaces et les distances réelles proportionnellement à la variable qu'il exprime. Cette technique est relativement récente : inventée durant le XIXème siècle, elle n'est fréquemment utilisée que depuis la seconde moitié du XXème. Par exemple, ci-dessous, la répartition des destinations touristiques dans le monde (où l'on peut voir que la France, l'Espagne et l'Italie apparaissent bien plus volumineuses que sur une carte classique de par leur forte attraction touristique). De nombreux cartogrammes sont consultables en ligne sur le site WorldMapper.



L'Atlas du monde réel (chez l'éditeur) propose avec 366 cartogrammes une représentation originale et souvent très efficace du monde, sur des problématiques très diverses (économiques, politiques, ressources, sociologiques, médicales, culturelles, etc...).

L'une des très grandes qualités de cet ouvrage (hormis sa présentation très claire et agréable) se cache derrière la méthode employée pour la génération de ses cartes. En effet, il s'agit d'une méthode numérique récente (2004) développée par Michael Gastner et Mark Newman (coauteur de l'ouvrage et chercheur numéricien à l'université du Michigan).
Cette méthode se base sur le phénomène physique de la diffusion (mécanique des fluides/thermique) : les territoires représentés se déforment comme s'il s'agissait de ballons contenant du gaz (la variable étudiée) avec des zones de pression (les zones de fortes densités de population, le plus souvent). Article de référence : Diffusion-based method for producing density equalizing maps, Michael T. Gastner and M. E. J. Newman (PDF).
D'un point de vue purement numérique, l'équation de la diffusion est résolue par une transformée de Fourrier rapide (FFT) et intégrée par une méthode de Runge-Kutta d'ordre 4. Selon les auteurs, une précision à 1.0E-4 (cela peut paraître décevant, mais une précision plus grande n'est quasiment pas observable humainement) est obtenue en peu d'itérations (ordre de temps de calcul : quelques minutes sur un ordinateur de bureau).

Ce qui m'a paru intéressant dans cette méthode, c'est l'application d'un problème de physique (la diffusion/mécanique des fluides) à un contexte tout à fait décalé (cartographie/représentation des données). Dans l'article cité plus haut, sont listées les précédentes méthodes de génération de cartogrammes, dont une autre consiste en une analogie physique avec l'élasticité des matériaux (mécanique solide déformable).
Dans d'autres domaines, pour ce type d'analogie, on peut citer l'utilisation de méthodes de CFD (calcul en mécanique des fluides) dans des calculs de trafic (routier ou autre) ou en finance ("flux" monétaires...).


Références :



Autres liens en vrac à propos des cartes :



Note : le cartogramme présenté ci-dessus est tiré de l'"Atlas du monde réel" et appartient à ses auteurs.

mardi 23 décembre 2008

Notations...

Il existe différentes façons de présenter les expressions mathématiques, les définitions de fonctions ou encore du code informatique. Juste pour l'exemple, sur l'expression [(5+1)*7 = 42] voici les 3 notations les plus courantes en programmation :



La notation infixée est la plus courante. C'est celle que l'on utilise la plus généralement tant en mathématiques qu'en programmation (j'entends par là, dans la majorité des langages...). Les opérateurs se placent entre les opérandes.

La notation préfixée place l'opérateur avant les opérandes. On la retrouve dans des langages tels que LISP ou Scheme. Même si elle peut paraître assez peu intéressante sur cet exemple, elle présente un grand intérêt : ne pas limiter un opérateur à seulement 2 opérandes. Par exemple [1 + 2 + 3 + 4 = 10] peut s'écrire plus succinctement [(+ 1 2 3 4)].

Enfin, la notation postfixée (ou Polonaise inversée) place elle les opérateurs à la suite des opérandes. Celle-ci est quasi-systématique dans les langages concaténatifs tels que Forth, Factor, Joy ou Cat (dont on devrait reparler ici très prochainement...). Vous remarquerez son absence de parenthèse : c'est son idée de base.

jeudi 24 juillet 2008

Algorithme Rho de Pollard en Ruby

L'algorithme Rho de Pollard permet de décomposer un entier en son produit de facteurs premiers. Cet algorithme se base sur une fonction dite aléatoire f, permettant d'obtenir une suite cyclique :

xi+1 = f(xi) % n


avec n l'entier à décomposer.

Attention, si :

pgcd(|xi - x2i|, n)

prend n pour valeur, l'algorithme produit une boucle infinie (il faudrait (y a qu'à...) alors changer la fonction f ou aller se faire cuire un steak de soja) : dans mon code, je lève une erreur, en l'occurrence.
Sinon, beaucoup de récursion...

Code prime.rb :
(Ruby 1.8.6 : $ prime.rb [integer])

def pgcd m, n
(n==0)? m : pgcd(n, m%n)
end

def f x, n
(x**2 + 1) % n
end

def x i, n
(i==0)? 2 : f(x(i-1,n), n)

end

class Integer
def is_prime?
res = true
if self < 2 then
res = false
else
for i in 2..Math.sqrt(self).to_i
if i.is_prime? and (self%i == 0) then
res = false
end

end
end
res
end
end

def pollard n
r = []

if n.is_prime?
r.push n
elsif n != 1
i, p = 0, 1
while p == 1
i += 1
p = pgcd((x(i,n)-x(2*i,n)).abs, n)
end

raise "Pollard Algorithm: Cycle FAIL" if p==n

if p.is_prime? then
r.push p
else
r.push pollard(p)
end

r.push pollard(n/p)
end
r.flatten!
r
end

input = ARGV[0].to_i
pollard(input).each {|x| puts x}

samedi 7 juin 2008

Ruby Duck-Safe interface

Suite à un précédent article sur DiamondBack Ruby, j'ai un peu réfléchis à la question de la sécurisation de l'appel de fonctions/procédures/méthodes, au niveau des types dans un langage dynamique tel que Ruby (/Python,/Perl/Etc...).

Finalement, quel est le problème ? Quelque soit le paradigme, il se situe au niveau de la capacité d'une fonction/procédure/méthode à traiter ses arguments en fonction de leur type, classe ou comportement. Problème simple donc. (Les aspects plus bas niveau sont ici peu intéressants : on est actuellement capables de les éluder).

Tout est dans la notion d'interface : dans les langages statiques, une interface n'est pas seulement un moyen d'appeler un "service" (fonction/méthode/...) mais c'est également un "contrat" qui impose des conditions sur les informations passées à l'appel (le plus souvent sur leur type). Par exemple, la fonction acheter_une_baguette ne peut se contenter de prendre 0.45 en argument : il faut que 0.45 soit en €, "de type €".

Ruby est un langage dynamique comme tant d'autres. Mais de par sa conception, sa "philosophie", il fait le choix de se concentrer sur ce que fait un objet plutôt que sur ce qu'il est : c'est le Duck Typing. On peut facilement critiquer cette approche du typage pour plusieurs raisons. Cet article sur Otaku en expose plusieurs. Pour ma part, je me contenterais de dire qu'elle réside dangereusement sur la langue (quel rapport entre Balançoire.balancer et Coupable.balancer ?).

Mais les langages statiques ne sont pas nécessairement satisfaisants sur ce point non plus. Pour faire un parallèle avec les mathématiques, on peut considérer que :

f : R -> R
x |-> x + 2

avec R l'ensemble des réels, est une déclaration de type statique.

Pour autant, f reste valable de N dans N (naturels), de C dans C (complexes), etc... Le Duck Typing assure que f est valable du moment que x possède une méthode "+", ce qui évite de redéfinir f pour chaque espace où cette fonction est valable.

Mais est-ce suffisant ? Prenons :

f : x |-> 2 / x

Dans ce cas, on doit de plus assurer que x n'est pas nul. Si mathématiquement, cela s'exprime sur l'espace sur lequel est défini x, "informatiquement" on aura le plus souvent x entier ou flottant. Les contraintes sur un argument ne se limite donc pas à son type/classe, ni à son comportement (possède méthode "+"), mais aussi à d'autres paramètres, comme son état (ici sa valeur). De plus, s'il s'agit ici d'un exemple simple : il existe probablement d'autres exemples mettant en évidence l'influence du contexte d'appel.

Je vous propose ici un module (naïf) permettant d'exprimer assez simplement, lors de l'implémentation d'une méthode, les contraintes associées à ses arguments. Le but est d'assurer ces contraintes sans pour autant surcharger le code de structures conditionnelles avec gestion d'exceptions : on déclare simplement notre contrat.

(sources également disponibles **sans fuck1n' coupure** ICI)

module Safety

# Negator for error message
@@neg_converter = {:is_a? => "is not a",
:respond_to? => "does not respond to",
:include? => "does not include",
:each_element_is_a? => "contains element(s) that is(are) not"}

# Ensure that constraints are respected
def ensure_it cstr
cstr.each do |arg, cstrs|
value = cstrs[0]
cstrs[1...cstrs.size].each do |pair|
if not value.method(pair[0]).call(pair[1]) then
raise "Argument #{arg} (#{value.inspect}) \
#{@@neg_converter[pair[0].to_sym]} #{pair[1]}."
end
end
end
end

private

# A simple example of constraint method
def each_element_is_a? klass
assertion = true
self.each do |elt|
assertion = false if not elt.is_a? klass
end
assertion
end

end


La méthode ensure_it checke les contraintes passées. Une contrainte est facilement exprimable par une méthode telle que each_element_is_a?.

Exemples :


require 'Safety'

class Fixnum
include Safety
def mult_by_plus num1, num2
ensure_it({:num1 => [num1, [:is_a?, Fixnum]],
:num2 => [num2, [:respond_to?, :next]]})
self*num1+num2
end

end

a = 1
puts a.mult_by_plus(1,2)
puts a.mult_by_plus(1,1)
puts a.mult_by_plus(1,1.0) #=> Error raised


Et :


require 'Safety'

include Safety

def potamok tab
ensure_it({:tab => [tab, [:respond_to?, :each],
[:each_element_is_a?, Fixnum]]})
val = 0
tab.each do |elt|
val += elt**2
end
val
end

puts potamok [42,33,59]
puts potamok [1,2,3,6,59.3] #=> Error raised


Toute remarque est la bienvenue.

mercredi 21 mai 2008

Typage statique pour Ruby

Via cet article sur Segment7, voici le lien vers une publication sur le développement de DRuby (DiamondBack Ruby) [:en, :pdf] : un outil (codé en OCaml) visant à autoriser le typage statique en Ruby. Le code source de cette application devrait être publié dans les mois à venir.

J'ai un avis assez mitigé sur ce genre de projet : d'un côté, j'apprécie la possibilité de choisir (cf. article précédent sur le typage en Groovy), et je reconnais tout à fait beaucoup des avantages du typage statique. Parmi eux, une certaine fiabilité et la détection précoce d'erreurs de développement.
Mais en Ruby (Perl, Python, etc...) ? L'un des avantages de ces langages dynamiques n'est-il pas d'"éluder" au maximum les contraintes de type pour un développement plus rapide et libre ? En Ruby en tout cas, la "philosophie" veut que l'on s'intéresse davantage au comportement d'un objet (no primitive type here !) qu'à sa classe (principe du "Duck Typing"). On croise donc plus souvent des foo.respond_to? :a_method que des foo.is_a? A_Class.

Il est cependant intéressant de se poser la question suivante (et pas seulement en Ruby !) :

Comment et/ou avec quelles techniques, assurer la fiabilité d'un programme dans un langage dynamique ?

Je vais essayer de bientôt placer quelques petits exemples de code sur ce sujet.

mercredi 2 avril 2008

Une classe pour une fonction

Une petite idée comme ça : plutôt que d'appeler directement une fonction, comme ici (loi des gaz parfaits) :

def compute_p v, n, t
r = 8.314
p = (n*r*t)/v
return p
end
puts "p = #{compute_p(1.0, 10.0, 273.5)}"


Pourquoi ne pas créer une classe, représentant cette fonction ? En effet, on peut alors définir un certain nombre d'options à l'exécution "internes" à notre fonction (ici, j'ai mis des exemples simples : print pour un affichage console, et clock pour retarder l'exécution d'un temps donné). On pourrait aussi sécuriser les arguments (non fait ici...) par rapport à des contraintes internes à la classe (ex : température > 0, autre ?) ou décider de remplacer certains arguments sous certaines conditions, éventuellement externes. Et bien d'autres choses, pour des problématiques concurrentielles... Des idées ?


class Compute_p_class

# Initializing the arguments as attributes
def initialize args
@v = args[:v]
@n = args[:n]
@t = args[:t]
@@r = 8.314
@opt = []
@opt_args = {}
end


# To add an option at execution
def add_option option, argopt = nil
@opt.push option
@opt_args[option] = argopt
end

# Wait for @opt_args[:clock] s before executing
def option_clock
t_beg = Time.now
t = t_beg
if @opt.include? :clock then
while t < t_beg + @opt_args[:clock]
t = Time.now
end
end
end

# Verbose-like
def option_print
if @opt.include? :print then
puts "Executing function Compute_p"
puts "with arguments"
puts "v = #{@v}"
puts "n = #{@n}"
puts "t = #{@t}"
end
end

# Execution after options
def execute
# Options management
option_print
option_clock
# Function core
p = (@n*@@r*@t)/@v
return p
end
end

values = {:v => 1.0, :n => 10.0, :t => 273.5}
calcul = Compute_p_class.new values
calcul.add_option :clock, 5.0
calcul.add_option :print

puts "p = #{calcul.execute}"

mercredi 26 mars 2008

Google Summer Of Code

Cette année encore, Google organise le Summer of Code (abrégé en SoC) : il s'agit d'une opération permettant à des étudiants du monde entier de s'investir dans un grand projet libre le temps de l'été. Pour en savoir plus :

Plutôt que de plagier cette dernière news très bien faite, je vais juste apporter quelques remarques.

Beaucoup de projets impliqués ; Un grand absent ?

De mes petits yeux fatigués, j'ai compté 177 projets libres participant au programme. C'est énorme. Chacun profitant de l'engagement de plusieurs étudiants, à temps plein, pendant 2 mois complets, il faut se figurer le bénéfice que cela génère pour le monde du libre ! Sans compter les 4500 $ pour l'étudiant et 500 $ pour le projet en cas de succès...

On retrouve beaucoup de noms très connus du monde libre : Apache, The GIMP, Wikimedia, Linux, Mozilla... ( Mais aussi certains un peu moins célèbres qui m'ont fait plaisir comme Battle for Wesnoth).

Mais il en manque certains, dont un qui saute aux yeux : OpenOffice.org. Pourquoi ? Vraiment là, je donne ma langue au chat... (Mauvaises relations avec Google ?).
J'ai aussi noté l'absence totale de logiciel de P2P (Azureus et Bittorrent sont eux aussi libres). Là en revanche, ça peut s'expliquer plus simplement vu l'utilisation souvent approximativement légale de ce type d'application. Quoique. A ce compte là, on pourrait exclure tous les projets de langage de prog' : on peut potentiellement en faire mauvais usage...

Les langages ? (Ruby ?)

Question essentielle s'il en est... On en retrouve un nombre considérable : C, C++ et Java bien sûr. Mais pas seulement. La plupart des langages de script sont là : PHP, Perl, Python, Ruby, Javascript, Groovy, Scheme... Et aussi du fonctionnel pour les durs : LISP (CommonLISP et Scheme notamment) et Haskell au moins. Et puis des langages de grognards : Fortran et Ada notamment sur GCC.
Au passage, je trouve vraiment exceptionnel de pouvoir participer, en tant qu'étudiant, au développement d'un "grand" langage via ce programme : LISP, PHP, Perl... Geeky !

Et le Ruby ? On le retrouve sur différents projets, et pas forcément ceux auxquels on pouvait s'attendre...
Certes, il y a Ruby Central dont les propositions de sujet sont très axées sur Merb et sur la collaboration avec d'autres langages (Python et Java notamment) ou d'autres interpréteurs (JRuby et Rubinius).
On retrouve ensuite Ruby dans les projets Codehaus (JRuby) et... NESCent : le "National Evolutionary Synthesis Center" sur le projet Bio* (Bio_ : Perl, Python, Ruby, SQL, Java...) dans le domaine de la bio-informatique. Ruby en science ?

Triple-win ? (Winwinwin...)

Vous l'aurez compris, je suis très favorable à ce type d'opération qui semble profitable aux trois protagonistes :
  • Pour les étudiants : de l'expérience (très valorisable) et potentiellement une rétribution non négligeable.
  • Pour les projets : 2 mois de travail par étudiant (+ 500 $ ?), un peu de pub, et potentiellement un nouveau contributeur régulier avec de l'expérience.
  • Pour Google : de la pub ciblant plus particulièrement le monde du libre. Mais aussi une grosse manœuvre RH de pré-recrutements éventuels.
Pourquoi je pose cette question ?

Parce qu'il est toujours bon de savoir pourquoi l'on reçoit de l'aide ou de l'argent. J'apprécie Google pour différentes raisons et différents produits. Mais si les pratiques de cette entreprise me paraissent bien plus correctes que d'autres (là je pense très fort à la petite boîte de Bill le portail, mais aussi au principal concurrent de Google pour la recherche en ligne, et malheureusement parfois à l'autre pomme...), elle n'en reste pas moins une entreprise comme une autre (peut être plus riche, certes...).
S'il serait dommage de tomber dans la paranoïa libriste extrémiste malheureusement trop courante, il faut néanmoins que le monde du libre sache clairement garder son indépendance et ses valeurs, tout en s'ouvrant davantage sur le monde de l'entreprise. Cela semble être le cas ici.

En bref...

Si contrairement à votre serviteur vous êtes (encore) étudiant et vous avez un poil de talent (l'acharnement marche aussi parfois...) : allez (re-)jeter un coup d'œil sur la page du SoC 2008...


jeudi 20 mars 2008

Matrices en Ruby : 3 - Linalg !

Les matrices sont assez mal gérées de base en Ruby (cf articles précédents : [1] et [2]). Heureusement, il existe une bonne bibliothèque basée sur LAPACK (Linear Algebra PACKage, bien connue en Fortran) :

Comme indiqué dans sa doc, cette lib permet pas mal de choses : gestion simple et fiable des matrices, opérations classiques (déterminant, trace, valeurs propres...), décompositions diverses (LU, Cholesky...) et différentes autres méthodes.

L'installation est simple. Ensuite un simple require 'linalg' suivi de include Linalg, et c'est parti ! La doc contient un bon petit tuto (recopié dans le README) d'introduction pour faire tour avec irb.

Deux petits exemples d'utilisations :

Problème N-corps :

N corps interagissent gravitationnellement selon la loi de Newton. Dans cet exemple, j'utilise Linalg uniquement pour la structure de mes vecteurs position et vitesse. Code crade et valeurs mal choisies...


Convection-diffusion :

Ici, il s'agit de la résolution 1D par la méthode des différences finies de l'équation d'advection-diffusion d'un scalaire passif (exemples : polluant en rivière, transfert de chaleur...). La méthode mathématique a été écrite rapidement... j'ai essayé de faire en finesse : la partie diffusive est centrée, et la partie advective décentrée. Mais du coup, j'ai pas pris le temps de faire de calculs de conditionnement et de condition CFL, ni de faire un schéma en temps moins brutal que du pur explicite... Je me suis cependant autorisé la possibilité de faire varier le champs de vitesse au cours du temps (utile par exemple pour coupler avec un modèle de calcul de champs de vitesses : Saint Venant pour de l'hydraulique ?). Par contre, ici aussi, les valeurs proposées sont assez mauvaises (pas de diffusion notamment !) : n'hésitez pas à tester avec d'autres !


Toute question, remarque ou commentaire est le bienvenu !

dimanche 2 mars 2008

Travail, travail...

Dans la vie, on fait pas toujours ce qu'on veut : Scheme va devoir un peu attendre... j'ai trouvé du taf :
Du coup, la fréquence de publication sur ce blog devrait baisser sensiblement dans les prochaines semaines. Je n'abandonne cependant pas ni ce blog, ni les petits langages que j'aime : en cas de disette, je posterai des vieux codes rigolos sortis des placards, en Fortran ou Ruby notamment. Je reste à l'affut sur le SDZ également.

Pour parler prog', j'avais cité Ada l'autre jour, et je l'attaque donc pour le boulot. Je ne suis pas persuadé de pouvoir "blogger" là-dessus tout de suite : il s'agit d'un langage assez particulier. OO dans sa version 95, mais avec de grosses séquelles de son origine procédurale. Il est souvent préféré au C dans le cadre d'applications critiques (pour systèmes embarqués notamment) pour sa rigueur imposée, sa meilleure (à priori) gestion des tableaux (et des problèmes d'indices), et sa capacité à ajouter des "règles" (contraintes) supplémentaires au compilateur : le tout dans un soucis permanent de fiabilité de l'exécutable. Exécutable plus volumineux qu'en C en revanche, mais (selon certaines sources) d'une vitesse (notion importante en temps réel) comparable au C++. Correct donc. Que dire d'autre, sinon qu'Ada possède un compilateur libre du projet GNU : GNAT (la référence, existant en version "pro" avec IDE et services associés) et que ce langage gère "nativement" la programmation concurrente ?

J'espère pouvoir vous en donner quelques exemples bientôt...

mardi 19 février 2008

Et maintenant, quel langage ?

Les habitués de forums de programmation pour débutants (SDZ ?) devraient avoir souri en lisant ce titre... (En effet, ce type de forum voit apparaître avec une fréquence de 2 à 10 par semaine des sujet portant un titre approché de ça : "Quel language choisire svp URGENT ?" le plus souvent).

Blague à part, la question n'est pas idiote. Loin de là.
Quel langage apprendre ?

Des langages !
Beaucoup !

Il y a beaucoup de langages. De plus en plus même (note : je vais parler ici des "vrais langages" de programmation, c'est à dire, à mon sens, ceux qui sont Turing-complet ; pas du HTML, LaTeX, XML ou autres...).

Lesquels sont généralistes ? La plupart.
Lesquels sont spécialisés ou orientés vers une utilisation précise ? La plupart aussi !
Je m'explique : Fortran permet de tout faire (à condition d'être courageux) mais n'a que peu d'intérêt en dehors du domaine scientifique. Ruby est généraliste, mais est surtout employé pour des applications web (Rails...). Python permet de faire de "vrais" programmes mais sera surtout utilisé (dans le monde pro) pour du scripting d'appoint. On cherche encore Ada ailleurs que dans de l'embarqué et le Javascript ailleurs que dans des applis web côté client... Et pourtant, dans l'absolu, tous permettent de faire la même chose.

Les généralistes et les familles

Cela dit, il existe quelques langages qui sont utilisés (utilisables ?) pour à peu près tout : le C++ et le Java. Pas de chance pour eux (ou pour moi !), je ne les apprécie pas outre mesure. Sans être allergique au C++ que j'ai déjà utilisé en milieu professionnel, je trouve qu'ils sont assez proches et assez lourds (j'ai déjà le Fortran à la maison, merci !) : je reconnais sans problème leurs qualités respectives, mais ils ne conviennent pas, à mon sens, pour un usage domestique/éducatif/récréatif. De plus il ne recèlent pas ou peu de concepts nouveaux pour moi (même si ça ne me ferait pas de mal de revoir la gestion des pointeurs et références en C++ et deux, trois petites choses...).

Dans le même ordre d'idée, je pourrais me mettre au Python. Mais comme il est très proche de Ruby, à quoi bon ? Me taper les différences de syntaxe et de convention pour faire les mêmes choses qu'en Ruby mais en Python ? Pas assez rentable à mon goût ! Je pense, ou plutôt espère, que connaître un langage dans une "catégorie" facilite et accélère l'apprentissage des langages proches, en cas de nécessité. Par exemple pour Ruby : Python, Perl, Groovy, Smalltalk...

Coder, pourquoi ?
Coder plus pour gagner plus...

Car si je code, ce n'est pas que pour le plaisir.

C'est vrai qu'après des débuts difficiles, je me suis mis à apprécier de plus en plus la programmation, pour pas mal de raisons. D'abord pour l'aspect mathématique assez fort que j'y retrouve. Ensuite pour le côté "Lego" : il y a un aspect "architectural" dans la construction d'un programme, des contraintes mais aussi une grande liberté devant son éditeur de texte (un peu comme face aux briques), et une fois terminé on peut "jouer avec" son programme. Enfin, c'est un monde riche en "concepts" liés à l'image que l'on (l'homme et/ou la machine) se fait d'un problème et de sa résolution.

Mais la programmation, c'est aussi une partie importante de mon métier (ingénieur modélisation - bon, ok, pas en ce moment, mais je vais trouver ^^). Et dans ce contexte, à mon niveau, il n'est pas question de choix. On travaille avec le(s) langage(s) qu'on nous donne. Et c'est là que ça se gatte... Dans le domaine de la simulation et analyse numérique, sont surtout utilisés le Fortran et le C++, que je maîtrise "relativement" bien. Les informations glanées sur le web, au cours d'entretiens, etc... ont mis en lumière d'autres "technologies" possibles : Matlab, VisualBasic, C et Ada principalement.
  • Je pourrais me mettre au Matlab mais c'est pas gratuit, même s'il existe SciLab dans le genre...
  • L'environnement VisualBasic, malgré tout le mal que j'en pense, a été installé sur ma bécane... moins d'une heure. Déjà, les IDE m'insupportent, alors quand on ajoute un helper autiste et des tutos qui commencent par "Comment insérer un copyright dans votre programme" (véridique : cherchez sur le web !) et enchaîne sur "Créer un menu dans une fenêtre", ça fait beaucoup. Sans rire, ce genre de truc est extrêmement dangereux pour le PC d'un gars comme moi... Dix minutes de plus et je transperçais l'écran à coup de tête. Dangereux je vous dis !
  • C après C++, connaissant le Fortran ? Mouais...
  • Ada serait sans doute le plus intéressant, mais il y a peu de chance qu'il me serve en milieu professionnel, vu qu'il est le plus souvent dédié au systèmes embarqués (domaine intéressant, mais un peu loin de ma branche).

L'utilisation éventuelle d'un langage en entreprise m'aide donc peu.

Concept ?
Aqui lo paradigme !

Il reste les "concepts".
Cela fait déjà un bon moment que le monde de la programmation fonctionnelle me fascine : attraction/répulsion.
Attraction car c'est une grande famille de langages, de LISP à Haskell en passant par Scheme et OCaml avec des méthodes intéressantes.
Répulsion car jusqu'ici, j'ai toujours été incapable de "décrypter" le moindre bout de code fonctionnel aperçu ici ou là : crispant.
Il y a aussi d'autres "concepts" (paradigmes en l'occurrence ici) : logique (PROLOG), concurrent (Ada, encore !), par contrainte...

Finalement...
Tout ça pour ça...

Finalement, c'est par hasard que je me suis mis... au Scheme.
Un article, chez RubyInside, décrivait un interpréteur pour Scheme, codé en Ruby, dans le bus. J'ai voulu tester. Du coup, il m'a fallu taper un peu de Scheme ; du coup, j'ai lu du Scheme ; du coup je me suis mis à comprendre un peu le Scheme ; du coup, j'apprends le Scheme.
Pour être tout à fait franc, ce langage faisait déjà parti de ceux qui me tentaient fortement, avec le LISP, l'OCaml, Io et Cobol (non, pour le Cobol, j'd3conne !).
Io a perdu car je voulais voir autre chose que de l'OO. Quite à se lancer dans le fonctionnel, autant prendre un langage "simple" : l'OCaml me semblait "trop riche" car multi-paradigme. Enfin, le LISP a eu un petit désavantage : cette citation de G. Chaitin sur la "pureté" d'un langage.
Scheme donc, avec l'interpréteur MzScheme (Bus-Scheme, celui en Ruby étant... peu utilisable ?).

Effectivement, Scheme est austère. Mais il semble reconnu pour son côté pédagogique et est (hormis pour les parenthèses) assez bref dans sa syntaxe : il y a une certaine élégance proche des maths je trouve. Il est vieux, mais a un certain charme... et j'avoue que je l'apprends avec un certain plaisir. Et pour ma bonne conscience professionnelle, Scheme est utilisé dans certains codes de calculs industriel, en appoint (bientôt un article sur "Quel(s) langage(s) dans tel programme ?").Que demander de plus ?

Références et Docs :

D'abord, deux textes pleins de sagesse (si si, il y a un rapport avec le reste...) :
L'article sur Bus-Scheme, l'implémentation en Ruby :
Commençons gentiment en Scheme (avec un interpréteur qui marche !) :
Pour tout le reste vu dans cet article, Wikipédia saura répondre... sinon demandez toujours !



lundi 18 février 2008

Iterative, recursive ou tail-recursive ?

Théoriquement, la récursion terminale est une forme optimisée de la récursivité : comme on ne s'enfonce que d'un cran dans la pile, on est sensé avoir des performances similaires à une méthode itérative équivalente.

Cependant, comme le montre le petit benchmark suivant, sur le cas simple de la fonction factorielle, Ruby n'optimise pas la récursion terminale, et c'est bien dommage. A noter que le langage fonctionnel Scheme (dont on va reparler très prochainement) a pour spécification de toujours optimiser la récursion terminale. Ruby 1.9 améliore-t-il les performances sur ce point ?

Code :
(testé sous Windows XP ; Ruby 1.8.6)

# Benchmark on factorial function
#Recursive, tail-recursive
#and iterative versions

# Naive recursive version
def fact_rec_naive num
if num == 0
1
else
fact_rec_naive(num-1)*num
end
end

# Tail recursive version
def fact_rec_tail num
def iterer n, acc
if n <= 1
acc
else
iterer(n-1, n*acc)
end
end
iterer(num,1)
end

# Iterative version
def fact_iter num
res = 1
(1..num).each do |i|
res *= i
end
res
end

# Benchmark
require 'benchmark'

Benchmark.bm(15) do |timer|
timer.report('Naive recursive') {
for i in (0...1000)
fact_rec_naive i
end
}
timer.report('Tail recursive') {
for i in (0...1000)
fact_rec_tail i
end
}
timer.report('Iterative') {
for i in (0...1000)
fact_iter i
end
}
end

#=>
# user system total real
#Naive recursive 4.281000 0.062000 4.343000 ( 4.344000)
#Tail recursive 4.735000 0.063000 4.798000 ( 4.812000)
#Iterative 3.640000 0.015000 3.655000 ( 3.672000)





Références :

vendredi 15 février 2008

Itératif ou récursif ? Analytique.

Dans la lignée de l'article de hier, un benchmark du même type sur la suite de Fibonacci. L'intérêt est ici de montrer que :

  • Ruby est lent en récursif : l'appel de fonction est très coûteux en temps cpu (la version 1.9 devrait améliorer ce point, c'est du moins ce qui avait été annoncé).
  • Plus que pour sur le cas de la fonction factorielle, on constate que la version itérative est moins claire (et élégante) que la récursive (certes, c'est en partie de ma faute...).
  • Lorsqu'on a à disposition une solution analytique, on est gentil : on l'utilise ! (d'autant qu'ici elle utilise le nombre d'or... Pourquoi se priver d'esthétisme ésotérique à la Phidias ?)
Le code :
(testé sous Windows, Ruby 1.8.6)



# Benchmark on Fibonacci

include Math
Sqrt5 = Math.sqrt(5.0)

# Recursive version
def fibo_rec n
if n < 3
1
else
fibo_rec(n-1) + fibo_rec(n-2)
end
end

# Analytic version
def fibo_analy n
((1/Sqrt5)*(((1+Sqrt5)/2)**n-((1-Sqrt5)/2)**n)).to_i
end

# Iterative version
def fibo_iter n
if n < 3
1
else
res1 = 1
res = 2
(n-3).times do
tmp = res
res += res1
res1 = tmp
end
res
end
end

# Benchmark
require 'benchmark'

Benchmark.bm(9) do |timer|
timer.report('Iterative'){
100.times do fibo_iter(20) end
}
timer.report('Analytic') {
100.times do fibo_analy(20) end
}
timer.report('Recursive') {
100.times do fibo_rec(20) end
}
end

#=>
# user system total real
#Iterative 0.016000 0.000000 0.016000 ( 0.016000)
#Analytic 0.000000 0.000000 0.000000 ( 0.000000)
#Recursive 1.375000 0.000000 1.375000 ( 1.375000)

mercredi 13 février 2008

Itératif ou récursif ?

Dans la série des questions que je me pose parfois sur la programmation, il y a celle de l'opposition entre méthode itérative et méthode récursive... Dans le cas général, y en a-t-il une de préférable ? Seulement dans certains cas ? Pourquoi ? Laquelle est la plus rapide ? La plus claire ? Etc... Comme ça fait un moment que j'ai envie de découvrir tranquillement le paradigme fonctionnel, ça me parait être des interrogations justifiées.

Pour le cas de Ruby, je peux déjà répondre à la question de la vitesse d'exécution sur le cas trivial de la fonction factorielle grâce à ce petit benchmark :



# Benchmark : recursive vs iterative
# on factorial function

# Recursive version
def factor_rec num
if num == 0
1
else
factor_rec(num-1)*num
end
end

# Iterative version
def factor_iter num
res = 1
(1..num).each do |i|
res *= i
end
res
end

# Benchmark
require 'benchmark'

Benchmark.bm(9) do |timer|
timer.report('Recursive') {
for i in (0...1000)
factor_rec i
end
}
timer.report('Iterative') {
for i in (0...1000)
factor_iter i
end
}
end

#=>
# user system total real
#Recursive 4.266000 0.062000 4.328000 ( 4.328000)
#Iterative 3.312000 0.016000 3.328000 ( 3.360000)