Chaines de caractères

Type de données commun dans les langages de programmation, on va ici s'attaquer aux chaines de caractères.

Dans ce chapitre, tu vas écrire un programme qui, étant donné une chaine de caractères, retourne la plus longue sous-chaine dupliquée dans la chaine donnée en entrée. Un exemple sera peut-être plus parlant :

"banana" => "ana"
"abcd" => ""

Aller c'est parti !

Écrire le test d’abord

On peut voir ça comme une tradition maintenant, on va commencer par le cas le plus simple.

;; strings-test.scm

(use-modules (srfi srfi-64)
             (strings))
             
(test-begin "harness-strings")

(test-equal "empty string has no duplicated substring"
  ""
  (longest-duplicated-substring-in ""))

(test-end "harness-strings")

Essayer et lancer le test

$ guile -L . strings-test.scm

La compilation échoue (on traite ce retour de la même façon qu'un test qui échoue).

Écrire le minimum de code pour faire compiler le test et vérifier la raison de son échec

Voici le code qui permet de lever d'erreur de compilation (on crée un fichier dans lequel on définie le module strings) :

;; strings.scm

(define-module (strings))

On relance le test.

$ guile -L . strings-test.scm
;;; note: auto-compilation is enabled, set GUILE_AUTO_COMPILE=0
;;;       or pass the --no-auto-compile argument to disable.
;;; compiling /home/jeko/Workspace/ghh-exercises/strings/strings-test.scm
;;; compiling ./strings.scm
;;; compiled /home/jeko/.cache/guile/ccache/3.0-LE-8-4.5/home/jeko/Workspace/ghh-exercises/strings/strings.scm.go
;;; strings-test.scm:8:3: warning: possibly unbound variable `longest-duplicated-substring-in'
;;; compiled /home/jeko/.cache/guile/ccache/3.0-LE-8-4.5/home/jeko/Workspace/ghh-exercises/strings/strings-test.scm.go
%%%% Starting test harness-strings  (Writing full log to "harness-strings.log")
strings-test.scm:6: FAIL empty string has no duplicated substring
# of unexpected failures  1

Ça compile. Donc le code ajouté précédemment nous a bien permis de progresser. Cependant, on peut toujours observer un avertissement dans les traces de compilation :

;;; strings-test.scm:8:3: warning: possibly unbound variable `longest-duplicated-substring-in'

Ajoutons le minimum de code pour lever l'avertissement (et je vais forcer l'échec, donc je défini une procédure qui ne retourne pas "") :

;; strings.scm

(define-module (strings))

(define-public (longest-duplicated-substring-in a-string)
  -1)

En relançant le test on voit bien qu'il n'y a plus ni avertissement, ni erreur à la compilation.

Dans le rapport de test harness-strings.log, on peut voir que le test a échoué car on attendait la valeur "" mais notre procédure fraichement définie retourne -1.

Écrire juste assez de code pour faire passer le test

;; strings.scm

(define-module (strings))

(define-public (longest-duplicated-substring-in a-string)
  "")

Nouvelle valeur retournée, le test passe à la prochaine exécution !

Réusiner

Dans le harnais de tests, on va éliminer une dupplication : le nom de la suite de tests.

;; strings-test.scm

(use-modules (srfi srfi-64)
             (strings))

(define test-suite-name "harness-strings")

(test-begin test-suite-name)

(test-equal "empty string has no duplicated substring"
  ""
  (longest-duplicated-substring-in ""))

(test-end test-suite-name)

Écrire le test d’abord

On a donc un premier test avec une chaine qui ne contient pas de sous-chaine dupliquée. Pour ce deuxième test, on va partir sur une chaine qui contient une sous-chaine dupliquée, la plus simple possible (un seul caractère dupliqué).

;; strings-test.scm

(use-modules (srfi srfi-64)
             (strings))

(define test-suite-name "harness-strings")

(test-begin test-suite-name)

(test-equal "empty string has no duplicated substring"
  ""
  (longest-duplicated-substring-in ""))

(test-equal "single char duplicated substring"
  "a"
  (longest-duplicated-substring-in "aa"))

(test-end test-suite-name)

On s'attend bien évidemment à ce que premier test passe et que le deuxième test échoue.

Essayer et lancer le test

$ guile -L . strings-test.scm

Écrire le minimum de code pour faire compiler le test et vérifier la raison de son échec

Allons regarder dans le rapport de tests que ce deuxième test échoue pour la bonne raison :

Test end:
  result-kind: fail
  actual-value: ""
  expected-value: "a"

Jusqu'ici tout est OK ! Notre procédure ne peut renvoyer que "" alors que notre test attend maintenant "a".

Écrire juste assez de code pour faire passer le test

;; strings.scm

(define-module (strings))

(define-public (longest-duplicated-substring-in a-string)
  (if (string-null? a-string)
      ""
      "a"))

