hypermove - vers l'avant et au-delà

All original work is licensed by Amirouche Boubekki under cc-by-nc-sa

Table of content

Recommendations basées sur les graphes

Prélude

Comme vous le savez peut-être déjà je suis un fan des graphes. L'idée qui ma charmé initialement est qu'il s'agit d'une base de donnée sans schema à la mongodb avec un support des transaction sur plusieurs modifications.

Le fonctionnement de ajgu reflette cette intêret dans le sens où ils y a un support complet des transactions tel qu'on peux le trouver dans des bases de données classiques comme postgresql and mysql.

Chemin faisant, j'ai découvert concepnet et je me suis rendu compte que c'était pas très rapide de charger la base de donnée. J'ai fait quelques tests avec wiredtiger je me suis rendu compte que c'était possible de passer de plusieurs heures de chargements à quelque minutes en utilisant le schema adéquat.

Entre temps, j'ai fait des experiences toujours avec wiredtiger. Inpiré par Guile et datomic j'ai crée un schema que j'appelle le TupleSpace. Assez fascinant. Et je me suis rendu compte que c'était non seulement completement posssible d'utiliser ce schema pour modeliser une base de donnée en forme de graphe mais que les performances ne devait pas être mauvaise dans un certains nombre de contexte.

AjguDB

Dans les grandes lignes voilà le fonctionnement de la nouvelle iteration d'ajgu nommé AjguDB qui n'offrent pour le moment qu'un backend LevelDB.

Definition du TupleSpace:

- Une table où chaque ligne est un tuple: identifiant, nom, valeur

- Une autre table où les tuples sont indexés de cette façon: nom, valeur, identifiant

Definition du schema de la graphdb au dessus du TupleSpace:

- Élément Edge

- Élément Vertex

Et enfin ajout du language de requete Gremlin qui est le grand absent de ajgu. Je me demande comment faisaient les gens avant.

Recommendation de film

Une des choses que l'on peux faire avec une graphdb c'est de la recommendation. Ce n'est pas la méthode la plus populaire. Mais elle peut-être plus puissante que la méthode classique de recommendation item-item car elle permet de prendre en compte l'existence de connection indirecte entre les items, ça demande quand même du travail. Donc nous n'etudirons pas cette méthode pour le moment.

Préparation

En attendant de nous allons nous contenter de recommendation classique item-item, c'est à dire «si machin à aimer ce film, tu devrais aimer ce film».

La première chose à faire est d'installer AjguDB:

pip install ajgudb

Ensuite télécharger le dataset movielens small:

wget http://files.grouplens.org/datasets/movielens/ml-latest-small.zip

Une fois decompressé, il faut charger le dataset dans ajgudb à l'aide du script suivant:

movielens-load.py:

from csv import reader

from ajgudb import AjguDB


if __name__ == '__main__':
    graph = AjguDB('db')

    # create indices
    print('Starting load of `movies.csv` in `db/`')
    with open('./movies.csv', 'r') as f:
        next(reader(f))  # skip heading
        for id, title, genres in reader(f):
            props = dict()
            props['label'] = 'movie'
            props['id'] = id
            props['title'] = title
            movie = graph.vertex(**props)
            for genre in genres.split('|'):
                genre = graph.get_or_create(
                    label='genre',
                    name=genre
                )
                movie.link(genre, label='partof')

    print('Starting load of `ratings.csv` in `db/`')
    with open('./ratings.csv', 'r') as f:
        next(reader(f))  # skip heading
        for userid, movieid, value, timestamp in reader(f):
            # get or create user
            user = graph.get_or_create(label='user', id=userid)
            # create edge between movie and user
            movie = graph.select(label='movie', id=movieid).one()
            props = dict()
            props['value'] = int(float(value))
            props['timestamp'] = int(float(timestamp))
            rating = user.link(movie, label='rating', **props)

    print('Starting load of `tags.csv` in `db/`')
    with open('./tags.csv', 'r') as f:
        next(reader(f))  # skip heading
        for userid, movieid, value, timestamp in reader(f):
            movie = graph.select(label='movie', id=movieid).one()
            user = graph.select(label='user', id=userid).one()
            props = dict()
            props['value'] = value
            props['timestamp'] = float(timestamp)
            tag = user.link(movie, label='tag', **props)

    print('closing')
    graph.close()

Recommendation

Cette partie est inspiré de «A graph based movie recommender engine»

Ouvrer une console ipython and ouvrez la base:

from ajgudb import AjguDB; from ajgudb.gremlin import *; db = AjguDB('db')

Maintenant nous pouvons laisser s'exprimer toutes la puissance des gremlins.

Récupérons le film Toy Story par exemple:

movie = db.get(1)

Pas trop difficille quand on connais déjà l'identifiant. Mais sinon on peut faire:

movie = db.one(title='Toy Story (1995)')

Ça c'est fait. A l'occasion on pourra changer de film.

Pour connaitre la moyenne des notes superieurs à 3 on fait:

query = db.query(
      incomings,
      select(label='rating'),
      key('value'),
      filter(lambda g, x: x.value > 3),
      value,
      mean
)
query(movie)

Ce qui s'est passé:

- À partir du film, on a remonté vers les arêtes entrantes à l'aide de incomings

- Puis on a séléctionné les arêtes des notes à l'aide de select(label='rating')

- Ensuite on demande la valeur de la clef de chaque arete avec key('value') pour avoir la note attribué

- Suite à ça, on filtre les notes

- Enfin on demande la valeur contenu dans l'iterateur et on fait la moyenne

Pas compliqué. Le langage est dynamique vous ne pouvez pas composer n'importe quel étape avec n'importe quel autre. Par exemple une fois que vous avez réupérer la valeur contenu dans l'iterateur avec value vous ne pouvez plus remontez dans les resultats avec l'étape back que je prensente dans la suite.

Une fois qu'on a filtrer les valeurs des notes on peux revenir sur les arêtes qui ont les notes que l'on veux considerer à l'aide de back. Cette étape retourne avec la selection actuel à l'étape précédente de selection, dans ce cas le select(label='rating'). Ce qui veux dire que dans l'iterateur on va trouver à la place des notes superieur à 3, toutes les arêtes qui ont une note superieur à 3. Pour verifier on peux faire:

query = db.query(
      incomings,
      select(label='rating'),
      key('value'),
      filter(lambda g, x: x.value > 3),
      back,
      get
)
query(movie)

L'étape get récupère les elements (noeuds ou arêtes) référencés dans l'iterateur et consome l'iterateur. Ce qui veux dire que plus aucune étape n'est possible après get.

Les arêtes de notes vont de l'utilisateur qui a donné la note vers le film noté. Pour récupéré les utilisateurs qui ont données les notes qui ont été selectionné, on ajoute l'étape start à la requete:

query = db.query(
      incomings,
      select(label='rating'),
      key('value'),
      filter(lambda g, x: x.value > 3),
      back,
      start,
      get
)
query(movie)

On va stocké la query précédentes dans liked_by comme ça, le code sera plus lisible.

liked_by = db.query(
         incomings,
         select(label='rating'),
         key('value'),
         filter(lambda g, x: x.value > 3),
         back,
         start
)

Remarquez qu'on a retirez le get à la fin.

Maintenant on veux connaitre les films que ces utilisateurs ont bien notés. Ce qui va donner une idée des films à recommender à quelqu'un qui a bien aimé toy story:

likes = db.query(
      outgoings,
      select(label='rating'),
      key('value'),
      filter(lambda g, x: x.value > 3),
      back,
      end
)

Si vous lisez bien likes fait le parcours inverse de liked_by.

Autre chose, la requetes précédentes va forcement retourner les même films plusieurs fois. On peux afffiner le resultat on passant par une étape de comptage group_count qui utilise un simple Counter.

Voici l'implementation de counter:

def group_count(graphdb, iterator):
    yield Counter(iterator)

Le counter va grouper tous les resultats dans un même élément dans l'iterateur. Pour completer cette étape final nous allons d'abord récupérer les résultats dans l'ordre des plus courant, derouler la liste, en enfin récupérer le titre des films:

sort = db.query(
    group_count,
    each(lambda g, x: x.most_common()),
    scatter,
    each(lambda g, x: x.value[0]),
    key('title'),
    limit(10),
    value
)

Sans grande surprise on retrouve Toy Story comme premier film à recommender aux gens qui ont aimé Toy Story :)

Le programme complet:

program.py:

from ajgudb import AjguDB
from ajgudb.gremlin import *  # noqa

db = AjguDB('db')

liked_by = db.query(
    incomings,
    select(label='rating'),
    key('value'),
    filter(lambda g, x: x.value > 3),
    back,
    start
)

likes = db.query(
    outgoings,
    select(label='rating'),
    key('value'),
    filter(lambda g, x: x.value > 3),
    back,
    end
)

sort = db.query(
    group_count,
    each(lambda g, x: x.most_common()),
    scatter,
    each(lambda g, x: x.value[0]),
    key('title'),
    limit(10),
    value,
)


movie = db.one(title='Toy Story (1995)')

for item in sort(likes(liked_by(movie))):
    print item

sfx: Template Language for Scheme Guile

Héllo,

I've been lurking around GNU Skribillo and GNU Artanis. I don't really like the rails-like syntax of Artanis, used in the template language. Agreed, it has its use-cases. I wanted to hack on something "small", so I've put together sfx.

The code of skribe reader is included in sfx.scm. So the only dependency is guile (2.0.11) and guile-reader that you can install using guix package -i guile-reader

This bare template language has the following features:

- wanna be simpler scheme xml (sxml) syntax

- templates with custom environment

- external libraries loading inside the template

- extending a template with another

Wanna be simpler sxml syntax

Skribe reader (implemented by guile-reader) provide a handy syntax to both define keywords and quasiquote. In an sxml context those features are used to implemented attributes and text nodes.

attributes

Attributes in sxml are defined as follow:

(div (@ (id "shell")) "This the main area")

Instead of requiring the nesting of (attribute-name attribute-value) sfx use the char short syntax :keyword to write keywords and use that to visually cue to read attribute names and attribute values. The above snippet becomes:

(div (@ :id "shell") "This the main area")

I'm not sure it's worth the trouble of diverting from sxml standard. That said, it looks more like plain xml.

text nodes

Text nodes can be defined as

(p [héllo hacker])

This is looks the same as the default reader. It becomes handy when you include an inline element inside the text node:

