Think Julia

Pour les exercices de ce chapitre, nous utiliserons une liste de mots français. Celle qui convient le mieux à notre objectif est une liste de mots collectée et mise dans le domaine public par Christophe Pallier dans le cadre du projet de dictionnaire Français-GUTenberg de Christophe Pythoud [8]. Il s'agit d'une liste de 336 531 mots encodés en UTF-8. Un navigateur comme Firefox permet d'enregistrer directement ce fichier sous le nom mots_FR.txt (par exemple).

Ce fichier est en mode texte brut, tout éditeur de texte peut l'afficher. Cependant, ce fichier est lisible depuis Julia. La fonction intégrée open prend le nom du fichier comme paramètre et retourne un flux de fichier utilisable pour lire le fichier.

julia> fin = open("/home/chemin_vers_fichier/mots_FR.txt")
IOStream(<file /home/chemin_vers_fichier/mots_FR.txt>)

fin est un flux de fichier utilisé pour l'entrée et lorsqu'il n'est plus nécessaire, il doit être fermé avec close(fin).

Julia fournit plusieurs fonctions de lecture, dont readline qui lit les caractères du fichier jusqu'à arriver à une NEWLINE et retourne le résultat sous forme de chaîne :

julia> readline(fin)
"a"

Le premier mot de cette liste est a (conjugaison du verbe « avoir » à la troisième personne au singulier du présent de l'indicatif).

Le flux de fichiers garde une trace de l'endroit où il s'est arrêté, si bien qu'appeler à nouveau readline conduit à l'affichage du mot suivant :

julia> readline(fin)
"à"

Parce que le fichier peut être parcouru dans une boucle for, ce programme lit le fichier mots_FR.txt et imprime chaque mot, un par ligne :

for line in eachline("/chemin_vers_fichier/mots_FR.txt")
    println(line)
end

Le dernier mot affiché est « zythums ».

9-2-1. Exercice 9-1▲

9-2-2. Exercice 9-2▲

9-2-3. Exercice 9-3▲

9-2-4. Exercice 9-4▲

9-2-5. Exercice 9-5▲

9-2-6. Exercice 9-6▲

Tous les exercices de la section 9.2Exercices présentent un point commun. Ils peuvent être résolus avec le modèle de recherche dans les chaînes (voir la section 8.8Recherche dans les chaînes). L'exemple le plus simple est le suivant :

function hasno_e(word)
    for letter in word
        if letter == 'e'
            return false
        end
    end
    true
end

La boucle for traverse les caractères du mot passé en argument. Si la lettre e est détectée, le programme retourne immédiatement false. Sinon, il passe à la lettre suivante. Si le programme sort de la boucle normalement, cela signifie que la lettre e n'a pas été décelée et, par conséquent, le programme retourne true.

Cette fonction pourrait être reformulée de manière plus concise en utilisant l'opérateur ∉ (\notin TAB), mais la version de base illustre bien la logique du schéma de recherche.

La fonction avoids est une version plus générale de hasno_e, bien qu'elle présente la même structure :

function avoids(word, forbidden)
    for letter in word
        if letter ∉ forbidden 
            return false
        end
    end
    true
end

Le programme peut retourner false dès qu'il trouve une lettre interdite passée comme second argument. S'il arrive au bout de la boucle, le programme retourne true.

La fonction usesonly est analogue, si ce n'est que le sens de la condition est inversé :

function usesonly(word, available)
    for letter in word
        if letter ∉ available
            return false
        end
    end
    true
end

Au lieu d'une série de lettres interdites, nous avons une série de lettres permises. Si nous trouvons une lettre qui n'est pas présente dans un mot, le programme retourne false.

useall est similaire, sauf que nous inversons le rôle du mot et de la série de lettres :

function useall(word, required)
    for letter in required
        if letter ∉ word
            return false
        end
    end
    true
end

Au lieu de parcourir les lettres du mot, la boucle parcourt les lettres obligatoires. Si l'une des lettres requises n'apparaît pas dans le mot, le programme retourne false.

Si vous pensez vraiment comme un informaticien, vous avez identifié que usesall est un exemple de problème déjà résolu. Dans ce cas, il est vraisemblable que vous ayez écrit :

function useall(word, required)
    usesonly(required, word)
end

Il s'agit d'un exemple de plan de développement de programmes appelé réduction à un problème préalablement résolu. Cela signifie que le programmeur identifie le problème sur lequel il travaille comme un cas de problème résolu et qu'il applique une solution existante.

Les fonctions de la section 9.3Recherche ont été écrites avec des boucles for parce que seuls divers caractères des chaînes étaient utiles. Il était donc possible de travailler sans les indices.

Pour isabecedarian, nous devons comparer des lettres adjacentes, ce qui est un peu délicat avec une boucle for :

function isabecedarian(word) 
    i = firstindex(word)
    previous = word[i]
    j = nextind(word, i)
    for c in word[j:end] 
        if c < previous 
            return false
        end
        previous = c
    end
    true
end

Une autre possibilité consiste à faire appel à la récursion :

function isabecedarian(word)
    if length(word) <= 1
        return true
    end
    i = firstindex(word)
    j = nextind(word, i)
    if word[i] > word[j]
        return false
    end
    isabecedarian(word[j:end])
end

Une option supplémentaire revient à exploiter une boucle while :

function isabecedarian(word)
    i = firstindex(word)
    j = nextind(word, 1)
    while j <= sizeof(word)
        if word[j] < word[i]
            return false
        end
        i = j
        j = nextind(word, i)
    end
    true
end

La boucle commence à i = 1 et j = nextind(word, 1). Elle se termine lorsque j > sizeof(word). À chaque passage, la boucle compare le i^ième caractère (qui peut être considéré comme le caractère courant) au j^ième caractère (qui est le suivant).

Si le caractère suivant est inférieur en termes d'ordre alphabétique au caractère courant, alors il y a rupture dans le schéma abécédaire. En conséquence, le programme retourne false.

Si la fin de la boucle est atteinte sans trouver de rupture, alors le mot passe le test. Pour se convaincre que la boucle se termine correctement, nous pouvons prendre pour exemple « choux ».

À présent, voici une version d'ispalindrome qui utilise deux indices. L'un commence au début et croît, l'autre commence à la fin et décroît.

function ispalindrome(word)
    i = firstindex(word)
    j = lastindex(word)
    while i < j
        if word[i] != word[j]
            return false 
        end
        i = nextind(word, i)
        j = prevind(word, j)
    end 
    true
end

Ce cas peut être réduit à un problème préalablement résolu :

function ispalindrome(word)
    isreverse(word, word)
end

La fonction isreverse a été étudiée à la section 8.13Débogage.

Tester des programmes est une tâche complexe. Les fonctions présentées dans ce chapitre sont relativement faciles à tester, car les résultats sont vérifiables manuellement. Nonobstant cela, il est difficile — voire impossible — de choisir un ensemble de mots qui permettent de tester toutes les erreurs possibles.

Par exemple avec hasno_e, deux cas sont évidents à vérifier : les mots qui ont un e devraient amener le programme à retourner false, et les mots qui n'en ont pas devrait forcer le programme à retourner true. Trouver chacun de ces cas est assez facile.

Très souvent, existent des sous-cas moins évidents. Parmi les mots qui contiennent un « e », il convient de tester les mots qui ont un « e » au début, à la fin et quelque part au milieu. Cela implique de tester les mots longs, les mots courts et les mots très courts, comme la chaîne vide. Or, la chaîne vide est un exemple de cas particulier non trivial où des erreurs se camouflent souvent.

En plus des situations de test à traiter manuellement, tester le programme avec une liste de mots comme mots_FR.txt est nécessaire. En analysant la sortie, il est peut-être possible de détecter des erreurs. Attention, toutefois : on court toujours le risque de détecter un type d'erreur (des mots qui ne devraient pas être inclus, mais qui le sont) et inversement (des mots qui devraient être inclus et qui… ne le sont pas).

En général, les tests contribuent à trouver des bogues. En tout état de cause, il n'est guère facile de produire un bon ensemble de tests. Même dans ce cas, personne ne peut être sûr à 100 % que le programme est correct. Selon le célèbre informaticien Edsger W. Dijkstra :

Program testing can be used to show the presence of bugs, but never to show their absence !(19)

flux de fichiers valeur qui représente un fichier ouvert.

réduction à un problème préalablement résolu procédé destiné à résoudre un problème en l'exprimant comme un cas de figure déjà résolu.

cas particulier cas de test atypique ou non trivial (et susceptible de ne pas être traité correctement).

9-7-1. Exercice▲

9-7-2. Exercice 9-8▲

9-7-3. Exercice 9-9▲