Tu peux exécuter les tests à nouveau pour confirmer que tous les tests passent à présent !

$ guile -L . strings-test.scm
;;; note: source file ./strings.scm
;;;       newer than compiled /home/jeko/.cache/guile/ccache/3.0-LE-8-4.5/home/jeko/Workspace/ghh-exercises/strings/strings.scm.go
;;; note: auto-compilation is enabled, set GUILE_AUTO_COMPILE=0
;;;       or pass the --no-auto-compile argument to disable.
;;; compiling ./strings.scm
;;; compiled /home/jeko/.cache/guile/ccache/3.0-LE-8-4.5/home/jeko/Workspace/ghh-exercises/strings/strings.scm.go
%%%% Starting test harness-strings  (Writing full log to "harness-strings.log")
# of expected passes      2

Réusiner

Rien de flagrant ici.

Écrire le test d’abord

Ce deuxième test spécifie le comportement de la procédure lorsqu'on lui passe une chaine de caractères contenant deux fois le même caractère. Mais il ne teste qu'un seul cas. Avec ce troisième test, on va généraliser. Dans le jargon du TDD, on appelle cette technique la triangulation.

;; strings-test.scm

(use-modules (srfi srfi-64)
             (strings))

(define test-suite-name "harness-strings")

(test-begin test-suite-name)

(test-equal "empty string has no duplicated substring"
  ""
  (longest-duplicated-substring-in ""))

(test-equal "only twice a char has a duplicated substring"
  "a"
  (longest-duplicated-substring-in "aa"))

(test-equal "only twice a char has a duplicated substring other case"
  "z"
  (longest-duplicated-substring-in "zz"))

(test-end test-suite-name)

Essayer et lancer le test

$ guile -L . strings-test.scm                                
;;; note: source file /home/jeko/Workspace/ghh-exercises/strings/strings-test.scm
;;;       newer than compiled /home/jeko/.cache/guile/ccache/3.0-LE-8-4.5/home/jeko/Workspace/ghh-exercises/strings/strings-test.scm.go
;;; note: auto-compilation is enabled, set GUILE_AUTO_COMPILE=0
;;;       or pass the --no-auto-compile argument to disable.
;;; compiling /home/jeko/Workspace/ghh-exercises/strings/strings-test.scm
;;; compiled /home/jeko/.cache/guile/ccache/3.0-LE-8-4.5/home/jeko/Workspace/ghh-exercises/strings/strings-test.scm.go
%%%% Starting test harness-strings  (Writing full log to "harness-strings.log")
strings-test.scm:16: FAIL twice a char has a duplicated substring other case
# of expected passes      2
# of unexpected failures  1

Comme on pouvait s'y attendre, notre troisième test échoue.

Écrire le minimum de code pour faire compiler le test et vérifier la raison de son échec

Puisqu'il n'y a pas d'erreur de compilation, tu peux aller vérifier que le test échoue bien parce qu'on attend que longest-duplicated-substring-in retourne "z" alors qu'elle ne returne que "a".

Test begin:
  test-name: "twice a char has a duplicated substring other case"
  source-file: "strings-test.scm"
  source-line: 16
  source-form: (test-equal "twice a char has a duplicated substring other case" "z" (longest-duplicated-substring-in "zz"))
Test end:
  result-kind: fail
  actual-value: "a"
  expected-value: "z"

Écrire juste assez de code pour faire passer le test

Plutôt que de retourner la même valeur "a" si la chaine de caractères n'est pas vide, modifions le code pour qu'il retourne une nouvelle chaine de caractères contenant le premier caractère de la chaine passée en entrée.

;; strings.scm

(define-module (strings))

(define-public (longest-duplicated-substring-in a-string)
  (if (string-null? a-string)
      ""
      (substring a-string 0 1)))

Maintenant, tout est vert !

Réusiner

La ligne (substring a-string 0 1) pourrait expliciter un peu plus son intention. Voilà ma proposition :

;; strings.scm

(define-module (strings))

(define-public (longest-duplicated-substring-in a-string)
  (if (string-null? a-string)
      ""
      (string-first-char a-string)))

(define (string-first-char a-string)
  (substring a-string 0 1))

N'oublie pas de rejouer les tests pour vérifier que je n'ai pas introduit de régression !

Écrire le test d’abord

Pour le dernier test de ce chapitre, on va gérer le cas d'une chaine de caractère qui contient deux caractères différents. Pourquoi ce test ? Parce que c'est le cas qui me parait être le plus simple que notre procédure ne gère pas encore. Chaque nouveau test doit être rouge !

;; strings-test.scm

(use-modules (srfi srfi-64)
             (strings))

(define test-suite-name "harness-strings")

(test-begin test-suite-name)

