Au début était la tortue Logo

Quand j'étais à l'école primaire, notre classe disposait de deux ordinosaures Thomson MO5 et TO7, reliques du plan français informatique pour tous. Ces deux machines étaient déjà dépassées à l'époque et décoraient le fond de notre classe.

Un jour, l'institutrice dépoussiéra un des ordinateurs Thomson et le démarra. Je me souviens que cet ordinateur austère, avec son crayon optique, était particulièrement pénible à utiliser. Son utilisation difficile avait de quoi entamer la curiosité d'un enfant, mais l'ordinateur proposait néanmoins une application amusante : la tortue Logo.

C'est cette tortue Logo que je vais essayer d'animer dans cet article en présentant un script écrit en Python capable d'afficher sa trace. Le tout en moins de 100 lignes de code que je commenterai.

Principe de la tortue Logo

La tortue Logo est un robot qui se déplace à la surface de l'écran. Un crayon est attaché à la tortue et trace son chemin quand il est baissé. La tortue obéit aux commandes formulées par son guide comme AVANCE, REPETE ou TOURNEDROITE.

Voici plusieurs polygones tracés par la tortue Logo, du triangle à l'octogone :

REPETE 3 [ AVANCE 50 TOURNEDROITE 120 ]
REPETE 4 [ AVANCE 50 TOURNEDROITE 90 ]
REPETE 5 [ AVANCE 50 TOURNEDROITE 72 ]
REPETE 6 [ AVANCE 50 TOURNEDROITE 60 ]
REPETE 8 [ AVANCE 50 TOURNEDROITE 45 ]

Mise en oeuvre et contraintes

Je m'impose les contraintes suivantes pour le programme capable d'afficher la trace d'une tortue Logo.

  • Le programme doit peser moins de 100 lignes de code.
  • Le programme est implémenté en Python. Comme chacun sait le python et la tortue sont des reptiles. Plus sérieusement, l'expressivité du langage Python et ses nombreux modules sont de précieux atouts pour respecter l'objectif de concision.
  • Le code du programme est en français (même si les mots clefs sont en anglais). Je ne parlais pas anglais à l'école primaire. De plus, la tortue ne comprend que le français.
  • Le programme enregistre la trace de la tortue dans une image adaptée à la publication sur le Web. Le format choisi est le format vectoriel SVG.
  • Le programme est suffisamment élaboré pour "tracer mon logo en Logo". Mon logo est un space invader façon pixel art.
  • Le programme n'est pas interactif. Il accepte en entrée un fichier contenant les commandes Logo et génère en sortie une image vectorielle SVG.

Ma tortue Logo en Python

Voici les 98 lignes de ma tortue Logo écrite en Python (fichier source). L'implémentation est grandement simplifiée en utilisant les bibliothèques pyparsing et svgwrite.

#!/usr/bin/python

from collections import namedtuple
from math import cos, sin, pi
from pyparsing import *
from svgwrite import Drawing
from svgwrite.path import Path
import sys

av = Group((Keyword('AV') | Keyword('AVANCE')).setParseAction(replaceWith('AV')) + Word(nums))
bc = Group(Keyword('BC') | Keyword('BAISSECRAYON').setParseAction(replaceWith('BC')))
lc = Group(Keyword('LC') | Keyword('LEVECRAYON').setParseAction(replaceWith('LC')))
re = Group((Keyword('RE') | Keyword('RECULE')).setParseAction(replaceWith('RE')) + Word(nums))
td = Group((Keyword('TD') | Keyword('TOURNEDROITE')).setParseAction(replaceWith('TD')) + Word(nums))
tg = Group((Keyword('TG') | Keyword('TOURNEGAUCHE')).setParseAction(replaceWith('TG')) + Word(nums))
commande = av | bc | lc | re | td | tg
repete = Group(Keyword('REPETE') + Word(nums) + Literal('[').suppress() + OneOrMore(commande) + Literal(']').suppress())
logo = OneOrMore(repete | commande)

LARGEUR_CANEVAS = 400

Position = namedtuple('Position', 'x y')