(p [héllo ,(b [hacker])

,() is a special syntax of skribe reader which provides (unquote) inside [brackey quasiquote].

With the default guile reader, this must be written as:

(p "héllo " (b "hacker"))

This is looks verbose and prone to error. One must not forget the space in the string before the (b) element.

templates with custom environment

You can pass custom variables to the template but those must be parameters. In the example sfx.scm (which includes example use of the procedures) the environment in which the template is evaled is defined more or less as follow:

(define value (make-parameter 42))
(define amirouche (make-person "amirouche" 30))
(define env (let ((value value)
(amirouche amirouche))
(the-environment)))

Then value can be echo'ed inside the template using the unquote syntax ,(), like in the following code:

(p [Here is a lucky number for you «,(value)»])

external libraries loading inside the template

As you can see the previous snippet, there is also a record inside the environment. One can (maybe) provide in the environment the required procedures to echo the correct fields but this is verbose. Instead sfx use (use-modules) form inside the template definition file.

The file looks like the following:

(use-modules (person))

`(html
(body
(p [My name is ,(person-name amirouche)])))

I could not make procedure definition work inside the template, this my be linked to the way I eval the template. It's shame because for quick and dirty hacks it can be handy like defining mini-templates inside the big template.

This is my second try at this and having a look at the code of haunt is helpful.

extending a template with another

I though that the implementation `extend` would be more involving.

extend is the dual of include. Given a base template base.sfx you define placeholders say (main) and ,(sidebar) and the rest is the "shell" of the application ie. the part of GUI that is always the same over the application.

If index.sfx inherit base.sfx the context in which base.sfx is rendered is the same as the context used to render ìndex.sfx plus the variables defined/passed in ìndex.sfx to base.sfx.

In the following example, title and intro are evaled and then added to (current-module) environment with which base.sfx is rendered.

(extend "base.sfx")
(current-module)

`((title `(h1 [Héllo again hacker!!]))
  (intro "This is a little presentation of sfx template language"))

I don't how to make `(current-module)` disappear but it's also more explicit. I'm not sure.

`extend` implement a pattern similar to inheritance in OOP.

I attach complete code with an example. There is small doc in the header of the file.

I improved the usuability of the module. It should be able to just drop `sfx.scm` in your project to use it.

Here an exemple use in scheme code:

;;
;; This requires at least a `index.sfx` file and `person.scm` where
;; a `<person>` record is defined.
;;

(use-modules (person))

(define persons (list (make-person "amirouche" 30)
                      (make-person "julien" 30)
                      (make-person "mez" 27)
                      (make-person "moh" 113)))

(define bindings `((value ,(make-parameter 42))
                   (title '(h1 "Héllo (again (and again)) hacker!"))
                   (persons ,persons)))

(with-output-to-file "index.html"
  (lambda () (render "index.sfx" bindings)))

There still one area where it can be improved regarding template resolution/finding. Right now it simply look for templates according the default `(open)` behavior which looks in cwd (current working directory).

I posted last version on Guile maillinglist.

Guile log parser combinators

Prelude

I've built a little markdown parser using guile-log. It's little in the sens it doesn't support all markdown specification. That said it can be useful.

In this article we will do see step by step how the parser combinators works, at least what I understand, in the little markdown parser.

Getting started

First thing first you must install all guile-log and guile-syntax-parse. Clone the following repositories and install the software:

git clone https://gitlab.com/guile-syntax-parse/guile-syntax-parse.git
git clone https://gitlab.com/gule-log/guile-log.git

Now create a env.sh script that will chain the correct environment for both of those softwares:

#!/bin/sh
./guile-syntax-parse/env ./guile-log/env "$@"

We will now check that everything works, run the following command:

./env guile

And at the guile REPL type the following:

(use-modules (logic guile-log parser))

If it fails something is wrong, go to irc.freenode.net#guile channel and ask for help.

If you want to read the code of little markdown you can download it with its test file.

Otherwise follow along for a step by step guide into the world of parser combinators and its implementation in guile-log.

Parser combinators

As the name suggest parser combinators are parser procedures that you can combine to build a new parsers. In pseudo-code it can be expressed as follow:

(define text-node
   (sequence (open-tag "text") text (close-tag "text")))

The above defines the text-node as a parser, which is a sequence of:

  1. an open-tag that will look for an open tag named text
  2. a text parser
  3. an close-tag that will look for an close tag named text

You might have guessed that the grammer of the parser is the code of the parser. This is a very powerful feature of parser combinators.

Parser combinator is a way to express a grammar. Depending on the engine it can support different kind of grammars (recursive, ambigious, ...).

A naive implementation of text-node could be written using guile-log as follow:

(use-modules (logic guile-log parser))

(define text-node
  (mk-token (f-seq (f-tag "<text>")
                   (f+ (f-not! (f-tag "</text>")))
                   (f-tag "</text>"))))

This is naive because it's not a correct xml parser, but it does the job of parsing some kind of xml nodes. Test it using the following code:

(parse "<text>Héllo Hacker!</text>" text-node)

This should return Héllo Hacker!. Now you have the basic idea in mind of how parser combinators makes writing parser easy. We will enter the specifics of guile-log API in the following section using the code of the little markdown parser.

Diving into (logic guile-log parser)

That's where lives parser combinators in guile-log. The documentation can be found at guile-log's website.

Make sure to import the module before trying the following code snippet

(use-modules (logic guile-log parser))

One the the most basic parser can be built with f-tag procedure. We used it earlier to parser start tag and end tags. In the context of markdown, it can be used to parse bold start tag the double stars in **my dreams**. Try that:

    (parse "**" (f-tag "**"))

This should return something. It's a low level datastructure used by guile-log. But the following returns false:

    (parse "//" (f-tag "**"))

** is not a token, but a delimiter for a token. It puts the parser in a mode as we will see later. Since it would be a bad example to turn into a token, we will use f-tag to parse something else and turn the result to a token:

    (parse "Héllo hacker!" (mk-token (f-tag! "Héllo hacker!")))

In the above snippet, two things changed, from left to right:

  1. we use mk-token to turn the result (if any) of the parser passed as argument to a string
  2. we use f-tag! with a ! to mark the content of the parser as a match. This the first use of ! in procedure names, marking result as "tokenizable"

We can write the parser as a sequence of two parser using f-seq:

    (parse "Héllo hacker!" (mk-token (f-seq (f-tag! "Héllo ")
                                            (f-tag! "hacker!"))))

f-seq will execute every parser that it receive as argument one after the other consuming input. Whereas f-and apply parser passed as argument without consuming the input. We won't use f-and right now, as it must be used with higher level parsers.

The actual code to parse a bold statment in the little markdown parser is the following:

(define f-bold
  (f-list #:bold (f-seq (f-tag "**")
                        (mk-token (f+ (f-not! (f-tag "**"))))
                        (f-tag "**"))))

This introduce a few procedures:

  1. f-list is used to build the ast this will create a list with the output of the parser prepended with #:bold
  2. f+ will repeat the parser passed as argument at least one time
  3. f-not! will match if the parser passed as argument doesn't match and mark the result as a token

Try:

(parse "**Héllo Hacker!**" f-bold)

Well, what remains is the composition of the above and the documentation. The most difficult construct in the little parser is text-token a product of stis. If you need help don't hesitate to ask on irc.freenode.net#guile I am amz3.

Guile dynamic Foreign Function Interface

Prelude

Ou «dynamic FFI». La documentation officiel se trouve dans la partie «Foreign Function Interface». Je dis ça parce que la documentation plus général sur le FFI en Guile est utile dans le cadre du FFI dynamique.

J'ai déjà fait des des bindings pour wiredtiger en Guile à l'aide de l'approche orienté C, qui m'a semblé plus simple à coder. Je m'interesse à la méthode dynamique, orienté Guile, c'est à dire la méthode où il n'est pas necessaire d'écrire de C.

NalaGinrut à travers un article introduisant le FFI dynamique et ijp à travers des bindings pour GDBM m'offrent des pistes pour avancer par contre il reste un problème qui n'est pas documenté ou vaguement dans la documentation à savoir le bindings de pointeur de fonction!

Binding Function Pointer

Un pointeur de fonction est une construction de haut niveau en C, qui consiste à passer une fonction en argument d'une autre fonction. C'est une pattern qui apporte une forme de dynamisme au programme. Par exemple utilisé dans certaines approches Orienté Objet pour associer les objets à leurs fonctions de traitement. Dans le cas de wiredtiger, c'est utilisé partout !

Function Pointers

Voici un exemple de code C qui reproduit grosso-modo l'utilisation faites par wiredtiger des pointeurs de fonction:

function-pointer.c:

#include <stdio.h>
#include <stdlib.h>

// fonction utilisé pour tester que le binding est
// actif aka. «ÇA MARCHE! Le reste devrait marcher...»
int debug(int a, int b) {
  return 1000 + a + b;
}


// definition en avance du type pour pouvoir
// l'utiliser dans la fonction presente dans
// la structure
typedef struct MyObject_ * MyObject;

struct MyObject_ {
  int (*print)(MyObject);
  void * value;
};


int my_object_print_integer(MyObject object) {
  printf("%i\n", (* (int *) object->value));

  return 113;
}

/* Constructeur pour les objects the type `MyObject` de
   type entier */
int my_object_integer(MyObject * object, int value) {
  // Create object
  object = malloc(sizeof(MyObject));

  if (object == NULL) {
    return -1;
  }

  object->value = value;

  // Set print method
  object->print = &my_object_print_integer;

  printf("object: %p\n", object);
  printf("object->print: %p\n", (object)->print);
  printf("object->value: %p\n", (object)->value);

  (object)->print(object);
  
  // Everything is ok!
  return 0;
}

Ensuite on compile ça avec les commandes:

compile.sh:

gcc -c -fPIC function-pointer.c -o function-pointer.o
gcc -shared -o function-pointer.so  function-pointer.o

Qui va créer une bibliothèque partagé.

Maintenant on a tout ce qu'il faut pour s'amuser en Guile :)

Foreign Function Interface bindings

function-pointer-api-lower.scm:

(define-module (function-pointer))

(use-modules (rnrs bytevectors))
(use-modules (srfi srfi-9))
(use-modules (srfi srfi-9 gnu))

(use-modules (ice-9 format))
(use-modules (system foreign))


;;;
;;; helper macro to quickly define immutable records
;;;
;;
;; FIXME: Taken from Guile (maybe should be in (srfi srfi-99))
;;        adapted to make it possible to declare record type like `<abc>' and keep
;;        field accessor bracket free. record name *must* have brackets or everything
;;        is broken
;;
;; Usage:
;;
;;   (define-record-type <abc> field-one field-two)
;;   (define zzz (make-abc 1 2))
;;   (abc-field-one zzz) ;; => 1
;;
;; FIXME: maybe this is less useful than the immutable record of (srfi srfi-9 gnu)
;;        I still use `set-field` and `set-fields`
(define-syntax define-record-type*
  (lambda (x)
    (define (%id-name name) (string->symbol (string-drop (string-drop-right (symbol->string name) 1) 1)))
    (define (id-name ctx name)
      (datum->syntax ctx (%id-name (syntax->datum name))))
    (define (id-append ctx . syms)
      (datum->syntax ctx (apply symbol-append (map syntax->datum syms))))
    (syntax-case x ()
      ((_ rname field ...)
       (and (identifier? #'rname) (and-map identifier? #'(field ...)))
       (with-syntax ((cons (id-append #'rname #'make- (id-name #'rname #'rname)))
                     (pred (id-append #'rname (id-name #'rname #'rname) #'?))
                     ((getter ...) (map (lambda (f)
                                          (id-append f (id-name #'rname #'rname) #'- f))
                                        #'(field ...))))
         #'(define-record-type rname
             (cons field ...)
             pred
             (field getter)
             ...))))))

;;;
;;; ffi helpers
;;;

(define *NULL* %null-pointer)
(define *pointer* '*)

;; This is small syntax change 
(define* ((dynamic-link* shared-object) func-name)
  (dynamic-func func-name shared-object))

;;; foreing macro

(define-syntax-rule (foreign
                     ;; function pointer and signature
                     (ret function-pointer args ...)
                     ;; foreign-function lambda wrapper
                     wrapper)
  (let ((foreign-function (pointer->procedure ret
                                              function-pointer
                                              (list args ...))))
    (lambda (. rest)
        (apply wrapper (append rest (list foreign-function))))))

;;;
;;; Example use:
;;;

;; header file for the library we want to build bindings
;;
;;
;; typedef struct MyObject_ * MyObject;
;;
;; struct MyObject_ {
;;   int (*print)(MyObject);
;;   void * value;
;; };
;;
;; // specific constructor for int type
;; int my_object_print_integer(MyObject object);
;;
;;

(define function-pointer (dynamic-link "./function-pointer.so"))
(define function-pointer* (dynamic-link* function-pointer))

;;; bind `debug` function
;;
;; This is example zero, a very simple binding
;;
;; XXX: here we introduce foreign macro that will allow to define
;;      the final `debug` procedure via a lambda that will wrap
;;      the call to the procedure actually bound by guile ie. `debug` c function
(define debug (foreign
               ;; signature: this declare the /signature/ and get the guile wrapped `debug` c function
               ;; via `function-pointer*` cf. [0]
               (int (function-pointer* "debug") int int)
               ;; wrapper: this is the user defined wrapper that will shake user provided arguments
               ;; and return value of the guile wrapped procedure
               ;; XXX: this the lambda that eventually called by the user
               (lambda (a b foreign-function)
                 ;; `foreign-function` is the guile wrapped c function `debug`
                 ;;
                 ;; XXX: There is no process of the return value
                 (foreign-function a b))))
;;;
;;; bind a constructor function
;;;

;; declare a record for foreign struct `MyObject`
;; XXX: `value` and `structure` are repeated in scheme data structure
;;      for easier debugging this should not be done in production code
(define-record-type* <my-object> structure value pointer)

;; also define a record to hold structure pointers
(define-record-type* <my-object-structure> print value)

;; also define a star procedure to build `<my-object>` the double pointer array
(define (make-my-object* array value)
  (let* ((pointer (make-pointer (array-ref array 0)))
         (structure (pointer->bytevector pointer 2 0 'u64)))
    (make-my-object (apply make-my-object-structure (map make-pointer structure))
                    value
                    (make-pointer (array-ref array 0)))))


;;
;; A slighty more complex example
;;
(define make-integer-my-object  ;; wrapped bound function
  (foreign
   ;; signature of the bound function
   (int (function-pointer* "my_object_integer") *pointer* int)
   ;; wrapper for the guile bound function
   (lambda (value foreign-function)
     ;; foreign-function is a MyObject constructor function aka. `my_object_integer`
     (let* (;; MyObject c function constructor expects a double pointer
            (*my-object #u64(0))
            (*my-object-pointer (bytevector->pointer *my-object))
            ;; construct the object with the guile bound function
            (code (foreign-function *my-object-pointer value)))

       ;; XXX: deal with the return value aka `code` variable
       (if (eq? code 0)
           ;; [1] we wrap the `MyObject` c pointer inside records... 
           (make-my-object* *my-object value)
           (error code))))))
  
;; This is an example of bouding a function pointer found in
;; structure
;;
;; XXX: The syntax of the `foreign` API is structured to allow for easy definition
;;      of this while still allowing for easy binding of toplevel function
(define (my-object-print my-object)
  ;; extra lambda to provide the /bound/ my-object ie. the `this` of C++ or `self` of python
    (foreign
     ;; signature
     (int (my-object-structure-print (my-object-structure my-object)) *pointer*)
     ;; wrapper
     (lambda (foreign-function)  ;; `MyObject->print` method doesn't take arguments
                                 ;; outside the object itself
       
       ;; need to hold a reference to the double pointer
       (foreign-function (my-object-pointer my-object)))))

;;; example use of the bound functions

(define my-object (make-integer-my-object 42))
(pk "it should print 42")
(pk "it should print 113" ((my-object-print my-object)))  ;; XXX: maybe avoid the double parens

property design tips in python

Prelude

Ces astuces sont classés de «classique» à «sujettes à controverse».

Do not @property away

Souvent on veux transformer des méthodes en property. Sauf que c'est pas forcement utile voir pertinent, c'est même parfois dangeureux. Les recommendations suivantes vont de la plus importante à la moins importante, en terminant par une méthode utilisé lors de la maintenance.

Don't hide processing

Règle importante: ne pas cacher un traitement compliqué à l'interieur d'une propriété. L'erreur typique est de pythoniser des valeurs. Ici nous passer un mot en minuscule. L'exemple suivant est simple et met en oeuvre completement la function décorateur property.

keyword_with_property.py:

#!/usr/bin/env python3


class MotClef:

    # XXX: Ne jamais faire ça! C'est moche!
    # Y a beaucoup de code, est inutile la
    # plus part du temps
    def _get_mot(self):
        return self._mot

    def _set_mot(self, chaine):
        self._mot = chaine.lower()

    def _del_mot(self):
        del self._mot

    mot = property(
        _get_mot,
        _set_mot,
        _del_mot,
        'Je suis le mot',
    )


motclef_zero = MotClef()
mot = 'Apparat'
print("«apparat» écrit dans le texte cette façon: ", mot)
motclef_zero.mot = mot
print("Mais il s'écrit en tant que mot-clef de cette façon: ", motclef_zero.mot)

On pourrait placer l'opération de baisse de la casse dans _get_mot et garder dans motclef_un._mot la version trouvé dans le texte. Mais c'est un mélange de symmetrie et d'assymetrie tout pourri. Il vaut mieux faire une rupture plus franche plutôt que tromper le lecteur au sujet du but du code en tentant de simplifir. Surtout, qu'au final, cela fait beaucoup de code.

Il faut lui préféré une méthode explicite par exemple:

keyword_from_string.py:

class MotClef:

    def from_string(self, chaine):
        self.mot = chaine.lower()

motclef_un = MotClef()
motclef_un.from_string('Apparat')
print(motclef_un.__dict__)

De cette façon on propose une assymetrie assez grande pour que le code reste simple et facile à appréhender.

Use property to create shortcuts

property est un outil passionnant pour la maintenance et la rétro-compatibilité. Il permet d'écrire du code vite sans avoir à l'utiliser. Au début du projet, on fait vite ou on veux faire vite. Ch'tite à ch'ti, ça devient un gros boulet avec plein de code et evidement de bug ou de choses qu'on aimerait changer. Dans ce cas, property est à recommender pour eviter de changer beaucoup de code. Il faut toute de même faire attention à ne pas créer du code plus compliquer en ne respectant pas la règle precedente. Par exemple, il est interessant de passer du code suivant:

property_before_shortcut.py:

class MotClef:

    def __init__(self, mot):
        self.mot = mot

Dans une version ultérieur, le mot clef est stocké en base de donnée. Pour eviter de changer tout le code partout on peux faire:

property_with_shortcut.py:

import db


class MotClef:

    def __init__(self, mot):
        self._objet_mot = db.recuperer_objet_mot(mot)

    @property
    def mot(self):
        return self._objet_mot.mot

C'est mathématiquement un bon raccourci.

Don't use @property

Si la valeur n'est pas modifiable c'est pas la peine de la faire passer pour une propriété. Typiquement les identifiants ou les p'tits calculs genre taille du mots. Préférez ce code:

keyword_size.py:

class MotClef:

    def from_string(self, chaine):
        self.mot = chaine.lower()

    def taille(self):
        return len(self.mot)


motclef_un = MotClef()
motclef_un.from_string('Apparat')
print('taille du mot-clef', motclef_un.taille())

Si vous mettez en mémoire le resultat, ne le cachez pas non-plus dans une propriété. Garder le look'n'feel d'une méthode, car - imparable - c'est bien une méthode.

Merge get/set methods

Je termine avec une astuce qui permet de reduire le nombre de méthode dans une API tout en gardant (presque) le même pouvoir sémantique.

Une autre façon de se passer de l'outil property est d'utiliser des méthodes, façon jQuery, en fuisionnant le getter et le setter. Par exemple lors de la création d'une classe qui dessine des mots:

draw_word.py:

# module fictif
from 2d import Canvas


class MonCanvas(Canvas):

    def texte(self, texte=None):
        if texte:
            # met à jour le texte dessiner en ce moment
            self._texte = texte
            self.effacer()
            # dessine le nouveau texte
            self.dessiner(texte)
        else:
            # renvoie le texte qui est dessiner en ce moment
            return self._texte

Ici on utilise la même methode pour assigner une valeur au texte et le (re?) dessiner ainsi que recupérer la valeur du texte si aucun arguments n'est passer en argument. On peut faire autrement mais il y a aura soit plus de méthodes (à se souvenir) soit un property super-pas-légal-et-moche-en-plus.

Why nerfed?

My framework, my very own framework, an API, a tooling around an ontology that I understand, my personal spell dictionary that helps me pursue my dreams. I know it's not fair.

Prelude

This post was motivated by the message of Steven on python tulip (asyncio) mailling-list. I am asking for background. Something that I did not document for nerfed

Nerfed is a framework that I'm working on, an evolving experiment of patterns and ideas. At the very core it's a framework for framework or a toolkit. It doesn't mean to be opiniated like regular frameworks instead it provides tools, patterns and ideas which are well understood and acknowledged (at least by myself) to build upon.

I started this work sometime last year studying Django, Flask, Zope through ZCA and somewhat Pyramid, Kivy, Clutter, a proprietary framework at $WORK and frontend development mostly Javascript based and some knowledge of Java GUIs. Those are not all related, those are not all frameworks, those are not all related to the same topic. I am word-buzzing of course (/duckduckgo optimization). Indeed, I'm not looking at building something for a specific task, it's only a toolkit after all. What I'm looking at is building something that is helpful and useful in crafting softwares (for the real!).

To hijack a marketing punchline, I want to create my Human API.

This sound selfish needless NIH wheel re-invention? Everybody has its toolbelt, small scripts, macros, habitudes and whatnot to “quickly experiments” things and sometimes they stay around or go abroad. I just make it kind of an official project of mine, to inherit some of the rigor related to softwares that are meant to be consumed by other developpers. Still I heavily rely copy/pasting between projects and else. There is an online messy repository, dedicated to socialite.

Guiding principles

It's not opiniated, but still it has some guiding principles:

- KISS: Keep. It. Simple. Stupid. Do not build overkill features. Every component must solve a problem in a simple way. Inhertiance and composition will allow to build more complex constructions. Building something complex is very easy. I attribute to Donald Knuth the quote «It's not by adding things to a system that one makes it perfect, it's by removing». It's so much important to a design, especially a toolkit, that it's implied by the name «nerfed». A simple thing doesn't mean that it must be naive or simplistic.

- DRY: Do. Not. Repeat. Yourself. DRY is not good in every situations but at the toolkit level it is. If two things do almost the same: factorize.

- Symmetry & Asymmetry: Take advantage of symmetry and asymmetry to make things simple and/or factorize.

- No API and Human API: This is implied by the above.

I repeated 4 times mostly the same thing, that nerfed must be simple, easy to the mind.

Components

So far [read “at some point”] there is [read “will be”] 2 components in Nerfed Global Application Tree made of Sub and App objects and a data part made of Imperator objects. Right now is waf specific, based on aiohttp.

Global Application Tree

The GAT is the entry point into the application, it's made of an App class and Sub objects and probably other kind of objects (database, cache, template, expert system...). There is an implementation in Nerfed but it can be summed up as follow in a web context:

class CarbenetCheeseChop(App):

   def __init__(self, settings):
      self.settings = settings

      # utilities

      self.db = DB(self)
      self.redis = Redis(self)
      self.template = TemplateEngine(self)

      # hook routes
      self.admin = self.add_sub('/admin', Admin(self))
      self.favorites = self.add_sub('/favorites', Favorites(self))
      self.login = self.add_sub('/login', Login(self))
      self.index = self.add_route('GET', '/, index)      

import settings
app = Application(settings)
app.wsgi.run()

A Sub is resursive, it has children that are also Sub instance. App is itself a Sub to simplify building simple applications.

This idea of Sub and App comes more or less from Django administration code as of 1.6 and its url system. Which itself has its roots in my reflexion about what a web framework SHOULD allow to do easily, namely create generic applications and plug them anywhere in an existing app several times. In Django terms: multiple instance of an app and routes hooked several times in the app/route system and stay manageable.

A Sub is not meant to be a widget class in the sens of an object having a visual representation with which an enduser CAN interact. The Sub CAN sport a widget. A sub is not a ReactJS Component, it's a controller.

The API itself is in flux, even if I'm pretty confident about the idea. Maybe too much.

Imperator

Imperator class (Je ne suis pas content du nom. Le mot «Data» raisonne creux) is a data-wrapper just like Form and Model classes except it is not smart at all. It statically describe somekind of data, it also provide a few methods to help to deal with it like "clone" or "freeze" to generate a dict from it. It's not just a dict with magic attributes. It's more. (Il fait plus que permettre d'écrire object.key à la place de object['key']). Property attributes are associated with a configuration (instead of behaviors) which allows to share and tune algorithm behaviors all in one place. At least single inhertance is possible. Multiple inheritance CAN make sens.

Otherwise

I'll probably add some classes to implement generic mediator/dispather pattern, state-machine and stuff. I will deal with that when I have more experience with native development. Basicly this is it. Checkout ◊link{github://amirouche/xp/python/nerfed/}{this directory for an example web framework built with those ideas}.

API cognitive load

A problem can have several solutions. A solution can have different implementations each of which with their own strengths and weakness in terms of space, time and genericity.

The goal of a look'n'feel api design is to optimize the cognitive effort required to understand, learn and use an API. Otherwise said, api look'n'feel aim to improve ease. API look'n'feel has nothing to do with the target domain.

While looking for ease one might trade it over expressive power.

Mastering the look'n'feel of an API involves mastering the cognitive load that it inhertent to it.

Cognitive load theory has been designed to provide guidelines intended to assist in the presentation of information in a manner that encourages learner activities that optimize intellectual performance

Sweller, J., Van Merriënboer, J., & Paas, F. (1998). "Cognitive architecture and instructional design". Educational Psychology Review

Here is some of those guidelines:

  1. People learn more effectively when they can build on what they already understand
  2. Take advantage of schemata
  3. Take advantage of visual thinking and other non-verbal thought
  4. The average person can retain only seven "chunks" of information in (short-term) memory
  5. Repeat!

Code Crafting Codex

At the very core of programming, there is an obvious need for a divide and conquer strategy. And that is at the personal level of reflexion. Of course it happens to be true in other domains.

This idea is also expressed as Separation of Concerns which wikipedia nails its value in the following wishful paragraph without mentioning its evil extrema:

The value of separation of concerns is simplifying development and maintenance of computer programs. When concerns are well separated, individual sections can be developed and updated independently. Of special value is the ability to later improve or modify one section of code without having to know the details of other sections, and without having to make corresponding changes to those sections.

Otherwise said two components satisfy “separation of concerns” if their implementation details don't leak.

Drawing lines is not easy, especially when you considered the infinite entangledments of human understandings.

I think that Zen of Python by Tim Peters provides useful abstract guiding principles:

Zen of Python Beautiful is better than ugly. Explicit is better than implicit. Simple is better than complex. Complex is better than complicated. Flat is better than nested. Sparse is better than dense. Readability counts. Special cases aren't special enough to break the rules. Although practicality beats purity. Errors should never pass silently. Unless explicitly silenced. In the face of ambiguity, refuse the temptation to guess. There should be one -- and preferably only one -- obvious way to do it. Although that way may not be obvious at first unless you're Dutch. Now is better than never. Although never is often better than *right* now. If the implementation is hard to explain, it's a bad idea. If the implementation is easy to explain, it may be a good idea. Namespaces are one honking great idea -- let's do more of those!

Those quotes are also helpful:

Simple things should be simple, complex things should be possible

Alan Kay

Perfection is achieved, not when there is nothing more to add, but when there is nothing left to take away.

Antoine de Saint-Exupery

To design something really well, you have to get it. You have to really grok what it's all about. It takes a passionate commitment to really thoroughly understand something, chew it up, not just quickly swallow it. Most people don't take the time to do that.

Steve Jobs

Programs are meant to be read by humans and only incidentally for computers to execute

Donald Knuth

The following quote must be studied in the light of broad sens that can take *the word before the last*:

There are only two hard things in Computer Science: cache invalidation and naming things.

Phil Karlton

And this one provides more food for thought:

The Internet was done so well that most people think of it as a natural resource like the Pacific Ocean, rather than something that was man-made. When was the last time a technology with a scale like that was so error-free? The Web, in comparison, is a joke. The Web was done by amateurs.

Alan Kay

If sounds, grounds, ideas and understandings are echoing, don't overestimate their infinite reflection that might be aiming an unforeseen dubious equilibrium, find you way out, escape the invisible tie knot, think on your own.

I'm doing it wrong

Quand je me retourne et je regarde les projets informatiques que j'ai fait ces 5 dernières années je me dis vraiment, what the fuck. J'ai négligé mes amis, ma famille et ma copine *hum* mon ex pour autant de trucs que j'ai jetés ou jetables. C'est en général du code qui m'a pris du temps, plus d'une soirée ou un week end par mois.

Si je ne l'avais pas fait, est ce que je serais aussi à l'aise en informatique?

En tout cas je suis persuadé que j'aurai pu mieux faire. Déjà en passant moins de temps sur chaque sujet. Sans essayer de passer par la case «je vais faire un projet complet qui va sauver le monde, me rendre empereur de la Terre et ses environs». J'en rajoute mais bon.

Le pire, ça doit être le sujet des graphdbs. Au final, il me semble que ce n'est pas possible de remplacer une base de donnée relationnel completement avec ce type de base de donnée. Pour certains problèmes ça reste interessant. C'est hyper élégant, simple, puissant mais pas suffisament je pense pour se séparer de postgres. Le pire, c'est que j'ai dérivé pour reinventer la roue. J'avais plein de raisons que je pensais raisonnable, mais au final j'ai juste fait mumuse avec des APIs.

Les bénéfices que j'en tire me semble maigres.

Je pense aussi que ce n'est pas la meilleur façon de faire progresser le logiciel libre et la cause du libre. Contribuer à des projets logiciel ou associatif existant c'est beaucoup plus interessant (et ceci est vrai aussi pour trouver un (bon) travail (même si certains s'en sorte s'en faire de libre)). C'est aussi plus difficile pas seulement parce qu'il y a déjà du code à lire ou parce qu'il faut interagir avec des gens mais aussi parce que ça change de mes habitudes.

Je pense aussi qu'on apprend plus, plus rapidement. Primo en lisant du code plus complexe et plus travaillé. Deuxio, on a des retours sur son code. Tertio rencontrer des gens et discuter ce qui est plus facile pour transmettre des connaissances que passer par du code.

À l'avenir, je reflechirai à deux fois avant de me lancer dans des projets perso pour privilegier les contributions.

J'ai encore incoming dans le pipe que je pense se demarque de mes précédents projets dans le sens où c'est un truc dont j'ai vraiment besoin et qui peux interesser d'autres personnes que des dev. Je dois encore mieux étudier les alternatives pour decider comment je vais continuer, si je continue. Je vais m'efforcer de trouver un moyen de l'integrer à projet existant. Sinon j'ai déjà une petite liste projets auxquelles j'aimerai contribuer.

5 things to make GNU Guile go from awesome to perfect

I (re)started to learn Guile Scheme. It's refreshing to code in this language without me feeling overwhelmed like with Haskell. Anyway they are a few things I'd like to be changed to make it perfect!

Whether perfect is better than awesome is left at the discretion of the reader.

0. Explicit and focused modules

There is a bunch of modules so called Scheme Request for Implementation (SRFIs) modules, a great thing, which keep their numeral names in Guile and in most Scheme implementation. Things like (srfi srfi-1) aren't particularly cool.

In general I have the feeling that things can be found in many modules: bytevectors in iconv and rnrs bytevectors, values related forms. Why values is in the builtins and not let-values or my favorite receive. Maybe it's possible to make those builtins?

At the end of the day, I have the filling that I'm looking a lot for procedures and those end up in places I couldn't guess.

let-values is both available in srfi 1 and rnrs. This is weird, I understand that there is standardization reason, but again not user-friendly and common in Guile.

1. There should be one preferable way to things

I know that this principle of Python. It's popular because it's a good thing. Making thing obvious doesn't mean it has to be simplistic.

This also applies to modules in general like stated above.

The obvious examples are procedure definition and value binding. I won't dive into let and its surrogates among which define itself.

There are two ways to define a procedure define and define*. The star means that the form or procedure is more powerful. In this case define* support keyword argument. I suppose that define is faster. I'd rather get things done and then add tweaks and tricks. So to my mind define* should be default.

When you are starting up, you'd rather limit yourself to a few core procedures and then explore what's beyond. At least Guile manual doesn't go that route.

2. use-modules is ugly

use-modules is the form used to import things, which the short version is equivalent to import *. It's true that there is a lot of things to import, compared to Python. That said, being explicit is very helpful to document the code.

It's possible to implement Python import:

import.scm:

(define-syntax-rule (from module import form)
  (use-modules (module #:select (form))))

(define-syntax-rule (from module import form as nickname)
  (use-modules (module #:select (form) #:renamer (lambda (x) 'nickname))))



;; examples:
(from (ice-9 receive) import receive)
(from (wiredtiger) import connection-open as wiredtiger:open)

I did not try to make it a builtin.

3. Currying support is not enough

One has to declare in advance how currying will happen, something like:

currying.scm:

(define* ((add b) c d)
  (+ b c d))

(define add1 (add 1))

(add1 2 3)  ;; 1 + 2 + 3


;; I often stumble upon the following construct
(map (lambda (x) (add1 2015 x)) (iota 42))

With the definition of add it's not possible to simply pass (add1 2015) to map. The lambda makes it very verbose. I recently discovered cut, it might enough, but still more to write than "free curying".

4. let forms are a pain

This is the first issue I stumbled upon, mainly because it adds a lot of parens. I actually like parens. But that is too much. I'm not the only one to find it painful since I often read code avoiding it when possible by using define.

Instead of:

with-let.scm:

(define* (affine a x b)
  (letrec ((alpha (* a x))
	   (beta (+ alpha b)))
    (+ 42 beta)))

You can do:

avoid-let.scm:

(define* (affine a x b)
  (define alpha (* a x))
  (define beta (+ alpha b))
  (+ 42 beta))

That trick doesn't work all the time.

I understand that there are cases where having let is convenient. However why not leave edge cases to what they are and keep other codes clean?

Wrapping up

Really, there is not much more to blame. It's true that sometimes I miss a few procedures here and there. It needs some love to make it more pratical. Hopefully GNU Guix growing popularity will help that cause.

Changing syntax, made more obvious the fact that I needed to rethink things. I read code more often and find it more easy to do. Being able to read Scheme something that seemed so alien and weird a few month ago, is quiet a positive outcome already.

And it also helped me to reconsider learning Haskell.

Lazy will continue

Cette citation de Bob Marlisp est complètement à propos de continuation de séquences paresseuses en scheme.

Dans cette article je vais presenter deux constructions:

1. Les séquences paresseuses similaires aux iterables comme xrange ou aux générateurs simples.

2. Les coroutines, l'équivalent des generateurs améliorés.

lazy sequence

Une sequence est dites paresseuses, si elle ne calcule pas tous les elements qui la compose à l'avance. L'interet est double, d'une part on economise la memoire, d'autre part le calcul se fait en plusieurs fois ce qui repartie la charge CPU dans le temps.

Il existe bien les streams scheme pour faire cela, seulement je veux explorer ça.

Il existe une autre approche emprunté a clojure nommé lazy-seq. Je n'est est pas besoin de la mise en cache des resultats (cela peux consommer beaucoup de memoire (Surtout quand on a pas besoin de cette memoization)).

La méthode simple est inspiré de lazy-seq, le principe est d'utiliser une recurrence et une closure qui va retarder le calcul de la prochaine valeur: Il aussi est possible d'implementer les sequences paresseuses à l'aide de routines de controle du flow des programmes comme yield en Python et call/cc en Scheme que j'essaye d'aborder dans la seconde partie.

lazyseq.scm:

(define multiples-of-three
  (let next ((n 3))
    (lambda ()
      (values n (next (+ n 3))))))

Ligne par ligne cela donne:

1. Definition d'une variable multiples-of-three qui va contenir la définition de la séquence.

2. La deuxieme ligne definie une lambda à l'aide de la forme let nommé qui encapsule le code de la séquence. Le let nommé est très utile pour définir des procédures recurrentes sans utiliser un autre define ou let plus lambda. Le let nommé est bien en dehors de la lambda definissant la séquence.

3. La lambda definissant le comportement de la séquence.

4. Elle retourne deux valeurs grace à values: la valeur courante n *et* à la lambda retourner par next, qui va permettre de continuer l'iteration.

La procédure multiples-of-three retourne toujours 3 et la lambda de la deuxième iteration. Après le premier appel, elle n'est plus jamais appellé. C'est la lambda qui définit la procédure qui est appellé mais avec un contexte différent.

L'utilisation du let nommé complique les choses en un sens. Voici une version qui ne l'utilise pas:

lazyseq-verbose.scm:

(define (multiples-of-three-rec n)
  (values n (lambda () (multiple-of-three-rec (+ n 3)))))


(define (multiples-of-three)
  (multiples-of-three-rec 3))

Voici comment cela s'utilise:

lazyseq-example.scm:

(use-modules (ice-9 receive))


(define multiples-of-three
  (let next ((n 3))
    (lambda ()
      (values n (next (+ n 3))))))


(receive (value next) (multiples-of-three)
  (format #t "~a\n" value)  ;; => 3
  (receive (value next) (next)
    (format #t "~a\n" value)  ;; => 6
    (receive (value next) (next)
      (format #t "~a\n" value))))  ;; => 9

On peux utiliser le même principe en Javascript ou Python. Dans le code suivant je présente une implementation de multiples-of-three en Javascript:

lazyseq.js:

function multiplesOfThree() {

    function next(n) {
	// wrap next call to delay its execution.
	function wrapper () {
	    return next(n + 3);
	};
	return {value: n, next:wrapper};
    }

    return next(3);
}

iter = multiplesOfThree()
console.log(iter)
iter = iter.next()
console.log(iter)
iter = iter.next()
console.log(iter)

Et en Python:

lazyseq.py:

def multiple_of_three():

    def next(n):
	return [n, lambda: next(n+3)]

    return next(3);

value, next = multiple_of_three()
print(value)
value, next = next()
print(value)
value, next = next()
print(value)

Remarque: les deux langages ont déjà un moyen beaucoup plus simple de faire ce genre de chose à l'aide de leur yield respectif, exemple en Python:

lazyseq-yield.py:

def multiple_of_three():
    n = 3
    while True:
        yield n
        n += 3

        
generator = multiple_of_three()

print(generator.next())
print(generator.next())
print(generator.next())

En javascript, avec une version recente de node et le flag --harmony cela donne:

lazyseq-yield.js:

function* multiplesOfThree(){
    var n = 3;
    while (true) {
	yield n;
	n = n + 3;
    }
}


iterator = multiplesOfThree()

console.log(iterator.next())
console.log(iterator.next())
console.log(iterator.next())

Cette méthode resoud en scheme le problème de la construction de la liste paresseuse de façon plus élégante. Ceci dit, il est encore necessaire de construire des procedures map, fold, for-each, filter spécifiques.

Continuations

Au cours de mes lectures il m'a semblé que call-with-continuation (call/cc pour les intimes) était la procedure (?) qui cristalise l'identité minimaliste de scheme dans le sens où il s'agit d'une construction très puissante et simple . Elle n'exsite pas ailleurs, on lui préfére des constructions spécialisés comme yield ou goto. En effet, call/cc peux emuler la plus part si ce n'est pas toutes les constructions de controles. Le support de call/cc se fait au prix de compilateurs/interpreteur plus compliqués.

Sans autres formes de procès voilà une procédure permettant d'implementer des coroutines:

coroutine.scm:

(define (coroutine routine)
  (let ((current routine)
	(status 'new))
    (lambda* (#:optional value)
      (let ((continuation-and-value
	     (call/cc (lambda (return)
			(let ((returner
			       (lambda (value)
				 (call/cc (lambda (next)
					    (return (cons next value)))))))
			  (if (equal? status 'new)
			      (begin
				(set! status 'running)
				(current returner))
			      (current (cons value returner)))
			  (set! status 'dead))))))
	(if (pair? continuation-and-value)
	    (begin (set! current (car continuation-and-value))
		   (cdr continuation-and-value))
	    continuation-and-value)))))

Dans les grandes lignes, un appel call/cc va créer un "label" dynamiquement referencé par la variable passé à la callback de call/cc. La callback est appellé immediatement. Si l'envie lui prend de "quitter/revenir" mais plus precisement the continuer sa vie avec la continuation elle va l'appeller (avec un argument si sa lui chante). Ce comportement de base est illustré dans le code suivant:

simple-callcc.scm:

(define why (call/cc (lambda (return)
		       (format #t "love me or leave me!")
		       (return "I leave!")
		       ;; the program never reach this part
		       (format #t "it probably left :("))))
(format #t "return actually populates WHY variable\n")
(format #t "WHY: ~a\n" why)

Avec cette exemple, on dirait que c'est rien de plus qu'un return. En fait c'est bien plus que ça. La continuation est une variable et pas un keyword, elle peux etre gardé en mémoire, passé à une autre procedure. Elle est dynamique contrairement à goto, qui attend un label qui peut-être resolue par le compilateur.

Mon implementation est loin d'être aussi facile à utiliser que le yield Python. En effet chaque yield crée une nouvelle continuation et donc un nouveau yield cf. second-yield:

coroutine-example.scm:

(define example-coroutine
  (coroutine (lambda (yield)
	       (display "coroutine says: HELLO!")
	       (newline)
	       (let ((second-yield (cdr (yield 1))))
		 (display "coroutine says: WORLD!")
		 (second-yield 2)
		 (newline)
		 (display "coroutine says: SORRY, I'M OUT")))))


(display (example-coroutine))
(newline)
(display (example-coroutine))
(newline)

Clairement cela necessite un peu plus de travail. J'ai tourné en rond un certain temps pour résoudre le problème de la creation des yield pour avoir une syntax moins imbriqué et plus lineaire sur .

Nulle doute que Artanis fera mieux.

Les delimited continuations et la procédure amb sont deux formes de controles qui peuvent être implementé à l'aide de call/cc.

note: search for yield in scheme (or lisp).

Python's __getitem__ meets generators

Python a un certains nombre de méthodes dites «magiques», notamment __getitem__. C'est la méthode qui est appellé lorsque on fait quelque chose comme make[some_fun], c'est l'opérateur «subscript».

Voyons voir:

simple-subscript.py:

class SubScript:

    def __getitem__(self, value):
        return 'value est %s' % str(value)


subscript = SubScript()
print(subscript[42])  # value est 42

# mais aussi
print(subscript[42:52])  # value est slice(42, 52, None)

# et encore
print(subscript[42:52:102])  # value est slice(42, 52, 102)

Vous allez me dire mais à quoi ça sert? Et bien c'est simple: implémenter une classe qui ressemble à une liste. Comme range en Python 3, qui est générateur qui accepte de se faire découper [to slice].

Le code suivant montre comment crée ce type de générateur:

generator-with-subscript.py:

class SubscriptableGenerator:

    def __init__(self, n=None, slice=None):
        self.n = n
        self.slice = slice

    def __getitem__(self, i):
        if isinstance(i, slice):
            return GeneratorSubscriptable(None, i)
        else:
            return self._compute_fibonacci(i)

    def __iter__(self):
        if self.slice:
            if self.slice.step:
                step = self.slice.step
            else:
                step = 1
            n = step
            while n <= self.slice.stop:
                yield self._compute_fibonacci(n)
                n += step
        else:
            n = 0
            while n <= self.n:
                yield self._compute_fibonacci(n)
                n += 1

    def _compute_fibonacci(self, n):
        if n == 0:
            return 0
        elif n == 1:
            return 1
        else:
            a = self._compute_fibonacci(n-1)
            b = self._compute_fibonacci(n-2)
            return a + b

fibo15 = SubscriptableGenerator(15)

print(list(fibo15))

print(fibo15[5])

print(list(fibo15[0:10]))

print(list(fibo15[0:10:2]))

Le code pourrait etre améliorer.

La construction générateur + slice est très interessante.

Berkeley database duplicates entries trick

Avec le backend Btree il est possible d'avoir plusieurs valeurs pour une meme clef. A chaque db.put('super-dupper-high-mojo-key', value) une nouvelle entrée est crée dans la base de donnée avec la clef et cette valeur. Si la clef existe déjà elle est ajouté à la fin (par défaut).

Le problème c'est que lorsqu'on supprime la clef db.delete('super-dupper-high-mojo-key'), la base va supprimer toutes les entrées. C'est pas forcement ce que l'on veux. Une façon de contourner ce problème est de mettre la valeur dans la clef et utilisé une chaine vide comme valeur.

Par exemple, si on index les propriétés des documents avec leur valeur de façon à pourvoir retrouver tous les documents qui ont une valeur donnée pour un champs donnée. Il faut utiliser un curseur, le placer à l'aide de cursor.range correctement:

bsddb-cursor-lookup.py:

from collections import namedtuple


cursor = index.cursor()

# Keys have the following format:
#
#  (attribute_name, value, identifier) -> ''
#
# Where identifier is the identifier of a document
# with ``attribute_name`` set to ``value``.
#
KeyIndex = namedtuple('KeyIndex', ('attribute', 'value', 'identifier'))


def lookup_documents_identifiers(attribute, value):
    # The idenfier placeholder is set to the empty
    # string so that the cursor will be positioned at the first
    # key found for the combination of ``attribute``
    # and ``value`` if any, because the empty strings is the
    # smallest string value and the index is sorted.
    lookup = KeyIndex(attribute, value, '')
    next = cursor.set_range(dumps(lookup))

    while next:
        key, _ = next  # value is a useless empty string
        key = KeyIndex(*loads(key))
        # check that key is within bound of the lookup
        if (key.attribute == lookup.attribute
            and key.value == lookup.value):
            yield key.identifier
            next = cursor.next()
        else:
            # it can mean that:
            #
            #   key.attribute != lookup.attribute
            #
            # which means there is no more document indexed
            # with this attribute, no need to iterate over more
            # keys
            #
            # or that:
            #
            #   key.value != lookup.value
            #
            # They are some document that have a value for
            # ``lookup.attribute`` but ``key.value`` is not
            # what we look for and will never be anymore since
            # the index is ordered.
            #
            # In both case, there is no more matching documents.
            break

En utilisant ce schema il est possible de mettre à jour l'index quand la valeur d'un attribut change sans impacter les autres documents ayant la meme valeur pour un attribut.

Multi-process oracle berkeley database

Another thing that is super useful with bsddb is the ability to access the database from several processus

Voilà, voilà:

multiprocess-bsddb.py:

#!/usr/bin/env python3
import os
from time import sleep
from datetime import datetime
from hashlib import md5
from json import dumps as _dumps
from json import loads as _loads
from shutil import rmtree
from bsddb3.db import *
from sys import exit
from multiprocessing import Process


def dumps(v):
    return _dumps(v).encode('ascii')


def loads(v):
    return _loads(v.decode('ascii'))


# reset database
path = '/tmp/bsddb-mutliprocess'
if os.path.exists(path):
    rmtree(path)
os.makedirs(path)


def opendb():
    # create and open database environment
    env = DBEnv()
    env.set_cachesize(1, 0)
    env.set_tx_max(4)
    flags = (DB_INIT_LOG |
             DB_INIT_LOCK |
             DB_INIT_TXN |
             DB_CREATE |
             DB_INIT_MPOOL
    )
    env.open(
        path,
        flags,
        0
    )
    # create database
    txn = env.txn_begin(flags=DB_TXN_SNAPSHOT)
    flags = DB_CREATE | DB_MULTIVERSION
    counter = DB(env)
    counter.open('counter', None, DB_BTREE, flags, 0, txn=txn)
    txn.commit()
    return env, counter


def writer(identifier):
    print('writer', identifier, 'running')
    env, counter = opendb()
    # open database and update it
    txn = env.txn_begin(flags=DB_TXN_SNAPSHOT)
    counter.put(identifier, dumps(0), txn=txn)
    txn.commit()

    for i in range(100):
        # print('writer', identifier, '@ iteration', i)
        txn = env.txn_begin(flags=DB_TXN_SNAPSHOT)
        count = counter.get(identifier, txn=txn)
        count = loads(count)
        count += i
        counter.put(identifier, dumps(count), txn=txn)
        txn.commit()
        sleep(0.2)
    print('writer', identifier, 'finished')
    counter.close()
    env.close()
    exit(0)


def reader(identifiers):
    # print('reader running')
    env, counter = opendb()
    for i in range(100):
        for identifier in identifiers:
            txn = env.txn_begin(flags=DB_TXN_SNAPSHOT)
            count = counter.get(identifier, txn=txn)
            txn.commit()
            if count:
                count = loads(count)
                print('time:', i, 'read', identifier, count)
        sleep(1)
    print('reader finished')
    counter.close()
    env.close()
    exit(0)


def uuid():
    now = datetime.now()
    now = now.isoformat()
    data = now.encode('ascii')
    id = md5(data)
    id = id.hexdigest()
    return id.encode('ascii')


if __name__ == '__main__':
    jobs = list()
    # spawn (or fork?) two writer
    identifiers = list()
    for i in range(2):
        identifier = uuid()
        identifiers.append(identifier)
        p = Process(target=writer, args=(identifier,))
        p.start()
        jobs.append(p)
    
    # spawn (or fork?) one writer
    p = Process(target=reader, args=(identifiers,))
    p.start()
    jobs.append(p)

    # check for deadlocks...
    env, counter = opendb()
    while True:
        dead = 0
        for job in jobs:
            if not job.is_alive():
                dead += 1
        if dead == 3:
            break
        r = env.lock_detect(DB_LOCK_DEFAULT)
        if r != 0:
            print('deadlock')

    # print result
    txn = env.txn_begin(flags=DB_TXN_SNAPSHOT)
    for identifier in identifiers:
        count = counter.get(identifier, txn=txn)
        if count:
            count = loads(count)
            print(identifier, count)
    txn.commit()
    counter.close()
    env.close()

Bref, ça marchotte plus qu'autre chose avec deux processus writer si on ajoute un sleep dans la boucle. La documentation recommande de faire du tuning pour minimiser les deadlocks. Meme si je sais toujours pas comment bsddb se débrouille avec, il semblerait qu'il tue les processus ou thread qui sont bloqués.

Avec deux écritures toutes les 0.2 secondes cela fait 10 écritures par secondes. Ce qui fait 600 écritures par minutes et 36 000 écriture par heure. Sachant que l'a modification d'un element necessite la lecture et l'écriture de plusieurs clefs.

Problablement que le problème est moins visible lorsque les différents processus accèdent à des clefs différentes.

Ah oui, meme avec un sleep(0.2) des fois ça marche pas du tout.

Making of ajgu graphdb

Description of Ajgu graph database design, which borrows a lot of ideas from titan database

Getting started with graph database

Quelque soit le marketing ou la base de donnée que vous choississez, vous aurez à faire cette API un jour ou l'autre donc la voici en Python avec quelques points specifiques à l'implementation dans Ajgu:

ajgu-basics.py:

class Vertex(dict):
    """Vertex object are returned by a Transaction
    via ``Transaction.get`` or ``Transaction.vertex``.

    Vertex's properties modification will only be persisted
    if done inside the transaction that returned it. Otherwise
    said do not modify a vertex outside of the transaction that
    returned it."""

    def outgoings(self, label=None):
        """Iterate over edges starting at this vertex.

        To only iterate over edges of a given label provide
        label parameter"""

    def incomings(self, label=None):
        """Iterate over edges coming to this vertex.

        To only iterate over edges of a given label provide
        label parameter"""


class Edge(dict):
    """Edge object are returned by a Transaction
    via ``Transaction.get`` or ``Transaction.edge``.

    Edge's properties modification will only be persisted
    if done inside the transaction that returned it. Otherwise
    said do not modify an edge outside of the transaction that
    returned it."""

    def identifier(self):
        """Return the identifier."""
        pass

    def start(self):
        """Retrieve the start vertex."""
        pass

    def label(self):
        """Returns the label."""
        pass

    def end(self):
        """Retrieve the end vertex."""
        pass


class Transaction:
    """``Transaction`` objects work as shadow copy of the actual
    database.

    All reads and writes must be done within a transaction."""

    def vertex(self, label):
        """Create a vertex with ``label`` as label
        and return it"""
        pass

    def edge(self, start, label, end):
        """Create a edge between ``start`` and ``end``
        with ``label`` as label and return it"""
        pass

    def get(self, identifier):
        """Returns the vertex or edge with ``identifier`` as identifier"""

    def all(self):
        """Iterate over all edges and vertex.

        Do not assume a particular ordering."""
        pass

    def query(self):
        pass

    def index():
        pass


class Graph:
    """``Graph`` objects are handles over a graph databases.

    Create or open graph database in ``path`` use the following code::

      graph = Graph('/path/to/database')

    """

    def transaction(self):
        """Context manager which returns a transaction.

        This allows to execute code with a better
        visual cue using the ``with`` keyword:

            with graph.transaction() as transaction:
                vertex = transaction.vertex('gnu/linux')
        """
        pass

    def begin_transaction(self):
        """Start a transaction and returns a ``Transaction`` object.

        This can be useful in complex situations. The transaction
        must be finalized using either ``Transaction.commit()`` or
        ``Transaction.rollback()``.

        ``Graph.transaction()`` should be prefered in simple
        cases (or don't use that if you don't know what you
        are doing)."""
        pass

Ajgu's implementation

bsddb

L'implementation de cette base de donnée est réalisé dans Ajgu à l'aide de Oracle Berkley Database, appellée aussi bsddb. C'est est une base de donnée clef-valeur qui a la remarquable proprieté de permettre d'étaler une transaction sur la lecture et l'écriture de plusieurs clefs. Une autre de ses particularités est le support de differents backends implementant une API d'objet dict augmenté: une table de hash simple, ainsi que un backend btree. De plus, plusieurs processus peuvent acceder à la meme base de donnée.

L'existence d'une propriété ACID dans bsddb permet de facilement implementer une base de donnée en forme de graphe qui veux elle meme fournir des transactions ACID. Dans Ajgu c'est problematique dés le debut dans le cadre de l'implementation de la classe Edge (cf. plus bas).

Le backend HASH de bsddb permet de rendre persistent des associations clefs-valeurs sans que celles-ci tiennent completement en memoire.

Le backend BTREE permet d'implementer un dictionnaire ordonnée à l'aide d'une fonction de comparaison. C'est un outil puissant pour parcourir une liste d'objet. Le point négatif étant que tout le dictionnaire doit tenir en mémoire pour eviter de trop grandes pertes en performances. Les dict augmenté BTREE sont généralement utilisés pour implementer des indexes.

Ajgu utilise un dictionnaire HASH pour rendre persistent les vertex et les edges, alors que des dictionnaire BTREE sont utilisés pour maintenir des indexes.

Ajgu peut-etre multiprocess grace à bsddb. Le verou global de l'interpreteur [GIL] rend les threads inutiles car les requetes peuvent garder le CPU occupé longtemps. Les échanges avec le disque deviennent minoritaire, on perd l'ordonnancement efficace des threads Python.

Bottom Layer

Au dessus d'un dictionnaire bsddb, un schema est implémenté pour permettre de persister les vertex et les edges. Des clefs sont générés aleatoirement et une structure de donnée formée uniquement de dict, list, int et float. Cette structure de donnée represente un vertex ou un edge. Elle contient les propriétés.

Cette structure est transformé en une chaine à l'aide de msgpack. Cette chaine est utilisé comme la valeur associé à la clef.

Les boites jaunes represente les structures de données serialisées à l'aide de msgpack.

Vertex

Le vertex a pour particularité d'enregistrer tous les identifiants des edges sortant et entrant avec leur label.

La structure qui est utilisé pour calculer la valeur associé à un identifiant ressemble à celà:

vertex.py:

value = [
    VERTEX,
    label,
    outgoings,
    incomings
]

VERTEX est une constante qui permet de distinguer dans le dictionnaire bsddb les edges des vertex.

Les variables outgoings et incomings sont des dictionnaires de liste d'identifiants, associant un label à des edges.

vertex-outgoings.py:

outgoings = dict(
    'some_label': [
        '123456789azerty',
        '987654321azerty',
    ],
    'another_label': [
        '123456789wxcvbn',
        '987654321wxcvbn',
    ]
)

Il y a un probleme dans ce schema, un noeud ayant un grand nombre d'edge rendera le vertex «lourd», c'est l'incarnation du problème de Bieber. De meme pour un grand nombre de propriété mais cela est moins courant.

Uniquement les identifiants des edges sont enregistrés avec le noeud. Ceci à pour conséquence d'avoir à «aller chercher» les edges à l'aide de leur identifiant ie. realiser un join. Inclure les edges entierements dans les vertex, renderait la creation et modification des edges couteuses.

Ne pas inclure les idententifiants necessiterait d'avoir la base de donnée en mémoire ou parcourir toute la base pour rechercher les edge en filtrant les edges avec leurs propriétés start ou end.

Edges

Les edges sont plus simples:

Dans la structure de donnée enregistré dans bsddb start et end sont uniquement des identifiants. Faire autrement renderait la manipulation des vertex plus couteuses.

Les vertex et les edges sont optimisés pour la création et modification. La suppression d'un edge ou d'un vertex reste quelque part couteuse car il faut aussi mettre à jour le reste de la base et supprimer les references à l'element supprimé. Voir l'implementation de Vertex.delete et Edge.delete.

Index

Des index sont créent pour permettre une navigation rapide et efficace du graphe. Il existe deux types d'indexes: les indexes globaux et les index locaux.

Global index

Les index globaux peuvent concerner les edges ou les vertex. L'objectif etant de pouvoir acceder à certains elements à l'aide de leur label ou leurs propriétés rapidement sans avoir à pacourir toute la base.

Il y a 2 types d'index globaux:

1. Index d'association exact ou d'unicité

2. Index d'ordonnancement qui peux filtrer mais aussi ordonnancer.

L'association exacte joue le meme role que les PRIMARY KEY, elle permet de retrouver à l'aide d'une chaine (un slug par exemple) ou un entier, un vertex ou un edge:

global-exact-index.py:

graph = Graph('/spam/egg')


# define exact global index
with graph.transaction() as transaction:
    articles = transaction.index()
    # we index only articles
    articles = articles.label('article')
    # we index articles by slug
    articles = articles.unique('slug')


# query an article
with graph.transaction() as transaction:
    making_of_ajgu = transaction.query()
    # find articles
    making_of_ajgu = making_of_ajgu.label('article')
    # fetch articles with 'making-of-ajgu' as slug
    making_of_ajgu = making_of_ajgu.filter('slug', 'eq', 'making-of-ajgu')
    # the "cursor" fetch the first and only result
    making_of_ajgu = making_of_ajgu.one()

Comme le code ci-dessus le montre, la création de l'index se fait en declarant une contrainte d'unicité sur la proprieté «slug» parmis les elements ayant le label «article».

L'index ordonnée permet de parcourir un ensemble d'élement dans un certains ordre en utilisant les fonctions de comparaisons des objets Python.

global-ordered-index.py:

graph = Graph('/spam/egg')


# define exact global index
with graph.transaction() as transaction:
    articles = transaction.index()
    # index only articles
    articles = articles.label('article')
    # index articles with their publication date
    articles = articles.order_by('published_at')


# query last ten articles
with graph.transaction() as transaction:
    articles = transaction.query()
    # find articles
    articles = articles.label('article')
    # order articles
    articles = articles.order_by('published_at')
    # last ten articles
    articles = articles[:-10]

L'index ordonnée peut aussi etre utilisé pour les requetes utilisant l'opérateur d'egalité.

Les deux types d'index global peuvent etre definit à l'aide de different clefs correspondant au label ou à une propriété des elements concernés.

global-filtered-and-ordered-index.py:

graph = Graph('/spam/egg')


# define filtered and ordered global index
with graph.transaction() as transaction:
    articles = transaction.index()
    # index only articles
    articles = articles.label('article')
    # index articles that are in 'hypermove' rubrique
    articles = articles.filter('rubrique', 'eq', 'hypermove')
    # index articles with their publication date
    articles = articles.order_by('published_at')


# query an article
with graph.transaction() as transaction:
    hypermove = transaction.query()
    # find articles
    hypermove = hypermove.label('article')
    # filter to find hypermove articles
    hypermove = hypermove.filter('rubrique', 'eq', 'hypermove')
    # order articles
    hypermove = hypermove.order_by('published_at')

Il est possible de créer des index arbitrairement complexe pour filtrer ou ordonnancé selon plusieurs propriétés.

Local index

L'index local concerne un noeud et ses edges. Cette index permet de charger uniquement les edges associés à un label et à certaines propriétés.

Voir aussi A Solution to the Supernode Problem une explication sur les «Supernode».

Une fois avoir piocher dans l'ensemble des noeuds, la navigation dans le graphe se fait à l'aide d'index locale.

local-index-navigation.py:

graph = Graph('/spam/egg')


# define ordered global index with a match value
with graph.transaction() as transaction:
    # Create a accounts global index
    accounts = transaction.index()
    accounts = accounts.label('accounts')
    accounts = accounts.match('username')  # username is unique
    # Create a local index to retrieve the followee
    followee = transaction.index()
    # the index is defined for vertex with "account" as label
    followee = followee.vertex('account')
    # index incoming edges that have "follow" label
    followee = followee.incomings('follow')
    followee = followee.order_by('followed_at').start()

# with the above indexed defined, the following query should
# be faster
with graph.transaction() as transaction:
    # Retrieve biever user by its username
    query = transaction.query()
    bieber = query.vertex('account').username('bieber')
    # retrieve all it's followees
    followees = bieber.incomings('follow').order_by('followed_at').start()
    # followee is an iterable over all followers of bieber
    

Dans l'exemple précedent l'index est utilisé pour parcourir les noeuds entrants d'un seul noeud. De la meme façon, l'index est utilisé lors des navigations impliquants plusieurs noeuds initiaux:

multiple-vertex-local-index-navigation.py:

graph = Graph('/spam/egg')


# define global index with country index
with graph.transaction() as transaction:
    # Create a articles global index
    person = transaction.index()
    person = person.label('person')
    person = person.match('job')
    # Create a local index
    friends = transaction.index()
    friends = friends.vertex('person')
    friends = friends.outgoings('know').start()
    # with this index, no need to load every single friend
    # to know their iq
    friends = friends.property('iq')


# with the above indexed defined, 
# the following query is faster
with graph.transaction() as transaction:
    # Retrieve all biologist friends
    query = transaction.query()
    biologists = query.vertex('person').job('biologist')
    # retrieve all the people *they* know
    friends_of_biologists = biologists.outoings('know').start()
    iqs = friends_of_biologists.property('iq').all()
    average = sum(iqs) / len(iqs)

What else?

La couche supérieur correspond à l'API de navigation inspiré de Tinkerpop Gremlin. Elle est presenté succintement dans les exemples précedents.

Je ne vais pas aller plus loin dans la description de l'implementation pour deux raisons:

a) J'ai pas encore écrit le code pour les index locaux et la navigation, notamment faire sorte que les indexes soient utilisés quand il le faut.

b) J'ai remis un oeil sur datomic. Après reflexion, un sous-ensemble de son design est plus simple que celui proposé par les bases de donnée en forme de graphes tout en étant aussi puissant. Certes un graphe d'objet est un graphe de donnée, mais utiliser une base de donnée en forme de graphe dans un langage orienté objet necessite de penser différemment son modèle de donnée.

Il me semble qu'une base de donnée 0) ACID 1) avec un unique type d'objet, les Elements ayant un comportement similaire aux documents mongodb 2) avec une gestion des «références» ou «clefs étrangères» efficaces 3) et un schema flexible est la base de donnée que je cherchais.

Les index de datomic sont un élèment de réponse à l'implementation d'une telle base de donnée, ils se cachent derrière les index globaux et locaux de feu Ajgu (qu'il repose en paix) mais en plus générique (et plus puissants?).

Pour voir plus de code, téléchargez ajgu-database-nov-2014.zip

Getting started with Oracle Berkeley Database

Berkeley database est la base de donnée la plus utilisé dans le monde d'après ses créateurs. Pourquoi? Car elle est très flexible. Ici je vais pas m'étaler sur les différentes fonctionnalités. Je défriche la création d'une base de donnée et la création d'index.

Le backend btree est très bien pour créer un index ordonnée.

ordered-keys.py:

import os
import shutil

from bsddb3.db import *

from json import dumps
from json import loads

# reset the database if it already exists
if os.path.exists('/tmp/bsddb'):
    shutil.rmtree('/tmp/bsddb')
os.makedirs('/tmp/bsddb')

# initialize the database
env = DBEnv()
env.open(
    '/tmp/bsddb',
    DB_CREATE | DB_INIT_MPOOL,
    0
)


def compare(a, b):
    # at initialisation time a & b are empty strings
    # those can't be deserialized by json
    if a and b:
        # a and b are string keys
        # In this case comparing them as is, is non-sens
        # they must be deserialized
        a = loads(a.decode('ascii'))
        b = loads(b.decode('ascii'))
        if a < b:
            return -1
        elif a == b:
            return 0
        else:
            return 1
    return 0


index = DB(env)
# set the function to compare keys
index.set_bt_compare(compare)
index.open('index', None, DB_BTREE, DB_CREATE, 0)


# populate the database

# keep track of all the values that are in the database
# in order of insertion
values = list()

i = 0  # keep track of insertion order
def populate(*key):
    global i
    values.append(list(key))
    key = dumps(key).encode('ascii')
    value = dumps(i).encode('ascii')
    index.put(key, value)
    i += 1

populate(1, 0, 0)
populate(3, 0, 0)
populate(0, 2, 1)
populate(2, 0, 0)
populate(0, 2, 0)

# fetch all index values in order
all = list()
cursor = index.cursor()
next = cursor.first()
while next:
    key, value = next
    key = loads(key.decode('ascii'))
    value = loads(value.decode('ascii'))
    all.append(key)
    next = cursor.next()

print('initial keys\t', sorted(values))
print('cursor keys\t', all)
assert sorted(values) == all

Un autre exemple plus parlant qui fait intervenir deux bases de données:

manual-index.py:

import os
import shutil

from bsddb3.db import *

from json import dumps as json_dumps
from json import loads as json_loads


def dumps(value):
    return json_dumps(value).encode('ascii')


def loads(value):
    return json_loads(value.decode('ascii'))


# reset the database if it already exists
if os.path.exists('/tmp/bsddb'):
    shutil.rmtree('/tmp/bsddb')
os.makedirs('/tmp/bsddb')

# initialize the database
env = DBEnv()
env.open(
    '/tmp/bsddb',
    DB_CREATE | DB_INIT_MPOOL,
    0
)


# create articles database
articles = DB(env)
# DB_HASH is recommanded for database
# that can not fit fully in memory
articles.open('articles', None, DB_HASH, DB_CREATE, 0)


# create index database
def compare(a, b):
    if a and b:
        a = loads(a)
        b = loads(b)
        if a < b:
            return -1
        elif a == b:
            return 0
        else:
            return 1
    return 0


def duplicate(a, b):
    # this compares ascii bytes values of the index
    # this is supposed to be the default comparaison
    # but the bsddb fails to do so
    if a < b:
        return -1
    elif a == b:
        return 0
    else:
        return 1

index = DB(env)

index.set_bt_compare(compare)
index.set_dup_compare(duplicate)
index.open('index', None, DB_BTREE, DB_CREATE, 0)


# populate the database
def populate(title, body, published_at, modified_at):
    value = dict(
        title=title,
        body=body,
        published_at=published_at,
        modified_at=modified_at,
    )
    value = dumps(value)
    # save article in articles database
    # here title is used as a key but it can
    # be anything memorable.
    key = title.encode('ascii')
    articles.put(key, value)

    # index the article
    key = (published_at, modified_at)
    key = dumps(key)
    value = title.encode('ascii')
    index.put(key, value)


body = 'a k/v store is a dictionary a set of key/value associations'
populate('Getting started with kv store (1/2)', body, 1, 5)
body = 'the gist of the practice of using kv stores is to build'
body += ' a schema on top of it using string patterns'
populate('Getting started with kv store (2/2)', body, 2, 2)

# for some reason the following article is put in the database
# before the followings even if it is published later
body = 'Wiretiger is kind of the successor of bsddb'
populate('Behold wiredtiger database (1/2)', body, 6, 10)

body = 'bsddb has still room to be put to good use.'
populate('Almighty bsddb (1/2)', body, 4, 3)
body = 'bsddb is stable!'
populate('Almighty bsddb (2/2)', body, 5, 2)

# the following articles will have the same index key
body = 'Working with wiredtiger is similar. Take advantage of its'
body += 'own features'
populate('Behold wiredtiger database (2/2)', body, 7, 0)
body = 'Good question'
populate('Is it worth the trouble?', body, 7, 0)


print('* All articles in chronological order')
cursor = index.cursor()
next = cursor.first()
while next:
    key, value = next
    key = loads(key)
    # the value is the title, this can also be used
    # to fetch the associated article in articles database
    title = value.decode('ascii')
    published_at, modified_at = key
    print('**', published_at, modified_at, title)
    next = cursor.next()


print('\n* All articles published between 4 and 6 inclusive in chronological order')

cursor = index.cursor()
next = cursor.set_range(dumps((4, 0)))
while next:
    key, value = next
    key = loads(key)
    if 4 <= key[0] <= 6:
        title = value.decode('ascii')
        published_at, modified_at = key
        print('**', published_at, modified_at, title)
        next = cursor.next()
    else:
        break


print('\n* Last three articles in anti-chronological order with body')
cursor = index.cursor()
previous = cursor.last()  # browse the index in reverse order
for i in range(3):
    # we don't need to deserialize the key
    _, value = previous
    # the value is the title, it is used to fetch the full article
    # datastructure. This is a join.
    article = articles.get(value)
    article = loads(article)
    title = value.decode('ascii')
    body = article['body']
    print('**', '%s: %s' % (title, body))
    previous = cursor.prev()

Comme c'est un peu très souvent qu'il faut construire des indexes bsddb fournis des routines pour aider:

automatic-index.py:

import os
import shutil

from bsddb3.db import *

from json import dumps as json_dumps
from json import loads as json_loads


def dumps(value):
    return json_dumps(value).encode('ascii')


def loads(value):
    return json_loads(value.decode('ascii'))


# reset the database if it already exists
if os.path.exists('/tmp/bsddb'):
    shutil.rmtree('/tmp/bsddb')
os.makedirs('/tmp/bsddb')

# initialize the database
env = DBEnv()
env.open(
    '/tmp/bsddb',
    DB_CREATE | DB_INIT_MPOOL,
    0
)


# create articles database
articles = DB(env)
# DB_HASH is recommanded for database
# that can not fit fully in memory
articles.open('articles', None, DB_HASH, DB_CREATE, 0)


# create index database
def compare(a, b):
    if a and b:
        a = loads(a)
        b = loads(b)
        if a < b:
            return -1
        elif a == b:
            return 0
        else:
            return 1
    return 0


def duplicate(a, b):
    # this compares ascii bytes values of the index
    if a and b:
        if a < b:
            return -1
        elif a == b:
            return 0
        else:
            return 1
    return 0

index = DB(env)

index.set_bt_compare(compare)
index.set_dup_compare(duplicate)
index.open('index', None, DB_BTREE, DB_CREATE, 0)


# XXX: this is the main change to the code
def callback(key, value):
    # this will keep the index automatically up-to-date
    value = loads(value)
    published_at = value['published_at']
    modified_at = value['modified_at']
    key = (published_at, modified_at)
    key = dumps(key)
    return key
articles.associate(index, callback)


def populate(title, body, published_at, modified_at):
    value = dict(
        title=title,
        body=body,
        published_at=published_at,
        modified_at=modified_at,
    )
    value = dumps(value)
    # save article in articles database
    key = title.encode('ascii')
    articles.put(key, value)
    # no need to update the index database
    # it's done by bsddb


body = 'a k/v store is a dictionary a set of key/value associations'
populate('Getting started with kv store (1/2)', body, 1, 5)
body = 'the gist of the practice of using kv stores is to build'
body += ' a schema on top of it using string patterns'
populate('Getting started with kv store (2/2)', body, 2, 2)
body = 'Wiretiger is kind of the successor of bsddb'
populate('Behold wiredtiger database (1/2)', body, 6, 10)
body = 'bsddb has still room to be put to good use.'
populate('Almighty bsddb (1/2)', body, 4, 3)
body = 'bsddb is stable!'
populate('Almighty bsddb (2/2)', body, 5, 2)
body = 'Working with wiredtiger is similar. Take advantage of its'
body += 'own features'
populate('Behold wiredtiger database (2/2)', body, 7, 0)
body = 'Good question'
populate('Is it worth the trouble?', body, 7, 0)


# XXX: index cursor return the primary database value,
# a json serialized article dictionary, no need
# to do the join manually
print('* All articles in chronological order')
cursor = index.cursor()
next = cursor.first()
while next:
    # XXX: just like before key is the **index key**
    # for that article
    key, value = next
    # XXX: but the value is the serialized article value of
    # instead of the primary key of the article
    # which means that the join was done by bsddb
    article = loads(value)
    title = article['title']
    published_at = article['published_at']
    modified_at = article['modified_at']
    print('**', published_at, modified_at, title)
    next = cursor.next()


print('\n* All articles published between 4 and 6 inclusive in chronological order')

cursor = index.cursor()
next = cursor.set_range(dumps((4, 0)))
while next:
    key, value = next
    key = loads(key)
    if 4 <= key[0] <= 6:
        article = loads(value)
        title = article['title']
        published_at = article['published_at']
        modified_at = article['modified_at']
        print('**', published_at, modified_at, title)
        next = cursor.next()
    else:
        break


print('\n* Last three articles in anti-chronological order with body')
cursor = index.cursor()
previous = cursor.last()  # browse the index in reverse order
for i in range(3):
    key, value = previous
    article = loads(value)
    title = value.decode('ascii')
    body = article['body']
    print('**', '%s: %s' % (title, body))
    previous = cursor.prev()


# XXX: The get method of the secondary database ie. the index
# also returns the primary data instead of the primary key
# of the article
print('\n* Retrieve the article published the 6/10')
# XXX: Using index.pget will return (primary_key, primary_data)
# here it's not required to retrieve the primary key
# since it's also available as part of primary_data
value = index.get(dumps((6, 10)))
article = loads(value)
title = article['title']
published_at = article['published_at']
modified_at = article['modified_at']
print('**', published_at, modified_at, title)
value = index.pget(dumps((6, 10)))

# XXX: Let's delete that article
key = title.encode('ascii')
articles.delete(key)

# XXX: Try to retrieve it from the index just like before
value = index.get(dumps((6, 10)))
assert value is None  # it's not anymore in the secondary index

Y a d'autres chose dans bsddb évidemment. Si le sujet vous interesse je vous conseille de lire les documents fournis par Oracle.

Dodge.py

Javascript with a Python syntax

Finalement, j'ai extrait la version veloce de Pythonium pour en faire un projet à part entière. L'idée d'avoir un Python complètement compatible avec CPython ne m'interesse pas.

Sinon dodge.py est disponible dans le dépot pythonium testé uniquement avec Python version 3.4. Il faut aussi classy.js. Ahem... pas tip top cette release mais s'en fou, s'en est pas une de toute façon!

Client feedback on the creation of the Earth

Bonjour Dieu,

Merci beaucoup pour tes efforts. Il y a vraiment quelque chose qui se passe. J'ai quelques points à remonter:

1 – J'aime beaucoup toute cette idée sur la lumière, mais j'ai un doute quant à la nomenclature. «Jour» et «nuit», ça va, mais j'ai le sentiment qu'on pourrait améliorer ça. Des idées ? Il faut vraiment qu'on trouve quelque chose dès que possible.

2 – Re: Le «ciel»... Ça manque de mojo. Il faudrais un truc plus «pop». Vous auriez pas d'autres idées?

3 – J'apprecie le travaille qui a été réalisé au niveau de la terre et des océans, mais en ce moment il y a beaucoup trop d'océan. Il faut s'y mettre et chercher pour trouver de la terre. De façon général, l'océan ne résonne pas vraiment bien avec nos utilisateurs. En discutant de ce sujet, l'équipe est venu avec une idée: pourquoi ne pas supprimer les océans. Des idées?

4 – On a remarqué que vous aviez recouvert la terre de végétation qui se reproduisent uniquement entre eux. De meme pour les arbres fruitiers. C'est fait exprès? S'il vous plaît donner votre avis.

5 – Actuellement, nous avons deux grandes sources de lumière dans le ciel... une grosse le jour et une plus petite la nuit? Nous craignons de ne pas avoir été clair lors de l'exposé initiale. Nous avons réellement besoin de plus que ça. Il faut que se soit mémorable, une experience à grande valeur ajoutée pour nos utilisateurs. Veuillez vous référer aux slides page 13 et 14. Donnez de la voix si nécessaire.

6 – Les océans remplit de vie ça passe, mais encore une fois, il faut reduire sa superficie. C'est un no-go pour nous.

7 – Est ce que c'est la dernière version des oiseaux? On a un mauvais feeling avec eux. On souhaiterais des clarifications avant de nous exprimer plus à ce sujet.

8 – Est ce qu'on pourrait avoir plus de bétail et d'animaux sauvages qui se baladent ensemble par éspèce? Encore une fois, chez notre utilisateur finale (slide 18) la terre et les animaux qui trainent dessus c'est hyper important. De fait, tout ce qui va permettre d'augmenter la quantité de terre permettra de transformer les utilisateurs passif en évangéliste.

9 – Re: «L'humanité.» Point interessant suite au brieffing. Ce qui est douleureux, c'est que l'humanité soit largement inspiré par vous. Heureusement, il y a plusieurs catégories d'utilisateurs (slide 27) et on veux vraiment qu'il se sente représenté (slide 28). Avoir des mamiphères bipèdes qui «dominent» la terre et les océan (si il y a toujours des océans) risque de démontiver nos utilisateurs, ce qui les frainera dans leur conversation en évangeliste. Pour faire court, une version alternative de l'humanité est à proscrire. C'est possible?

10 – Oubliez complétement «Soyez féconds et multipliez vous». Celà ne résonne pas du tout avec notre l'engagement de marque comme une marque familliale (slide 34).

Je comprend que c'est samedi et vous avez peut-etre envisagé de vous mettre une mine demain pour admirer votre création et tout, mais j'espère que vous pourrez reprendre ça demain. Je dois me presenter lundi à la première heure devant l'équipe dirigeante, il serait donc bien qu'on puisse nous aussi faire un point demain à la première heure. Je serait pas loin de mon téléphone toute le week-end pour discuter. Vous et votre équipe approchez une grande victoire.

Merci!

Cette article est une traduction de Client Feedback On the Creation of the Earth

Python 3 the very basics

Les bases qui permettent de se servir de Python comme d'une calculette pour faire les courses.

Il y a plein de ressources en français pour apprendre le Python, je ne pense pas continuer cette série d'article. À la place voici une liste qui peux aider: a) Débuter avec Python au lycée b) Introduction à Python 3 sans oublier le mémento qui va avec.

Cette note est basée sur learn X in Y minutes sous license Creative Commons by-sa. La license est maintenue à l'identique.

python-3-le-minimum-du-minimum.py:

#!/usr/bin/env python3
# Une ligne de commentaire commence par un croisillon

# La PEP8 recommende de laisser un espace après le croisillion
# cf. http://legacy.python.org/dev/peps/pep-0008/

# La PEP8 recommende de ne pas écrire de lignes de plus de 80
# caractères. Si le commentaire ne tiens pas en une ligne
# il est possible d'enchainer les lignes de commentaires.


# 1. Types de bases et leurs opérateurs

# Il existe deux types de nombres:
# - les nombres décimaux dit flottants
# - les nombres entiers

# Les opérations mathématiques ressemblent à des opérations mathématiques
1 + 1  # => 2
8 - 1  # => 7
10 * 2  # => 20

# Les commentaires peuvent aussi se trouvrer à la fin d'une ligne.
# La PEP8 recommende de laisser deux espaces à la fin du code
# avant le croisillon

# Par défaut la division retourne un nombre flottant
35 / 5  # => 7.0

# Il existe un opérateur de division entière (ie. euclidienne)
5 // 3  # => 1
-5 // 3  # => -2

# Si un flottant apparait dans une opération arithmétique
# le resultat sera un flottant
3 * 2.0  # => 6.0

# La division entière de deux flottants va retourner
# la "version" flottant du resultat de la division entière
5.0 // 3.0  # => 1.0 au lieu de 1 
-5.0 // 3.0  # => -2.0 au lieu de 2

# Pour réalisé un modulo il faut utiliser le caractère ``%``
7 % 3  # => 1

# Il est possible d'utiliser des parenthèses pour grouper
# les opérations arithmétiques
(1 + 3) * 2  # => 8

# Il existe un type booléen
True
False

# Il est possible de nier une valeur booléene à l'aide de
# l'opérateur ``not``
not True  # => False
not False  # => True

# L'opération d'égalité se fait à l'aide d'un double signe égale
1 == 1  # => True
2 == 1  # => False

# Il existe aussi un opérateur d'inégalité
1 != 1  # => False
2 != 1  # => True

# Ainsi que les opérateurs classiques de comparaisons
1 < 10  # => True
1 > 10  # => False
2 <= 2  # => True
2 >= 2  # => True

# Il est possible d'enchainer les comparaisons
1 < 2 < 3  # => True
2 < 3 < 2  # => False

# Il y a trois façons de rentrer des chaines de caractères
string = 'This is also a string.'
# Dans la chaine suivante le caractère ``'`` apparait
string = "Lil' did you know."
# Dans la chaine suivante les caractères ``'`` et ``"``
# apparaisent dans la chaine. Aussi la chaine peut s'étaler
# sur plusieurs lignes.
string = """This isn't a "mishmash

this pure Python!"""

# Il est possible d'acceder aux élèments de la chaine à l'aide
# de l'opérateur ``spam[]``
"This is a string"[0]  # => 'T'

# Il est possible d'ajouter des chaines de caractères
chaine = "Hello " + "world!"  # => "Hello world!"

# Cela dit ce n'est pas la méthode recommendé, il faut lui preferer
# l'interpolation
"%s can be %s" % ('string', 'interpolated')


# ``None`` est un objet unique, il correspond à ``null`` dans
# d'autres langages
None  # => None

# Il ne faut pas utiliser l'opérateur d'égalité ``==`` pour comparer
# un objet à ``None``. ``is`` est l'opérateur qu'y conviens.
"etc" is None  # => False
None is None  # => True


# 2. Variables et Collections

# Pour créer une variable, il suffit de lui assigner une valeur
some_var = 5
some_var  # => 5

# La PEP8 recommende d'utiliser des lettres_minuscules_separe_par_des_espaces
# pour nommer les variables

# Il est possible d'assigner une nouvelle valeur à une variable sans
# autre forme de procès
some_var = 3.14
some_var = True

# Acceder à une variable qui n'a pas été définit précédemment va
# lever une erreur dites "NameError"
some_unknown_var
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
# NameError: name 'some_unknown_var' is not defined


# Créer une liste ordonnée vide
some_list = list()
# Créer une liste ordonnée avec des élèments
some_other_list = [3, 4, 5, 6]

# Pour acceder à un élèment de la liste, la meme syntaxe vue
# por les chaines peut-etre utilisé
some_other_list[0]  # => 3

# En cas de dépassement, une erreur dite "IndexError" est levé
some_other_list[4]
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
# IndexError: list index out of range


# Il est possible de parcourir la liste en sens
# inverse en utilisant des index négatifs
some_other_list[-1]  # => 6
some_other_list[-2]  # => 5

# Il est possible de retirer des élèments de la liste à l'aide du mot-clef ``del``
del some_other_list[2]  # [3, 4, 6]


# Il est possible d'ajouter une liste à une autre liste
a = [1, 2, 3]
b = [4, 5, 6]
ab = a + b  # [1, 2, 3, 4, 5, 6]

# Il est possible d'ajouter un element à une liste de la façon suivante:
yet_another_list = ab + [7]  # [1, 2, 3, 4, 5, 6, 7]

# Pour savoir si un élèment est inclus dans une liste
# il faut utiliser le mot-clef ``in``
1 in yet_another_list   # => True


# Il est possible assigner les élèments d'une liste
# à des variables à l'aide de la syntaxe suivante
a, b, c = [1, 2, 3]     # a == 1, b == 2 et c == 3


# Un dictionnaire est un ensemble d'association clef -> valeur.
# Dans un certains sens, il est similaire à une liste, sauf que le plus souvent
# pour acceder aux valeur il faut passer par des chaines.
#
# Il est possible de créer un dictionnaire vide à l'aide de la syntaxe suivante
empty_dict = dict()
# Un dictionnaire pre-remplis peut-etre créer de la façon suivante:
filled_dict = {"one": 1, "two": 2, "three": 3}

# Pour acceder aux valeur utiliser la syntaxe ``some_dict[clef]``
filled_dict["one"]   # => 1
# un code équivalent:
key = 'one'
filled_dict[key]

# Pour verifier l'existence d'une clef il faut utiliser
# le mot-clef ``in``
"one" in filled_dict  # => True
1 in filled_dict  # => False

# Acceder à une clef qui n'existe pas va lever une erreur
# dite "KeyError"
filled_dict["four"]
# Traceback (most recent call last):
#   File "<stdin>", line 1, in <module>
# KeyError: 'four'

# Il est possible de supprimer une entrée dans le dictionnaire
# à l'aide de la syntaxe suivante
del filled_dict["one"]


# Un ensemble peux-etre créer à l'aide du code suivant:
empty_set = set()
# Pour créer un ensemble pré-remplit, le code suivant est suffisant:
some_set = {1, 1, 2, 2, 3, 4}
# un ensemble contiens chaque valeur une fois
some_set == {1, 2, 3, 4}  # => True

# Pour connaitre l'intersection entre deux ensembles,
# l'opérateur esperluete ``&`` peut etre utiliser
other_set = {3, 4, 5, 6}
some_set & other_set   # => {3, 4}

# Pour réaliser l'opération d'union il faut utiliser
# L'opérateur trait vertical ``|``
some_set | other_set   # => {1, 2, 3, 4, 5, 6}

# Pour réaliser l'opération de différence, il faut utiliser
# l'opérateur moins ``-``
{1, 2, 3, 4} - {2, 3, 5, 7}   # => {1, 4, 7}

# Le mot-clef ``in`` permet de savoir si un élèment est dans
# un ensemble
2 in some_set   # => True
10 in some_set   # => False

# Il est aussi possible de verifier l'existence d'un objet
# dans une liste a l'aide du meme operateur ``in`` 
2 in [1, 2, 3]
2 in [4, 5, 6]

# Enfin...
# None, 0, les chaines vides, les listes vides et les dictionnaires vides
# et les ensembles vides sont considérés comme ayant une valeur ``False``
bool(0)  # => False
bool("")  # => False
bool([])  # => False
bool({})  # => False

# Toutes les autres valeurs sont considérées comme équivalentes à ``True``

[python3]

Maintenant quelques exercices:

1. Etant donnée un livre qui a 250 pages, 60 lignes par page et 15 mots par ligne en moyenne. Combien de mot y a t-il a peu pres dans le livre?

2. Etant donnee la phrase "Quelle belle arbre" ainsi que "Quelle belle fleur", calculer le nombre de mots qui apparaissent dans les deux phrases.

3. On considère deux dictionnaires, le premier est former par l'association des chiffres de 0 a 9 avec leur écriture en francais, le second est former par les chiffres de 0 a 9 en francais associés aux nombres de 0 a 9 en anglais. Mettez en place une suite d'operation qui permet de retrouver l'ecriture d'un nombre en anglais a partir d'un chiffre.

Good luck!