Ceci est un post sur la recursion dans un post sur la recursion

On distingue deux formes de récursion : La recursion directe ou indirecte.

Dans la récursion directe (exemple en ruby)  la fonction s'appelle directement.

def facdir(n)
return 1 if n==1
return (n * facdir(n-1))
end


La fonction fac s'appelle en se transmettant le paremetre n-1

Dans la méthode indirecte , la fonction s'appelle aussi , mais elle va se transmettre son contexte
en plus de son parametre  normal.
Pour une fonction simple , le contexte sera limité à une variable destinée à accueillir le résultat.


Exemple :


def facind_r(n,prod)
return prod if n==1
return facind_r(n-1,n*prod)
end


La variable 'prod' est le 'contexte'.

L'appel de la fonction se fera par :

def facind(n)
    facind_r(n,1)
end



La méthode indirecte est meilleure que la méthode directe.
A l'appel d'une itération le système n'a pas besoin de mettre
dans la pile l'appel de la fonction CAR AUCUNE opération ne sera à réaliser à son retour.







En Haskell :


module Main where

 facdir :: Int -> Int 
 facdir 1 = 1
 facdir n = n * facdir(n-1)


 facind :: Int ->Int
 facind n = facind_r (n,1)

 facind_r :: (Int,Int)  -> Int 
 facind_r (1,prod) = prod
 facind_r (n,prod) = facind_r( n-1, n* prod )
 

En Erlang:

-module (fac2).
- export([facdir/1,facind/1]).

facdir(1) -> 1;
facdir(N) -> N * facdir(N-1).

facind(N) -> facind_r(N,1).
facind_r(1,Prod) -> Prod;
facind_r(N,Prod) -> facind_r(N-1,N*Prod).
 

#python , #ruby : c'est presque pareil

En relisant un tutorial python en francais , j'ai été frappé par la ressemblance entre Ruby et Python.


Exemple en Ruby

#!/usr/bin/ruby
def dupont 
 print "dupont\n"
end
def suite(v) 
 puts v 
end
def encore(param1,param2)
 puts param1,param2 

end
# appel de la fonction
dupont

En Python :

#!/usr/bin/python
def dupond() :
 print "dupond"
 
def suite(chaine) : 
  print chaine

def encore(param1,param2) : 
  print param1,param2 
  
# appel de la fonction
dupond()



L'obligation d'utiliser les parenthèses dans l'appel d'une methode ou fonction Python a des conséquences étonnantes.

En Python , comme en 'c' , il est possible d'assigner une variable à une fonction
ex   :  data= suite   # sans les parenthèses !

Et de demander data('exemple') pour appeler en coulisse la fonction suite avec le parametre 'exemple'.

La même chose en Ruby est plus compliquée à faire :

data= self.method(:suite)
data.call("coucou") 

Ces mécanismes ne doivent pas être confondus avec le currying qui est un  procédé qui permet de
transformer une fonction qui a plusieurs parametre en une fonction qui ne prend qu'un paramètre.

Exemple en Haskell :


module Main where
 prod x y = x * y
 double= prod 2
 triple = prod 3


Prelude> :load currying.hs
[1 of 1] Compiling Main             ( currying.hs, interpreted )
Ok, modules loaded: Main.
*Main> double(6)
12
*Main> triple(4)
12

La signature de la fonction prod reflète ce phénomène
*Main> :t prod
prod :: (Num a) => a -> a -> a

(prod 2)4
Un appel à prod  retourne une fonction lambda \y = 2 * y
Puis un deuxième appel finalise le calcul en remplacant y par 4 => 8

C'est un système extrêmement important en programmation fonctionnelle.

#Ruby , #Erlang , #Haskell et les autres

J'ai profité de mes vacances pour lire l'ouvrage suivant:



Seven Languages in Seven Weeks: A Pragmatic Guide to Learning Programming Languages. (Lien vers l'editeur ici).

Les langages présentés sont :

IO : (lien ici) io est un langage orienté objet inspiré par smaltalk. Son originalité réside dans l'utilisation comme dans javascript d'objets basés sur les prototypes plutôt que sur des classes.
Un objet io (ou javascript) est un simple tableau associatif. Une clé du tableau peut contenir une donnée , une fonction ou une référence vers une fonction d'un prototype. L'instanciation d'un objet se fait par clonage et non pas à partir d'un modèle (template) comme dans le cas des langages basés sur les classes.

Ruby (le top du top)

Prolog.

Scala : (lien ici ) scala est un langage développé par les ingénieurs de twitter basé sur la JVM. Il permet d'utiliser les librairies Java. L'intérêt de scala est de fournir une ouverture vers les langages fonctionnels avec en plus la possibilité de mettre en place des traitements parallèles (concurrents)

Erlang. (lien ici) c'est le langage qui à mon sens permet de débuter avec les langages fonctionnels.


Clojure. (lien ici ) Ce langage est une implémentation de Lisp destinée à utiliser une JVM. Il se présente comme une évolution possible de java.

Haskell. (lien ici) Haskell est le langage fonctionnel par excellence, qui est le fruit d'un travail collectif d'un groupe de chercheurs et non pas une construction d'une personne isolée. Un bon livre de référence est

La lecture de ce livre est difficile, aussi il est possible de lire cet ouvrage collectivement sur le forum suivant: (lien ici )
Une version gratuite et commentée du livre est disponible ici.




Pour chacun de ces langages, l'auteur propose des points à approfondir sur une semaine. Et il interroge les concepteurs de ces langages sur leurs motivations et les perspectives d'évolutions. C'est un très bon livre.

Pour ceux qui sont passionnés de langage et qui veulent se lancer dans l'écriture d'un nouveau langage : le livre à avoir est :(lien ici)
Create Your Own Programming Language de Marc-André Cournoyer

A system to achieve every programmer’s dream.
Learn how to create a simple programming language in a few days with this easy step-by-step guide.

#nosql , decisionnel et #forumdecideo

Je suis intervenu au forum decideo lien ici , cet évenement a été d'une très grande qualité et très bien organisé (philippe Nieuwbourg) . Un intervenant avant moi : renaud FINAZ de Micropole Univers a fait une intervention brillante sur l'état de l'art dans le domaine du stockage des données au sens large du terme.

Je partage son analyse dans les grandes lignes:

Le volume de stockage n'est plus un problème : le Tera est accessible à tous pour moins de 100 euros.

Le volume d'information produit pour Internet en deux ans (2009/2009) est plus important que tout le volume d'information existant (X 5)


(source http://gigaom.com/2010/03/16/northscale/)

Toute cette information est en grande partie déstructurée.

Ainsi, ce n'est plus la donnée qui fait la richesse d'une entreprise c'est sa faculté de traiter cette donnée.

Le problème des performances.

Il y a deux point de contention possibles: alimentation et l'indexation (structuration) pour la restitution.

L'alimentation.
L'alimentation d'une base de données /entrepôt à partir des différentes sources de données.
Comment intégrer, contrôler , agréger des millions de lignes de données. Actuellement ces fonctions sont traités par des programmes en mode itératifs ligne par ligne ou en mode ensembliste par des opérations portant sur un ensemble de données.

Il es possible de paralléliser les traitements à conditions mais il faut le prévoir au préalablement. Ce parallélisme est rudimentaire : j'ai N sources de données je vais les traiter par N programmes lancés en même temps. Cette méthode est naïve car elle ne fait que déplacer le problème sur le moteur de la base qui lui traite les opérations en mode file d'attente (voir page sur ACID)

Il faut donc utiliser un système d'alimentation basé sur des traitements fortement 'concurrents' qui traitent avec des bases de données qui respectent le modèle ACID mais tout en étant capable de s'affranchir du modèle file d'attente (voir le théorème de CAP) de Brewer






Concernant les langages à utiliser.
Il n'y a pas de secret , regardons ce qui se fait chez les entreprise full web 2.0 (Facebook, twitter , amazon et google).

Les langages fonctionnels: Haskell mais surtout Erlang qui nativement est capable de travailler sur plusieurs nœuds de machine et de gérer la perte de serveur.
Scala le langage fonctionnel de twitter basé sur une JVM

Les langages hybrides: Ruby et Python

Tous ces langages possèdent des fonctions puissantes de MAP/REDUCE


L'indexation et la structuration des données.

Le calcul des agrégats ou la création des index est réalisable au moment du chargement des données ou a posteriori . Pour les agrégats et les index , il sera possible de paralléliser massivement les opérations de Map /Reduce.

Les bases à utiliser.



Tout sera fonction du type d'information à stocker .

• Pour des restitutions de documents!: CouchDB ou mongoDB (plutot hierarchique)
• Pour des cubes: prendre des bases orientées colonnes : cassandra, htable..

Plaquettes (cheatsheet) #haskell , #uml #jquery et #ruby

J'adore les plaquettes plastifiées présentant toutes les options possibles, on peut s'en servir comme aide-mémoire, soutasse. Autant de connaissance dans un si petit volume, c'est magique.
Un site ici http://www.cheat-sheets.org/ qui centralise ces aide-memoires.

• Haskell :ici une plaquette du langage haskell :Haskell cheatsheet
• Erlang: http://weblogs.asp.net/nleghari/archive/2007/12/29/erlang-cheat-sheet.aspx
  
• UML : UML sur une page :http://www.loufranco.com/blog/files/UMLCheatsheet.html
• Jquery: La fameuse librairie javascript http://labs.impulsestudios.ca/jquery-cheat-sheet
• HTML5: http://woork.blogspot.com/2009/09/html-5-visual-cheat-sheet-by-woork.html
• Les filtres tcpdump et wireshark: http://packetlife.net/blog/2008/oct/18/cheat-sheets-tcpdump-and-wireshark/
• Ruby rails etc voir sur le site.

Mixer #haskell #Erlang #Java dans #Ruby

Il est possible de s'amuser à faire interagir un programme Ruby avec d'autres langages.

Avec Haskell.
Le projet Hubris se veut un pont entre ruby et Haskell. Il s'utilise en mode inline ou sous forme d'appel de module.

require 'hubris' # best line ever

class Target
 hubris :inline =>"triple::Int->Int; triple n = 3*n"
end

t = Target.new
puts t.triple(10)
  => 30

Un article sur http://www.engineyard.com/blog/2010/a-hint-of-hubris/ détaille son utilisation.

Avec Erlang.
Le projet erlectricity permet de communiquer avec un process Erlang.
Le projet présente un exemple d'un simple programme de type 'echo'

require 'rubygems'
require 'erlectricity'

receive do |f|
 f.when([:echo, String]) do |text|
   f.send!([:result, "You said: #{text}"])
   f.receive_loop
 end


end

Avec du C.
(tiré de rmag numero 5)
Il faut se munir des fichiers sources Ruby . Et construire un répertoire sous la forme:

rmag/  
rmag.c # source code  extconf.rb # ruby file to create makefile
example.rb # a simple script to show our ext
LICENSE # license
README # some info

Le rmag.c devra commencer par la ligne magique:

#include “ruby.h”

Le fichier responsable de la création du makefile contiendra:

require 'mkmf'
ext_name = 'Rmag'
create_makefile(ext_name)

Avec Java.

Il faut utiliser la machine virtuelle Jruby et inclure le module

# This is the 'magical Java require line'.
require 'java'

A partir de là il est possible d'écrire des lignes en java.

frame = javax.swing.JFrame.new("Window") # Creating a Java JFrame
label = javax.swing.JLabel.new("Hello")



exemples à prendre sur le wiki de jruby.


Go: Un nouveau langage par Google

Google communique sur son nouveau langage maison : GO.
Avant même le lancement du projet, le sujet a déclenché une polémique sur web en raison de son appellation déjà utilisée par une autre équipe:
Voir le fil de discussion ici:



Go est un langage compilé comme le C ou le C++. Il est aussi orienté traitement concurrent (dans le sens de parallélisation des traitements) comme Erlang. Ainsi les processus dialoguent entre eux par des 'Channels' ex:

chan1 <- "exemple"

Ici la chaine "exemple" est envoyée à un autre processus branché en entrée du canal "chan1"

On utilise le mot réservé 'go' pour lancer un processus , avec souvent comme paramètre le canal à brancher en entrée et en sortie :
ex:

go ma_fonction(ch_in, ch_out,un_paramètre)

Ici ma_fonction pourra lire des données à partir de ch_in et écrire des données en sortie sur ch_out

 i := <-ch_in;  // Receive value of new variable 'i' from 'ch_in'.   ch_out <- i  // Send 'i' 

Les nostalgiques du Pascal retrouveront le signe ':=' qui ici permet la déclaration et le chargement d'une variable: c'est l'initialisation.

Le blog du langage go (golang) propose une illustration des processus concurrents basée sur la recherche des nombres premiers par le Crible d'Ératosthène


C'est un excellent exercice à faire en Erlgan, sur lequel je vais passer plusieurs soirées.




Le langage est fortement typé, avec des types basiques permettant de construire des structures.
Il est possible de manipuler des types originaux comme les 'channel' (type chan) et les slices : tranches de tableau. A noter qu'il n'existe que les boucles 'for' , pas de 'while' ou de 'do'.

Je suis un peu déçu de l'ensemble. Maintenant que je connais mieux les langages fonctionnels, je persiste à croire qu'il faut éviter de partager des ressources si on désire vraiment paralléliser les processus. Pour cela comme dans les langages fonctionnel il ne faut pas d'effet de bord.
Le caractère immuable des variable en Haskell ou en Erlang est très déconcertant mais c'est solution la plus simple.

Pour terminer, je suis très étonné de google sorte un nouveau langage alors que le gourou du Python est son employé. Et que dire de cette remarque relevée sur le site de Google: depuis 10 ans aucun langage ne s'est distingué.. Merci Guido.“No major systems language has emerged in over a decade, but over that time the computing landscape has changed tremendously. "

Les deux pilliers du succés de Google: map et reduce

Je suis tombé sur une série d'article concernant Google. Comment google réalise l'analyse du contenu du web ?.

Il y a deux possibilités :
Avoir un gros programme qui traite toutes les données ou plusieurs petits programmes qui traitent en même temps les informations.
c'est cette dernière solution qu'utilise google et qui a fait son succès.

On utilise pour cela des principes simples :
- Les données à analyser sont copiées sur des baies de fichier partagées .
- Des milliers de petits programmes s'exécutent en parallèle sur chaque noeud (fonction 'map')
- Les résultats sont agrégés par une fonction de réduction 'reduce'

Exemple : compter des mots dans un texte

Fonction map
(noeud 1)
mot <=> cardinalité
linux 12
processeur 2
web 10
...............
(noeud 2)
mot <=> cardinalité
linux 8
processeur 0
web 3
...............
Par application de la fonction 'reduce' on obtient :
mot <=> cardinalité
linux 20 (12+8)
processeur 2 (2+0)
web 13 (10+3)
...............

L'ensemble du processus est piloté par un programme de surveillance qui relance les programmes défectueux.

Pour du traitement massif d'information, les programmes ne doivent pas hésiter à 'sauter' les lignes erronées.
Ce document ici http://labs.google.com/papers/mapreduce.html expose le processus utilisé par google

Les fonctions map et reduce peu presentes dans des langages impératifs (sauf Ruby ou Python) sont la base des langages fonctionnels.
La fonction reduce possède des synonymes comme 'fold' , 'inject' ou encore 'accumulate'.

Un programmeur élévé aux langages impératifs choisira naturellement de faire un gros programme qui réalisera les traitement en une seule passe. Par contre un pseudo développeur (comme moi) aura tendance à appliquer intutivement les principes de la programmation fonctionnelle. C'est pour cela que j'ai investi dans des livres sur le langage fonctionnel Haskell.