class Tortue:
    def __init__(self):
        self.pos = Position(LARGEUR_CANEVAS / 2, LARGEUR_CANEVAS / 2)
        self.cap = 0  # en degres : 0 => haut, 90 => droite
        self.crayon_bas = True
        self.chemin = Path(d='', stroke = 'black', fill='white')
        self.chemin.push('M{x},{y}'.format(x=self.pos.x, y=self.pos.y))

    def __radian(self):
        return self.cap * pi / 180.0 - pi / 2.0

    def avance(self, nb_pas):
        self.pos = Position(self.pos.x + int(round(cos(self.__radian()) * nb_pas)),
                            self.pos.y + int(round(sin(self.__radian()) * nb_pas)))
        if self.crayon_bas:
            self.__svg_lineto()

    def recule(self, nb_pas):
        self.avance(- nb_pas)

    def tourne_droite(self, angle):
        self.cap = (self.cap + angle) % 360

    def tourne_gauche(self, angle):
        self.tourne_droite(- angle)

    def baisse_crayon(self):
        self.crayon_bas = True
        self.__svg_moveto()

    def leve_crayon(self):
        self.crayon_bas = False

    def trace_commandes(self, commandes):
        for cmd in commandes:
            if cmd[0] == 'AV':
                self.avance(int(cmd[1]))
            elif cmd[0] == 'RE':
                self.recule(int(cmd[1]))
            elif cmd[0] == 'TD':
                self.tourne_droite(int(cmd[1]))
            elif cmd[0] == 'TG':
                self.tourne_gauche(int(cmd[1]))
            elif cmd[0] == 'BC':
                self.baisse_crayon()
            elif cmd[0] == 'LC':
                self.leve_crayon()
            elif cmd[0] == 'REPETE':
                nb = int(cmd[1])
                for i in range(nb):
                    self.trace_commandes(cmd[2:])

    def trace_programme(self, programme):
        self.trace_commandes(logo.parseString(programme))

    def trace_fichier(self, fichier):
        with open(fichier, 'r') as contenu:
            self.trace_programme(contenu.read())

    def __svg_moveto(self):
        self.chemin.push('M{x},{y}'.format(x=self.pos.x, y=self.pos.y))

    def __svg_lineto(self):
        self.chemin.push('L{x},{y}'.format(x=self.pos.x, y=self.pos.y))

    def enregistre_svg(self, fichier):
        dessin = Drawing(fichier, profile='full', fill='white')
        dessin.add(self.chemin)
        dessin.save()


if __name__ == '__main__':
    tortue = Tortue()
    tortue.trace_fichier(sys.argv[1])
    tortue.enregistre_svg(sys.argv[2])

Quelques commentaires

Un peu de trigonométrie

Au départ, la tortue Logo est positionnée au centre de l'écran et pointe vers le Nord. Depuis sa position initiale, elle se déplace pas à pas et peut tourner sur sa droite ou sur sa gauche par degrés.

Par exemple, la tortue Logo trace un triangle de 100 pas de côté quand elle avance de 100 pas et tourne de 120 degrés sur sa droite à trois reprises :

REPETE 3 [ AVANCE 100 TOURNEDROITE 120 ]

Pour calculer la position de la tortue après chaque déplacement, il faut tenir compte :

  • de la position initiale de la tortue ;
  • de son orientation ;
  • du nombre de pas qu'elle doit effectuer.

Un soupçon de grammaire

La tortue Logo obéit à des commandes qui ressemblent au langage naturel (AVANCE, TOURNEDROITE, REPETE, etc.). Une partie de notre programme est donc dévolue à l'analyse syntaxique (parsing, en anglais) des commandes Logo.

La bibliothèque pyparsing permet d'implémenter un analyseur syntaxique avec Python en décrivant une grammaire formelle.

Voici, par exemple, la grammaire formelle du mini langage Logo interprétable par notre tortue.

av ::= "AVANCE" + nombre
bc ::= "BAISSECRAYON"
lc ::= "LEVECRAYON"
re ::= "RECULE" + nombre
td ::= "TOURNEDROITE" + nombre
tg ::= "TOURNEGAUCHE" + nombre
commande ::= av | bc | lc | re | td | tg
repete ::= "REPETE" + nombre + "[" + UnOuPlus(commande) + "]"
logo ::= UnOuPlus(repete | commande)

La transcription en Python avec pyparsing se fait presque directement. Pour chaque commande, on définit aussi un raccourci (e.g. AV pour AVANCE) :