(test-equal "empty string has no duplicated substring"
  ""
  (longest-duplicated-substring-in ""))

(test-equal "twice a char as a string has a duplicated substring"
  "a"
  (longest-duplicated-substring-in "aa"))

(test-equal "only twice a char as a string has a duplicated substring other case"
  "z"
  (longest-duplicated-substring-in "zz"))

(test-equal "only two different chars as a string has not duplicated substring"
  ""
  (longest-duplicated-substring-in "bc"))

(test-end test-suite-name)

Essayer et lancer le test

$ guile -L . strings-test.scm 
;;; note: source file /home/jeko/Workspace/ghh-exercises/strings/strings-test.scm
;;;       newer than compiled /home/jeko/.cache/guile/ccache/3.0-LE-8-4.5/home/jeko/Workspace/ghh-exercises/strings/strings-test.scm.go
;;; note: auto-compilation is enabled, set GUILE_AUTO_COMPILE=0
;;;       or pass the --no-auto-compile argument to disable.
;;; compiling /home/jeko/Workspace/ghh-exercises/strings/strings-test.scm
;;; compiled /home/jeko/.cache/guile/ccache/3.0-LE-8-4.5/home/jeko/Workspace/ghh-exercises/strings/strings-test.scm.go
%%%% Starting test harness-strings  (Writing full log to "harness-strings.log")
strings-test.scm:22: FAIL only two different chars as a string has not duplicated substring
# of expected passes      3
# of unexpected failures  1

Sans surprise, notre nouveau test ne passe pas ! Et c'est tant mieux !

Écrire le minimum de code pour faire compiler le test et vérifier la raison de son échec

Pas de problème de compilation, donc on peut directement regarder la raison de l'échec :

Test begin:
  test-name: "only two different chars as a string has not duplicated substring"
  source-file: "strings-test.scm"
  source-line: 22
  source-form: (test-equal "only two different chars as a string has not duplicated substring" "" (longest-duplicated-substring-in "bc"))
Test end:
  result-kind: fail
  actual-value: "b"
  expected-value: ""

Alors que notre nouveau test s'attend à ce que l'on retourne une chaine vide, notre procédure retourne le premier caractère de la chaine donnée en entrée.

Écrire juste assez de code pour faire passer le test

;; strings.scm

(define-module (strings))

(define-public (longest-duplicated-substring-in a-string)
  (if (string-null? a-string)
      ""
      (if (string=? (substring a-string 0 1) (substring a-string 1 2))
          (string-first-char a-string)
          "")))

(define (string-first-char a-string)
  (substring a-string 0 1))

Et voilà le travail !

$ guile -L . strings-test.scm 
;;; note: source file ./strings.scm
;;;       newer than compiled /home/jeko/.cache/guile/ccache/3.0-LE-8-4.5/home/jeko/Workspace/ghh-exercises/strings/strings.scm.go
;;; note: auto-compilation is enabled, set GUILE_AUTO_COMPILE=0
;;;       or pass the --no-auto-compile argument to disable.
;;; compiling ./strings.scm
;;; compiled /home/jeko/.cache/guile/ccache/3.0-LE-8-4.5/home/jeko/Workspace/ghh-exercises/strings/strings.scm.go
%%%% Starting test harness-strings  (Writing full log to "harness-strings.log")
# of expected passes      4

Réusiner

Éliminer les duplication et désimbriquer les if !

;; strings.scm

(define-module (strings))

(define-public (longest-duplicated-substring-in a-string)
  (if (and (not (string-null? a-string)) (twice-char? a-string))
      (string-first-char a-string)
      ""))

(define (twice-char? a-string)
  (string=? (string-first-char a-string) (string-second-char a-string)))

(define (string-first-char a-string)
  (substring a-string 0 1))

(define (string-second-char a-string)
  (substring a-string 1 2))

Quatre tests, tous verts !

$ guile -L . strings-test.scm 
;;; note: source file ./strings.scm
;;;       newer than compiled /home/jeko/.cache/guile/ccache/3.0-LE-8-4.5/home/jeko/Workspace/ghh-exercises/strings/strings.scm.go
;;; note: auto-compilation is enabled, set GUILE_AUTO_COMPILE=0
;;;       or pass the --no-auto-compile argument to disable.
;;; compiling ./strings.scm
;;; compiled /home/jeko/.cache/guile/ccache/3.0-LE-8-4.5/home/jeko/Workspace/ghh-exercises/strings/strings.scm.go
%%%% Starting test harness-strings  (Writing full log to "harness-strings.log")
# of expected passes      4

La solution n'est pas complète et je t'invite à t'exercer en allant encore plus loin. Tu peux même m'envoyer tes tests et tes sources si tu souhaites que je te fasse un retour dessus. Ça me fera plaisir !

Conclusion

• More TDD practice
• Strings
• Triangulation