Stringhe

In questo capitolo affronteremo le stringhe, un tipo di dati comune nei linguaggi di programmazione.

In questo capitolo scriverai un programma che, data una stringa, restituisce la più lunga sotto-stringa duplicata nella stringa di partenza. Un esempio sarà forse più esplicativo:

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

Procediamo!

Scrivere prima il test

Ora possiamo vederla come una tradizione, inizieremo con il caso più semplice.

;; 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")

Provare a eseguire il test

$ guile -L . strings-test.scm

La compilazione fallisce (questo feedback viene trattato come un test fallito).

Scrivere la quantità minima di codice per l'esecuzione del test e controllare l'output del test non riuscito.

Ecco il codice che elimina l'errore di compilazione (creiamo un file in cui definiamo il modulo strings):

;; strings.scm

(define-module (strings))

Eseguiamo nuovamente il 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

Compila correttamente. Quindi il codice aggiunto in precedenza ci ha aiutato a progredire. Tuttavia, possiamo ancora vedere un avviso nelle tracce di compilazione:

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

Aggiungiamo il codice minimo per eliminare l'avviso (forzerò il fallimento, quindi definisco una procedura che non restituisce ""):

;; strings.scm

(define-module (strings))

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

Eseguendo nuovamente il test, puoi notare che non ci sono più avvisi o errori di compilazione.

Nel report del test harness-strings.log, si può vedere che il test è fallito perché ci si aspettava il valore "", ma la nostra procedura appena definita restituisce -1.

Scrivere abbastanza codice per farlo passare

;; strings.scm

(define-module (strings))

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

Nuovo valore restituito, il test è superato!

Refactor

Nel test harness, elimineremo una duplicazione: il nome della suite di test.

;; 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)

Scrivere prima il test

Abbiamo quindi un primo test con una stringa che non contiene una sottostringa duplicata. Per questo secondo test, inizieremo con una stringa che contiene una sottostringa duplicata, la più semplice possibile (un solo carattere duplicato).

;; 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)

Prevediamo che il primo test passi e il secondo fallisca.

Provare ed eseguire il test

$ guile -L . strings-test.scm

Scrivere la quantità minima di codice per l'esecuzione del test e controllare l'output del test non riuscito.

Guardiamo il rapporto di prova per vedere che questo secondo test fallisce per una buona ragione:

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

Fin qui tutto bene! La nostra procedura può restituire solo "", mentre il nostro test ora si aspetta "a".

Scrivere abbastanza codice per farlo passare

;; strings.scm

(define-module (strings))

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

Esegui nuovamente i test per confermare che vengano tutti superati!

$ 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

Refactor

Non c'è nulla di ovvio qui.

Scrivere prima il test

Questo secondo test specifica il comportamento della procedura quando le viene passata una stringa contenente lo stesso carattere due volte. Ma verifica solo un caso. Con questo terzo test, generalizzeremo. Nel gergo TDD, questa tecnica si chiama triangolazione.

;; 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)

Provare ed eseguire il 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

Come previsto, il terzo test fallisce.

Scrivere la quantità minima di codice per l'esecuzione del test e controllare l'output del test che fallisce

Poiché non c'è alcun errore in fase di compilazione, si può verificare che il test fallisce perché ci si aspetta che longest-duplicated-substring-in restituisca "z" quando invece restituisce solo "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"

Scrivere abbastanza codice per farlo passare

Invece di restituire lo stesso valore "a" se la stringa non è vuota, modifichiamo il codice in modo che restituisca una nuova stringa contenente il primo carattere della stringa di input.

;; strings.scm

(define-module (strings))

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

Dovrebbe essere tutto "green" adesso.

Refactor

La riga (substring a-string 0 1) potrebbe rendere la sua funzione un po' più esplicita. Ecco la mia proposta:

;; 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))

Non dimenticate di riprodurre i test per assicurarvi che non sia stata introdotta alcuna regressione!

Scrivere prima il test

Per l'ultimo test di questo capitolo, gestiremo il caso di una stringa che contiene due caratteri diversi. Perché questo test? Perché è il caso che mi sembra più semplice e che la nostra procedura non gestisce ancora. Ogni nuovo test deve essere "red"!

;; 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)

Provare ed eseguire il 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

Nessuna sorpresa, il nostro nuovo test non viene superato! E questo è un bene!

Scrivere la quantità minima di codice per l'esecuzione del test e controllare l'output del test che fallisce

Nessun problema di compilazione, quindi possiamo esaminare direttamente il motivo del fallimento:

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: ""

Mentre il nuovo test si aspetta di restituire una stringa vuota, la nostra procedura restituisce il primo carattere della stringa in ingresso.

Scrivere il codice sufficiente a superare il 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))

Ed ecco che si parte!

$ 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

Refactor

Eliminiamo i duplicati e sbarazziamoci degli `if' annidati.

;; 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))

Quattro test, tutti "green"!

$ 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 soluzione non è completa e ti invito a esercitarti andando oltre. Puoi anche inviarmi i tuoi test e le tue fonti se vuoi che ti dia un feedback. Sarò felice di farlo!