av = Group((Keyword('AV') | Keyword('AVANCE')).setParseAction(replaceWith('AV')) + Word(nums))
bc = Group(Keyword('BC') | Keyword('BAISSECRAYON').setParseAction(replaceWith('BC')))
[...]
commande = av | bc | lc | re | td | tg

Une fois que pyparsing a digéré les commandes Logo, la fonction trace_commandes() identifie chaque commande et ses éventuels paramètres et les transmet à la fonction associée :

def trace_commandes(self, commandes):
    for cmd in commandes:
        if cmd[0] == 'AV':
            self.avance(int(cmd[1]))
[...]
        elif cmd[0] == 'BC':
            self.baisse_crayon()
[...]
        elif cmd[0] == 'REPETE':
            nb = int(cmd[1])
            for i in range(nb):
                self.trace_commandes(cmd[2:])

À noter que la fonction trace_commandes() utilise la récursivité pour gérer la commande REPETE.

Un chemin vers SVG

La trace de la tortue Logo est dessinée dans une image SVG avec la bibliothèque svgwrite. Le programme n'utilise qu'un seul élément de SVG, le path qui est parfaitement adapté à notre usage.

Un path SVG comprend un attribut d (pour data) qui est une liste de commandes L (pour lineto) ou M (pour moveto) suivies des coordonnées cartésiennes. La première commande d'un path SVG doit être une commande moveto.

Par exemple, pour tracer un angle droit, il faut donner les coordonnées de trois points et tracer deux lignes entre ces trois points :

<path d="M10,10  L10,100  L100,100"/>

Dans le cas de notre tortue Logo, il suffit d'un path SVG pour matérialiser sa trace.

  • Quand la tortue reçoit la commande BAISSECRAYON, on ajoute une commande moveto pour débuter sa trace.
  • À chaque déplacement de la tortue, on ajoute une commande lineto au path SVG si le crayon est baissé.

Pixel art vectoriel

Pour conclure, j'ai demandé à la tortue Logo de tracer le space invader qui me sert d'avatar (fichier source).

Enfin, la vidéo suivante montre la tortue Logo filant à toute allure telle un lièvre.

Tortue Logo : LEVECRAYON.

Given enough compilers, all bugs are shallow

This post title is a poorly paraphrased version of Linus' law "given enough eyeballs, all bugs are shallow". What I want to illustrate is that using more than one compiler allows to notice more bugs.

I compiled some C++ code at work with Clang instead of GCC and it spotted the following issue with sleep() that GCC ignored:

#include <unistd.h>

int main(void)
{
        sleep(0.5);
        return 0;
}

As noticed by Clang, the argument of sleep is an unsigned int, so sleep(0.5) is converted to sleep(0). This is what happens when Pythonistas dare write some C code (Python's time.sleep() accepts a floating point number of seconds) .

$ clang-3.8 -Wall -Werror test-sleep.c -o test-sleep
test-sleep.c:5:8: error: implicit conversion from 'double' to 'unsigned int' changes value from 0.5 to 0 [-Werror,-Wliteral-conversion]
        sleep(0.5);
        ~~~~~ ^~~
1 error generated.

This is not to say that Clang is better than GCC: both are great compilers. But the effort of compiling a code base with GCC and Clang is worth it because it catches more bugs.

Emulate a slow block device with dm-delay

When debugging a problem caused by high I/O latency on Linux, it may be interesting to emulate a slow or congested block device. The device mapper driver which manages logical volumes on Linux has a solution for that: the dm-delay target.

In this article, we will use the dm-delay target to delay reads and writes to a block device. We will first create a ramdisk which is a blazingly fast block device. Then we will stack a dm-delay target on top of it and measure the I/O latency it introduces.

Creating a ramdisk

A ramdisk is a RAM backed disk. Since data written to RAM do not persist without power, a ramdisk should never be used to store real data. Compared to a hard disk drive, a ramdisk is much smaller in size: its size is capped by the computer RAM size. But as we will see, a ramdisk is much faster than a hard disk drive.

On Linux, a set of ramdisks is created by loading the brd kernel module. The number of ramdisks and their size is configured by passing arguments to modprobe: rd_nr is the maximum number of ramdisks and rd_size is the size of each ramdisk in kibibytes.

$ sudo modprobe brd rd_nr=1 rd_size=1048576
$ ls -l /dev/ram0
brw-rw---- 1 root disk 1, 0 Aug 24 20:00 /dev/ram0
$ sudo blockdev --getsize /dev/ram0 # Display the size in 512-byte sectors
2097152

Creating a delayed target with dm-delay

The kernel documentation explains how to configure a delayed target with dmsetup. For instance, you can use a script like this one to stack a delayed block device on top of a given block device:

#!/bin/sh
# Create a block device that delays reads for 500 ms
size=$(blockdev --getsize $1) # Size in 512-bytes sectors
echo "0 $size delay $1 0 500" | dmsetup create delayed

Checking the latency of dm-delay

Let's check the latency introduced by dm-delay. We use fio to compare the latency of the ramdisk (/dev/ram0) with the latency of the delayed device (/dev/dm-0). The job file for fio that describes the I/O workload is as follows:

[random]
# Perform 4K random reads for 10 seconds using direct I/Os
filename=/dev/dm-0
readwrite=randread
blocksize=4k
ioengine=sync
direct=1
time_based=1
runtime=10

At the end of the run, fio displays a bunch of statistics. One of them is the completion latency (denoted as clat):

  • ramdisk: 1.33 µs
  • delayed block device: 499735.14 µs

The latency of the ramdisk is very low whereas the latency of the delayed block device stacked on top of the ramdisk is close to the 500 ms delay we configured.

A similar experiment for writes shows that dm-delay also delays writes to the device. As a sidenote, if you want to delay writes with dm-delay, you have to provide a second set of parameters to dmsetup:

#!/bin/sh
# Create a block device that delays reads for 500 ms and writes for 300 ms
size=$(blockdev --getsize $1) # Size in 512-bytes sectors
echo "0 $size delay $1 0 500 $1 0 300" | dmsetup create delayed

Suspending I/Os

The device mapper can also be requested to suspend and resume I/Os.

$ sudo dmsetup suspend /dev/dm-0
$ sudo dmsetup resume  /dev/dm-0

Send F10 to GRUB with Minicom

I recently had to modify the kernel command line of a machine that I accessed with a serial console. GRUB displayed the following message explaining that I had to "press Ctrl-x or F10 to boot".

Minimum Emacs-like screen editing is supported. TAB lists
completions. Press Ctrl-x or F10 to boot, Ctrl-c or F2 for
a command-line or ESC to discard edits and return to the GRUB menu.

Unfortunately, pressing F10 in minicom was equivalent to hitting ESC: my changes were discarded and I was sent back to the GRUB menu.

It turns out that the following keystroke sequences allow to send F10 with minicom: ESC+O+Y or ESC+0.

Send desktop notifications with cron

At work, I tend to check my mailbox too often. That's unnecessary. As an experiment, I have decided to check it once every hour. Since I don't want to spend "brain cycles" remembering when I should check my mailbox, I have added a cron task to display a notification every hour.

Desktop notifications on Linux can be displayed with a command line utility named notify-send:

$ notify-send "Hi ${USER}!" "it's time to check your email." --icon=dialog-information

However, when notify-send is invoked by cron, nothing is displayed. The script invoked by cron cannot communicate with the desktop environment because the DBUS_SESSION_BUS_ADDRESS variable is not set.

As a consequence, you have to retrieve the value of the DBUS_SESSION_BUS_ADDRESS for your session. You can do that by parsing the /proc/$PID/environ pseudo file of your window manager (i3 in my case):

$ grep -z DBUS_SESSION_BUS_ADDRESS /proc/$(pidof i3)/environ | cut -d= -f2-
unix:abstract=/tmp/dbus-ajRnZ5v7g9,guid=f8761603e1845a282e104e1a5515bcec

I wrote the following shell script named remind-email to grab the bus address of the DBUS session and display a desktop notification:

#!/bin/sh

export DBUS_SESSION_BUS_ADDRESS=$(grep -z DBUS_SESSION_BUS_ADDRESS /proc/$(pidof i3)/environ | cut -d= -f2-)
notify-send "Hi ${LOGNAME}!" "it's time to check your email." --icon=dialog-information

The script is invoked every hour by the following cron entry (use crontab -e to edit your cron tables):

0 * * * * /home/foo/bin/remind-email